【机器学习】Logistic Regression 的前世今生(理论篇)
Logistic Regression可以说是机器学习的入门算法。不过,你真的有把握能够把LR从头到脚讲一遍吗?你会现场建模,数学推导?你知道它的正则化的作用?你能讲清楚它跟MaxEnt最大熵模型的关系吗?ok,你说这些你都会?那你知道并它的行化怎么做吗?有几种并行化的方式呢?啥?!你说你还会?大神,请受我一拜!
Logistic Regression 的前世今生(理论篇)
本博客仅为作者记录笔记之用,不免有很多细节不对之处。
还望各位看官能够见谅,欢迎批评指正。
博客虽水,然亦博主之苦劳也。
如需转载,请附上本文链接,不甚感激!
http://blog.csdn.net/cyh_24/article/details/50359055
写这篇博客的动力是源于看到了下面这篇微博:

我在看到这篇微博的时候大为触动,因为,如果是rickjin来面试我,我想我会死的很惨,因为他问的问题我基本都回答不上来。所以,痛定思痛,我决定今后对一些算法的理解不能只是停留在表面,而应该至少往前推一步,尝试看得更远一些。
对于学习机器学习的人来说,Logistic Regression可以说是一个入门的算法,算法本身不复杂,不过也正是因为这个原因,很多人往往忽略了这个算法的一些内在精髓。
这篇博客里,我打算就rickjin问的一些问题,进行总结:
1. LR原理
2. LR的求解数学推导
3. LR的正则化
4. 为什么LR能比线性回归好?
5. LR与MaxEnt的关系
6. 并行化的LR
逻辑回归模型
虽然逻辑回归 姓 回归,不过其实它的真实身份是二分类器。介绍完了姓,我们来介绍一下它的名字,逻辑斯蒂。这个名字来源于逻辑斯蒂分布:
逻辑斯蒂分布
设X是连续随机变量,X服从逻辑斯蒂分布是指X具有下列的分布函数和密度函数:
有没有发现 F(x) <script type="math/tex" id="MathJax-Element-5">F(x)</script>是啥?有图你就知道真相了:

有没有发现右边很熟悉?没错,就是sigmoid 曲线,只不过,这个曲线是以点( μ <script type="math/tex" id="MathJax-Element-6">\mu</script>, 12 <script type="math/tex" id="MathJax-Element-7">\dfrac{1}{2}</script>) 为中心对称。从图中可以看出,曲线在中心附近增长速度较快,而形状参数 γ <script type="math/tex" id="MathJax-Element-8">\gamma</script> 值越小,曲线在中心附近增长越快,请自行脑补一下。
二项逻辑回归模型
之前说到,逻辑回归是一种二分类模型,由条件概率分布 P(Y|X) <script type="math/tex" id="MathJax-Element-9">P(Y|X)</script> 表示,形式就是参数化的逻辑斯蒂分布。这里的自变量 X <script type="math/tex" id="MathJax-Element-10">X</script>取值为实数,而因变量
也就是说,输出 Y=1 <script type="math/tex" id="MathJax-Element-19">Y=1</script>的对数几率是由输入 x <script type="math/tex" id="MathJax-Element-20">x</script>的线性函数表示的模型,这就是 逻辑回归模型。当
w⋅x <script type="math/tex" id="MathJax-Element-21">w \cdot x</script>的值越接近正无穷, P(Y=1|x) <script type="math/tex" id="MathJax-Element-22">P(Y=1|x)</script> 概率值也就越接近1.
模型的数学形式确定后,剩下就是如何去求解模型中的参数。在统计学中,常常使用极大似然估计法来求解,即找到一组参数,使得在这组参数下,我们的数据的似然度(概率)最大。
设:
似然函数:
对数似然函数:
现在要求 w <script type="math/tex" id="MathJax-Element-28">w</script> 使得
在机器学习领域,我们更经常遇到的是损失函数的概念,其衡量的是模型预测错误的程度。常用的损失函数有0-1损失,log损失,hinge损失等。通常是最小化损失函数,这里为啥求极大似然估计?
实际上,对数似然损失在单个数据点上的定义为:
如果取整个数据集上的平均对数似然损失,我们恰好可以得到:
即在逻辑回归模型中,我们最大化似然函数和最小化对数似然损失函数实际上是等价的。
接下来就是对 L(w) <script type="math/tex" id="MathJax-Element-32">L(w)</script>求极大值(也可认为是求 J(w) <script type="math/tex" id="MathJax-Element-33">J(w)</script>的最小值),得到 w <script type="math/tex" id="MathJax-Element-34">w</script>的估计值。逻辑回归学习中通常采用的方法是梯度下降法 和 牛顿法。
[先跑个题],讲到求极值的方法,突然想到有几个可视化的gif图,能够很直观地体现各种算法的优劣,好东西当然要分享了。
Imgur 网友通过可视化方法,对比了SGD, momentum, Nesterov, AdaGrad, AdaDelta,
RMSProp等优化算法在Long Valley, Beale’s Function及Saddle Point情况下的性质。
Long Valley: 
Beale’s Function:

Saddle Point:

以后会专门写一篇来讲求极值的方法,这是题外话了,我们还是继续回归逻辑吧,哈哈。
下面介绍使用梯度下降法来求解逻辑回归问题。
使用梯度下降法(Gradient Descent)求解逻辑回归
算法(梯度下降法求解逻辑回归)
输入:目标函数:
输出: J(w) <script type="math/tex" id="MathJax-Element-38">J(w)</script> 的极小值点 w∗ <script type="math/tex" id="MathJax-Element-39">w^*</script>
过程:
(1) 取初始值 w0∈Rn <script type="math/tex" id="MathJax-Element-40">w_0\in \bf R^n</script>, 令 k=0 <script type="math/tex" id="MathJax-Element-41">k=0</script>
(2) 计算 J(wk) <script type="math/tex" id="MathJax-Element-42">J(w_k)</script>
(3) 计算梯度 gk=g(wk)=∇J(w) <script type="math/tex" id="MathJax-Element-45">g_k=g(w_k)=\nabla J(w)</script>
若 ||gk||<ϵ <script type="math/tex" id="MathJax-Element-48">||g_k||<\epsilon</script> ,停止迭代,令
否则,令 pk=−g(wk) <script type="math/tex" id="MathJax-Element-50">p_k=-g(w_k)</script>,求 λk <script type="math/tex" id="MathJax-Element-51">\lambda_k</script>,使得
(4) 令 wk+1=wk+λkpk <script type="math/tex" id="MathJax-Element-53">w_{k+1}=w_k+\lambda_kp_k</script>,计算 J(wk+1) <script type="math/tex" id="MathJax-Element-54">J(w_{k+1})</script>
当 ||J(wk+1)−J(wk)||<ϵ <script type="math/tex" id="MathJax-Element-55">||J(w_{k+1})-J(w_k)||<\epsilon</script> 或 ||wk+1−wk||<ϵ <script type="math/tex" id="MathJax-Element-56">||w_{k+1}-w_k||<\epsilon</script>,停止迭代,令
(5) 否则,令 k=k+1 <script type="math/tex" id="MathJax-Element-58">k=k+1</script>,转(3).
逻辑回归的正则化
当模型的参数过多时,很容易遇到过拟合的问题。而正则化是结构风险最小化的一种实现方式,通过在经验风险上加一个正则化项,来惩罚过大的参数来防止过拟合。
正则化是符合奥卡姆剃刀(Occam’s razor)原理的:在所有可能选择的模型中,能够很好地解释已知数据并且十分简单的才是最好的模型。
我们来看一下underfitting,fitting跟overfitting的情况:

显然,最右这张图overfitting了,原因可能是能影响结果的参数太多了。典型的做法在优化目标中加入正则项,通过惩罚过大的参数来防止过拟合:
p=1或者2,表示 L1 <script type="math/tex" id="MathJax-Element-60">L_1</script> 范数和 L2 <script type="math/tex" id="MathJax-Element-61">L_2</script>范数,这两者还是有不同效果的。
L1 <script type="math/tex" id="MathJax-Element-62">L_1</script>范数:是指向量中各个元素绝对值之和,也有个美称叫“稀疏规则算子”(Lasso regularization)。那么,参数稀疏 有什么好处呢?
一个关键原因在于它能实现 特征的自动选择。一般来说,大部分特征 xi <script type="math/tex" id="MathJax-Element-63">x_i</script>和输出 yi <script type="math/tex" id="MathJax-Element-64">y_i</script> 之间并没有多大关系。在最小化目标函数的时候考虑到这些额外的特征 xi <script type="math/tex" id="MathJax-Element-65">x_i</script>,虽然可以获得更小的训练误差,但在预测新的样本时,这些没用的信息反而会干扰了对正确 yi <script type="math/tex" id="MathJax-Element-66">y_i</script> 的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命,它会学习地去掉这些没有信息的特征,也就是把这些特征对应的权重置为0。
L2 <script type="math/tex" id="MathJax-Element-67">L_2</script>范数:它有两个美称,在回归里面,有人把有它的回归叫“岭回归”(Ridge Regression),有人也叫它“权值衰减”(weight decay)。
它的强大之处就是它能 解决过拟合 问题。我们让 L2 <script type="math/tex" id="MathJax-Element-68">L2</script> 范数的规则项 ||w||2 <script type="math/tex" id="MathJax-Element-69">||w||_2</script> 最小,可以使得 w <script type="math/tex" id="MathJax-Element-70">w</script> 的每个元素都很小,都接近于0,但与
为了更直观看出两者的区别,我再放一张图:

为了简单,上图只考虑了 w <script type="math/tex" id="MathJax-Element-72">w</script>为二维
一句话总结就是:
L1 <script type="math/tex" id="MathJax-Element-80">L_1</script> 会趋向于产生少量的特征,而其他的特征都是0,而 L2 <script type="math/tex" id="MathJax-Element-81">L_2</script> 会选择更多的特征,这些特征都会接近于0。为什么逻辑回归比线性回归要好?
虽然逻辑回归能够用于分类,不过其本质还是线性回归。它仅在线性回归的基础上,在特征到结果的映射中加入了一层sigmoid函数(非线性)映射,即先把特征线性求和,然后使用sigmoid函数来预测。然而,正是这个简单的逻辑函数,使得逻辑回归模型成为了机器学习领域一颗耀眼的明星。
下面我们来谈谈逻辑回归与线性回归的异同点吧。
假设随Tumor Size变化,预测病人的肿瘤是恶性(malignant)还是良性(benign)的情况。给出8个数据如下(阈值为0.5):
![此处输入图片的描述][10]
图1.a中,粉色线是预测模型,可以看出,模型能够完全把结果预测对了,但是图1.b中蓝色线却预测的很差。
这主要是由于线性回归在整个实数域内敏感度一致,而分类范围,需要在[0,1]之内。而逻辑回归就是一种减小预测范围,将预测值限定为[0,1]间的一种回归模型,其回归方程与回归曲线如下图所示。逻辑曲线在z=0时,十分敏感,在z>>0或z<<0处,都不敏感,将预测值限定为(0,1)。
逻辑回归与最大熵模型MaxEnt的关系?
逻辑回归跟最大熵模型到底有啥区别呢?
简单粗暴 的回答是:逻辑回归跟最大熵模型没有本质区别。逻辑回归是最大熵对应类别为二类时的特殊情况,也就是当逻辑回归类别扩展到多类别时,就是最大熵模型。
下面来详细地介绍一下:
在进行下面推导之前,先上几个数学符号定义:
- π(x)u <script type="math/tex" id="MathJax-Element-82">\pi(x)_u</script> 表示,输入时 x <script type="math/tex" id="MathJax-Element-83">x</script>, 输出的
y=u <script type="math/tex" id="MathJax-Element-84">y=u</script>的概率;- A(u,v) <script type="math/tex" id="MathJax-Element-85">A(u,v)</script> 是一个指示函数,若 u=v <script type="math/tex" id="MathJax-Element-86">u=v</script>,则 A(u,v)=1 <script type="math/tex" id="MathJax-Element-87">A(u,v)=1</script>;否则 A(u,v)=0 <script type="math/tex" id="MathJax-Element-88">A(u,v)=0</script>
- 我们的目标,就是从训练数据中,学习得到一个模型,使得 π(x)u <script type="math/tex" id="MathJax-Element-89">\pi(x)_u</script> 最大化,也就是输入 x <script type="math/tex" id="MathJax-Element-90">x</script>,预测结果是
y <script type="math/tex" id="MathJax-Element-91">y</script> 的概率最大,也就是使得 π(x)y <script type="math/tex" id="MathJax-Element-92">\pi(x)_{y}</script> 最大;回顾逻辑回归
标准的逻辑回归是二类模型,有:
P(Y=1|x)=π(x)1=ew⋅x1+ew⋅x<script type="math/tex; mode=display" id="MathJax-Element-93"> P(Y=1|x) = \pi(x)_1 =\dfrac{e^{w \cdot x}}{1+e^{w \cdot x}}</script>P(Y=0|x)=π(x)0=1−π(x)1<script type="math/tex; mode=display" id="MathJax-Element-94"> P(Y=0|x) = \pi(x)_0 = 1-\pi(x)_1 </script>我们用一个更加泛化的形式来表达 π() <script type="math/tex" id="MathJax-Element-95">\pi()</script>,(只是在这里,k=2):
π(x)v=ewv⋅x∑ku=1ewu⋅x<script type="math/tex; mode=display" id="MathJax-Element-96">\pi(x)_v=\dfrac{e^{w_v \cdot x}}{\sum_{u=1}^k e^{w_u \cdot x}}</script>回到我们的目标:令 π(xi)yi <script type="math/tex" id="MathJax-Element-97">\pi(x_i)_{y_i}</script> 最大,可以用极大似然估计的方法来求解。
L(w)=∏i=1nπ(xi)yi<script type="math/tex; mode=display" id="MathJax-Element-98">L(w)=\prod_{i=1}^n \pi(x_i)y_i</script>
lnL(w)=∑i=1nln(π(xi)yi)<script type="math/tex; mode=display" id="MathJax-Element-99">lnL(w)=\sum_{i=1}^n ln(\pi(x_i)y_i)</script>对 lnL(w) <script type="math/tex" id="MathJax-Element-100">lnL(w)</script>求偏导,得到:
δδwu,jlnL(w)=...=∑i=1,yi=unxij−∑i=1nxijπ(xi)u<script type="math/tex; mode=display" id="MathJax-Element-101">\frac{\delta}{\delta w_{u,j}}lnL(w)=...=\sum_{i=1,\;y_i=u}^nx_{ij}-\sum_{i=1}^nx_{ij}\pi(x_i)_u</script>令偏导等于0,可以得到:
∑i=1nxijπ(xi)u=∑i=1,yi=unxij,(forallu,j)<script type="math/tex; mode=display" id="MathJax-Element-102">\sum_{i=1}^nx_{ij}\pi(x_i)_u=\sum_{i=1,\;y_i=u}^nx_{ij}, (for\;all\; u,j)</script>使用 A(u,yi) <script type="math/tex" id="MathJax-Element-103">A(u,y_i)</script> 这个函数,我们可以重写等式:
∑i=1nxijπ(xi)u=∑i=1nA(u,yi)xij,(forallu,j)<script type="math/tex; mode=display" id="MathJax-Element-104">\sum_{i=1}^nx_{ij}\pi(x_i)_u=\sum_{i=1}^n A(u,y_i)x_{ij}, (for\;all\; u,j)</script>回顾最大熵模型
想要证明逻辑回归跟最大熵模型是等价的,那么,只要能够证明它们的 π() <script type="math/tex" id="MathJax-Element-105">\pi()</script> 是相同,结论自然就出来了。现在,我们不知道最大熵模型的 π() <script type="math/tex" id="MathJax-Element-106">\pi()</script>,但是我们知道下面的一些性质:
π(x)v≥0always<script type="math/tex; mode=display" id="MathJax-Element-107">\pi(x)_v\geq0 \quad always</script>
∑v=1kπ(x)v=1always<script type="math/tex; mode=display" id="MathJax-Element-108">\sum_{v=1}^k\pi(x)_v = 1 \quad always</script>
∑i=1nxijπ(xi)u=∑i=1nA(u,yi)xij,(forallu,j)<script type="math/tex; mode=display" id="MathJax-Element-109">\sum_{i=1}^nx_{ij}\pi(x_i)_u=\sum_{i=1}^n A(u,y_i)x_{ij}, (for\;all\; u,j)</script>利用信息论的只是,我们可以得到 π() <script type="math/tex" id="MathJax-Element-110">\pi()</script> 的熵,定义如下:
−∑v=1k∑i=1nπ(xi)vlog[π(xi)v]<script type="math/tex; mode=display" id="MathJax-Element-111">-\sum_{v=1}^k\sum_{i=1}^n\pi(x_i)_vlog[\pi(x_i)_v]</script>现在,我们有了目标: ∑π() <script type="math/tex" id="MathJax-Element-112">\sum\pi()</script> 最大,也有了上面的4个约束条件。求解约束最优化问题,可以通过拉格朗日乘子,将约束最优化问题转换为无约束最优化的对偶问题。我们的拉格朗日式子可以写成如下:
L=∑j=1m∑v=1kwv,j(∑i=1nπ(xi)vxij−A(v,yi)xij)<script type="math/tex; mode=display" id="MathJax-Element-113">L=\sum_{j=1}^m\sum_{v=1}^kw_{v,j}(\sum_{i=1}^n\pi(x_i)_vx_{ij}-A(v,y_i)x_{ij})</script>
+∑v=1k∑i=1nβi(π(xi)v−1)<script type="math/tex; mode=display" id="MathJax-Element-114">+\sum_{v=1}^k\sum_{i=1}^n\beta_i(\pi(x_i)_v-1)</script>
−∑v=1k∑i=1nπ(xi)vlog[π(xi)v]<script type="math/tex; mode=display" id="MathJax-Element-115">-\sum_{v=1}^k\sum_{i=1}^n \pi(x_i)_vlog[\pi(x_i)_v]</script>对 L <script type="math/tex" id="MathJax-Element-116">L</script>求偏导,得到:
<script type="math/tex; mode=display" id="MathJax-Element-117">\frac{\delta}{\delta \pi(x_i)_u}L=w_u \cdot x_i+\beta_i-log[\pi(x_i)_u]-1</script>δδπ(xi)uL=wu⋅xi+βi−log[π(xi)u]−1 令偏导=0,得到: wu⋅xi+βi−log[π(xi)u]−1=0 <script type="math/tex" id="MathJax-Element-118">w_u \cdot x_i+\beta_i-log[\pi(x_i)_u]-1=0</script>,从而得到:
π(xi)u=ewu⋅xi+βi−1<script type="math/tex; mode=display" id="MathJax-Element-119">\pi(x_i)_u=e^{w_u \cdot x_i+\beta_i-1}</script>因为有约束条件: ∑kv=1π(x)v=1 <script type="math/tex" id="MathJax-Element-120">\sum_{v=1}^k \pi(x)_v = 1</script>,所以,
∑v=1kewv⋅xi+βi−1=1<script type="math/tex; mode=display" id="MathJax-Element-121">\sum_{v=1}^ke^{w_v \cdot x_i+\beta_i-1}=1</script>因此,可以得到
eβ=1/∑v=1kewv⋅xi−1<script type="math/tex; mode=display" id="MathJax-Element-122">e^\beta=1/\sum_{v=1}^ke^{w_v \cdot x_i-1}</script>把 eβ <script type="math/tex" id="MathJax-Element-123">e^\beta</script> 代入 π() <script type="math/tex" id="MathJax-Element-124">\pi()</script>,并且简化一下式子:
π(x)u=ewu⋅x∑kv=1ewv⋅x<script type="math/tex; mode=display" id="MathJax-Element-125">\pi(x)_u=\frac{e^{w_u\cdot x}}{\sum_{v=1}^k e^{w_v \cdot x}}</script>有没有发现这就是逻辑回归中,提到的那个泛化的式子,这就证明了逻辑回归是最大熵模型的一个特殊例子(k=2)!
到此,逻辑回归与最大熵模型的关系就解释完毕了,总结一下:
逻辑回归跟最大熵模型没有本质区别。逻辑回归是最大熵对应类别为二类时的特殊情况
指数簇分布的最大熵等价于其指数形式的最大似然。
二项式分布的最大熵解等价于二项式指数形式(sigmoid)的最大似然;
多项式分布的最大熵等价于多项式分布指数形式(softmax)的最大似然。假设分布求解最大熵,引入拉格朗日函数,求偏导数等于0,直接求出的就是sigmoid函数形式。还有很多指数簇分布都有对应的最大似然解。而单个指数簇分布往往表达能力有限,这就需要引入了多个指数簇分布的混合模型,比如高斯混合,从而引出EM算法。
Logistic Regression的理论部分讲的差不多了,下一篇文章将介绍Logistic Regression的并行化 工程问题。敬请期待…
Please feel free to contact me if you have any questions.
参考文献
[1]. 李航,《统计学习方法》 [2]. John Mount. *"The equivalence of logistic regression and maximum entropy models"* [3]. http://tech.meituan.com/intro_to_logistic_regression.html [4]. http://blog.csdn.net/zouxy09/article/details/24971995 [5]. http://www.tuicool.com/articles/auQFju
更多推荐



所有评论(0)