Dynamics in exchangeable partitions and hierarchies

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

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

假设我们希望有一个计算机程序自动组织大量的网站，根据主题对它们进行分组。该计划观察到，“临床”和“伤害”这两个词经常在同一页面上出现，而“baste”和“chop”这两个词经常在其他页面上出现，从而形成了两个类别的基础：医疗和烹饪网站。我们可以预先定义类别，或者我们可以让程序有机地识别类别。在后一种情况下，我们将使用非参数贝叶斯（NPB）聚类算法。这些算法基于可交换的概率模型，这意味着我们接收数据的顺序是没有意义的-即第一和第二个网站与第八个和第一百个网站一样可能共享相同的主题。中国餐馆流程（CRP）就是这样一种模式。想象一下，顾客走进一家摆着巨大桌子的大点心店。第一个顾客必须独自坐着。随后的顾客根据以下规则随机选择座位：第n个顾客将以概率m/n与其他m个顾客加入一张桌子，或者以概率1/n单独坐着。在上面的示例中，客户和表代表网站和类别。这并不明显，但CRP是可交换的：顾客1和2坐在一起的可能性与顾客8和100坐在一起的可能性一样。我的研究涉及可交换结构的随机增长或变化模型。CRP是在可交换分区上的生长过程。另一个例子是重新就座的中国餐馆过程（RCRP），在这个过程中，我们开始的不是一个空的餐馆，让新的顾客进入，而是从已经就座的顾客开始，在每一步中，一个随机选择的顾客站起来，随机选择一个新的座位。这可以作为一个模型来更新我们对哪些网站属于哪些类别的猜测。在接下来的五年里，我将解决以下问题：（1）以各种方式描述RCRP对大量客户的限制，以及（2）介绍和研究可交换层次结构的增长过程，如CRP：我们重复子分区段的分区，以便为根据主题，子主题，子子主题等划分的文档提供模型。自2010年以来，问题（1）得到了广泛的研究。近年来，我在描述每张桌子上的客户数量如何随着时间的推移而变化方面取得了重大进展。我相信我即将完成这一描述。之后，我将描述一个版本，我们可以看到每个客户的座位。对于问题（2），只有一个模型的增长可交换的层次结构已被充分研究：嵌套中餐厅过程。但我写了两篇论文，发现可交换的层次结构可以表现出其他行为。我计划引入新的、更灵活的模型，然后将其应用于嵌套聚类问题。