变分推断学习笔记(3)——三硬币问题的变分推断解法

变分推断学习笔记系列:

  1. 变分推断学习笔记(1)——概念介绍
  2. 变分推断学习笔记(2)——一维高斯模型的例子
  3. 变分推断学习笔记(3)——三硬币问题的变分推断解法

其实三硬币的例子不写,前面的介绍也够了,写这个纯粹是吃撑了。这次我们采取更加普遍的假设,将原先假设的3枚硬币拓展开来。现在假设有\(K+1\)个骰子,第一个骰子有\(K\)个面,其余的骰子有\(T\)个面。进行如下实验:先掷第一个骰子,根据投出的结果\(Z_k\),选择第\(Z_k\)个骰子再投,观测到投出的\(N\)个结果,每个结果\(w_n\)可能是 \[ 1,3,7,8,3,2,6,9,... \]

可以看到现在第1个骰子投出的标签服从多项分布: \[Z_k \sim Multinomial(\pi)\] 然后剩余骰子投出的面也服从多项分布 \[W_{Z_{kt}} \sim Multinomial(\theta_{Z_k})\] 我们假设,随机变量\(\pi\)\(\theta\)的先验分布为狄利克雷分布,超参分别为\(\alpha\)\(\beta\)

Read More

使用LeanCloud平台为Hexo博客添加文章浏览量统计组件

在原来的wordpress博客中有一个WP-PostViews Plus插件,可以统计每篇文章的浏览量,可以为游客提供热门文章的信息,(顺便满足一下作者的虚荣心)。现在切换到静态博客Hexo了,就需要第三方服务来实现这样的动态数据处理。这里要感谢师弟ariwaranosai给我推荐的LeanCloud平台,以及为hexo博客添加访问次数统计功能(基于BAE)提供的思路。使用LeanCloud的优点是它自己实现了一个AV.view 类,不需要考虑JavaScript的跨站访问问题。

创建Lean Cloud应用

首先一句话介绍Lean Cloud:

LeanCloud(aka. AVOS Cloud)提供一站式后端云服务,从数据存储、实时聊天、消息推送到移动统计,涵盖应用开发的多方面后端需求。

我们只用到它的数据存储部分,具体步骤如下:

  1. 首先到『控制台』创建一个应用,名字随便取。
  2. 点击新建应用的『数据』选项,选择『创建Class』,取名为”Counter“。
  3. 点击新建应用右上角的齿轮,在『应用Key』选项里得到APP ID 和 APP Key,在后面会用到。

修改Hexo页面

新建popular_posts.ejs

首先在theme/你的主题/layout/_widget目录下新建popular_posts.ejs文件,其内容为

1
2
3
4
5
6
7
8
9
<% if (site.posts.length){ %>
<div class="widget-wrap">
<h3 class="widget-title">浏览数目</h3>
<div class="widget">
<ul class="popularlist">
</ul>
</div>
</div>
<% } %>

修改head.ejs

修改theme/你的主题/layout/_partial/head.ejs文件,在head标签的最后插入:

1
2
<script src="https://cdn1.lncld.net/static/js/av-min-1.2.1.js"></script>
<script>AV.initialize("你的APP ID", "你的APP Key");</script>

注意Lean Cloud引用的js文件位置可能会变化,如果代码里位置打不开的话,记得去官方的JavaScript SDK文档找一下最新的位置。

修改after-footer.ejs

修改theme/你的主题/layout/_partial/after-footer.ejs文件,在最后插入:

Read More

博客迁移小记

一点闲话

扯一点闲话,这半年发生了不少事,导致博客断更了半年多。一言难尽,就上一句心灵鸡汤来概括吧,顺便弘扬一下正能量:

所有的事情最后都会有好结局,如果你觉得结局不好,那是因为还没有到最后。

迁移原因

进入正题,这两天闲下来之后,也是起了心思,想把博客从wordpress迁移到静态博客上,原因如下:

  1. 最近用惯了markdown,想更方便地写东西,更加专注于内容。而wordpress没有好用的markdown插件,以前都是写tex里然后往博客上粘贴,太麻烦了。
  2. 作为一个不称职的程序员,用了这么久的wordpress,现在终于想要有一点control every thing的感觉,自己动手折腾个静态博客,顺便学习一下javascript,jquery,css基础。
  3. 还有就是静态博客的普遍优点了,比如不用服务器,省了买空间的钱(免费的Github Pages),访问速度快,容易被搜索引擎抓取等。

静态博客先使用了Github推荐的Jekyll,发现需要自己搞的东西太多,于是转用了基于node.js的Hexo。Hexo有以下优点:

  1. 生成文章速度非常快。
  2. 命令简单,只需要会hexo nhexo ghexo shexo d就能 搞定一切。
  3. 中文用户多,文档和插件比较全。
  4. 能通过插件解决markdwon和mathjax冲突问题。

搭建参考

在搭建过程,主要参考了以下文章:

以上的文章已经足够基本了解hexo博客的整个搭建过程了,只需要照做即可。我的博客主题是基于landscape-plus改的,另外参考了howiefh的 landscape-f主题,添加了多说最近评论小部件以及我自己写的浏览计数小部件。图片都托管在七牛云存储上。

迁移问题

在博客从wordpress迁移到hexo的过程中,主要碰到的问题及解决办法如下:

  1. 原wordpress博客链接的死链问题。原先我wordpress文章链接用的是坑爹的默认生成方式,是通过?传p的参数来获取文章的URL。问题是p是个随机数字,我又没办法在静态页面上动态地获取p的值做重定向。现在折衷的解决办法是暂时不改域名,先用着github提供的二级域名,然后在原域名上用wordpress的Redirect插件对文章链接做301重定向,看看搜索引擎能不能把原文章的URL给改了。 (我会尽快把这个域名的DNS解析转到github的博客上来)。目前你可以通过www.crescentmoon.info访问原wordpress博客,但是点击任何文章都会跳转到新博客来:-D。这个没有成功,请从搜索引擎点文章名过来的读者在博客页面寻找一下那篇文章吧囧。
  2. mathjax和markdown渲染冲突问题。因为markdown的解析要优先于mathjax,所以经常会导致mathjax渲染失败,需要玩一些tricks,比如latex语法中的下标’_‘要改成转义的’\_’, equation环境需要套一个div标签或者rawblock环境等,带来了无穷无尽的麻烦。还好hexo上有大神写的hexo-renderer-pandoc插件,用pandoc去代替默认的markdown渲染器,完美地解决了这个问题。
  3. 文章的浏览数小部件问题。原先我的wordpress有个显示文章浏览数的小插件,现在换成静态网页了,就必须用第三方的服务实现这个功能,具体请见下一篇博客啦。
  4. 多说评论没有跟过来的问题,这个正在解决中。

概率图模型简介

介绍

定义

概率图模型(Graphical Model)是概率论和图论之间的桥梁,概率图模型的基本想法来自模块的概念,即一个复杂系统是由简单的部分所联合而成的。概率论部分告诉我们哪些部分是耦合在一起的,然后提供推断模型的方法,而图论部分给我们一个非常直观的认识,把拥有相互关系的变量看做数据结构,从而导出一般化的方法来解决这个问题。很多经典的多元概率系统,比如混合模型,因子分析,隐含马尔科夫模型,Kalman filter 和Ising model等,从概率图模型的角度来看,都可以看做普遍隐含形成过程的一种实例表现。这意味着,一旦在某个系统上有什么特别的方法发现,就很容易推广到一系列的模型中去。除此之外,概率图模型还非常自然地提供了设计新系统的方法。

在概率图模型中,点代表随机变量,点与点之间边的存在与否代表了点与点之间是存在条件依赖。点与边的组合描绘了联合概率分布的特征结构。假设有\(N\)个二元随机变量,在没有任何信息帮助的情况下,联合分布\(P(X_1,\ldots,X_N)\),需要\(O(2^N)\)个参数。而通过概率图描绘点与点之间的条件关系之后,表示联合分布,所需要的参数会减少很多,这对后面的模型的推断和学习是有帮助的。

概率图模型主要分为两种,无向图(也叫Markov random fields)和有向图(也叫Bayesian networks),前者多用于物理和图像领域,后者多用于AI和机器学习,具体的基本就不多介绍了。下面给出一个简单贝叶斯网络的例子。

QQ截图20140224133640

这里Cloudy指是否多云,Sprinkler指洒水器是否打开,Rain指是否有雨, WetGrass指草地是否湿了。

Read More

变分推断学习笔记(2)——一维高斯模型的例子

变分推断学习笔记系列:

  1. 变分推断学习笔记(1)——概念介绍
  2. 变分推断学习笔记(2)——一维高斯模型的例子
  3. 变分推断学习笔记(3)——三硬币问题的变分推断解法

举一个一元高斯模型的例子。假设我们有数据\(\mathbf{X}=\{x_1,\ldots,x_M\}\),要推断平均值\(\mu\)和精度\(\tau(1/\sigma)\)的后验概率分布。 写出似然 \[\begin{equation} p(\mathbf{X}|\mu,\tau)=(\frac{\tau}{2\pi})^{N/2}\exp\{-\frac{\tau}{2}\sum^N_{n=1}(x_n-\mu)^2\} \end{equation}\] 其中\(\mu,\tau\)各自服从先验分布 \[\begin{equation}p(\mu|\tau)=N(\mu|\mu,(\lambda_0\tau)^{-1})\end{equation}\] \[\begin{equation}p(\tau)=Gam(\tau|a_0,b_0)\end{equation}\] 其中Gam为Gamma分布(见备注1)。

通用的估计方法

好,我们现在假设\(q\)之间的分布都独立。 \[\begin{equation}q(\mu,\tau)=q_u(\mu)q_r(\tau)\end{equation}\]

Read More

变分推断学习笔记(1)——概念介绍

变分推断学习笔记系列:

  1. 变分推断学习笔记(1)——概念介绍
  2. 变分推断学习笔记(2)——一维高斯模型的例子
  3. 变分推断学习笔记(3)——三硬币问题的变分推断解法

问题描述

变分推断是一类用于贝叶斯估计和机器学习领域中近似计算复杂(intractable)积分的技术,它广泛应用于各种复杂模型的推断。本文是学习PRML第10章的一篇笔记,错误或不足的地方敬请指出。

先给出问题描述。记得在上一篇EM的文章中,我们有一个观察变量\(\mathbf{X}=\{x^{\{1\}},\ldots,x^{\{m\}}\}\)和隐藏变量\(\mathbf{Z}=\{z^{\{1\}},\ldots,z^{\{m\}}\}\), 整个模型\(p(\mathbf{X},\mathbf{Z})\)是个关于变量\(\mathbf{X},\mathbf{Z}\)的联合分布,我们的目标是得到后验分布\(P(\mathbf{Z}|\mathbf{X})\)的一个近似分布。

在之前介绍过Gibbs Sampling这一类Monte Carlo算法,它们的做法就是通过抽取大量的样本估计真实的后验分布。而变分推断不同,与此不同的是,变分推断限制近似分布的类型,从而得到一种局部最优,但具有确定解的近似后验分布。

之前在EM算法的介绍中我们有似然的式子如下: \[\begin{equation}\ln p(\mathbf{X})=L(q)+KL(q||p)\end{equation}\] 其中
\[\begin{equation}L(q)=\int q(\mathbf{Z})\ln{\frac{p(\mathbf{X},\mathbf{Z})}{q(\mathbf{Z})}}d\mathbf{Z}\end{equation}\]
\[\begin{equation}KL(q||p)=-\int q(\mathbf{Z}) \ln{\frac{p(\mathbf{Z}|\mathbf{X})}{q(\mathbf{Z})}}d\mathbf{Z}\end{equation}\]

这里公式中不再出现参数\(\theta\),因为参数不再是固定的值,而变成了随机变量,所以也是隐藏变量,包括在\(\mathbf{Z}\)之内了。

Read More

背包问题学习笔记(2)-问法的变化

所有问法均以01背包问题为例,问题如下: 有\(N\)种物品和一个容量为\(V\)的背包,每种物品都有无限件可用。放入第i种物品的费用是\(C_i\),价值是\(W_i\),求背包所装物体的价值最大。 基本代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include
using namespace std;
const int N=4,V=10;
int F[N+1][V+1];
int C[N+1]={0,3,4,4,5};
int W[N+1]={0,4,6,6,7};
void BasicZeroOnePack() //O(NV)
{
memset(F,0,sizeof(F));
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
F[i][v]=F[i-1][v]; //默认不加入物品
if(v>=C[i]) //可以加入的时候考虑一下
F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
}
}
}

改动都是基于这个代码。

恰好装满的要求

如果要求恰好装满的话,初始化时除了\(F[0]=0\)以外,其余的F[1,…V]均设为负无穷。因为如果要求恰好装满,初始化的时候只有容量为0的背包装容量为0的物体才是合法状态,其余的状态全都不合法,用负无穷表示。

Read More

背包问题学习笔记(1)-基本的背包问题介绍

背包问题是动态规划中非常经典的问题。这里仅仅是一份学习笔记和简单的代码实现,更详细的介绍请见参考1和2。

01背包问题

题目

\(N\)种物品和一个容量为\(V\)的背包,每种物品都有无限件可用。放入第i种物品的费用是\(C_i\),价值是\(W_i\)。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不超过背包容量,且价值总和最大。

基本思路

\(F[i,v]\)代表前\(i\)件物品放入容量为\(v\)的背包可以获得的最大价值。 01背包的状态转移方程为: \[F[i,v]=\max\{F[i-1][v],F[i-1][v-C_i]+W_i\}\] 将“前\(i\)件物品放入容量为\(v\)的背包”中这个子问题,只考虑地\(i\)件物品的策略(放或不放)。如果放入\(i\)物品,问题转为“前i-1件物品放入容量为\(v-C_i\) 的背包中“这个子问题的最大价值\(F[i-1,v-C_i]\)加上\(W_i\)。如果不放,问题转化为”前i-1件物品放入容量为\(v-C_i\) 的背包中“,价值为\(F[i-1,v]\)

代码是

Read More

我是否吃遍了食堂的盘子?

前一阵子突发奇想,想看看吃饭吃了这么久,是不是把食堂里的盘子都吃过一遍了。提出问题如下: 现存在1,2,3号个盘子,每次吃饭拿一个盘子,用完之后放回去,请问吃了5次饭之后三个盘子都被用过的概率是多少?如果是m个盘子,吃了n次饭所有的盘子都被用过的概率呢?

求概率

虽然我猜出了公式,但是还是不怎么懂。。。讲一下猜的过程:

  1. 3个盘子吃了5次饭的情况。 既然我要算所有盘子都被吃过的情况,那么只要排除掉盘子没吃过的情况就好了。首先考虑只用了2个盘子的情况,总够有\(C^2_3 \cdot 2^5\)种。但是要注意到这里对2个盘子的穷举已经包括了只用了1个盘子的情形而且还冗余了,所以要减掉冗余的3种情况。 所以三个盘子都被用过的概率为:
    \[1-\frac{C^2_3 \cdot 2^5 -3}{3^5}=\frac{150}{243}\]
  2. 4个盘子吃了5次饭的情况。 这里我们首先考虑只用了3个盘子的情况,共有\(C^3_4 \cdot 3^5\)种情况。但是对这3个盘子的情况的列举已经包括了只包含2个盘子的情况,所以要减去\(C^2_4 \cdot 2^5\)种2个盘子的情况,但是要注意的是对这2个盘子的列举又已经包括了1个盘子的情况,所以要加上种只含一个盘子的情况\(C^1_4 \cdot 1^5\)补回来。 所以三个盘子都被用过的概率为:
    \[ 1-\frac{C^3_4 \cdot 3^5-C^2_4 \cdot 2^5+C^1_4 \cdot 1^5}{4^5}=\frac{240}{1024} \]
  3. m个盘子吃了n次饭的情况。 根据上面的减减加加的想法推断(完全是瞎猜好么),就可以得到m个盘子吃了n次饭的概率公式:
    \[ 1-\frac{C^{m-1}_n \cdot (m-1)^n-C^{m-2}_n \cdot (m-2)^n+... \pm C^1_n \cdot 1^n}{m^n} \]
    m个盘子都被用过的概率为: 随便代入一个例子。m=20,n=50得到的概率为:0.16417976964878256。用模拟的方法发现这个数是对的- -。

求期望

虽然我们知道了具体的概率,还是希望有个期望值来告诉我们大概在吃几个盘子的时候你能够舔遍全食堂的盘子。根据《算法导论》5.4.2的说法,我们将吃到以前没吃过的盘子的时候定义为“命中”,然后我们要求为了吃完m个盘子需要吃的次数n。

命中次数可以用来讲n次吃饭划分为多个阶段。第i个阶段包括从第i-1次命中到第i次命中所吃的次数。第1阶段因为所以盘子都没被吃过,所以是必中的。第i阶段的每一次吃饭,都有i-1个盘子被吃过,m-i+1个盘子没被吃过,这样第i次命中的概率就是(m-i+1)/m。

\(n_i\)表示第i阶段的吃饭次数。每个随机变量\(n_i\)都服从概率为(m-i+1)/m的几何分布。根据几何分布的期望可以算得
\[ E[n_i]=\frac{m}{m-i+1}\]
由期望的线性性质,可以得到
\[E[n]=E[\sum^m_{i=1}n_i]=\sum^m_{i=1}E[n_i]=\sum^m_{i=1}\frac{m}{m-i+1}=m \sum \frac{1}{m}=m(\ln m+O(1))\]

最后的式子是调和级数的上界,所以我们希望吃完所有的盘子大概需要\(m\ln m\)次,这个问题也被称作赠卷收集者问题(coupon collector’s problem)。 如果食堂有1000 个盘子,我们大学4年估计是吃不完的。。。

三硬币问题-一个EM算法和Gibbs Sampling的例子

讲一个EM算法和Gibbs 抽样的小例子,用于加深理解(变分推断版本请见变分推断学习笔记(3)——三硬币问题的变分推断解法)。

题目(引用自参考1):假设有3枚硬币,分别记做A,B,C。这些硬币正面出现的概率分别是\(\pi\),\(p\)\(q\)。进行如下掷硬币实验:先掷硬币A,根据其结果选出硬币B或C,正面选B,反面选硬币C;然后投掷选重中的硬币,出现正面记作1,反面记作0;独立地重复\(n\)次(n=10),结果为 \[1111110000\] 我们只能观察投掷硬币的结果,而不知其过程,估计这三个参数\(\pi\),\(p\)\(q\)

EM算法

可以看到投掷硬币时到底选择了B或者C是未知的。我们设隐藏变量Z 来指示来自于哪个硬币,\(Z=\{z_1,z_2,\ldots,z_n \}\),令\(\theta=\{\pi,p,q\}\),观察数据\(X=\{x_1,x_2,\ldots,x_n \}\)

写出生成一个硬币时的概率: \[\begin{split}P(x|\theta) & =\sum_z P(x,z|\theta)=\sum_z P(z|\pi)P(x|z,\theta) \\& =\pi p^x (1-p)^{1-x}+(1-\pi)q^x(1-q)^{1-x} \\\end{split}\] 有了一个硬币的概率,我们就可以写出所有观察数据的log似然函数: \[L(\theta|X)=\log P(X|\theta)=\sum^n_{j=1}\log[\pi p^{x_j} (1-p)^{1-{x_j}}+(1-\pi)q^{x_j}(1-q)^{1-{x_j}}]\] 然后求极大似然 \[\hat{\theta}=\arg \max L(\theta|X)\] 其中\(L(\theta|X)=\log P(X|\theta)=\log \sum_Z P(X,Z|\theta)\)。因为log里面带着加和所以这个极大似然是求不出解析解的。

Read More