假設(shè)我們有一張房子屬性及其價格之間的關(guān)系表(如下圖所示) ，根據(jù)這些數(shù)據(jù)如何估計其他房子的價格？我們的第一個反應(yīng)肯定是參考屬性相似的房子的價格。在屬性較少時這個方法還行得通，屬性太復(fù)雜時就不那么簡單了。很顯然，我們最終目的是根據(jù)這些數(shù)據(jù)學習到房子屬性和價格之間的某種關(guān)系，然后利用這種關(guān)系預(yù)測其他房子的價格。

我們將問題形式化，給出如下相關(guān)說明。 訓練集 — 用于學習這種關(guān)系的數(shù)據(jù)集合； 測試集 — 用于測試所學關(guān)系準確性的數(shù)據(jù)集合； \(x\) — 輸入變量/特征； \(y\) — 目標變量； \((x,y)\) —單 個訓練樣本； \(m\)— 訓練集中的樣本數(shù)目； \(n\) — 特征維度； \((x^{(i)},y^{(i)})\) — 第\(i\)個訓練樣本。

在這類問題中，我們可以利用目標變量調(diào)整模型，屬 于監(jiān)督學習(Supervised Learning) 范疇。由于目標變量是連續(xù)的，是一個典型的 回歸(Regression) 問題。監(jiān)督學習的框架如下圖所示：設(shè)計學習算法，再用訓練集進行訓練，最后得到一個反映輸入變量和目標變量之間映射關(guān)系的模型，利用該模型可以預(yù)測出測試數(shù)據(jù)的目標變量。

在監(jiān)督學習中，我們有\(zhòng)(m\)個訓練樣本組成的訓練集。如何表述模型是設(shè)計學習算法的第一步。在這里，我們簡單地采用一個線性模型

\begin{equation}h_{\theta}(x)=\theta_0+\theta_1x_1+\cdots+\theta_nx_n=\sum_{i=0}^n\theta_ix_i=\theta^Tx\end{equation}

其中\(zhòng)(\theta_0\)為截距，\(\theta_1,\cdots,\theta_n\)為輸入變量\(x)\)每一維變量對應(yīng)的參數(shù)。為了便于表述，引入\(x_0=1\)。

學習算法的職責在于利用訓練集選擇合適的參數(shù)\(\theta\)，使得模型盡可能做出準確的預(yù)測。 在回歸問題中，使\(h_{\theta}(x)\)以最大限度接近\(y\)是最合理的切入角度。我們使用如下的 代價函數(shù)(cost function) ：

\begin{equation}J(\theta)=\frac{1}{2}\sum_{i=1}^m(h_{\theta}(x^{(i)})-y^{(i)})^2\end{equation}

\(J(\theta)\)是關(guān)于參數(shù)\(\theta\)的函數(shù)，我們要做的就是\(\min_{\theta}J(\theta)\)。

接下來討論兩類求解算法。一類是迭代形式的 搜索算法(Search algorithm) ，另一類是 解析表達式 。

搜索算法的基本策略就是先在參數(shù)空間賦予參數(shù)\(\theta\)一個猜測的初始值，然后以此初始值為出發(fā)點，不斷修改\(\theta\)以減小\(J(\theta)\)，直到\(\theta\)收斂到可使\(J(\theta)\)收斂到最小值，這時的參數(shù)\(\theta\)就是我們要求解的可使模型性能最好的參數(shù)。下面，我們以 梯度下降(Gradient descent) 為基礎(chǔ)，介紹三種搜索算法。

梯度下降的思想源于函數(shù)沿著梯度的反方向下降速度最快，參數(shù)更新規(guī)則為

\begin{equation}\theta_i=\theta_i-\alpha\frac{\partial}{\partial\theta_i}J(\theta)\end{equation}

其中\(zhòng)(\alpha\)為學習率(learning rate)，控制在梯度反方向上移動的步長。這是一個很自然的算法，只要我們始終沿著梯度方向走，就能不斷減小\(J(\theta)\)。 但是該算法存在兩個問題，一是依賴初始點的位置，二是依賴于學習率。 如果\(J(\theta)\)僅存在一個極小值，那么初始點的選取無所謂，最終總會收斂到全局最優(yōu)解(如下左圖)；否則，\(J(\theta)\)會因初始點的不同而收斂到不同極小值，只能達到局部最優(yōu)，而局部最優(yōu)解里面也存在優(yōu)劣之分(如下右圖)，我們的問題屬于第一種情況。學習率\(\alpha\)太小，收斂花費的時間太長；但\(\alpha\)過大，又很可能會錯過極小值。針對第一個問題，現(xiàn)在的解決辦法就是選擇不同的初始值進行迭代，最后選擇最優(yōu)的解；第二個問題的解決辦法有 線性搜索(Line Search) 等，這里不進行介紹。

?

現(xiàn)在僅考慮單個樣本\((x,y)\)情況下的梯度下降問題：

\begin{align}\frac{\partial}{\partial\theta_j}J(\theta)&=\frac{\partial}{\partial\theta_i}\frac{1}{2}(h_{\theta}(x)-y)^2\\&=2\cdot \frac{1}{2}(h_{\theta}(x)-y)\cdot \frac{\partial}{\partial\theta_i}(h_{\theta}(x)-y)\\&=(h_{\theta}(x)-y)\cdot\frac{\partial}{\partial\theta_i}(\theta_0x_0+\theta_1x_1+\cdots+\theta_nx_n-y)\\&=(h_{\theta}(x)-y)\cdot x_i\end{align}

結(jié)合公式(3)和公式(7)，我們得到的參數(shù)更新規(guī)則如下：

\begin{equation}\theta_i=\theta_i-\alpha(h_{\theta}(x^{(j)})-y^{(j)})x_i^{(j)}\end{equation}

有了上述更新規(guī)則，下面就直接引出三種搜索算法：

批梯度下降(Batch gradient descent) 的特點在于每次更新參數(shù)都要掃描訓練集中的所有樣本。對于較小的訓練集，該方法還是不錯的；但對于人口普查等有海量樣本的數(shù)據(jù)庫就不合適了，其計算量之大可想而知。

隨機梯度下降(Stochastic gradient descent,SGD) 規(guī)避了批梯度下降的缺陷，每次只用一個樣本更新所有參數(shù)。對于大的數(shù)據(jù)集，隨機梯度下降比批梯度下降更快趨近到極小值。但隨機梯度下降并不能保證收斂到極小值，而是會在極小值鄰域振蕩。在實際應(yīng)用中，最小值的鄰域也在可接受的范圍內(nèi)。

算法3是前面兩種算法的折衷方案，其思路是先將整訓練集隨機置亂，再以滑動窗口形式將其劃分成若干塊，然后在每塊上以批梯度下降的方式更新參數(shù)，以塊為單位用隨機梯度下降方式更新參數(shù)。這樣做的有兩點好處：一是綜合了算法1和2的優(yōu)點；二是分塊計算為并行處理提供了條件(如下圖所示)。

我們怎樣判斷是否收斂呢？這里簡單介紹兩種辦法：

1. 參數(shù)\(\theta\)在連續(xù)幾次迭代中變化非常小，可視為達到收斂
2. 函數(shù)值\(J(\theta)\)在連續(xù)幾次迭代中沒什么變化也可視為處于收斂狀態(tài)

下面，我們討論該問題的解析形式求解方法。

首先，有必要在這里提供基本的矩陣知識：

• 矩陣的跡(Trace)操作

\begin{align}&Tr(A)=\sum_{i=1}^nA_{ii}\\&Tr(a)=a\\&Tr(AB)=Tr(BA)\\&Tr(ABC)=Tr(CAB)=Tr(BCA)\\\end{align}

• 矩陣的求導(dǎo)規(guī)則

函數(shù)\(f:\mathbb{R}^{m\times n}\mapsto \mathbb{R}\)，將\(m\times n\)的矩陣映射到實數(shù)空間，其求導(dǎo)規(guī)則如下：

\begin{equation} \nabla_Af(A)=\left[ \begin{array}{ccc}\frac{\partial f}{\partial A_{11}} & \cdots & \frac{\partial f}{\partial A_{1n}}\\\vdots & \ddots & \vdots \\\frac{\partial f}{\partial A_{m1}} & \cdots & \frac{\partial f}{\partial A_{mn}}\end{array} \right]\end{equation}

針對矩陣跡求導(dǎo)的規(guī)則如下：

\begin{align} &\nabla_ATr(AB)=B^T\\ &\nabla_ATr(A)=\nabla_ATr(A^T)\\ &\nabla_ATr(ABA^TC)=CAB+C^TAB^T\\ &\nabla_ATr(BAC)=B^TC^T=CB\\ &\nabla_{A^T}f(A)=(\nabla_Af(A))^T \end{align}

更多內(nèi)容請參考《Matrix Cookbook》，這份文檔只給出結(jié)論，沒有具體證明，可以作為日常矩陣運算的參考手冊，內(nèi)容比較全面。

定義矩陣\(X\)為每個訓練樣本在行級疊加成的矩陣：\(X=\left[ \begin{array}{c}(x^{(1)})^T\\ \vdots\\ (x^{(m)})^T \end{array}\right],\vec{y}=\left[ \begin{array}{c}y^{(1)}\\ \vdots\\ y^{(m)}\end{array}\right]\)。

代價函數(shù)轉(zhuǎn)化為矩陣的形式：

\begin{equation} J(\theta)=\frac{1}{2}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2=\frac{1}{2}(X\theta-\vec{y})^T(X\theta-\vec{y}) \end{equation}

我們的問題只存在一個最優(yōu)解，所以最小值肯定是在極值點處取得，直接對\(\theta\)求導(dǎo)即可得到最優(yōu)參數(shù)：

\begin{align}\nabla_\theta J(\theta)&=\frac{1}{2}\nabla_\theta Tr[(X\theta-\vec{y})^T(X\theta-\vec{y})]\\ &=\frac{1}{2}\nabla_\theta Tr[\theta^TX^TX\theta-\theta^TX^T\vec{y}-\vec{y}^TX\theta+\vec{y}^T\vec{y}]\\ &=\frac{1}{2}[\nabla_\theta Tr(\theta\theta^TX^TX)-\nabla_\theta Tr(\theta^TX^T\vec{y})-\nabla_\theta Tr(\vec{y}^TX\theta)]\\ &=\frac{1}{2}(X^TX\theta+X^TX\theta-X^T\vec{y}-X^T\vec{y})=0\\ &\Rightarrow \theta=(X^TX)^{-1}X^T\vec{y} \end{align}

上述結(jié)果看起來相當完美！稍微留意一下我們就可以發(fā)現(xiàn)，矩陣\((X^TX)^{-1}\)不一定存在。當樣本數(shù)目\(m\)小于特征的維度\(n\)時，\((X^TX)^{-1}\)肯定是不存在的；反過來，我們也只能說\((X^TX)^{-1}\)可能存在。這個問題我還不知道怎么破...

下面展示一下我在數(shù)據(jù)集 Housing Data Set 上做的實驗。模型采用上述的線性回歸，以批梯度下降方式學習最優(yōu)參數(shù)。編程語言為Matlab，數(shù)據(jù)集在data目錄下，minFunc目錄里面是采用了線性搜索的梯度下降工具包， 代碼在這里下載 。數(shù)據(jù)集中一共有506個樣本，每個樣本有14個屬性，最后一個屬性為房子價格，其他13個屬性則作為每個樣本的特征，更詳細的描述請移步 Housing Data Set 。為了便于觀察實驗結(jié)果，我選取的第6個屬性作為每個樣本的特征，因為這個屬性在整個數(shù)據(jù)集上變換范圍比較小，繪制的圖形美觀一些。如果要改用其他的數(shù)據(jù)，只需修改loadData.m這個文件。最后的展示的結(jié)果是二維的圖，綠色的為樣本 點 ，紅色的直線為我們學習到的線性模型。

在回歸問題中，為什么最小二乘(Least Square)是代價函數(shù)的一個合理選擇？我們先給出兩個假設(shè)，然后從概率論角度進一步解釋線性回歸中最小二乘是如何與最大似然(Maximum Likelihood)統(tǒng)一的。

• 假設(shè)一：樣本特征和輸出變量間的關(guān)系為

\begin{equation}y^{(i)}=\theta^Tx^{(i)}+\epsilon^{(i)}\end{equation}

其中誤差項\(\epsilon^{(i)}\)既可以被看作未考慮的其他相關(guān)因素，也可以被視為隨機噪聲。

• 假設(shè)二：\(\epsilon^{(i)}\)滿足獨立同分布(Independently Identically Distributed,IID)的高斯模型\(\epsilon^{(i)}\sim\mathcal{N}(0,\sigma^2)\)，其概率密度函數(shù)如下：

\begin{equation}p(\epsilon^{(i)})=\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{\epsilon^2}{2\sigma^2}\right)\end{equation}

由上式很容易得到如下的關(guān)系：

\begin{equation}p(y^{(i)}|x^{(i)};\theta)=\frac{1}{\sqrt{2\pi}\sigma}\exp(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2})\end{equation}

根據(jù)獨立同分布的假設(shè)，似然函數(shù)形式如下：\begin{align}L(\theta)&=p(\vec{y}|X;\theta)\\&=\prod_{i=1}^mP(y^{(i)}|x^{(i)};\theta)\\&=\prod_{i=1}^m\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2}\right)\end{align}

為便于計算，求得相應(yīng)的對數(shù)似然函數(shù)：

\begin{align}\ell(\theta)&=\log L(\theta)\\&=\log\prod_{i=1}^m\frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2\sigma^2}\right)\\&=\sum_{i=1}^m\log\frac{1}{\sqrt{2\pi}\epsilon}\exp\left(-\frac{(y^{(i)}-\theta x^{(i)})^2}{2\sigma^2}\right)\\&=m\log\frac{1}{\sqrt{2\pi}\sigma}-\frac{1}{2\sigma^2}\sum_{i=1}^m(y^{(i)}-\theta^Tx^{(i)})^2\end{align}

根據(jù)最大似然的規(guī)則，能使公式(34)最大的參數(shù)\(\theta\)為最佳參數(shù)。最大化\(\ell(\theta)\)等價于最小化\(J(\theta)=\frac{1}{2}\sum_{i=1}^m(y^{(i)}-\theta^Tx^{(i)})^2\)。在前面兩個假設(shè)的前提下，最小二乘回歸與最大似然是對應(yīng)統(tǒng)一的。

Supervised Learning-Regression