The Normal Equations
要找 \(J\) 的最小值除了 gradient descent 演算法之外，還有許多方式，這裡介紹另一個方法，使用這個方法直接使用 explict 的方式算出最小值，這樣可以不需要使用遞迴的方式。在這個方法中，我們直接把 \(J\) 對每個 \(\theta_j\) 做微分，然後將其設定為零，為了簡化代數的推導，我們先介紹一些微積分的矩陣表示法。
矩陣的微分
假設 \(f\) 是一個從 \(\mathbb{R}^{m\times n}\) 映射到 \(\mathbb{R}\)（也就是從 \(m\times n\) 的矩陣映射到實數）的函數，則 \(f\) 對矩陣 \(A\) 的微分定義為：\[\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)\]
所以事實上這個 gradient \(\nabla_Af(A)\) 本身也是一個 \(m\times n\) 的矩陣，其中第 (\(i\), \(j\)) 個元素為 \(\partial f/\partial A_{ij}\)，例如假設
\[A=\left(
\begin{array}{ccc}
A_{11}&A_{12}\\
A_{21}&A_{22}
\end{array}
\right)\]
而 \(f : \mathbb{R}^{2\times 2} \mapsto \mathbb{R}\) 定義為
\[f(A)=\frac{3}{2}A_{11}+5A^2_{12}+A_{21}A_{22}\]
其中 \(A_{ij}\) 代表矩陣 \(A\) 中的第 (\(i\), \(j\)) 個元素。則我們可以得到
\[\nabla_Af(A)= \left(
\begin{array}{cc}
\frac{3}{2}&10A_{12}\\
A_{22}&A_{21}
\end{array}
\right)\]
矩陣的 trace
接著我們介紹矩陣的 trace 運算子（表示成「tr」），對於一個 \(n\times n\) 的方陣 \(A\)，它的 trace 定義為對角線上元素的總和\[tr(A)=\sum_{i=1}^nA_{ii}\]
如果 \(a\) 是一個實數（也就是 \(1\times 1\) 的矩陣），則 \(tr(a) = a\)。
trace 運算子有一些特性，例如如果有有兩個方陣 \(A\) 與 \(B\)，則我們可以推導出 \(tr(AB)=tr(BA)\)，進而得到
\[tr(ABC) = tr(CAB) = tr(BCA)\\
tr(ABCD) = tr(DABC) = tr(CDAB) = tr(BCDA)\]
另外還有一些簡單的性質也可以很容易推導出來，如果 \(A\) 與 \(B\) 為方陣，而 \(a\) 為實數，則
\begin{align*}
tr(A)&=tr(A^T)\\
tr(A + B)&=tr(A) + tr(B)\\
tr(aA)&=atr(A)
\end{align*}
經過一推推導後，可以得到下面這些矩陣微分的等式
\begin{align}
\nabla_Atr(AB)&=B^T\label{eq:eq1}\\
\nabla_{A^T}f(A)&=(\nabla_Af(A))^T\label{eq:eq2}\\
\nabla_Atr(ABA^TC)&=CAB+C^TAB^T\label{eq:eq3}\\
\nabla_A|A|&=|A|(A^{-1})^T\label{eq:eq4}
\end{align}
最後的第 \eqref{eq:eq4} 條方程式只適用於 \(A\) 是 non-singular 方陣的情況，其中 \(|A|\) 是代表 \(A\) 矩陣的行列式（determinant）。
假設我們有一個固定的矩陣 \(B \in \mathbb{R}^{n\times m}\)，我們可以定義一個函數 \(f: \mathbb{R}^{m\times n} \mapsto \mathbb{R}\) 為
\[f(A)=tr(AB)\]
這樣的定義是有意義的，因為對所有的 \(A\in\mathbb{R}^{m\times n}\)，\(AB\) 就會是一個方陣，就樣就可以適用於 trace 運算子，也就是把 \(\mathbb{R}^{m\times n}\) 映射到 \(\mathbb{R}\)，接著我們對其進行微分，就可以得到 \(\nabla_Af(A)\) 這個 \(m\times n\) 的矩陣，上面第 \eqref{eq:eq1} 條等式告訴我們這個矩陣的第 (\(i\), \(j\)) 個元素會等於 \(B^T\) 的第 (\(i\), \(j\)) 個元素，也就是 \(B_{ji}\) 。
詳細的證明這裡就跳過了，若要找詳細的證明在一般線性代數的書中應該都會有。
Least Squares
接著我們可以開始使用矩陣的表示法來推導 \(\theta\) 在 \(J(\theta)\) 達到最小時的解析解，首先我們把 \(J\) 改用矩陣的形式表示。若給定一組 training set，我們定義它的 design matrix \(X\) 為一個 \(m\times n\) 的矩陣（如果將截距項也算進去，就是 \(m\times (n+1)\) 的矩陣）：\[X=\left(
\begin{array}{c}
(x^{(1)})^T\\
(x^{(2)})^T\\
\vdots\\
(x^{(m)})^T
\end{array}
\right)\]
其中每一個 \((x^{(i)})^T\) 都是一個列向量（row vector），代表第 \(i\) 筆 training example。而 \(\vec{y}\) 定義為一個 \(m\) 維的向量，其中包含所有 training set 的目標變數：
\[\vec{y}=\left(
\begin{array}{c}
y^{(1)}\\
y^{(2)}\\
\vdots\\
y^{(m)}\\
\end{array}
\right)\]
因為 \(h_\theta(x^{(i)})=(x^{(i)})^T\theta\)，所以可以得到
\[
X\theta-\vec{y}=\left(
\begin{array}{c}
(x^{(1)})^T\theta\\
\vdots\\
(x^{(m)})^T\theta
\end{array}
\right) - \left(
\begin{array}{c}
y^{(1)}\\
\vdots\\
y^{(m)}\\
\end{array}
\right)=\left(
\begin{array}{c}
h_\theta(x^{(1)})-y^{(1)}\\
\vdots\\
h_\theta(x^{(m)})-y^{(m)}\\
\end{array}
\right)
\]
因為對任何的 \(z\) 我們可以得到 \(z^Tz=\sum_iz_i^2\)，因此
\[
\frac{1}{2}(X\theta-\vec{y})^T(X\theta-\vec{y}) = \frac{1}{2}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2=J(\theta)
\]
最後配合前面矩陣微分公式的第 \eqref{eq:eq2} 條與第 \eqref{eq:eq3} 條，我們可以得到
\begin{equation}
\nabla_{A^T}tr(ABA^TC)=B^TA^TC^T+BA^TC
\label{eq:eq5}
\end{equation}
因此
\[
\begin{aligned}
\nabla_\theta J(\theta)=&\nabla_\theta\frac{1}{2}(X\theta-\vec{y})^T(X\theta-\vec{y})\\
=&\frac{1}{2}\nabla_\theta(\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^TX^TX\theta-\theta^TX^T\vec{y}-\vec{y}^TX\theta+\vec{y}^T\vec{y})\\
=&\frac{1}{2}\nabla_\theta(tr(\theta^TX^TX\theta)-1tr(\vec{y}^TX\theta)+\vec{y}^T\vec{y})\\
=&\frac{1}{2}(X^TX\theta+X^TX\theta-1X^T\vec{y})\\
=&X^TX\theta-X^T\vec{y}
\end{aligned}
\]
在第三行我們使用實數的 trace 就是他自己本身這個性質。第四行是使用 \(tr(A)=tr(A^T)\) 這個性質。第五行則是令 \(A^T=\theta\)、\(B=B^T=X^TX\)、\(C=I\) 然後使用第 \eqref{eq:eq5} 條與第 \eqref{eq:eq1} 條等式推導得到的（其中因為 \(\vec{y}^T\vec{y}\) 跟 \(\theta\) 沒有關係，所以微分之後就不見了）。
因為我們要要求 \(J\) 的極小值，所以令其微分等於零，即可得到這個 normal equation：
\[X^TX\theta=X^T\vec{y}\]
所以就可以得到 \(J\) 的極小值就發生在
\[\theta=(X^TX)^{-1}X^T\vec{y}\]
的時候。
這裡如果 \(X^TX\) 是一個 singular 矩陣的話（也是說某些資料可能有重複的問題），那它的反矩陣 \((X^TX)^{-1}\) 就會不存在，這時候可以使用 pseudo inverse 的方式處理。
繼續閱讀：史丹佛大學機器學習（Machine Learning）上課筆記（三）
沒有留言:
張貼留言