<统计学习方法>的本章结构
- 逻辑斯谛回归模型
- 逻辑斯谛分布
- 二项逻辑斯谛回归模型
- 模型参数估计
- 多项逻辑斯蒂回归模型
- 最大熵模型
- 最大熵原理
- 最大熵模型定义
- 最大熵模型学习
- 极大似然估计
- 模型学习的最优化算法
- 改进的迭代尺度法
- 拟牛顿法
在最大熵的通用迭代算法GIS中, E过程就是跟着现有的模型计算每一个特征的数学期望值, M过程就是根据这些特征的数学期望值和实际观测值的比值, 调整模型参数. 这里最大化的目标函数是熵函数.
--吴军, 数学之美
$P_{244}$
这里的熵函数是条件熵.
Logistic regression is a special case of maximum entropy with two labels +1 and −1.
在<机器学习>上把这个叫做对数几率回归
逻辑斯谛回归模型和最大熵模型, 既可以看作是概率模型, 又可以看作是非概率模型.
信息量是对信息的度量, PRML中有关于信息量的讨论, 信息是概率的单调函数.
- 信息和概率的关系参考PRML中1.6节信息论部分的描述.
如果我们知道某件事件一定会发生, 那么我们就不会接收到信息. 于是, 我们对于信息内容的度量将依赖于概率分布$p(x)$
如果我们有两个不相关的事件x, y, 那么我们观察到两个事件同时发生时获得的信息应该等于观察到事件各自发生时获得的信息之和, 即$h(x,y)=h(x)+h(y)$, 这两个不相关的事件是独立的, 因此$p(x,y)=p(x)p(y)$
根据这两个关系, 很容易看出$h(x)$一定与$p(x)$的对数有关. 所以有
$$h(x)=-\log_2{p(x)}=\log_2{\frac{1}{p(x)}}$$
- 负号确保了信息非负
- 低概率事件$x$对应了高的信息.
熵可以从随机变量状态需要的平均信息量角度理解, 也可以从描述统计力学中无序程度的度量角度理解.
关于熵, 条件熵, 互信息, 这些内容在第五章5.2节有对应的描述.
下面看下信息熵在PRML中的表达
假设一个发送者想传输一个随机变量$x$的值给接受者. 在这个过程中, 他们传输的平均信息量可以通过求信息$h(x)$关于概率分布$p(x)$的期望得到.
这个重要的量叫做随机变量$x$的熵
Venn图辅助理解和记忆, 这个暂时不画, 下面考虑下为什么Venn图能帮助理解和记忆?
因为熵的定义把连乘变成了求和, 对数的贡献. 这样可以通过集合的交并来实现熵之间关系的理解.
-
概率
$\sum _{i=1}^{n}{p_i=1}$ $p \in [0,1]$ -
熵
$Ent(D) \in [0, \log_2{|\mathcal Y|}]$ , 熵可以大于1. 熵是传输一个随机变量状态值所需的比特位下界(信息论角度的理解) -
信息熵是度量样本集合纯度最常用的一种指标.
$Ent(D)=-\sum \limits ^{|\mathcal Y|}_{k=1}p_k\log_2{p_k}$ - if
$p=0$ , then$p\log_2{p}=0$ -
$Ent(D)$ 越小, D的纯度越高. 非均匀分布比均匀分布熵要小. - 熵衡量的是不确定性, 概率描述的是确定性
- if
-
联合熵(相当于并集)
$H(X, Y) = H(X) + H(Y|X) = H(Y)+H(X|Y) = H(X|Y)+H(Y|X)+I(X;Y)$ 这个通过Venn应该是相对容易记忆, 是不是容易理解这个又汉姆雷特了.
如果X和Y独立同分布, 联合概率分布$P(X,Y)=P(X)P(Y)$
-
条件熵
条件熵是最大熵原理提出的基础,最大的是条件熵, 这个在书中有写(定义6.3).
条件熵衡量了条件概率分布的均匀性.
最大熵, 就是最大这个条件熵
find
$$\begin{aligned} p^*&=\arg\max\limits_{p\in \mathcal C}H(p)\ &=\arg \max\limits_{p\in \mathcal C}(-\sum\limits_{x,y} {\tilde p(x)p(y|x)\log p(y|x) }) \end{aligned} $$
接下来的概念, 把熵的思想应用在模式识别问题中.
-
互信息
互信息(mutual information), 对应熵里面的交集, 常用来描述差异性
一般的, 熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息. 注意一下, 这里第五章中用到了$H(D, A)$ 可以对应理解下.
- feature selection
- Feature Correlation, 刻画的是相互之间的关系. 相关性主要刻画线性, 互信息刻画非线性
-
信息增益
这个对应的是第五章的内容, 决策树学习应用信息增益准则选择特征. $$ g(D,A)=H(D)-H(D|A) $$ 信息增益表示得知X的信息而使类Y的信息的不确定性减少的程度.
在决策树学习中, 信息增益等价于训练数据集中类与特征的互信息.
-
相对熵 (KL 散度)
相对熵(Relative Entropy)描述差异性, 从分布的角度描述差异性, 可用于度量两个概率分布之间的差异.
KL散度不是一个度量.
KL散度满足非负性.
考虑由$p(x,y)$给出的两个变量x和y组成的数据集. 如果变量的集合是独立的, 那么他们的联合分布可以分解为边缘分布的乘积$p(x,y)=p(x)p(y)$
如果变量不是独立的, 那么我们可以通过考察联合分布与边缘分布乘积之间的KL散度来判断他们是否"接近"于相互独立.f
$$I(x,y)=KL(p(x,y)|p(x)p(y))=-\iint p(x,y) \ln {\left( \frac{p(x)p(y)}{p(x,y)}\right)}$$ 这被称为变量x和变量y之间的互信息.
--PRML 1.6.1
注意这里, 参考下第五章中关于互信息的描述
决策树学习中的信息增益等价于训练数据集中类与特征的互信息
注意这里面类Y, 特征X.
互信息和条件熵之间的关系 $$ I(x,y)=H(X)-H(x|y)=H(y)-H(y|x) $$ 可以把互信息看成由于知道y值而造成的x的不确定性的减小(反之亦然). 这个就是信息增益那部分的解释.
-
交叉熵
刻画两个分布之间的差异 $$ \begin{aligned} CH(p,q)&=-\sum\limits_{i=1}^{n}p(x_i)\log{q(x_i)}\ &=-\sum\limits_{i=1}^{n}p(x_i)\log{p(x_i)}+\sum\limits_{i=1}^{n}p(x_i)\log{p(x_i)}-\sum\limits_{i=1}^{n}p(x_i)\log{q(x_i)}\ &=H(p)+\sum\limits_{i=1}^{n}p(x_i)\log{\frac{p(x_i)}{q(x_i)}}\ &=H(p)+KL(p||q) \end{aligned} $$
CNN时候常用
对于各种熵的理解, 是构建后面的目标函数的基础.
最大熵原理(Maxent principle)是概率模型学习的一个准则.
书中通过一个例子来介绍最大熵原理, 下面引用一下文献中关于这个例子的总结.
Model all that is known and assume nothing about that which is unknown. In other words, given a collection of facts, choose a model which is consistent with all the facts, but otherwise as uniform as possible.
-- Berger, 1996
书中关于这部分的总结如下：满足约束条件下求等概率的方法估计概率分布
关于最大熵原理有很多直观容易理解的解释, 比如Berger的例子, 比如吴军老师数学之美中的例子. 最大熵原理很常见, 很多原理我们都一直在用, 只是没有上升到理论的高度.
等概率表示了对事实的无知, 因为没有更多的信息, 这种判断是合理的.
最大熵原理认为要选择的概率模型首先必须满足已有的事实, 即约束条件
最大熵原理根据已有的信息（约束条件）, 选择适当的概率模型.
最大熵原理认为不确定的部分都是等可能的, 通过熵的最大化来表示等可能性.
最大熵的原则, 承认已有的, 且对未来无偏
最大熵原理并不直接关心特征选择, 但是特征选择是非常重要的, 因为约束可能是成千上万的.
这部分书中只描述了模型空间$\mathcal P$, 两个约束$C_1$和$C_2$是一致性约束的情况.
在Berger 1996里面有展开这部分, 分了四个图, 分别讨论了
- 概率模型空间$\mathcal {P}$
- 单一约束$C_1$
- 一致性(consistent)约束$C_1$和$C_2$, 这种情况下模型唯一确定$p=C_1\bigcap C_2$
- 非一致性(inconsistent)约束$C_1$和$C_3$, 这种情况下没有满足约束条件的模型.
关于特征和约束, Berger有他的阐述
指示函数
$f(x,y)=\begin{cases} 1 & if\ y=en\ and\ April\ follows\ in\ 0 & otherwise \end{cases}$
上面这个$f$直接引用自Berger的说明, 原来的例子是英语in到法语的翻译.
这里面f就是特征函数, 或者特征.
定义一个期望, 如果是二值函数的话, 就相当于计数. 通过样本得到的这个统计. 但是样本是有限的, 并不是一个真实的分布, 所以叫经验分布, 如果我们拿到的这个模型能够表示实际的分布, 那么就可以假设经验分布和真实分布是相等的. 这个, 就是约束方程, 或者约束.
一般模型的特征是关于x的函数, 最大熵模型中的特征函数, 是关于x和y的函数. 注意理解$f(x)$与$f(x, y)$的区别. 关于特征函数可以参考条件随机场中例11.1关于特征部分的内容增强理解.
假设分类模型是一个条件概率分布,
给定一个训练集
N是训练样本容量,
联合分布P(X, Y)与边缘分布P(X)的经验分布分别为$\widetilde P(X, Y)和\widetilde P(X)$
$$ \begin{aligned} &\widetilde P (X=x, Y=y)=\frac{\nu(X=x, Y=y)}{N} \ &\widetilde P (X=x)=\frac {\nu (X=x)}{N} \end{aligned} $$ 上面两个就是不同的数据样本, 在训练数据集中的比例.
如果增加n个特征函数, 就可以增加n个约束条件
假设满足所有约束条件的模型集合为
定义在条件概率分布$P(Y|X)$上的条件熵为
则模型集合$\cal {C}$中条件熵$H(P)$最大的模型称为最大熵模型, 上式中对数为自然对数.
特征函数$f(x,y)$关于经验分布$\widetilde P (X, Y)$的期望值, 用$E_{\widetilde P}(f)$表示
特征函数$f(x,y)$关于模型$P(Y|X)$与经验分布$\widetilde P (X)$的期望值, 用$E_{P}(f)$表示
如果模型能够获取训练数据中的信息, 那么就可以假设这两个期望值相等, 即
上面这个也是约束方程
通过对已知训练集数据的分析, 能够拿到联合分布的经验分布和边缘分布的经验分布.
特征函数用来描述$f(x, y)$描述输入x和输出y之间的某一事实. $$ f(x,y) = \begin{cases} 1 & x与y满足某一事实\ 0 & 否则 \end{cases} $$
这里, 满足的事实, 可以是in, 显然, 特征函数可以自己定义, 可以定义多个, ~~~这些就是约束 ~~~
之前理解的不对, 看前面有描述特征和约束的关系.
这里面重复一下书中的过程, 在$L(P, w)$对$P$求导并令其为零的情况下解方程能拿到下面公式 $$ P(y|x)=\exp{\left(\sum_{i=1}^{n}w_if_i(x,y)+w_0-1\right)}=\frac{\exp{\left(\sum\limits_{i=1}^{n}w_if_i(x,y)\right)}}{\exp{\left(1-w_0\right)}} $$ 书中有提到因为$\sum\limits{_y}P(y|x)=1$, 然后得到模型
注意这里面$Z_w$是归一化因子.
这里面并不是因为概率为1推导出了$Z_w$的表达式, 而是因为$Z_w$的位置在分母, 然后对应位置$\exp(1-w_0)$也在分母, 凑出来这样一个表达式, 意思就是遍历y的所有取值, 求分子表达式的占比.
综上, 如果$f_i(x,y)$只检测是不是存在这种组合, 那么概率就是归一化的出现过的特征, 系数求和再取e指数.
最大熵模型的学习过程就是求解最大熵模型的过程.
最大熵模型的学习可以形式化为约束最优化问题. $$ \begin{eqnarray*} \min \limits_{P\in \mathcal {C}}-H(P)=\sum\limits_{x,y}\widetilde P(x)P(y|x)\log P(y|x)\tag{6.14}\ s.t. E_P(f_i)-E_{\widetilde P}(f_i)=0, i =1,2,\dots,n\tag{6.15}\ \sum \limits_y P(y|x)=1\tag{6.16} \end{eqnarray*} $$
可以通过例6.2 来理解最大熵模型学习的过程, 6.2 考虑了两种约束条件, 这部分内容可以通过python符号推导实现, 西面代码整理整个求解过程.
from sympy import *
# 1 constrains
P1, P2, P3, P4, P5, w0, w1, w2 = symbols("P1, P2, P3, P4, P5, w0, w1, w2", real=True)
L = P1 * log(P1) + P2 * log(P2) + P3 * log(P3) + P4 * log(P4) + P5 * log(P5) \
+ w0 * (P1 + P2 + P3 + P4 + P5 - 1)
P1_e = (solve(diff(L, P1), P1))[0]
P2_e = (solve(diff(L, P2), P2))[0]
P3_e = (solve(diff(L, P3), P3))[0]
P4_e = (solve(diff(L, P4), P4))[0]
P5_e = (solve(diff(L, P5), P5))[0]
L = L.subs({P1: P1_e, P2: P2_e, P3: P3_e, P4: P4_e, P5: P5_e})
w = (solve([diff(L, w0)], [w0]))[0]
P = [P1_e.subs({w0: w[0]}),
P2_e.subs({w0: w[0]}),
P3_e.subs({w0: w[0]}),
P4_e.subs({w0: w[0]}),
P5_e.subs({w0: w[0]})]
P# 2 constrains
P1, P2, P3, P4, P5, w0, w1, w2 = symbols("P1, P2, P3, P4, P5, w0, w1, w2",real=True)
L = P1*log(P1) + P2*log(P2)+P3*log(P3)+P4*log(P4)+P5*log(P5)\
+w1*(P1+P2-3/10)\
+w0*(P1+P2+P3+P4+P5-1)
P1_e = (solve(diff(L,P1),P1))[0]
P2_e = (solve(diff(L,P2),P2))[0]
P3_e = (solve(diff(L,P3),P3))[0]
P4_e = (solve(diff(L,P4),P4))[0]
P5_e = (solve(diff(L,P5),P5))[0]
L = L.subs({P1:P1_e, P2:P2_e, P3:P3_e, P4:P4_e, P5:P5_e})
w = (solve([diff(L,w1),diff(L,w0)],[w0,w1]))[0]
P = [P1_e.subs({w0:w[0], w1:w[1]}),
P2_e.subs({w0:w[0], w1:w[1]}),
P3_e.subs({w0:w[0], w1:w[1]}),
P4_e.subs({w0:w[0], w1:w[1]}),
P5_e.subs({w0:w[0], w1:w[1]})]
P# 3 constrains
P1, P2, P3, P4, P5, w0, w1, w2 = symbols("P1, P2, P3, P4, P5, w0, w1, w2",real=True)
L = P1*log(P1) + P2*log(P2)+P3*log(P3)+P4*log(P4)+P5*log(P5)\
+w2*(P1+P3-1/2)\
+w1*(P1+P2-3/10)\
+w0*(P1+P2+P3+P4+P5-1)
P1_e = (solve(diff(L,P1),P1))[0]
P2_e = (solve(diff(L,P2),P2))[0]
P3_e = (solve(diff(L,P3),P3))[0]
P4_e = (solve(diff(L,P4),P4))[0]
P5_e = (solve(diff(L,P5),P5))[0]
L = L.subs({P1:P1_e, P2:P2_e, P3:P3_e, P4:P4_e, P5:P5_e})
w = (solve([diff(L,w2),diff(L,w1),diff(L,w0)],[w0,w1,w2]))[0]
P = [P1_e.subs({w0:w[0], w1:w[1],w2:w[2]}),
P2_e.subs({w0:w[0], w1:w[1],w2:w[2]}),
P3_e.subs({w0:w[0], w1:w[1],w2:w[2]}),
P4_e.subs({w0:w[0], w1:w[1],w2:w[2]}),
P5_e.subs({w0:w[0], w1:w[1],w2:w[2]})]
P逻辑斯谛回归模型和最大熵模型学习归结为以似然函数为目标函数的最优化问题, 通常通过迭代算法求解.
$$ \begin{aligned} L(w)&=\sum\limits^{N}{i=1}[y_i\log\pi(x_i)+(1-y_i)\log(1-\pi(x_i))]\ &=\sum\limits^{N}{i=1}[y_i\log{\frac{\pi(x_i)}{1-\pi(x_i)}}+\log(1-\pi(x_i))]\ &=\sum\limits^{N}_{i=1}[y_i(w\cdot x_i)-\log(1+\exp(w\cdot{x_i})] \end{aligned} $$
- 逻辑斯谛回归模型与朴素贝叶斯的关系
- 逻辑斯谛回归模型与AdaBoost的关系
- 逻辑斯谛回归模型与核函数的关系
课后习题的第一个题目提到了指数族(Exponential family)分布, 这个概念在PRML中有单独的章节进行阐述.
感觉大部分的算法实现, 其实都是在刷权重, 另外, 其实算法能跑起来, 能预测, 并不能说明算法实现的正确的.
关于代码实现, 网上看似众多的版本,应该基本上都源自最早15年的一份GIS的程序.
无论怎样,这些代码的实现, 都会有助于对Maxent的理解.推荐后面参考文献[1]
李航老师在本章的参考文献中(1, 2)是Berger的文章.
代码来源: https://vimsky.com/article/776.html 相关公式: https://vimsky.com/article/714.html
提几点:
- 代码参考文献可以看berger的文章, 公式编号基本对应.
- 这份代码用defaultdict实现了稀疏存储.
- 如果$f(x, y)$只是判断$(x, y)$在特征中出现的指示函数, 那么特征可以简单的表示为$(x, y)$, 这样给定一份含有标签的数据集, 特征的数量就是
$m \times n$ 其中$m$是标签的数量,$n$ 是词表大小.注意书中注释过,$f(x,y)$ 可以是任意实值函数. - 这份代码思路很清晰,
$(E_{\widetilde p}, Z_x \Rightarrow P(y|x) \Rightarrow E_p) \Rightarrow \delta $ , 具体参考书中公式6.22, 6.23, 6.34 - 体会一下在做直方图的时候, 对于同一个样本, 同样的特征出现多次的贡献是一样的.
- 在未知的情况下, 输出结果等概率.
参考链接: https://github.com/WenDesi/lihang_book_algorithm/tree/master/maxENT
本来是想在这个代码的基础上更改, 但是代码分解的不是非常容易理解. 改来改去基本上面目全非了. 保留链接以示感谢. 博主写了一系列代码, 至少有个成体系的参考.
提几点:
-
没有用稀疏存储, 所以, 矩阵中会有很多零. 需要除零错误处理
with np.errstate(divide='ignore', invalid='ignore'): tmp = np.true_divide(self.EPxy, self.EPx) tmp[tmp == np.inf] = 0 tmp = np.nan_to_num(tmp)
分子分母都是0对应nan, 分母为0对应inf
-
尝试了三种数据, 可以通过命令行参数实现数据选择.
- Demo中用到的data
- train_binary.csv 这份数据的来源是参考链接中的, 只考虑了0,1两种数据, 标签少.
- sklearn中的digits, 标签全, 但是8x8大小, 比mnist少.
-
书中有一个地方还是不理解的, 提到了$f^#$是不是常数的问题.
-
没有采用字典的方式实现稀疏存储, 但是numpy的数组操作还是很便捷的, 后面有空评估一下存储和计算资源的消耗情况.
-
大多数算法感觉都是在刷权重, 考虑哪些量可以用, 哪些方法可以让权重刷的更合理, 哪些方法能刷的更快.
- Berger,1995, A Brief Maxent Tutorial
- [数学之美:信息的度量和作用]
- [数学之美:不要把鸡蛋放在一个篮子里 谈谈最大熵模型]
- 李航·统计学习方法笔记·第6章 logistic regression与最大熵模型（2）·最大熵模型
- 最大熵模型与GIS ,IIS算法
- 关于最大熵模型的严重困惑：为什么没有解析解？
- 最大熵模型介绍 这个是Berger的文章的翻译.
- 理论简介 代码实现
- 另外一份代码
- 如何理解最大熵模型里面的特征？
- Iterative Scaling and Coordinate Descent Methods for Maximum Entropy Models