在前面的時間，我學習了Logistic回歸，這是用來進行二分類學習的一種算法。雖然按照書上的介紹，編寫了算法實作代碼，但對其原理并不清楚，總感覺沒有了解透。于是我又找到吳恩達的Marchine Learning課程，再次學習了線性回歸和Logistic回歸。
Machine Leanring這門課程是先從線性回歸講起，然後再介紹的Logistic回歸，個人感覺這樣的次序更容易了解。《機器學習實戰》這本書也有線性回歸的内容，不過放在比較後面的第8章，而且書中給出的解法是直接求解法，并沒有采用梯度下降算法。
線性回歸
在[機器學習實戰劄記] Logistic回歸中，我們了解到回歸的定義，其目的是預測數值型的目标值，最直接的方法是依據輸入寫出一個目标值的計算公式。比如：
HorsePower = 0.0015 * annualSalary - 0.99 * hoursListeningToPublicRadio 複制
這就是所謂的回歸方程(regression equation)，其中的0.0015和-0.99稱作回歸系數(regression weights)，求這些回歸系統的過程就是回歸。一旦有了這些回歸系統，再給定輸入，做預測就非常容易。
回歸中使用得最多的就是線性回歸，而非線性回歸問題也可以經過變化，簡化為線性回歸問題。比如有如下圖所示的資料集：
可以通過引入高階多項式：
這樣問題仍然變成如何求解回歸系數的問題。
如何求解這些回歸系統呢？這裡就需要了解代價函數(Cost Function)的概念。
代價函數
直覺上，我們判斷一個拟合函數的好壞，就是看我們的實際值離拟合直線是近還是遠，理想的情況下，資料點都在拟合直線上，但現實中往往并沒有這樣一條拟合直線，如下圖所示：
那如何評價資料點離拟合直線的遠近呢？最常使用的就是方差距離，這個應該不陌生，在k-近鄰算法中就是使用了該公式來表示資料點之間的距離。
因為訓練資料集有多個資料點，是以使用均值作為最終的評估資料，這就是為什麼要引入代價函數的原因。
該圖簡化了模型，隻考慮單輸入變量，是以隻需要θ0, θ1兩個回歸參數。
理想的情況下，J的函數值為0。現在的問題是，如何取θ0, θ1值，使得J(θ)最小。
在Cost Funciton - Intuition部分，講解了如何推導θ0, θ1，其方法依然是逐漸簡化，比如先固定θ0, 分别取不同的值，然後畫出假設函數和Cost Function函數，下一步固定θ0, θ1，分别取不同的值：
右面曲線的含義是，選取任何顔色并沿着“圓”走，會獲得相同的成本函數值。例如，上面綠線上的三個綠色點對于J(θ0，θ1)具有相同的值。越往曲線的中心，J(θ0，θ1)值越小，是以曲線中心對應的θ0，θ1就是我們要找到的回歸系統。
梯度遞減算法
在x軸上放置θ0，在y軸上放置θ1，在垂直z軸上放置代價函數，那麼圖上的點将是使用我們的假設與那些特定theta參數的成本函數的結果，如下面的圖表所示：
很明顯，如果我們找到圖中的“坑底”，我們就已經成功了，圖中紅色箭頭顯示圖表中的最小點。現在的問題是如何找到這個“坑底”呢？其實看到這個圖，你是否會聯想到一座山，如何到達山谷，隻要我們沿着下坡走，就可以到達山谷，至于起點在哪，并不重要。如何最快達到山谷？當然是沿着最陡的坡度下山。梯度遞減算法的原理和下山的原理一樣：
- 任意選擇一個θ0, θ1
- 根據梯度下降原則更新θ0, θ1，直到代價函數值達到最小
在上圖中，存在多個“坑底”，也就是存在多個局部最優解，按照梯度遞減算法，得到局部最優解，可能并不是全局最優解。不過對于我們的線性回歸代價函數而言，不存在多個局部最優解，隻有一個全局最優解，這就是所謂凸函數的概念。
梯度下降算法是，重複以下計算，直到收斂：
需要注意的是，每次疊代，θ0, θ1需要同步更新，也就是說在一次疊代過程中，不能使用新計算出的的θ0值來更新θ1。
看到這個算式是不是有點懵，在高數中一定學過偏導數這個概念，大多數人可能忘了，沒關系。如果我們固定θ0，隻考慮θ1的疊代，上面的算式可以寫為：
如果對高數還有一點印象的話，可以了解這是一個導數算式。如果這個也不記得，那我們可以簡單了解為對函數曲線的某一個點畫切線，這個斜率就是函數在該點的導數。
這個斜率可能為正數，也可能為負數，這樣無論從哪個點出發，經過疊代，都可以到達最低點。當斜率為0時，θ1值不再變化，即求得最優解。
α值的選取
在上面的梯度下降算法中，還有一個重要的參數α，這個相當于下山的步幅，這個α值的選擇也有講究，如果值過小，梯度下降緩慢，需要很多次的疊代才能達到收斂。如果值過大，梯度下降過程中可能越過了最低點，形成震蕩，無法收斂。
如何選擇這個α值，主要依靠經驗。另外就是先選擇一個值，評估一下收斂速度，然後再選擇一個适合的值。
實作梯度下降算法
上面給出了梯度下降算法的一般化形式，如果要實作這個算法，我們需要知道那個偏導數的算術表達式。回到線性回歸，梯度下降算法的表達式為：
其中m為訓練資料集的大小，xi, yi為訓練資料集的值。
其實有一個更通用的偏導數推導公式：
為了友善矩陣運算，資料集添加了一列，x0=1，代入到上述公式，就可以看出它們其實是等價的。
多變量回歸
教程為了簡化起見，從單變量回歸入手，然後再過渡到多變量回歸。有了單變量回歸的基礎，了解多變量回歸并不困難，其中最主要的一點是要了解矩陣運算，将單變量回歸的算術運算改寫為矩陣運算即可。比如回歸函數的矩陣化表示為：
需要注意的是，x0是為了友善矩陣化表示而引入的，x0固定等于1。
相應的，我們的梯度遞減算法更新為：
可以看出，和單變量回歸非常相似，僅僅是多了一些計算。
在k-近鄰算法中，我們讨論過歸一化數值的問題。在梯度遞減算法中，也要對資料進行處理，以加快疊代速度，通常采用的計算方法為：
其中μi是特征(i)的所有值的平均值，si是值的範圍(max - min)或标準偏差。
正态方程式解法
看過《機器學習實戰》第8章的同學可能會疑惑，書上并沒有采用梯度下降算法，而是直接采用如下方程式求解：
這個方程式看起來很簡潔，實作起來似乎更簡單，不需要疊代。然而問題在于這個方程式存在求逆的運算，這帶來兩個問題：
- 并非所有的矩陣都存在逆
- 對一個巨大的矩陣求逆，将非常耗時
下表給出兩種方法各自的優缺點：
| 梯度下降算法 | 正态方程式 |
|---|---|
| 需要選擇一個合适的alpha值 | 不需要選擇alpha值 |
| 需要多次疊代 | 無需疊代 |
| 複雜度O(kn2) | 複雜度O(n3), 需要計算XTX的逆 |
| 當n很大時可以很好的工作 | 如果n很大，将會非常慢 |
用正态方程求逆的複雜度為O(n3)。 是以如果有很多特征，那麼正态方程求解将會很慢。在實踐中，當n超過10,000時，采用梯度遞減算法更合适。
小結
在《機器學習實戰》第8章，還介紹了局部權重線性回歸。其實，對于這些基礎的算法，基本上不需要我們去編寫代碼，現有的機器學習庫都已經實作得相當完善，那這是不是意味着我們不需要去了解算法呢？也不是。就拿線性回歸來說，我們需要了解什麼情況下使用梯度遞減法、alpha值的選擇，如何判斷疊代是否收斂等等。也就是說，有了對算法的了解，我們可以在實際中更好的選擇合适的算法，更好的調整參數。