線性回歸之最小二乘法
1.最小二乘法的原理
最小二乘法的主要思想是通過確定未知引數\(\theta\)（通常是一個引數矩陣），來使得真實值和預測值的誤差（也稱殘差）平方和最小，其計算公式為\(E=\sum_{i=0}^ne_i^2=\sum_{i=1}^n(y_i-\hat{y_i})\)，其中\(y_i\)是真實值，\(\hat{y_i}\)是對應的預測值，如下圖所示（來源于維基百科，Krishnavedala的作品），就是最小二乘法的一個示例，其中紅色為資料點，藍色為最小二乘法求得的最佳解，綠色即為誤差，
圖中有四個資料點分別為：(1, 6), (2, 5), (3, 7), (4, 10)，在線性回歸中，通常我們使用均方誤差來作為損失函式，均方誤差可以看作是最小二乘法中的E除以m（m為樣本個數），所以最小二乘法求出來的最優解就是將均方誤差作為損失函式求出來的最優解，對于圖中這些一維特征的樣本，我們的擬合函式為\(h_\theta(x)=\theta_0+\theta_1x\)，所以損失函式為 $$J(\theta_0,\theta_1)=\sum_{i=0}^m(y^{(i)}-h_\theta(x^{(i)}))^2=\sum_{i=0}^m(y^{(i)}-\theta_0-\theta_1x^{(i)})^2$$（這里損失函式使用最小二乘法，并非均方誤差），其中上標(i)表示第i個樣本，
2.最小二乘法求解
要使損失函式最小，可以將損失函式當作多元函式來處理，采用多元函式求偏導的方法來計算函式的極小值，例如對于一維特征的最小二乘法，\(J(\theta_0,\theta_1)\)分別對\(\theta_0\)，\(\theta_1\)求偏導，令偏導等于0得：
\[\frac{\partial J(\theta_0,\theta_1)}{\partial\theta_0}=-2\sum_{i=1}^{m}(y^{(i)}-\theta_0-\theta_1x^{(i)}) = 0\tag{2.1} \]\[\frac{\partial J(\theta_0,\theta_1)}{\partial\theta_1}=-2\sum_{i=1}^{m}(y^{(i)}-\theta_0-\theta_1x^{(i)})x^{(i)} = 0\tag{2.2} \]聯立兩式，求解可得：
\[\theta_0 =\frac{\sum_{i=1}^m(x^{(i)})^2\sum_{i=1}^my^{(i)}-\sum_{i=1}^mx^{(i)}\sum_{i=1}^mx^{(i)}y^{(i)}}{m\sum_{i=1}^m(x^{(i)})^2-\sum_{i=1}^mx^{(i)}(\sum_{i=1}^mx^{(i)})^2} \tag{2.3} \]\[\theta_1 =\frac{m\sum_{i=1}^mx^{(i)}y^{(i)}-\sum_{i=1}^mx^{(i)}\sum_{i=1}^my^{(i)}}{m\sum_{i=1}^m(x^{(i)})^2-\sum_{i=1}^mx^{(i)}(\sum_{i=1}^mx^{(i)})^2} \tag{2.4} \]對于圖1中的例子，代入公式\((2.3)\)和\((2.4)\)進行結算得，\(\theta_0 = 3.5, \theta_1=1.4,J(\theta) = 4.2\)，
對于n維特征的樣本，同樣可以采用這種方式來求解，對于特征維度\((x_1,x_2, \cdots,x_n)\)，我們增加一個第0維\(x_0=1\)，這樣增廣特征向量\(x = (x_0,x_1,\cdots,x_n)\)，增廣權向量為\(\theta = (\theta_0, \theta_1,\dots,\theta_n)\).
此時我們的擬合函式變為：
\[h_\theta(x) = \sum_{i=0}^n\theta_ix_i =\theta_0+ \theta_1x_1 + \cdots+\theta_nx_n \]損失函式變為：
\[J(\theta)=\sum_{j=1}^m(h_\theta(x^{(j)})-y^{(j)})^2=\sum_{j=1}^m(\sum_{i=0}^n\theta_ix_i^{(j)}-y^{(j)})^2 \]損失函式\(J(\theta)\)分別對\(\theta_i(i=0,1,\dots,n)\)求偏導，得：
\[\frac{\partial J(\theta)}{\partial\theta_i} = 2\sum_{j=1}^m(h_\theta(x^{(j)})-y^{(j)})x^{(j)}=2\sum_{j=1}^m(\sum_{i=0}^n\theta_ix_i^{(j)}-y^{(j)})x^{(j)}\quad (i=0,1,\dots,n) \]令偏導等于0，則有：
\[\sum{j=1}^m(\sum{i=0}^n\theta_ix_i^{(j)}-y^{(j)})x^{(j)}=0\quad (i=0,1,\dots,n) \]這樣最終得到的結果就是一個線性方程組，未知數的個數為n+1，方程的個數也為n+1，這樣就可以通過高斯消元法解出\(\theta_i(i=0,1,\dots,n)\)，具體可參見：詳解最小二乘法原理和代碼，
對于線性回歸問題，我們可以依據擬合函式的形式進行特征空間變換，即廣義線性回歸，例如，\(h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_2^2\)，我們可以令\(x_2:=x_2^2\)，這里\(:=\)表示賦值，即將右邊的值賦給左邊，這樣又變成了我們所熟悉的擬合函式形式，
對于非線性回歸問題，最小二乘法的思想同樣適用，只不過函式形式有所變化，例如，對于擬合函式\(h_\theta(x)=\theta_0+\theta_1x+\theta_2l nx\)，此時\(J(\theta)=\sum_{j=1}^m(h_\theta(x^{(j)})-y^{(j)})^2\)，求偏導的結果為：
\[\frac{\partial J(\theta)}{\partial\theta_i}=2\sum_{j=1}^{m}(h_\theta(x^{(j)})-y^{(j)})\frac{\partial h_\theta(x)}{\theta_i}\quad (i=0,1,2);其中\frac{\partial h_\theta(x)}{\theta_0} = 1, \frac{\partial h_\theta(x)}{\theta_2} = x, \frac{\partial h_\theta(x)}{\theta_2} = lnx \]同樣可以構造線性方程組，用高斯消元法求解，
3.矩陣求解最小二乘法
對于函式\(?_??(x)=??_0+??_1??_1+\dots+??_????_??\)，我們將其用矩陣表示為：
\[X\theta = Y \qquad \tag{3.1} \]其中，
\[X = \left\{\begin{matrix} (x^{(1)})^T \\ (x^{(2)})^T \\ \vdots \\(x^{(m)})^T \end{matrix} \right\} , Y = \left\{\begin{matrix} y^{(1)} \\ y^{(2)} \\ \vdots \\y^{(m)}) \end{matrix} \right\},x^{(j)}=\left\{\begin{matrix} x_0^{(j)}) \\ x_1^{(j)} \\ \vdots \\ x_n^{(j)} \end{matrix} \right\}, \theta = \left\{\begin{matrix} \theta_0 \\ \theta_1 \\ \vdots \\ \theta_n \end{matrix} \right\} \]m表示樣本個數，n為特征維度，\(x_0^{(i)}=1\quad(i = 0,1,\dots,m)\)，即\(X\)的第一列全為1，\(x_i^{(j)}\)表示第j個樣本的第i個特征，\(X\)為增廣樣本矩陣((1+n)*m維)，\(Y\)為真實值組成的列向量，
損失函式表示為：
\[J(\theta)=\sum_{j=1}^m(h_\theta(x^{(j)})-y^{(j)})^2=(X\theta?Y)^T(X\theta?Y) \tag{3.2} \]根據最小二乘法，利用矩陣求導得：（具體推導參見線性回歸矩陣推導和線性回歸相關向量求導）
\[\frac{\partial J(\theta)}{\partial\theta}=2X^T(X\theta-Y) \]令求導結果等于0矩陣，可得：
\[X^TX\theta = X^TY\quad\Rightarrow \quad \theta = (X^TX)^{-1}X^TY \tag{3.3} \]對于圖1中的例子，利用公式\((3.3)\)計算得：\(\theta = \left\{\begin{matrix} 3.5 \\1.4\end{matrix} \right\}\)
4.總結
最小二乘法可以直接求解引數矩陣，在計算時可以直接套入公式，但是仍有一定的局限性，主要體現在：
1.\(X^TX\)的逆矩陣可能不存在，這個在Matlab中，可以通過求偽逆來進行計算，
2.對于\((3.1)\)式，可以將其看成一個線性方程組（假設各方程線性無關），如果樣本個數m小于特征維數n，那么此方程組有無窮多個解，如果m = n，有唯一解，如果m大于n，無解（即存在矛盾解），最小二乘法一般是在m大于n的時候使用，此時求出來的解是最優近似解，
3.最小二乘法的時間復雜度為\(O(n^3)\)，當n特別大的時候（一般大于10000），求逆矩陣的程序非常復雜，此時采用最小二乘法，會非常耗時，
參考鏈接：
最小二乘法小結
半小時學習最小二乘法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/131564.html
標籤：其他