好早之前就发现逻辑斯蒂回归好像和朴素贝叶斯里面的后验概率公式还有最大似然、信息熵、交叉熵、伯努利分布、回归分析、几率(odds)等等有着千丝万缕CZFZ(错综复杂)、PSML(扑朔迷离)的关系。一直感觉逻辑斯蒂分布好像在很多地方都比较受宠并且有一些优良的性质经常被提及,不过又说不太清楚到底是怎么回事。
于是,我终于,去翻了教材讲义知乎CSDN之后,把这些东西给理清楚了!
这是一篇非非非非常长的文章
也可以戳下面链接看分节的版本哟~
细讲逻辑斯蒂回归与朴素贝叶斯、最大熵原理的爱恨交织(一)
细讲逻辑斯蒂回归与朴素贝叶斯、最大熵原理的爱恨交织(二)
细讲逻辑斯蒂回归与朴素贝叶斯、最大熵原理的爱恨交织(三)
细讲逻辑斯蒂回归与朴素贝叶斯、最大熵原理的爱恨交织(四)
细讲逻辑斯蒂回归与朴素贝叶斯、最大熵原理的爱恨交织(五)
细讲逻辑斯蒂回归与朴素贝叶斯、最大熵原理的爱恨交织(六)
长文预警 ⇓\ \Downarrow⇓,ready?
第一节 —— 另辟蹊径从生态学入手
种群生态学考虑单一物种的生存模式和状态。其中,关于种群个体数量的变化,有所谓的马尔萨斯模型和逻辑斯蒂模型。
马尔萨斯模型
种群在某一状态下增长速率与种群个体数成正比。种群越大,增速越快。 这比较好理解,例如一只羊一年生一只,那么三只羊一年就能生三只。种群个体数从一变成三增了三倍,种群数量的增速也变为了原来的三倍。 把这个正比关系写成微分方程:y(t) 表示种群大小,它是时间 t 的函数。r 是比值系数:
dy(t)dt=r⋅y(t)\frac{dy(t)}{dt} = r·y(t)dtdy(t)=r⋅y(t)
解这个微分方程:
1ydy=rdt\frac{1}{y} dy = rdty1dy=rdt
⇒∫1ydy=∫rdt\Rightarrow\int\frac{1}{y}dy = \int rdt⇒∫y1dy=∫rdt
⇒logy=rt\Rightarrow logy = rt⇒logy=rt
⇒y=ert\Rightarrow y = e^{rt}⇒y=ert
原来这就是我们熟悉的指数函数。
这个模型的不足在于,它只考虑了“生”的过程,没考虑“存”的实际情况。即便“生”的速率与种群大小成正比,但是能否存活还要受环境因素的制约。
逻辑斯蒂模型
种群大小增长到一定程度后,由于种内个体之间争夺有限的资源,存活率就会下降,导致种群个体数量的增长率下降。于是,有人对上述模型进行了改进,就有了(生态学中的)逻辑斯蒂模型。
这个模型依旧是用一个微分方程表示种群个体数量与增长速率的关系:dy(t)dt=ry(t)×[1−y(t)K]\frac{dy(t)}{dt} = ry(t)\times[1-\frac{y(t)}{K}]dtdy(t)=ry(t)×[1−Ky(t)]
K可以解读为环境最大容纳量(capacity),r依旧是比值系数。解这个微分方程:
dy=rK⋅y⋅(K−y)dtdy = \frac{r}{K}·y·(K-y)dtdy=Kr⋅y⋅(K−y)dt
1Ky−y2dy=rKdt\frac{1}{Ky-y^2} dy = \frac{r}{K} dtKy−y21dy=Krdt
∫1Ky−y2dy=∫rKdt\int\frac{1}{Ky-y^2} dy = \int\frac{r}{K} dt∫Ky−y21dy=∫Krdt
logy−log(K−y)K=rK⋅t(0<y<K)\frac{logy-log(K-y)}{K} = \frac{r}{K}·t \ \ \ \ (0<y<K)Klogy−log(K−y)=Kr⋅t(0<y<K)
log(yK−y)=rtlog(\frac{y}{K-y}) = rtlog(K−yy)=rt
yK−y=ert\frac{y}{K-y} = e^{rt}K−yy=ert
y=Kert1+ert=K1+e−rty = \frac{Ke^{rt}}{1+e^{rt}} = \color{red}\frac{K}{1+e^{-rt}}y=1+ertKert=1+e−rtK
最后这个红色的解,是不是很熟悉???是不是很像炼丹师抬头不见低头见的sigmoid?!
我们对y求导:
y′=−K(−r)ert(1+e−rt)2y' = \frac{-K(-r)e^{rt}}{(1+e^{-rt})^2}y′=(1+e−rt)2−K(−r)ert
=Kr⋅11+e−rt⋅e−rt1+e−rt\quad= Kr·\frac{1}{1+e^{-rt}}·\frac{e^{-rt}}{1+e^{-rt}}=Kr⋅1+e−rt1⋅1+e−rte−rt
=Kr⋅11+e−rt⋅(1−11+e−rt)\quad= Kr·\frac{1}{1+e^{-rt}}·(1-\frac{1}{1+e^{-rt}})=Kr⋅1+e−rt1⋅(1−1+e−rt1)
=ry(1−yK)⇐\quad = ry(1-\frac{y}{K}) \quad \Leftarrow=ry(1−Ky)⇐ 符合最一开始的微分方程
忽略掉那些系数,可以概括为,对于满足逻辑斯蒂模型的函数,它的导数等于 (它自己) ×\times× (1 - 它自己)
特别地,当K = r = 1时,y=11+e−t=σ(t)y = \frac{1}{1+e^{-t}} \color{red}= \sigma(t)y=1+e−t1=σ(t) sigmoid成功现形!
y′=(11+e−t)(1−11+e−t)=y⋅(1−y)y' = (\frac{1}{1+e^{-t}})(1-\frac{1}{1+e^{-t}}) = y·(1-y)y′=(1+e−t1)(1−1+e−t1)=y⋅(1−y)
⇕\color{red}\Updownarrow⇕
σ′(t)=σ(t)[1−σ(t)]\color{red}\sigma'(t) = \sigma(t)[1- \sigma(t)]σ′(t)=σ(t)[1−σ(t)]
第二节 —— 统计回归分析中的逻辑斯蒂
逻辑斯蒂分布
设X是随机变量。逻辑分布指满足如下累计分布函数和概率密度函数的分布:
F(x)=P(X≤x)=11+e−(x−μ)sF(x) = P(X \leq x) = \frac{1}{1+e^{ \frac{-(x- \mu )}{s}}}F(x)=P(X≤x)=1+es−(x−μ)1
f(x)=F′(x)=e−(x−μ)ss(1+e−(x−μ)s)2f(x) = F'(x) = \frac{e^{ \frac{-(x- \mu )}{s}}}{s(1+e^{ \frac{-(x- \mu )}{s}})^2}f(x)=F′(x)=s(1+es−(x−μ))2es−(x−μ)
μ\muμ:位置参数,决定函数图像沿x轴方向的位移
sss:形状参数,决定函数图像的高矮胖瘦
大家可以用几何画板画一下μ\muμ和sss取不同值时的图像,直观的理解一下这两个参数的作用。
F(x)F(x)F(x)是以点 (μ,12)(\mu,\frac{1}{2})(μ,21) 中心对称的曲线。它越靠近中心增长越快。sss越小,在中心附近的增长越快。
特别地,当 μ\muμ=0, sss=1 时,F(x)=11+e−x=σ(x)F(x) = \frac{1}{1+e^{-x}} \color{red}= \sigma(x)F(x)=1+e−x1=σ(x)
逻辑斯蒂分布有和广泛的而应用。它最早来源于生长曲线的需要,现在还用于经济(例如描述一个产品在广告上投入与最后销售额的关系)、人口统计等领域。
逻辑斯蒂回归
对一个二元分类问题建模。
假设一个工厂生产的产品:达标/不达标 ~Bernoulli(p)Bernoulli(p)Bernoulli(p), p是产品达标的概率。
其中这个p受工厂其他各项指标的影响,比如流水线个数,员工人数,已投入使用时长,当日温度等等。假如我们就把举例的这四个作为特征,也就是说每一条数据(代表一个工厂)的特征向量有四维。
xi⃗={xi1xi2xi3xi4}\vec{x_i} = \left\{ \begin{matrix} x_{i1}\\x_{i2}\\x_{i3}\\x_{i4} \end{matrix} \right\}xi=⎩⎪⎪⎨⎪⎪⎧xi1xi2xi3xi4⎭⎪⎪⎬⎪⎪⎫
角标的含义:xijx_{ij}xij代表第 i 条数据的第 j 维。整个数据集的sample总数是N(i = 1, 2, …, N)
逻辑斯蒂回归的dataset应该是这个亚子的:
其中,PiP_iPi的计算方法就是从这个工厂的产品中抽出n个然后检测出当中有r个达标,用 rn\frac{r}{n}nr 作为该工厂产品Bernoulli分布的 p . 刚才我们讲p受工厂的四个特征影响,那么我们的目标就是让p用 x⃗\vec{x}x 来表示。
Goal: Regress PiP_iPi on xi⃗\vec{x_i}xi
第一个当然想到的是直接把 PiP_iPi 当做线性回归里面的 “y“
⇒Model:Pi=β0+β1xi1+...+β4xi4+ϵi\Rightarrow Model: P_i=\beta_0 + \beta_1x_{i1} + ... + \beta_4x_{i4} + \epsilon_i⇒Model:Pi=β0+β1xi1+...+β4xi4+ϵi
不过这个不太行,因为 0≤Pi≤10\leq P_i \leq10≤Pi≤1,而 xi⃗Tβ⃗\vec {x_i}^T \vec{\beta}xiTβ 可能落在这个区间外。这样用 xi⃗Tβ⃗\vec {x_i}^T \vec{\beta}xiTβ 表示 PiP_iPi 就没有意义。
Idea: Do transformation on PiP_iPi(统计学中 logistic regression 的精髓呀呀呀!)
⇒Model:log(Pi1−Pi)=β0+β1xi1+...+β4xi4+ϵi\Rightarrow Model: log(\frac{P_i}{1-P_i})=\beta_0 + \beta_1x_{i1} + ... + \beta_4x_{i4} + \epsilon_i⇒Model:log(1−PiPi)=β0+β1xi1+...+β4xi4+ϵi
⇔Model:log(Pi1−Pi)=xi⃗Tβ⃗+ϵ⃗\Leftrightarrow Model: log(\frac{P_i}{1-P_i})=\vec {x_i}^T \vec{\beta} + \vec \epsilon⇔Model:log(1−PiPi)=xiTβ+ϵ
⇔Fittedmodel:log(Pi^1−Pi^)=xi⃗Tβ⃗^\Leftrightarrow Fitted \ model: log(\frac{\hat{P_i}}{1-\hat{P_i}})=\vec {x_i}^T \hat{\vec{\beta}}⇔Fittedmodel:log(1−Pi^Pi^)=xiTβ^
有 ^ 符号的代表是根据样本数据算出来的参数estimates。对上式做一点变形:
Fittedmodel:Pi^=exp(xi⃗Tβ⃗)1+exp(xi⃗Tβ⃗)=11+exp(−xi⃗Tβ⃗)=σ(xi⃗Tβ⃗)Fitted \ model: \hat{P_i} = \frac{exp(\vec {x_i}^T \vec{\beta})}{1+exp(\vec {x_i}^T \vec{\beta})} = \frac{1}{1+exp(- \ \vec {x_i}^T \vec{\beta})} \color{red}= \sigma(\vec {x_i}^T \vec{\beta})Fittedmodel:Pi^=1+exp(xiTβ)exp(xiTβ)=1+exp(−xiTβ)1=σ(xiTβ)
具体在计算的时候,把上面那个表格里每一行的 PiP_iPi 都算一个相应的
log(Pi1−Pi)log(\frac{P_i}{1-P_i})log(1−PiPi),并把这个当成线性回归里面的 “y”,剩下的回归就都清楚啦~
下面简单说一下为什么要这么做 transformation。
在统计学中一个事件A的几率:odds = P(A)1−P(A)\frac{P(A)}{1-P(A)}1−P(A)P(A)
对数几率 = log(P(A)1−P(A))log(\frac{P(A)}{1-P(A)})log(1−P(A)P(A))
对数几率这个函数叫做 logitlogitlogit 函数:logit(y)=y1−ylogit(y) = \frac{y}{1-y}logit(y)=1−yy
回到刚才的例子中,那么A =“达标”。Pi=P(A∣xi⃗)P_i= P(A \ |\ \vec{x_i})Pi=P(A∣xi)
oddsofAatxi⃗=P(A∣xi⃗)1−P(A∣xi⃗)=Pi1−Piodds \ of \ A \ at \ \vec{x_i} = \frac{P(A \ |\ \vec{x_i})}{1-P(A \ |\ \vec{x_i})} = \frac{P_i}{1-P_i}oddsofAatxi=1−P(A∣xi)P(A∣xi)=1−PiPi
logoddsofAatxi⃗=log(Pi1−Pi)=xi⃗Tβ⃗+ϵ⃗log\ odds\ of\ A\ at\ \vec{x_i} = log\Big(\frac{P_i}{1-P_i}\Big) = \vec {x_i}^T \vec{\beta} + \vec \epsilonlogoddsofAatxi=log(1−PiPi)=xiTβ+ϵ
于是,逻辑斯蒂回归用一句话概括就是:用 x⃗\vec{x}x 的线性函数去拟合了二元事件的对数几率。因此,逻辑斯蒂回归也叫作 “对数几率回归”。
广义线性
一般线性:y=β0+β1xi1+β2xi2+...+ϵi=xi⃗Tβ⃗+ϵ⃗\color{#FF7256}y\color {black} = \beta_0 + \beta_1x_{i1} + \beta_2x_{i2} +... + \epsilon_i = \vec {x_i}^T \vec{\beta} + \vec \epsilony=β0+β1xi1+β2xi2+...+ϵi=xiTβ+ϵ
广义线性:transformationofy=β0+β1xi1+β2xi2+...+ϵi=xi⃗Tβ⃗+ϵ⃗\color{#FF7256}transformation\ of\ y \color{black}= \beta_0 + \beta_1x_{i1} + \beta_2x_{i2} +... + \epsilon_i = \vec {x_i}^T \vec{\beta} + \vec \epsilontransformationofy=β0+β1xi1+β2xi2+...+ϵi=xiTβ+ϵ
transformation 可以用 log(y)log(y)log(y), logit(y)logit(y)logit(y),Φ−1(y)\Phi^{-1}(y)Φ−1(y) 等等。←Φ−1是正态分布的累计分布函数的反函数\leftarrow \Phi^{-1} 是正态分布的累计分布函数的反函数←Φ−1是正态分布的累计分布函数的反函数。
在logistic regression中就是用的 logitlogitlogit函数做的 transformation。所以,说白了logistic regression依然是Independent variable x⃗\vec{x}x 的线性模型,只是给Dependent variable 套了一层外衣。
第三节 —— 视角切换到机器学习
我们把刚才统计中的各种符号和术语渐变到机器学习中来。
一切似乎都逐渐明朗了。
w⃗Tx⃗\vec{w}^T\vec{x}wTx 不就是特征的 weighted sum 嘛。假如共有k个特征(b 表示bias):
w⃗={w1w2..wkb}xi⃗={xi1xi2..xik1}\vec{w}=\left\{ \begin{matrix} w_1\\w_2\\.\\.\\w_k\\b \end{matrix} \right\} \quad \quad \vec{x_i} = \left\{ \begin{matrix} x_{i1}\\x_{i2}\\.\\.\\x_{ik}\\1 \end{matrix} \right\}w=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧w1w2..wkb⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫xi=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧xi1xi2..xik1⎭⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎫
还记不记得最简单粗暴的 Perceptron 二分类? 神经网络入门时都会看到这样一张图:
Sign() 就是一个简单粗暴的step function。当自变量低于阈值时,函数值为0,超过阈值时函数值为1. 它也算一个 activation function吧,作用就是给 w⃗Tx⃗\vec{w}^T\vec{x}wTx 套一层外衣,变成了输出。但是sign() 不可导成为了致命伤。于是我们给 w⃗Tx⃗\vec{w}^T\vec{x}wTx 换件衣服变成: σ(w⃗Tx⃗)=11+exp(−w⃗Tx⃗)←这就舒服多了!\sigma(\vec{w}^T\vec{x}) = \frac{1}{1+exp(- \ \vec{w}^T\vec{x})} \quad\leftarrow 这就舒服多了!σ(wTx)=1+exp(−wTx)1←这就舒服多了!
σ()\sigma()σ()光滑可导并且值域还刚好是(0,1),因此可以模拟概率。
像回归分析中的一样,考虑一个二分类模型,label服从 Bernoulli(p)Bernoulli(p)Bernoulli(p) 分布,yi=1y_i=1yi=1 (正例) 的概率为 PiP_iPi 。之后,训练 logistic regression模型意味着用特征的线性组合去拟合p的对数几率 (跟刚才一样)。
Model:log(Pi1−Pi)=w⃗Tx⃗⇔{Pi=P(yi=1∣xi⃗)=11+exp(−w⃗Tx⃗)=σ(w⃗Tx⃗)1−Pi=P(yi=0∣xi⃗)=exp(−w⃗Tx⃗)1+exp(−w⃗Tx⃗)=1−σ(w⃗Tx⃗)Model: log(\frac{P_i}{1-P_i}) = \vec{w}^T\vec{x} \quad \Leftrightarrow \quad \begin{cases} P_i=P(y_i=1\ |\ \vec{x_i}) = \frac{1}{1+exp(-\vec{w}^T\vec{x})}=\sigma(\vec{w}^T\vec{x}) \\ \ \\ 1-P_i= P(y_i=0\ |\ \vec{x_i})= \frac{exp(-\vec{w}^T\vec{x})}{1+exp(-\vec{w}^T\vec{x})}=1-\sigma(\vec{w}^T\vec{x}) \end{cases} Model:log(1−PiPi)=wTx⇔⎩⎪⎨⎪⎧Pi=P(yi=1∣xi)=1+exp(−wTx)1=σ(wTx)1−Pi=P(yi=0∣xi)=1+exp(−wTx)exp(−wTx)=1−σ(wTx)
所以,模型输出是 σ(w⃗Tx⃗)\sigma(\vec{w}^T\vec{x})σ(wTx),它的含义是:在看到 xi⃗\vec {x_i}xi 的条件下,模型认为 yi=1y_i=1yi=1 的概率。如果输出大于 12\frac{1}{2}21,则预测正例,如果小于 12\frac{1}{2}21,则预测负例。
第四节:神奇的吻合 —— 逻辑斯蒂回归的损失函数
1. Logistic Loss —— Negative sum of log accuracy
假设预测对得1分,否则0分,label ∈\in∈ {1, -1}
那么,对于第i条训练数据,若真实 label = 1,得1分的概率为 11+exp(−w⃗Txi⃗)\frac{1}{1+exp(-\vec{w}^T\vec{x_i})}1+exp(−wTxi)1
若真实 label = -1,得1分的概率为 exp(−w⃗Txi⃗)1+exp(−w⃗Txi⃗)=11+exp(w⃗Txi⃗)\frac{exp(-\vec{w}^T\vec{x_i})}{1+exp(-\vec{w}^T\vec{x_i})} = \frac{1}{1+exp(\vec{w}^T\vec{x_i})}1+exp(−wTxi)exp(−wTxi)=1+exp(wTxi)1
把这两种情况综合一下,得1分的概率为 P(accurate) = 11+exp(−yiw⃗Txi⃗)\frac{1}{1+exp(-\color{red}y_i\color{black}\vec{w}^T\vec{x_i})}1+exp(−yiwTxi)1
Loss=NegativesumoflogaccuracyLoss = Negative\ sum\ of\ log\ accuracyLoss=Negativesumoflogaccuracy
=−∑i=1nlog(P(accurate))\quad\quad\ =-\displaystyle\sum^{n}_{i=1}log(P(accurate))=−i=1∑nlog(P(accurate))
=−∑i=1nlog(11+exp(−yiw⃗Txi⃗))\quad\quad\ =-\displaystyle\sum^{n}_{i=1}log(\frac{1}{1+exp(-y_i\vec{w}^T\vec{x_i})})=−i=1∑nlog(1+exp(−yiwTxi)1)
=∑i=1nlog[1+exp(−yiw⃗Txi⃗)]\quad\quad\ =\displaystyle\sum^{n}_{i=1}log[\ 1+exp(-y_i\vec{w}^T\vec{x_i})\ ]=i=1∑nlog[1+exp(−yiwTxi)]
n 是 batch_size
如果我们用SGD(stochastic gradient descent)的话,n = 1。对 Loss 求关于 w⃗\vec ww 的导数:
∂Loss∂w⃗=exp(−yiw⃗Txi⃗)(−yixi⃗)1+exp(−yiw⃗Txi⃗)\frac{\partial{Loss}}{\partial{\vec w}} = \frac{exp(-y_i\vec{w}^T\vec{x_i}) (-y_i\vec{x_i})}{1+exp(-y_i\vec{w}^T\vec{x_i})}∂w∂Loss=1+exp(−yiwTxi)exp(−yiwTxi)(−yixi)
=(−yixi⃗)P(notaccurate)\quad\quad\quad\ \ =(-y_i\vec{x_i})P(not\ accurate)=(−yixi)P(notaccurate)
还记得梯度下降的权重更新方法吗?⇒w⃗=w⃗−αd\Rightarrow\ \ \vec w = \vec w-\alpha d⇒w=w−αd
其中,α\alphaα 是 learning rate,ddd 是gradient,也就是刚才算的 (−yixi⃗)P(notaccurate)(-y_i\vec{x_i})P(not\ accurate)(−yixi)P(notaccurate)
权重更新:w⃗=w⃗−αP(notaccurate)yixi⃗\ \vec w = \vec w-\alpha P(not\ accurate)y_i\vec{x_i}w=w−αP(notaccurate)yixi
一般情况下,logistic loss 的公式为 L(y,f(x))=log[1+exp(−yf(x))]\color{#FF7256}L(y, f(x))=log[\ 1+exp(-yf(x))\ ]L(y,f(x))=log[1+exp(−yf(x))] 。也就是说,在logistic regression 中,f(x)=w⃗Tx⃗f(x)=\vec w^T\vec xf(x)=wTx,而在一般情况下,f(x)f(x)f(x) 可以用更复杂的函数甚至是神经网络代替。
2. Maximum Likelihood Loss
刚才我们定义 label (y) ∈\in∈ {1,-1}。现在令 t = y+12\frac{y+1}{2}2y+1,则 t ∈\in∈ {1,0}
{y=1⇒t=1y=−1⇒t=0\begin{cases} y=1\ \Rightarrow \ t=1 \\ y=-1\ \Rightarrow \ t=0 \end{cases}{y=1⇒t=1y=−1⇒t=0
在模型中条件概率 P(ti∣xi⃗)P(t_i\ |\ \vec{x_i})P(ti∣xi) 符合 BernoulliBernoulliBernoulli 分布。
即 {P(ti=1∣xi⃗)=σ(w⃗Txi⃗)P(ti=0∣xi⃗)=1−σ(w⃗Txi⃗)\begin{cases} P(t_i=1\ |\ \vec{x_i}) = \sigma(\vec w^T\vec{x_i}) \\ P(t_i=0\ |\ \vec{x_i}) = 1-\sigma(\vec w^T\vec{x_i}) \end{cases}{P(ti=1∣xi)=σ(wTxi)P(ti=0∣xi)=1−σ(wTxi)
在极大似然的视角下假设这个模型是正确的,那么看到我们数据集中的 n 个样本:(x1⃗,t1),(x2⃗,t2),...,(xn⃗,tn)(\vec{x_1}, t_1), (\vec{x_2}, t_2), ..., (\vec{x_n}, t_n)(x1,t1),(x2,t2),...,(xn,tn) 的概率(likelihood)为:
Likelihood=∏i=1n[σ(w⃗Txi⃗)]ti[1−σ(w⃗Txi⃗)]1−tiLikelihood=\displaystyle \prod^{n}_{i=1}\ [\sigma(\vec w^T\vec{x_i})]^{t_i}\ [1-\sigma(\vec w^T\vec{x_i})]^{1-t_i}Likelihood=i=1∏n[σ(wTxi)]ti[1−σ(wTxi)]1−ti
log(Likelihood)=∑i=1n{tilog[σ(w⃗Txi⃗)]+(1−ti)log[1−σ(w⃗Txi⃗)]}log(Likelihood)=\displaystyle \sum^{n}_{i=1}\ \{\ t_ilog[\sigma(\vec w^T\vec{x_i})]+(1-t_i)log[1-\sigma(\vec w^T\vec{x_i})]\ \}log(Likelihood)=i=1∑n{tilog[σ(wTxi)]+(1−ti)log[1−σ(wTxi)]}
maxw⃗{log(Likelihood)}=minw⃗{−log(likelihood)}max_{\vec w}\ \{ log(Likelihood)\}= min_{\vec w}\ \{ -log(likelihood)\}maxw{log(Likelihood)}=minw{−log(likelihood)}
⇒Loss=−log(Likelihood)=−∑i=1n{tilog[σ(w⃗Txi⃗)]+(1−ti)log[1−σ(w⃗Txi⃗)]}\Rightarrow \color{red}Loss\color{black}=-log(Likelihood) = \color{red}-\displaystyle \sum^{n}_{i=1}\ \{\ t_ilog[\sigma(\vec w^T\vec{x_i})]+(1-t_i)log[1-\sigma(\vec w^T\vec{x_i})]\ \}⇒Loss=−log(Likelihood)=−i=1∑n{tilog[σ(wTxi)]+(1−ti)log[1−σ(wTxi)]}
3. Cross Entropy Loss
看到最大似然损失的时候,大家有没有发觉最大似然损失的公式跟二项交叉熵损失是一样的呀!
CrossEntropyLoss=−∑i=1n{tilog[σ(w⃗Txi⃗)]+(1−ti)log[1−σ(w⃗Txi⃗)]}\color{red}Cross Entropy Loss=-\displaystyle \sum^{n}_{i=1}\ \{\ t_ilog[\sigma(\vec w^T\vec{x_i})]+(1-t_i)log[1-\sigma(\vec w^T\vec{x_i})]\ \}CrossEntropyLoss=−i=1∑n{tilog[σ(wTxi)]+(1−ti)log[1−σ(wTxi)]}
不过我们依旧要从信息论的视角来好好地盘一盘交叉熵。
熵是随机变量不确定性的度量,它也是平均意义上描述随机变量所需的编码长度的度量。
相对熵,也叫 K-L散度,描述两个随机分布之间距离。它的定义如下:(∑x\displaystyle \sum_{x}x∑ 代表对随机变量 xxx 所有可能的取值求和)
KL(P∣∣Q)=∑xP(x)logP(x)Q(x)KL(P\ ||\ Q)=\displaystyle \sum_{x}P(x)log\frac{P(x)}{Q(x)}KL(P∣∣Q)=x∑P(x)logQ(x)P(x)
⇔KL(P∣∣Q)=−∑xP(x)logQ(x)−(−∑xP(x)logP(x))\Leftrightarrow KL(P\ ||\ Q)=-\displaystyle \sum_{x}P(x)logQ(x)\ -\ (-\displaystyle \sum_{x}P(x)logP(x))⇔KL(P∣∣Q)=−x∑P(x)logQ(x)−(−x∑P(x)logP(x))
⇔KL(P∣∣Q)=CrossEntropy(P∣∣Q)−H(P)\color{#FF7256}\Leftrightarrow KL(P\ ||\ Q)=CrossEntropy(P\ ||\ Q)-H(P)⇔KL(P∣∣Q)=CrossEntropy(P∣∣Q)−H(P)
⇔KL(P∣∣Q)=分布P和Q的交叉熵−分布P的信息熵\Leftrightarrow KL(P\ ||\ Q)= 分布P和Q的交叉熵-分布 P 的信息熵⇔KL(P∣∣Q)=分布P和Q的交叉熵−分布P的信息熵
信息论课本上摘录内容:相对熵度量真实分布为 PPP 而假定分布为 QQQ 时的无效性。例如,已知随机变量的真是分布为 PPP,于是可以构造平均长度为 H(P)H(P)H(P) 的编码描述这个随机变量。但如果使用针对分布 QQQ 的编码,那么平均编码长度为 H(P)+KL(P∣Q)=CrossEntropy(P∣Q)H(P)+KL(\ P|\ Q) = CrossEntropy(P\ |\ Q)H(P)+KL(P∣Q)=CrossEntropy(P∣Q)。
CrossEntropy(P∣Q)=−∑xP(x)logQ(x)\color{#FF7256}CrossEntropy(P\ |\ Q)=-\displaystyle\sum_{x}P(x)logQ(x)CrossEntropy(P∣Q)=−x∑P(x)logQ(x)
在机器学习中,真实分布 PPP 就是样本数据的分布,而假定分布 QQQ 就等同于模型认为的分布。我们希望 PPP 和 QQQ 的距离越近越好。由于 H(P)H(P)H(P) 跟模型参数无关,所以在训练参数的时候,缩小 KL(P∣∣Q)KL(P\ ||\ Q)KL(P∣∣Q) 等同于缩小 CrossEntropy(P∣∣Q)CrossEntropy(P\ ||\ Q)CrossEntropy(P∣∣Q)。这就是为啥机器学习中这么喜欢用交叉熵。它的含义:描述两个概率分布的差异,差异越小,交叉熵越小。
在二分类问题中,随机变量 labellabellabel 代表类别,它只有两种可能的取值:1,0. 然后我们考虑在已知特征 xi⃗\vec {x_i}xi 情况下的条件概率分布。真实的条件概率分布为 RRR(为了避免和后面 BernoulliBernoulliBernoulli 分布里的 PiP_iPi 弄混),模型模拟的条件概率分布为 QQQ。
CrossEntropyi(R∣Q)=−∑k=1,0R(label=k∣xi⃗)logQ(label=k∣xi⃗)CrossEntropy_i(R\ |\ Q)=-\displaystyle \sum_{k=1, 0}R(label=k\ |\ \vec{x_i})\ logQ(label=k\ |\ \vec{x_i})CrossEntropyi(R∣Q)=−k=1,0∑R(label=k∣xi)logQ(label=k∣xi)
其中,logQ(label=1∣xi⃗)=σ(w⃗Txi⃗)=PilogQ(label=1\ |\ \vec{x_i})=\sigma(\vec w^T\vec{x_i})=P_ilogQ(label=1∣xi)=σ(wTxi)=Pi,logQ(label=0∣xi⃗)=1−σ(w⃗Txi⃗)=1−PilogQ(label=0\ |\ \vec{x_i})=1 -\sigma(\vec w^T\vec{x_i})=1-P_ilogQ(label=0∣xi)=1−σ(wTxi)=1−Pi
由于样本标签已确定,所以样本中的条件概率分布就不是随机的了:
①If label = 1, then R(label=1∣xi⃗)=1R(label=1\ |\ \vec{x_i})=1R(label=1∣xi)=1,R(label=0∣xi⃗)=0R(label=0\ |\ \vec{x_i})=0R(label=0∣xi)=0,
⇒CrossEntropyi(R∣Q)=−[1⋅logPi+0⋅log(1−Pi)]\Rightarrow CrossEntropy_i(R\ |\ Q)=-[1·logP_i+0·log(1-P_i)]⇒CrossEntropyi(R∣Q)=−[1⋅logPi+0⋅log(1−Pi)]
②If label = 0, then R(label=1∣xi⃗)=0R(label=1\ |\ \vec{x_i})=0R(label=1∣xi)=0,R(label=0∣xi⃗)=1R(label=0\ |\ \vec{x_i})=1R(label=0∣xi)=1
⇒CrossEntropyi(R∣Q)=−[0⋅logPi+1⋅log(1−Pi)]\Rightarrow CrossEntropy_i(R\ |\ Q)=-[0·logP_i+1·log(1-P_i)]⇒CrossEntropyi(R∣Q)=−[0⋅logPi+1⋅log(1−Pi)]
综合一下这两个case:CrossEntropyi(R∣Q)=−[label⋅logPi+(1−label)⋅log(1−Pi)]CrossEntropy_i(R\ |\ Q)=-[label·logP_i+(1-label)·log(1-P_i)]CrossEntropyi(R∣Q)=−[label⋅logPi+(1−label)⋅log(1−Pi)]
对每一条数据的损失进行加和,就得到了交叉熵损失的公式(刚才列出来过了):
−∑i=1n{tilog[σ(w⃗Txi⃗)]+(1−ti)log[1−σ(w⃗Txi⃗)]}-\displaystyle \sum^{n}_{i=1}\ \Big\{t_ilog[\sigma(\vec w^T\vec{x_i})]+(1-t_i)log[1-\sigma(\vec w^T\vec{x_i})]\Big\}−i=1∑n{tilog[σ(wTxi)]+(1−ti)log[1−σ(wTxi)]}
小结
Maximum Likelihood Loss 与 Cross Entropy Loss 是等价的,也就是说,使Likelihood最大化的过程也是使交叉熵最小化的过程,也就等同于使模型模拟的分布与样本数据的真是分布越来越近。这看似一个神奇的巧合,事实上,是有理论的链条将它们连接起来的。相对熵在统计学中对应的就是 “似然比的对数期望”。
KL(P∣∣Q)=∑xP(x)logP(x)Q(x)=Ex[logP(x)Q(x)]KL(P\ ||\ Q)=\displaystyle \sum_{x}P(x)log\frac{P(x)}{Q(x)}=E_x\Big[log\frac{P(x)}{Q(x)}\Big]KL(P∣∣Q)=x∑P(x)logQ(x)P(x)=Ex[logQ(x)P(x)]
按照这个思路推导下去,那么交叉熵其实就是 “似然的对数期望”:(设 x 是随机变量)
w⃗∗=argmaxw⃗∏i=1nQ(x∣w⃗)←\vec w^*=argmax{\vec w} \displaystyle \prod^{n}_{i=1} Q(x\ |\ \vec w)\ \leftarroww∗=argmaxwi=1∏nQ(x∣w)← 对参数做最大似然估计
=argminw⃗∏i=1nQ(x∣w⃗)\quad\ =argmin_{\vec w} \displaystyle \prod^{n}_{i=1} Q(x\ |\ \vec w)=argminwi=1∏nQ(x∣w)
=argminw⃗∑i=1nlogQ(x∣w⃗)\quad\ =argmin_{\vec w} \displaystyle \sum^{n}_{i=1} logQ(x\ |\ \vec w)=argminwi=1∑nlogQ(x∣w)
=argminw⃗∑xCount(X=x)logQ(x∣w⃗)←\quad\ =argmin_{\vec w} \displaystyle \sum_{x} Count(X=x)logQ(x\ |\ \vec w)\ \leftarrow=argminwx∑Count(X=x)logQ(x∣w)← 从按index的遍历改为按x的取值遍历
=argminw⃗∑x(Count(X=x)n)logQ(x∣w⃗)←\quad\ =argmin_{\vec w} \displaystyle \sum_{x} (\frac{Count(X=x)}{n})logQ(x\ |\ \vec w)\ \leftarrow=argminwx∑(nCount(X=x))logQ(x∣w)← 给目标函数除以了样本总数 n,缩放目标函数不会改变 argminargminargmin 的结果。
=argminw⃗∑xR^(X=x)logQ(x∣w⃗)←R^(X=x)=Count(X=x)n是样本数据的经验分布\quad\ =argmin_{\vec w} \displaystyle \sum_{x} \hat{R}(X=x)logQ(x\ |\ \vec w)\ \leftarrow\ \color{#8AD597}\hat{R}(X=x)=\frac{Count(X=x)}{n} 是样本数据的经验分布=argminwx∑R^(X=x)logQ(x∣w)←R^(X=x)=nCount(X=x)是样本数据的经验分布
=argminw⃗Ex∼R^logQ(x∣w⃗)\quad\ =argmin_{\vec w} E_{x\sim \hat{R}}logQ(x\ |\ \vec w)=argminwEx∼R^logQ(x∣w)
=argminw⃗Ex∼RlogQ(x∣w⃗)←当数据量足够大并且采样方法足够好时,样本数据的经验分布=真实分布\quad\ =argmin_{\vec w} E_{x\sim R}logQ(x\ |\ \vec w)\ \leftarrow \color{#8AD597} 当数据量足够大并且采样方法足够好时,样本数据的经验分布=真实分布=argminwEx∼RlogQ(x∣w)←当数据量足够大并且采样方法足够好时,样本数据的经验分布=真实分布
=argminw⃗∑xR(X=x)logQ(x∣w⃗)←\quad\ =argmin_{\vec w} \displaystyle \sum_{x} R(X=x)logQ(x\ |\ \vec w) \leftarrow=argminwx∑R(X=x)logQ(x∣w)← 现在已经推导到了 “求使交叉熵最小化的参数” 这个形式
接下来还能推出 LogisticLossLogistic\ LossLogisticLoss 与最大似然损失也是等价的:
If label ∈\in∈ {1,-1},then Q(yi∣xi⃗)=11+exp(−yiw⃗Txi⃗)=σ(yiw⃗Txi⃗)Q(y_i\ |\ \vec{x_i}) = \frac{1}{1+exp(-y_i\vec{w}^T\vec{x_i})}=\sigma(y_i\vec{w}^T\vec{x_i})Q(yi∣xi)=1+exp(−yiwTxi)1=σ(yiwTxi)
Likelihood=∏i=1nσ(yiw⃗Txi⃗)Likelihood= \prod^n_{i=1}\sigma(y_i\vec{w}^T\vec{x_i})Likelihood=i=1∏nσ(yiwTxi)
−log(Likelihood)=−∑i=1nσ(yiw⃗Txi⃗)=∑i=1nlog[1+exp(−yiw⃗Txi⃗)]-log(Likelihood)=-\sum^n_{i=1}\sigma(y_i\vec{w}^T\vec{x_i})=\displaystyle\sum^{n}_{i=1}log[\ 1+exp(-y_i\vec{w}^T\vec{x_i})\ ]−log(Likelihood)=−i=1∑nσ(yiwTxi)=i=1∑nlog[1+exp(−yiwTxi)]
If label ∈\in∈ {1,0},then Q(yi∣xi⃗)=σ(w⃗Txi⃗)]yi[1−σ(w⃗Txi⃗)]1−yiQ(y_i\ |\ \vec{x_i}) =\sigma(\vec w^T\vec{x_i})]^{y_i}\ [1-\sigma(\vec w^T\vec{x_i})]^{1-y_i}Q(yi∣xi)=σ(wTxi)]yi[1−σ(wTxi)]1−yi
Likelihood=∏i=1nσ(w⃗Txi⃗)]ti[1−σ(w⃗Txi⃗)]1−tiLikelihood=\prod^n_{i=1}\sigma(\vec w^T\vec{x_i})]^{t_i}\ [1-\sigma(\vec w^T\vec{x_i})]^{1-t_i}Likelihood=i=1∏nσ(wTxi)]ti[1−σ(wTxi)]1−ti
−log(Likelihood)=−∑i=1n{yilog[σ(w⃗Txi⃗)]+(1−yi)log[1−σ(w⃗Txi⃗)]}-log(Likelihood)=-\sum^n_{i=1}\Big\{y_ilog[\sigma(\vec w^T\vec{x_i})]+(1-y_i)log[1-\sigma(\vec w^T\vec{x_i})]\Big\}−log(Likelihood)=−i=1∑n{yilog[σ(wTxi)]+(1−yi)log[1−σ(wTxi)]}
可见 LogisticLossLogistic\ LossLogisticLoss 与极大似然损失等价,区别仅仅是标签的定义不同。
这就是本节标题中 “神奇的吻合” 的含义:逻辑斯蒂回归模型的参数无论是用 Logistic Loss 还是 Maximum Likelihood Loss 还是 Cross Entropy Loss 训练出来的是同一组参数!但是这并非纯属偶然,而是同一个概念在信息论中和在统计学中本来就有对应关系。
第五节:分类器中的天真小弟 —— 朴素贝叶斯
朴素贝叶斯文本分类模型
考虑如下文本分类模型:P(yi,di)P(y_i, d_i)P(yi,di) 表示一篇文章以及它的 label 的联合概率。did_idi 指第 i 条训练数据中的文本。假设 did_idi 中每个词都是一个特征。
条件独立分布假设:已知文本标签的条件下,特征的分布是相互独立的。(已知标签后 yiy_iyi,did_idi 的概率等于该文本中每个词出现的概率乘积。
利用贝叶斯条件概率公式:
P(yi,di)=P(y=yi)P(di∣y=yi)P(y_i, d_i)=P(y=y_i)P(d_i\ |\ y=y_i)P(yi,di)=P(y=yi)P(di∣y=yi)
=P(y=yi)∏j=1VP(xj∣y=yi)Cdi(xj)\quad\quad\quad\quad=P(y=y_i)\displaystyle \prod^{V}_{j=1}P(x_j\ |\ y=y_i)^{C_{d_i}(x_j)}=P(y=yi)j=1∏VP(xj∣y=yi)Cdi(xj)
其中,VVV 代表字典的 size,xjx_jxj 代表 the jthj^{th}jth word in dictionary,Cdi(xj)C_{d_i}(x_j)Cdi(xj) 代表词 xjx_jxj 在文件 did_idi 中出现的次数。
Define:P(y=yi)=πyi,P(xj∣y=yi)=θyi,xj←P(y=y_i)=\pi_{y_i}, \quad P(x_j\ |\ y=y_i)=\theta_{y_i,\ x_j}\ \leftarrowP(y=yi)=πyi,P(xj∣y=yi)=θyi,xj← 这两种概率就是我们要估计的参数
⇒P(yi,di)=πyi∏j=1V(θyi,xj)Cdi(xj)\Rightarrow P(y_i, d_i)=\pi_{y_i}\displaystyle \prod^{V}_{j=1}{(\theta_{y_i,\ x_j})}^{C_{d_i}(x_j)}⇒P(yi,di)=πyij=1∏V(θyi,xj)Cdi(xj)
用最大似然法估计朴素贝叶斯的最佳参数
(参数下面带波浪线代表是参数向量 / 矩阵, D 代表数据集中文件的总个数)
Likelihood(π∼,θ∼)=∏i=1DP(yi,di)Likelihood(\underset \sim{\pi},\ \underset \sim{\theta})=\displaystyle \prod^D_{i=1}P(y_i, d_i)Likelihood(∼π,∼θ)=i=1∏DP(yi,di)
=∏i=1D[πyi∏j=1V(θyi,xj)Cdi(xj)]\quad\quad\quad\quad\quad=\displaystyle \prod^D_{i=1}[\pi_{y_i}\displaystyle \prod^{V}_{j=1}{(\theta_{y_i,\ x_j})}^{C_{d_i}(x_j)}]=i=1∏D[πyij=1∏V(θyi,xj)Cdi(xj)]
log(Likelihood(π∼,θ∼))=∑i=1D[logπyi+∑j=1VCdi(xj)log(θyi,xj)]log(Likelihood(\underset \sim{\pi},\ \underset \sim{\theta}))=\displaystyle \sum^D_{i=1}\Big[log\pi_{y_i}+\displaystyle \sum^{V}_{j=1}{C_{d_i}(x_j)}log(\theta_{y_i,\ x_j})\Big]log(Likelihood(∼π,∼θ))=i=1∑D[logπyi+j=1∑VCdi(xj)log(θyi,xj)]
约束:{①∑k=1Kπk=1②foreveryk,∑j=1Vθk,j=1\begin{cases} ①\ \ \displaystyle \sum^{K}_{k=1}\pi_k=1 \\ ②\ \ for\ every\ k,\ \displaystyle \sum^V_{j=1}\theta_{k,\ j}=1 \end{cases}⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧①k=1∑Kπk=1②foreveryk,j=1∑Vθk,j=1
log(Lπk)=∑i=1D[logπyi+∑j=1VCdi(xj)log(θyi,xj)]+α(∑k=1Kπk−1)←log(L_{\pi_k})=\displaystyle \sum^D_{i=1}\Big[log\pi_{y_i}+\displaystyle \sum^{V}_{j=1}{C_{d_i}(x_j)}log(\theta_{y_i,\ x_j})\Big]+\alpha(\sum^K_{k=1}\pi_k-1)\ \leftarrowlog(Lπk)=i=1∑D[logπyi+j=1∑VCdi(xj)log(θyi,xj)]+α(k=1∑Kπk−1)← 对 πk\pi_kπk 求最优解,对第一个约束引入拉格朗日乘子
∂log(Lπk)∂πk=∑i=1D1πkIyi=k+α=0,\frac{\partial{log(L_{\pi_k})}}{\partial{\pi_k}}=\displaystyle \sum^D_{i=1}\frac{1}{\pi_k}I_{y_i=k}+\alpha=0,∂πk∂log(Lπk)=i=1∑Dπk1Iyi=k+α=0, fork=1,2,...,K←\quad for\ k=1,\ 2,\ ...,\ K\ \leftarrowfork=1,2,...,K← 对 πk\pi_kπk 求偏导数并令其得0
Iyi=kI_{y_i=k}Iyi=k 是 Indicator function, Iyi=k={1ifyi=k0otherwiseI_{y_i=k}=\begin{cases} 1\quad if\ y_i=k \\ 0\quad otherwise \end{cases}Iyi=k={1ifyi=k0otherwise
⇒∑i=1DIyi=kπk+α=0\Rightarrow\ \ \frac{\sum^D_{i=1}I_{y_i=k}}{\pi_k}+\alpha=0⇒πk∑i=1DIyi=k+α=0
⇒πk=−(yi=k的文件数)α\Rightarrow\ \ \pi_k=\frac{-(y_i=k的文件数)}{\alpha}⇒πk=α−(yi=k的文件数)
根据第一个约束,我们有: ∑k=1Kπk=−∑k=1K(yi=k的文件数)α=−(总文件个数)α=1\sum^K_{k=1}\pi_k=\frac{-\sum^K_{k=1}(y_i=k的文件数)}{\alpha}=\frac{-(总文件个数)}{\alpha}=1∑k=1Kπk=α−∑k=1K(yi=k的文件数)=α−(总文件个数)=1
⇒α=−(总文件个数)\Rightarrow\ \ \ \alpha=-(总文件个数)⇒α=−(总文件个数)
⇒πk=yi=k的文件数总文件个数\Rightarrow\ \ \color{red}\pi_k=\frac{y_i=k的文件数}{总文件个数}⇒πk=总文件个数yi=k的文件数
log(Lθk,j)=∑i=1D[logπyi+∑j=1VCdi(xj)log(θyi,xj)]+μk(∑j=1Vθk,j−1)←log(L_{\theta_{k,\ j}})=\displaystyle \sum^D_{i=1}[log\pi_{y_i}+\displaystyle \sum^{V}_{j=1}{C_{d_i}(x_j)}log(\theta_{y_i,\ x_j})]+\mu_k(\sum^V_{j=1}\theta_{k,\ j}-1)\ \leftarrowlog(Lθk,j)=i=1∑D[logπyi+j=1∑VCdi(xj)log(θyi,xj)]+μk(j=1∑Vθk,j−1)← 对 θk,j\theta_{k,\ j}θk,j 求最优解,对第二个约束引入拉格朗日乘子
∂log(Lθk,j)∂θk,j=∑i=1DCdi(xj)θk,jIyi=k+μk=0,\frac{\partial{log(L_{\theta_{k,\ j}})}}{\partial{\theta_{k,\ j}}}=\displaystyle \sum^D_{i=1}\frac{C_{d_i}(x_j)}{\theta_{k\ ,j}}I_{y_i=k}+\mu_k=0,∂θk,j∂log(Lθk,j)=i=1∑Dθk,jCdi(xj)Iyi=k+μk=0, fork=1,2,...,K,j=1,2,...,V←\quad for\ k=1,\ 2,\ ...,\ K,\ j=1,\ 2,\ ...,\ V\ \leftarrowfork=1,2,...,K,j=1,2,...,V← 对 θk,j\theta_{k,\ j}θk,j 求偏导数并令其得0
⇒yi=k的文件中词xj的个数θk,j+μk=0\Rightarrow\ \ \frac{y_i=k的文件中词x_j的个数}{\theta_{k,\ j}}+\mu_k=0⇒θk,jyi=k的文件中词xj的个数+μk=0
⇒θk,j=−(yi=k的文件中词xj的个数)μk\Rightarrow\ \ \theta_{k,\ j}=\frac{-(y_i=k的文件中词x_j的个数)}{\mu_k}⇒θk,j=μk−(yi=k的文件中词xj的个数)
根据第二个约束,我们有:
∑j=1Vθk,j=−∑j=1V(yi=k的文件中词xj的个数)μk=−(yi=k的文件中所有词的个数)μk=1\sum^V_{j=1}\theta_{k,\ j}=\frac{-\sum^V_{j=1}(y_i=k的文件中词x_j的个数)}{\mu_k}=\frac{-(y_i=k的文件中所有词的个数)}{\mu_k}=1∑j=1Vθk,j=μk−∑j=1V(yi=k的文件中词xj的个数)=μk−(yi=k的文件中所有词的个数)=1
⇒μk=−(yi=k的文件中所有词的个数)\Rightarrow\ \ \ \mu_k=-(y_i=k的文件中所有词的个数)⇒μk=−(yi=k的文件中所有词的个数)
⇒θk,j=yi=k的文件中词xj的个数yi=k的文件中所有词的个数\Rightarrow\ \ \color{red}\theta_{k,\ j}=\frac{y_i=k的文件中词x_j的个数}{y_i=k的文件中所有词的个数}⇒θk,j=yi=k的文件中所有词的个数yi=k的文件中词xj的个数
朴素贝叶斯,逻辑斯蒂回归,傻傻分不清楚?
之前我们讲一个文件 did_idi 的特征是文件当中的所有单词,那么从现在起 did_idi 用一个特征向量 xi⃗\vec{x_i}xi 表示。
利用贝叶斯条件概率公式:
P(yi∣xi⃗)=P(yi,xi⃗)P(xi⃗)=P(xi⃗∣yi)P(yi)P(xi⃗)P(y_i\ |\ \vec{x_i})=\frac{P(y_i, \vec{x_i})}{P(\vec{x_i})}=\frac{P(\vec{x_i}\ |\ y_i)P(y_i)}{P(\vec{x_i})}P(yi∣xi)=P(xi)P(yi,xi)=P(xi)P(xi∣yi)P(yi)
在二分类问题中,yi∈{1,0}y_i\in\{1,0\}yi∈{1,0}:
{P(yi=1∣xi⃗)=P(xi⃗∣yi=1)P(yi=1)P(xi⃗)←后验概率P(yi=0∣xi⃗)=P(xi⃗∣yi=0)P(yi=0)P(xi⃗)←后验概率\begin{cases} P(y_i=1\ |\ \vec{x_i})=\frac{P(\vec{x_i}\ |\ y_i=1)P(y_i=1)}{P(\vec{x_i})}\ \leftarrow \ \color{#8AD597}后验概率\\ \\ P(y_i=0\ |\ \vec{x_i})=\frac{P(\vec{x_i}\ |\ y_i=0)P(y_i=0)}{P(\vec{x_i})}\ \leftarrow \ \color{#8AD597}后验概率 \end{cases}⎩⎪⎨⎪⎧P(yi=1∣xi)=P(xi)P(xi∣yi=1)P(yi=1)←后验概率P(yi=0∣xi)=P(xi)P(xi∣yi=0)P(yi=0)←后验概率
上面的等式左边是后验概率,然后我们用等式右边的先验概率给表示了。等式右边的分子中 P(xi⃗∣yi=k)P(\vec{x_i}\ |\ y_i=k)P(xi∣yi=k) 和 P(yi=k)P(y_i=k)P(yi=k) 都是参数,用刚才的最大似然法估计。在预测的时候,由于上面两个后验概率表达式的分母一样,所以只要比较分子即可,哪个大就预测为哪一类。
在提及分类问题的时候经常有 “最大后验概率” 这个说法。但是,由于我们忽略了上面两个后验概率表达式的分母 P(xi⃗)P(\vec{x_i})P(xi),因此模型其实计算的是 P(xi⃗∣yi=k)P(yi=k)=P(yi,xi⃗)P(\vec{x_i}\ |\ y_i=k)P(y_i=k) = P(y_i, \vec{x_i})P(xi∣yi=k)P(yi=k)=P(yi,xi)。 朴素贝叶斯其实是对特征向量和标签的 联!合!分!布!建模,而非直接对后验概率建模!
继续回到上面两个后验概率的表达式,分母 P(xi⃗)P(\vec{x_i})P(xi) 的作用看作是“归一化”,因为
P(xi⃗)=P(yi=1,xi⃗)+P(yi=0,xi⃗)P(\vec{x_i})=P(y_i=1, \vec{x_i})+P(y_i=0, \vec{x_i})P(xi)=P(yi=1,xi)+P(yi=0,xi)
=P(xi⃗∣yi=1)P(yi=1)+P(xi⃗∣yi=0)P(yi=0)\quad\quad\quad=P(\vec{x_i}\ |\ y_i=1)P(y_i=1)+P(\vec{x_i}\ |\ y_i=0)P(y_i=0)=P(xi∣yi=1)P(yi=1)+P(xi∣yi=0)P(yi=0)
=两式分子之和\quad\quad\quad=两式分子之和=两式分子之和
我们对 P(yi=1∣xi⃗)P(y_i=1\ |\ \vec{x_i})P(yi=1∣xi) 做一些变形:
P(yi=1∣xi⃗)=P(xi⃗∣yi=1)P(yi=1)P(xi⃗∣yi=1)P(yi=1)+P(xi⃗∣yi=0)P(yi=0)P(y_i=1\ |\ \vec{x_i})=\frac{P(\vec{x_i}\ |\ y_i=1)P(y_i=1)}{P(\vec{x_i}\ |\ y_i=1)P(y_i=1)+P(\vec{x_i}\ |\ y_i=0)P(y_i=0)}P(yi=1∣xi)=P(xi∣yi=1)P(yi=1)+P(xi∣yi=0)P(yi=0)P(xi∣yi=1)P(yi=1)
=11+P(xi⃗∣yi=0)P(yi=0)P(xi⃗∣yi=1)P(yi=1)\quad\quad\quad\quad\ \ =\frac{1}{1+\frac{P(\vec{x_i}\ |\ y_i=0)P(y_i=0)}{P(\vec{x_i}\ |\ y_i=1)P(y_i=1)}}=1+P(xi∣yi=1)P(yi=1)P(xi∣yi=0)P(yi=0)1
=11+exp{−log(P(xi⃗∣yi=1)P(yi=1)P(xi⃗∣yi=0)P(yi=0))}\quad\quad\quad\quad\ \ =\frac{1}{1+exp\Big\{-log\big(\frac{P(\vec{x_i}\ |\ y_i=1)P(y_i=1)}{P(\vec{x_i}\ |\ y_i=0)P(y_i=0)}\big)\Big\}}=1+exp{−log(P(xi∣yi=0)P(yi=0)P(xi∣yi=1)P(yi=1))}1 (♠)
=11+exp{−log(π1∏j=1V(θ1,xj)Cdi(xj)π0∏j=1V(θ0,xj)Cdi(xj))}\quad\quad\quad\quad\ \ =\frac{1}{1+exp\Bigg\{-log\bigg(\frac{\pi_{1} \prod^{V}_{j=1}{(\theta_{1,\ x_j})}^{C_{d_i}(x_j)}}{\pi_{0} \prod^{V}_{j=1}{(\theta_{0,\ x_j})}^{C_{d_i}(x_j)}} \big)\Bigg\}}=1+exp{−log(π0∏j=1V(θ0,xj)Cdi(xj)π1∏j=1V(θ1,xj)Cdi(xj))}1 (♠’)
=11+exp{−[logπ1+∑j=1VCdi(xj)log(θ1,xj)−logπ0−∑j=1VCdi(xj)log(θ0,xj)]}\quad\quad\quad\quad\ \ =\frac{1}{1+exp\Bigg\{-\bigg[log\pi_{1}+ \sum^{V}_{j=1}C_{d_i}(x_j)log(\theta_{1,\ x_j})-log\pi_{0}- \sum^{V}_{j=1}C_{d_i}(x_j)log(\theta_{0,\ x_j}) \bigg]\Bigg\}}=1+exp{−[logπ1+∑j=1VCdi(xj)log(θ1,xj)−logπ0−∑j=1VCdi(xj)log(θ0,xj)]}1
=11+exp{−log(π1π0)−∑j=1VCdi(xj)log(θ1,xjθ0,xj)}\quad\quad\quad\quad\ \ =\frac{1}{1+exp\Bigg\{- log\big(\frac{\pi_1}{\pi_0}\big)-\sum^{V}_{j=1}C_{d_i}(x_j)log\big(\frac{\theta_{1,\ x_j}}{\theta_{0,\ x_j}}\big)\Bigg\} }=1+exp{−log(π0π1)−∑j=1VCdi(xj)log(θ0,xjθ1,xj)}1 (♦)
令 b=log(π1π0)b=log\big(\frac{\pi_1}{\pi_0}\big)b=log(π0π1), wj=log(θ1,xjθ0,xj),forj=1,2,...,Vw_j=log\big(\frac{\theta_{1,\ x_j}}{\theta_{0,\ x_j}}\big),\ for \ j=1,2,...,Vwj=log(θ0,xjθ1,xj),forj=1,2,...,V
既然 did_idi 是用文件中每个词的个数表示的,那么字典里共 VVV 个词意味着每个文件的特征向量有 VVV 维。
于是: xi⃗={Cdi(word1)Cdi(word2)...Cdi(wordV)1←bias}\vec{x_i} = \left\{ \begin{matrix} C_{d_i}(word_1)\\C_{d_i}(word_2)\\.\\.\\.\\C_{d_i}(word_V)\\1\color{#8AD597}\ \leftarrow\ bias\color{black} \end{matrix} \right\}xi=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧Cdi(word1)Cdi(word2)...Cdi(wordV)1←bias⎭⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎫,w⃗={w1w2...wVb}={log(θ1,word1θ0,word1)log(θ1,word2θ0,word2)...log(θ1,wordVθ0,wordV)log(π1π0)}\quad\vec w=\left\{ \begin{matrix} w_1 \\ w_2 \\ .\\.\\.\\ w_V \\ b \end{matrix}\right\} = \left\{ \begin{matrix} log\big(\frac{\theta_{1,\ word_1}}{\theta_{0,\ word_1}}\big) \\ \\ log\big(\frac{\theta_{1,\ word_2}}{\theta_{0,\ word_2}}\big) \\.\\.\\.\\ log\big(\frac{\theta_{1,\ word_V}}{\theta_{0,word_V}}\big) \\ \\ log\big(\frac{\pi_1}{\pi_0}\big) \end{matrix}\right\}w=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧w1w2...wVb⎭⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎫=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧log(θ0,word1θ1,word1)log(θ0,word2θ1,word2)...log(θ0,wordVθ1,wordV)log(π0π1)⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫
将 xi⃗,w⃗\vec{x_i},\ \vec wxi,w 带入上面的 (♦)式,得到:P(yi=1∣xi⃗)=11+exp(−w⃗Txi⃗)P(y_i=1\ |\ \vec{x_i})=\frac{1}{1+exp(-\vec{w}^T\vec{x_i})}P(yi=1∣xi)=1+exp(−wTxi)1
哟吼~ 我们竟然把朴素贝叶斯中的后验概率推出了 logistic regression 的模样!
这时候不禁会想,难道朴素贝叶斯和 logistic regression 是。。。等。。。价的?小朋友你是否有很多问号???
是不是会这么想:假如一开始就把后验概率用 xi⃗\vec{x_i}xi 和 w⃗\vec ww 表示,直接对后验概率建模,那样就是 logistic regression 模型。然后由于 logistic regression 是用最大似然损失,经过梯度下降求得的使损失最小化的参数,而朴素贝叶斯刚好也是用最大似然法求的最优参数,这样 logistic regression 和朴素贝叶斯对文本二分类问题的解就,一模一样了吗??
Emmmm其实不然。
注意看刚刚的一大串推导当中(♠)→\rightarrow→ (♠’)这一步是在把 P(xi⃗∣yi=k)P(\vec{x_i}\ |\ y_i=k)P(xi∣yi=k) 展开,这时候用到了特征之间的条件独立假设!而如果一开始用的 logistic regression 模型,得到 P(yi=1∣xi⃗)=P(y_i=1\ |\ \vec{x_i})=P(yi=1∣xi)= 11+exp(−w⃗Txi⃗)\frac{1}{1+exp(-\vec{w}^T\vec{x_i})}1+exp(−wTxi)1,然后反着推,就没有条件独立假设,是推不回去的。Logistic regression 训练参数的时候即便特征之间不独立,也能训练出最优的参数,但此时 w⃗\vec ww 不一定等于 {log(θ1,word1θ0,word1)log(θ1,word2θ0,word2)...log(θ1,wordVθ0,wordV)log(π1π0)}\left\{ \begin{matrix} log\big(\frac{\theta_{1,\ word_1}}{\theta_{0,\ word_1}}\big) \\ \\ log\big(\frac{\theta_{1,\ word_2}}{\theta_{0,\ word_2}}\big) \\.\\.\\.\\ log\big(\frac{\theta_{1,\ word_V}}{\theta_{0,word_V}}\big) \\ \\ log\big(\frac{\pi_1}{\pi_0}\big) \end{matrix}\right\}⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧log(θ0,word1θ1,word1)log(θ0,word2θ1,word2)...log(θ0,wordVθ1,wordV)log(π0π1)⎭⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎫
Take away message:Logistic regression + 条件独立假设 (约束) ⇔\Leftrightarrow⇔ Naive Bayes. Logistic regression is more general, more 牛逼.
整理 Logistic Regression 和 Naive Bayes 的异同
第六节:逻辑斯蒂回归& 最大熵模型的血缘关系
最大熵原理
学习概率模型时,在所有可能的,满足约束条件的模型中,熵最大的模型最好。
概率分布 P 的熵 =H(P)=−∑xP(x)logP(x)=H(P)=-\displaystyle \sum_xP(x)logP(x)=H(P)=−x∑P(x)logP(x)
熵满足这个不等式:0≤H(P)≤log∣X∣0\leq H(P)\leq log|X|0≤H(P)≤log∣X∣. ∣X∣|X|∣X∣ 代表随机变量 X 所有可能的取值的个数。当且仅当 X 是均匀分布的时候,右边的等号成立,此时熵最大。直观地讲,最大熵原理认为要选择的概率模型首先必须要满足已有的事实,即约束条件。在没有更多信息的情况下,那些不确定的部分都是 “等可能” 的。“等可能” 不容易操作,而熵则是一个可优化的数值。于是最大熵原理通过熵的最大化来表示 “等可能性”。
最大熵模型的定义
训练数据集 T={(x1⃗,y1),(x2⃗,y2),...,}T=\{(\vec{x_1}, y_1),\ (\vec{x_2},y_2),\ ...,\ \}T={(x1,y1),(x2,y2),...,}
用特征函数 f(x⃗,y)f(\vec x,\ y)f(x,y) 描述 x⃗\vec xx 和 yyy 之间的某一事实:
f(x⃗,y)={1ifx⃗&y满足某一事实0otherwisef(\vec x,\ y)=\begin{cases} 1\quad if\ \vec x\ \&\ y\ 满足某一事实 \\ 0\quad otherwise\end{cases}f(x,y)={1ifx&y满足某一事实0otherwise
定义在训练数据集上的经验分布:
{P^(X⃗=x⃗,Y=y)=Count(X⃗=x⃗,Y=y)N←经验联合分布P^(X⃗=x⃗)=Count(X⃗=x⃗)N←经验边缘分布\begin{cases} \hat{P}(\vec X=\vec x,\ Y=y)=\frac{Count(\vec X=\vec x,\ Y=y)}{N}\ \leftarrow\ \color{#8AD597}经验联合分布\\ \hat{P}(\vec X=\vec x)=\frac{Count(\vec X=\vec x)}{N}\ \leftarrow\ \color{#8AD597}经验边缘分布\end{cases}{P^(X=x,Y=y)=NCount(X=x,Y=y)←经验联合分布P^(X=x)=NCount(X=x)←经验边缘分布
假设分类模型是对条件概率分布 P(Y∣X⃗)P(Y\ |\ \vec X)P(Y∣X) 建模。
定义 {f(x⃗,y)在经验联合分布上的期望:EP^(f)=∑x⃗,yP^(x⃗,y)f(x⃗,y)f(x⃗,y)关于模型P(Y∣X⃗)与经验边缘分布P^(X⃗)的期望:EP(f)=∑x⃗,yP(y∣x⃗)P^(x⃗)f(x⃗,y)\begin{cases} f(\vec x,\ y) 在经验联合分布上的期望:E_{\hat P}(f)=\displaystyle\sum_{\vec x,\ y}\hat P(\vec x,\ y)f(\vec x,\ y) \\ \\ f(\vec x,\ y) 关于模型P(Y\ |\ \vec X)与经验边缘分布\hat{P}(\vec X)的期望:E_{P}(f)=\displaystyle\sum_{\vec x,\ y}P(y\ |\ \vec x)\hat P(\vec x)f(\vec x,\ y) \end{cases}⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧f(x,y)在经验联合分布上的期望:EP^(f)=x,y∑P^(x,y)f(x,y)f(x,y)关于模型P(Y∣X)与经验边缘分布P^(X)的期望:EP(f)=x,y∑P(y∣x)P^(x)f(x,y)
约束条件: EP^(f)=EP(f)E_{\hat P}(f)=E_{P}(f)EP^(f)=EP(f) (这两个期望相等表明模型可以从数据集获得有关真实分布充足的信息)
如果有 n 个事实,那么将构造 n 个特征函数,就要有 n 个约束条件。
假设满足所有约束条件的集合为:C≡{P∈P∣EP^(fi)=EP(fi),i=1,2,...,n}C\equiv\{P\in\ \mathcal{P}\ |\ E_{\hat P}(f_i)=E_{P}(f_i),\ \ i=1,2,...,n\}C≡{P∈P∣EP^(fi)=EP(fi),i=1,2,...,n}
定义在条件概率分布上的条件熵为: H(P)=−∑x⃗,yP^(x⃗)P(y∣x⃗)logP(y∣x⃗)H(P)=-\displaystyle \sum_{\vec x,\ y}\hat{P}(\vec x)P(y\ |\ \vec x)logP(y\ |\ \vec x)H(P)=−x,y∑P^(x)P(y∣x)logP(y∣x)
⇒\Rightarrow⇒ 最大熵模型就是模型集合 CCC 中 H(P)H(P)H(P) 最大的模型
最大熵模型的学习
最大熵模型的学习等价于约束最优化问题:maxP∈CH(P)⇔minP∈CH(P)\underset{P\in C}{max}H(P)\ \Leftrightarrow\ \underset{P\in C}{min}H(P)P∈CmaxH(P)⇔P∈CminH(P)
约束:EP^(fi)=EP(fi),i=1,2,...,nE_{\hat P}(f_i)=E_{P}(f_i),\ \ i=1,2,...,nEP^(fi)=EP(fi),i=1,2,...,n,∑yP(y∣x⃗)=1\displaystyle\sum_yP(y\ |\ \vec x)=1y∑P(y∣x)=1
将约束最优化问题转化为无约束最优化的对偶问题
引入拉格朗日乘子 w0,w1,...,wnw_0,w_1,...,w_nw0,w1,...,wn,定义拉格朗日函数 L(P,w⃗)\mathcal{L}(P,\ \vec w)L(P,w) (听起来神秘兮兮的~ 别走,先往下看着)
L(P,w⃗)≡−H(P)+w0[1−∑yP(y∣x⃗)]+∑i=1nwi[EP^(fi)−EP(fi)]\mathcal{L}(P,\ \vec w)\equiv -H(P)+w_0[1-\displaystyle\sum_{y}P(y\ |\ \vec x)]+\sum^n_{i=1}w_i[E_{\hat P}(f_i)-E_{P}(f_i)]L(P,w)≡−H(P)+w0[1−y∑P(y∣x)]+i=1∑nwi[EP^(fi)−EP(fi)]
=∑x⃗,yP^(x⃗)P(y∣x⃗)logP(y∣x⃗)+w0[1−∑yP(y∣x⃗)]+∑i=1nwi[∑x⃗,yP^(x⃗,y)fi(x⃗,y)−∑x⃗,yP(y∣x⃗)P^(x⃗)fi(x⃗,y)]\quad\quad\quad\quad= \sum_{\vec x,\ y}\hat{P}(\vec x)P(y\ |\ \vec x)logP(y\ |\ \vec x)+w_0[1-\sum_{y}P(y\ |\ \vec x)]+\sum^n_{i=1}w_i\Big[\sum_{\vec x,\ y}\hat P(\vec x,\ y)f_i(\vec x,\ y)-\sum_{\vec x,\ y}P(y\ |\ \vec x)\hat P(\vec x)f_i(\vec x,\ y)\Big]=∑x,yP^(x)P(y∣x)logP(y∣x)+w0[1−∑yP(y∣x)]+∑i=1nwi[∑x,yP^(x,y)fi(x,y)−∑x,yP(y∣x)P^(x)fi(x,y)]
原始最优化问题: minP∈Cmaxw⃗L(P,w⃗)\underset{P\in C}{min}\ \underset{\vec w}{max}\ \mathcal{L}(P,\ \vec w)P∈CminwmaxL(P,w)
对偶问题:maxw⃗minP∈CL(P,w⃗)\underset{\vec w}{max}\ \underset{P\in C}{min}\ \mathcal{L}(P,\ \vec w)wmaxP∈CminL(P,w)
由于 maxw⃗\underset{\vec w}{max}wmax 是凸函数,原始问题的解和对偶问题的解是等价的。
maxw⃗minP∈CL(P,w⃗)←\underset{\vec w}{max}\ \color{red}\underset{P\in C}{min}\ \mathcal{L}(P,\ \vec w)\ \color{black}\leftarrowwmaxP∈CminL(P,w)← 先求红色的部分,它是 w⃗\vec ww 的函数。
记 Ψ(w⃗)=minP∈CL(P,w⃗)\Psi(\vec w)=\underset{P\in C}{min}\ \mathcal{L}(P,\ \vec w)Ψ(w)=P∈CminL(P,w),称 Ψ(w⃗)\Psi(\vec w)Ψ(w) 为 “对偶函数”。
同时,将 Ψ(w⃗)\Psi(\vec w)Ψ(w) 的解记为:Pw⃗=ArgminP∈CL(P,w⃗)=Pw⃗(y∣x⃗)P_{\vec w}=\underset{P\in C}{Argmin}\ \mathcal{L}(P,\ \vec w)=P_{\vec w}(y\ |\ \vec x)Pw=P∈CArgminL(P,w)=Pw(y∣x)
∂L(P,w⃗)∂P(y∣x⃗)=∑x⃗,yP^(x⃗)[logP(y∣x⃗)+1]−∑yw0−∑x⃗,yP^(x⃗)∑i=1nwifi(x⃗,y)\frac{\partial{\mathcal{L}(P,\ \vec w)}}{\partial{P(y\ |\ \vec x)}}=\displaystyle\sum_{\vec x,\ y}\hat{P}(\vec x)\big[logP(y\ |\ \vec x)+1\big]-\sum_yw_0-\sum_{\vec x,\ y}\hat{P}(\vec x)\sum^n_{i=1}w_if_i(\vec x,\ y)∂P(y∣x)∂L(P,w)=x,y∑P^(x)[logP(y∣x)+1]−y∑w0−x,y∑P^(x)i=1∑nwifi(x,y)
其中,∑yw0=∑y∑xP^(x⃗)w0=∑x⃗,yP^(x⃗)w0←∑xP^(x⃗)=1\displaystyle\sum_yw_0=\sum_y\sum_x\hat{P}(\vec x)w_0=\sum_{\vec x,\ y}\hat{P}(\vec x)w_0\ \leftarrow\ \color{#8AD597}\sum_x\hat{P}(\vec x)=1y∑w0=y∑x∑P^(x)w0=x,y∑P^(x)w0←x∑P^(x)=1
⇒∂L(P,w⃗)∂P(y∣x⃗)=∑x⃗,yP^(x⃗)[logP(y∣x⃗)+1−w0−∑i=1nwifi(x⃗,y)]\Rightarrow\ \frac{\partial{\mathcal{L}(P,\ \vec w)}}{\partial{P(y\ |\ \vec x)}}=\displaystyle\sum_{\vec x,\ y}\hat{P}(\vec x) \Big[logP(y\ |\ \vec x)+1-w_0-\sum^n_{i=1}w_if_i(\vec x,\ y) \Big]⇒∂P(y∣x)∂L(P,w)=x,y∑P^(x)[logP(y∣x)+1−w0−i=1∑nwifi(x,y)]
令 ∂L(P,w⃗)∂P(y∣x⃗)=0\frac{\partial{\mathcal{L}(P,\ \vec w)}}{\partial{P(y\ |\ \vec x)}}=0∂P(y∣x)∂L(P,w)=0,在 P^(x⃗)>0\hat{P}(\vec x)>0P^(x)>0 时,
解得 Pw⃗(y∣x⃗)=exp{w0+∑i=1nwifi(x⃗,y)−1}=P_{\vec w}(y\ |\ \vec x)=exp\big\{w_0+\sum^n_{i=1}w_if_i(\vec x,\ y)-1\big\}=Pw(y∣x)=exp{w0+∑i=1nwifi(x,y)−1}=exp{∑i=1nwifi(x⃗,y)}exp{1−w0}\frac{exp\big\{\sum^n_{i=1}w_if_i(\vec x,\ y)\big\}}{exp\{1-w_0\}}exp{1−w0}exp{∑i=1nwifi(x,y)}
由于 ∑yP(y∣x⃗)=1\displaystyle\sum_yP(y\ |\ \vec x)=1y∑P(y∣x)=1,∑yexp{∑i=1nwifi(x⃗,y)}exp{1−w0}=1⇒\frac{\sum_{y}exp\big\{\sum^n_{i=1}w_if_i(\vec x,\ y)\big\}}{exp\{1-w_0\}}=1\ \Rightarrowexp{1−w0}∑yexp{∑i=1nwifi(x,y)}=1⇒ ∑yexp{∑i=1nwifi(x⃗,y)}=exp{1−w0}\ \sum_{y}exp\big\{\sum^n_{i=1}w_if_i(\vec x,\ y)\big\}=exp\{1-w_0\}∑yexp{∑i=1nwifi(x,y)}=exp{1−w0}
令 Zw⃗(x⃗)=∑yexp{∑i=1nwifi(x⃗,y)}Z_{\vec w}(\vec x)=\sum_{y}exp\big\{\sum^n_{i=1}w_if_i(\vec x,\ y)\big\}Zw(x)=∑yexp{∑i=1nwifi(x,y)},
把 Pw⃗(y∣x⃗)P_{\vec w}(y\ |\ \vec x)Pw(y∣x) 表达式中的分母替换掉,得到:Pw⃗(y∣x⃗)=\color{red}P_{\vec w}(y\ |\ \vec x)=Pw(y∣x)=exp{∑i=1nwifi(x⃗,y)}Zw⃗(x⃗)=exp{特征的加权和}归一化因子\color{red}\frac{exp\big\{\sum^n_{i=1}w_if_i(\vec x,\ y)\big\}}{Z_{\vec w}(\vec x)}\color{#8AD597}=\frac{exp\{特征的加权和\}}{归一化因子}Zw(x)exp{∑i=1nwifi(x,y)}=归一化因子exp{特征的加权和} (♠)
将 Pw⃗(y∣x⃗)P_{\vec w}(y\ |\ \vec x)Pw(y∣x) 代入 L(P,w⃗)\mathcal{L}(P,\ \vec w)L(P,w) 可得:
Ψ(w⃗)=∑x⃗,yP^(x⃗)Pw⃗(y∣x⃗)logPw⃗(y∣x⃗)+w0[1−∑yPw⃗(y∣x⃗)]+∑i=1nwi[∑x⃗,yP^(x⃗,y)fi(x⃗,y)−∑x⃗,yPw⃗(y∣x⃗)P^(x⃗)fi(x⃗,y)]\Psi(\vec w)=\sum_{\vec x,\ y}\hat{P}(\vec x)P_{\vec w}(y\ |\ \vec x)logP_{\vec w}(y\ |\ \vec x)+w_0\big[1-\sum_{y}P_{\vec w}(y\ |\ \vec x) \big]+\sum^n_{i=1}w_i\Big[\sum_{\vec x,\ y}\hat P(\vec x,\ y)f_i(\vec x,\ y)-\sum_{\vec x,\ y}P_{\vec w}(y\ |\ \vec x)\hat P(\vec x)f_i(\vec x,\ y)\Big]Ψ(w)=∑x,yP^(x)Pw(y∣x)logPw(y∣x)+w0[1−∑yPw(y∣x)]+∑i=1nwi[∑x,yP^(x,y)fi(x,y)−∑x,yPw(y∣x)P^(x)fi(x,y)]
=∑x⃗,yP^(x⃗)Pw⃗(y∣x⃗)logPw⃗(y∣x⃗)+∑i=1nwi[∑x⃗,yP^(x⃗,y)fi(x⃗,y)−∑x⃗,yPw⃗(y∣x⃗)P^(x⃗)fi(x⃗,y)]←\quad\quad\ \ =\sum_{\vec x,\ y}\hat{P}(\vec x)P_{\vec w}(y\ |\ \vec x)logP_{\vec w}(y\ |\ \vec x)+\sum^n_{i=1}w_i\Big[\sum_{\vec x,\ y}\hat P(\vec x,\ y)f_i(\vec x,\ y)-\sum_{\vec x,\ y}P_{\vec w}(y\ |\ \vec x)\hat P(\vec x)f_i(\vec x,\ y)\Big]\ \leftarrow=∑x,yP^(x)Pw(y∣x)logPw(y∣x)+∑i=1nwi[∑x,yP^(x,y)fi(x,y)−∑x,yPw(y∣x)P^(x)fi(x,y)]← ∑yPw⃗(y∣x⃗)=1\ \sum_{y}P_{\vec w}(y\ |\ \vec x)=1∑yPw(y∣x)=1,所以带 w0w_0w0 的那一项就没了
=∑x⃗,yP^(x⃗)Pw⃗(y∣x⃗)[logPw⃗(y∣x⃗)−∑i=1nwifi(x⃗,y)]+∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)\quad\quad\ \ =\sum_{\vec x,\ y}\hat{P}(\vec x)P_{\vec w}(y\ |\ \vec x)\Big[logP_{\vec w}(y\ |\ \vec x)-\sum^n_{i=1}w_if_i(\vec x,\ y)\Big]+\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y)=∑x,yP^(x)Pw(y∣x)[logPw(y∣x)−∑i=1nwifi(x,y)]+∑x,yP^(x,y)∑i=1nwifi(x,y)
=∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)+∑x⃗,yP^(x⃗)Pw⃗(y∣x⃗)[∑i=1nwifi(x⃗,y)−logZw⃗(x⃗)−∑i=1nwifi(x⃗,y)]\quad\quad\ \ =\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y) + \sum_{\vec x,\ y}\hat{P}(\vec x)P_{\vec w}(y\ |\ \vec x)\Big[\sum^n_{i=1}w_if_i(\vec x,\ y)-logZ_{\vec w}(\vec x)-\sum^n_{i=1}w_if_i(\vec x,\ y)\Big]=∑x,yP^(x,y)∑i=1nwifi(x,y)+∑x,yP^(x)Pw(y∣x)[∑i=1nwifi(x,y)−logZw(x)−∑i=1nwifi(x,y)]
=∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)−∑x⃗,yP^(x⃗)Pw⃗(y∣x⃗)logZw⃗(x⃗)\quad\quad\ \ =\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y) - \sum_{\vec x,\ y}\hat{P}(\vec x)P_{\vec w}(y\ |\ \vec x)logZ_{\vec w}(\vec x)=∑x,yP^(x,y)∑i=1nwifi(x,y)−∑x,yP^(x)Pw(y∣x)logZw(x)
=∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)−∑x⃗P^(x⃗)logZw⃗(x⃗)∑yPw⃗(y∣x⃗)←\quad\quad\ \ =\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y) - \sum_{\vec x}\hat{P}(\vec x)logZ_{\vec w}(\vec x)\sum_{y}P_{\vec w}(y\ |\ \vec x)\ \leftarrow=∑x,yP^(x,y)∑i=1nwifi(x,y)−∑xP^(x)logZw(x)∑yPw(y∣x)← 再次用到 ∑yPw⃗(y∣x⃗)=1\ \sum_{y}P_{\vec w}(y\ |\ \vec x)=1∑yPw(y∣x)=1
=∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)−∑x⃗P^(x⃗)logZw⃗(x⃗)\quad\quad\ \ =\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y) - \sum_{\vec x}\hat{P}(\vec x)logZ_{\vec w}(\vec x)=∑x,yP^(x,y)∑i=1nwifi(x,y)−∑xP^(x)logZw(x)
之后求对偶问题的外部极大化解: maxw⃗Ψ(w⃗)\underset{\vec w}{max}\ \Psi(\vec w)wmaxΨ(w)
Ψ(w⃗)=∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)−∑x⃗P^(x⃗)logZw⃗(x⃗)\color{red}\Psi(\vec w)=\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y) - \sum_{\vec x}\hat{P}(\vec x)logZ_{\vec w}(\vec x)Ψ(w)=x,y∑P^(x,y)i=1∑nwifi(x,y)−x∑P^(x)logZw(x)
可以用梯度下降等优化算法算出最优权值:w⃗∗\vec{w}^*w∗
于是,Pw⃗∗(y∣x⃗)P_{\vec {w}^*}(y\ |\ \vec x)Pw∗(y∣x) 就是最大熵模型的解。
对于每个具体问题,构造出的最大熵模型的第一步求解 minP∈CL(P,w⃗)\underset{P\in C}{min}\ \mathcal{L}(P,\ \vec w)P∈CminL(P,w) 都是一样的,所以我们把最大熵模型的 “学习” 归结为对偶函数 Ψ(w⃗)\Psi(\vec w)Ψ(w) 的极大化。最大熵模型即可被概括成由上面 (♠) 式表示的条件概率分布。
下面证明对 Ψ(w⃗)\Psi(\vec w)Ψ(w) 的极大化等价于对最大熵模型的极大似然估计。
回顾一下从训练数据集中统计出的经验概率分布:{P^(X⃗=x⃗,Y=y)=Count(X⃗=x⃗,Y=y)NP^(X⃗=x⃗)=Count(X⃗=x⃗)N\begin{cases} \hat{P}(\vec X=\vec x,\ Y=y)=\frac{Count(\vec X=\vec x,\ Y=y)}{N}\\ \hat{P}(\vec X=\vec x)=\frac{Count(\vec X=\vec x)}{N}\end{cases}{P^(X=x,Y=y)=NCount(X=x,Y=y)P^(X=x)=NCount(X=x)
在数据采集得足够好时,数据中的经验概率分布就是真实的概率分布。
LikelihoodP^(Pw⃗)=log∏x⃗,yPw⃗(y∣x⃗)Count(X⃗=x⃗,Y=y)Likelihood_{\hat P}(P_{\vec w})=log\displaystyle\prod_{\vec x,\ y}P_{\vec w}(y\ |\ \vec x)^{Count(\vec X=\vec x,\ Y=y)}LikelihoodP^(Pw)=logx,y∏Pw(y∣x)Count(X=x,Y=y)
=log∏x⃗,yPw⃗(y∣x⃗)Count(X⃗=x⃗,Y=y)N←\quad\quad\quad\quad\quad\quad\quad\quad=log\displaystyle\prod_{\vec x,\ y}P_{\vec w}(y\ |\ \vec x)^{\frac{Count(\vec X=\vec x,\ Y=y)}{N}}\ \leftarrow=logx,y∏Pw(y∣x)NCount(X=x,Y=y)← 对这个式子的极大化等于对上式的极大化
=log∏x⃗,yPw⃗(y∣x⃗)P^(X⃗=x⃗,Y=y)\quad\quad\quad\quad\quad\quad\quad\quad=log\displaystyle\prod_{\vec x,\ y}P_{\vec w}(y\ |\ \vec x)^{\hat P(\vec X=\vec x,\ Y=y)}=logx,y∏Pw(y∣x)P^(X=x,Y=y)
log[LikelihoodP^(Pw⃗)]=∑x⃗,yP^(x⃗,y)logPw⃗(y∣x⃗)log[Likelihood_{\hat P}(P_{\vec w})]=\displaystyle\sum_{\vec x,\ y}\hat P(\vec x,\ y)logP_{\vec w}(y\ |\ \vec x)log[LikelihoodP^(Pw)]=x,y∑P^(x,y)logPw(y∣x)
=∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)−∑x⃗,yP^(x⃗,y)logZw⃗(x⃗)\quad\quad\quad\quad\quad\quad\quad\quad\quad\ \ =\displaystyle\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y)-\displaystyle\sum_{\vec x,\ y}\hat P(\vec x,\ y)logZ_{\vec w}(\vec x)=x,y∑P^(x,y)i=1∑nwifi(x,y)−x,y∑P^(x,y)logZw(x)
=∑x⃗,yP^(x⃗,y)∑i=1nwifi(x⃗,y)−∑x⃗,yP^(x⃗)logZw⃗(x⃗)\quad\quad\quad\quad\quad\quad\quad\quad\quad\ \ =\displaystyle\sum_{\vec x,\ y}\hat P(\vec x,\ y)\sum^n_{i=1}w_if_i(\vec x,\ y)-\displaystyle\sum_{\vec x,\ y}\hat P(\vec x)logZ_{\vec w}(\vec x)=x,y∑P^(x,y)i=1∑nwifi(x,y)−x,y∑P^(x)logZw(x)
=Ψ(w⃗)←\quad\quad\quad\quad\quad\quad\quad\quad\quad\ \ =\Psi(\vec w)\ \leftarrow=Ψ(w)← 已证明对偶函数 Ψ(w⃗)\Psi(\vec w)Ψ(w) 等于对数似然函数 log[LikelihoodP^(Pw⃗)]log[Likelihood_{\hat P}(P_{\vec w})]log[LikelihoodP^(Pw)]
这样,最大熵模型的学习就可以转换为具体求解对数似然函数极大化问题。
小结
再贴一遍最大熵模型的条件概率表达式:
Pw⃗(y∣x⃗)=\color{red}P_{\vec w}(y\ |\ \vec x)=Pw(y∣x)=exp{∑i=1nwifi(x⃗,y)}Zw⃗(x⃗),\color{red}\frac{exp\big\{\sum^n_{i=1}w_if_i(\vec x,\ y)\big\}}{Z_{\vec w}(\vec x)},Zw(x)exp{∑i=1nwifi(x,y)},
Zw⃗(x⃗)=∑yexp{∑i=1nwifi(x⃗,y)}\color{red}Z_{\vec w}(\vec x)=\sum_{y}exp\big\{\sum^n_{i=1}w_if_i(\vec x,\ y)\big\}Zw(x)=y∑exp{i=1∑nwifi(x,y)}
文章快讲完了,我终于要说到逻辑斯蒂回归了,题目不是说要谈它和最大熵模型的血缘关系嘛,下面开始滴血验亲:
令 fi(x⃗,y)={xi←特征向量x⃗的第i维Ify=1(正例)0Ify=0(反例)f_i(\vec x,\ y)=\begin{cases}x_i\ \leftarrow\ \color{#8AD597}特征向量\ \vec x\ 的第 i 维\color{black}\quad If\ y=1\ (正例) \\ 0\quad\ If\ y=0\ (反例)\end{cases}fi(x,y)={xi←特征向量x的第i维Ify=1(正例)0Ify=0(反例),i=1,2,..,V\quad i=1,2,..,Vi=1,2,..,V
VVV 代表特征向量的维度
可能这里有点疑问,因为一开始定义的 fi(x⃗,y)f_i(\vec x,\ y)fi(x,y) 不本来是取值为1和0的二值函数嘛。不过我觉得不需要纠结在这些细节,因为一共有多少个 fif_ifi 是自己定的,这完全就是乘一个系数的问题,可以用很多个 fif_ifi 相加来替代。比如可以设定共有 x1+x2+...+xVx_1+x_2+...+x_Vx1+x2+...+xV 个二值特征函数,然后规定 w1−wx1w_1-w_{x_1}w1−wx1 全部相等,wx1+1−wx1+x2w_{x_1+1}-w_{x_1+x_2}wx1+1−wx1+x2 全部相等,…,wx1+...+xV−1−wx1+...+xVw_{x_1+...+x_{V-1}}-w_{x_1+...+x_V}wx1+...+xV−1−wx1+...+xV 全部相等。这里只是提供一点思路,主要想说明的是在设计 fif_ifi 是非常灵活的。
根据上面对 fi(x⃗,y)f_i(\vec x,\ y)fi(x,y) 的定义,可以算出这些东西:
Zw⃗(x⃗)=∑y=1,0exp{∑i=1Vwifi(x⃗,y)}=exp{∑i=1Vwixi}+exp{0}=1+exp(w⃗Tx⃗)Z_{\vec w}(\vec x)=\displaystyle\sum_{y=1,\ 0}exp\big\{\sum^V_{i=1}w_if_i(\vec x,\ y)\big\}=exp\big\{\sum^V_{i=1}w_ix_i\big\}+exp\{0\} = 1+exp(\vec w^T \vec x)Zw(x)=y=1,0∑exp{i=1∑Vwifi(x,y)}=exp{i=1∑Vwixi}+exp{0}=1+exp(wTx)
Pw⃗(y=1∣x⃗)=P_{\vec w}(y=1\ |\ \vec x)=Pw(y=1∣x)= exp(w⃗Tx⃗)1+exp(w⃗Tx⃗)=11+exp(−w⃗Tx⃗)\frac{exp(\vec w^T \vec x)}{1+exp(\vec w^T \vec x)}=\frac{1}{1+exp(-\vec w^T \vec x)}1+exp(wTx)exp(wTx)=1+exp(−wTx)1
Pw⃗(y=1∣x⃗)=P_{\vec w}(y=1\ |\ \vec x)=Pw(y=1∣x)= 11+exp(w⃗Tx⃗)\frac{1}{1+exp(\vec w^T \vec x)}1+exp(wTx)1
通过合理的设计特征函数,并代入最大熵模型的概率表达式后,我们得到了逻辑斯蒂回归的条件概率表达式。可以说,逻辑斯蒂模型就是一个最大熵模型!它符合最大熵的思想。
它们俩的关系大概是爸爸和儿子的关系,最大熵模型更加 general,因为它未规定特征函数的具体形式。
写在最后
① 从概率论角度,Logistic Regression 符合极大似然思想,意味着最优模型能使我们看到现有样本数据的概率最大。
② 从信息论角度,Logistic Regression 的优化过程等价于对交叉熵的最小化,意味着最优模型模拟的分布与真实分布的 K-L 散度最小。
③ 同时,Logistic Regression 满足最大熵思想,意味着它是在所有满足约束条件的模型集合中,不确定的部分分布最均匀的模型。 此处的约束是:P(Y∣X⃗)P(Y\ |\ \vec X)P(Y∣X) 服从 BernoulliBernoulliBernoulli 分布,其次, P(Y∣X⃗)P(Y\ |\ \vec X)P(Y∣X) 是 x⃗\vec xx 的线性函数,即 P(Y=y∣X⃗=x⃗)=f(w⃗Tx⃗)P(Y=y\ |\ \vec X=\vec x)=f(\vec w^T\vec x)P(Y=y∣X=x)=f(wTx)。满足这些约束之后使熵最大化推出的 fff 就是 sigmoid。
那么 ② 和 ③ 都是信息论的视角,为什么让一个熵最小一个熵最大呢?这块不要搞混哈。“找到满足约束条件的模型中熵最大的模型” 可以分解为两步:
Max Entropy 管的是那些约束条件约束不到的范围,让概率分布尽可能均匀。这一步就是对偶问题的第一步,确定了一般形式,但没确定具体参数。
Cross Entropy 管的是能约束到的范围。即在已知样本数据的分布后,让模拟的分布和数据中的分布越相近越好。这一步是对偶问题的第二步,用最大似然确定最优参数。
而我们在训练 Logistic Regression 的时候,是采用了最大熵模型的一般形式(采用对偶问题第一步的解),规定了 fif_ifi 的具体细节,并且用梯度下降等优化方法确定了具体参数的最优解(解决对偶问题的第二步,此处用 Logistic loss / Maximum Likelihood loss / Cross Entropy loss 都等价)。
哇,虽然这篇文章的主角一直是 Logistic Regression,自带甩不掉的主角光环,但原来最大熵模型才是最大的Boss!
啊 你终于看完了这篇 Toooo Loooooooong 的文章,撒个花吧!
本博客仅为作者记录学习笔记和心得之用,不免有细节不严谨之处,欢迎指正,不胜感激!如需转载,请附上本文链接:/weixin_43928665/article/details/106826264
Reference:
李航 《统计学习方法》(第2版)
Thomas M. Cover Joy A. Thomas 《Elements of Information Theory》(Second Edition)
Logistic Regression 的前世今生(理论篇)
逻辑回归与朴素贝叶斯的区别
逻辑回归(对数几率回归)和朴素贝叶斯分类器的对比
常见回归和分类损失函数比较
交叉熵损失函数原理详解
为什么 LR 模型要使用 sigmoid 函数,背后的数学原理是什么?
最大似然估计与交叉熵的关系
交叉熵(Cross-Entropy)与最大似然