学习了《统计学习方法》逻辑斯谛回归与最大熵模型这一章节，现在对这章节做一些笔记。逻辑斯谛回归是工业界非常常用的模型之一，它具有可解释性强、参数训练快等优点；但它和最大熵模型有什么关系，这里做一些笔记方便自己后面的复习。
首先介绍最大熵模型，它是一种模型选择的原则，它本身在工业界并不常用，但它的思想几乎是很多模型选择算法中都有体现；其次通过例子说明逻辑斯谛回归是最大熵模型的一个特例。
最大熵模型
最大熵模型通俗的解释就是按照模型熵最大的原则来选择模型，当我们预测一个随机变量时，最好假设它均匀分布，保留全部不确定性，此时预测的风险最小。举个例子：如果投掷一颗骰子，让你预测各面出现的概率，在没有任何额外信息的情况下，我们会认为骰子是均匀的，各面出现的概率为1/6，从直觉上说，这是最稳妥的策略。
以上的直觉告诉我们最大熵模型是最稳妥的策略，具体数学上如果迭代学习最大熵的模型呢？《统计学习方法》最大熵模型的学习给了我们数学上的推导，这里稍做下疏理，方便自己后面的复习理解：
最大熵模型是一个概率模型，目的是寻找符合要求的条件分布 $P(Y|X)$ 。在定义最大熵模型之前，需要引入下列概念：
联合分布的经验分布： $\tilde{P}(X=x,Y=y) = \frac{v(X=x,Y=y)}{N}$
边缘分布的经验分布： $\tilde{P}(X=x) = \frac{v(X=x)}{N}$
其中， $v(X=x,Y=y)$ 表示训练集中样本 $(x,y)$ 出现的频数， $v(X=x)$ 表示训练数据中输入 $x$ 出现的频数， $N$ 表示训练集样本数。
特征函数： $f(x,y)=\left\{\begin{matrix}
1, & x与y满足某一事实 & \\
0, & 否则 & \\
\end{matrix}\right.$
此特征函数具有普遍性，因此得到“最大熵模型”的一般形式。 如果替换为某种特殊形式，可以得到“逻辑斯谛模型” 。
特征函数 $f$ 关于经验分布 $\tilde{P}(X,Y)$ 的期望值： $E_{\tilde{P}}(f) = \sum_{x,y} \tilde{P}(x,y)f(x,y)$
特征函数 $f$ 关于联合分布 $P(X,Y) = \tilde{P}(X)P(Y|X)$ 的期望值： $E_P(f) = \sum_{x,y} \tilde{P}(x)P(y|x) f(x,y)$
我们假设训练集对于模型的学习是有效的，使得 $E_{\tilde{P}}(x) = E_{P}(f)$ ，此时特征函数 $f$ 称为模型的约束条件。
最大熵模型：假设满足所有约束条件的模型集合为 $E_P(f_i) = E_\tilde{P}(f_i),(i=1,2,...,n)$ ，定义在条件概率分布 $P(Y|X)$ 上的条件熵为
$H(P) = H(Y|X) = - \sum_{x \in X} P(x) \sum_{y \in Y} P(y|x) logP(y|x) = - \sum_{x,y} \tilde{P}(x)P(y|x)logP(y|x)$ 。
满足约束条件且使得条件熵 $H(P)$ 最大的模型，称为“最大熵模型”。
最大熵模型的学习分为两步：
步骤一：转化为最优化问题
对于给定的训练集 $T = {(x_1, y_1), (x_2, y_2), ..., (x_N,y_N)}$ ，特征函数 $f_i(x,y), i=1,2,3,...,n$ ，最大熵模型的学习等价于约束最优化问题：
$\underset{P}{max} \ H(P)=- \sum_{x,y} \tilde{P}(x)P(y|x)logP(y|x)$
约束条件：条件1 $E_P(f_i) = E_\tilde{P}(f_i),(i=1,2,...,n)$ ；条件2 $\sum_{y} P(y|x)=1$
一般需进一步转化为求最小值问题：
$\underset{P}{min} \ -H(P) = \sum_{x,y} \tilde{P}(x)P(y|x)logP(y|x)$
约束条件：条件1 $E_P(f_i) = E_\tilde{P}(f_i),(i=1,2,...,n)$ ；条件2 $\sum_{y} P(y|x)=1$
求条件极值，一般采用拉格朗日乘数法（对于条件极值套路性解法），定义拉格朗日函数 $L(P,w)$ ，这里我们把 $P$ 和 $w$ 看成是自变量：
$L(P, w) = \sum_{x,y} \tilde{P}(x)P(y|x)logP(y|x) + w_0(1 - \sum_{y} P(y|x) ) + \sum_{i=1}^{n} w_i \left ( \sum_{x,y} \tilde{P}(x,y)f_i(x,y) - \sum_{x,y} \tilde{P}(x)P(y|x)f_i(x,y) \right ) $
对 $L(P, w)$ 的求极值，可以算得： $P(y|x) = exp(\sum_{i=1}^{n} w_i f_i(x,y) + w_0 -1 ) = \frac{exp(\sum_{i=1}^{n}w_i f_i(x,y))}{exp(1-w_0)}$
根据约束条件 $\sum_{y} P(y|x) = 1$ 得：
$Z_w(x) = \sum_y exp \left ( \sum_{i=1}^{n} w_i f_i(x,y) \right )$
$P_w(y|x) = \frac{1}{Z_w(x)} \cdot exp(\sum_{i=1}^{n} w_i f_i(x,y))$
步骤二：求 $w$ 的值
此处有两种方法，一是直接求 $L(P_w, w)$ 的极大值，确定参数 $w$ ，在确定 $P_w(y|x)$ 后，再通过 $\frac{\partial L(P_w, w)}{\partial w} = 0$ 求 $w$ 的值；
二是通过 极大似然法 得到对数似然函数，《统计学习方法》书中叙述较为简单，这里补充下：
首先看“单变量”的似然函数： $L(X=x_1, X=x2, ..., X=x_N; Y) = \prod_{i=1}^{N} P(X=x_i; Y)$
设 $N$ 为样本数， $x_j \in \{ a_1, a_2, ..., a_K \}$ ，即 $x$ 有 $K$ 种可能的取值。
$L(x, y) = P(x=a_1; y)^{n_1} P(x=a2; y)^{n_2} ... P(x=a_K; y)^{n_K}$ ， $n_1, n_2, ..., n_K$ 是取值为 $a_j$ 的样本的个数，可以用 $v(x=a_j)$ 表示。
所以， $L(x, y) = \prod_{j=1}^{K} P(x=a_j; y)^{v(x=a_j)}$ 。
接下来看书中的情况，求 $P(Y|X)$ 的似然函数，也就是“多变量”条件分布的似然函数：
$L(P) = P(y_1|x_1)^{v(x_1,y_1)} P(y_2|x_2)^{v(x_2,y_2)} ... P(y_K|x_K)^{v(x_K,y_K)} = \prod_{x,y} P(y|x)^{v(x,y)}$
如果对 $L(P)$ 开 $N$ 次方，得到 $L^*(P) = \prod_{x,y} P(y|x) ^ {\frac{v(x,y)}{N}} = \prod_{x,y} P(y|x)^{\tilde{P}(x,y)}$ ， 对求极值无影响。
转化为以上形式后，《统计学习方法》那一章节证明了结论，最终结论：最大熵模型的极大似然估计等价于对偶函数极大化。
最大熵模型的最终形式：
对于似然函数的最优化问题，常用的方法有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。通过常用的最优化算法可以确定 $w$ 参数，$w$` 确定后，最终最大熵模型等于：
$Z_w(x) = \sum_y exp \left ( \sum_{i=1}^{n} w_i f_i(x,y) \right )$
$P_w(y|x) = \frac{1}{Z_w(x)} \cdot exp(\sum_{i=1}^{n} w_i f_i(x,y))$
逻辑斯谛回归是最大熵模型的特例
这里通过一个例子来说明逻辑斯谛回归是最大熵模型的特例。
二分类问题
定义特征函数，其中 $g(x)$ 为提取每个x的特征，输出x特征，向量维度为约束条件的个数。
$f_i(x,y) = \left\{ \begin{matrix}
g(x)^{(i)}, & y=1 & \\
0, & x=1 &
\end{matrix} \right.$
一般地，特征函数可以是任意实值函数，所以这里把y=1中g(x)定义为提取每个x的特征。
将以上特征函数代入到之前求出的最大熵模型中：
$Z_w(x) = exp( \sum_{i=1}^{n} w^{(i)} g(x)^{(i)}) + exp( \sum_{i=1}^{n} w^{(i)} * 0) = 1 + exp( \sum_{i=1}^{n} w^{(i)} g(x)^{(i)})$
$P(y=1|x) = \frac{ exp( \sum_{i=1}^{n} w^{(i)} g(x)^{(i)}) }{ Z_w(x) } = \frac{exp( \sum_{i=1}^{n} w^{(i)} g(x)^{(i)}) }{Z_w(x)}$
$P(y=0|x) = \frac{ exp( \sum_{i=1}^{n} w^{(i)} 0) }{ Z_w(x) } = \frac{1}{ Z_w(x) }$
为了方便，将上式括号内记为向量的形式，仍记为 $w$ , $g(x)$ ，进一步简化得：
$P(y=1|x) = \frac{exp(w \cdot g(x) )}{1 + exp(w \cdot g(x))}$
$P(y=0|x) = \frac{1}{1+exp(w \cdot g(x))} = 1 - P(y=1|x)$
以上形式即为《统计学习方法》书上的逻辑斯谛回归的标准形式。
多分类问题
设类别 $y \in \{1,2,3,...,K\}$ ，对于不同类别，有不同的参数向量 $w_1, w_2, ..., w_K$ ，注意 $w_k$ 是一个向量 （每个向量的维度即为约束条件的数量）。相应地， $g(x)$ 也为一个向量。
$f(x,y) = \left \{\begin{matrix}
g(x), & 当y=k，k=1,2,...,K-1 & \\
0, & 当y=K &
\end{matrix}\right.$
那么，
$Z_w(x) = \sum_{y} exp(\sum_{i=1}^{n} w_i f_i(x,y)) = \sum_{k=1}^{K} exp( \sum_{i=1}^{n} w_k^{(i)} g(x)^{(i)} ) = 1 + \sum_{k=1}^{K-1} exp( \sum_{i=1}^{n} w_k^{(i)} g(x)^{(i)} )$
其中 $w_k^{(i)}$ 和 $g(x)^{(i)}$ 代表 $w_k$ 和 $g(x)$ 向量中的第 $i$ 个元素。
当 $k \in \{1,2,3,...,K-1\}$ 时， $P(Y=k|x) = \frac{ exp( \sum_{i=1}^{n} w_k^{(i)} g(x)^{(i)} ) }{1 + \sum_{k=1}^{K-1} exp( \sum_{i=1}^{n} w_k^{(i)} g(x)^{(i)} ) }$
特别地，当 $k=K$ 时， $P(Y=K|x) = \frac{1}{1 + \sum_{k=1}^{K-1} exp( \sum_{i=1}^{n} w_k^{(i)} g(x)^{(i)} )}$
为了方便，将上式括号内记为向量的形式，仍记为 $w$ ， $g(x)$ ，进一步简化得：
$P(y=k|x) = \frac{exp(w_k \cdot g(x))}{ 1 + \sum_{k=1}^{K-1} exp(w_k \cdot g(x)) }$ ， 其中 $k \in \{1,2,3,...,K-1\}$
$P(y=K|x) = \frac{1}{1 + \sum_{k=1}^{K-1} exp(w_k \cdot g(x)) }$
以上形式即为《统计学习方法》书上的多项逻辑斯谛回归的形式。
我理解最大熵模型是一种很抽象的描述，在不同的算法中我们需要定义不同的特征函数求出对应的权重值，来解决不同的问题。
总结
日常生活中处处存在最大熵模型，这里疏理了下对《统计学习方法》中最大熵模型的理解；通过举例说明了逻辑斯谛模型也是最大熵模型的原则的应用。
多分类问题实际也是 $softmax$ 分类器的形式，后续也学习下 $softmax$ 的思想。
参考文献
李航统计学习方法（第六章） ，知乎
最大熵模型 ，知乎
《统计学习方法》第六章-逻辑斯谛回归与最大熵模型，李航