CS229機器學習（一）——線性回歸

01-28

問題引入

在談我們今天要講的線性回歸模型之前，我們可以先看一個問題：

圖一某地房屋面積與對應房價

假設你要在北京三環內買一套房，經過你精心的調研，你搜集到了一組如上圖所示的數據，該數據展示了北京三環內房屋的面積與之對應的房屋價格。那麼，你現在就想能否找到一個模型（函數）可以去擬合這麼一組數據，並能很好預測在北京三環內任意房屋面積的房價呢？

當然可以！在解決問題之前，我們先用機器學習的思維建立一套統一的符號系統，用符號來描述該問題。

$x^{left( iright)}$ 稱作輸入，在本問題中表示圖一中第 $i$ 個房屋對應的面積（如果你將表中的房屋從1到 $n$ 進行編號），也稱為第 $i$ 個樣本的輸入特徵。
$y^{left( i right)}$ 稱作輸出，在本問題中表示圖一中第 $i$ 個房屋對應的房屋價格也稱為對應第 $i$ 個輸入我們要預測的輸出。
$left( x^{(i)}，y^{(i)} right)$ 稱為第 $i$ 個訓練樣本，即單個樣本，是一對輸入與輸出。
$left{ left( x^{(i)}，y^{(i)} right);i=1,2,...,m right}$ 稱為訓練集，該訓練集中有m個樣本，可以認為我們選取了m套房的面積和價格作為訓練數據，剩餘的數據作為測試集。
$chi$ 稱作輸入空間，值得注意的是這裡的輸入空間不僅包含我們已經搜集到的那些樣本的輸入，也包含那些我們沒有搜集到的樣本的輸入也就是我們要預測的樣本的輸入。
$Y$ 稱作輸出空間，解釋類比與 $chi$ 。

有了上述的符號定義，我們就可以明確我們要乾的事情，就是找一個函數 $f$ ，可以滿足對於 $chi$ 中的任意輸入我們都能得到 $Y$ 中與之對應的輸出。當然， $chi$ 和 $Y$ 我們是無法全部得到的，我們只有這兩個空間中的一部分數據也就是 $left{ left( x^{(i)}，y^{(i)} right);i=1,2,...,m right}$ ，所以我們問題轉化為找到一個函數 $f$ 使得 $f(x^{(i)})$ 儘可能的接近 $y^{left( i right)}$ 並且這個函數在測試集上也能得到很好的輸出。

說到這，我們再回到這個房價預測問題的本身，按常識來說，房價這個東西基本上可以取到任意數值，所以可以認為預測的房價是個連續型變數。我們把該類問題就稱為回歸問題。如果預測的問題是較小數量的離散型變數（就是預測的數值在一定範圍類並且只取幾個特定數值），那麼我們把該類問題稱為分類問題。

好啦，有了以上的基本問題的引入，我們可以開始去找那個牛逼哄哄的預測函數了！

線性回歸

本節就從最簡單的線性函數找起，學過線性代數的同學一定知道形如

$f(x_{1},...,x_{n})=sum_{i=1}^{n}{theta_{i}x_{i}}+theta_{0}$

都稱為線性函數，其可以寫成一個行向量和一個列向量的乘積。

那麼，我們要利用線性函數去預測房價 $y^{left( i right)}$ ，就是要找到線性函數中的參量 $theta$ ， $theta$ 確定了，線性函數也就確定了。我們的問題也就解決了。那這個參數如何確定呢？

特定問題的線性模型定義

在解決這個問題之前我們先把之前的房價預測問題複雜一下，要想得到一個好的房價預測模型，單靠房屋面積肯定是做不出好的預測的，因為影響房價的因素不止一個，於是你又費盡千辛萬苦，找到了另一組特徵，卧室的數量。

圖2 加了卧室數量的新數據樣本

那麼我們的線性回歸模型可以定義為如下:

$h_{theta}(x_{1}^{(i)},...,x_{n}^{(i)})=sum_{j=0}^{n}{theta_{j}x_{j}^{(i)}}=theta^{T}x^{(i)}=x^{(i)T}theta$

對上面函數解釋做以下幾點解釋：

對於第 $i$ 個樣本（簡單理解為圖2中第 $i$ 行的房屋）來說，只有房屋面積（ $x_{1}^{(i)}$ ）和卧室數量（ $x_{2}^{(i)}$ ）兩個特徵，所以線性函數只有如上的三個參量。
求和形式中多了一個 $x_{0}^{(i)}$ ，我們默認把他定義為1。
向量形式表示時一個是三維的行向量一個是三維的列向量
如果有 $n$ 個特徵，則模型可以定義為 $h(x_{1}^{(i)},...,x_{n}^{(i)})=sum_{j=0}^{n}{theta_{j}x_{j}^{(i)}}=theta^{T}x^{(i)}$

這樣我們對特定問題的線性模型已經定義完畢，但我們依舊沒有確定我們想要的 $theta$ ，這個不要急，咱們慢慢來。

建立損失函數

要想確定這個 $theta$ 我們就得考慮它得滿足什麼條件。還記得之前我們有說過要建立一個線性模型，使得這個模型對於輸入 $x^{(i)}$ 有 $f(x^{(i)})$ 儘可能接近 $y^{(i)}$ ，那麼我們如何描述這個儘可能的接近？沒有錯，我們可以選擇最小二乘！通過最小二乘我們可以建立如下的損失函數:

$J(theta)= frac{1}{2}sum_{i=1}^{m}{(h_{theta}(x_{1}^{(i)},...,x_{n}^{(i)})-y^{(i)})^{2}}$

對以上函數做個簡單的說明：

$J(theta)$ 表徵的是所有訓練樣本的預測輸出（預測房價）與訓練樣本真實房價的差距。
求和中的 $m$ 代表的是樣本數量（前文也提到過）， $n$ 代表的是每個樣本的特徵數量，房價問題中就是房屋面積和卧室數量也就是2。
該函數由於訓練樣本輸入輸出都是已知的，所以僅僅是關於 $theta$ 的函數。

損失函數建立後，再看看我們的目標，是使預測的輸出與真實的輸出儘可能的接近，也就是說我們要使 $J(theta)$ 儘可能的小，於是我們的問題轉化為找一組 $theta$ 值使得 $J(theta)$ 最小。好啦，我們離求出 $theta$ 只差一步了!

求解 $theta$ 的兩種方法

終於可以求解 $theta$ 了，想想還有點小激動呢！在這裡有兩種方法，一種是人盡皆知的梯度下降法，另一種就是簡單粗暴的直接求導法。梯度下降法以後講的場合會很多，在BP里我們再詳細介紹，所以今天我們著重來說說直接求導法。

在介紹這種方法之前先回顧一下需要的基礎知識：

一個結果為標量的函數關於一個矩陣求導

對於一個函數 $f$ 可以將一個 $mtimes n$ 的矩陣映射為一個實數( $R^{mtimes n}rightarrow R$ )寫成具體公式的形式就是

$f(A)=p$ 其中 $Ain R^{mtimes n},pin R$

那麼我們現在要讓函數 $f$ 對 $A$ 求導，我們有以下公式

即讓函數 $f$ 對矩陣 $A$ 中的每一個元素進行求導，求導的結果對應放到該元素的位置。所以 $A$ 是 $mtimes n$ 維的，那麼 $▽_{A}f(A)$ 也是 $mtimes n$ 維的。

矩陣的跡及其相關性質

首先明確以下，矩陣的跡（trace簡寫為 $tr$ ）一定是對方陣而言的，即矩陣的大小一定是 $ntimes n$ 維的，那麼對應於 $ntimes n$ 維的矩陣 $A$ ，那麼它的跡可以表示為：

$tr A=sum_{i=1}^{n}{A_{ii}}$

即矩陣對角線上所有元素之和，那麼對應於一個實數 $a$ 來說，它的跡就是它本身即

$tr a=a$

有了定義，再介紹下我們將用到的矩陣的跡的幾條性質，對於矩陣 $A(mtimes n)，B(ntimes m)$ （括弧中是它們的大小），我們知道 $AB$ 為 $mtimes m$ 的方陣，所以我們有：

$tr AB=tr BA$ (1)

$tr ABC=tr CAB=tr BCA$ (2)

當 $m=n$ 時即， $A,B$ 都是方陣, $a$ 為實數時我們有：

$tr A=tr A^{T}$ (3)

$tr (A+B)=tr A+tr B$ (4)

$tr (aA)=a tr A$ (5)

最後給出幾條矩陣的跡在微分中的性質（ $AB$ 的結果依然為方陣）：

$▽_{A}tr (AB)=B^{T}$ (6)

$▽_{A^{T}}f(A)=(▽_{A}f(A))^{T}$ (7)

$▽_{A}trABA^{T}C=CAB+C^{T}AB^{T}$ (8)

對於以上的性質有興趣的同學可以去證明一下下，我們這裡直接用就好了。

問題正式求解

好，有了上面的知識儲備，我們來求解我們的問題吧。

我們知道我們的房價問題的訓練數據集 $left{ left( x^{(i)}，y^{(i)} right);i=1,2,...,m right}$ 中有 $m$ 個樣本，而對應每個樣本的輸入 $x^{(i)}=left{ x_{1}^{(i)},...,x_{n}^{(i)} right}$ （是個列向量）又對應了 $n$ （房價預測問題的 $n=2$ ）個特徵，所以我們可以把這些輸入寫到一個 $mtimes n$ 的大矩陣 $X$ 裡面作為我們的整體輸入（代表 $m$ 個樣本每個樣本有 $n$ 個特徵）

與輸入對應，將 $m$ 個樣本的輸出寫到一個 $m$ 維的列向量 $y$ 里

所以，結合我們原始的損失函數和線性回歸函數

$J(theta)= frac{1}{2}sum_{i=1}^{m}{(h_{theta}(x_{1}^{(i)},...,x_{n}^{(i)})-y^{(i)})^{2}}= frac{1}{2}sum_{i=1}^{m}{(h_{theta}(x^{(i)})-y^{(i)})^{2}}$

$h_{theta}(x_{1}^{(i)},...,x_{n}^{(i)})=sum_{j=0}^{n}{theta_{j}x_{j}^{(i)}}=theta^{T}x^{(i)}=x^{(i)T}theta$

由於上式的回歸函數是對一個樣本而言的結果，如果同時計算m個樣本的預測結果就可以轉化為

$Xtheta=[x^{(1)T}theta,...,x^{(m)T}theta]^{T}=[h_{theta}(x^{(1)}),...,h_{theta}(x^{(m)})]^{T}$

最後得到我們矩陣形式的損失函數為

$J(theta)=frac{1}{2}(Xtheta-y)^{T}(Xtheta-y)$

所以接下來要做的就是對 $J(theta)$ 求導並令導數為0，對 $theta$ 進行求解，就是我們的最終結果。

推導過程：

$▽_{theta}J(theta)=▽_{theta}frac{1}{2}(Xtheta-y)^{T}(Xtheta-y)$

又 $(Xtheta-y)^{T}=(Xtheta)^{T}-y^{T}=theta^{T}X^{T}-y^{T}$ 所以帶回上式乘開有

$▽_{theta}J(theta)=frac{1}{2}▽_{theta}(theta^{T}X^{T}Xtheta-theta^{T}X^{T}y-y^{T}Xtheta+y^{T}y)$

又由於 $J(theta)$ 是一個實數，所以 $J(theta)= tr J(theta)$ 那麼上式就轉化為求跡的問題

$▽_{theta}J(theta)=frac{1}{2}▽_{theta}(trtheta^{T}X^{T}Xtheta-trtheta^{T}X^{T}y-tr y^{T}Xtheta+try^{T}y)$

又 $theta^{T}X^{T}y=( y^{T}Xtheta)^{T}$ （則 $theta^{T}X^{T}y和( y^{T}Xtheta)^{T}$ 的跡相同（公式（3））），且 $y^{T}y$ 是與 $theta$ 無關的量，上式可簡化為

$▽_{theta}J(theta)=frac{1}{2}▽_{theta}(trtheta^{T}X^{T}Xtheta-2tr y^{T}Xtheta)$

又

$▽_{theta}trtheta^{T}X^{T}Xtheta=▽_{theta}trthetatheta^{T}X^{T}X=▽_{theta}trtheta Itheta^{T}X^{T}X=X^{T}Xtheta I+(X^{T}X)^{T}theta I^{T}=2X^{T}Xtheta$

第一個等號運用公式（2），第2個等號是在 $theta$ 和 $theta^{T}$ 之間插入了一個單位陣 $I$ ，第3個等號是運用公式（8）將 $X^{T}X$ 看作一個整體運算。

又

$▽_{theta}2tr y^{T}Xtheta=▽_{theta}2trtheta y^{T}X=2(( y^{T}X))^{T}=2X^{T}y$

第一個等號運用公式（2），第二個等號運用公式（6）。

所以

$▽_{theta}J(theta)=2X^{T}Xtheta+2X^{T}y$

令上式為0，解得：

$theta=(X^{T}X)^{-1}X^{T}y$

到此，我們終於把這個 $theta$ 給求解出來了。本文的內容到此也終於告一段落了。不過大家還記得之前損失函數我們是直接給出來的吧，說是可以度量預測值與真實值的一個距離，那麼這個度量是否是真的有效呢？下一回我們將從概率的角度對整個過程做一番解釋，然後直接推導出我們的損失函數，不要太心急，敬請期待！