邏輯回歸（Logistic Regression）

這節(jié)學(xué)習(xí)的是邏輯回歸（Logistic Regression），也算進(jìn)入了比較正統(tǒng)的機(jī)器學(xué)習(xí)算法。啥叫正統(tǒng)呢？我概念里面機(jī)器學(xué)習(xí)算法一般是這樣一個(gè)步驟：

1）對于一個(gè)問題，我們用數(shù)學(xué)語言來描述它，然后建立一個(gè)模型，例如回歸模型或者分類模型等來描述這個(gè)問題；

2）通過最大似然、最大后驗(yàn)概率或者最小化分類誤差等等建立模型的代價(jià)函數(shù)，也就是一個(gè)最優(yōu)化問題。找到最優(yōu)化問題的解，也就是能擬合我們的數(shù)據(jù)的最好的模型參數(shù)；

3）然后我們需要求解這個(gè)代價(jià)函數(shù)，找到最優(yōu)解。這求解也就分很多種情況了：

      a）如果這個(gè)優(yōu)化函數(shù)存在解析解。例如我們求最值一般是對代價(jià)函數(shù)求導(dǎo)，找到導(dǎo)數(shù)為0的點(diǎn)，也就是最大值或者最小值的地方了。如果代價(jià)函數(shù)能簡單求導(dǎo)，并且求導(dǎo)后為0的式子存在解析解，那么我們就可以直接得到最優(yōu)的參數(shù)了。

      b）如果式子很難求導(dǎo)，例如函數(shù)里面存在隱含的變量或者變量相互間存在耦合，也就互相依賴的情況。或者求導(dǎo)后式子得不到解釋解，例如未知參數(shù)的個(gè)數(shù)大于已知方程組的個(gè)數(shù)等。這時(shí)候我們就需要借助迭代算法來一步一步找到最有解了。迭代是個(gè)很神奇的東西，它將遠(yuǎn)大的目標(biāo)（也就是找到最優(yōu)的解，例如爬上山頂）記在心上，然后給自己定個(gè)短期目標(biāo)（也就是每走一步，就離遠(yuǎn)大的目標(biāo)更近一點(diǎn)），腳踏實(shí)地，心無旁貸，像個(gè)蝸牛一樣，一步一步往上爬，支撐它的唯一信念是：只要我每一步都爬高一點(diǎn)，那么積跬步，肯定能達(dá)到自己人生的巔峰，盡享山登絕頂我為峰的豪邁與忘我。

       另外需要考慮的情況是，如果代價(jià)函數(shù)是凸函數(shù)，那么就存在全局最優(yōu)解，方圓五百里就只有一個(gè)山峰，那命中注定了，它就是你要找的唯一了。但如果是非凸的，那么就會(huì)有很多局部最優(yōu)的解，有一望無際的山峰，人的視野是偉大的也是渺小的，你不知道哪個(gè)山峰才是最高的，可能你會(huì)被命運(yùn)作弄，很無辜的陷入一個(gè)局部最優(yōu)里面，坐井觀天，以為自己找到的就是最好的。沒想到山外有山，人外有人，光芒總在未知的遠(yuǎn)處默默綻放。但也許命運(yùn)眷戀善良的你，帶給你的總是最好的歸宿。也有很多不信命的人，覺得人定勝天的人，誓要找到最好的，否則不會(huì)罷休，永不向命運(yùn)妥協(xié)，除非自己有一天累了，倒下了，也要靠剩下的一口氣，邁出一口氣能支撐的路程。好悲涼啊……哈哈。

        呃，不知道扯那去了，也不知道自己說的有沒有錯(cuò)，有錯(cuò)的話請大家不吝指正。那下面就進(jìn)入正題吧。正如上面所述，邏輯回歸就是這樣的一個(gè)過程：面對一個(gè)回歸或者分類問題，建立代價(jià)函數(shù)，然后通過優(yōu)化方法迭代求解出最優(yōu)的模型參數(shù)，然后測試驗(yàn)證我們這個(gè)求解的模型的好壞，冥冥人海，滾滾紅塵，我們是否找到了最適合的那個(gè)她。

一、邏輯回歸（LogisticRegression）

       Logistic regression （邏輯回歸）是當(dāng)前業(yè)界比較常用的機(jī)器學(xué)習(xí)方法，用于估計(jì)某種事物的可能性。之前在經(jīng)典之作《數(shù)學(xué)之美》中也看到了它用于廣告預(yù)測，也就是根據(jù)某廣告被用戶點(diǎn)擊的可能性，把最可能被用戶點(diǎn)擊的廣告擺在用戶能看到的地方，然后叫他“你點(diǎn)我??！”用戶點(diǎn)了，你就有錢收了。這就是為什么我們的電腦現(xiàn)在廣告泛濫的原因了。

       還有類似的某用戶購買某商品的可能性，某病人患有某種疾病的可能性啊等等。這個(gè)世界是隨機(jī)的（當(dāng)然了，人為的確定性系統(tǒng)除外，但也有可能有噪聲或產(chǎn)生錯(cuò)誤的結(jié)果，只是這個(gè)錯(cuò)誤發(fā)生的可能性太小了，小到千萬年不遇，小到忽略不計(jì)而已），所以萬物的發(fā)生都可以用可能性或者幾率（Odds）來表達(dá)?！皫茁省敝傅氖悄呈挛锇l(fā)生的可能性與不發(fā)生的可能性的比值。

       Logistic regression可以用來回歸，也可以用來分類，主要是二分類。還記得上幾節(jié)講的支持向量機(jī)SVM嗎？它就是個(gè)二分類的例如，它可以將兩個(gè)不同類別的樣本給分開，思想是找到最能區(qū)分它們的那個(gè)分類超平面。但當(dāng)你給一個(gè)新的樣本給它，它能夠給你的只有一個(gè)答案，你這個(gè)樣本是正類還是負(fù)類。例如你問SVM，某個(gè)女生是否喜歡你，它只會(huì)回答你喜歡或者不喜歡。這對我們來說，顯得太粗魯了，要不希望，要不絕望，這都不利于身心健康。那如果它可以告訴我，她很喜歡、有一點(diǎn)喜歡、不怎么喜歡或者一點(diǎn)都不喜歡，你想都不用想了等等，告訴你她有49%的幾率喜歡你，總比直接說她不喜歡你，來得溫柔。而且還提供了額外的信息，她來到你的身邊你有多少希望，你得再努力多少倍，知己知彼百戰(zhàn)百勝，哈哈。Logistic regression就是這么溫柔的，它給我們提供的就是你的這個(gè)樣本屬于正類的可能性是多少。

       還得來點(diǎn)數(shù)學(xué)。（更多的理解，請參閱參考文獻(xiàn)）假設(shè)我們的樣本是{x, y}，y是0或者1，表示正類或者負(fù)類，x是我們的m維的樣本特征向量。那么這個(gè)樣本x屬于正類，也就是y=1的“概率”可以通過下面的邏輯函數(shù)來表示：

       這里θ是模型參數(shù)，也就是回歸系數(shù)，σ是sigmoid函數(shù)。實(shí)際上這個(gè)函數(shù)是由下面的對數(shù)幾率（也就是x屬于正類的可能性和負(fù)類的可能性的比值的對數(shù)）變換得到的：

       換句話說，y也就是我們關(guān)系的變量，例如她喜不喜歡你，與多個(gè)自變量（因素）有關(guān)，例如你人品怎樣、車子是兩個(gè)輪的還是四個(gè)輪的、長得勝過潘安還是和犀利哥有得一拼、有千尺豪宅還是三寸茅廬等等，我們把這些因素表示為x₁, x₂,…, x_m。那這個(gè)女的怎樣考量這些因素呢？最快的方式就是把這些因素的得分都加起來，最后得到的和越大，就表示越喜歡。但每個(gè)人心里其實(shí)都有一桿稱，每個(gè)人考慮的因素不同，蘿卜青菜，各有所愛嘛。例如這個(gè)女生更看中你的人品，人品的權(quán)值是0.6，不看重你有沒有錢，沒錢了一起努力奮斗，那么有沒有錢的權(quán)值是0.001等等。我們將這些對應(yīng)x₁, x₂,…, x_m的權(quán)值叫做回歸系數(shù)，表達(dá)為θ₁, θ₂,…, θ_m。他們的加權(quán)和就是你的總得分了。請選擇你的心儀男生，非誠勿擾！哈哈。

       所以說上面的logistic回歸就是一個(gè)線性分類模型，它與線性回歸的不同點(diǎn)在于：為了將線性回歸輸出的很大范圍的數(shù)，例如從負(fù)無窮到正無窮，壓縮到0和1之間，這樣的輸出值表達(dá)為“可能性”才能說服廣大民眾。當(dāng)然了，把大值壓縮到這個(gè)范圍還有個(gè)很好的好處，就是可以消除特別冒尖的變量的影響（不知道理解的是否正確）。而實(shí)現(xiàn)這個(gè)偉大的功能其實(shí)就只需要平凡一舉，也就是在輸出加一個(gè)logistic函數(shù)。另外，對于二分類來說，可以簡單的認(rèn)為：如果樣本x屬于正類的概率大于0.5，那么就判定它是正類，否則就是負(fù)類。實(shí)際上，SVM的類概率就是樣本到邊界的距離，這個(gè)活實(shí)際上就讓logistic regression給干了。

       所以說，LogisticRegression 就是一個(gè)被logistic方程歸一化后的線性回歸，僅此而已。

好了，關(guān)于LR的八卦就聊到這。歸入到正統(tǒng)的機(jī)器學(xué)習(xí)框架下，模型選好了，只是模型的參數(shù)θ還是未知的，我們需要用我們收集到的數(shù)據(jù)來訓(xùn)練求解得到它。那我們下一步要做的事情就是建立代價(jià)函數(shù)了。

       LogisticRegression最基本的學(xué)習(xí)算法是最大似然。啥叫最大似然，可以看看我的另一篇博文“從最大似然到EM算法淺解”。

       假設(shè)我們有n個(gè)獨(dú)立的訓(xùn)練樣本{(x₁, y₁) ,(x₂, y₂),…, (x_n, y_n)}，y={0, 1}。那每一個(gè)觀察到的樣本(x_i, y_i)出現(xiàn)的概率是：

       上面為什么是這樣呢？當(dāng)y=1的時(shí)候，后面那一項(xiàng)是不是沒有了，那就只剩下x屬于1類的概率，當(dāng)y=0的時(shí)候，第一項(xiàng)是不是沒有了，那就只剩下后面那個(gè)x屬于0的概率（1減去x屬于1的概率）。所以不管y是0還是1，上面得到的數(shù)，都是(x, y)出現(xiàn)的概率。那我們的整個(gè)樣本集，也就是n個(gè)獨(dú)立的樣本出現(xiàn)的似然函數(shù)為（因?yàn)槊總€(gè)樣本都是獨(dú)立的，所以n個(gè)樣本出現(xiàn)的概率就是他們各自出現(xiàn)的概率相乘）：

       那最大似然法就是求模型中使得似然函數(shù)最大的系數(shù)取值θ*。這個(gè)最大似然就是我們的代價(jià)函數(shù)（cost function）了。

       OK，那代價(jià)函數(shù)有了，我們下一步要做的就是優(yōu)化求解了。我們先嘗試對上面的代價(jià)函數(shù)求導(dǎo)，看導(dǎo)數(shù)為0的時(shí)候可不可以解出來，也就是有沒有解析解，有這個(gè)解的時(shí)候，就皆大歡喜了，一步到位。如果沒有就需要通過迭代了，耗時(shí)耗力。

       我們先變換下L(θ)：取自然對數(shù)，然后化簡（不要看到一堆公式就害怕哦，很簡單的哦，只需要耐心一點(diǎn)點(diǎn)，自己動(dòng)手推推就知道了。注：有x_i的時(shí)候，表示它是第i個(gè)樣本，下面沒有做區(qū)分了，相信你的眼睛是雪亮的），得到：

       這時(shí)候，用L(θ)對θ求導(dǎo)，得到：

       然后我們令該導(dǎo)數(shù)為0，你會(huì)很失望的發(fā)現(xiàn)，它無法解析求解。不信你就去嘗試一下。所以沒辦法了，只能借助高大上的迭代來搞定了。這里選用了經(jīng)典的梯度下降算法。

二、優(yōu)化求解

2.1、梯度下降(gradient descent)

        Gradient descent 又叫 steepest descent，是利用一階的梯度信息找到函數(shù)局部最優(yōu)解的一種方法，也是機(jī)器學(xué)習(xí)里面最簡單最常用的一種優(yōu)化方法。它的思想很簡單，和我開篇說的那樣，要找最小值，我只需要每一步都往下走（也就是每一步都可以讓代價(jià)函數(shù)小一點(diǎn)），然后不斷的走，那肯定能走到最小值的地方，例如下圖所示：

      但，我同時(shí)也需要更快的到達(dá)最小值啊，怎么辦呢？我們需要每一步都找下坡最快的地方，也就是每一步我走某個(gè)方向，都比走其他方法，要離最小值更近。而這個(gè)下坡最快的方向，就是梯度的負(fù)方向了。

對logistic Regression來說，梯度下降算法新鮮出爐，如下：

      其中，參數(shù)α叫學(xué)習(xí)率，就是每一步走多遠(yuǎn)，這個(gè)參數(shù)蠻關(guān)鍵的。如果設(shè)置的太多，那么很容易就在最優(yōu)值附加徘徊，因?yàn)槟悴椒ヌ罅恕＠缫獜膹V州到上海，但是你的一步的距離就是廣州到北京那么遠(yuǎn)，沒有半步的說法，自己能邁那么大步，是幸運(yùn)呢？還是不幸呢？事物總有兩面性嘛，它帶來的好處是能很快的從遠(yuǎn)離最優(yōu)值的地方回到最優(yōu)值附近，只是在最優(yōu)值附近的時(shí)候，它有心無力了。但如果設(shè)置的太小，那收斂速度就太慢了，向蝸牛一樣，雖然會(huì)落在最優(yōu)的點(diǎn)，但是這速度如果是猴年馬月，我們也沒這耐心啊。所以有的改進(jìn)就是在這個(gè)學(xué)習(xí)率這個(gè)地方下刀子的。我開始迭代是，學(xué)習(xí)率大，慢慢的接近最優(yōu)值的時(shí)候，我的學(xué)習(xí)率變小就可以了。所謂采兩者之精華啊！這個(gè)優(yōu)化具體見2.3 。

       梯度下降算法的偽代碼如下：

################################################

初始化回歸系數(shù)為1

重復(fù)下面步驟直到收斂{

        計(jì)算整個(gè)數(shù)據(jù)集的梯度

        使用alpha x gradient來更新回歸系數(shù)

}

返回回歸系數(shù)值

################################################

      注：因?yàn)楸疚闹惺乔蠼獾腖ogit回歸的代價(jià)函數(shù)是似然函數(shù)，需要最大化似然函數(shù)。所以我們要用的是梯度上升算法。但因?yàn)槠浜吞荻认陆档脑硎且粯拥?，只是一個(gè)是找最大值，一個(gè)是找最小值。找最大值的方向就是梯度的方向，最小值的方向就是梯度的負(fù)方向。不影響我們的說明，所以當(dāng)時(shí)自己就忘了改過來了，謝謝評論下面@wxltt的指出。另外，最大似然可以通過取負(fù)對數(shù)，轉(zhuǎn)化為求最小值。代碼里面的注釋也是有誤的，寫的代碼是梯度上升，注銷成了梯度下降，對大家造成的不便，希望大家海涵。

2.2、隨機(jī)梯度下降SGD (stochastic gradient descent)

      梯度下降算法在每次更新回歸系數(shù)的時(shí)候都需要遍歷整個(gè)數(shù)據(jù)集（計(jì)算整個(gè)數(shù)據(jù)集的回歸誤差），該方法對小數(shù)據(jù)集尚可。但當(dāng)遇到有數(shù)十億樣本和成千上萬的特征時(shí)，就有點(diǎn)力不從心了，它的計(jì)算復(fù)雜度太高。改進(jìn)的方法是一次僅用一個(gè)樣本點(diǎn)（的回歸誤差）來更新回歸系數(shù)。這個(gè)方法叫隨機(jī)梯度下降算法。由于可以在新的樣本到來的時(shí)候?qū)Ψ诸惼鬟M(jìn)行增量的更新（假設(shè)我們已經(jīng)在數(shù)據(jù)庫A上訓(xùn)練好一個(gè)分類器h了，那新來一個(gè)樣本x。對非增量學(xué)習(xí)算法來說，我們需要把x和數(shù)據(jù)庫A混在一起，組成新的數(shù)據(jù)庫B，再重新訓(xùn)練新的分類器。但對增量學(xué)習(xí)算法，我們只需要用新樣本x來更新已有分類器h的參數(shù)即可），所以它屬于在線學(xué)習(xí)算法。與在線學(xué)習(xí)相對應(yīng)，一次處理整個(gè)數(shù)據(jù)集的叫“批處理”。

        隨機(jī)梯度下降算法的偽代碼如下：

################################################

初始化回歸系數(shù)為1

重復(fù)下面步驟直到收斂{

        對數(shù)據(jù)集中每個(gè)樣本

               計(jì)算該樣本的梯度

                使用alpha xgradient來更新回歸系數(shù)

 }

返回回歸系數(shù)值

################################################

2.3、改進(jìn)的隨機(jī)梯度下降

      評價(jià)一個(gè)優(yōu)化算法的優(yōu)劣主要是看它是否收斂，也就是說參數(shù)是否達(dá)到穩(wěn)定值，是否還會(huì)不斷的變化？收斂速度是否快？

       上圖展示了隨機(jī)梯度下降算法在200次迭代中（請先看第三和第四節(jié)再回來看這里。我們的數(shù)據(jù)庫有100個(gè)二維樣本，每個(gè)樣本都對系數(shù)調(diào)整一次，所以共有200*100=20000次調(diào)整）三個(gè)回歸系數(shù)的變化過程。其中系數(shù)X2經(jīng)過50次迭代就達(dá)到了穩(wěn)定值。但系數(shù)X1和X0到100次迭代后穩(wěn)定。而且可恨的是系數(shù)X1和X2還在很調(diào)皮的周期波動(dòng)，迭代次數(shù)很大了，心還停不下來。產(chǎn)生這個(gè)現(xiàn)象的原因是存在一些無法正確分類的樣本點(diǎn)，也就是我們的數(shù)據(jù)集并非線性可分，但我們的logistic regression是線性分類模型，對非線性可分情況無能為力。然而我們的優(yōu)化程序并沒能意識到這些不正常的樣本點(diǎn)，還一視同仁的對待，調(diào)整系數(shù)去減少對這些樣本的分類誤差，從而導(dǎo)致了在每次迭代時(shí)引發(fā)系數(shù)的劇烈改變。對我們來說，我們期待算法能避免來回波動(dòng)，從而快速穩(wěn)定和收斂到某個(gè)值。

       對隨機(jī)梯度下降算法，我們做兩處改進(jìn)來避免上述的波動(dòng)問題：

1）在每次迭代時(shí)，調(diào)整更新步長alpha的值。隨著迭代的進(jìn)行，alpha越來越小，這會(huì)緩解系數(shù)的高頻波動(dòng)（也就是每次迭代系數(shù)改變得太大，跳的跨度太大）。當(dāng)然了，為了避免alpha隨著迭代不斷減小到接近于0（這時(shí)候，系數(shù)幾乎沒有調(diào)整，那么迭代也沒有意義了），我們約束alpha一定大于一個(gè)稍微大點(diǎn)的常數(shù)項(xiàng)，具體見代碼。

2）每次迭代，改變樣本的優(yōu)化順序。也就是隨機(jī)選擇樣本來更新回歸系數(shù)。這樣做可以減少周期性的波動(dòng)，因?yàn)闃颖卷樞虻母淖儯沟妹看蔚辉傩纬芍芷谛浴?/span>

       改進(jìn)的隨機(jī)梯度下降算法的偽代碼如下：

################################################

初始化回歸系數(shù)為1

重復(fù)下面步驟直到收斂{

       對隨機(jī)遍歷的數(shù)據(jù)集中的每個(gè)樣本

              隨著迭代的逐漸進(jìn)行，減小alpha的值

              計(jì)算該樣本的梯度

              使用alpha x gradient來更新回歸系數(shù)

    }

返回回歸系數(shù)值

################################################

       比較原始的隨機(jī)梯度下降和改進(jìn)后的梯度下降，可以看到兩點(diǎn)不同：

1）系數(shù)不再出現(xiàn)周期性波動(dòng)。2）系數(shù)可以很快的穩(wěn)定下來，也就是快速收斂。這里只迭代了20次就收斂了。而上面的隨機(jī)梯度下降需要迭代200次才能穩(wěn)定。