最大熵模型和条件随机场

2018-10-31 本文已影响0人 Milkmilkmilk

最大熵模型：

前言引入：

如何理解最大熵模型，先从一个给预测值从实数域到概率值的转换再用最大熵构造特征的思想的角度来理解最大熵模型。

考虑一个解决k分类问题的手段，对每个类别做一个分类器，对于一个分类器而言，类别就变成 "是这个类别" 和 "不是这个类别" 。那么最后对这k个分类器输出的值选择一个最大分类器输出值的那个分类来作为类别结果。那么我们使用最简单线性回归来做这个事情（回归一样也能做分类，只是要经过修改，但是不修改也同样能做）。

也就是以下：（为了方便快速，直接截图抄CBB老师PPT上面的式子。）
$x = (x_1,x_2,...,x_m)$ 是输入向量。考虑k分类 $y \epsilon \{1,2,...,k\}$ 。
k个分类器模型：
$\phi_i(x) = w_{i1}x_1 + ... + w_{im}x_m, 1\le i \le k$
那么我们取结果：
$\hat{y} = argmax_{1 \le i \le k} \phi_i(x)$

但是我们的输出值是在实数域上的，感觉不是很友好（虽然说其实是有意义的，数值越大，说明模型对自己的预测越有信心，甚至说我们想让模型做出有信心的预测，抛弃掉在离中心0比较近的那些预测---这个就是SVM的核心思想margin），所以考虑把实数上的值做一个映射，映射到[0,1]范围上来。类似softmax，我们可以做一个这样的事情：
$\psi(x) = exp( \phi(x) )$
$p(y=i|x) = \frac{\psi_i(x)}{\sum^k_{j=1}{\psi_j(x)}}$
$\hat{y} = argmax_{1 \le i \le k} p(y=i|x)$
这个就是我们从实数域转换到[0,1]上的方法。

然后介绍最大熵模型包括后面的条件熵模型最常用的特征选择的技巧。
考虑：
$\phi_i(x) = w_{i1}x_1 + ... + w_{im}x_m, 1\le i \le k$
这个式子可以定性地理解为，不同的特征(x)设置好了不同的权重(w)，对预测结果的影响。虽然说w是训练的，但是假设，我们有大量的训练数据，对于一个类别 $y=i$ 出现的时候x中的某个特征 $x_j$ （为了方便讨论，这里假设x上面特征的值都是0或者1。）也就是说某个对 $(x_j,i)$ 老是出现。那么模型要往这个方向趋近，明显对于 $y=i$ 这个分类器而言，他一定会认为 $x_j$ 贡献比较大，从而对应的参数会学习出来比较大。
那么我们不是直接让机器学习所有的x特征，而是让机器学习从x特征上挖掘出来的特征。（之后说的特征都是指挖掘出来的特征。x就称为输入向量。）
那么对于输入向量x，明显我们可以做是否出现 $(x_j,y=j)$ 这样的特征。
形式化就是
$f(x,y) = I(x=x_j and y=j)，其中I是指示函数，内部逻辑满足时候为1，不满足为0.$
并且对于特征，应该有不同的权值，而这个权值就是我们想要学习的参数。
从而有以下模型：
$\phi_i(x) = \lambda_{i1} f_{i1}(x,y) + ... + \lambda_{iN} f_{iN}(x,y)$
$\psi(x) = exp( \phi(x) )$
$p(y=i|x) = \frac{\psi_i(x)}{\sum^k_{j=1}{\psi_j(x)}}$
$\hat{y} = argmax_{1 \le i \le k} p(y=i|x)$
其中：
$p(y=i|x) = \frac{\psi_i(x)}{\sum^k_{j=1}{\psi_j(x)}} = \frac{exp(\sum_i \lambda_{i} f_{i}(x,y) )}{\sum_y exp(\sum_i \lambda_{i} f_{i}(x,y) )}$
就是推导之后的最大熵模型。

这种解释，比起直接给出形式，给出经验期望和真实期望相同条件来推导能够更好理解什么是特征函数，也是最大熵的重要特点。

但是只有这样的话，还是感觉不出来最大熵是如何操作的，这里给出一个老师课上的实例（特别棒！！！）：

考虑自然语言处理里面填词问题：
语料库（训练数据）：
I would like to play basketball.
I like to eat french fries.
I want to play football.
I go to watch moves.
Do you want to play chess.
I play games.

考虑一个填词预测问题：
输入：
Do you like ___ play games?

我们控制一下特征相关，只考虑单词的左右相邻的两个单词。
比如上述的问题，输入特征为 you like play games 这4个单词。
同时我们的语料库应该处理成：
I -> would like
would -> I like to
like -> I would to play
to -> would like play basketball
play -> like to basketball
...

然后我们可以考虑设置特征：
特征的设置是随意的，往往是可以根据人为地去了解数据，观察数据。比如我会设置以下：
f(x=play,y=to) 。（这里的特征的含义就认为x中存在play,后面也一样，因为理论上x应该是4个词的序列。）
f(x=like,y=to)。
f(x=like,y=I)。
f(x=play,y=I)。
f(x=interesting,y=I)。
这样，咱们可以根据上述的来进行计算了。
对于我们的输入___边上四个单词是you like play games
假设我们已经通过训练数据训练好了模型的参数 $\lambda$
从而我们可以计算：
$p(y=i|x) = \frac{\psi_i(x)}{\sum^k_{j=1}{\psi_j(x)}}$
并且获得分类的结果。

最大熵和条件随机场之间的关系：

可以考虑序列标注这个问题。（最大熵和条件随机场都能做这个问题，特别是条件随机场在这个问题上是历史优秀的。）

考虑用最大熵来做序列标注，这里有两个思路：
1：直接首先将序列标注问题看作分类问题，假设序列y的长度有n个，并且序列上的元素的状态有m种，那么这个类别一共有 $m^n$ 个。这个会带来类别指数爆炸问题（要求数据量，计算量。）
2：考虑每次只预测一个序列中的一项，一项项预测过去，然后最后得出序列。明显这个有问题，根本就失去了序列中元素的前后顺序关系。

那么如何解决这个问题呢？

image.png

由上图，我们可以预测一个子序列，比如上面，我们预测 $y_{i-1},y_i$ 。这样类别也就 $m^2$ 种。还是可以接受的。

image.png
然后可以类似最上面的分析来解决这个分类问题。
用特征和参数的线性组合来给每个子序列的不同类别设置分值。
并且有了子序列的分值，我们可以获得整个序列的分值。
然后对其做softmax，和上面一样，就行了。
（其实对于这个模型，我们可以用神经网络的角度去理解。）
而上面这种类似最大熵的模型，其实就是条件随机场，并且我们可以发现如果
特别地，序列的长度就1个，那么这个就是最大熵模型了。所以条件随机场是最大熵在序列上的扩展。（并且又有名字是最大熵马尔可夫模型。）

典型的最大熵模型的理解和推导：

直接理解例子：

image.png

解决上面问题的最大熵模型：

image.png

解释一下：
经典的熵模型：
其思想就是在设置好的特征之后，希望我们的概率模型p(x,y)，对于我们设置好的特征的期望等于样本对于特征的期望。

注意这里的“希望”，因为我们根本就没有办法确定p(x)的真实概率。所以在计算我们概率模型的期望的时候借用 $\hat{p}(x)$ 也就是样本中x出现的概率。包括我们的优化目标熵。

另外我们使用的熵是条件熵。
并且用上面的“希望”思路来化简这个条件熵。
从而得到下面的式子：
$p^* = \arg \max_{p\epsilon P} H(p)$
$E_pf_j = E_\hat{p}f_j , 1\le j \le k$
$\sum_y p(y|x) = 1$
其中:
$E_\hat{p}f = \sum_{x\epsilon X,y\epsilon Y} \hat{p}(x,y)f(x,y)$
$E_pf = \sum_{x\epsilon X,y\epsilon Y} p(x,y)f(x,y) \approx \sum_{x\epsilon X,y\epsilon Y}\hat{p}(x)p(y|x)f(x,y)$
$H(p) = -\sum_{x,y}p(x,y)logp(y|x) \approx -\sum_{x,y}\hat{p}(x)p(y|x)log(y|x)$
其中p(y|x)是已经知道的，用softmax一样的手段，以及特征挖掘来模拟的。
利用最大熵原则进行建模一般不存在解析方法。但是可以使用梯度下降等手段。
如果对其分析求导后，可以发现模型就是最上面说到的模型。

宝宝老师PPT上另外一个不错的例子：

image.png

总之，如果要使用最大熵的话，只要设计好特征，然后有了“”概率“”的对应公式，然后求解即可。

图模型：

图模型是用来研究若干个随机变量的联合分布的问题的，一般随机变量之间因为有一些关系，不独立，从而会有连边。

具体就不细讲了。
一般有两个分类：

有向图模型：隐马尔科夫，这种模型一般都可以直接用概率模型，并且用动态规划的思想来求解。
无向图模型：条件随机场，这种模型一般都是把值归一化当做概率来进行求解问题。（最大熵也是这样的）所以归一化这部分是需要消耗比较多时间的。

处理图模型的想法也很简单，就是分区来处理。
比如：
引入最大团的概念，把图分区成一个个最大团。
然后对团设计一个势函数。
直接上老师的PPT，不打公式了。

image.png

注意势函数，其实相当于把一个团 $X_c$ 结合成一个数值。
把这个数值归一化就能当做这个团的概率。
然后整个联合分布就是由所有团的概率的乘积。

具体势函数的选择，也同样是类似softmax + 特征选择技巧。（这里 $\phi$ 没有具体指定，所以没有体现特征选择，但是其实我们可以使用最大熵里面那个特征选择的线性组合函数。其实这样就和条件随机场很接近了！）

要知道，在无向图上面找最大团这个是一个不容易的问题，现在都还没有多项式的求解方法。那么条件随机场就直接假定了相邻两个随机变量为一个团。
因为自然语言处理里面语句都是一条条的，并且一般比较看相邻的两个词之间的关系，所以这里主要介绍链式的条件随机场，其他的结构也是一样的。

image.png

有了前面的思想。其实条件随机场的模型就已经出来了。

image.png

可以知道，条件随机场模型，我们可以从多个角度去看。
1）无向图模型。团的势函数用上softmax 以及特征提取的思想。
2）最大熵模型在预测整个序列的时候，假设子序列之间独立从而分解成预测一个个子序列。
其实上面两个角度是统一的。
并且可以结合以上的思想，我们可以发现最重要的还是特征思想，以及转换成概率模型进行求解。

而做序列标注问题，用维特比算法求解即可。

最大熵模型和条件随机场

最大熵模型：

前言引入：

最大熵和条件随机场之间的关系：

典型的最大熵模型的理解和推导：

图模型：

猜你喜欢

热点阅读