【機(jī)器學(xué)習(xí)】（2）：梯度下降算法

    上一章中我們簡單介紹了機(jī)器學(xué)習(xí)的大概情況，今天我們開始循序漸進(jìn)地學(xué)習(xí)機(jī)器學(xué)習(xí)中相關(guān)的算法。在接觸經(jīng)典算法之前，我們先來了解下“梯度下降”算法。
一、算法背景
    作為一個算法演示的背景，我們還是采用上一章中提到的房屋價格和房屋大小的關(guān)系問題，不同大小的房屋對應(yīng)不同的房價，我們要通過分析已有的數(shù)據(jù)樣本，來預(yù) 測一個新樣本的房價。這里其實(shí)是監(jiān)督式學(xué)習(xí)中回歸問題的簡單應(yīng)用，如果所有的特性因變量都是一次的關(guān)系，那么就稱之為一個線性回歸問題。下面就是我們解決 問題的基本思路：

    首先從訓(xùn)練集中使用學(xué)習(xí)算法，得到一個關(guān)于問題的假設(shè)（實(shí)質(zhì)是H(X)=Y的映射），然后選取一個新的房屋，由其大小預(yù)測其價格。解決這個問題還需要規(guī)定一些符號便于后面的說明，如：
1. M：樣本集，表示所有的訓(xùn)練集；
2. X：輸入變量，也叫做feature，這個例子里就是房屋大??；
3. Y：輸出變量，也叫做targeted variable，這個例子里就是房屋價格；
4. (X,Y)：表示一個訓(xùn)練樣本實(shí)例；
5. 第i個樣本實(shí)例：；

二、梯度下降
    對于上面房屋價格和房屋大小的這個例子，如果我們僅僅考慮線性關(guān)系，那么Y應(yīng)當(dāng)都是X的線性關(guān)系。作為演示的例子，我們不妨設(shè)房屋大小、房間數(shù)量是房屋價 格的兩個線性因變量，那么我們的假設(shè)H(X)其實(shí)可以寫作關(guān)于X的函數(shù)，為了方便，我們將后面所用到的公式和結(jié)果一并寫在下面：

（1）式中表示的是當(dāng)考慮房屋大小和房間數(shù)量兩個因變量時的線性函數(shù)，其中X0的值為1，X1表示房屋大小，X2表示房間數(shù)量；
（2）式中的J函數(shù)，就是我們的目標(biāo)函數(shù)，即如果存在一個函數(shù)可以最好的擬合現(xiàn)有的訓(xùn)練數(shù)據(jù)集M，那么所有樣本在該函數(shù)上的方差一定最小，前面乘以1/2是為了后面運(yùn)算化簡的方便，不必細(xì)究；
（3）式就是我們所說的梯度下降算法的更新公式，將現(xiàn)有訓(xùn)練集的所有樣本考慮在內(nèi)，那么變量成為了兩個系數(shù)，因此我們不斷變化系數(shù)以尋求使得H函數(shù)達(dá)到最小值的值，這里的是一個常變量，表示的是每次下降的步長，如果該值過小，導(dǎo)致算法收斂時間太長，如果該值過大，則有可能會越過最小值點(diǎn)；
（4）式是僅僅考慮只有一個樣本的時候得到的關(guān)于梯度下降的公式；
（5）式是考慮有m個樣本的時候的梯度下降公式；
（6）式是隨機(jī)梯度下降公式；
    注意！梯度下降的思想其實(shí)很簡單，如果將所有的樣本值繪成等高線圖，那么好比一個人站在其中一點(diǎn)，每當(dāng)要邁步的時候都要考慮哪個方向邁一步可以最快下山。這里其選擇的最快下山方向其實(shí)是該點(diǎn)的偏導(dǎo)數(shù)。具體如圖：


    同理，我們也可以看等高線圖：

    從上面的（5）式中我們可以看出，每次更新一次系數(shù)的時候，都需要遍歷所有的樣本集合進(jìn)行運(yùn)算，因此稱為“批梯度算法”，但是如果遇到非常大的樣本集合， 這樣無疑是十分低效的。因此我們又有了“隨機(jī)梯度算法”，其思想就是每次只使用一個樣本來更新所有的參數(shù)值，但是需要更新m*n次（m是樣本大小，n是因 變量個數(shù)），偽代碼就是：
Repeat {
    For j = 1 to m {
        (6)式  (for all i)
    }
}
    隨機(jī)梯度算法的收斂速度要比批梯度要快，但是最后收斂的未必有批梯度那么準(zhǔn)確，也許會圍繞最小值點(diǎn)來回?cái)[動。由于梯度算法的核心是減去了偏導(dǎo)數(shù)，因此梯度算法一定會有收斂值，而且對于線性問題來說，所得的局部最小值往往就是全局最小值。