绪论：初识机器学习

3 监督学习

监督学习（Supervised Learning）：给出每个样例的“正确答案”

回归（regression）：预测连续值输出
分类（classification）：预测离散值输出

4 无监督学习

聚类（clustering）

单变量线性回归

6 模型描述

假设函数（Hypothesis）：要预测的函数

7 代价函数

假设函数：

$h_\theta (x_i)=\theta_0+\theta_1 x_i$

参数：

$\theta_0 , \theta_1$

平方误差代价函数：

$J(\theta_0,\theta_1)=\frac{1}{2m} \sum^m_{i=1} (h_\theta (x_i)-y_i)^2$

目标：

$minimize_{\theta_0,\theta_1} J(\theta_0,\theta_1)$

平方差对于大多数问题，特别是回归问题，都是一个合理的选择。当 $J(\theta_0,\theta_1)$ 取值最小的时候，也就是假设函数拟合最好的时候。

由于平方之后求导会多出一个常量2，所以代价函数乘以$\frac{1}{2}$正好可以消掉。

10 梯度下降

损失函数：$J(\theta_0,\theta_1)$

目标：$minimize_{\theta_0,\theta_1} J(\theta_0,\theta_1)$

思路：

随机初始化$\theta_0 , \theta_1$
持续改变$\theta_0 , \theta_1$以减小$J(\theta_0,\theta_1)$知道达到一个最小值。

使用梯度下降的时候每一次计算都朝着下降速度最快的方向，但是不同的初始值可能导致最后走向不同的局部最低点。

梯度下降算法（Gradient descent algorithm）
反复直到收敛（convergence）：

$\theta_j := \theta_j -\alpha \frac{d}{d \theta_j} J(\theta_0,\theta_1) \quad (for \\; j=0 \\; and \\; j=1)$

注意：同步更新
$temp_0 := \theta_0 - \alpha \frac{d}{d \theta_0} J(\theta_0,\theta_1) $
$temp_1 := \theta_1 - \alpha \frac{d}{d \theta_1} J(\theta_0,\theta_1) $
$\theta_0 := temp_0$
$\theta_1 := temp_1$

注解：
:=为赋值（assignment）符号
$\alpha$ 为学习率

11 梯度下降知识点总结

导数项决定斜率（slope）即下降方向始终朝向最小值。
如果当前 $\theta$ 已经在局部最小，则此处斜率为0，$\theta$ 将不会再改变。

如果学习率太小，会导致下降速度很慢，同时也可能陷入局部最优值（local optima）无法出来。
如果学习率太大，可能跨过最小值，导致无法收敛甚至发散（diverge）。

随着逼近局部最低点，斜率减小，此时每次更新的幅度也将随之自动变得越来越小，所以没必要改变 $\alpha$。

12 线性回归梯度下降

$\frac{d}{d \theta_j} J(\theta_0,\theta_1) = \frac{d}{d \theta_j} \frac{1}{2m} \sum^m_{i=1} (h_\theta (x_i)-y_i)^2 \\\\ \qquad\qquad\qquad\\; = \frac{d}{d \theta_j} \frac{1}{2m} \sum^m_{i=1} (\theta_0 + \theta_1 x_i - y_i)$

分别求导：
$\theta_0 : \frac{d}{d \theta_0} J(\theta_0,\theta_1) = \frac{1}{m} \sum^m_{i=1} (h_\theta (x_i)-y_i) $
$\theta_1 : \frac{d}{d \theta_1} J(\theta_0,\theta_1) = \frac{1}{m} \sum^m_{i=1} (h_\theta (x_i)-y_i)\cdot x_i$

$\theta_0 := \theta_0 - \alpha \frac{1}{m} \sum^m_{i=1} (h_\theta (x_i)-y_i) $
$\theta_1 := \theta_1 - \alpha \frac{1}{m} \sum^m_{i=1} (h_\theta (x_i)-y_i)\cdot x_i$

凸函数（convex function）只有一个局部最优解。

“Batch” 梯度下降：意味着每一步下降都会使用整个训练集的样本。

多变量线性回归

28 多特征

注解：
$x^{(i)}$：第i个训练数据。
$x^{(i)}_j$：第i个训练数据中的第j个特征值。

新的假设函数：

$h_\theta (x)=\theta_0 + \theta_1 x_1 + \theta_2 x_2 + \dots +\theta_n x_n$

对于每个数据样例都有一个$x^{(i)}_0=1$

29 多元梯度下降

$\theta_j := \theta_j - \alpha \frac{1}{m} \sum^m_{i=1} (h_\theta (x^{(i)})-y^{(i)})x^{(i)}_j$

因为$x^{(i)}_0=1$，所以仍与之前的一元算法等效。

30 多元梯度下降法演练I——特征缩放

如果不同的特征值在相近的范围内，这样梯度下降法就能更快的收敛。
通常我们在进行特征缩放的时候将范围大致限定在$-1\le x_i \le 1$范围内。

均值归一化（mean normalization）
将 $x_i$ 替换为 $x_i-\mu_i$ 以使得特征值有接近于0的均值。但是不要将其应用到 $x_0$ 上，应为 $x_0$ 恒为1，不可能有为0到平均值。

通常我们使用如下式子：

$x_i := \frac{x_i - \mu_i}{range_i}$

注解：
$x_i$：第i个特征值。
$\mu_i$：第i个特征值的均值。
$range_i$：第i个特征值的取值范围的长度（最大值减去最小值）。

缩放不必特别精准，只要收敛速度加快就行了。

31 多元梯度下降法演练II——学习率

通过绘制迭代次数与最小损失值（$min_\theta J(\theta)$）的函数曲线，可以判断梯度下降算法是否正常运行。当曲线趋近于平坦的时候就代表差不多收敛了。

同样也可以使用自动检测算法通过判断在一次迭代后 $J(\theta)$ 是否小于某一阈值 $\varepsilon$ 来判断是否收敛。但是阈值的取值通常难以确定，所以还是直接绘图观察比较好。

如果观察到 $J(\theta)$ 曲线在上升或者在上下震荡，通常的办法是降低学习率 $\alpha$。
在 $\alpha$ 足够小的时候，$J(\theta)$ 应当在每一轮迭代后下降。但是如果 $\alpha$ 太小，那么梯度下降的收敛速度将非常慢。

在选取 $\alpha$ 的时候，我们从 $\dots , 0.001 , 0.01 , 0.1 , 1 ,\dots$ 每隔10倍取值尝试，然后绘图观察，选取一个下降最快的 $\alpha$ 。

32 特征和多项式回归

多项式回归（polynomial regression）

$h_\theta (x) = \theta_0 + \theta_1 x + \theta_2 x^2 + \theta_3 x^3$

在这种情况下特征缩放就非常重要，这样才能将值的范围变得具有可比性。

33 正规方程（区别于迭代方法的直接解法）

正规方程（normal equation）：直接求解 $\theta$ 最优值的方法即多元微分求极值。

$\theta = (X^T X)^{-1} X^T y$

注解：
$m$ 个训练样本， $n$ 个特征。
X：所有特征的矩阵，其中$x_0=1$ ，所以其尺寸为：$m \times (n+1)$。
y：所有样例的标签向量。

使用正规方程进行计算的时候就不用进行特征缩放。

梯度下降	正规方程
需要选择$\alpha$	不需要选择$\alpha$
需要很多次迭代	不需要迭代
当 $n$ 很大的时候也能很好的工作	需要计算 $(X^T X)^{-1}$
	当 $n$ 很大的时候会很慢(矩阵计算的代价以$O(n^3)$ 增长)

当特征数量小于10000的时候，我们通常使用正规方程

34 正规方程在矩阵不可逆情况下的解决方案

一般矩阵不可逆的情况可能发生在：

存在冗余的特征，线性相关（linearly dependent）
特征太多了（e.g. $m\le n$）
- 删掉一些特征或者进行正规化（regularization）

Logistic回归

47 假设陈述

Sigmoid function和Logistic function 是同义词，可以互换。

$g(z)=\frac{1}{1+e^{-z}}$

Logistic回归模型
期望 $0\le h_\theta (x) \le 1$:

$h_\theta (x) = g(\theta^T x)=\frac{1}{1+e^{-\theta^T x}}=P(y=1 | x;\theta )$

48 决策界限

决策边界是假设函数的一个属性，决定于其参数，它不是数据集的属性。

49 代价函数

线性回归代价函数：

$Cost(h_\theta (x),y)=\frac{1}{2}(h_\theta (x) - y)^2$

Logistic回归代价函数：

$Cost(h_\theta (x),y)= \begin{cases} -\log (h_\theta (x)) & \textrm{if y=1} \\\\ -\log (1-h_\theta (x)) & \textrm{if y=0} \end{cases}$

当 $y=1,h_\theta (x) =1$ 时 $Cost=0$ ，但是当 $h_\theta (x) \to 0$ 时 $Cost \to \infty$。

$y=0$时同理。
上图显示出，当预测错误的时候，我们会用一个很大的代价值来惩罚学习算法。

50 简化代价函数与梯度下降

由定义可知总有 $y=0$ 或 $y=1$ ，所以可以对代价函数做如下简化：

$Cost(h_\theta (x),y)=-y\log (h_\theta (x))-(1-y)\log (1-h_\theta (x))$

梯度下降

$J(\theta)=-\frac{1}{m}\left [\sum_{i=1}^m y^{(i)}\log (h_\theta (x^{(i)}))+(1-y^{(i)})\log (1-h_\theta (x^{(i)})) \right ]$

期望$min_\theta J(\theta)$：
重复执行并同步更新$\theta_j$

$\theta_j := \theta_j - \alpha \sum_{i=1}^m (h_\theta (x^{(i)})-y^{(i)})x_j^{(i)}$

此处Logistic回归与线性回归的看似很像但区别在于 $h_\theta (x)$ 不同：

线性回归：$h_\theta (x)=\theta^T X$
Logistic回归：$h_\theta (x) = \frac{1}{1+e^{-\theta^T X}}$

使用向量化的计算可保证同步更新。

51 高及优化

除梯度下降以外的优化算法还有：

共轭梯度法（Conjugate gradient）
BFGS
L-BFGS

这三种方法的优点在于：

不需要手动选择学习率$\alpha$，每一次迭代它们都会使用线搜索算法找到最优的学习率。
收敛速度快于梯度下降

缺点：更复杂

52 多元分类：一对多

对于多分类问题，我们可以将问题处理为多个二分类：1对多余

这样我们就得到了输入样例对每一类的概率，最终我们选取概率最高的一个作为它的分类结果。

正则化

55 过拟合问题

欠拟合（underfitting），过拟合（overfitting）

解决过拟合

减少特征数量
1. 手工选择某些特征保留
2. 模型选择法
正则化（regularization）
1. 保留所有特征，但是减少参数 $\theta_j$ 的量级/值
2. 当我们有很多特征，每一个特征都对预测有一点帮助的时候，这个方法会工作的很好。

56 代价函数

正则化

$J(\theta)=\frac{1}{2m}\left [ \sum_{i=1}^m (h_\theta (x^{(i)}) - y^{(i)})^2+ \lambda \sum_{j=1}^n \theta_j^2 \right ]$

$\lambda$是正则化参数，用于控制两个不同目标之间的取舍，既要拟合目标函数，又要保持参数尽量的小，保持假设模型相对简单。
如果$\lambda$太大，将导致惩罚太大，最终欠拟合。

一般不对$x_0$进行正则化。

57 线性回归的正则化

梯度下降
重复执行：

由于$\alpha、\lambda$都大于0，且$\alpha$很小，则$\alpha \frac{\lambda}{m}<1$，所以本质上加了正则项以后的式子相对于没加之前的式子在每一次迭代的时候都将$\theta$乘了一个比1略小的数。

正规方程

$\theta = \left (X^TX + \lambda \underbrace{ \left [ \begin{array}{cccc} 0 & 0 & \ldots & 0 \\\\ 0 & 1 & \ldots & 0 \\\\ \vdots & \vdots & \ddots & 0 \\\\ 0 & 0 & 0 & 1 \end{array} \right ] }_{(n+1)\times (n+1)} \right )^{-1} X^Ty$

只要保证 $\lambda$ 大于0，则加上正则项以后的矩阵必可逆。

61 Logistic回归的正则化

$J(\theta)=-\frac{1}{m} \left [\sum_{i=1}^m y^{(i)}\log (h_\theta (x^{(i)}))+(1-y^{(i)})\log (1-h_\theta (x^{(i)})) \right ]+\frac{\lambda}{2m} \sum_{j=1}^n \theta^2_j$

梯度下降
重复执行：

神经网络学习

62 非线性假设

当使用Logistic回归做非线性假设的时候，参数的数量会随着特征值数量n以$O(n^2)$的规模增长。当在计算图像数据的时候，参数的规模会超过百万以上，此时使用Logistic回归计算会非常慢。所以我们选用神经网络来实现。

64 模型展示 I

$x_0$ 被称为偏置单元或偏置神经元，取值为1。
$\theta$ 在此处一般被称之为权重。

在神经网络中，第一层被称为输入层，最后一层被称为输出层，中间的都被称为隐藏层。

$a_1^{(2)}=g(\theta_{10}^{(1)}x_0+\theta_{11}^{(1)}x_1+\theta_{12}^{(1)}x_2+\theta_{13}^{(1)}x_3) \\\\ a_2^{(2)}=g(\theta_{20}^{(1)}x_0+\theta_{21}^{(1)}x_1+\theta_{22}^{(1)}x_2+\theta_{23}^{(1)}x_3) \\\\ a_3^{(2)}=g(\theta_{30}^{(1)}x_0+\theta_{31}^{(1)}x_1+\theta_{32}^{(1)}x_2+\theta_{33}^{(1)}x_3)$ $h_\theta (x) = g(\theta_{10}^{(2)}a_0^{(2)}+\theta_{11}^{(2)}a_1^{(2)}+\theta_{12}^{(2)}a_2^{(2)}+\theta_{13}^{(2)}a_3^{(2)})$

每一个神经元都是一个激活函数。则整个神经网络的参数数量就是每一层参数数量的乘积。

65 模型展示 II

从输入层到计算出$h_\theta (x)$ 的过程称为前向传播。
神经网络所做的事其实就和Logistic回归一样，只不过输入值变成了上一层网络的输出值。

神经网络参数的反向传播算法

72 代价函数

线性回归：

$J(\theta)=-\frac{1}{m} \left [\sum_{i=1}^m y^{(i)}\log (h_\theta (x^{(i)}))+(1-y^{(i)})\log (1-h_\theta (x^{(i)})) \right ]+\frac{\lambda}{2m} \sum_{j=1}^n \theta^2_j$

神经网络：

73 反向传播算法

前向传播

反向传播（backpropagation）
$\delta_j^{(l)}$代表了第$l$层的第$j$个节点的误差。
对每一个输出计算（第四层网络）：
$\delta_j^{(4)}=a_j^{(4)}-y_j$，向量计算法：$\delta^{(4)}=a^{(4)}-y$
$\delta^{(3)}=(\Theta^{(3)})^T \delta^{(4)}\cdot g’(z^{(3)}),\\; g’(z^{(3)})=a^{(3)}\cdot (1-a^{(3)})$
$\delta^{(2)}=(\Theta^{(2)})^T \delta^{(3)}\cdot g’(z^{(2)}),\\; g’(z^{(2)})=a^{(2)}\cdot (1-a^{(2)})$

$\frac{\partial}{\partial \Theta_{ij}^{(l)}} J(\Theta) = a_j^{(l)} \delta_i^{(l+1)} \\; (忽略\lambda 或者 \lambda=0)$

算法总流程：

Training set {$(x^{(1)},y^{(1)}),\dots ,(x^{(m)},y^{(m)})$}
Set $\Delta_{ij}^{(l)}=0 \\; ($for all $l,i,j)$
For $i= 1$ to $m$
Set $a^{(1)}=x^{(i)}$
Perform forward propagation to compute $a^{(l)}$ for $l=2,3,\dots ,L$
Using $y^{(i)}$ ,compute $\delta^{(L)} = a^{(L)} - y^{(i)}$
Compute $\delta^{(L-1)},\delta^{(L-2)},\dots ,\delta^{(2)}$
$\Delta_{ij}^{(l)} := \Delta_{ij}^{(l)}+a_j^{(l)}\delta_i^{(l+1)}$
$D_{ij}^{(l)} := \frac{1}{m} \Delta_{ij}^{(l)} + \lambda \Theta_{ij}^{(l)}$ if $j\ne 0$
$D_{ij}^{(l)} := \frac{1}{m} \Delta_{ij}^{(l)}$ if $j = 0$

$\frac{\partial}{\partial \Theta_{ij}^{(l)}} J(\Theta) = D_{ij}^{(l)}$

74 理解反向传播

前向传播

反向传播
其实前向传播和反向传播非常相似，只是计算的方向不同。

要注意的是，在反向传播过程中，并不更新偏置单元。

76 梯度检测

梯度检测（gradient checking）用以检测前向传播和反向传播过程中出现的bug，主要是反向传播。

使用双侧差分而不是单侧差分，这样可以得到更精确的结果。$\varepsilon$不要取太小，以免遇到一些数值计算上的问题。

当我们把计算应用到参数向量上去的时候：

通过比较梯度检测运算出来的梯度和反向传播运算出来的梯度是否相近，可以判断我们训练得到的结果是否正确。

77 随机初始化

当我们使用梯度下降或一些高级算法的时候，我们需要对$\theta$选取一些初始值。
$\theta$可以全部被初始化为0，但是在实际训练中，全部初始化为0起不了任何作用。所有的初始值相同会导致最终每个节点在梯度下降以后的结果相同，这意味着所有的节点都在计算相同的特征，这是一种高度荣誉的现象。最终的输出结果只计算了一个特征，这种情况阻止了网络去学习其他特征。
所以我们在初始化的时候应该选取接近于0的随机初始值。

78 组合到一起

在进行神经网络训练之前，我们要选取一个合适的网络架构。
一般输入节点个数由你的数据集特征的维度所决定，输出节点个数取决于目标分类的个数。
对于应藏层，合理的默认值是一层应藏层，如果选择不止一层隐藏层的话将每层的节点个数设为相同，节点的个数越多越好，不过太多的话计算会很慢，一般设为输入层的几倍即可。

应用机器学习的建议

84 评估假设

将数据集划分成训练集和测试集，一般按照7:3的比例。

线性回归的训练测试流程

在训练集上学习参数$\theta$（最小化训练误差$J(\theta)$）

计算测试集误差：

$J_{test}(\theta)=\frac{1}{2m_{test}} \sum_{i=1}^{m_{test}} (h_\theta (x_{test}^{(i)})-y_{test}^{(i)})^2$

Logistic回归的训练测试流程

对于Logistic回归也可以像线性回归一样在训练集上学习参数$\theta$，然后在测试集上计算误差$J(\theta)$。

还有一种评估标准叫做错误分类：

$err(h_\theta (x),y)=\begin{cases} 1 & \textrm{if} \\; h_\theta(x) \ge 0.5, y=0 ; \textrm{or if} \\; h_\theta (x) < 0.5, y=1 \\\\ 0 & \textrm{otherwise} \end{cases} \\\\ Test_{error} = \frac{1}{m_{test}} \sum_{i=1}^{m_{test}} err(h_\theta (x_{test}^{(i)}),y_{test}^{(i)}))$

85 模型选择和训练、验证、测试集

由于需要测试模型的泛化能力，如果只划分训练集和测试集，则在训练集上训练，用测试集找出复杂程度最合适的模型，接下来我们将无法进行泛化能力的检测。所以要在划分一个交叉验证集（cross validation）出来。
一般训练、验证、测试集经典的划分比例为6:2:2。

接下来我们使用训练集训练模型，使用验证集来选择模型，使用测试集来验证模型的泛化能力。

86 诊断偏差与方差

当模型偏差高的时候，训练误差和验证误差都很高，原因是模型过于简单；当模型方差高的时候，训练误差很低，验证误差远大于训练误差，原因是模型过于复杂。

87 正则化和偏差、方差

当正则项$\lambda$过大的时候会导致模型过于简单偏差过高欠拟合，反之过小的时候会导致模型过于复杂方差过高过拟合。

89 学习曲线

随着训练样本的增加，训练误差会越来越大，要想拟合所有数据越来越难；而验证误差会逐渐减小，因为模型泛化能力增加了。

高偏差
对于高偏差情况，验证误差和训练误差都很大，随着训练集的增加会逐渐趋于平坦且很接近。对于高偏差情况继续增加训练样本并没有帮助。

高方差
对于高方差情况，一开始验证误差会很高，训练误差比较低，且两种误差之间间距很大。但随着样本数量的增加，训练误差逐渐增大，验证误差逐渐减小，慢慢靠近。所以在高方差情况下，增加训练样本是有帮助的。

91 决定接下来做什么

线性回归

方案	解决的问题
获取更多的训练样本	修正高方差
减少特征数量	修正高方差
增加特征	修正高偏差
增加多项式特征（复杂度）	修正高偏差
减小正则项$\lambda$	修正高偏差
增大正则项$\lambda$	修正高方差

神经网络
使用简单的神经网络，参数更少，计算量更小，但是容易欠拟合。

使用复杂的神经网络，更多的参数，计算量更大，更容易过拟合。但是可以使用正则项来解决过拟合问题，通常复杂网络加正则项的方案比使用简单的神经网络更好。

机器学习系统设计

94 误差分析

在系统设计上建议先使用一个简单粗暴的算法快速实现，然后进行误差分析，来了解你的模型主要是在哪些方面不足，这样能快速抓住后期工作的正确方向。
建议在交叉验证集上做误差分析而不是在测试集上。使用数值评估方法很重要。

95 不对称性分类的误差评估

当一类样本数量远低于另一类的时候，我们称其为偏斜类（skewed classes）。此时再使用精确度来评估模型将不再合适，而应使用查准率与召回率的度量标准。

	样本为真	样本为假
预测为真	真正例（TP）	假正例（FP）
预测为假	假反例（FN）	真反例（TN）

查准率：在我们预测为真的样本中，到底有多少真的为真样本。

$查准率=\frac{真正例}{预测为真的例子}=\frac{真正例}{真正例+假正例}$

召回率：我们所预测为真的样本占总的正样本

$召回率=\frac{真正例}{真实为真的例子}=\frac{真正例}{真正例+假反例}$

使用查准率与召回率，即便是在有偏斜类的情况下我们也能根据是否两项指标都很高来判断我们的算法是否很好。

96 精确度和召回率的权衡

根据不同的情况，我们有时需要高查准率，有时有需要高召回率。对于不同的查准率和召回率，如何去决定哪一个模型更好我们可以使用如下方法：

F1 Score

$F1 Score = 2\frac{PR}{P+R}$

	Precision(P)	Recall(R)	Average	F1 Score
Algorithm 1	0.5	0.4	0.45	0.444
Algorithm 2	0.7	0.1	0.4	0.175
Algorithm 3	0.02	1.0	0.51	0.0392

可以看出使用平均数并不是一个好的评估方法，而F1 Score的分子可以看出，只有在查准率和召回率都很高的时候得分才会很高。

98 机器学习数据

真正提高学习算法性能的方法是给予一个算法大量的训练数据，不同的算法可能会有细微的误差，但总的趋势都是随着数据量的增加从而性能提升。

支持向量机

101 优化目标

Logistic回归

$\min_\theta \frac{1}{m} \left [\sum_{i=1}^m y^{(i)}\log (h_\theta (x^{(i)}))+(1-y^{(i)})\log (1-h_\theta (x^{(i)})) \right ]+\frac{\lambda}{2m} \sum_{j=1}^n \theta^2_j$

支持向量机（SVM）

区别1：支持向量机去掉了常数项$\frac{1}{m}$,但对最终结果并不影响。
区别2:支持向量机使用$C$，而不使用$\lambda$。

注解：

n为特征数量，m为样本数量。

假设函数形式

$h_\theta (x) \begin{cases} 1 & \textrm{if}\\; \Theta^Tx \ge 0 \\\\ 0 & \textrm{otherwise} \end{cases}$

102 直观上对大间隔的理解

对于Logistic回归期望的是$\Theta^T x \ge 0$ 或者 $\Theta^T x < 0$ 即可做出分类。而支持向量机要求的更高，它希望$\Theta^T x \ge 1$ 或者 $\Theta^T x \le -1$。这就像是在支持向量机中构建了一个安全因子，一个安全间距。

SVM决策边界
把优化问题看作是通过选择参数来使得第一项等于0。

线性可分样例

黑色线条与蓝色线条的间距称为支持向量机的间距。相对于绿色和红色的线条，黑色线条会更加稳健，会尽量用大的间距去分离。所以有时支持向量机被称为大间距分类器。

但支持向量机（黑线）要比大间距分类器（红线）更复杂。当$C$很大的时候，支持向量机会从黑线变成红线，但$C$不是很大的时候支持向量机还是黑色这条线。如果数据不是线性可分的，支持向量机仍然可以正常工作。

103 大间隔分类器的数学原理

为简化证明，令：$\theta_0 = 0 , n=2$

$\min_\theta \frac{1}{2} \sum_{j=1}{n} \theta_j^2 = \frac{1}{2} (\theta_1^2+\theta_2^2) =\frac{1}{2} (\sqrt{\theta_1^2 + \theta_2^2})^2 = \frac{1}{2} \| \theta \|^2$ $\Theta^T x^{(i)}=P^{(i)}\| \Theta \| = \theta_1 x_1^{(i)}+\theta_2 x_2^{(i)}$

s.t.

$\begin{array}{cc} \Theta^T x^{(i)} \ge 1 \to p^{(i)}\cdot \| \theta \| \ge 1 & \textrm{if} \\; y^{(i)}=1 \\\\ \Theta^T x^{(i)} \le -1 \to p^{(i)}\cdot \| \theta \| \le -1& \textrm{if} \\; y^{(i)}=0 \end{array}$

参数向量$\Theta$实际上与决策边界成90度正交。因为令$\theta_0 = 0$，所以决策边界过原点。

在第一种决策边界下可以看到$p^{(1)}$和$p^{(2)}$长度都很小，所以为了使$p^{(1)} \cdot | \theta | \ge 1,p^{(2)}\cdot | \theta | \le -1$，$| \theta | $必须很大。但是我们的目标函数的优化方向是减小$| \theta | $，所以这种决策边界不会被选择。

同理，第二种决策边界的$| \theta | $计算出来会很小，所以这种决策边界会被选择。

104 核函数1

我们手动选取三个landmark，然后根据这三个landmark计算出新的特征。

$f_1 = \textrm{similarity}(x,l^{(1)})=\textrm{exp}\left (-\frac{\| x-l^{(1)} \|^2}{2\sigma^2} \right )=\textrm{exp}\left (-\frac{\sum_{j=1}^n (x_j-l_j^{(1)})^2}{2\sigma^2}\right )$

similarity函数我们称之为核函数，此处我们使用的是高斯核函数。为简化计算同样忽略$x_0$。

如果$x\approx l^{(1)}$:

$f_1\approx \textrm{exp}\left ( -\frac{0^2}{2\sigma^2} \right ) \approx 1$

如果$x$离$l^{(1)}$很远:

$f_1\approx \textrm{exp}\left ( -\frac{(\textrm{large number})^2}{2\sigma^2} \right ) \approx 0$

同样的对$f2,f3$进行计算，我们就由$l^{(1)},l^{(2)},l^{(3)}$转化得到了三个新的特征$f_1,f_2,f_3$。

$\sigma$是高斯核函数的一个参数，从下面这个样例中可以看出$\sigma$的不同取值的影响。

根据上面计算出的新特征进行计算，当样本落在红圈之内的时候预测为1，在外面的时候预测为0。

由此我们就通过landmark和核函数训练出了非常复杂的非线性决策边界。

105 核函数2

如何选取landmark
我们直接将所有样本都取为landmark，然后使用这些landmark对每一个样本计算出新的特征向量$f^{(i)}$，其中$f_0^{(i)}=1$。接下来使用这些新的特征向量进行训练即可。

训练

需要注意的一点是，在SVM实际实现中，最后一部分$\sum_{j=1}^m \theta^2_j$会略有不同。实际实现中，会用$\Theta^T$乘以某个矩阵M，这依赖于你采用的核函数，再乘$\Theta$，即$\Theta^T M \Theta$。这其实是另一种略有区别的距离度量方法，这其实是$| \Theta |^2$的缩放版本。这个数学上的优化使得SVM能更有效的运行在更大的训练集上，因为你将所有样版都作为了landmark，这样新的特征向量维度将会特别大，使用原来的式子计算量将会非常大。

其实也可以将核函数的方法应用在Logistic回归等其他算法上，但是因为没有了专门为SVM设计的那样的优化，计算起来会非常的慢。

如何调参
在进行SVM调参的时候，一个重要的优化目标是参数$C$，其作用和正则化参数$\lambda$相同。还有一个重要参数就是高斯核函数中的$\sigma$。

106 使用SVM

一般我们在使用用SVM的时候选取核函数最常用的两种就是线性核函数和高斯核函数，没有核函数其实也算是线性核函数。

并不是所有你选用的similarity函数都能作为核函数。核函数要满足默塞尔定理（Mercer’s Theorem）。这是因为在实现SVM并进行优化的过程中，都是将注意力集中在可以满足默塞尔定理的核函数上的。只有选取这样的核函数，你才能应用到现在大多数SVM软件包上去。

你还能选择的一些其他核函数：

一般线性核函数性能会比较差。如果你准备做一些文本分类就可以选择字符串核函数。

多分类
一般的SVM软件包里已经实现了多分类函数，你只需要调用就行了。

其实现思想还是one-vs-all。如果你需要分K类，你就要训练K个SVM，然后分别对每一类做预测最终得到一个onehot的向量。

Logistic回归 VS SVM
以n代表特征数，m代表样本数。

当n很大的时候（相对于m）：
使用Logistic回归或者使用无核SVM（线性核函数）

当n很小，m比较适中的时候：
使用高斯核函数的SVM

当n很小，m很大的时候：
添加更多特征，然后使用Logistic回归或者使用无核SVM（线性核函数）

无监督学习

109 K-Means算法

如果发现某一个聚类中心没有簇点，则可以直接移除那个聚类中心，但这样分类的个数会减小。如果确实要保留原有的分类个数，可以考虑重新随机初始化中心点。但更常规的做法是直接移除。

110 优化目标

111 随机初始化

直接随机选取K个样本作为初始的聚类中心是比较推荐的方法。

为了避免陷入局部最优解，要多次随机初始化，找到一个最好的结果。

112 选取聚类数量

到现在为止，最好的方法还是进行数据可视化然后人工选取。

手肘法

使用手肘法有时也并不能给出一个很好的结果。

有时我们使用K-Means是为了为下一个目标做准备。所以此时选取K值应该取决于选取哪一个分类数量会更好的服务于下一个目标。

降维

115 目标 I：数据压缩

降维是为了去除数据中高度冗余的特征。在节省空间的同时也加快了算法的运行速度。

116 目标 II：可视化

降维也可以方便进行数据可视化。

117 主成分分析问题规划1

对于降维问题，现在最流行最常用的一个算法叫做主成分分析方法（principal components analysis PCA）。

主成分分析要做的就是找到一个投影代价最小的平面对数据进行投影。在进行主成分分析之前，常规的做法是先进行数据均值归一化和特征规范化。

PCA会选取红色那条投影代价最小的平面，而不是洋红色那条。

为找到这样的平面，首先需要在n维数据中找到一个向量$\mu^{(1)}$，其向量的方向为正或为负无所谓。
尽管PCA看起来和线性回归很像，但是却是完全不同的算法。PAC最小化的是正交距离，而线性回归最小化的是平方差距离。

118 主成分分析问题规划2

数据预处理

均值归一化
特征规范化

PCA算法
协方差矩阵计算：

$\Sigma = \frac{1}{m} \sum_{i=1}^n (x^{(i)})(x^{(i)})^T$

协方差矩阵Sigma是一个 $n\times n$ 的正定矩阵。
接下来我们要做的就是对协方差矩阵进行奇异值分解，得到一个矩阵 $U$

1	[U,S,V] = svd(Sigma)

注解：
S为一个对角阵，U·S·V=Sigma。

取 $U$ 前 $k$ 列，构成一个 $n\times k$ 的降维矩阵 $U_{reduce}$，我们将使用这个矩阵来对我们的数据进行降维。
然后我们计算出一个 $k$ 维向量 $z$,这就是我们降维所得到的结果。

119 主成分数量选择

在PCA中我们将 $n$ 维数据降维为 $k$ 维,这个 $k$ 是我们在PCA算法中需要调节的一个重要参数，被称为主成分数量。

平均平方误差：

$\frac{1}{m} \sum_{i=1}^m \| x^{(i)} - x_{approx}^{(i)} \|^2$

总体方差：

$\frac{1}{m} \sum_{i=1}^m \| x^{(i)} \|^2$

典型的 $k$ 值选择需要满足99%的方差将会被保留。常用的比例还有95%、90%等等。

$\frac{\frac{1}{m} \sum_{i=1}^m \| x^{(i)} - x_{approx}^{(i)} \|^2}{ \frac{1}{m} \sum_{i=1}^m \| x^{(i)} \|^2} \le 0.01 \qquad \textrm{(1%)}$

在实际应用中不需要弄明白这个方差代表什么，只需要保证满足上面这个式子即可。

如何去选择一个合适的 $k$,可以尝试将 $k=1$ 或其他初始值代入上面的式子计算进行比较然后再做调整。在实际操作中可以利用之前奇异值分解得到的 $S$ 矩阵。

120 压缩重现

虽然我们之前对数据做了压缩，但是压缩后的低维数据仍能表示原来高维数据所具有的信息。而且低维数据可以还原为高维数据，即将原来压缩的式子反过来进行运算。

这样我们计算出来的 $x_{approx}$ 就很接近我们原来的 $x$，这个过程我们称之为原始数据重构。

121 应用PCA的建议

当我们在进行一个高维度数据的有监督学习的时候，计算速度会很慢，此时就可以使用PCA对数据进行降维以达到加速的效果。

$(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots , (x^{(m)},y^{(m)})$
Extract inputs:
Unlabeled dataset: $x^{(1)},x^{(2)},\dots ,x^{(m)} \in \mathbb{R}^{10000}$
$\downarrow PCA$
$z^{(1)},z^{(2)},\dots ,z^{(m)} \in \mathbb{R}^{1000}$
New training set:
$(z^{(1)},y^{(1)}),(z^{(2)},y^{(2)}),\dots , (z^{(m)},y^{(m)})$

使用PCA相当于建立了一个从 $x$ 到 $z$ 的映射，进行特征缩放。要注意的是在交叉验证集和测试集上要使用和训练集一样的PCA参数。因为我们保留了99%的方差，所以即使降维了也不会影响到模型分类的精度。

PCA错误用法
有一种对PCA的错误用法是使用PCA来防止过拟合。虽然PCA可以起到一些防止过拟合的作用，但这并不是其正确的用法，也不是防止过拟合的好方法，最好还是使用正则项。这是因为PCA虽然保留了99%的方差，但是仍会丢掉一些有用信息，而使用正则项因为实在有标签的数据上进行训练，所以不会有信息被丢掉。

还有一个对PCA的错误用法就是，在一开始设计机器学习系统的时候就讲PCA考虑进去，而没有想过不用PCA进行训练会有怎样的结果。正确的做法是当不使用PCA遇到问题（运行太慢、内存硬盘占用量大）的时候才考虑使用PCA。

异常检测

123 问题动机

异常检测有点类似一个无监督学习。

我们先对一些正常样本进行检测获取数据构建模型P，然后当一个新的样本进来的时候，如果它落在P的靠近中间的位置，那么可以判断它是一个正常的；如果落在远离中心的位置，那么就会被判定为是一个异常的样本。

这种异常检测方法常被一些购物网站用来检测用户是否有异常行为，比如被盗号之类的。

124 高斯分布

$\sigma$ 被称为标准差。

参数估计
参数估计即从数据集中估算出$\mu、\sigma$ 两个参数。

$\mu =\frac{1}{m} \sum_{i=1}^m x^{(i)} \quad \sigma^2 = \frac{1}{m} \sum_{i=1}^m (x^{(i)}-\mu)^2$

在一些统计课上学习的公式使用的是$\frac{1}{m-1}$，但在机器学习领域中更喜欢选择使用$\frac{1}{m}$的版本，这对最终结果影响不大，因为机器学习使用的数据集一般都很大。

125 算法

为了得到一个最终的概率函数，我们会对每一个特征建立一个概率函数然后累乘。

$x_1 \sim N(\mu_1 ,\sigma_1^2) , x_2 \sim N(\mu_2 ,\sigma_2^2) ,\dots , x_n \sim N(\mu_n ,\sigma_n^2) \\\\ P(x) = P(x_1;\mu_1 ,\sigma_1^2)P(x_2;\mu_2 ,\sigma_2^2)\dots P(x_n;\mu_n ,\sigma_n^2)=\prod_{j=1}^n P(x_j;\mu_j ,\sigma_j^2)$

尽管从统计学角度说上面式子每一个特征都应该满足独立假设，但在实际应用中既是独立假设不成立这个算法也能正常运行。

异常检测算法

1.Choose features $x_i$ that you think might be indicative of anomalous examples.
2.Fit parameters $\mu_1,\dots ,\mu_n,\sigma_1^2,\dots ,\sigma_n^2$
$\mu_j =\frac{1}{m} \sum_{i=1}^m x_j^{(i)} \\\\ \sigma_j^2 = \frac{1}{m} \sum_{i=1}^m (x_j^{(i)}-\mu_j)^2$
3.Given new example $x$,compute $P(x)$:
$P(x)=\prod_{j=1}^n P(x_j;\mu_j ,\sigma_j^2)=\prod_{j=1}^n \frac{1}{\sqrt{2\pi} \sigma_j} \textrm{exp}(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})$
Anomaly if $P(x)<\varepsilon$

126 开发和评估异常检测系统

虽然异常检测系统近似于一个务监督学习，但是在开发的过程中我们还是给他打上标签，正常样本为0，异常样本为1。然后将数据集划分为训练集、校验集和测试集，其中异常样本全部分配到校验集和测试集中。
然后使用无标签训练集来拟合目标函数$P(x)$。
在带标签的校验集和测试集上进行预测评估。因为正常样本会远大异常样本产生样本偏斜，所以我们使用查准率与查全率、F1 Score的指标来进行评估。
同样使用交叉验证集来选择阈值参数$\varepsilon$。

127 异常检测 VS 监督学习

异常检测
通常正常样本远大于异常样本，但仍能很好的工作。
通常遇到的异常情况都不尽相同，新的异常样本肯能和之前的截然不同，很难通过学习预测之后新异常的大概样子。当遇到一个新异常样本的时候，使用高斯函数会更快速的拟合。

监督学习
正负样本比例比较均匀。
通过对大量正负样本的学习能大致掌握新的正负样本可能的样子。

128 选择要使用的功能

如果你的数据不符合高斯分布，建议使用一些转换函数将其近似转换为高斯分布。

如果你现有的模型无法正常预测一个新的异常样本的时候，分析这个异常样本，从而提取出新的特征来进行模型训练，从而将其区分开来。

129 多变量高斯分布

参数$\mu, \Sigma$（协方差矩阵）

$P(x;\mu,\Sigma)=\frac{1}{(2\pi)^{\frac{n}{2}} | \Sigma |^{\frac{1}{2}}} \textrm{exp} \left ( -\frac{1}{2} (x-\mu)^T \Sigma^{-1} (x-\mu) \right )$

130 使用多变量高斯分布的异常检测

参数拟合：
训练集：${ x^{(1)},x^{(2)},\dots ,x^{(m)} }$

$\mu = \frac{1}{m} \sum_{i=1}^m x^{(i)} \quad \Sigma = \frac{1}{m} \sum_{i=1}^m (x^{(i)}-\mu )(x^{(i)}-\mu)^T$

原始的高斯分布模型可以算是多元高斯分布的一个特例，即$\Sigma$矩阵为对角阵的情况，它们都是与轴对其的。而多元高斯分布还能拟合出如对角线这样的一些更复杂的模型。

原始模型 VS 多元高斯模型
如果存在一个异常是由两个特征同时影响造成的，那么使用原始模型想要解决这个问题就要使用这两个特征组合起来创造新的特征来加入训练。相比之下多元高斯能自动捕获这两种特征之间的关系。

原始模型的一大优势是计算成本低，它能适应大规模的数据集和特征。而多元高斯分布因为要计算协方差矩阵，计算量就要大得多。

当训练样本很少的时候原始模型也能正常工作。而对于多元高斯分布，必须满足训练样本数量大于特征数量，不然协方差矩阵将是奇异矩阵不可逆，这种情况下就不能使用多元高斯分布。同样的，如果存在大量冗余特征也可能导致不可逆。一般我们只有在训练样本数量远大于特征数量的时候才使用多元高斯分布。

大规模机器学习

140 学习大数据集

在机器学习中，通常情况下决定因素往往不是最好的算法，而是谁的训练数据最多。

141 随机梯度下降

每次梯度下降的时候都使用整个训练集的数据求梯度确实是收敛最快的方法，但是当数据集很大的时候相应的计算代价也会很大，这种使用全部数据集进行梯度下降的方法称为Batch梯度下降。

随机梯度下降就是先把所有数据随机打乱，然后遍历对每一个数据进行梯度下降。随机梯度下降与Batch梯度下降不同的地方就在于不需要对多个数据进行求和，而是对每个数据单独梯度下降。虽然每次下降方向并不都是朝着最优的方向，但是总的趋势是收敛的，最终能得到一个近似于全局最小的结果。

142 Mini-Batch梯度下降

Mini-Batch梯度下降介于Batch梯度下降和随机梯度下降之间，他每次迭代使用b个样本。b的常用取值在2～100之间。
Mini-Batch梯度下降比随机梯度下降要好的一点是，它可以在b个样本中实现并行计算，而不是遍历每一个样本。

143 随机梯度下降收敛

在进行Batch梯度下降时，我们每进行一次迭代就计算一次cost，以此绘图观察是否收敛。

在随机梯度下降中，可以每进行n次迭代就计算前n次迭代的平均cost，然后绘图观察是否收敛。
1）因为并不是每次都走向全局最优，所以cost曲线会以一个震荡的趋势逐渐下降。如果减小学习率的话则会下降的更慢震荡幅度更小，但是最终会更接近于全局最优。
2）如果提高n的取值，曲线将会变得更为平滑，但是这样信息就会有所延迟。
3）如果看到曲线一直震荡没有明显下降的趋势，可增大n值再观察，此时会发现函数趋势实际上是减小的。如果n太小，因为有噪声的存在会不好观察。如果增大n值观察仍没有下降，那么可能算法就存在问题。
4）如果观察到曲线是上升的趋势，那就说明是发散的，应该降低学习率。