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

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

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

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

\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}

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

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

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

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

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

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

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

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

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

?

現在僅考慮單個樣本\((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}

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

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

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

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

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

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

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

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

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

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

• 矩陣的跡(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}

• 矩陣的求導規則

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

\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}

針對矩陣跡求導的規則如下：

\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}

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

定義矩陣\(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]\)。

代價函數轉化為矩陣的形式：

\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}

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

\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}

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

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

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

• 假設一：樣本特征和輸出變量間的關系為

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

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

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

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

由上式很容易得到如下的關系：

\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}

根據獨立同分布的假設，似然函數形式如下：\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}

為便于計算，求得相應的對數似然函數：

\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}

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

Supervised Learning-Regression