改进的迭代尺度法(IIS)详细解析 | 统计学习方法学习笔记 |

作者: 舟晓南 | 来源:发表于2022-09-02 13:31 被阅读0次

IIS是一种最大熵模型学习的最优化算法。最大熵模型：舟晓南：统计学习方法 - 最大熵模型解析 | 数据分析，机器学习，学习历程全记录

已知最大熵模型为：

《统计学习方法》中直接给出对数似然函数为：

现在解释如何得到上式的对数似然函数：

首先根据对数似然函数的一般形式给出：

在上式中，第二行的箭头成立，是因为指数v(x, y)表示x和y确定时的个数，N为总样本数，除以总样本数不改变w，因此成立。

因为

为常数，这对于我们求极大值没有用处，因此忽略，所以：

因为

所以最终可以得到书中的对数似然函数：

现在求对数似然函数w的极大值，假设最大熵模型当前的参数向量是w，找到一个新的参数向量 $\omega +\delta$ ，使模型的对数似然函数值增大。如果能有这样一种参数向量更新的方法 $\omega \rightarrow \omega +\delta$ ，那么就可以不停迭代，直至找到对数似然函数的最大值。

因为：

所以：

利用不等式 $-log\alpha \geq 1-\alpha ， \alpha >0$ (不等式证明可参考：证明 logX < X 对所有 X > 0 成立)可得：

利用

于是：

又因为：

所以有

于是：

我们将等式右端记为： $A（\delta |\omega ）$ ，这是似然函数的下界，于是有： $L（\omega +\delta ）-L（\omega ）\geq A（\delta |\omega ）$ 。

如果我们能够找到适当的 $\delta$ 使下界提高，那么似然函数也会随之提高。但 $\delta$ 是一个向量，不易同时对每个方向都进行优化，于是固定其它方向，仅优化其中的一个方向，这时我们需要再一次更新下界，使得可以仅优化一个方向。

具体的，我们引入一个量：

表示所有特征在(x,y)中出现的次数。在书中对f#为常数或不为常数的情况做了讨论，不过对于f#什么时候为常数，网络上各有理解。我们首先回顾一下f(x,y)是什么：

首先这个函数f本身代表的是一个规则，即x与y满足某一事实，则为1，否则为0。括号内的x和y是输入值，即每一个数据点的数据，或者说是每一个实例的数据。

那么fi(x, y)中的下标i表示的是不同的规则，比如f1(x, y)在x=1, y=2的情况下为1，否则为0；f2(x, y)在x=2，y=2的情况下为1，否则为0。

对某一个实例而言，我们将其代入f1和f2中，判断这个实例的数据是否符合f1和f2的规则，如果仅符合f1而不符合f2，则f1=1，f2=0。

那么 $\sum_{}^{}f_{i} (x,y)$ 实际上是对一个特定的实例的数据进行i次不同规则的判断。

举一个例子，如果f1(x, y)为x1=1, y=0则为1，否则为0，f2(x, y)为x2=0，y=0为1，否则为0。那么对于某一个实例(x1=1, x2=0, y=0)来说，它既满足f1也满足f2，所以f1=1, f2=1，那么 $\sum_{}^{}f_{i} (x,y)=2，i=1，2$ 。

那么对于另一个实例(x1=1, x2=1, y=0)，它满足f1但不满足f2，所以f1=1，f2=0，那么 $\sum_{}^{}f_{i} (x,y)=1，i=1，2$

这就是为什么在《统计学习方法》中提到f#(x, y)可能为常数，也可能不为常数。在常数的情况下，说明每一个实例的数据符合的规则的数量是一样的，比如有三个规则，实例1符合规则1和规则2，实例2符合规则2和规则3，实例3符合规则1和规则3，尽管它们符合的规则不同，但数量相同，三个实例的f#(x, y)都为2。

当然，f#(x, y)为常数的情况发生的概率很小，因此f#(x, y)在大部分情况下都不是常数。

为了更好的理解，我们再看下标i还出现在权值和权值的更新值上，这说明实际上每一个特征函数fi(x, y)都对应了一个权值wi，对于一个特定的实例来说，如果它符合f1(x, y)的规则，那么权值w1就会作用在这个实例上，也就是说在预测或者分类的时候，模型会考虑f1(x, y)所代表的特征，如果该实例不符合f2(x, y)，那么w2就不会作用在这个实例上，毕竟f2(x, y)=0，这样模型在预测或分类时，就不会考虑f2(x, y)所代表的特征，毕竟这个实例都没有这个特征，又为什么要去考虑它呢？

回到IIS算法本身，定义了f#(x, y)后，可以将 $A（\delta |\omega ）$ 改写为：