前言

参考：

• 《统计学习》—李航（蓝皮）
• 部分来自网络的内容（主要是liaohuiqiang的博客）

逻辑回归

模型

关于对数几率和logit函数的引入我们在感知机的文章中已经提到
下面正式介绍逻辑回归（又称逻辑斯蒂回归）

逻辑斯谛分布 ：设X是连续随机变量，X服从逻辑斯谛分布，则具有以下分布函数和密度函数。其中\mu为位置参数，\gamma>0为形状参数。
::: align-center
\begin{aligned} &f(x)=\frac{e^{-\frac{(x-\mu)}{\gamma}}}{\gamma(1+e^{-\frac{(x-\mu)}{\gamma}})^2}\\ &F(x)=\frac{1}{1+e^{-\frac{(x-\mu)}{\gamma}}} \end{aligned}

:::
此为逻辑斯蒂分布的标准定义

二项逻辑回归模型

实际上，简单地说，若我们考虑对数几率函数logit(p)=\log\frac{p}{1-p}=\omega x
计算反函数后可得
::: align-center
p=\frac{e^{\omega x}}{1+e^{\omega x}}

:::
若p是正类P(Y=1|x)的概率，则
::: align-center
\begin{aligned} &P(Y=1|x)=\frac{e^{\omega x}}{1+e^{\omega x}}=\frac{1}{1+e^{-\omega x}}\\ &P(Y=0|x)=\frac{1}{1+e^{\omega x}}=\frac{e^{-\omega x}}{1+e^{-\omega x}} \end{aligned}

:::
由标准定义，容易知此时\mu=0,\gamma=\frac{1}{\omega}，这称为二项逻辑回归，它是一种分类模型

策略和算法

学习Logistic回归模型时，可以应用极大似然估计法估计模型参数。
设P(Y=1|x)=\pi(x),P(Y=0|x)=1-\pi(x)，则似然函数为
::: align-center
\prod_{i=1}^N[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}

:::
注：这是伯努利分布，y_i只可能取0或1，写出分段函数后合并结果（将对y_i的分情况讨论转化为上面的幂次项）得到上面的似然函数

取对数得对数似然函数
::: align-center
\begin{aligned} &L(\omega)=\sum_{i=1}^{N}[y_i\log\pi(x_i)+(1-y_i)\log(1-\pi(x_i))\\ &=\sum_{i=1}^N[y_i\log\frac{\pi(x_i)}{1-\pi(x_i)}+\log(1-\pi(x_i))]\\ &=\sum_{i=1}^N[y_i(\omega x_i)-\log(1+e^{\omega x_i})] \end{aligned}

:::
对L(\omega)求极大，得到\omega的估计值\hat{\omega}。问题变成以对数似然函数为目标的最优化问题，
::: align-center
\arg\max_{\omega}L(\omega)=\sum_{i=1}^{N}[y_i(\omega x_i)-\log(1+e^{\omega x_i})]

:::

注：这里的“似然函数”与之前的损失函数有区别，对于损失函数损失越小越好，故应求能使其达到最小值的参数，而对于此“似然函数”，似然效果应“尽可能的好”，特别地，对于我们上面的给出的似然函数，应求在给定样本集时使其值最大的参数

Logistic回归学习中通常采用梯度下降法及拟牛顿法。

最大熵模型

最大熵原理

最大熵原理是概率模型学习的一个准则，认为在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。

通常用约束条件来确定概率模型的集合，所以最大熵原理可表述为“在满足约束条件的模型集合中选取熵最大的模型”。
::: align-center
\begin{aligned} &H(P)=-\sum_{x}P(x)\log P(x)\\ &0\le H(P)=\log |X| \end{aligned}

:::
|X|是X的取值个数，当且仅当X是均匀分布时，不等式右边的等号成立，熵最大。

最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分是“等可能的”，等概率表示了对事实的无知。因为没有更多信息，这种判断是合理的，“等可能”不易操作，可通过“熵最大”来表示。故此时熵最大的模型就是最好的模型。

最大熵模型

给定训练数据，可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布，分别以\widetilde{P}(X,Y)和\widetilde{P}(X)表示
::: align-center
\begin{aligned} &\widetilde{P}(X,Y)=\frac{v(X=x,Y=y)}{N}\\ &\widetilde{P}(X)=\frac{v(X=x)}{N} \end{aligned}

:::
其中v是表示频数的函数，N表示样本容量
用特征函数f(x,y)描述x和y之间的某一事实，它是一个二值函数（一般地，特征函数可以是任意实值函数）。
::: align-center
\left\{\begin{matrix} 1 & x,y\space meet\space some\space condition\\ 0 & otherwise \end{matrix}\right .

:::

特征函数f(x,y)关于经验分布\widetilde{P}(X,Y)的期望值，用E_{\widetilde{P}}(f)=\sum_{x,y}\widetilde{P}(x,y)f(x,y)表示。
::: align-center
E_{\widetilde{P}}(f)=\sum_{x,y}\widetilde{P}(x,y)f(x,y)

:::

特征函数f(x,y)关于模型P(Y|X)与经验分布\widetilde{P}(X)的期望值，用E_{p}(f)表示。
::: align-center
E_{P}(f)=\sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y)

:::

如果模型能够获取训练数据中的信息，那么就可以假设这里两个期望值相等，即
::: align-center
E_{P}(f)=E_{\widetilde{P}}(f)

:::
或
::: align-center
\sum_{x,y}\widetilde{P}(x,y)f(x,y)=\sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y)

:::
将上式作为模型学习的约束条件，假如有n个特征函数f_i(x,y),那么就有n个约束条件

最大熵模型的定义

假设满足所有约束条件的模型集合为：
::: align-center
\mathcal{C}=\{P\in\mathcal{P}|E_{P}(f)=E_{\widetilde{P}}(f),i=1,2,\cdots,n\}

:::
定义在条件概率分布P(Y|X)上的条件熵为：
::: align-center
H(P)=\sum_{x,y}\widetilde{P}(x)P(y|x)\log P(y|x)

:::
则模型集合\mathcal{C}中条件熵H(P)最大的模型称为最大熵模型。

最大熵模型的学习

最大熵模型的学习问题可归结为最优化问题
::: align-center
\begin{aligned} &\max_{P\in\mathcal{C}}H(P)=-\sum_{x,y}\widetilde{P}(x)P(y|x)\log P(y|x)\\ &s.t.\space E_{P}(f_i)=E_{\widetilde{P}}(f_i),i=1,2,\cdots,n\\ &\sum_y P(y|x)=1 \end{aligned}

:::
按照习惯可将其改写为求解最小值问题
::: align-center
\begin{aligned} &\min_{P\in\mathcal{C}}-H(P)=\sum_{x,y}\widetilde{P}(x)P(y|x)\log P(y|x)\\ &s.t.\space E_{P}(f_i)-E_{\widetilde{P}}(f_i)=0,i=1,2,\cdots,n\\ &1-\sum_y P(y|x)=0 \end{aligned}

:::
可以知道，这是一个条件极值问题，且函数的性质较好，可使用拉格朗日乘数法求解，故定义拉格朗日函数
::: align-center
L(P,\omega)=-H(P)+\omega_0(1-\sum_y P(y|x))+\sum_{i=1}^n\omega_i(E_{P}(f_i)-E_{\widetilde{P}}(f_i))

:::
此时最优化问题可表示为
::: align-center
\min_{P\in\mathcal{C}}\space\max_{\omega}L(P,\omega)

:::
注：除了数学分析中对拉格朗日乘数法的代数解释外，笔者还需要指出带参数的约束项又称为“罚项”，要将罚项参数最大化的目的就是为了在不满足约束条件时，惩罚力度能够“足够大”，那么此时函数值就与满足约束条件时能够产生足够大的偏差，从而起到“约束”的效果，这就是上面最小值问题内部取最大的原因
它的对偶问题为
::: align-center
\max_{\omega}\space\min_{P\in\mathcal{C}}L(P,\omega)

:::
可证明L(P,\omega)是关于P的凸函数，在此时最优化问题和其对偶问题是等价的,可以通过求解对偶问题求解最优化问题

首先可求解对偶问题内部的极小值问题，它的解为关于\omega的函数，记为\Psi(\omega)，即
::: align-center
\Psi(\omega)=\min_{P\in\mathcal{C}}L(P,\omega)=L(P_\omega,\omega)

:::
其中\Psi(\omega)称为对偶函数，同时将其最优化问题的解P_{\omega}记为
::: align-center
P_{\omega}=\arg\min_{P\in\mathcal{C}}L(P,\omega)=P_{\omega}(y|x)

:::
因为求解此最优化问题的解，涉及到的变量为P(y|x)

求L(P,\omega)对P(y|x)的偏导数，令其为零,得驻点为
::: align-center
P(y|x)=exp(\sum_{i=1}^n\omega_if_i(x,y)+\omega_0-1)=\frac{exp(\sum_{i=1}^n \omega_if_i(x,y))}{exp(1-\omega_0)}

:::
此时一个需要格外注意的问题就是概率论的基本假设—所有概率的和必须为1，这里我们求了式子关于概率的偏导数，这可能会破坏基本假设，即这里实际上得到的驻点，可能并不满足\sum_{y}P(y|x)=1这个基本约束，为此结果必须归一化

代入约束条件可得
::: align-center
\sum_y \frac{exp(\sum_{i=1}^n \omega_if_i(x,y))}{exp(1-\omega_0)}=1

:::
因为分母是常数，故有
::: align-center
exp(1-\omega_0)=\sum_y exp(\sum_{i=1}^n\omega_if_i(x,y))

:::
回代回原式即可得归一化后的解
::: align-center
P_{\omega}(y|x)=\frac{1}{Z_{\omega}(x)}exp(\sum_{i=1}^n\omega_if_i(x,y))（*）

:::
其中Z_{\omega}(x)=\sum_y exp(\sum_{i=1}^n\omega_if_i(x,y))称为规范化因子

之后即可求解最优化问题外部的极大化\Psi(\omega)问题，即
::: align-center
\omega^*=\arg\max_{\omega}\Psi(\omega)

:::

得到\omega^*后代入P_{\omega}(y|x)得到P_{\omega^*}(y|x)，即得到学习后的模型（最大熵模型）

策略和算法

从以上最大熵模型学习中可以看出，最大熵模型是由（*）式表示的条件概率分布。下面证明对偶函数的极大化等价于最大熵模型的极大似然估计。得证后即可通过似然函数使用相应的算法估计参数

已知训练数据的经验概率分布\widetilde{P}(X,Y)，条件概率分布P(Y|X)的对数似然函数表示为
::: align-center
L_{\widetilde{P}}(P_{\omega})=\log\prod_{x,y}P(y|x)^{\widetilde{P}(x,y)}=\sum_{x,y}\widetilde{P}(x,y)\log P(y|x)

:::
当条件概率分布P(Y|X)为最大熵模型时，对数似然函数变为
::: align-center
\begin{aligned} &L_{\widetilde{P}}(P_{\omega})=\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^{n}\omega_if_i(x,y)-\sum_{x,y}\widetilde{P}(x,y)\log Z_{\omega}(x)\\ &=\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^{n}\omega_if_i(x,y)-\sum_{x}\widetilde{P}(x)\log Z_{\omega}(x) \end{aligned}

:::
对偶函数由上面的推导得其应为拉格朗日函数代入P_{\omega}后的结果，即
::: align-center
\begin{aligned} &\Psi(\omega)=\sum_{x,y}\widetilde{P}(x)P_{\omega}(y|x)\log P_{\omega}(y|x)+\sum_{i=1}^n\omega_i(\sum_{x,y}\widetilde P(x,y)f_i(x,y)-\sum_{x,y}\widetilde{P}(x)P_{\omega}(y|x)f_i(x,y))\\ &=\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^n \omega_i f_i(x,y)+\sum_{x,y}\widetilde{P}(x)P_{\omega}(y|x)(\log P_{\omega}(y|x)-\sum_{i=1}^n \omega_i f_i(x,y))\\ &=\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^n \omega_i f_i(x,y)+\sum_{x,y}\widetilde{P}(x)P_{\omega}(y|x)\log Z_{\omega}(x)\\ &=\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^n \omega_i f_i(x,y)+\sum_{x,y}\widetilde{P}(x)\log Z_{\omega}(x) \end{aligned}

:::
可以发现对偶函数等于对数似然函数，证明对偶问题中的对偶函数极大化等价于最大熵模型的极大似然估计

此时最大熵模型的学习问题转化为求解对数似然函数
::: align-center
\begin{aligned} &L_{\widetilde{P}}(P_{\omega}) =\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^{n}\omega_if_i(x,y)-\sum_{x}\widetilde{P}(x)\log Z_{\omega}(x)\\ &Z_{\omega}(x)=\sum_y exp(\sum_{i=1}^n\omega_if_i(x,y)) \end{aligned}

:::

极大化的问题
或对偶函数
::: align-center
\begin{aligned}&\Psi(\omega)=P_{\omega}(y|x)=\frac{1}{Z_{\omega}(x)}exp(\sum_{i=1}^n\omega_if_i(x,y))\\ &Z_{\omega}(x)=\sum_y exp(\sum_{i=1}^n\omega_if_i(x,y)) \end{aligned}

:::

极大化的问题

最大熵模型表现为以上形式，与Logistic回归模型有类似的形式，它们又称对数线性模型。

模型学习的最优化算法

Logistic回归模型，最大熵模型的学习以似然函数为目标函数的最优化问题，通常通过迭代算法求解。从最优化观点看，这时的目标函数具有很好的性质，它是光滑的凸函数，因此多种最优化方法都使用，保证能找到全局最优解。

常用的方法有改进的迭代尺度法，梯度下降法，牛顿法或拟牛顿法。牛顿法或拟牛顿法一般收敛速度更快。

简单练习

逻辑回归

解：
构建逻辑回归模型（未增广特征向量形式）
::: align-center
P(Y=1|X)=\sigma(\omega^Tx+b)=\frac{e^{(\omega_1x_1+\omega_2x_2+\omega_3x_3+b)}}{1+e^{(\omega_1x_1+\omega_2x_2+\omega_3x_3+b)}}

:::
其中\omega=\begin{bmatrix}\omega_1\\\omega_2\\\omega_3\end{bmatrix}，b\in\mathbb{R}
求解优化问题
::: align-center
\arg\max_{\omega}L(\omega)=\sum_{j=1}^{6}[y_i(\omega^T x_j+b)-\ln(1+e^{\omega^T x_j+b})]

:::
这里我们使用全局梯度“下降”法，计算
::: align-center
\begin{aligned} &\frac{\partial L}{\partial \omega}=\sum_{j=1}^6[y_jx_j-\frac{e^{\omega^T x_j+b}}{1+e^{\omega^T x_j+b}}x_j]=\sum_{j=1}^6[y_j-\sigma(\omega^Tx_j+b)]x_j\\ &\frac{\partial L}{\partial b}=\sum_{j=1}^6[y_j-\frac{e^{\omega^T x_j+b}}{1+e^{\omega^T x_j+b}}]=\sum_{j=1}^6[y_j-\sigma(\omega^Tx_j+b)] \end{aligned}

:::
迭代公式为
::: align-center
\begin{aligned} &\omega_{k+1}=\omega_{k}+\frac{\partial L}{\partial \omega}\\ &b_{k+1}=b_k+\frac{\partial L}{\partial b} \end{aligned}

:::
注：这里中间是加号

若干次迭代后，参数收敛至\omega=(1.12,0.98,0.85)^T,b=-3.76
此时带入预测样本点(1,2,-2)^T，计算得P(Y=1|X)=0.058<0.5
所以此点为负类点

最大熵原理

解：
（1）
根据题干要求，要求最大化概率分布p_i的熵损失函数-\sum_{i=1}^6p_i\ln p_i，可以得知的信息为来自样本的经验期望E(X)=4.5（随机变量X为骰子的点数），由此可知要求解约束优化问题
::: align-center
\begin{aligned} &\max_{p_i}-\sum_{i=1}^6p_i\ln p_i\\ &s.t.\space \sum_{i=1}^6 ip_i=4.5\\ &\sum_{i=1}^6p_i=1 \end{aligned}

:::
按照习惯将其改写为求极小值问题
::: align-center
\begin{aligned} &\min_{p_i}\sum_{i=1}^6p_i\ln p_i\\ &s.t.\space \sum_{i=1}^6 ip_i-4.5=0\\ &\sum_{i=1}^6p_i-1=0 \end{aligned}

:::
构造拉格朗日函数
::: align-center
\mathcal{L}(p_i,\lambda,\mu)=\sum_{i=1}^6p_i\ln p_i+\lambda(\sum_{i=1}^6 ip_i-4.5)+\mu(\sum_{i=1}^6p_i-1)=0

:::
对p_i求偏导并令其等于零
::: align-center
\sum_{i=1}^6\ln p_i+1+\lambda i+\mu=0

:::
也即求和内的每一项都为零
::: align-center
\ln p_i+1+\lambda i+\mu=0

:::
解得p_i=e^{-\lambda i-\mu-1}=\frac{e^{-\lambda i}}{Z}，其中Z=\sum_{j=1}^6 e^{-\lambda j}是规范化因子，由上面第二个约束条件得到

然后由第一个约束条件得到
::: align-center
\frac{\sum_{i=1}^6 ie^{-\lambda i}}{Z}=4.5\Rightarrow f(\lambda)=\frac{\sum_{i=1}^6 ie^{-\lambda i}}{Z}-4.5=0

:::

之后使用数值方法（如牛顿迭代法）得到\lambda的数值解，这里我们使用牛顿迭代法作为示例
令E(i)=\frac{\sum_{i=1}^6 ie^{-\lambda i}}{Z}，则f'(\lambda)=\frac{dE[i]}{d\lambda}
若读者将\frac{dE(i)}{d\lambda}按照求导商法则和链式法则展开，整理后会发现其等于-\frac{\sum_{i=1}^6i^2e^{-\lambda i}}{Z}+(\frac{\sum_{i=1}^6ie^{-\lambda i}}{Z})^2=-E(i^2)+E^2(i)，也就是说f'(\lambda)=-Var(i)，这个结论对于类似形式（指数函数族）的最大熵约束优化问题普适，可用于简化一部分计算

如此，牛顿迭代公式为
::: align-center
\lambda_{k+1}=\lambda_k-\frac{E(i)-4.5}{-Var(i)}

:::
若干次迭代后解收敛至\lambda=-0.371（假设\epsilon=1e-6)
则回代得到概率分布为
::: align-center
p_i=\frac{e^{0.371 i}}{\sum_{j=1}^6e^{0.371 j}}

:::
并得p_1\approx0.05,p_2\approx0.07,p_3\approx0.10,p_4\approx0.15,p_5\approx 0.23,p_6\approx0.40

（2）
设四种套餐所占的销售份额为p_i,i=1,2,3,4，另设其对应的单价v_i,i=1 ,2,3,4分别为8，3，2，1
要利用总营业额和就餐人次，我们需要首先求得单价的期望，对于样本来说，单价的平均值，故有
::: align-center
\sum_{i=1}^4v_ip_i=\frac{2.5\times10^5}{1\times10^5}=2.5

:::
作为约束条件

故此问题又可变为约束优化问题
::: align-center
\begin{aligned} &\min_{p_i}\sum_{i=1}^4p_i\ln p_i\\ &s.t.\space \sum_{i=1}^4 v_ip_i-2.5=0\\ &\sum_{i=1}^4p_i-1=0 \end{aligned}

:::
采用和（1）类似的方法，最后求得p_1=0.1,p_2=0.25,p_3=0.30,p_4=0.35，故销售份额分别为10%，25%，30%，35%