Dynamics in exchangeable partitions and hierarchies

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

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.