最大熵模型学习

最大熵模型的原理用通俗的话解释很好理解，但是对于模型的数学定义却不是那么容易理解。
其实，网上有大量的论文、笔记、幻灯片介绍最大熵模型，这篇文章主要是我对该模型的一些笔记和推导。

最大熵模型的原理

最大熵原理是统计学习的一般原理，将它应用到分类问题时得到最大熵模型。在实际处理分类问题时，我们常常将数据看成是有对应关系的实例。实例称为Event，每个Event包含一个上下文环境Context和对应类别Outcome，是一个Context和Outcome的二元组。

假设分类模型学习的是一个条件概率分布$P(X|Y)$，给定训练集：

$$T=\lbrace (x_1,y_1),(x_2,y_2)…(x_n,y_n) \rbrace$$

学习的目标是用最大熵原理选择最好的分类模型。

给定训练集之后，可以通过统计得到联合分布$P(X,Y)$的经验分布和边缘分布$P(X)$的经验分布，分别以$\tilde{P}(X,Y)$和$\tilde{P}(X)$表示。这里

$$\tilde{P}(X=x,Y=y)=\frac{v(X=x,Y=y)}{N}$$
$$\tilde{P}(X=x)=\frac{v(X=x)}{N}$$

另外还有用特征函数(feature function)$f(x,y)$描述输入x和输出y之间的函数，特征的全体可以看做是n个特征函数组成的一个集合。每个特征函数可以是从Context到{0，1}的二值函数。比如：

feature_function

一组特征函数就将Context从上下文空间映射到特征空间上了。

现在，通过我们观察的一组数据，进行简单的统计就可以直到任意一个Context x和Outcome y的组合的联合概率$\tilde{P}(x,y)$，于是可以计算某一特征函数$f_i$关于经验分布$\tilde{P}(x,y)$的期望：

$$E_{\tilde{P}}(f_i)=\sum_{x,y}\tilde{P}(x,y)f_i(x,y)$$

从另一个角度考虑，利用贝叶斯公式，特征函数$f_i$关于模型$P(y|x)$与经验分布$\tilde{P}(x)$的期望为：

$$E_{P}(f_i)=\sum_{x,y}\tilde{P}(x)P(y|x)f_i(x,y)$$

如果模型能够获取足够的训练集的信息，那么就可以假设这两个期望值是相等的。假设我们有n个特征函数，那么我们就有n组等式$E_{\tilde{P}}(f_i)=E_{P}(f_i)，i=1,2,…,n$，也即n个约束条件。

假设的模型P有许多，它们组成一个模型空间$\mathcal{P}$，而满足上面一系列特征函数期望构成的等式的概率分布构成了$\mathcal{P}$的一个子集。

$$\mathcal{C}=\lbrace p \in \mathcal{P} | E_{\tilde{P}}(f_i)=E_{P}(f_i)，i=1,2,…,n\rbrace$$

熵就是评估该空间中某个模型的指标，定义在条件概率分布$P(Y|X)$上的条件熵为

$$H(P)=-\sum_{x,y}\tilde{P}(x)P(y|x)logP(y|x)$$

所以，最大熵模型$p^*$就是
$$p^* = arg\max_{p\in\mathcal{C}}H(p)$$

maxent toolkit

下载

我直接在作者的github上下载的zip压缩文件，下载地址：maxent。
解压缩

shhe@nustm:~$ unzip maxent-master.zip
编译安装

shhe@nustm:~/maxent-master$ ./configure --prefix=/home/usr/path

因为是在服务器上安装，没有root权限，所以使用‘–prefix’参数将安装目录修改到/home/usr/path下。
这里的路径可根据需要自行修改，不过要记住具体的位置，因为之后安装python模块的时候需要泳道这一步产生的文件。这些文件分别在两个目录下，/home/usr/path/include和/home/usr/path/lib。

shhe@nustm:~/maxent-master$ make

shhe@nustm:~/maxent-master$ make install

此处本来需要root权限，不过在之前执行configure的时候已经修改了安装路径，所以顺利通过。
测试（可选）

(1) 单元测试

shhe@nustm:~/maxent-master$ make unittest

(2) 测试Python接口

shhe@nustm:~/maxent-master$ cd python

shhe@nustm:~/maxent-master/python$ python runall.py
安装Python接口

这里也是在无root权限下安装，所需要重新定位安装目录。

shhe@nustm:~/maxent-master/python$ vim setup.py

修改setup.py文件，找到之前编译过程产生的相关文件，在setup.py的78~88行：
```
include_dirs=[
   "../lib",
     "../src",
     "/home/usr/path/include",
    ],

    library_dirs=[
    "../src/opt",
    "../src",
    "/home/usr/path/lib",
    ] + opt_lib_path,
```
可以看到，此处有两行的路径已被我修改为之前编译时指定的路径。

运行setup.py:

shhe@nustm:~/maxent-master/python$ python setup.py build

shhe@nustm:~/maxent-master/python$ python setup.py install --prefix=~/.local

这时终端会显示输出几行writing开头的文字，复制下其中的./local/lib/python2.7/site-packages部分，这是你用户目录下的Python模块目录，根据版本和计算机的不同会有所区别。

将指定路径下的lib和bin分别加入环境变量中：

shhe@nustm:~$ echo "PYTHONPATH=$HOME/.local/lib/python2.7/site-packages" >> .bashrc

shhe@nustm:~$ echo "export PATH=$HOME/.local/bin:$PATH" >> .bashrc

shhe@nustm:~$ source .bashrc

这样，就实现了没有root权限情况下的Python模块安装。
使用

【未完成】

请参考基于最大熵模型的分词工具maxent

请参考Maxent