主要学习课程：
吴恩达《Machine Learning》

其他学习资料以及笔记参考均在文末列出

1 引言
- 1.1 监督学习
  - 1.1.1 回归问题
  - 1.1.2 分类问题
- 1.2 无监督学习
  - 1.2.1 聚类算法
  - 1.2.2 鸡尾酒会算法
2 单变量线性回归(Linear Regression with One Variable)
3 线性代数回顾(Linear Algebra Review)
4 多变量线性回归(Linear Regression with Multiple Variables)
5 逻辑回归(Logistic Regression)
6 正则化(Regularization)
7 神经网络：表述(Neural Networks: Representation)（如何构建假设模型）
8 神经网络的学习(Neural Networks: Learning)（如何构建训练集和如何自动学习参数）
9 应用机器学习的建议(Advice for Applying Machine Learning)
10 机器学习系统的设计(Machine Learning System Design)
11 支持向量机(Support Vector Machines)
12 无监督学习1：聚类(Clustering)
13 无监督学习2：降维(Dimensionality Reduction)
14 非监督学习3：异常检测(Anomaly Detection)
15 推荐系统(Recommender Systems)
16 大规模机器学习(Large Scale Machine Learning)
17 应用实例：图片文字识别(Application Example: Photo OCR)
18 总结
19 参考

引言

监督学习

对于数据集中每一个样本都有对应的标签，包括回归（regression）和分类（classification）。

K近邻算法
线性回归
logistic回归
支持向量机（SVM）
决策树和随机森林
神经网络

回归问题

想要预测连续的数值输出（例中为房价）。

例，回归：设法预测连续值的属性。给一个房价数据集，在这个数据集中的每个样本都是实际卖价。想要估算某大小的房子价格。

分类问题

离散值。0/1

例，分类：设法预测离散值的输出。根据肿瘤大小判断是否有癌症（恶性/良性），什么类型的癌症

这里只使用了一个特征（肿瘤大小），机器学习问题中也可以使用多个特征属性。例如，知道年龄和肿瘤大小：

学习算法在数据上画出一条直线，分开恶性与良性。

特征可以有无穷多个，这时使用各种算法避免内存溢出。

无监督学习

数据集中没有任何的标签，未告知要按什么分类。包括聚类（clustering），著名的一个例子是鸡尾酒晚会。

聚类算法

把数据分成不同的簇。

K均值算法（K-means）
基于密度的聚类方法(DBSCAN)
最大期望算法

用途：

组织大型的计算机集群，分析那些机器趋向于协同工作。
社交网络分析，判断哪些人互相认识。
市场细分，将顾客细分到标题党市场。
天文数据分析。

例：谷歌新闻，收集新闻把同一主题的显示在一起。如图，点击下方几个连接，都是不同媒体报道同一个新闻事件。

鸡尾酒会算法

鸡尾酒会问题，聚会上同时说话声音混杂，麦克风录下重叠的声音，算法分离声音。
代码：（分离两种声音，Octave语言）

[W, s, v] = svd((repmat(sum(x.*x, 1), size(x, 1), 1).*x)*x)*x');

单变量线性回归(Linear Regression with One Variable)

模型表示

监督学习工作模式

学习过程解释：
1）将训练集中的房屋价格喂给学习算法。
2）学习算法工作，输出一个函数，用h表示。
3）h表示hypothesis（假设），代表的是学习算法的解决方案或者函数。
4）h根据输入的x值得到y值，因此h是x到的y的一个函数映射。
5）可能的表达式：hθ(x)=θ0+θ1x，只有一个特征或者出入变量，称为单变量线性回归问题。

代价函数

定义

图中红色的点表示真实值yi，即真实的数据集；
h(x)表示的通过模型得到的预测值。

学习算法的优化目标：选择出可以使得建模误差的平方和能够最小的模型参数(θ~0~,θ~1~)，即对代价函数J(平方误差函数)求最小值。

直观解释

1）通过假设θ~0~=0来进行，假设函数h(x)是关于x的函数，代价函数J(θ~0~,θ~1~)是关于θ~1~的函数，使得代价函数最小化。这里θ~1~=1时J最小。

2）通过等高线图来进行解释。通过绘制出等高线图可以看出来，必定存在某个点，使得代价函数最小，即：可以看出在三维空间中存在一个使得J(θ0,θ1)最小的点。

梯度下降

定义

梯度下降是一个用来求函数最小值的算法。使用梯度下降算法来求出代价函数J的最小值。
梯度下降思想：开始时随机选择一个参数的组合，计算代价函数，然后寻找下一个能让代价函数值下降最多的参数组合。持续这么做直到到到一个局部最小值（local minimum），因为并没有尝试完所有的参数组合，所以不能确定得到的局部最小值是否便是全局最小值（global minimum），选择不同的初始参数组合，可能会找到不同的局部最小值。
算法定义：

:=表示赋值，=表示真假判定
α：学习率（learning rate），决定了沿着能让代价函数下降程度最大的方向向下迈出的步子有多大。α越大，梯度下降越迅速。
学习率太小：收敛速度慢需要很长的时间才会到达全局最低点。
学习率太大：可能越过最低点，甚至可能无法收敛

反复做这一步直到收敛，然后更新参数θ~j~。要同步更新两个(θ~0~和θ~1~)，即，j=0和j=1时，更新θ~0~和θ~1~。

直观解释

求导的目的是取红点的切线。

如果α太小，即学习速率太小，结果就只能一点点挪动，需要很多步才能到达全局最低点。

如果α太大，那么梯度下降法可能会越过最低点，会导致无法收敛，甚至发散。下一次迭代又移动了一大步，一次次越过最低点，直到发现实际上离最低点越来越远。

如果θ~1~初始化在局部最低点，结果是局部最优点的导数(切线的斜率)将等于零，θ~1~不再改变。这解释了为什么即使学习速率保持不变时，梯度下降也可以收敛到局部最低点。

随着梯度下降法的运行，导数项(斜率)会越来越小，θ~1~缩小的幅度会越来越小，即移动的幅度会越来越小。直到最终移动幅度非常小，这时，已经收敛到局部极小值。

Batch梯度下降（批量梯度下降）

批量梯度下降指的是在梯度下降的每一步中，都用到了所有的训练样本。梯度下降中，在计算微分求导项时，需要进行求和运算，在每一个单独的梯度下降中，需要对所有m个训练样本求和。

线性代数回顾(Linear Algebra Review)

矩阵和向量

矩阵

大写字母A, B, C, X...表示矩阵
矩阵的维数：行数×列数

例：

单位矩阵

向量

小写字母a, b, x, y...表示向量
向量是一种特殊的矩阵，是只有一列的矩阵
n维向量：含n个元素的向量
例：

矩阵运算

加法

矩阵的加法：只有行列数相等的矩阵可以相加
例：

矩阵与标量（实数）乘法

逐个元素做运算
例：

矩阵与矩阵乘法

1、当矩阵A的列数（column）等于矩阵B的行数（row）时，A与B可以相乘。
2、矩阵C的行数等于矩阵A的行数，C的列数等于B的列数。
3、乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和。
（左列要等于右行，得数的维度取左行右列）

矩阵乘法在单变量线性回归中的应用

矩阵与向量乘法
7Z05
矩阵与矩阵乘法

逆和转置

逆矩阵

矩阵A的逆矩阵是A^-1^
只有方阵才有逆矩阵。

转置矩阵

矩阵A的逆矩阵是A^T^
行变列

向量化代码实现

例1：

例2：梯度下降

把 θ 看做一个向量，然后 θ - α 乘以向量 δ 来更新 θ
δ等于

多变量线性回归(Linear Regression with Multiple Variables)

多维特征公式

多变量梯度下降

算法

开始随机选择一系列的参数值，计算所有的预测结果后，再给所有的参数一个新的值，如此循环直到收敛。
Python 代码

def computeCost(X, y, theta):
    inner = np.power(((X * theta.T) - y), 2)
    return np.sum(inner) / (2 * len(X))

梯度下降方法1：特征缩放

在面对多维特征问题时，要保证这些特征尺度（最大值和最小值差距）相近
以房价问题为例，假设使用两个特征：房屋的尺寸和房间的数量。尺寸的值为 0-2000平方英尺，而房间数量的值则是0-5，以两个参数分别为横纵坐标，绘制代价函数的等高线图能，如图，图像会显得很扁，梯度下降算法需要非常多次的迭代才能收敛。因为房屋面积对价格影响很大，卧室数量对房价影响不大

解决的方法是将所有特征的尺度缩放到大约-3到3之间（特征值尺度不一定要完全一样，足够接近就行）。如图，把两个特征x1 x2修改至如下，使收敛更快：

（想象橄榄球和篮球）

均值归一化(Mean Normalization)

最简单的方法是令：
$$
x_n = \frac{x_n-μ_n}{s_n}
$$
μ~n~是平均值，s~n~是最大值减去最小值（近似值就行，不用太精确，只是为了让梯度下降更快一点而已）

梯度下降法实践2：学习率

收敛所需要的迭代次数无法预知，可通过迭代次数和代价函数的图表观测何时趋于收敛。

图表还可用于判断梯度下降法有没有正常工作：

如果学习率α过小，则达到收敛所需的迭代次数会非常高；如果学习率α过大，每次迭代可能不会减小代价函数，可能会越过局部最小值导致无法收敛。
通常尝试如下一系列α值：0.01, 0.03, 0.1, 0.3, 1, 3, 10，对这些值绘制 J(θ) 随迭代步数变化的曲线，然后选择使得 J(θ) 快速下降的一个 α 值（通常取最大值或比最大值略小一点的值）。

自动收敛测试：代价函数的下降值小于某个阀值（例如0.001）时就判断收敛。但选择阈值很困难，图表法更好。

特征和多项式回归

根据问题，可以将原有特征合并为新特征
例：

总结：
1）根据实际问题，选择使用哪些特征（后序将探讨一些能自动选择合适的使用特征的算法）
2）根据函数图形特性选择更好的模型
3）将多次函数模型转换为线性回归模型
注意：采用多项式回归模型时，在运行梯度下降算法前，要进行特征缩放！

正规方程(Normal Equation)

梯度下降法要慢慢迭代来求 θ，而正规方程法可以一步求出 θ 的最优值。
原理是求导等于 0 的点斜率等于0
例子：

步骤
1）在前加一列全 1 的数据
2）构建矩阵 X，包含训练样本的所有特征变量
3）用预测值构建向量 y
4）
$$
θ = (X^TX)^{-1}X^Ty
$$
注意：正规方程法不需要特征缩放

补充问题：当计算 (X^T^X)^-1^X^T^y 时，矩阵 X^T^X 不可逆怎么办？
在Octave里，使用pinv() 函数不管可不可逆都能计算出来（python呢？）
为什么会有不可逆的情况：①两个特征线性相关了（行或者列线性相关，矩阵就不是满秩，就不可逆了），这时候二选一删掉一组值 ②特征值太多，比如 m ≤ n（m < n的时候，rank(X) <= m < n被限制了），这时候删掉一些值或者使用正则化的方法

梯度下降与正规方程的比较

梯度下降	正规方程
需要选择学习率α	不需要选择学习率α
需要多次迭代，需要画出 J(θ) 的曲线来检查收敛性	一次运算得出
当特征数量 n 大时也能较好适用	需要计算 (X^T^X)^-1^ （是一个nn的矩阵）如果特征数量 n 过大则运算时间长，矩阵逆的计算时间复杂度为 O(n^3^)（通常来说当n < 10000 时可以使用*）
适用于各种类型的模型	只适用于线性模型，不适合逻辑回归模型等其他模型

逻辑回归(Logistic Regression)

逻辑回归是什么

逻辑回归实际上是一种分类算法，y = 0 or 1
再区别一下回归和分类
回归模型：输出连续
分类模型：输出离散

公式

逻辑回归 = 线性回归 + sigmoid函数

损失函数

想求解出好的参数，需要使用损失函数

代码实现
使用spark框架，引入pyspark包
数据是libsvm格式的
数据格式定义：第一列label列，后面每个值冒号前表示这是第几个特征，冒号后表示这个特征下的特诊值
这是一个二分类问题，目标列只有 0/1 两种

引入数据之后，就会有一行做一个训练集和测试集的划分

用一行代码来训练这个模型

神经网络中每一个节点都是一个逻辑回归

分类问题的假设表示

假设表示(the hypothesis representation)：要用来表示我们的假设的方程。

可以看出，把线性回归应用于分类问题通常不是一个好主意

引入逻辑回归模型，该模型的输出变量范围始终在 0 和 1 之间。 逻辑回归模型假设表示：
$$
h_θ(x) = g(θ^TX)
$$
X 代表特征向量 g 代表逻辑函数（logistic function)，也称为S形函数（Sigmoid function），公式为：$$g(z) = \frac{1}{1+e^{-z}}$$

h(θ) 的作用是，对于给定的输入变量，根据选择的参数计算输出变量=1的可能性

函数图像：

python代码实现：

import numpy as np

def sigmoid(z):
   return 1 / (1 + np.exp(-z))

决策边界(decision boundary)

例1：

注意，决策边界不是训练集的属性，而是假设本身及其参数的属性，只要给定参数向量 θ，决策边界就确定了。
后序将讨论如何利用训练集确定参数取值，不用再像上面这样通过绘制训练集确定决策边界

例2：
逻辑回归也可以像线性回归一样，在特征中添加额外的高阶多项式

例3：更加复杂的决策边界

h~θ~(x) 与 Cost(h(θ), y) 的关系图示：

“代价”的直观体现：

代价函数

简化的成本函数和梯度下降

推导：

所以，逻辑回归的代价函数：

这个更新规则的式子正是我们用来做线性回归梯度下降的，但假设的定义发生了变化

所以逻辑函数的梯度下降，跟线性回归的梯度下降实际上是两个完全不同的东西。
线性回归中监控梯度下降法以确保其收敛的方法，也可以用在逻辑回归中，来监测梯度下降，以确保它正常收敛。
同样，之前的特征缩放的方法，也适用于逻辑回归。

其他高级算法

当有一个很大的机器学习问题时，可以不使用梯度下降法，而选择更高级的算法，如共轭梯度法 BFGS (变尺度法) 和 L-BFGS (限制变尺度法)。不需要真正理解这些算法的内环间在做什么，而是直接使用一个软件库。

多类别分类：一对多

多类别：y可以取一些离散值
将其分成多个二元分类问题，如下图中，有 3 个分类器，每个分类器都针对其中 1 种情况进行训练

正则化(Regularization)

正则化的技术可以改善或者减少过度拟合(over-fitting)问题。

过度拟合的问题

回归问题的例子：

分类问题的例子：

如果发现过拟合问题，应该如何处理？

减少选取变量的数量。
①人工检查变量清单，选择保留和舍弃某些特征变量。
②使用模型选择算法来帮忙，自动选择保留哪些变量舍弃哪些变量。
缺点：也舍弃了一些信息
正则化。
保留所有的特征，但是减少参数的大小。

代价函数

从之前的事例中看出，是高次项导致了过拟合的产生，所以如果能让这些高次项的系数接近于0，就能很好地拟合。
正则化的基本方法：减小这些参数 θ 的值。修改代价函数，在其中设置一点惩罚
修改后的代价函数如下：

通过这样的代价函数选择出的和 θ~3~ 和 θ~4~ 对预测结果的影响比之前要小许多。假如有非常多的特征，并不知道其中哪些特征需要惩罚，可以对所有的特征进行惩罚，缩小每一个参数：

这里 λ 称为正则化参数（Regularization Parameter），作用是控制两个不同目标间的取舍，从而保持假设模型的相对简单，避免出现过拟合的情况。

如果对这些 θ 惩罚程度过大（λ 过大），那么最后这些参数都会接近 0，相当于把假设函数的全部项都忽略掉了，导致模型变成h~θ~(x) = θ~0，可以说这个假设模型的偏见性太强或者说偏差过高。
经过正则化处理的模型与原模型的可能对比如下图所示：

注：根据惯例，我们只对θ~1~到θ~100~进行正则化，不包含θ~0~

正则化线性回归

正则化的逻辑回归模型

神经网络：表述(Neural Networks: Representation)（如何构建假设模型）

非线性假设

模型表示1

$$x_0$$ 称作偏置单元（偏置神经元），因为总等于1，所以不画出也行
在神经网络中，参数 θ 又可被成为权重（weight）

第一层成为输入层（Input Layer），最后一层称为输出层（Output Layer），非输入层或输出层的层都叫隐藏层（Hidden Layers）

模型表示2

前向传播：

其他神经网络架构（神经网络中神经元的连接方式）例1：

每层的 θ 都不同，第一层 3*4，第二层 2*4，第三层 1*3
例2：

样本和直观理解1：神经网络计算简单逻辑函数

XOR是异或，两输入相异=1；XNOR是同或（异或非，XOR取反），两输入相同=1
x1和x2两个的值如果相同（同真 1 或同假 0）的话就是红叉叉 y=1，两个值不同的话就是蓝色圆圈 y=0，要用异或
下面有两个例子展示神经网络中的单个神经元是如何被用来计算逻辑函数的

AND

用神经网络表示 AND 函数
图中将做以下几步：
1）添加一个偏置单元（也叫+1单元），也可以理解为 $$x_0$$
2）标出权重（或称参数）
3）写出假设模型 h(x) = g(...)
4）画出真值表
思路：偏置单元的权重绝对值在其他x权重之和和权重之和的相反数之间，但比单个权重大

OR

用神经网络表示 OR 函数，同上
思路：偏置单元的权重绝对值在其他x权重之和和权重之和的相反数之间，但比单个权重小

NOT

用神经网络表示 NOT 函数
思路：在预期得到非结果的变量前面放一个很大的权重

(NOT $x_1$) AND (NOT $x_2$)

样本和直观理解2：神经网络计算复杂逻辑函数

当网络拥有多层，函数复杂程度：layer 2<layer 3<...<layer n
按这种方法我们可以逐渐构造出越来越复杂的函数。

下面继续以例子展示神经网络如何计算复杂的非线性假设模型

XNOR

其他例子

Yann LeCun手写数字的识别
其实是一个多类别分类问题，分类 0 ~ 9 的数字。

多类别分类

就像一对多法，下例中我们有 4 个逻辑回归分类器：

$$y^(i)$$的值取决于对应的图像$$x^(i)$$
一个训练样本要由一组$$(x^(i), y^(i))$$组成，$$x^(i)$$是其中一种图像，$$y^(i)$$是其中一个向量
输出值$$h(x^(i))$$约等于$$y^(i)$$

神经网络的学习(Neural Networks: Learning)（如何构建训练集和如何自动学习参数）

代价函数

让代价函数最小化：反向传播算法

前向传播法：

反向传播法：
算出最后一层误差 δ^(4)^之后算前面几层的误差 δ

反向传播算法的直观理解

前向传播：

反向传播：

注意：δ 只关于隐藏单元，不包括偏置单元

实现注意：展开参数

（Octave实现）

梯度检验

在反向传播算法与梯度下降算法结合时，很容易产生一些不易察觉的bug
为了避免这样的问题，采取梯度检验（Gradient Checking）方法，思想是通过估计梯度值来检验我们计算的导数值是否真的是我们要求的，以此确保结果正确。
对梯度的估计采用的方法是在代价函数上沿着切线的方向选择离两个非常近的点，计算两个点的平均值用以估计梯度。即对于某个特定的，我们计算出在 θ - ε 处和 θ + ε 的代价值（是一个非常小的值，通常选取 0.001），然后求两个代价的平均，用以估计在 θ 处的代价值。

当 θ 是一个向量时：

随机初始化

为 θ 选取初始值
在逻辑回归中可以令所有的初始参数都为 0，但在训练网络时没有用，同理，如果我们初始所有的参数都为一个非0的数，结果也是一样的。这叫做对称权重问题。
例：

如果令所有的初始参数都为 0，则同色权重相同，即隐藏单元 a~1~ 和 a~2~ 都以同一输入函数来计算的，不管进行几次梯度下降，a^(2)^ ~1~ 总等于 a^(2)^ ~1~，δ 值也总相同，会导致高度冗余
用随机初始化来解决对称权重问题：
对每一个 θ 初始化为一个接近 0 的，范围在 -ε 到 ε 之间的随机值。假设我们要随机初始一个尺寸为 10×11 的参数矩阵，代码如下：

import numpy as np

Theta1 = np.random.rand(10, 11) * (2 * eps) - eps

总结：
1）将权重 θ 初始化为一个接近 0 的，范围在 -ε 到 ε 之间的随机值
2）反向传播
3）梯度检验
4）梯度下降或者其他高级算法来最小化代价函数 J(θ)

综合起来

使用神经网络时的步骤：
1）选择网络架构：选择多少层以及决定每层分别有多少个单元
① 输入层的数量等于特征x^(i)^的维度
② 输出层的数量等于要区分的类别个数。例：
不能用常数 5，要用向量

③ 通常 1 个隐藏层，如果大于 1 个，通常每个隐藏层有相同单元数。通常，隐藏单元越多越好，但越多计算量越大

2）训练神经网络
① 随机初始化权重（参数）：通常很小，接近于 0
② 使用正向传播方法，根据 x^(i)^ 计算所有的 h~θ~(x^(i)^)（也就是输出值 y 的向量）
③ 编写计算代价函数 J(θ) 的代码
④ 使用反向传播方法计算所有偏导数，也就是 J(θ) 关于参数 θ 的偏导数
⑤ 使用梯度检查方法检验这些偏导数，④ 中已得到的偏导数项 vs用数值方法得到的估计值，确保基本接近
⑤.5 停用梯度检查
⑥ 使用优化算法（梯度最小法或者更高级的算法，如LBFGS、共轭梯度）和反向传播(计算出偏导数的值)结合，来最小化代价函数 J(θ)

应用机器学习的建议(Advice for Applying Machine Learning)

发现错误后决定下一步做什么

继续预测房价的学习例子，假如在得到学习参数 J 以后，当在一组新房屋样本上测试假设时，发现它在预测中产生了不可接受的大误差。接下来应该尝试什么?

不应该随机选择某种方法来改进算法，而是运用一些机器学习诊断法来帮助我们知道哪些方法对我们的算法是有效的。
“诊断法”意思是：一种测试法，通过执行这种测试，能够了解算法在哪出现了问题，也能知道要想改进一种算法的效果，什么样的尝试是有意义的

首先，画出学习曲线或别的方法，发现有方差问题（交叉验证集误差 J~cv~ 比训练集误差 J~train~ 大一些）或偏差问题

获得更多的训练样本——解决高方差（但代价较大）
尝试减少特征的数量——解决高方差
尝试获得更多的特征——解决高偏差
尝试增加多项式特征——解决高偏差
尝试减少正则化程度 λ——解决高偏差
尝试增加正则化程度 λ——解决高方差

评估一个假设

特征过多的时候无法通过画假设出图像来评估假设，需要使用另一种方法

将所有数据按 7: 3 随机选择（如果有规律），分为训练集和测试集
首先从训练数据中学习得到参数 θ，然后我们有两种方式计算误差：
1）对于线性回归模型，我们利用测试集数据计算代价函数 J：

2）对于逻辑回归模型：
法 ①：与逻辑回归的一样，唯一区别是使用m~test~个测试样本

法 ②：错误分类（0/1 错误分类）

模型选择和交叉验证集：选择特征数量与 λ

假设我们要在10个不同次数的二项式模型之间进行选择：

上面这样用测试集选择模型，然后使用相同的测试集来计算误差是不对的。正确的做法如下：
使用60%的数据作为训练集，使用 20%的数据作为（交叉）验证集，使用20%的数据作为测试集

下面定义训练误差，（交叉）验证误差和测试误差：

模型选择的步骤：
1）使用训练集训练出10个模型
2）用10个模型分别对交叉验证集计算得出交叉验证误差（代价函数的值）
3）选取代价函数值最小的模型
4）用步骤3中选出的模型对测试集计算得出推广误差（代价函数的值）

诊断偏差和方差

当运行一个学习算法时，如果这个算法的表现不理想，那么多半是出现两种情况：要么是偏差比较大，要么是方差比较大。换句话说，出现的情况要么是欠拟合，要么是过拟合问题。下面说明如何观察是偏差问题还是方差问题

正则化和偏差/方差

什么是偏差和方差

在我们在训练模型的过程中，一般会使用一些正则化方法来防止过拟合。但是我们可能会正则化的程度太高或太小了，即我们在选择λ的值时也需要思考与刚才选择多项式模型次数类似的问题。

选择一系列的想要测试的 λ 值，通常 2 倍增长（如：下例图上共12个）。同样把数据分为训练集、交叉验证集和测试集。
选择 λ 的步骤：
1）使用训练集训练出12个不同程度正则化的模型
2）用12个模型分别对交叉验证集计算的出交叉验证误差
3）选择得出交叉验证误差最小的模型（下例中假设是5）
4）运用步骤3中选出模型对测试集计算得出推广误差，我们也可以同时将训练集和交叉验证集模型的代价函数误差

当 λ 较小时，训练集拟合较好（过拟合）（J~train~ 小）；交叉验证集误差较大（ J~cv~ 大）
随着 λ 的增加，训练集误差 J~train~ 不断增加（欠拟合，高偏差），而交叉验证集误差 J~cv~ 则是先减小后增加

（真实图像更凌乱）

学习曲线

学习曲线可以用来判断某一个学习算法是否处于偏差、方差问题或者二者皆有
学习曲线是将训练集误差和交叉验证集误差作为训练集样本数量（m）的函数绘制的图表。

高偏差情况下学习曲线的大致走向：

学习算法处于高偏差（欠拟合）的情况下，增加更多数据到训练集没有帮助。所以要学会判断是否处于高偏差（欠拟合）情况

高方差情况下学习曲线的大致走向：

学习算法处于高方差（过拟合）的情况下，增加更多数据到训练集对改进算法有帮助

决定下一步做什么：神经网络的欠拟合和过拟合

选择简单的（隐含单元少的）神经网络结构，参数不多，容易欠拟合。优点是计算量小
大型（隐含单元数多或有很多隐含层）神经网络结构，参数多，容易过拟合。计算量大，但性能好。过拟合时用正则化的方法来修正

对于神经网络中的隐藏层的层数的选择，默认使用一层，若想选用多层，可以把数据分为训练集、交叉验证集和测试集，从一层开始递增地针对不同隐藏层层数的神经网络训练神经网络，然后选择交叉验证集代价最小的神经网络。

机器学习系统的设计(Machine Learning System Design)

例：识别垃圾邮件

接下来将讲述在设计器学习系统时，怎样用更加系统性的方法，从一堆不同的方法中，选取合适的那一个

误差分析

构建一个学习算法的方法：
1）从一个简单的能快速实现的算法开始，快速实现该算法并用交叉验证集数据测试这个算法（要避免过早优化，以实际数据指导决策）
2）绘制学习曲线，看是否存在高偏差、高方差或其他问题，由此决定是增加更多数据，或者添加更多特征，还是其他选择
3）进行误差分析：人工检查交叉验证集中在算法中产生预测误差的样本，看看这些样本是否有某种系统化的趋势（如，在构造垃圾邮件分类器时，看一看交叉验证数据集的情况，然后看一看哪些邮件被算法错误地分类，找到系统性的规律：什么类型的邮件总是被错误分类）
优化过程中，使用数值分析方法来评估算法效果很好。比如通过交叉验证在使用和不适用某算法时各自的错误率来估计算法的效果，这叫做交叉验证错误率，注意，是在交叉验证集上做误差分析而不是在测试集上

偏斜类的误差度量

偏斜类（skewed classes）情况：一个类中的样本数与另一个类的数据相比多很多
使用分类误差或分类精确度来作为评估度量可能会在遇到偏斜类问题时产生问题，例如：我们希望用算法来预测癌症是否是恶性的，在我们的训练集中，只有0.5%的实例是恶性肿瘤。假设我们编写一个非学习而来的算法，在所有情况下都预测肿瘤是良性的，那么误差只有0.5%。然而我们通过训练而得到的神经网络算法却有1%的误差。这时，误差的大小是不能视为评判算法效果的依据的。

使用查准率（Precision）和查全率（Recall）评估模型的好坏
我们将算法预测的结果分成四种情况：
1）正确肯定（True Positive, TP）：预测为真，实际为真
2）正确否定（True Negative, TN）：预测为假，实际为假
3）错误肯定（False Positive, FP）：预测为真，实际为假
4）错误否定（False Negative, FN）：预测为假，实际为真

则：
查准率 = TP / (TP + FP)，越高越好。
“看预测的准不准”。例，在所有我们预测有恶性肿瘤的病人中，实际上有恶性肿瘤的病人的百分比
召回率（查全率） = TP / (TP + FN)，越高越好。
“看正确预测的数量够不够”。例，在所有实际上有恶性肿瘤的病人中，成功预测有恶性肿瘤的病人的百分比
对于我们刚才那个总是预测病人肿瘤为良性的算法，其召回率（查全率）是 0。

查准率和查全率之间的权衡

如果希望只在非常确信的情况下预测为真（比如肿瘤为恶性），即我们希望更高的查准率，可以使用比 0.5 更大的阀值，如 0.7，0.9。但这样会降低查全率。这样做我们会减少错误预测病人为恶性肿瘤的情况，同时却会增加未能成功预测肿瘤为恶性的情况。如果我们希望提高查全率，尽可能地让所有有可能是恶性肿瘤的病人都得到诊断，我们可以使用比 0.5 更小的阀值，如 0.3。
将不同阀值情况下，查全率与查准率的关系绘制成图表，曲线的形状根据具体算法的不同而不同：

选择临界值的算法
$$
F_1 = 2\frac{PR}{P + R}
$$
选择使 F_1 值最高的阀值。

机器学习的数据

大部分时候收集过多的数据没什么用，但特征要足够多以能够保证算法能足够根据这些特征判断出正确的类别（低偏差）（可以这么来判断特征值的数量是否足够：一个人类专家看到了特征值 x，能预测出 y 值吗？），数据集要足够的大以保证能够匹配得上前边那么多参数（使其低方差较低）。即特征数目与数据量同时足够多，可以保证偏差和方差都不高

支持向量机(Support Vector Machines)

优化目标

大边界的直观理解

支持向量机有时候也被叫做大间距分类器。
如果有一个正样本 y = 1，则其实仅要求 θ^T^ x 大于等于0，就能将该样本恰当分出，因为如果 θ^T^ x > 0 ，我们的模型代价函数值为 0，类似地，如果有一个负样本，则仅需要 θ^T^ x < 0就会将负例正确分离，但是支持向量机的要求更高，不仅仅要能正确分开输入的样本，即不仅仅要求 θ^T^ x >0，而是需要比 0 值大很多，比如大于等于 1，也需要比 0 小很多，比如希望它小于等于 -1，这就相当于在支持向量机中嵌入了一个额外的安全因子，或者说安全的间距因子。
支持向量机模型的代价函数：

为直观感受支持向量机，这里把 C 设置成非常大的常数

支持向量机将会选择这个黑色的决策边界，在分离正样本和负样本上它显得的更好。数学上来讲，这条黑线使得正样本和负样本间有更大的距离，这个距离叫做间距(margin)。

这使 SVM 具有鲁棒性
因此支持向量机有时被称为大间距分类器

当 C 非常大的时候，学习算法会受异常点(outlier) 的影响。比如我们加入一个额外的正样本：

仅仅基于一个样本，就将决策界从这条黑线变到这条粉线
（这样可以让我们对 SVM 是如何作为大间距分类器工作的有一个更直观的理解）
如果 C 不那么小，最终还是那条黑线。可见 C 的作用类似于 1/λ

数学背后的大边界分类（选修）

向量内积
||u||表示u的范数（长度）

支持向量机做的事，就是极小化参数向量范数（长度）的平方

左图：

右图：

以上就是为什么支持向量机最终会找到大间距分类器的原因。因为它试图极大化这些 p ^(i)^ 的范数，也就是训练样本到决策边界的距离。即便 θ~0~ 不等于0，支持向量机仍然会找到正样本和负样本之间的大间距分隔。

核函数1

下面这篇博客也很好地介绍了核函数：
https://www.cnblogs.com/hichens/p/11874645.html

这里先视 x~0~ 为 1

相似度函数就是核函数
当 x 和标记 l 相似度很接近的时候距离接近 1，如果很不一样就接近 0

特征 f~1~ 衡量了 x 到第一个标记 l^(i) 的距离（相似度）有多近， f~1~ 的值在0, 1间（看第一张图）
δ^2^ 变小，突起变窄，等高线图收缩，特征f~1~ 下降到 0 的速度变快
假设样本处于粉色位置

当接近两个标记点中任意一个时，预测值就会接近 1，否则预测值等于 0
这样，图中红色的封闭曲线所表示的范围，便是我们依据一个单一的训练样本和我们选取的地标所得出的判定边界，在预测时，我们采用的特征不是训练样本本身的特征，而是通过核函数计算出的新特证 f~1~, f~2~, f~3~。

核函数2：选择标记点(landmarks)

直接将训练样本作为标记点

支持向量机也可以不使用核函数，不使用核函数又称为线性核函数(linear kernel)，当我们不采用非常复杂的函数，或者我们的训练集特征非常多而样本非常少的时候，可以采用这种不带核函数的支持向量机。

在使用支持向量机时的偏差-方差折中参数的选择
面是支持向量机的两个参数 C 和 σ 的影响：
（C = 1 / λ）
C 较大时，相当于 λ 较小，可能会导致过拟合，高方差；
C 较小时，相当于 λ 较大，可能会导致低拟合，高偏差；
σ 较大时，对应的相似度函数(核函数)相对平滑，随输入 x 变变化缓慢（如下图所示），可能会导致低方差，高偏差；
σ 较小时，可能会导致低偏差，高方差。

使用支持向量机

使用 SVM 直接调库就行，但还是需要以下几个步骤：
1）选择参数 C
2)选择核函数（相似函数），或者不用核函数（这叫线性核函数）
构建高斯核函数（Gaussian kernel）：（线性特征少，样本量足用高斯svm）
JOC4C
注意：在使用高斯函数前，需要将特征变量的大小按比例归一化
RNBRZOJT4
注：并非所有相似函数 similarity(x, l) 都是有效的核。需要满足“默塞尔定理（Mercer's Mhemorem）”的条件，才能使SVM包的优化正确运行，并且不会发散

在高斯核函数之外我们还有其他一些选择，如：

多项式核函数（Polynomial Kernel）
字符串核函数（String kernel）
卡方核函数（ chi-square kernel）
直方图交集核函数（histogram intersection kernel）
......

这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征，这些核函数需要满足Mercer's定理，才能被支持向量机的优化软件正确处理。

一对多（one-vs-all）方法也可以用于做多分类
（这里的一对多，详见6、7节，就是分4个类要用4个模型，每个模型都有一个theta向量）
V0KKE8

选择特征数量 n 和训练样本数量 m：
(1)如果 n 比 m 大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，选用逻辑回归模型或者不带核函数的 svm。比如文本分类，垃圾邮件，特征多而样本少
(2)如果 n 较小，而且 m 大小适中，例如 n 在 1-1000 之间，而 m 在10-10000之间，使用高斯核函数的 svm。
(3)如果 n 较小，而 m 较大，例如 n 在1-1000 之间，而 m 大于50000，则使用高斯函数的 svm 会非常慢，解决方案是尝试手动创建更多特征变量，然后使用逻辑回归或不带核函数的支持向量机

使用 SVM 而不是神经网络：神经网络训练起来可能很慢，使用 SVM 包更快速，SVM 具有的优化问题是凸优化问题，可以找到全局最小值

无监督学习1：聚类(Clustering)

无监督学习：简介

无监督学习：让计算机学习无标签数据，而不像之前的标签数据。
监督学习与无监督学习对比：

图上的数据看起来可以分成两个分开的点集（称为簇），一个能够找到圈出的这些点集的算法，就被称为聚类算法

K-均值算法

K-均值（K-means）是现在最热门广泛的聚类算法，算法接受一个无标签的数据集，然后将数据聚类成不同的簇。它是一个一个迭代算法
步骤
0）接受两个参数：簇的数量 K，一系列无标签数据集 x（规定样本点 x^(i)^ 是一个 n 维实数向量(x~0~ =1)）
1）随机初始化 K 个点，叫做聚类中心（cluster centroids）

2）进行簇分配：遍历每个点，然后根据每个点与哪个聚类中心更近，来将每个数据点分配给其中一个聚类中心

3）移动聚类中心：将 K 个聚类中心移动到该组点的均值处

4）重复步骤 2 - 3，直到中心不再改变，此时 K均值已经聚合
（如果存在一个没有点的聚类中心，就直接移除那个聚类中心，最终得到 K-1 个簇而不是 K 个。如果需要 K 个簇，那就重新初始化聚类中心）

使用K-均值解决分离不加的簇的问题
K-means 也可以用于解决这样看起来不好分簇的数据集
例：T-shirt知道身高体重分尺码S, M, L 执行 K-means 算法，会分簇，由此来分三个尺码

优化目标

回顾刚才给出的 K-均值迭代算法，循环中第一步是用于减小 c^(i)^ 引起的代价（把每个点分配给最近发聚类中心，这样就可以使每个点到对应的聚类中心距离的平凡最小化），循环中第二步则是用于减小 μ~i~ （聚类中心）引起的代价。迭代的过程一定会是每一次迭代都在减小代价函数，不然便是出现了错误

随机初始化

运行 K-均值算法之前，要先随机初始化所有的聚类中心点，步骤如下：
1）使 K < m，即聚类中心点个数小于所有训练集样本数量
2）随机选择 K 个训练样本，然后令 K 个聚类中心分别与这 K 个训练实例相等

K 均值算法可能会落在局部最优，导致不能很好地最小化畸变函数 J。如何使算法避开局部最优？

为了解决这个问题，我们通常需要多次运行 K-均值算法(50-1000 次，如100 次），每一次都重新进行随机初始化，进行比较，选择代价函数 J 最小的那个。这种方法在 K 较小的时候（2--10）还是可行的，但是如果 K 较大，这么做也可能不会有明显的改善。

选择聚类数量 K

手动选择。

肘部法则

改变聚类数量 K 值，计算畸变函数 J
随着聚类数量 K 增加，J 减小，画出一条曲线。曲线的肘部的 K 值就是我们要选择的 K 值
肘部之前，J 下降快，肘部之后，J 下降慢

但是也可能出现这种模棱两可的图像：

这时候就没办法使用该法则了

根据实际目的选择 K 值

更好的方法是，看哪个 K 值能更好地应用于后续目的，由此来决定 K 值的选择。
例1：之前的 T 恤尺寸例子，可以S, M, L，也可以 XS, S, M, L, XL，看市场需求等
例2：图片压缩，看需要图片质量更好还是图片占空间更小

无监督学习2：降维(Dimensionality Reduction)

动机一：数据压缩

减少冗余
例：
假设有两个特征：厘米长度 x~1~ ，英寸长度 x~2~。冗余了，想降到一维
例2：
假设有两个特征：飞行员技能与飞行员对职业热爱

投影，来降维

动机二：数据可视化

特征很多的时候没法可视化，降维至二维，即 2 个特征，更易可视化
但此时输出一般不会具有物理意义，要自己弄明白它们的含义
例：

观察得到：
横轴：国家规模或总体积极活跃程度(GPT)
纵轴：人均GPT或个人经济活跃程度

PCA 主成分分析问题

主成分分析(PCA, Principal Component Analysis)是最常见的降维算法。
应用 PCA 前应该先进行均值归一化和特征规范化，使得特征们的均值为 0，并且数值在可比较的范围内

找一个数据投影后能够最小化投影误差的方向

PCA 定义：企图找到一个低维平面来对数据进行投影，最小化投影误差（即投影前后距离）的平方。找出 k 个方向，来对数据进行投影。
正式定义是要找出一组向量，将这些数据投影到 k 个向量展开的线性子空间上（一个 k 维平面）
方向向量是一个经过原点的向量，而投射误差(projection error)是从特征向量向该方向向量作垂线的长度。

例：

PCA 会选择红色线而非粉色

PCA 与线性回归之间的关系
主成分分析问题 PCA 画的图表和线性回归有点像，但PCA 不是线性回归
1）下图中，左边是线性回归的误差（垂直于横轴投影），右边则是主要成分分析 PCA 的误差（垂直于红线投影）：

2）同时，线性回归是要根据每个 x 预测特殊的变量 y，而 PCA 是用所有的 x 来预测，没有特殊的变量 y

PCA 主成分分析算法

PCA n 维下降到 k 维：
1）数据预处理：均值归一化和特征缩放。我们需要计算出所有特征的均值，然后令 x~j~ = x~j~ - μ~j~。如果特征是在不同的数量级上，我们还需要将其除以标准差 δ^2^

2）计算协方差矩阵（covariance matrix）：（是一个n*n的矩阵）
$$
\sum = \frac{1}{m}\sum_{i=1}^{n}(x^(i))(x^(i))^T
$$
（这里 x 是 n 维，所以 x~0~ 不能 = 1 (那样是 n+1 维)）
利用奇异值分解（SVD, singular value decomposition）来求解
python 代码：

import numpy as np

U, S, V = np.linalg.svd(matrix)

3）计算协方差矩阵的特征向量（eigenvectors）：
特征向量 u^(i)^ 和 z：

需要上一步中输出的 U，它也是一个 n*n 的矩阵。想将数据从 n 维降至 k 维，提取前 k 个向量 u^(1)^ ~ u^(k)^

$$
z = U_{reduce}^Tx
$$

压缩重建

$$
x{approx}^{(i)} = U{reduce}z
$$

注意是“近似”，有损。

主成分数量选择

我们希望在平均投影误差平方除以数据总方差尽可能小的情况下选择尽可能小的值。

常见的数字：0.01（1%），0.05（5%）（95%~99%）
图上选择 k，使得99%的方差被保留（可以理解为，有损压缩，损失的数据不超过百分之一）
为保留99%的方差，往往减少数据维数但仍保留大部分方差。现实生活中很多特征都是高度相关的，对数据进行很多压缩，仍然可以保留这么多的方差

实现算法
算法 1）（实现起来很低效）
先令 k = 1，然后计算，然后查看比例是否小于 1%（是否保留了 99%的方差）。如果是，就令 k = 1，如果不是的话再令 k = 2，如此类推运行 PCA，直到找到可以使得比例小于 1%的值。

算法 2）

import numpy as np

U, S, V = np.linalg.svd(matrix)

得到U, S, V
S 是一个 n*n 的对角矩阵

从 1 开始缓慢增加 k 的值（k = 1, 2, 3,...)，选择满足不等式的最小 k 值保留。
以上步骤只要调用一次 SVD

应用 PCA主成分分析法的建议

假使我们正在针对一张 100×100像素的图片进行某个计算机视觉的机器学习，即总共有10000 个特征。步骤如下：
1）运用 PCA主要成分分析将数据压缩至1000个特征（实际上大概能减少到 1/5 或 1/10而几乎不影响性能）
2）对训练集运行学习算法（神经网络，逻辑回归，...），输入压缩后的低维 z
3）在预测时，使用 PCA，将输入的特征 x 转通过 PCA 的映射关系转换成特征向量 z，然后再把 z 代入，进行预测
注：只在训练集上运行 PCA，拟合这些参数，而不能在交叉验证集或者测试集上。定义了 x 到 z 的映射后，可以运用在交叉验证集或者测试集的其他样本中

PCA 的应用

PCA 的应用与 k 值的选择

错误应用
1）尝试使用 PCA 防止过拟合是不好的，乖乖使用正则化就好

因为 PCA 不需要用到标签 y，只要用输入的 x ^(i)^，以此来寻找近似的低维数据，这是有损的，而正则化是需要用到 y 的
2）不要默认要用 PCA。定计划时，先想想能不能不要降维，不用 PCA，先试试能不能使用最原始的数据 x ^(i)^ 训练学习算法，太慢或者内存不够，实在不行再考虑 PCA 和 z^(i)^

非监督学习3：异常检测(Anomaly Detection)

虽然主要用于非监督学习问题，但从某些角度看，它又类似于一些监督学习问题。

问题的动机

什么是异常检测
通过 P(x) 检测异常行为
例：

上图中，在蓝色圈内的数据属于该组数据的可能性较高，而越是偏远的数据，其属于该组数据的可能性就越低。
这种方法称为密度估计
例2：欺诈检测
异常检测主要用来识别欺诈。例如在线采集而来的有关用户的数据，一个特征向量中可能会包含如：用户多久登录一次，访问过的页面，在论坛发布的帖子数量，甚至是打字速度等。尝试根据这些特征构建一个模型，可以用这个模型来识别那些不符合该模式的用户。

概率小则异常

例3：工业生产领域
检测一个计算机数据中心，特征可能包含：内存使用情况，被访问的磁盘数量，CPU的负载，网络的通信量等。根据这些特征可以构建一个模型，用来判断某些计算机是不是有可能出错了。

高斯分布（正态分布）(Gaussian Distribution, Normal Distribution)

$$
X \sim N(μ, σ^2)
$$
~ 表示“服从”

例：

红色面积，即积分一定为1

参数估计问题就是给定数据集，找到 μ 和 $$σ^2$$ 的值，计算方法如下：

基于高斯分布的异常检测算法

分布项 p(x) 的估计问题也叫密度估计问题

Π：累乘符号

异常检测算法
1）选择在出现异常时会很明显的特征量 $$x_i$$
2）对训练集，即 m 个未做标记的样本 {$$x^(i), ..., x^(m)$$}，进行参数拟合

3）给出新案例 x，计算 p(x)，判断是否异常

例：

开发和评估异常检测系统

在开发学习算法(选择特征等)时，如果有一种评估学习算法的方法，做出决策就会容易得多。
假设有一些已标记异常和非异常的数据（正常时y = 0，异常时y = 1）
训练集：无标签
交叉检验集和测试集：含标签，知道有无异常
例：
例如：有10000台（绝大多数）正常引擎的数据，有20台异常引擎的数据。这样分配数据：
6000台正常引擎的数据作为训练集（60%）
2000台正常引擎和10台异常引擎的数据作为交叉检验集（20%）
2000台正常引擎和10台异常引擎的数据作为测试集（20%）
注意：交叉训练集和测试集数据不能相同，也就是不能直接把 4000的数据又放 cv 又放 test
具体的评价方法如下：
1）根据测试集数据，估计特征的平均值和方差，使用高斯函数，构建函数 p(x)
2）对交叉检验集，我们尝试使用不同的 ε 值作为阀值，并预测 y，判断数据是否异常，根据 F1 值或者查准率与查全率的比例来选择 ε
（这里数据很倾斜(y = 0 情况占绝大多数)，所以分类正确率不是一个好的评判指标）
3）选出 ε 后，针对测试集进行预测，计算异常检验系统的 $$F_1$$ 值（= F2*（RP)/(P+R)），或者查准率与查全率之比

异常检测与监督学习对比

之前我们构建的异常检测系统也使用了带标记的数据，与监督学习有些相似，下面的对比有助于选择采用监督学习还是异常检测：

异常检测	监督学习
非常少量的正向类（异常数据 y =1）（一般 0 \~ 20 个），大量的负向类（y = 0）	同时有大量的正向类和负向类
许多不同种类的异常，很难从小数量的正样本中去学习异常种类，而且未来可能出现的异常可能又将不一样。这种情况，对负样本用高斯分布模型 p(x)来建模而不是根据非常少量的正向类数据来训练算法。	有足够多的正向类实例，足够用于训练算法，未来可能遇到的正样本与训练集中的非常近似。
例如：欺诈行为检测，生产（例如飞机引擎）检测数据中心的计算机运行状况（以上问题，在有非常多样例的情况下，也可以转成监督学习问题）	例如：邮件过滤器（有足够样例），天气预报，肿瘤分类

选择特征

下面谈谈如何选择特征：

上面那张图是正常的高斯分布图像（钟形曲线），但如果得到下面那张不像高斯分布的图像，数据的分布不是高斯分布，进行转换能使算法运行得更好
通常，对数据进行一次对数转换：

其他办法：

附：
当数据呈现偏度（Skewness）时，说明数据的分布不是对称的，即右尾长或左尾长。通过对数转换，可以拉伸或压缩数据，减少数据的偏度，使其更加接近正态分布。
此外，对数转换还可以减少数据的尖峰度（Kurtosis）。尖峰度描述了数据分布的峰度，即数据集中在平均值附近的程度。当数据的尖峰度较高时，说明数据集的峰值处比较尖锐，尾部比较厚重。通过对数转换，可以拉长数据集的尾部，减小尖峰度，使数据更加接近正态分布。

如何得到异常检测算法的特征
与监督学习的误差分析步骤类似
先训练出一个完整的算法，在一组交叉验证集上运行算法，然后找出那些预测出错的样本，并看看能否找到一些其他的特征来帮助学习算法，让那些在交叉检验集中判断出错的样本表现得更好
例：

异常样本和正常样本的 P 值差不多，人工查看没标记出来的异常样本与正常样本的区别，由此创建一个新特征，能发现异常
为异常算法选择特征变量时，可以通过将一些相关的特征进行组合，来获得一些新的更好的特征（选在异常情况下可能会特大或特小的特征）
例如，在检测数据中心的计算机状况的例子中，我们可以用CPU负载与网络通信量的比例作为一个新的特征，如果该值异常地大，便有可能意味着该服务器是陷入了一些问题中。

多元高斯分布（选修）

多元高斯分布的优势：能够描述两个特征变量之间可能存在正相关或负相关的情况

使用多元高斯分布进行异常检测（选修）

回顾一下多元高斯分布和多元正态分布：

如何把这些综合起来开发一个异常检测算法？

多元高斯模型的轮廓（等高线）总是轴对齐的，下图三个都可以用原始模型来拟合

原始模型应用更广泛

大规模机器学习(Large Scale Machine Learning)

处理大数据集

大型数据集的学习

比如上方左图，看出是高方差，添加训练用例能提升效果；而右图是高方差，添加训练用例没什么用，而是要添加额外的特征项或额外的隐藏单元

算法1：随机梯度下降法

这里以线性回归为例，当数据很大时，批量梯度下降法要遍历很多数据，还得迭代，耗时很长

随机梯度下降只需要考虑一个训练样本
步骤：
1）随机打乱所有数据：将 m 个训练样本重新随机排列（这能使收敛快一点）
2）对所有的训练样本进行遍历（1~10 次），对所有 j 更新 $$θ_j$$
（与批量梯度下降不同的是，随机梯度下降不需要对全部 m 个样本求和来得到梯度项，而只要对当个训练样本求出梯度项(见红框)）

整个过程随机迂回地朝全局最小值前进（下图红：批量，粉：随机），能得到一个很接近全局最小值的参数
这是舍弃了最优路径从而获得时间复杂度的减少

算法2：小批量(Mini-bactch)梯度下降

各种梯度下降算法样本数量

优缺点
优点：当有一个好的向量化方式时，小批量梯度下降法会比随机梯度下降法更有效，那样的话这个求和覆盖了 b 个（2~200，倾向于 10）样本的总和能以更向量化的方式执行
缺点：当有一个额外参数 b 时，确定 Mini-batch 大小可能要费些时间

确保随机梯度下降正确收敛 & α 的选择

之前确保批量梯度下降已经收敛的方法：绘制出代价函数 $$J_{(θ)}$$ 图像
但训练集非常大的时候，不希望总是暂停算法来遍历整个训练集以计算 J。
在随机梯度下降中，我们在每一次更新 θ 之前都用该样本计算一次代价 J。为了检测是否收敛，每 1000 次迭代后，求出这 1000 次对训练样例代价的平均值，然后绘制这些平均值与 1000 次迭代的次数之间的函数图表，观察是否收敛

当我们绘制这样的图表时，可能会得到一个颠簸不平（很多噪声因为才 1000 例，添加样例可使图像更加平滑，如上图 2 添加到 5000 例，变成红线，但这种缺点是每过 5000 例才能有一个数据点）看起来完全没有在减小的函数图像（如上图3中蓝线所示）。增加 α，可使函数更加平缓，也许能看出下降的趋势（如上图 3 中红线所示）；或者可能函数图表仍然是颠簸不平且不下降的（如上图 3 洋红色线所示），那么我们的模型本身可能存在一些错误

学习率a通常保持不变，如果我们想要 θ 更好地收敛到全局最小值，可以让 α 值随时间逐渐减小

迭代次数 = 已经计算出来的训练样本数量，常数1、2由我们自己选择（但得花时间去选择这两个常数，算法更复杂）
这个公式的作用是，随着算法的运行，迭代次数越来越大，学习速率 α 越来越小，每一步越来越精确，最终收敛到全局最小值

在线学习

从连续的数据流中学习，适合预测变化的事情
这种优化算法可以根据变化的用户偏好进行调适
例1：优化给用户开出的价格

例2：点击率预测学习问题（predicted click-through rate, CTR 预测），学习用户点击某一个提供给他们的连接的概率
根据用户的搜索词，匹配需要呈现的搜索结果

每个用户搜索，就获得 10 个数据样本

映射化简 & 数据并行

数据大到没法在一台电脑上跑完的情况下，可以使用映射化简（Map-reduce）方法

为书写方便，假设有 400 个样例，Map-reduce 把数据分成多个子集，本例中假设有 4 台计算机并行，故分成 4 个子集。
每个机器对 100 个样本求和，然后放到中心服务器上

其实就是把一个工作分给多个机器共同完成

这样可以加到约四倍速，但可能有网络延迟

如果要运用 Map-reduce，需要考虑：这个学习算法是否可以表示成对训练集的一种求和？

例：

Map-reduce 也可以用于单机
如果电脑有多个 CPU，多核CPU又有很多核心，可以把数据集分成多份，发送给多个核心，再把每个核心结果加起来，最终得到整个训练集之和

优点：网络延迟很小

有些线性代数函数库能够利用多核 CPU 的多个核心来并行处理矩阵运算，这时候可以不用 Map-reduce。这也是算法的向量化实现如此重要的缘故（比调用循环快）。

应用实例：图片文字识别(Application Example: Photo OCR)

本章概述：

如何组合一个复杂的机器学习系统
机器学习流水线概念
如何分配资源来对下一步计划作出决定
如何将机器学习应用到计算机视觉 CV 问题中
人工数据合成的概念

什么是照片 OCR：问题描述和流水线（pipeline）

照片光学字符识别（photo OCR, Photo Optical Character Recognition）问题：让计算机读出图片中的文字信息
扫描，读取文字

步骤：
1）文字侦测（Text detection）——将图片上的文字与其他环境对象分离开来
2）字符切分（Character segmentation）——将文字分割成一个个单一的字符
3）字符分类（Character classification）——确定每一个字符是什么
4）拼写错误纠正（这里不讨论）

这样一个系统叫做机器学习流水线
流程图表示：

一维滑动窗口

图片中文字对应的矩形长宽比不一，如何检测它们？
先来看一个行人识别的例子：
这个例子里要识别的对象具有相似的长宽比

训练步骤：
1）定长宽比例标准：82*36
2）从训练集中选一些 82*36 的正样本和负样本

思路总结：对一个图块进行处理，判断是否包含有行人
判断过程：
用之前训练识别行人的模型时所采用的图片尺寸在我们要进行行人识别的图片上进行剪裁，然后将剪裁得到的切片交给模型，让模型判断是否为行人，然后在图片上将剪裁区域滑动一个步长（也叫滑动参数，一般 4 或 8），重新进行剪裁，将新剪裁的切片也交给模型进行判断，如此循环直至将图片全部检测完
然后再用更大的图块做如上步骤（意思是选择更大的图块，然后调整到 82*36 的大小，然后给分类器）

回到文字检测：
1.流水线第一步：文字侦测
1)训练模型能够区分字符与非字符
2)运用滑动窗口技术识别字符。下图中亮白色的区域是经过这些步骤后被认为是文字的区域，灰色是可能有文字但概率不高的区域
3)将分类器的输出应用于放大算子：扩大白色区域
4)以宽高比作为过滤条件，过滤掉高度比宽度更大的区域（认为单词的长度通常比高度要大），然后在长宽比正常的矩形周围画上框
（还是会遗漏一些难以识别出来的文字）

2.流水线第二步：字符分割
分割出单个字符
再次使用监督学习算法，判断是否有文字分割的地方

3.模型训练完后，仍然使用滑动窗口技术来进行字符识别

获取大量数据和人工数据

最可靠的得到高性能机器学习系统的方法是：使用一个低偏差机器学习算法，并用庞大的训练集训练它
如果遇到一个机器学习问题，先绘制学习曲线来确保分类器偏差较低，再去想需要多少资源才能获得大量数据，这有可能是耗时短且很好的提高性能的方法

如何获得数据：

人工数据合成
手动收集数据、添加标签
众包（众包数据标记）：雇人为数据做标记，如Amazon Mechanical Turk

人工数据合成的两种形式：

自己创造数据
已有小的标签训练集，以某种方式扩充训练集

以文字识别应用为例
1)自己创造数据：从字体网站下载各种字体，然后利用这些不同的字体配上各种不同的随机背景图片创造出一些用于训练的实例。
2)已有小的标签训练集，以某种方式扩充训练集：利用已有的数据，然后对其进行修改，例如将已有的字符图片进行一些扭曲、旋转、模糊处理。注意，只有认为当实际数据可能和经过这样处理后的数据类似时，才可以创造出这样的数据。（比如改变一些随机像素的亮度在这里没有意义。再比如音频，背景音可能会有汽车噪声，但加入随机无意义的噪音是没意义的）

上限分析（Ceiling Analysis）：下一步工作的流水线（pipeline）

使用上限分析（Ceiling Analysis）可以判断哪个模块最值得投入精力去做

对学习系统使用一个数值评价量度，这里假如使用字符准确度作为量度

给测试样本捣点儿乱，对第一个模块中的每个测试样本，都给它手动提供正确的文本检测结果，即人工识别并提供 100%正确的输出结果给下一个模块，然后看应用的整体效果提升了多少。
接下来，对第二个模块，第三个，第四个，...，保留之前添加的正确样本，并执行同样操作。
执行完最后一个，得到 100%准确率。这时能明白如果对每一个模块进行改善，它们各自的上升空间有多大，由此判断重心应该在哪