索鸟网

  1. 首页
  2. 什么叫做CRP(Chinese Restaurant Process),中国餐馆过程在hlda中的使用

什么叫做CRP(Chinese Restaurant Process),中国餐馆过程在hlda中的使用


Author : Jasperyang
School : BUPT

写在前面

是这样的,我在看Blei大牛03年的hlda论文中提到了CRP,觉得这是个很有意思的数学现象,并且深入了解后便于后面的研究,便通过查找不同资料加以理解。

正文

中国餐馆过程是一个典型的Dirichlet过程混合模型。可以将中国餐馆过程描述如下:

假设一个中国餐馆中,可以有无限个桌子,来吃饭的第一位顾客坐了第一张桌子。

对于每一位顾客,都按照下面的规则来选择桌子坐下,对于第n个顾客:

$$ \frac{n_{k}}{a_{0}+n-1}$$

其中,nk 表示第k个桌子上已经有的顾客数。n−1表示在这个顾客之前,已有的顾客总数。 a0就是个参数(需设置)。

顾客可以选择坐在一个没有人坐的桌子上K+1的概率为

$$ \frac{a_{0}}{a_{0}+n-1}$$

在这里,可以将顾客类比成数据,将每一张桌子类别成类。

这么讲不具体,下面贴个R语言的代码详细说。



# Generate table assignments for `num_customers` customers, according to
  # a Chinese Restaurant Process with dispersion parameter `alpha`.
  #
  # returns an array of integer table assignments
  def chinese_restaurant_process(num_customers, alpha)
   return [] if num_customers <= 0
  
   table_assignments = [1] # first customer sits at table 1
   next_open_table = 2 # index of the next empty table
  
   # Now generate table assignments for the rest of the customers.
   1.upto(num_customers - 1) do |i|
     if rand < alpha.to_f / (alpha + i)
       # Customer sits at new table.
       table_assignments << next_open_table
       next_open_table += 1
     else
       # Customer sits at an existing table.
       # He chooses which table to sit at by giving equal weight to each
       # customer already sitting at a table. 
       which_table = table_assignments[rand(table_assignments.size)]
       table_assignments << which_table
     end
   end
  
   table_assignments
  end
  
  

输出如下:

> chinese_restaurant_process(num_customers = 10, alpha = 1)
  1, 2, 3, 4, 3, 3, 2, 1, 4, 3 # table assignments from run 1
  1, 1, 1, 1, 1, 1, 2, 2, 1, 3 # table assignments from run 2
  1, 2, 2, 1, 3, 3, 2, 1, 3, 4 # table assignments from run 3
  
  > chinese_restaurant_process(num_customers = 10, alpha = 3)
  1, 2, 1, 1, 3, 1, 2, 3, 4, 5
  1, 2, 3, 3, 4, 3, 4, 4, 5, 5
  1, 1, 2, 3, 1, 4, 4, 3, 1, 1
  
  > chinese_restaurant_process(num_customers = 10, alpha = 5)
  1, 2, 1, 3, 4, 5, 6, 7, 1, 8
  1, 2, 3, 3, 4, 5, 6, 5, 6, 7
  1, 2, 3, 4, 5, 6, 2, 7, 2, 1
  

这里的alpha就是a0,会发现,a0越大,最后分出来的桌子可能会越多。

以上这么讲是 Hierarchical Topic Models and the Nested Chinese Restaurant Process 这篇论文的原意。

这个位置选择方式也就是公式的合理性是在别的文章中讲解的。

首先需要介绍一下狄利克雷过程。

Dirichlet Process (DP)被称为分布的分布。从DP抽取出的每个样本(一个函数)都可以被认为是一个离散随机变量的分布函数,这个随机变量以非零概率值在可数无穷个离散点上取值。比较有意思的是,从DP可以推导出几个非常著名的问题: Chinese Restaurant Process (CRP)、Polya Urn Scheme和Stick-breaking Process。简单的介绍可以见Edwin Chen的博文“Infinite Mixture Models with Nonparametric Bayes and the Dirichlet Process”,这篇详解了包括dp,crp等好几个过程,但是没有讲数学推导。

DP的特性使得它在非参数贝叶斯聚类模型中可以被用作参数的先验分布。Dirichlet Process Mixture (DPM)是这种非参数贝叶斯聚类模型中的一个典型代表。DPM可以认为是有限混合(Finite Mixture,FM)模型的一个推广,FM(如Gaussian Mixture模型)必须首先给定类数,而DPM则不需要,它可以依据数据自行判断类数。理论上来说,DPM的类数随着log(样本点数量)的增长速度增长。目前研究者已经提出了很多训练DPM的算法,从Gibbs Sampling,到Collapsed Gibbs Sampling,到Variational方法。

想进一步了解DP和DPM的同学,可以去Yee W. Teh的主页上看看,里面可以找到很多相关的papers,slides,presentations,以及用Matlab写的DPM开源软件。想仔细了解DPM的各个算法及具体推导,建议看看Xiaodong Yu的博文,里面也有他总结的一个很详细的学习笔记(虽然里面有一些小笔误),以及更多的参考资料。

在hlda中将这个crp推广到多层级的topic其实很简单,就是先找一家餐馆也就是一个root_topic,然后在这家餐馆里的每个桌子上放的是别的餐馆的名字,一次类推,就可以无限的延续下去。

最后

这篇主要就是讲 Chinese Restaurant Process ,后续的文章我可能会去详解HLDA。

r 论文

来源地址:https://segmentfault.com/a/1190000010694630 版权归作者所有!

相关教程

  • 餐馆中的服务员---垃圾回收

    垃圾制造者的产生,推动了垃圾处理者的出现,所以在我们现在的生活中,人们生产的垃圾都会通过相应的手段去处理掉,而不影响现代人的正常生活。程序来源于生活,所以程序世界也如同现代世界一样,也要产生垃圾。当然,也需要垃圾回收员来处理生产出来的垃圾. 垃圾 在程序世界中,不再被任何变量使用的对像,或者说不再被继续使用的变量就是垃圾。 function(){ v
  • 如何使用HTML5自定义数据属性

    在本文中,我将向你介绍如何使用HTML5自定义数据属性。我还将向你介绍一些开发人员在工作中经常使用的优秀实例。 为什么需要自定义数据属性? 很多时候我们需要存储一些与不同DOM元素相关联的信息。这些信息对于读者来说可能是不需要的,但是可以轻松的访问这些信息将会给我们开发者的工作带来极大的便利。 例如,假设你有一份某个餐饮类网站上所有餐馆的名单。在HT
  • 我的web前端自学之路:什么叫做认真对待前端自学

    上一篇我检讨了自己为什么没有自学好前端,然后给自己为什么学习前端“生拉硬拽”一些了理由。除了有了一些要学习的理由是不够的,因为我还是不知道该怎么认真的学。今天我会谈谈几点对“如何自学”的看法。 努力有那么重要吗 如果从最后的结果来看,努力还真的没那么重要,因为如果没学会的话,准确的是如果自己努力过后自己的生活没有改变的话,那努力有什么用呢。 我觉得其实大多人的“努力”是
  • 以通俗的方式理解关键渲染路径

    以通俗的方式理解关键渲染路径 我在看了 google 的 Critical Rendering Path (中文)后, 想把 CRP(Critical Rendering Path) 用通俗易懂的方式描述出来。 官方文档当然是描述最为详尽且可靠的。 文章里的有些图片是直接引用自官方文档。 如果存在侵权, 立刻删除。 1. 什么是 CRP ? 游览器从开始
  • quartz在spring中的使用

    1.spring配置文件配置 注册自定义作业类 <bean id="myJob" > <property name="string" value="I am quantz job"/> </bean> 配置JobDetail <bean id="jobDetail" >
  • highcharts 在angular中的使用

    网址 https://segmentfault.com/q/10...https://www.hcharts.cn/demo/h...https://github.com/pablojim/h... 安装依赖 npm install highcharts-ng --save 引入依赖 "highcharts/highcharts.src.js", "hi
  • JMS 在 SpringBoot 中的使用

    JMS 在 SpringBoot 中的使用 摘要:本文属于原创,欢迎转载,转载请保留出处:https://github.com/jasonGeng88/blog> 本文所有服务均采用docker容器化方式部署 当前环境 Mac OS 10.11.x docker 1.12.1 JDK 1.8 SpringBoot 1.5 前言 基于之前一
  • 使用ARM模板在Azure中国大规模部署DC/OS集群

    容器技术是目前非常流行的技术,尤其是在以Docker作为容器引擎的推动下,让容器的轻量级,可移植,自包含,隔离性等的上了一个新的台阶,目前谈及Dev/Ops,CI/CD很少能够绕过Docker的。Azure在去年就推出了容器服务ACS,以其对开源的全面兼容性,开放性,最全面的编排器(DC/OS, Kubernetes,Swarm)支持而广受好评,但在中国和很多地区,AC