Dynamics in exchangeable partitions and hierarchies

可交换分区和层次结构中的动态

• 批准号: RGPIN-2020-06907
• 负责人: Forman, Noah
• 金额: $ 1.68万
• 依托单位: McMaster University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=718481
• 关键词: Dynamics; exchangeable; partitions; hierarchies

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.

假设我们希望有一个计算机程序通过根据主题对网站进行分组来自动组织大量网站。该程序观察到，“临床”和“伤害”这两个词经常在同一页面上同时出现，而“酱”和“剁”这两个词经常在其他页面上同时出现，从而形成了两类网站的基础：医疗和烹饪网站。