Andrew Ng Machine Learning - Week 三：Logistic Regression & Regularization_GIS

Andrew Ng Machine Learning - Week 3：Logistic Regression & Regularization

此文是斯坦福大学，机器学习界 superstar — Andrew Ng 所开设的 Coursera 课程：Machine Learning 的课程笔记。力求简洁，仅代表本人观点，不足之处希望大家探讨。
课程网址：https://www.coursera.org/learn/machine-learning/home/welcome

Week 1: Introduction 笔记：http://blog.csdn.net/ironyoung/article/details/46845233
Week 2：Linear Regression with Multiple Variables笔记：http://blog.csdn.net/ironyoung/article/details/47129523

Week 3：Logistic Regression & Regularization

Logistic Regression
1. 对于分类问题而言，很容易想到利用线性回归方法，拟合之后的 $h_{\theta}(x)>0.5$ 则为True，其余为False.
2. 但是线性回归有一个问题，拟合出的值都是离散的，范围不确定。为了方便分析，我们希望将拟合出的值限制在0~1之间。因此，出现了逻辑回归。
3. 逻辑回归的模型是一个非线性模型：sigmoid函数，又称逻辑回归函数。但它本质上又是一个线性回归模型，因为除去sigmoid映射函数关系，其他的步骤，算法都是线性回归的。
4. sigmoid函数（或，逻辑回归函数）：g(z)=1/(1+e?z)。其函数图像为：
  
  这个函数的特征非常明显
  - 函数值一直在0~1范围内；
  - 经过 $(0, 0.5)$ 点。这个很容易作为区分0，1类的分界线。
5. 逻辑回归中，对于原本线性回归中拟合而成的hypothesis函数，需要经过sigmoid函数的修饰：hθ(x)=θTx?hθ(x)=g(θTx)
  此时，hθ(x)的含义发生了变化，hθ(x)=P(y=1|x;θ)。成为
  - ”the probability that y=1, given x, parameterized by $\theta$ ”
  - 因此有， $P(y=0|x;\theta) + P(y=1|x;\theta) = 1$
6. Decision Boundary。表示的是 hypothesis 函数确定之后，划分数据分类的界限，并不一定可以百分百区分数据集，只是函数的属性之一。下图蓝色曲线即为某个 Desicision Boundary。
Cost Function
1. 回忆线性回归的 cost function，我们在其中插入 cost 函数的概念： $J({\theta _0},{\theta _1}) = \frac{1}{2m}\sum\limits_{i = 1}^m {{{({h_\theta }({x^{(i)}}) - {y^{(i)}})}^2}} \\ = \frac {1}{m}\sum\limits_{i = 1}^m {cost({h_\theta(x^{(i)}) }, {y^{(i)}})} =\frac {1}{m}\sum\limits_{i = 1}^m {cost({h_\theta(x) }, y)}$
2. 完全照搬线性回归的 cost function 到逻辑回归中，因为sigmoid函数的非线性，会造成 $J(\theta)$ 取值的不断震荡，导致其是一个非凸形函数（non-convex）。表示在“ $J(\theta)—\theta$ ”二维图中如下：
3. 我们需要构造一种新的 cost 函数。出发点为：
  - 当 $y=1$ 时，若hypothesis函数拟合结果为0，即为“重大失误”，cost 趋于无穷大；
  - 当 $y=0$ 时，若hypothesis函数拟合结果为1，即为“重大失误”，cost 趋于无穷大；
4. 构造的新 cost 函数：
  $c o s t (h θ (x), y) = {? l o g (h θ (x)), y = 1 ? l o g (1 ? h θ (x)), y = 0$ $cost({h_\theta(x) }, y)=\left\{ \begin{aligned} -log(h_{\theta}(x)) ,y=1 \\ -log(1-h_{\theta}(x)) ,y=0 \end{aligned} \right.$
  如果进一步合并，可以得到最终逻辑回归的cost函数。并且值得指出的是，代入这个cost函数通过梯度下降法得到的 $\theta$ 更新函数依然成立：
  
  $cost({h_\theta(x) }, y)= -ylog(h_{\theta}(x)) - (1-y)log(1-h_{\theta}(x))$
  ${\theta _j}: = {\theta _j} - \alpha \frac{1}{{m}}\sum\limits_{i = 1}^m [{{{({h_\theta }({x^{(i)}}) - {y^{(i)}})}}}x_j^{(i)}]$
梯度下降法的优化
1. 对于梯度下降法的优化有很多，但是都需要 $J(\theta)$ 与 $\frac{\partial J(\theta)}{\partial \theta_j}$ 的代码。
2. 以此为基础的对于梯度下降法的优化（视频中都没有具体介绍，有兴趣的同学可以点击链接）有：
  - 共轭梯度法：https://en.wikipedia.org/wiki/Conjugate_gradient_method
  - BFGS：https://en.wikipedia.org/w/index.php?title=Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm&redirect=no
  - L-BFGS：https://en.wikipedia.org/wiki/Limited-memory_BFGS
3. 这些优化方法的特点也很一致：
  - 不需要人为选择 $\alpha$ ，自适应性
  - 更复杂，更慢
4. 这里提到了两个MATLAB的非线性优化函数：
  - optimset：创建或编辑一个最优化参数选项。具体调用在MATLAB中 help optimset 命令查看；
  - fminunc：最小值优化。具体调用在MATLAB中 help fminunc 命令查看；
5. 个人建议：Ng在优化这一部分讲的过于简略，基本等于什么都没说……还是要根据这几个方法名称在使用时搜索更多。
one vs. all (one vs. rest)
1. 如果需要进行多类的分类，需要一种精妙的修改，使得两类的分类问题得以适用于多类的分类。
  - 现已知有n类样本需要区分开（1，2，3，……）；
  - 以原1类为新1类，剩余的原2，3，……作为新2类。原本的多类问题变成了二类问题， $h_{\theta}^{(1)}(x)=P(y=1|x;\theta)$ ；
  - 以原2类为新1类，剩余的原1，3，……作为新2类。再分类， $h_{\theta}^{(2)}(x)=P(y=2|x;\theta)$ ；
  - …… $h_{\theta}^{(i)}(x)=P(y=i|x;\theta)$ ；
  - 对于任意一个 $x$ 而言，如何分辨是哪一类呢？于是，求出所有的 $h_{\theta}^{(1)}(x)，h_{\theta}^{(2)}(x)，h_{\theta}^{(3)}(x)，……，h_{\theta}^{(n)}(x)$ ，值最大对应的 $i$ （表示 $y=i$ 的概率最大）即为 $x$ 的所属分类
Regularization（正则化）
1. 拟合会产生三种情况：
  - underfitting（欠拟合）=high bias，大部分训练样本无法拟合
  - overfitting（过拟合）=high variance，为了拟合几乎每一个训练样本。导致拟合函数极为复杂，易产生波动，泛化（generalize）能力差，虽然训练样本几乎百分百拟合，但是测试样本很可能因为极大波动而极少拟合成功
  - just right，对于训练样本，拟合得不多不少刚刚好，并且泛化到测试样本拟合效果同样较好
2. 欠拟合，比较好解决，创造并引入更多的特征即可。例如：对于 $x,y$ 而言，可以引入 $x^2,y^2,xy$ 等等新的特征
3. 过拟合，则比较复杂。可用的方法有两个：
  - Reduce number of features，降维（PCA？）
  - Regularization，正则化。保持所有的特征数量不变，而去改变特征前的度量单位 $\theta_j$ （若 $\theta_j$ 趋于0，则此特征可视为无影响）
4. 解决过拟合的正则化方法，因此需要引入全新的优化目标到 cost function 中。原先的 cost function 只是希望适合拟合更为接近，现在还需要使得特征前的度量单位 $\theta_j$ 的最小。因此有：
  
  $J({\theta _0},{\theta _1}) = \frac{1}{2m}[\sum\limits_{i = 1}^m {{{({h_\theta }({x^{(i)}}) - {y^{(i)}})}^2}}+\lambda\sum\limits_{i = 1}^m{\theta_{j}^2}]$
5. 正则化方法处理之后， $\frac{\partial J(\theta)}{\partial \theta_j}$ 发生对应变化，因此我们有：
  
  ${\theta _j}: = {\theta _j} - \alpha [(\frac{1}{{m}}\sum\limits_{i = 1}^m {{{({h_\theta }({x^{(i)}}) - {y^{(i)}})}}}x_j^{(i)})+\frac{\lambda}{{m}}\theta_{j}]\\:={\theta _j}(1 - \alpha \frac{\lambda}{{m}}) - \alpha \frac{1}{{m}}\sum\limits_{i = 1}^m {{{({h_\theta }({x^{(i)}}) - {y^{(i)}})}}}x_j^{(i)}$
6. 若 $\lambda$ 非常大（例如 $10^{10}$ ），则正则化方法会导致结果 underfitting。这也很好理解，因为优化目标中有使得 $\lambda\sum\limits_{i = 1}^m{\theta_{j}^2}$ 尽可能小，这样会导致 $\theta$ 全部趋于 0。一般来说， $\alpha, \lambda, m > 0$ ，所以 $(1 - \alpha \frac{\lambda}{{m}})<1$ ，常见使其取值0.99 左右
Regularization for Normal Equation
- 课程视频中缺少证明，因此我们仅需掌握结论使用即可
- 对于 Week 2 中的Normal Equation方法，原本需要求解的方程 $\theta = (x^{T}x)^{-1}x^{T}y$ 做一个小小的改动：
  
  $\theta = (x^{T}x + \lambda\begin{equation} \left( \begin{array}{cccccc} 0 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1\\ \end{array} \right) \end{equation})^{-1}x^{T}y$
  若样本拥有n个特征，则 $\begin{equation} \left( \begin{array}{cccccc} 0 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1\\ \end{array} \right) \end{equation}$ 表示的是(n+1) * (n+1)维的对角矩阵，除了(0, 0)取值为 0，其余对角位置取 1。
- non-invertibility：非不可逆性……好拗口，意思就是对于原本的 $(x^{T}x)$ 矩阵可能会出现不可逆的情况。但是，对于正则化之后的矩阵 $(x^{T}x + \lambda\begin{equation} \left( \begin{array}{cccccc} 0 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1\\ \end{array} \right) \end{equation})$ 一定是可逆的（未提供证明）。

编程作业答案：https://github.com/cnauroth/machine-learning-class