監督學習應用與梯度下降
本課内容：
1、 線性回歸
2、 梯度下降
3、 正規方程組
（複習）監督學習：告訴算法每個樣本的正确答案，學習後的算法對新的輸入也能輸入正确的答案
1、 線性回歸
例：Alvin汽車，先讓人開車，Alvin攝像頭觀看（訓練），而後實作自動駕駛。
本質是一個回歸問題，汽車嘗試預測行駛方向。
例：上一節課的房屋大小與價格資料集
引入通用符号：
m = 訓練樣本數
x = 輸入變量（特征）
y = 輸出變量（目标變量）
(x,y) – 一個樣本
–第i個訓練樣本 =
本例中：m：資料個數，x：房屋大小，y：價格
監督學習過程：
1) 将訓練樣本提供給學習算法
2) 算法生成一個輸出函數（一般用h表示，成為假設）
3) 這個函數接收輸入，輸出結果。（本例中為，接收房屋面積，輸出房價）将x映射到y。
如下圖所示：
對假設進行線性表示：
通常來說，回歸問題有多個輸入特征。如上例中，我們還已知房屋的卧室數，即有個第二個特征。即
表示大小，
表示卧室數，則可将假設寫成：
為了将公式寫整潔，定義
，則h可寫成：
n = 特征數目，
：參數
選擇
的目的，是使h(x)與y的平方差盡量小。又由于有m個訓練樣本，需要計算每個樣本的平方差，最後為了簡化結果乘以1/2，即：
我們要做的就是求：min(J(
))
求min(J(
))方法：梯度下降和正規方程組
2、 梯度下降
梯度下降是一種搜尋算法，基本思想：先給出參數向量一個初始值，比如0向量；不斷改變，使得J(
)不斷縮小。
改變 的方法：梯度下降
如圖所示，水準坐标軸表示
，垂直坐标表示J(
)
一開始選擇0向量作為初始值，假設該三維圖為一個三維地表，0向量的點位于一座“山”上。梯度下降的方法是，你環視一周，尋找下降最快的路徑，即為梯度的方向，每次下降一小步，再環視四周，繼續下降，以此類推。結果到達一個局部最小值，如下圖：
當然，若初始點不同，則結果可能為另一個完全不同的局部最小值，如下：
表明梯度下降的結果依賴于參數初始值。
梯度下降算法的數學表示：
為指派運算符，即表示程式中的的指派語句。
每一次将
減去
對
求偏導的結果，即沿最陡峭的“山坡”下降
将偏導數展開分析：
代入上式：
：學習速度，即決定你下山時每一步邁多大。設的過小，收斂時間長，設的過大，可能會超過最小值
（1） 批梯度下降算法：
上述為處理一個訓練樣本的公式，将其派生成包含m個訓練樣本的算法，循環下式直至收斂：
複雜度分析：
對于每個
的每次疊代，即上式所示，時間為O(m)
每次疊代（走一步）需要計算n個特征的梯度值，複雜度為O(mn)
一般來說，這種二次函數的
的三維圖形為一個碗狀，有一個唯一的全局最小值。其等高線為一個套一個的橢圓形，運用梯度下降會快速收斂到圓心。
梯度下降性質：接近收斂時，每次的步子會越來越小。其原因是每次減去
乘以梯度，但是梯度會越來越小，是以步子會越來越小。
下圖為使用梯度下降拟合的上例房屋大小和價格的曲線
檢測是否收斂的方法：
1) 檢測兩次疊代
的改變量，若不再變化，則判定收斂
2) 更常用的方法：檢驗
，若不再變化，判定收斂
批梯度下降算法的優點是能找到局部最優解，但是若訓練樣本m很大的話，其每次疊代都要計算所有樣本的偏導數的和，時間過慢，于是采用下述另一種梯度下降方法。
（2） 随機梯度下降算法（增量梯度下降算法）：
每次計算
不需要再周遊所有資料，而是隻需計算樣本i即可。
即批梯度下降中，走一步為考慮m個樣本；随機梯度下降中，走一步隻考慮1個樣本。
每次疊代複雜度為O(n)。當m個樣本用完時，繼續循環到第1個樣本。
上述使用了疊代的方法求最小值，實際上對于這類特定的最小二乘回歸問題，或者普通最小二乘問題，存在其他方法給出最小值，接下來這種方法可以給出參數向量的解析表達式，如此一來就不需要疊代求解了。
3、 正規方程組
給定一個函數J，J是一個關于參數數組的函數，定義J的梯度關于的導數，它自己也是一個向量。向量大小為n+1維（從0到n），如下：
是以，梯度下降算法可寫成：
更普遍的講，對于一個函數f，f的功能是将一個m*n的矩陣映射到實數空間上，即：
假設輸入為m*n大小的矩陣A，定義f關于矩陣A的導數為：
導數本身也是個矩陣，包含了f關于A的每個元素的偏導數。
如果A是一個方陣，即n*n的矩陣，則将A的迹定義為A的對角元素之和，即：
trA即為tr(A)的簡化。
一些關于迹運算符和導數的定理：
1) trAB = trBA
2) trABC = trCAB = trBCA
3)
4)
5) 若
，tra = a
6)
有了上述性質，可以開始推導了：
定義矩陣X，稱為設計矩陣，包含了訓練集中所有輸入的矩陣，第i行為第i組輸入資料，即：
則由于
，是以可得：
又因為對于向量z，有
，則有：
由上述最後一個性質可得：
通過上述6個性質，推導：
倒數第三行中，運用最後一個性質
将
置為0，則有：
稱為正規方程組
可得：