機器學習筆記（1）—— 回歸和分類

05-03

本文為學習吳恩達（Andrew Ng）老師系列講座的學習心得，圖表和公式未加說明均來自吳老師的講座Coursera | Online Courses From Top Universities. Join for Free，不定期更新。

機器學習分為監督學習（Supervised Learning）和無監督學習（Unsupervised Learning）兩類。

第一周

監督學習主要解決兩類問題：

- 回歸（Regression），例如，根據歷史上的天氣數據預測明天的氣溫，或者吳老師的例子是根據已知戶型房產的已知價格來推斷新房產能賣多少錢。

- 分類（Classification），例如，根據歷史上的天氣數據來預測明天是否會下雨，或者預測明天是晴天，雨天還是雪天。兩個例子的區別是第一種分類只有兩個類別（1 - 下雨，0 - 不下雨），後一種分類有多個類別（1 - 晴天，2 - 雨天，3 - 雪天）

從上述描述可以看出，回歸類問題的輸出是連續的而分類問題的結果是離散的。監督學習的本質是在結果可驗證（如房產的最終售出價格和明天的天氣）的情況下，建立輸入參數（房產面積）和輸出參數（售出價格）之間的關係（或者映射，或者函數），這種關係被稱為假設（Hypothesis），為便於理解，以下仍稱之為模型。每一組已知的輸入和輸出參數都可以通過特定演算法用於訓練函數，以提高其準確性。其過程如下圖：

為了衡量模型的準確性，代價函數（cost function）的概念被引入。對於回歸類問題，尋求代價函數最小的訓練演算法其實就是最小二乘法：

這裡Theta0和Theta1是模型H_theta(X)的兩個常數，在房產的例子里，可以把Theta0理解為房屋的基礎價格，即與面積無關的部分，Theta1理解為單位價格，即與房屋面積成正比的部分。

H_theta(X)= Theta0+Theta1*x

即一條直線。

選擇合適的Theta組使得該直線儘可能與所有已知的距離最近，叫最小一乘。而我們的目標是要構建一個模型，這裡是一條直線，使得直線與現有數據（training set）在縱軸方向上（不是最短距離那個方向）儘可能接近，因此用最小二乘。

這裡需要特別注意的是代價函數有一個1/2的係數，其實最小二乘是沒有的，吳老師的解釋是人為加這個係數，在後面做梯度下降的時候求導時約掉，可以簡化計算。

可以想像，對於模型為一條直線的情形，只有一種Theta組合，使得代價函數J最小，這個Theta參數構建的模型H即使得代價函數最小的最優解。

以下介紹求解最小代價函數的方法：

梯度下降法（Gradient descent）

Alpha 表示學習速率（Learning rate），而不是步長。增加學習速率有可能加快收斂，也有可能導致無法收斂。由於求導項dJ/dtheta的存在，越趨近J最低點，dJ/dtheta越趨於零，即Thetaj改變的步長也越小。因此，學習速率其實是將代價函數對具體參量的變化率反映在參量步進長度上的一個轉換率。同一個代價函數里可能有多個局部最低點，從不同初始位置出發可能在不同的最低點上收斂。收斂的條件可以設置為兩次迭代代價函數的差值小於某閾值。

帶入上一節中導出的J表達式，可以得出線性回歸問題的導數項，這裡，可以看到人為設置的1/2係數項可以使化簡後的表達簡潔：

可以看到，在上述表達式中，每個訓練組的數據都得到了顧及（sigma(thetai*xi)項），也就是說，此演算法追求的目標是盡量是模型H與所有訓練數據接近。此演算法稱為批量梯度下降（Batch gradient descent）。

另一個注意點是，Thetaj的迭代是同時發生的，即：

第二周

模型的向量化

上述討論均假設模型只有兩個參數Theta0和Theta1，下面將模型H推廣到多維情況：

h_theta(x)的向量化表達式為：

注意，x0實際上是不存在的，或者說等於常數1，這樣做是為了是向量表達完美統一，並保證h_theta(x)始終有一個常數項。

批量梯度下降的迭代過程可以表示為：

until delta_J < threshold.

特徵伸縮（Feature scaling）

簡單的說，如果輸入自變數x^(i)不在同一個範圍內，就會導致在有的x方向收斂的快，有的x方向收斂的慢，結果總的迭代步數增加，運算時間增加。因此，需要將所有的自變數統一在一個可以比擬的變化範圍，計算公式：

特徵伸縮不影響計算結果。

學習速率（Learning rate）

在步長合理的情況下，代價函數J會隨著迭代數增加而降低。而如果步長過大會有以下兩種情況產生：

第一種是發散，第二種是震蕩，都沒有辦法在某個點收斂，因此需要減小學習速率。而如果學習速率過小，則會收斂很慢。

多項式回歸（Polynomial regression）

上述討論的模型H中的自變數或者特徵都是x^j的一次函數，沒有平方，立方或是開方存在。再某些情況下，增加特徵的多項式可以更好的擬合模型。（when? How?）

這裡需要注意的是，增加多項式的情況下，特徵尺度也會跟著改變，比如x範圍為0-100，x^2的範圍就是0-10000。

標準方程（Normal equation）

上述介紹的是通過迭代計算的梯度下降法，另一種求最優模型（或最小代價函數）的方法是標準方程，不用迭代，而是求得J在所有參數Theta方向上導數為零時的Theta值。（其實就是最小二乘法）此時Theta組為：

計算舉例：

例中共有m=4組訓練組，注意x0是另外加上去的，恆等於1，為保持矩陣表示完美統一。標準方程和梯度下降法的對比：

標準方程最大的計算量來自於（n+1）*(n+1)階矩陣的逆運算，因此其複雜程度會隨著特徵數的增加而極速增加，在特徵數大於10000時推薦使用迭代法。

(X^T)*X不可逆的兩種原因

1 特徵冗餘，例如x_1表示房屋的面積（平方米），x_2表示房屋的面積（平方英尺），兩者可以留其一。

2 特徵過多。即特徵數大於訓練組數，n>m。我的理解是，這樣的話會導致方程數不及未知數數。解決方法是降低特徵數量。或者增加訓練組數？

第三周

以上談論的是回歸（Regression）問題，接下來討論分類（Classification）問題。

討論分類問題的核心是怎麼把利用回歸演算法得出的連續結果轉化為離散的分類結果，這裡引入轉移函數（Sigmoid）。

把h_theta(x)通過轉移函數，即將轉移函數的自變數換成(Theta^T)*x，我們可以將所有模型的輸出控制在0-1之間，也可以認為這個結果代表結果為1的概率。

決定界限（Decision boundary）

轉移函數雖然成功的將正負無窮之間的變數成功控制在0到1之間，但依然是連續變化的，我們的最終目標是要輸出0或者1的確定值。決定界限是決定h_theta(x)中哪些是0哪些是1的分界。

注意這裡的0.5是一個可以改變的量，提高它對應著輸出結果是1的門檻變高，在後面的有偏分類（Skewed classification）會用到。

邏輯回歸（Logitic regression）

這裡雖然叫回歸，但其實還是分類問題，由於歷史原因沒有叫分類（Classification）。

邏輯回歸的代價函數與普通回歸問題不同（否則會產生很多波浪，造成一系列局部極小值），如下圖：

所以要構造一個凸面（convex）的代價函數，因此邏輯回歸的代價函數表達式為：

$J( heta) = - frac{1}{m} displaystyle sum_{i=1}^m [y^{(i)}log (h_ heta (x^{(i)})) + (1 - y^{(i)})log (1 - h_ heta(x^{(i)}))]$

（為啥是上面這樣的，我也不太明白）

矩陣化表達式：

$egin{align*} & h = g(X heta) ewline & J( heta) = frac{1}{m} cdot left(-y^{T}log(h)-(1-y)^{T}log(1-h) ight) end{align*}$

迭代過程與線性回歸完全類似：

$heta := heta - frac{alpha}{m} X^{T} (g(X heta ) - vec{y})$

多類別分類問題

一對多（one vs all）演算法，即把多個類別逐個分析，每次分析其實都相當於0-1分類問題。

過擬合和正則化

首先說明擬合程度的問題：

擬合階數過低，無法體現細節，導致訓練階段和驗證階段都會出現很大的偏差（Vias），而擬合階數過高，儘管可以完美擬合訓練組，但在驗證階段會遇到很大的方差（Variance），兩種情況都會體現在高的驗證階段代價函數 $J_{cv}$ 上。

解決過擬合（Overfitting）的辦法是正則化（Regularisation），即在代價函數里增加一個懲罰項，用於懲罰（penalize）導致過擬合的特徵量。

$min_ heta dfrac{1}{2m} ( sum_{i=1}^m (h_ heta(x^{(i)}) - y^{(i)})^2 + lambda sum_{j=1}^n heta_j^2)$

由於 $lambda$ 不為零，當我們努力降低代價函數時，順便就把 $heta$ 一塊降低了，即抑制了高階特徵量項的影響。這裡需要注意的是，懲罰項不包括 $heta_0$ ，即對於代價函數中的常數項不做懲罰。

以下為線性回歸考慮正則化後的迭代過程：

$j eq0$

可以看到，等式右邊第一項 $heta_j(1 - alphafrac{lambda}{m})$ 實質是給 $heta_j$ 乘以一個比1小的數，進一步抑制 $heta_j$ 的影響。

類似的，邏輯回歸正則化後的代價函數表達式為

$J( heta) = - frac{1}{m} sum_{i=1}^m large[ y^{(i)} log (h_ heta (x^{(i)})) + (1 - y^{(i)}) log (1 - h_ heta(x^{(i)}))large] + frac{lambda}{2m}sum_{j=1}^n heta_j^2$

-----------------------------------------------------------------------------------------------------------------

以下補充內容部分來自Andrew Ng老師在Stanford的在線課程 Machine Learning

上面描述了兩種求解最優假設函數的方法（梯度下降和標準方程），這裡補充另外一種方法，牛頓迭代法。

牛頓法的用途是求非線性方程 $f(x)=0$ 的解，這裡的 $f(x)$ 對應到我們的需求是代價函數對假設函數的參數 $heta$ 的一階偏導數 $frac {partial J}{partial heta}$ 。

牛頓迭代的理論依據是泰勒級數，滿足Dirichlet的函數 $f(x)$ 在 $x^{(k)}$ 處展開為：

$f(x^{(k)}+Delta x^{(k)})=f(x^{(k)})+f^{prime}(x^{(k)})Delta x^{(k)}+f^{primeprime}(x^{(k)}) frac {(Delta x^{(k)})^2} {2!}+ cdots +f^{(n)}(x^{(k)}) frac {(Delta x^{(k)})^n} {n!}+cdots+cdots=0$