Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

McMaster University

$23,000.00

Dynamics in exchangeable partitions and hierarchies

FY 2020-21

Summary
Suppose that we wish to have a computer program automatically organize a large collection of websites by grouping them according to topic. The program observes that the words “clinical” and “injury” often occur together on the same pages, while the words “baste” and “chop” often occur together on others, thus forming the basis for two categories: medical and cooking websites. We could define our categories in advance, or we could allow the program to identify categories organically. In the latter case, we would use a non-parametric Bayesian (NPB) clustering algorithm. Such algorithms are based on probabilistic models that are exchangeable, meaning, loosely, that the order in which we receive data is meaningless i.e. the first and second websites are as likely to share the same topic as are the eighth and one hundredth. The Chinese restaurant process (CRP) is one such model. Imagine customers entering a vast dim sum restaurant with giant tables. The first customer must sit alone. Subsequent customers choose seats at random according to the following rule: the nth customer will join a table with m other customers with probability m/n, or will sit alone with probability 1/n. In our example above, customers and tables represent websites and categories. It is not obvious, but the CRP is exchangeable: customers 1 and 2 are as likely to sit together as customers 8 and 100. My research concerns models for random growth or change in exchangeable structures. The CRP is a growth process on exchangeable partitions. Another example is the reseating Chinese restaurant process (RCRP), in which, instead of beginning with an empty restaurant and having new customers enter, we begin with customers already seated, and at each step a randomly chosen customer stands up and randomly chooses a new seat. This can be used as a model for updating our guesses on which websites belong to which categories. In the next five years, I will address the following problems: (1) describe, in various ways, the limit of the RCRP on vast numbers of customers, and (2) introduce and study growth processes, like the CRP, for exchangeable hierarchies: partitions in which we sub-partition the segments repeatedly, in order give models for documents partitioned according to topic, sub-topic, sub-sub-topic, etc.. Problem (1) has been widely studied since 2010. In recent years, I've made major progress towards describing how the numbers of customers at each table change over time, in the limit. I believe that I am close to completing that description. Afterwards, I will work on describing a version in which we can see where each customer is seated. For problem (2), only one model for growing exchangeable hierarchies has been well-studied: the nested Chinese restaurant process. But I have written two papers that find that exchangeable hierarchies can exhibit other behaviors. I plan to introduce new, more flexible models, which can then be applied to nested clustering problems.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2020-06907
Name nom
Forman, Noah
Department département
Mathematics & Statistics
Organization id
27
Institution établissement
McMaster University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2020
Award amount
23000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
3007
Research subject group en
Statistics and probability
Research subject group fr
Statistique et probabilité
Research subject en
Stochastic processes
Research subject fr
Processus stochastiques
Installment
inst:1-5
Partie
5
Nb partie
5
Application title
Dynamics in exchangeable partitions and hierarchies
Keyword
NSERC
Application summary
Suppose that we wish to have a computer program automatically organize a large collection of websites by grouping them according to topic. The program observes that the words “clinical” and “injury” often occur together on the same pages, while the words “baste” and “chop” often occur together on others, thus forming the basis for two categories: medical and cooking websites. We could define our categories in advance, or we could allow the program to identify categories organically. In the latter case, we would use a non-parametric Bayesian (NPB) clustering algorithm. Such algorithms are based on probabilistic models that are exchangeable, meaning, loosely, that the order in which we receive data is meaningless i.e. the first and second websites are as likely to share the same topic as are the eighth and one hundredth. The Chinese restaurant process (CRP) is one such model. Imagine customers entering a vast dim sum restaurant with giant tables. The first customer must sit alone. Subsequent customers choose seats at random according to the following rule: the nth customer will join a table with m other customers with probability m/n, or will sit alone with probability 1/n. In our example above, customers and tables represent websites and categories. It is not obvious, but the CRP is exchangeable: customers 1 and 2 are as likely to sit together as customers 8 and 100. My research concerns models for random growth or change in exchangeable structures. The CRP is a growth process on exchangeable partitions. Another example is the reseating Chinese restaurant process (RCRP), in which, instead of beginning with an empty restaurant and having new customers enter, we begin with customers already seated, and at each step a randomly chosen customer stands up and randomly chooses a new seat. This can be used as a model for updating our guesses on which websites belong to which categories. In the next five years, I will address the following problems: (1) describe, in various ways, the limit of the RCRP on vast numbers of customers, and (2) introduce and study growth processes, like the CRP, for exchangeable hierarchies: partitions in which we sub-partition the segments repeatedly, in order give models for documents partitioned according to topic, sub-topic, sub-sub-topic, etc.. Problem (1) has been widely studied since 2010. In recent years, I've made major progress towards describing how the numbers of customers at each table change over time, in the limit. I believe that I am close to completing that description. Afterwards, I will work on describing a version in which we can see where each customer is seated. For problem (2), only one model for growing exchangeable hierarchies has been well-studied: the nested Chinese restaurant process. But I have written two papers that find that exchangeable hierarchies can exhibit other behaviors. I plan to introduce new, more flexible models, which can then be applied to nested clustering problems.