逻辑斯谛回归与最大熵模型

《统计学习方法》笔记 第6章

Posted by Cheereus on January 27, 2020

第6章 逻辑斯谛回归与最大熵模型

6.1 逻辑斯谛回归模型

6.1.1 逻辑斯谛分布

逻辑斯谛分布(logistic distribution)定义:

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

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

6.1.2 二项逻辑斯谛回归模型

二项逻辑斯谛回归模型(binomial logistic regression model)是一种分类模型,由条件概率分布 $P(Y \vert X)$ 表示,形式为参数化的逻辑斯谛分布:

其中,$x\in R^n$ 是输入,$Y \in \{0,1\}$ 是输出,$\omega\in R^n$ 和 $b \in R$ 是参数,$\omega$ 称为权值向量。$b$ 称为偏置,$\omega\cdot x$ 为 $\omega$ 和 $x$ 的内积。

逻辑斯谛回归比较两个条件概率的大小,将实例 $x$ 分到概率值较大的那一类。

有时为了方便,将权值向量和输入向量加以扩充,扔记作 $\omega,x$,即 $\omega=(\omega^{(1)},\omega^{(2)},\cdots,\omega^{(n)},b)^T, x=(x^{(1)},x^{(2)},\cdots,x^{(n),1})^T$。这时,逻辑斯谛回归模型如下:

一个事件的几率(odds)是指该事件发生的概率与该事件不发生的概率的比值。如果事件发生的概率是 $p$ 那么该事件的几率是 $\displaystyle\frac{p}{1-p}$,该事件的对数几率(log odds)或 logit 函数是

对逻辑斯谛回归而言,有:

即在逻辑斯谛回归模型中,输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数。或者说,输出 $Y=1$ 的对数几率是由输入 $x$ 的线性函数表示的模型,即逻辑斯谛回归模型。

6.1.3 模型参数估计

逻辑斯谛回归模型学习时,对于给定的训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$,其中 $x_i \in R_n, \ y_i \in \{0,1\}$,可以应用极大似然估计法估计模型参数,从而得到逻辑斯谛回归模型。

设:

似然函数为:

对数似然函数为:

对 $L(\omega)$ 求极大值,得到 $\omega$ 的估计值。

逻辑斯谛回归通常采用的方法是梯度下降法及拟牛顿法。

6.1.4 多项逻辑斯谛回归

6.2 最大熵模型

6.2.1 最大熵原理

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

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

熵满足下列不等式:

式中,$\vert X \vert$ 是 $X$ 的取值个数,当且仅当 $X$ 的分布是均匀分布时右边的等号成立。也就是说,当 $X$ 服从均匀分布时,熵最大。

最大熵原理通过熵的最大化来表示等可能性。

6.2.2 最大熵模型的定义

假设分类模型是一个条件概率分布 $P(Y \vert X)$,$X \in \mathcal{X} \subseteq R^n$ 表示输入,$Y \in \mathcal{Y}$ 表示输出,$\mathcal{X}$ 和 $\mathcal{Y}$ 分别是输入和输出的集合。这个模型表示的是对于给定的输入 $X$,以条件概率 $P(Y \vert X)$ 输出 $Y$。

给定一个训练数据集:

学习的目标是用最大熵原理选择最好的分类模型。

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

其中,$\mathcal{v}(X=x,Y=y)$ 表示训练数据中样本 $(x,y)$ 出现的频数,$\mathcal{v}(X=x)$ 表示训练数据中输入 $x$ 出现的频数,$N$ 表示训练样本容量。

用特征函数 $f(x,y)$ 描述输入 $x$ 和输出 $y$ 之间的某一个事实。其定义是

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

特征函数 $f(x,y)$ 关于模型 $P(Y \vert X)$ 与经验分布 $\widetilde{P}(X)$ 的期望值,用 $E_P(f)$ 表示:

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

将此式作为魔性学习的约束条件。

最大熵模型的定义为:

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

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

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

6.2.3 最大熵模型的学习

最大熵模型的学习可以形式化为约束最优化问题。

首先,引进拉格朗日乘子 $\omega_0,\omega_1,\cdots,\omega_n$,定义拉格朗日函数:

最优化的原始问题是:

对偶问题是:

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

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

且有

其中

$Z_\omega(x)$ 称为规范化因子;$f_i(x,y)$ 是特征函数;$\omega_i$ 是特征的权值。由上述两式表示的模型 $P_\omega=P_\omega(y \vert x)$ 就是最大熵模型。这里,$\omega$ 是最大熵模型中的参数向量。

之后,求解对偶问题外部的极大化问题

将其解记为 $\omega^*$,即

即最大熵模型的学习归结为对偶函数 $\Psi(\omega)$ 的极大化。

6.2.4 极大似然估计

对偶函数的极大化等价于最大熵模型的极大似然估计。

最大熵模型与逻辑斯谛回归模型有类似的形式,它们又称为对数线性模型(log linear model)。模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计。

6.3 模型学习的最优化算法

6.3.1 改进的迭代尺度法(improved interative scaling,IIS)

输入:特征函数 $f_i,f_2,\cdots,f_n$;经验分布 $\widetilde{P}(X,Y)$,模型 $P_\omega(y \vert x)$;

输出:最优参数值 $\omega_i^$;最优模型 $P_{\omega^}$。

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

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

  1. 令 $\delta_i$ 是方程 $\ \displaystyle\sum_{x,y}\widetilde{P}(x)P(y \vert x)f_i(x,y)\exp(\delta_i f^{#}(x,y))=E_{\widetilde P}(f_i)\$ 的解,这里 $f^{#}(x,y)=\displaystyle\sum_{i=1}^nf_i(x,y)$
  2. 更新 $\omega_i$ 值:$\omega_i \leftarrow \omega_i + \delta_i$

(3) 如果不是所有 $\omega_i$ 都收敛,重复步 (2

这一算法关键的一步是求解方程中的 $\delta_i$。如果 $f^{#}(x,y)$ 是常数,即对任何 $x,y$,有 $f^{#}(x,y)=M$,那么 $\delta_i$ 可以显示的表示成

如果 $f^{#}(x,y)$ 不是常数,那么必须通过数值计算求 $\delta_i$,简单有效的方法是牛顿法。

6.3.2 拟牛顿法(BFGS)

输入:特征函数 $f_i,f_2,\cdots,f_n$;经验分布 $\widetilde{P}(X,Y)$,目标函数 $f(\omega)$,梯度 $g(\omega)=\nabla f(\omega)$,精度要求 $\epsilon$;

输出:最优参数值 $\omega_i^$;最优模型 $P_{\omega^}(y \vert x)$。

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

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

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

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

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

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

其中,

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

第6章完结