Dynamics in exchangeable partitions and 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.