Max Entropy学习总结

Posted on | In | Visitors:

模型推导

最大熵是选择最优模型的一个准则，即，首先要满足已有的事实（约束条件），然后在没有更多信息的情况下，那些不确定的部分都是“等可能的”。“等可能”本身不容易操作，熵是一个可以优化的数值目标。

这里最大熵最大化的，是条件熵$H(Y|X)$。

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

具体的关于信息熵的文章，可以看colah的这篇博客，里面对信息熵/互信息/条件熵的物理意义做很好的解释。

好的，我们的最大熵有了目标函数。刚才说了，我们还必须要保证满足已有的事实，这一点如何用数学公式去描述呢？

首先引入特征函数： $$f(x,y)=\left\{\begin{matrix}
1, \;\;x与y满足某一事实 \\
0，\;\;否则
\end{matrix}\right.$$

下面注意到两个期望：

  • 1.特征函数$f(x,y)$在训练样本中关于经验分布$\tilde P(x,y)$的期望：$E_{\tilde P}(f)=\sum_{x,y}\tilde P(x,y)f(x,y)$。
  • 2.特征函数$f(x,y)$关于建立的理论模型$P(Y|X)$与经验分布$\tilde P(x)$的期望：$E_{P}(f)=\sum_{x,y}\tilde P(x)P(y|x)f(x,y)$。

我们希望，模型在训练完以后，能够获取到训练数据中的信息。这个想法，用上面的两个期望表达，就是：

$$E_{\tilde P}(f)=E_{P}(f)$$

给定了目标函数和约束条件，我们通过拉格朗日对偶法，解得模型的更一般的形式，（具体的求解过程省略，这里主要是展现模型思想）：

$$P_w(y|x)=\frac{1}{Z_w(x)}exp\bigl(\begin{smallmatrix} \sum_{i=1}^{n} w_i\cdot f_i(x,y) \end{smallmatrix}\bigr)$$

其中，$Z_w(x)$是归一化因子，$Z_w(x)=\sum_yexp\bigl(\begin{smallmatrix}\sum_{i=1}^{n} w_i\cdot f_i(x,y) \end{smallmatrix}\bigr)$。$w \in R^n$是权值向量，$f_i(x,y)$是特征函数。

这个形式和无向图模型几乎一毛一样～

对数似然函数

$$L(w) = log\prod_{x,y}P(y|x)^{\tilde P(x,y)} $$

$$ = \sum_{x,y}\tilde P(x,y)logP(y|x) \;\;代入最大熵模型 $$

$$ = \sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\tilde P(x,y)logZ_w(x)$$

$$ = \sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x\tilde P(x)logZ_w(x)$$

模型训练的优化算法

GIS算法

GIS，Generalized Iterative Scaling，算法流程：

  • 初始化所有$w_i$为任意值，一般可以设置为0，即：$w_i^{(0)}=0,\;i\in {1,2,3,…,n}$。其中$n$是特征的个数，上标表示迭代轮数。
  • 重复更新权值直到收敛：
    • $w_i^{(t+1)}=w_i^{(t)}+\frac{1}{C}log\frac{E_{\tilde P}(f_i)}{E_{P^{(n)}}(f_i)}$
  • 具体的，$E_{\tilde P}(f_i)=\frac{1}{N}\sum_{j=1}^Nf_i(x_j, y_j)$，即，这个特征函数在所有训练数据上的值的平均值。
    • 具体的，$E_{P^{(n)}}(f_i)=\frac{1}{N}\sum^N_{j=1}\sum_yP^{(n)}(y|x_j)f_i(x_i, y)$。即，某个特征关于模型的期望值在训练集上的值的平均值。

GIS的python实现，参考http://www.hankcs.com/ml/the-logistic-regression-and-the-maximum-entropy-model.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import sys
import math
from collections import defaultdict

class MaxEnt:
    def __init__(self):
        self._train_data = []  # 样本集, 元素是[y,x1,x2,...,xn]的元组
        self._Y = set()  # 标签集合,相当于去重之后的y
        self._xy2num = defaultdict(int)  # Key是(xi,yi)对，Value是count(xi,yi)
        self._data_N = 0  # 样本数量
        self._fea_N = 0  # 特征对(xi,yi)总数量
        self._xy2id = {}  # 对(x,y)对做的顺序编号(ID), Key是(xi,yi)对,Value是ID
        self._C = 0  # 样本最大的特征数量,用于求参数时的迭代，见IIS原理说明
        self._train_exp = []  # 样本分布的特征期望值
        self._model_exp = []  # 模型分布的特征期望值
        self._w = []  # 对应n个特征的权值
        self._lastw = []  # 上一轮迭代的权值
        self._EPS = 0.01  # 判断是否收敛的阈值

    def load_data(self, filename):
        for line in open(filename, "r"):
            sample = line.strip().split("\t")
            if len(sample) < 2:  # 至少：标签 + 一个特征
                continue
            y = sample[0]
            X = sample[1:]
            self._train_data.append(sample)  # labe + features
            self._Y.add(y)  # label
            for x in set(X):  # set给X去重
                self._xy2num[(x, y)] += 1

    def _init_params(self):
        self._data_N = len(self._train_data)
        self._fea_N = len(self._xy2num)
        self._C = max([len(sample) - 1 for sample in self._train_data])
        self._w = [0.0 for _ in range(self._fea_N)]
        self._lastw = self._w[:]
        self._calc_train_exp()

    def is_convergence(self):
        """判断是否收敛"""
        for w, lw in zip(self._w, self._lastw):
            if math.fabs(w - lw) >= self._EPS:
                return False
        return True

    def _zx(self, X):
        """计算Z(X)"""
        ZX = 0.0
        for y in self._Y:
            sum_ = 0.0
            for x in X:
                if (x, y) in self._xy2num:
                    sum_ += self._w[self._xy2id[(x, y)]]
            ZX += math.exp(sum_)
        return ZX

    def _pyx(self, X):
        """计算p(y|x)"""
        ZX = self._zx(X)
        results = []
        for y in self._Y:
            sum_ = 0.0
            for x in X:
                if (x, y) in self._xy2num:  # 这个判断相当于指示函数的作用
                    sum_ += self._w[self._xy2id[(x, y)]]
            pyx = 1.0 / ZX * math.exp(sum_)
            results.append((y, pyx))
        return results

    def _calc_train_exp(self):
        """特征关于经验数据的期望"""
        self._train_exp = [0.0 for _ in range(self._fea_N)]
        for i, xy in enumerate(self._xy2num):
            self._train_exp[i] = self._xy2num[xy] * 1.0 / self._data_N
            self._xy2id[xy] = i

    def _calc_model_exp(self):
        """特征关于模型的期望"""
        self._model_exp = [0.0 for _ in range(self._fea_N)]
        for sample in self._train_data:
            X = sample[1:]
            pyx = self._pyx(X)
            for y, p in pyx:
                for x in X:
                    if (x, y) in self._xy2num:
                        self._model_exp[self._xy2id[(x, y)]] += p * 1.0 / self._data_N

    def train(self, maxiter=1000):
        self._init_params()
        for iter_num in range(0, maxiter):
            # print("Iter:%d..." % i)
            self._lastw = self._w[:]  # 保存上一轮权值
            self._calc_model_exp()
            # 更新每个特征的权值
            for i, w in enumerate(self._w):
                # 迭代式更新w
                self._w[i] += 1.0 / self._C * math.log(self._train_exp[i] / self._model_exp[i])
            # print(self._w)
            # 检查是否收敛
            if self.is_convergence():
                break

    def predict(self, input_):
        X = input_.strip().split("\t")
        prob = self._pyx(X)
        return prob

训练数据来自各种天气情况下是否打球的例子。其中字段依次是:

play / outlook / temperature / humidity / windy

1
2
3
4
5
6
maxent = MaxEnt()
maxent.load_data('max_entropy_data.txt')
maxent.train()
print(maxent.predict("sunny\thot\thigh\tFALSE"))
print(maxent.predict("overcast\thot\thigh\tFALSE"))
print(maxent.predict("sunny\tcool\thigh\tTRUE"))
1
2
3
[('yes', 0.0041626518719793), ('no', 0.9958373481280207)]
[('yes', 0.9943682102360447), ('no', 0.00563178976395537)]
[('yes', 1.4464465173635744e-07), ('no', 0.9999998553553482)]

IIS算法

IIS，Improved Iterative Scaling。GIS的收敛取决于$C$的取值，因此有了改进的IIS。

IIS的想法是：假设最大熵模型当前的参数向量是$w=(w_1, …, w_n)^T$，我们希望找到一个新的参数向量$w+\delta=(w_1+\delta_1, …, w_n+\delta_n)^T$，使得对数似然函数值能增加。

$$L(w+\delta)-L(w)=\sum_{x,y}\tilde P(x,y)\sum^n_{i=1}\delta_if_i(x,y)-\sum_x\tilde P(x)log\frac{Z_{w+\delta}(x)}{Z_w(x)}$$

$$ \geq\sum_{x,y}\tilde P(x,y)\sum^n_{i=1}\delta_if_i(x,y)+1-\sum_x\tilde P(x)\frac{Z_{w+\delta}(x)}{Z_w(x)}\;\;根据-log\alpha \geq 1-\alpha$$

$$=\sum_{x,y}\tilde P(x,y)\sum^n_{i=1}\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)exp\sum^n_{i=1}\delta_if_i(x,y)\;\;记为A(\delta|w)$$

即，$A(\delta|w)$是对数似然函数改变量的下界。IIS试图每一次只优化一个变量$\delta_i$使$A(\delta|w)$最大。

引入新的量：$f^\#(x,y) = \sum_i f_i(x,y)$，表示所有特征在$(x,y)$出现的次数。

$A(\delta|w)改写成\;\;\sum_{x,y}\tilde P(x,y)\sum^n_{i=1}\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)exp(f^\#(x,y)\sum^n_{i=1}\frac{\delta_if_i(x,y)}{f^\#(x,y)})$

利用Jensen不等式，得到：

$exp(\sum^n_{i=1}\frac{f_i(x,y)}{f^\#(x,y)}\delta_if^\#(x,y)) \leq \sum^n_{i=1}\frac{f_i(x,y)} {f^\#(x,y)}exp(\delta_if^\#(x,y))$

记$B(\delta|w)=\sum_{x,y}\tilde P(x,y)\sum^n_{i=1}\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\sum^n_{i=1}\frac{f_i(x,y)} {f^\#(x,y)}exp(\delta_if^\#(x,y))$

求偏导：$\frac{\partial B(\delta|w)}{\partial \delta_i} = \sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)exp(\delta_if^\#(x,y))$

令偏导为0，求得每次更新的$\delta$。

IIS算法流程：

  • 输入：特征函数$f_1, f_2, …, f_n$。经验分布$\tilde
    P(X, Y)$，模型$P_w(y|x)$。
  • 输出：最优参数值$w_i^*$，最优模型$P_w$。
  • 对所有$i \in {1,2,…,
    n}$，取初值$w_i=0$。
  • 对每一$i \in {1,2,…, n}$:
    • 令$\delta_i$是方程：$\sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)exp(\delta_if^\#(x,y))$的解。
    • 更新$w_i$的值为：$w_i + \delta_i$。