Andrew Ng机器学习课程笔记（第一至第三周）

本笔记基于Coursera上吴恩达（Andrew Ng）的机器学习课程内容集结而成。（课程链接）
全课程分为十一周，每周都有1-3个测验。第二周至第九周附有编程作业，一共8份。

第一周：

机器学习导论

机器学习定义：一个电脑程序从任务T学习，获得经验E来提升任务T的表现，整个过程用法方法P来衡量。（"A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E."）
监督学习(Supervised Learning)大致分为两种：回归和分类。机器学习需要已标签的数据用作模型训练。（已标签的数据是指预先知道输入和所对应输出的数据组。）
非监督学习(Unsupervised Learning)则并不知道训练数据的输出，而就是说，并不预先知道数据的结果。模型要透过数据来寻找数据之间的结构。

单一变量（单元变量）的线性回归（Linear Regression）

模型：输入单一一个变量x，给出相应的单一结果y。
假设函数(Hypothesis Function)：
\[ \hat y = h_\theta(x) = \theta_0 + \theta_{1}x \]
该方程将会是一条直线（\( y = a + bx\))。

代价函数（Cost function）

假设函数的准确性将用代价函数来衡量。
\[ J(\theta_0,\theta_1) = \frac{1}{2m} \sum_{i=1}^m (\hat{y_i} - y_i)^2 = \frac{1}{2m}\sum_{i=1}^m (h_{\theta}(x_i)-y_i)^2 \]
在\(\frac{1}{2}\bar{x}\)中，\(\bar{x}\)是指预测数值和实际数值的平均误差，也就是\((h_{\theta}(x_i)-y)^2\)的平均值。而\(\frac{1}{2m}\)是为了方便之后的微积分计算，因为\(\frac{1}{2}\)会在微积分计算中被约除。

梯度下降（Gradient Descent）

梯度下降法是用代价函数的梯度（slope），逐步修改参数。这样我们可以寻找出在最小误差/最大误差（global/local maximum/minimum**）下，参数的数值。
**(注：梯度下降法并不保证每次都能寻找到全域最大\最小值）
梯度下降的公式
\[\theta_j := \theta_j - \alpha\frac{\partial}{\partial\theta_j} J(\theta_0, \theta_1) \]
在单一变量的线性回归的梯度下降法则为：
\[\begin{gather}
\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}(h_\theta(x_{i}) - y_{i}) \cr
\theta_1 := \theta_1 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}((h_\theta(x_{i}) - y_{i}) x_{i})
\end{gather}\]
其中\(\alpha\)的数值是自行设定的，详细在后面讲解。梯度下降法将不停循环直至收敛。

第二周：

多变量的线性回归

在这个情况下，假设函数为：
\[h_\theta (x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3 + \cdots + \theta_n x_n\]
用矩阵表示：
\[h_\theta(x) =\begin{bmatrix}\theta_0 \hspace{2em} \theta_1 \hspace{2em} ... \hspace{2em} \theta_n\end{bmatrix}\begin{bmatrix}x_0 \newline x_1 \newline \vdots \newline x_n\end{bmatrix}= \theta^T x\]
注：课程中\(x_0\)的数值假设为1.
为了加快计算，推荐使用数组\(X\)来代替单一输入\(x\)的，这样就不用写循环来计算每一个单一\(x\)了。
假设\(X\)的由3个\(x\)组成，每一行代表一个\(x\)，每个\(x\)有1个变量。\(\theta\)依旧使用矩阵来表示。
\[X = \begin{bmatrix}x^{(1)}_0 & x^{(1)}_1 \newline x^{(2)}_0 & x^{(2)}_1 \newline x^{(3)}_0 & x^{(3)}_1 \end{bmatrix},\theta = \begin{bmatrix}\theta_0 \newline \theta_1 \newline\end{bmatrix}\]

新方法的计算公式为：
\[h_{\theta}(X)=X\theta\]

代价函数

新公式为：
\[J(\theta) = \frac{1}{2m}\sum_{i=1}^m (h_{\theta}x^{(i)}-y^{(i)})^2\]
使用矩阵计算的版本为：
\[J(\theta) = \frac {1}{2m} (X\theta - \vec{y})^{T} (X\theta - \vec{y})\]
其中，\(\vec{y}\)是所有y数值的向量。

多变量的梯度下降

梯度下降并没有改变，还是需要为每个参数做运算。
\[\begin{gather}
\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}(h_\theta(x^{(i)}) - y^{(i)}) \cdot x_{0}^{(i)}) \cr
\theta_1 := \theta_1 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}((h_\theta(x^{(i)}) - y^{(i)}) \cdot x_{1}^{(i)}) \cr
\theta_2 := \theta_2 - \alpha \frac{1}{m} \sum\limits_{i=1}^{m}((h_\theta(x^{(i)}) - y^{(i)}) \cdot x_{2}^{(i)}) \cr
...
\end{gather}\]
也就是说：
\[ \theta_j := \theta_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)} \hskip1em \text{for j := 0..n}\]
使用矩阵计算：
\[\theta := \theta - \frac{\alpha}{m} X^{T} (X\theta - \vec{y})\]

特征标准化（Feature Normalization）

如果数据特征的数值都在差不多的范围内的话，梯度下降法的速度将会加快。这是因为\(\theta\)会在小数值范围的时候下降得更快，在大数值范围的时候速度则变慢。所以当特征数值都不均匀的时候，计算效率会明显下降。
理想情况下，特征数值的范围应为：
\[-1 \le x_{(i)} \le 1\]
或者：
\[-0.5 \le x{(i)} \le 0.5\]
有两种方法可以达到这个效果，分别是：特征缩放(feature scaling)和均值归一(mean normalization)。两种方法合并的话，公式为：
\[x_i := \frac{x_i - \mu_i}{s_i}\]
\(\mu_i\)是所有特征(i)的平均数值。\(s_i\)是特征数值的范围（最大值-最小值），或者使用标准偏差(standard deviation)。

有关梯度下降法的提示

画图。\(J(\theta)\)为y轴，循环的次数为x轴，如果\(J(\theta)\)上升,说明\(\alpha\)的数值过大。
自动收敛测试。如果\(J(\theta)\)的下降值少于E，停止循环。E的数值应小于\(10^{-3}\)。

正规方程（Normal Equation）

使用正规方程可以直接计算出\(\theta\)的最优解，这方法并不需要循环。
公式为：
\[\theta = (X^{T} X)^{-1} X^{T} y\]

正规方程和梯度下降的对比

梯度下降	正规方程
需要选择\(\alpha\)	不需要选择\(\alpha\)
需要许多循环	不需要循环
\(O(kn^2)\)	\(O(n^3)\),需要计算\((X^{T}X)^{-1})\)
当\(n\)很大时，运算没有问题	当\(n\)很大时，运算变慢

正规方程中，不可逆矩阵（noninvertible）的计算方法
\(X^{T}X\)可能得出一个不可逆的矩阵。通常是因为特征之间线性相关（linear dependent），有些特征是多余的（Redundant）。或者因为矩阵中有过多的特征（e.g. \(m \le n\),特征的数量多于数据的的数量 )，这种情况下需要删除一些特征或者正规化数据（Regularization）。

使用'pinv'比使用'inv'更好。

第三周

逻辑回归

逻辑回归使用来处理分类问题。

二元分类（Binary Classification）

输出的结果y只会出现0或1。\(y \in {0, 1}\)通常0代表否，1代表是。
假设函数的范围：
\[0 \le h_{\theta}(x) \le 1 \]
假设函数是：
\[\begin{gather}
h_{\theta}(x) = g(\theta^{T}x) \cr
z = \theta^{T}x \cr
g(z) = \frac {1} {1 + e^{-z}}
\end{gather}\]
假设函数实际上给的是输出是1的几率。如果\(h_{\theta}(x) = 0.7 \)，即是说有70%的几率输出是1。
\[h_{\theta}(x) = P(y = 1|x; \theta) = 1 - P(y = 0|x; \theta)\]
\[P(y = 0|x; \theta) + P(y = 1|x; \theta) = 1 \]

决策边界

因为最终的结果只能是0或1，所以我们需要将\(h_{\theta}(x)\)的结果转换成0或者1。
\[\begin{gather}h_{\theta}(x) \ge 0.5 \rightarrow y = 1 \cr h_{\theta}(x) < 0.5 \rightarrow y = 0 \end{gather}\]
所以，可以这样表示：
\[\begin{gather}\theta^{T}x \ge 0 \Rightarrow y = 1 \cr \theta^{T}x < 0 \Rightarrow y = 0 \end{gather}\]

代价函数

逻辑回归的代价函数是：
\[\begin{gather} J(\theta) = \dfrac{1}{m} \sum_{i=1}^m Cost(h_\theta(x^{(i)}),y^{(i)}) \cr Cost(h_\theta(x),y) = -\log(h_\theta(x)) \hskip1em \text{if y = 1} \cr Cost(h_\theta(x),y) = -\log(1-h_\theta(x)) \hskip1em \text{if y = 0}
\end{gather}\]
将以上两条合并起来的话，得出的结果是：
\[Cost(h_{\theta}(x), y) = - y \space log(h_{\theta(x)}) - (1 - y)log(1 - h_{\theta}(x)) \]
使用矩阵运算的话：
\[\begin{gather}h = g(X\theta) \cr
J(\theta) = \frac{1}{m} \cdot (-y^{T}log(h) - (1 - y)^{T}log(1-h))
\end{gather} \]

梯度下降

梯度下降的公式为：
\[\theta_j := \theta_j - \alpha \dfrac{\partial}{\partial \theta_j}J(\theta)\]
把偏积分的公式扩展：
\[\theta_j := \theta_j - \frac{\alpha}{m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)}\]
使用矩阵运算：
\[\theta := \theta - \frac{\alpha}{m} X^{T} (g(X \theta ) - \vec{y})\]

多元分类

面对多元分类，需要做的只是为每个类别逐个做一次单独分类。
\[\begin{gather} y \in \lbrace0, 1 ... n\rbrace \cr h_\theta^{(0)}(x) = P(y = 0 | x ; \theta) \cr h_\theta^{(1)}(x) = P(y = 1 | x ; \theta) \cr \cdots \cr h_\theta^{(n)}(x) = P(y = n | x ; \theta) \cr \mathrm{prediction} = \max_i( h_\theta ^{(i)}(x) )\cr\end{gather}\]

正规化（Regularization）

欠拟合则是指假设函数不能很好得在现有数据上给出良好的结果。
过拟合问题是指假设函数能在现有数据上给出良好的结果，但是面对新的数据给出的结果却十分不理想。
能解决过拟合问题的方法有两种：

1. 减少特征的数量
   a. 人手挑选特征
   b. 使用模型选择算法
2. 正规化 - 在不减少特征的情况下，减少参数\(\theta_j\)的数值

正规化的线性回归

公式为：
\[min_\theta\ \dfrac{1}{2m}\ \left[ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})^2 + \lambda\ \sum_{j=1}^n \theta_j^2 \right]\]
梯度下降改为：
\[\begin{gather}
\theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \cr
\theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right]
\end{gather}\]
抽出分母：
\[\theta_j := \theta_j(1 - \alpha\frac{\lambda}{m}) - \alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)}\]
正规方程：
\begin{align*}& \theta = \left( X^TX + \lambda \cdot L \right)^{-1} X^Ty \newline& \text{where}\ \ L = \begin{bmatrix} 0 & & & & \newline & 1 & & & \newline & & 1 & & \newline & & & \ddots & \newline & & & & 1 \newline\end{bmatrix}\end{align*}
在原先的正规方程中，当\(m \le n\)，\(X^{T}X\)是不可逆的。加上\(\lambda \cdot L\)后，\(X^{T}X + \lambda \cdot L\)是可逆的。

正规化的逻辑回归

公式为：
\[J(\theta) = - \frac{1}{m} \sum_{i=1}^m [ y^{(i)}\ \log (h_\theta (x^{(i)})) + (1 - y^{(i)})\ \log (1 - h_\theta(x^{(i)}))] + \frac{\lambda}{2m}\sum_{j=1}^n \theta_j^2\]
注：第二个和，\(\sum_{j=1}^n \theta_j^2\)并不包括\(\theta_0\)，（\(\theta\)从0到n一共有n+1个数值），这个和跳过了\(\theta_0\)，从1计算到n。
梯度下降为：
\[\begin{gather}
\theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \cr
\theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right]
\end{gather}\]