Logistic回歸與最大熵模型-理論推導(dǎo)

logistics與最大熵思維導(dǎo)圖.png

1. logistics 回歸模型

logistics模型

1.1 logistics模型構(gòu)建

對(duì)于數(shù)據(jù)集T=\{(x_1,y_1),...,(x_N,y_N)\}有
Logistics模型的基本思想也是線性回歸，其公式為：
\begin{align} h_w(x_i) =\frac{e^{w·x_i}} {1+e^{w·x_i}} \tag{1.1} \end{align}
公式(1.1)被稱為sigmoid函數(shù)，一般來(lái)說(shuō)，若h_w(x_i)>0.5則分類判定為1，否則為0。

1.2 估計(jì)參數(shù)\theta

設(shè)P(Y=1|x)=\pi(x)，P(Y=0|x)=1-\pi(x)，則似然函數(shù)為：
\begin{align} L(w) =&\prod_{i=1}^{N}[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i} \tag{1.2} \\ log L(w) =&\sum_{i=1}^{N}[y_i({w}·x_i) - log(1+exp({w}·x_i))] \tag{1.3} \end{align}
目標(biāo)是找到w使得L(w)達(dá)到最大值，一般使用梯度上升。

2. 最大熵模型

2.1 最大熵原理

首先要明確兩個(gè)問(wèn)題：

  • 熵最大有什么意義嗎？
    我們之前提過(guò)信息熵表示不確定程度，所以熵最大，也就是系統(tǒng)的不確定程度最大，系統(tǒng)中沒(méi)有任何個(gè)人的主觀假設(shè)。
  • 最大熵是什么？
    當(dāng)你要猜一個(gè)概率分布時(shí)，如果你對(duì)這個(gè)分布一無(wú)所知，那就猜熵最大的均勻分布，如果你對(duì)這個(gè)分布知道一些情況，那么，就猜滿足這些情況的熵最大的分布。

下面兩個(gè)網(wǎng)址是描述的比較清楚的：

2.2 最大熵模型

看完《機(jī)器學(xué)習(xí)面試之最大熵模型》之后，我的理解：

假設(shè)有一個(gè)樣本空間為N的數(shù)據(jù)集，共有m個(gè)特征，為\boldsymbol{x}=[x_1, x_2, ..., x_m]，類標(biāo)簽為\boldsymbol{y}=[y_1, y_2,..,y_k]，我們的目標(biāo)是求P(y|x)，那么，根據(jù)樣本空間中的N條數(shù)據(jù)，可以計(jì)算出\widetilde{P}(x)和\widetilde{P}(x,y)（因?yàn)槭歉鶕?jù)已知數(shù)據(jù)求出來(lái)的，并不能代表真實(shí)世界中的分布，所以上面加了波浪線），然后，定義了一個(gè)函數(shù)：

特征f是指x與y之間存在的某種特定的關(guān)系

“如果x,y滿足某種條件”，這句話一開始讓我摸不著頭腦，后來(lái)才明白，可以把它看成，x,y這種組合若出現(xiàn)在樣本空間中，則為1，否則為0。它們的個(gè)數(shù)為n個(gè)。

小資的AI課堂-最大熵模型

這樣的話，就可以算f(x,y)的期望了：

  • 特征函數(shù)f(x,y)關(guān)于\widetilde{P}(x,y)的期望值為：
    E_{\widetilde{P}}(f)=\sum_{x,y} \widetilde{P}(x,y)f(x,y) \tag{2.1}
    由于我們的目標(biāo)是求P(y|x)，那么，借助貝葉斯公式，我們可以得出第二個(gè)期望的計(jì)算公式：
    E_{P}(f)=\sum_{x,y} \widetilde{P}(x)P(y|x)f(x,y) \tag{2.2}

如果，這倆公式能相等的話，就十分完美了（注意，這里要把\sum_{x,y} \widetilde{P}(x,y)f(x,y)看成是\sum_{x,y} \widetilde{P}(x)P(y|x)f(x,y)的約束條件），于是有：
\sum_{x,y} \widetilde{P}(x,y)f(x,y)=\sum_{x,y} \widetilde{P}(x)P(y|x)f(x,y) \tag{2.3}

根據(jù)f(x,y)的定義可知，有多少種特征和類標(biāo)簽前的組合，就有多少個(gè)約束條件:f(x,y)。那么，把樣本空間中的所有約束條件都算上，

又因?yàn)?，條件熵為：（為什么請(qǐng)看這里：《決策樹【python實(shí)現(xiàn)】》— 條件熵）
H(P) = -\sum_{x,y} \widetilde{P}(x)P(y|x)logP(y|x) \tag{2.4}

那么，也就是說(shuō)，我們要在這個(gè)空間中找一個(gè)“沒(méi)有任何主觀假設(shè)的模型”，即條件概率的最大熵。

2.3 最大熵模型的目標(biāo)函數(shù)

找出了約束最優(yōu)化問(wèn)題， 下面來(lái)求解一下。

1. 把求max的問(wèn)題轉(zhuǎn)化成求min的問(wèn)題。要求

\underset{p \in C}{max}\ H(P) = -\sum_{x,y} \widetilde{P}(x)P(y|x)logP(y|x)
等價(jià)于求
\underset{p \in C}{min}\ -H(P) = \sum_{x,y} \widetilde{P}(x)P(y|x)logP(y|x)\tag{2.5}
引入拉格朗日算子w_1,w_2,...,w_n，可得到方程：
\begin{align} L(P, w) &= -H(P) + w_0(1-\sum_{y}P(y|x)) + \sum_{i=1}^{n}[w_i (E_P(f_i(x,y))-E_{ \widetilde{P}}(f_i(x,y)))] \tag{2.6}\\ &= \sum_{x,y} \widetilde{P}(x)P(y|x)logP(y|x) + w_0[1-\sum_{y}P(y|x)] + \sum_{i=1}^{n} \{ w_i [\sum_{x,y }P(x,y)f_i(x,y) - \sum_{x,y }\widetilde{P}(x)P(y|x)f_i(x,y)] \}\tag{2.7} \end{align}

2. 由最優(yōu)化問(wèn)題可知，我們的目標(biāo)是求：

\begin{align} \underset{p \in C}{min}\ \underset{w}{max}\ L(P,w)\tag{2.8-1} \end{align}

對(duì)偶問(wèn)題

\begin{align} \underset{w}{max}\ \underset{p \in C}{min}\ L(P,w)\tag{2.8-2} \end{align}

基本思想是：先把\underset{p \in C}{min}\ L(P,w)的解用w表示出來(lái)，然后再求w的解即可。

a.先求\underset{p \in C}{min}\ L(P,w)：

當(dāng)L(P,w)滿足約束條件時(shí)，令
\psi(w) = \underset{p \in C}{min}\ L(P,w) = L(P_w,w) \tag{2.9}
設(shè)\psi(w)的解為P_w(y|x)，求L(P,w)對(duì)P(y|x)的偏導(dǎo)數(shù)，并令其為0：
\begin{align} \frac{\partial {L(P, w)}}{\partial{p(y|x)}} &= \sum_{x,y} \{ \widetilde{P}(x)logP(y|x) + \widetilde{P}(x)\} - \sum_{y}w_0 + \sum_{i=1}^{n} \{ w_i [0 - \sum_{x,y }\widetilde{P}(x)f_i(x,y) ] \} \\ &= \sum_{x,y}\widetilde{P}(x) ( logP(y|x) + 1) - \sum_{x,y}\widetilde{P}(x)w_0 - \sum_{i=1}^{n} \{ w_i \sum_{x,y }\widetilde{P}(x)f_i(x,y) \} \\ &= \sum_{x,y}\widetilde{P}(x) ( logP(y|x) + 1) - \sum_{x,y}\widetilde{P}(x)w_0 - \sum_{i=1}^{n} \{ w_i \sum_{x,y }\widetilde{P}(x)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) \}\tag{2.10} \end{align}
令式(2.10)為0，則有：
\begin{align} 0 =& \sum_{x,y}\widetilde{P}(x) \{( logP(y|x) + 1) - w_0 - \sum_{i=1}^{n} w_i f_i(x,y)\} \\ p(y|x) =& exp ( w_0 + \sum_{i=1}^{n} w_i f_i(x,y)-1 ) \\ p(y|x) =& \frac{exp (\sum_{i=1}^{n} w_i f_i(x,y))} {exp ( w_0 -1) }\tag{2.11} \end{align}
又因\sum_{y}p(y|x)=1，代入公式(2.11)，則有：
\begin{align} 1 =& \sum_{y} \frac{exp (\sum_{i=1}^{n} w_i f_i(x,y))} {exp ( w_0 -1) } \\ exp ( w_0 -1) =& \sum_{y} exp (\sum_{i=1}^{n} w_i f_i(x,y))\tag{2.12} \end{align}
令(2.12)為Z_w(x)，代入(2.11)，結(jié)果記為p_w(y|x)，則有
\begin{align} p_w(y|x) =& \frac{exp (\sum_{i=1}^{n} w_i f_i(x,y))} {\sum_{y} exp (\sum_{i=1}^{n} w_i f_i(x,y))}\tag{2.13} \end{align}
因此，優(yōu)化目標(biāo)\psi(x)的解為公式(2.13)，其中Z_w(x)被稱為規(guī)范化因子。

b. 再使(2.13)極大化，求w

即求
\begin{align} \underset{w}{max}\ \psi(w) \tag{2.14} \end{align}
在公式(2.6)中，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=p_w(y%7Cx)" alt="p_w(y|x)" mathimg="1">是在\sum_y p(y|x)=1的條件下得出，故而有：
\begin{align} L(P_w, w) &= -H(P_w) + \sum_{i=1}^{n} [w_i (E_{\widetilde{P}} (f_i(x,y)) - E_{P_w}(f_i(x,y)))] \\ &=\sum_{x,y} \widetilde{P}(x) P_w(y|x) log P_w(y|x) + \sum_{i=1}^{n} w_i (E_\widetilde{P} (f_i(x,y)) - \sum_{x,y}\widetilde{P}(x)·P_w(y|x)·f_i(x,y)) \\ &= \sum_{i=1}^{n}w_i ·E_{\widetilde{P}}(f_i(x,y)) + \sum_{x,y} \widetilde{P}(x) P_w(y|x)·(log P_w(y|x) - \sum_{i=1}^{n} w_if_i(x,y)) \tag{2.15} \end{align}

將
\begin{align} P_w(y|x) =& \frac{exp (\sum_{i=1}^{n} w_i f_i(x,y))} {\sum_{y} exp (\sum_{i=1}^{n} w_i f_i(x,y))}\tag{2.13} \end{align}
代入公式(2.15)，得
\begin{align} L(P_w, w) &= \sum_{i=1}^{n}w_i ·E_{\widetilde{P}}(f_i(x,y)) + \sum_{x,y} \widetilde{P}(x) P_w(y|x)·(\sum_{i=1}^{n} w_i f_i(x,y)-logP_w(x) - \sum_{i=1}^{n} w_if_i(x,y)) \\ &= \sum_{i=1}^{n}w_i ·E_{\widetilde{P}}(f_i(x,y)) - logZ_w(x) · \sum_{x,y} \widetilde{P}(x) P_w(y|x) \tag{2.16} \\ &=\sum_{i=1}^{n}w_i ·E_{\widetilde{P}}(f_i(x,y)) - logZ_w(x) ·( \sum_{x}\sum_{y} \widetilde{P}(x) P_w(y|x)) \\ &=\sum_{i=1}^{n}w_i ·E_{\widetilde{P}}(f_i(x,y)) - logZ_w(x) ·( \sum_{x}\widetilde{P}(x))\\ &=\sum_{i=1}^{n}w_i ·\sum_{x,y} \widetilde{P}(x,y)f_i(x,y) - logZ_w(x) ·( \sum_{x}\widetilde{P}(x))\tag{2.17} \end{align}
由于(2.13)式并沒(méi)有一個(gè)顯式的解析解，因此需要借助于數(shù)值的方法。由于是一個(gè)光滑的凸函數(shù)，所以可以求解的方法很多?？梢允褂玫姆椒ㄓ校?/p>

  1. 通用迭代尺度法（GIS: Generalized Iterative Scaling）。
  2. 改進(jìn)的迭代尺度法（IIS: Improved Iterative Scaling）。
  3. 梯度下降算法
  4. 擬牛頓法（牛頓法）

其中，前兩個(gè)方法是專門為最大熵模型而設(shè)計(jì)的，后兩種方法為通用的算法。

3. 靈魂兩問(wèn)

3.1 為什么對(duì)偶函數(shù)的極大化 = 最大熵模型的似然估計(jì)

3.1.1 對(duì)偶函數(shù)極大化

如果不好理解，可以將\psi(w)看成是關(guān)于w的函數(shù)。

3.1.1 最大熵模型的似然估計(jì)

\begin{align} L_{\widetilde{P}}(P_w) &= \sum_{x,y} \widetilde{P}(x,y)logP(y|x) \\ &=\sum_{x,y} \widetilde{P}(x,y)·(\sum_{i=1}^{n}w_i f_i(x,y)-logZ_w(x)) \\ &= \sum_{x,y} \widetilde{P}(x,y)·\sum_{i=1}^{n}w_i f_i(x,y) - logZ_w(x) · \sum_{x,y} \widetilde{P}(x) P_w(y|x) \tag{3.1} \end{align}
因?yàn)楣?2.1)
E_{\widetilde{P}}(f)=\sum_{x,y} \widetilde{P}(x,y)f(x,y) \tag{2.1}
所以公式(3.1)=(2.16)。故而，對(duì)偶函數(shù)的極大化 = 最大熵模型的似然估計(jì)。

3.2 logistics模型和最大熵模型，有什么關(guān)系？

3.2.1 logistics模型
二分類模型

\begin{align} P(Y=1|x)=\frac{exp(w·x)}{1+exp(w·x)} \\ P(Y=0|x)=\frac{1}{1+exp(w·x)} \end{align}

多分類模型

\begin{align} P(Y=i|x)=&\frac{exp(w_i·x)}{1+\sum_{i=1}^{n-1}exp(w_i·x)},\ i=1,2,3...,n-1\\ P(Y=i|x)=&\frac{1}{1+\sum_{i=1}^{n-1}exp(w_i·x)} \end{align}

logistics模型的通用表達(dá)式

\begin{align} P(y|x)=\frac{exp(w_i·x)} {\sum_{i=1}^{n}exp(w_i·x)}, i=1,2,3...,n;w_1=0 \end{align}

3.2.2 最大熵模型

\begin{align} p_w(y|x) =& \frac{exp (\sum_{i=1}^{n} w_i f_i(x,y))} {\sum_{y} exp (\sum_{i=1}^{n} w_i f_i(x,y))}\tag{2.13} \end{align}
當(dāng)類標(biāo)簽只有兩個(gè)的時(shí)候，最大熵模型就是logistics回歸模型。具體原因

小資的AI課堂-最大熵模型

4. 參考文獻(xiàn)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容