史丹佛大學機器學習（Machine Learning）上課筆記（二）

本篇為史丹佛大學機器學習（Machine Learning）課程 Lecture 2 的後半段筆記，其接續上半段的內容。

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）上課筆記（三）