ML-逻辑回归

基础

逻辑回归（logistic regression）是统计学习中的经典分类方法，虽然被称为回归，但其实是个分类模型。其本质是假设某个数据服从逻辑分布，就可以使用极大似然法估计出其线性回归的参数，之后再使用 Sigmoid 逻辑函数对其分类。
面试的时候千万不要说你很了解 LR，因为细节真的太多了😂

逻辑回归模型

逻辑回归分布

设 X 是连续随机变量，X 服从逻辑分布是指具有下列分布函数和密度函数：
$$ F(x) = P(X<=x) = {\frac {1} {1 + e^{-(x-\mu)/\gamma}}} $$
$$ f(x) = F^‘(x) = {\frac {e^{-(x-\mu)/\gamma}} {\gamma(1+e^{-(x-\mu)/\gamma})^2}} $$
$\mu$ 为位置参数，$\gamma>0$ 为形状参数。

分布函数属于逻辑函数，其分布是一条 S 型曲线（sigmoid curve），该曲线以点 $(\mu, {\frac {1} {2}})$ 为中心对成，即满足
$$ F(-x + \mu) - {\frac {1} {2}} = -F(x-\mu) + {\frac {1} {2}} $$
该曲线在中心附近增长速度较快，在两端增长速度较慢。同时逻辑回归的分布函数在 $\mu=0,\gamma=1$ 的特殊参数下就是 Sigmoid 逻辑函数。
形状参数 $\gamma$ 越小，曲线在中心位置的增长越快。

二项逻辑回归模型

二项逻辑回归模型（binomial logistic regression model）是一种分类模型，由条件概率分布 P(Y|X) 表示，形式为参数化的逻辑分布。
$$ P(Y=1|x) = {\frac {\exp{(w·x+b)}} {1+\exp{(w·x+b)}}} $$
$$ P(Y=0|x) = {\frac {1} {1+\exp{(w·x+b)}}} $$
随机变量 X 取值为实数，随机变量 Y 取值为 1 或 0。
$x\in R^n$ 是输入，$Y\in{0,1}$ 是输出，$w\in R^n$ 和 $b\in R$ 是参数，$w$ 称为权值向量，$b$ 称为偏置，$w·x$ 是 $w$ 和 $x$ 的内积。

至此，对于给定的输入实例，可以根据上述公式求得 $P(Y=1|x)$ 和 $P(Y=0|x)$ 的概率，逻辑回归比较两个值的大小，然后将实例分到概率较大的一类中。

某个事件的几率（odds）是指该事件发生的概率与不发生概率的比值。如果事件发生的概率为 $p$，那么该事件的几率就是 ${\frac {p} {1-p}}$，该事件的对数几率（log odds）或 logit 函数是：
$$ logit(p) = log {\frac {p} {1-p}} $$

而对于逻辑回归而言，即可得：
$$ log {\frac {P(Y=1|x)} {1-P(Y=1|x)}} = w·x $$

也就是说在逻辑回归模型中，输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数，即可将线性函数 $w·x$ 转换为概率：
$$ P(Y=1|x) = {\frac {exp(w·x)} {1+exp(w·x)}} $$

此时线性函数的值越接近正无穷，概率值就越接近 1，线性函数的值越接近负无穷，概率值就越接近 0，即此模型就是概率回归模型。

多项逻辑回归模型

前面说的二项逻辑回归模型可以通过扩展随机变量 Y 的取值集合 $Y\in{1,2,3,…,K}$，那么多项逻辑回归的模型是：
$$ P(Y=k|x) = {\frac {exp(w_k·x)} {1+sum_{k=1}^{K-1} exp(w_k·x)}} , \quad k = {1, 2, 3, …, K}$$
其中 $x\in R^{n+1}, w_k\in R^{n+1}$

模型参数估计

在逻辑回归的学习中，对于给定的数据集，可以使用极大似然估计法估计模型参数，从而得到逻辑回归模型
假设：
$$ P(Y=1|X) = \pi(x), \quad P(Y=0|X) = 1 - \pi(x) $$
似然函数：
$$ \Pi_{i=1}^N [\pi(x_i)]^{y_i} [1-\pi(x_i)]^{1-y_i} $$
对数似然函数：
$$\begin{equation}\begin{split}
L(w) &= 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(w·x_i) - log(1+exp(w·x_i))]
\end{split}\nonumber\end{equation}$$
对 $L(w)$ 求极大值，从而得到 $w$ 的估计值。

至此问题就变成了以对数似然函数为目标的最优化问题。逻辑斯谛回归中通常采用的方法是：

改进的迭代尺度法
梯度下降法
牛顿法
拟牛顿法

改进的迭代尺度法

改进的迭代尺度法（improved iterative scaling, IIS）是一种最大熵模型学习的最优化算法。
IIS 的想法是：假设最大熵模型当前的参数向量是 $w=(w_1,w_2,…,w_n)^T$，那希望找到新的参数向量 $w+\delta = (w_1+\delta_1,w_2+\delta_2,…,w_n+\delta_n)^T$，以此使得模型的对数似然函数值增大。即找到一种参数向量的更新方法：$\tau:w \rightarrow w+\delta$，那么就可以使用这一方法，直至找到对数似然函数的最大值。

改进的迭代尺度算法 IIS ：

输入：特征函数 $f_1,f_2,…,f_n$；经验分布 $\widetilde{P}(X,Y)$，模型 $P_w(y|x)$

输出：最优参数值 $w_i^*$；最优模型 $P_{w^*}$

过程：

对所有的 $i \in {1,2,…,n}$，取初始值 $w_i=0$。

对每一个 $i \in {1,2,…,n}$：

a. 令 $\delta_i$ 是方程 $sum_{x,y} \widetilde{P}(x) P(y|x) f_i(x,y) \exp{(\delta_i sum_{i=1}^nf_i(x,y))} = E_{\widetilde{P}}(f_i)$ 的解。

b. 更新 $w_i$ 值：$w_i \leftarrow w_i + \delta_i$。

如果所有的 $w_i$ 都收敛，则继续重复步骤 2。
这一步骤的关键是求解 $\delta_i$。如果 $sum_{i=1}^nf_i(x,y)$ 是常数，即对所有的 x,y 都有 $sum_{i=1}^nf_i(x,y) = M$，那么 $\delta_i$ 就可以显示地表示为
$$ \delta_i = {\frac {1} {M}} \log{\frac {E_{\widetilde{P}} (f_i)} {E_P (f_i)}} $$
如果 $sum_{i=1}^nf_i(x,y)$ 不是常数，则必须通过数值计算求 $\delta_i$。

梯度下降法

梯度下降法（gradient descent）的计算过程就是沿着梯度下降的方向求解极小值（也可以沿着梯度上升的方向求最大值）。
$$ \theta_1 = \theta_0 - \alpha {\frac {\delta} {\delta \theta_j}} J(\theta) $$
$\alpha$ 被称为学习率或步长，用来控制每一步行走的距离。其不能太大，也不能太小。

梯度下降法：

输入：特征函数 $f_1,f_2,…,f_n$；经验分布 $\widetilde{P}(X,Y)$，模型 $P_w(y|x)$

输出：最优参数值 $w_i^*$；最优模型 $P_{w^*}$

过程：

初始化终止距离 $\epsilon$ 以及步长 $\alpha$。

确定当前位置的损失函数梯度，对于 $\theta_i$，其梯度表达式如下：
$$ {\frac {\delta} {\delta \theta_j}} J(\theta) $$

使用步长乘以损失函数的梯度得到当前的下降距离，即 $\alpha {\frac {\delta} {\delta \theta_j}} J(\theta)$。

确定是否所有的 $\theta_i$ 都小于终止距离 $\epsilon$，如果都小于则确定当前的 $\theta_i$ 为本次计算结果。

更新表达式 $\theta_i = \theta_i - \alpha {\frac {\delta} {\delta \theta_i}} J(\theta)$ 然后转入步骤 2。

拟牛顿法

最大熵模型还可以应用牛顿法或拟牛顿法。

最大熵模型学习的 BFGS 算法：

输入：特征函数 $f_1,f_2,…,f_n$；经验分布 $\widetilde{P}(X,Y)$，目标函数 $f(w)$，梯度 $g(w)= \nabla{f(w)}$，精度要求 $\epsilon$

输出：最优参数值 $w_i^*$；最优模型 $P_{w^*}$

过程：

选定初识点 $w^{(0)}$，取 $B_0$ 为正定对称矩阵，置 $k=0$

计算 $g_k=g(w^{(k)})$ 。若 $||g_k||<\epsilon$ 则停止计算，得 $w^*=w^{(k)}$；否则转步骤 3

由 $B_k p_k = -g_k$ 求出 $p_k$

一维搜索：求 $\lambda_k$ 使得
$$ f(w^{(k)} + \lambda_k p_k) = min_{\lambda>=0} f(w^{(k)} + \lambda p_k) $$

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

计算 $g_{k+1} = g()w^{(k+1)}$，若 $||g_{k+1}|| < \epsilon$ 则停止计算，得 $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_k^T B_k} {\delta_k^T B_k \delta_k}} $$
其中 $y_k = g_{k+1}-g_k, \delta_k = w^{(k+1)}-w^{(k)}$

置 $k=k+1$，转步骤 3。

逻辑回归

正则化

正则化是一个通用的算法和思想，任何会产生过拟合现象的算法都可以使用正则化来避免过拟合。在经验风险最小化的基础上（训练误差最小化），尽可能地采用简单模型，可以有效提高泛化预测精度。而正则化之所以有效是因为其降低了特征的权重，使得模型更加简单。

正则化一般采用 L1 范式或 L2 范式，其形式分别为 $\Phi(w) = ||x||_1$ 和 $\Phi(w) = ||x||_2$。

`L1` 正则化

L1 正则化也称为 LASSO 回归，其为模型增加了一个参数 w，而此参数 w 服从零均值拉普拉斯分布：
$$ f(w|\mu,b) = {\frac {1} {2b}} \exp{-{\frac {|w-\mu|} {b}}} $$

那么之后的似然函数如下：
$$\begin{equation}\begin{split}
L(w) &= P(y|w,x) P(w) \\
&= \Pi_{i=1}^N p(x_i)^{y_i} (1-p(x_i))^{1-y_i} \Pi_{j=1}^d {\frac {1} {2b}} \exp({-{\frac {|w_j|} {b}}})
\end{split}\nonumber\end{equation}$$

对该式子取 log 再取负可得目标函数：
$$ -\ln{L(w)} = - sum_i[y_i \ln{p(x_i)} + (1-y_i) \ln{(1-p(x_i))}] + {\frac {1} {2b^2}} sum_j |w_j| $$

等价于原始损失函数的后面再加上了 L1 正则项，因此 L1 的本质就是为模型增加模型参数服从零均值拉普拉斯分布的这一特点。

`L2` 正则化

L2 正则化也称 Ridge 回归，其本质是为模型增加了一个参数 w，而此参数服从零均值正态分布。
$$ f(w|\mu,)\sigma = {\frac {1} {\sqrt{2\pi} \sigma}} \exp{(- {\frac {(w-\mu)^2} {2 \sigma^2}})} $$

那么之后的似然函数如下：
$$\begin{equation}\begin{split}
L(w) &= P(y|w,x)P(w) \\
&= \Pi_{i=1}^N p(x_i)^{y_i} (1-p(x_i))^{1-y_i} \Pi_{j=1}^d {\frac {1} {\sqrt{2\pi}\sigma}} \exp{(- {\frac {w_j^2} {2\sigma^2}})} \\
&= \Pi_{i=1}^N p(x_i)^{y_i} (1-p(x_i))^{1-y_i} {\frac {1} {\sqrt{2\pi}\sigma}} \exp{(- {\frac {w^T w} {2\sigma^2}})}
\end{split}\nonumber\end{equation}$$

对上式子取 log 再取负可得到目标函数：
$$ - \log{L(w)} = - sum_i [y_i \log{p(x_i)} + (1 - y_i) \log{(1-p(x_i))}] + {\frac {1} {2 \sigma^2}} w^T w + const $$

上述公式等价于原始的 cross - entropy 之后再加上 L2 正则项，至此 L2 正则的本质也就是为模型增加模型参数服从零均值正态分布这一特点。

`L1` 正则与 `L2` 正则的区别

L1 正则化增加了所有权重 w 参数的绝对值之和，使得更多的 w 趋向于零，从而导致模型参数变得稀疏。而 L2 正则化则是增加了所有权重 w 参数的平方之和，使得参数 w 仅可能趋向于零但不为零，以此导致模型参数更加稠密，从而防止过拟合。

并行化

在逻辑回归的求解过程中，无论是改进的迭代尺度法还是牛顿法，其本质都是需要计算梯度的，因此逻辑回归的并行化主要是对目标函数梯度计算的并行化。

梯度下降法详解

在线学习

😭TODO

最大熵模型

原理

最大熵模型（maximum entropy model）是由最大熵原理推导而成。最大熵原理认为：学习概率模型时，在所有可能的概率分布中，熵最大的模型也就是最好的模型。通常使用约束条件来确定概率模型的集合，而最大熵原理也可以表示为在满足约束条件的模型集合中选取熵最大的模型。
假设离散随机变量 $X$ 的概率分布是 $P(X)$，则其熵为：
$$ H(P) = - sum_x P(x) logP(x) $$
熵需要满足 $0<=H(P)<=log|X|$，其中 $|X|$ 是 X 的取值个数，当且仅当 X 的分布是均匀分布是右边的等号才会成立。（X 服从均匀分布时，其熵最大）

概率模型集合可使用由欧氏空间中的单纯形表示，其中一个点表示一个模型，整个单纯形代表模型集合。单纯形中的直线表示约束条件，直线的交集对应于满足所有约束条件的模型集合。然而这样的模型会存在多个，最大熵原理则是在众多的模型中选择最优的模型。
单纯形是指在 n 维欧氏空间中的 n+1 个仿射无关的点的集合的凸包。

定义

最大熵原理是统计学习中的一般原理，将它应用到分类得到最大熵模型。假设分类模型是一个条件概率分布 $P(Y|X)$，其表示对于给定的输入 X，会以条件概率 $P(Y|X)$ 输出 Y，其中 $X,Y$ 分别表示输入和输出。

给定一个训练数据集 $T={(x_1, y_1), …, (x_N, y_N)}$，学习的目标是使用最大熵原理选择最好的分类模型。对于给定的训练数据集，可以确定联合分布 $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 表示训练样本容量。

首要模型需要考虑满足条件，可以使用特征函数（feature function） $f(x, y)$ 描述输入 $x$ 和输出 $y$ 之间的某一个事实，其定义为：
$$
f(x, y) =
\begin{cases}
1, & \text{x 与 y 满足某一条件} \\
0, & \text{否则}
\end{cases}
$$
上述定义为一个二值函数，当 x 和 y 满足某个事实时取值为 1，否则为 0。
特征函数 $f(x, y)$ 关于经验分布 $\widetilde{P}(X, Y)$ 的期望值用 $E_\widetilde{p} (f)$ 来表示：
$$ E_\widetilde{p} (f) = sum_{x,y} \widetilde{P}(x,y) f(x,y) $$
特征函数 $f(x, y)$ 关于模型 $P(Y|X)$ 与经验分布 $\widetilde{P}(X)$ 的期望值用 $E_\widetilde{p}(f)$ 来表示：
$$ E_p (f) = sum_{x,y} E_\widetilde{p}(x) P(y|x) f(x,y) $$
那么在训练数据集中获得足够多的条件，就可以假设两个期望值相等，即：
$$ E_p (f) = E_\widetilde{p}(f) $$
$$ sum_{x,y} \widetilde{P}(x) P(y|x) f(x,y) = sum_{x,y} \widetilde{P}(x,y) f(x,y) $$

假设满足所有约束条件的模型集合为 $\varsigma = {p \in P|E_p(f_i) = E_\widetilde{p}(f_i), i=1,2, …, n}$，定义在条件概率分布 $P(Y|X)$ 上的条件熵为：
$$ H(P) = - sum_{x,y} \widetilde{P}(x) P(y|x) logP(y|x) $$
则模型集合 $\varsigma$ 中条件熵 $H(P)$ 最大的模型称为最大熵模型，而公式中的对数为自然对数。

学习

最大熵模型的学习过程就是求解最大熵模型的过程，最大熵模型的学习可以形式化为最优化问题。

对于给定的训练数据集 $T = {(x_1, y_1), …, (x_N, y_N)}$ 以及特征函数 $f_i(x,y), i=1,2,…,N$，最大熵模型的学习等价于约束最优化问题：
$$ max_{P \in \varsigma} H(P) = - sum_{x,y} \widetilde{P}(x) P(y|x) logP(y|x) $$
$$ E_p(f_i) = E_\widetilde{p}(f_i), \quad i=1,2,…,n $$
$$ sum_y P(y|x) = 1 $$
按照求解最优化问题的习惯，将求最大值问题改写为等价的求最小值问题：
$$ min_{P \in \varsigma} -H(P) = sum_{x,y} \widetilde{P}(x) P(y|x) logP(y|x) $$
$$ s.t. \quad E_p(f_i) - E_\widetilde{p}(f_i) = 0, \quad i=1,2,…,n $$
$$ sum_y P(y|x) = 1 $$

至此可以将约束最优化的原始问题转换为无约束最优化的对偶问题，通过求解对偶问题来求解原始问题。

引入拉格朗日乘子 $w_0, w_1, …, w_n$。
定义拉格朗日函数 $L(P, w)$。
$$\begin{equation}\begin{split}
L(P, w) &= -H(P) + w_0(1-sum_yP(y|x)) + sum_{i=1}^n w_i (E_\widetilde{p}(f_i) - E_p(f_i)) \\
&= sum_{x,y} \widetilde{P}(x) P(y|x) logP(y|x) + w_0(1-sum_yP(y|x)) \\
&+ sum_{i=1}^n w_i (sum_{x,y} \widetilde{P}(x,y) f_i(x,y) - sum_{x,y} \widetilde{P}(x) P(y|x) f_i(x,y)) \\
\end{split}\nonumber\end{equation}$$

上述可得需要优化的原始问题是:
$$ min_{P \in \varsigma} max_w L(P, w) $$
那么对偶问题是：
$$ max_w min_{P \in \varsigma} L(P, w) $$

由于拉格朗日函数 $L(P, w)$ 是 P 的凸函数，因此原始问题的解等价于对偶问题的解。
求解对偶问题内部的极小化。
$min_{P \in \varsigma} L(P, w)$ 是 w 的函数，将其记作：
$$ \Psi(w) = min_{P \in \varsigma} L(P, w) = L(P_w, w) $$

$\Psi(w)$ 是对偶函数，同时将其记作：
$$ P_w = arg min_{P \in \varsigma} L(P, w) = P_w(y|x) $$

之后求 $L(P, w)$ 对 $P(y|x)$ 的偏导数。
$$\begin{equation}\begin{split}
{\frac {\partial{L(P, w)}} {\partial{P(y|x)}}} &= sum_{x,y} \widetilde{P}(x)(logP(y|x)+1) - sum_y w_0 - sum_{x,y}(\widetilde{P}(x) sum_{i=1}^n w_i f_i(x,y)) \\
&= sum_{x,y} \widetilde{P}(x)(logP(y|x)+1-w_0-sum_{i=1}^n w_i f_i(x,y))
\end{split}\nonumber\end{equation}$$

在令偏导数等于 0，$\widetilde{P}(x)>0$ 的情况下，解得：
$$\begin{equation}\begin{split}
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)}}
\end{split}\nonumber\end{equation}$$

由于 $sum_yP(y|x)=1$，可得：
$$ P_w(y|x) = {\frac {1} {Z_w(x)}} exp(sum_{i=1}^n w_i f_i(x,y)) $$
而这其中 $Z_w(x) = sum_y exp(sum_{i=1}^n w_i f_i(x,y))$

$Z_w(x)$ 被称为规范化因子，$f_i(x,y)$ 是特征函数，$w_i$ 是特征的权值，模型 $P_w=P_w(y|x)$ 就是最大熵模型，而 w 是最大熵模型的参数向量。
求解对偶问题外部的极大化。
$max_w \Psi(w)$ 将其解记作 $w^*$，即：
$$ w^* = arg max_w \Psi(w) $$

应用最优化算法求对偶问题 $\Psi(w)$ 的极大化得到 $w^*$，表示 $P^* \in \varsigma$。此时这里的 $p^*=P_{w^*}=P_{w^*}(y|x)$ 也就是学习到的最优模型（最大熵模型）。即可得到最大熵模型的学习就是对偶函数 $\Psi(w)$ 的极大化。

总结

对于文章中不理解的特有名词，还是需要自己去了解查询。
如果你在阅读途中遇到了看不懂、不了解等因素，可以先放一放，阅读完毕后你就会明白之前是什么含义。

引用

梯度下降法详解
 Logistic回归

个人备注

此博客内容均为作者学习《统计学习方法》所做笔记，侵删！
若转作其他用途，请注明来源！

基础