统计学习方法笔记之逻辑斯谛模型与最大熵模型
in 机器学习 with 2 comments

统计学习方法笔记之逻辑斯谛模型与最大熵模型

in 机器学习 with 2 comments

逻辑斯谛回归(Logistic Regression)模型是经典的分类方法,而最大熵则是概率模型中学习的一个准则,将其推广到分类问题得到最大熵模型(maximum entropy model)。两者都属于对数线性模型。

逻辑斯谛模型

逻辑斯谛分布

设$X$是连续随机变量,$X$服从逻辑斯谛分布是指$X$具有以下分布函数和密度函数:

$$ F(x) = P(X< x) = \frac{1}{1+e^{\frac{-(x-\mu)}{\gamma}}} $$

$$ f(x) = F'(x) = \frac{e^{\frac{-(x-\mu)}{\gamma}}}{\gamma(1+e^{\frac{-(x-\mu)}{\gamma}})^2} $$

其中,$\mu$是位置参数,$\gamma >0$为形状参数。

逻辑斯谛分布的密度函数$f(x)$和分布函数$F(x)$如下所示。分布函数属于逻辑斯谛函数,其图像是一条$S$形曲线,该曲线以$(\mu, \frac{1}{2})$为中心对称,即满足:

$$ F(-x+\mu)- \frac{1}{2} = -F(x+\mu)+\frac{1}{2} $$

曲线在中心附近增长速度较快,在两端增长速度较慢。形状参数$\gamma$的值越小,曲线在中心附近增长越快。

逻辑斯谛分布

二项逻辑斯谛回归

二项逻辑斯谛回归模型是一种分类模型,由条件概率分布$P(Y|X)$表示,形式为参数化的逻辑斯谛分布,$X$的取值范围为实数,$Y$的取值为1或0,那么如下的条件概率分布:

$$ P(Y=1|x) = \frac{\exp(w \cdot x+b)}{1+\exp(w \cdot x+b)} \\ P(Y=0|x) = \frac{1}{1+\exp(w \cdot x+b)} $$

其中$w \cdot x$表示内积,$x \in R^n$,$w \in R^n$和$b \in R$是参数,$w$称为权值向量,$b$称为偏置。

对于输入的实例$x$,逻辑斯谛模型计算其条件概率$P(Y=1|x)$与$P(Y=0|x)$,通过比较大小将$x$分到概率值大的那一类。

有时为了方便,将权值向量与输入实例$x$进行扩充,仍记作$w,x$,即$w=(w^{(1)},w^{(2)},\cdots,w^{(n)}, b)^T$,$x=(x^{(1)},x^{(2)}, \cdots,x^{(n)},1)^T$,这时,逻辑斯谛模型就变成了:

$$ P(Y=1|x) = \frac{\exp(w \cdot x)}{1+\exp(w \cdot x)} \\ P(Y=0|x) = \frac{1}{1+\exp(w \cdot x)} $$

模型特点

一个事件的几率是指该事件发生的概率和不发生的概率的比值。如果一个事件发生的概率是$p$,那么该事件的几率就是$\frac{p}{1-p}$,该事件的对数几率就是:

$$ logit(p) = \log\frac{p}{1-p} $$

对于逻辑斯谛模型来说,$Y=1$的几率就是:

$$ \log \frac{P(Y=1|x)}{1-P(Y=1|x)} = w \cdot x $$

也就是说,在逻辑斯谛模型中,输出$Y=1$的对数几率是输入$x$的线性函数。考虑到公式

$$ P(Y=1|x) = \frac{\exp(w \cdot x)}{1+\exp(w \cdot x)} $$

可以得到,线性函数的值越接近于正无穷,概率值就越接近1;线性函数的值越接近负无穷,概率值就越接近0。

多项逻辑斯谛回归

设随机变量$Y$的取值集合为$\{1,2,\cdots,K\}$,那么多项逻辑斯谛回归模型是:

$$ P(Y=k|x) = \frac{\exp(w_k \cdot x)}{1+\sum^{K-1}_{k=1}\exp(w_k \cdot x)},k=1,2,\cdots,K-1 \\ P(Y=K|x) = \frac{1}{1+\sum^{K-1}_{k=1}\exp(w_k \cdot x)} $$

其中$x\in R^{n+1}$,$w \in R^{n+1}$。

模型参数估计

可以应用极大似然估计模型参数。

设:

$$ P(Y=1|x) = \pi(x),P(Y=0|x) = 1 - \pi(x) $$

似然函数为:

$$ \prod^N_{i=1} [\pi(x_i)]^{y_i}[1 - \pi(x_i)]^{1-y_i} $$

对数似然函数为:

$$ \begin{align} L(w) &= \sum^N_{i=1}[y_i \log \pi(x_i) + (1-y_i)\log(1-\pi(x_i))] \\ &=\sum^N_{i=1}\left[ y_i\log \frac{\pi(x_i)}{1-\pi(x_i)} + \log(1-\pi(x_i)) \right] \\ &= \sum^N_{i=1}[y_i(w \cdot x_i) - \log (1+\exp(w \cdot x_i))] \end{align} $$

对$L(w)$求极大值,得到$w$的估计值。这样,问题就变成了以对数似然函数为目标函数的最优化问题。逻辑斯谛回归学习中通常采用的方法是梯度下降法及拟牛顿法。

最大熵模型

最大熵原理认为,学习概论模型时,在所有可能的概率模型分布中,熵最大的模型时最好的模型。

假设离散随机变量$X$的概率分布是$P(X)$,则其熵为:

$$ H(P) = -\sum_x P(x)\log P(x) $$

熵满足下列不等式:

$$ 0 \leq H(P) \leq \log|X| $$

式中,$|X|$是$X$的取值个数,当且仅当$X$的分布是均匀分布时右边的等号成立,这就是说$X$服从均匀分布时,熵最大。换句话说,最大熵原理认为要选择的概率模型首先必须满足已有的事实,在没有更多信息的情况下,那些不确定的部分都是等可能的。

定义

首先考虑模型应该满足的条件。给定数据集,可以确定联合分布$P(X,Y)$的经验分布和$P(X)$的经验分布,记作$\widetilde{P}(X,Y)$和$\widetilde{P}(x)$:

$$ \widetilde{P}(X=x,Y=y) = \frac{v(X=x,Y=y)}{N}\\ \widetilde{P}(X=x) = \frac{v(X=x)}{N} $$

$v(X=x,Y=y)$表示样本$(x,y)$出现的频数;$v(X=x)$表示训练数据中样本$x$出现的频数,$N$代表训练样本容量。

特征函数$f(x,y)$描述输入$x$与输出$y$是否满足某一事实:

$$ f(x,y) = \left\{ \begin{align} 1,\ x\; and \; y \;satify \;a\;fact; \\ 0,\ otherwise \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{align} \right. $$

$E_{\widetilde{P}}(f)$代表特征函数$f(x,y)$对$\widetilde{P}(X,Y)$的期望值:

$$ E_{\widetilde{P}}(f) = \sum_{x,y}\widetilde{P}(x,y)f(x,y) $$

$E_P(f)$代表关于模型$P(Y|X)$特征函数$f(x,y)$关于模型$P(Y|X)$与$\widetilde{P}(X)$的期望值:

$$ E_P(f) = \sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y) $$

如果模型能够获取训练数据中的信息,那么就可以假设这两个期望值想等,即:

$$ E_P(f) = E_{\widetilde{P}}(f) $$

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

设满足所有约束条件的模型集合为:

$$ \mathcal{C}\equiv \{P\in \mathcal{P} | E_P(f_i = E_{\widetilde{P}}(f_i)),i=1,2,\cdots,n \} $$

定义在条件概率分布$P(Y|X)$上的条件熵为:

$$ H(P) = -\sum_{x,y}\widetilde{P}(x)P(y|x) \log P(y|x) $$

则模型集合$\mathcal{C}$中条件熵最大的模型称为最大熵模型。式中的对数为自然对数。

模型的学习

最大熵模型的学习也就是求解最大熵模型的过程。对于给定的数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$以及特征函数$f_i(x,y),i=1,2,\cdots,n$,最大熵模型的学习等价于约束最优化问题:

$$ \max_{P \in \mathcal{C}} H(P) = -\sum_{x,y}\widetilde{P}(x)P(y|x) \log P(y|x) \\ s.t. \ E_P(f_i) = E_{\widetilde{P}}(f_i), \quad i=1,2,\cdots,n \\ \sum_y P(y|x) = 1 $$

按照最优化问题的习惯,将求最大值问题改写为等价的求最小值问题:

$$ \min_{P \in \mathcal{C}} - H(P) = \sum_{x,y}\widetilde{P}(x)P(y|x) \log P(y|x) \\ s.t. \ E_P(f_i) = E_{\widetilde{P}}(f_i), \quad i=1,2,\cdots,n \\ \sum_y P(y|x) = 1 $$

这里,将约束最优化的原始问题转化为无约束最优化的对偶问题。首先,引入拉格朗日乘子$w_0,w_1,\cdots,w_n$,定义拉格朗日函数$L(P,w)$:

$$ L(P,w) = -H(P)+w_o(1-\sum_y P(y|x) ) + \sum^n_{i=1}w_i(E_{\widetilde{P}}(f_i)-E_P(f_i)) $$

最优化的原始问题是$\min_{P \in \mathcal{C}} \max_w L(P,w)$,对偶问题是$\max_w \min_{P \in \mathcal{C}}L(P,w)$。

首先,求解对偶问题的极小化问题$\min_{P \in \mathcal{C}}L(P,w)$。$\min_{P \in \mathcal{C}}L(P,w)$是$w$的函数,将其记作:

$$ \psi(w) = \min_{P \in \mathcal{C}}L(P,w) = L(P_w,w) $$

$\psi(w)$称为对偶函数,同时将其解记作:

$$ P_w = \arg \min_{P \in \mathcal{C}} L(P,w) = P_w(y|x) $$

具体地,求$L(P,w)$对$P(y|x)$的偏导数并令其等于0,在$\widetilde{P} > 0$的情况下,解得:

$$ P(y|x) = \frac{\exp(\sum^n_{i=1}w_i f_i(x,y))}{exp(1-w_0)} $$

由于$\sum_y P(y|x) = 1$,得:

$$ P_w (y|x) = \frac{1}{Z_w(x)}\exp(\sum^n_{i=1}w_i f_i(x,y)) $$

其中:

$$ Z_w(x) = \sum_y \exp(\sum^n_{i=1}w_if_i(x,y)) $$

称为规范化因子。

然后求解对偶问题外部的极大化问题$\max_w \psi(w)$,

将其解记为$w^*$,即$w^* = \arg \max_w \psi(w)$,也就是说,可以应用最优化算法求对偶函数$\psi(w)$的极大化,得到$w^*$,即最大熵模型。

最优化算法

改进的迭代尺度算法IIS

假设输入特征函数$f_1(x,y),f_2(x,y),\cdots,f_n(x,y)$,经验分布$\widetilde{P}(X,Y)$,模型$P_w(y|x)$,按以下步骤求解:

(1)对所有$i \in \{1, 2, \cdots, n\}$,取初值$w_i=0$;

(2)对每一$i \in \{1, 2, \cdots, n\}$,

​ (a)令$\delta_i$是方程

$$ \sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y)\exp(\delta_i,f^\#(x,y))=E_{\widetilde{P}}(f_i) $$

的解,其中:

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

​ (b)更新$w_i$值:$w_i \gets w_i + \delta_i$;

(3)如果不是所有的$w_i$都收敛,重复(2)步;

拟牛顿法

对于最大熵模型而言,

$$ P_w(y|x) = \frac{\exp(\sum^n_{i=1}w_i f_i(x,y))}{\sum_y \exp(\sum^n_{i=1}w_if_i(x,y))} $$

目标函数:

$$ \min_{w \in R^n} f(w) = \sum_x \widetilde{P}(x)\log \sum_y \exp(\sum^n_{i=1}w_i f_i(x,y)) - \sum_{x,y}\widetilde{P}(x,y)\sum^n_{i=1}w_if_i(x,y) $$

梯度:

$$ g(w) = \left( \frac{\partial f(w)}{\partial w_1}, \frac{\partial f(w)}{\partial w_2}, \cdots, \frac{\partial f(w)}{\partial w_n} \right)^T $$

其中

$$ \frac{\partial f(w)}{\partial w_i} = \sum^n_{i=1}\widetilde{P}(x,y)P_w(y|x)f_i(x,y) - E_{\widetilde{P}}(f_i), \quad i=1,2,\cdots,n $$

响应的拟牛顿法BFGS如下:

假设输入特征函数$f_1(x,y),f_2(x,y),\cdots,f_n(x,y)$,经验分布$\widetilde{P}(X,Y)$,目标函数$f(w)$,梯度$g(w)=\nabla f(w)$,精度要求$\varepsilon$,按以下步骤求解:

(1)选定初始点$w^{(0)}$,取$B_0$为正定对称矩阵,置$k=0$;

(2)计算$g_k=g(w^{(k)})$。若$||g_k|| < \varepsilon$,则停止计算,得$w^* = w^{(k)}$;否则转(3);

(3)由$B_k p_k = -g_k$,求出$p_k$;

(4)一维搜索:求$\lambda_k$使得:

$$ f(w^{(k)} +\lambda_kp_k) = \min_{\lambda \geq 0}f(w^{(k)} + \lambda p_k) $$

(5)置$w^{(k+1)} = w^{(k)}+\lambda_k p_k$;

(6)计算$g_{k+1} = g(w^{(k+1)})$,若$||g_{k+1}|| < \varepsilon$,则停止计算,得$w^* = w^{(k+1)}$;否则,按下式求出$B_{k+1}$:

$$ B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T \delta_k} - \frac{B_k \delta_k \delta^T_k B_k}{\delta_k^T B_k \delta_k} $$

其中,

$$ y_k = g_{k+1} - g_k, \quad \delta_k = w^{(k+1)} - w^{(k)} $$

(7)置$k = k+1$,转(3);

参考

李航《统计学习方法(第二版)》第六章

Responses
  1. 厉害厉害,看得脑阔疼。

    Reply
    1. @Flicker

      我也是硬着头皮看的哈哈哈

      Reply