机器学习

1 入门

P1-1 什么是机器学习

机器学习（Machine Learning）是计算机从某一经验 E 上学习，解决某一任务 T，进行某一性能度量 P，通过 P 测定在 T 上的表现因经验 E 而获得提高
机器学习包括：监督学习（Supervised learning），和无监督学习（Unsupervised learing），强化学习（Reinforcement Learning）

P1-2 监督学习

监督学习是：给算法一个数据集，其中包含正确答案（标签）
回归（Regression）问题：预测的结果是连续的
分类（Classification）问题：预测的结果是离散值

P1-3 无监督学习

无监督学习是：给定一个数据集，其中不包含样本的标签

2 线性回归

P2-1 模型描述

监督学习的算法过程：

P2-2 损失函数

损失函数 Loss Function 使得所假设的函数与数据更加拟合
平方误差函数 $J({\theta }_0,{\theta }_1)=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^i{)}^2$
目标: $\underset{{\theta }_0,{\theta }_1}{min}J({\theta }_0,{\theta }_1)$

P2-3 梯度下降

梯度下降(Gradient descent)最小化损失函数
思路:从一个初始值开始(一般为 0),一点点改变参数的值,使得损失函数减小,以至于达到局部最小或者全局最小
算法: ${\theta }_j={\theta }_j-\alpha \frac{\delta }{\delta {\theta }_0}J({\theta }_0,{\theta }_1)$ , $\alpha$ 是学习率(Learning rate)
当接近局部最小点时,梯度下降法会自动采用较小的步幅去更新参数,因此不需要去调整 $\alpha$ 的大小

p2-4 线性回归的梯度下降

$J({\theta }_0,{\theta }_1)=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^i{)}^2$
${\theta }_j={\theta }_j-\alpha \frac{\delta }{\delta {\theta }_0}J({\theta }_0,{\theta }_1)$

${\theta }_0={\theta }_0-\alpha \frac{\delta }{\delta {\theta }_0}[\frac{1}{2m}\sum _{i=1}^m({\theta }_0+{\theta }_1{x}^{(i)}-y^i{)}^2]={\theta }_0-\alpha [\frac{1}{m}\sum _{i=1}^m({\theta }_0+{\theta }_1{x}^{(i)}-y^i)]$
${\theta }_1={\theta }_1-\alpha \frac{\delta }{\delta {\theta }_1}[\frac{1}{2m}\sum _{i=1}^m({\theta }_0+{\theta }_1{x}^{(i)}-y^i{)}^2]={\theta }_1-\alpha [\frac{1}{m}\sum _{i=1}^m({\theta }_0+{\theta }_1{x}^{(i)}-y^i)x^{(i)}]$
损失函数一般是凸函数(convex function)只有一个全局最优解
Batch Gradient Descent:每次计算损失函数,都遍历整个数据集

3 矩阵和向量

P3-1 矩阵和向量

矩阵(matrix)
矩阵维度(Dimension): 行数 x 列数或者 ${\mathbb{R}}^{4\mathrm{x}2}$
向量(vector) 只有一列的矩阵 n x 1 ${\mathbb{R}}^4$

P3-2 矩阵乘法特征

$AB\ne BA$ 不满足乘法交换律 Not Communicative
$A(BC)=(AB)C$ 满足乘法结合率 Associative
单位向量(Identity Matrix) diagonals = 1

P3-3 矩阵的转置与逆

其中,A 是一个方阵, 并且其逆矩阵存在
没有逆矩阵的矩阵一般称为奇异矩阵(singular)或者退化矩阵(degenerate)

4 多元线性回归

P4-1 多元

多元(多特征)(Multi features)数据样本中包含多个变量
假设函数: $h_{\theta }(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2\cdots +{\theta }_n{x}_n$
矩阵形式: $h_{\theta }(x)={\theta }^{T}x$, $x=[x_0,x_1,x_2\dots {]}^T\in {\mathbb{R}}^{\mathbb{n}\mathbb{+}\mathbb{1}},\theta =[{\theta }_0,{\theta }_1,{\theta }_2\dots {]}^T\in {\mathbb{R}}^{\mathbb{n}\mathbb{+}\mathbb{1}}$

P4-2 多元梯度下降

与 P2-3 梯度下降 类似,逐个更新每个参数,每次更新时是同时更新]

P4-3 特征缩放

特征缩放(Feature Scaling)是使得特征都在相似的变化范围内,加速梯度下降的速度
如 $x_1\in [0,2000],x_2\in [0,5]$,损失函数的等值线就会很狭长,因此可以采用
1 $\frac{x_1}{2000},\frac{x_2}{5}$
2 $x_1=\frac{x_1-\mu }{s}$ 其中 $\mu$ 是均值, s 是范围(max-min) (Mean Normalization 方法)
将二者缩放到相似的范围之内
通常一般缩放到 $-3\le x_i\le 3$,但是不要太小,也不能太大

P4-4 学习率

$\alpha$ 是学习率,每次的进行梯度下降的步幅大小
如果损失函数的值在变大 or 起伏不断,则说明学习率选择的可能偏大
一般选择 0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1, 选择这中间的一个,然后偏小一点

P4-5 多项式回归

对于复杂的数据集，如果采用多元目标函数进行拟合时：
$h_{\theta }(x)={\theta }_0+{\theta }_{1}x+{\theta }_2{x}^2+{\theta }_3{x}^3$
$h_{\theta }(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2+{\theta }_3{x}_3$
则，可以通过 $x_1=x,x_2=x^2,x_3=x^3$ ,将其转为线性回归模型，同时采用特征缩放来控制特征的大小

P4-6 正规方程

正规方程：通过代数的方法，直接解出最后结果(可以不使用特征缩放)，但特征数量不要太多 1W
目标函数 $h_{\theta }(x)=\theta x+{\theta }_0$
结果: $\theta =(X^{T}X{)}^{-1}{X}^{T}y$
证明过程:

P4-7 正规方程在矩阵不可逆情况

为什么会出现不可逆的情况？
存在多余的特征，是线性相关的
存在太多的特征，如样本数量 < 特征的数量
删除多余的特征，或者采用正则化
在进行计算时，如果真的存在不可逆的情况，可以采用伪逆的方式解决

5 逻辑回归(分类)

P5-1 分类

预测值是离散的数值，如果是两个数字{0,1},则是二分类,如果是{0, 1, 2, 3},则是多分类
逻辑回归(Logistic Regression)是一种分类算法,输出的结果是 0, 1

P5-2 假设函数

在 Logistic function 中, 目标函数的输出应当在 $0\le h_{\theta }\le 1$
$g(z)=\frac{1}{1+e^{-z}},z={\theta }^{T}x$
目标函数 $h_{\theta }(x)=\frac{1}{1+e^{-{\theta }^{T}x}}$
Sigmoid Function 和 Logistic Function 是一个意思

P5-3 决策边界

目标函数 $h_{\theta }(x)=\frac{1}{1+e^{-{\theta }^{T}x}}$
如果 $h(x)\ge 0.5$,预测 y=1; 如果 $h(x)<0.5$,预测 y=0 => ${\theta }^{T}x\ge 0$ 或者 ${\theta }^{T}x<0$
决策边界:使得 $h(x)=0.5$ 的直线或者平面或者超平面(假设函数的属性,和数据集无关)
非线性决策边界:添加额外的高阶多项式

P5-4 损失函数

对于线性回归算法来说,Loss function= $J({\theta }_0,{\theta }_1)=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^i{)}^2$
对于逻辑回归算法,需要进行改动:
$J({\theta }_0,{\theta }_1)=\frac{1}{m}\sum _{i=1}^m\frac{1}{2}Cost(h_{\theta }(x^{(i)}),y^i)$,

如果不进行改动,由于目标函数变为非线性,因此损失函数将不再是凸函数

继续改写 Cost 函数
$Cost(h_{\theta }(x^{(i)}),y^i)=-y\log (h_{\theta }(x^{(i)}))-(1-y)\log (1-h_{\theta }(x^{(i)}))$
采用梯度下降 ${\theta }_j={\theta }_j-\alpha \frac{\delta }{\delta {\theta }_0}J({\theta }_0,{\theta }_1)$ 进行更新参数

与线性回归类似,逻辑回归也可以使用特征缩放

P5-5 高级优化

除了梯度下降(Gradient descent)还有共轭梯度下降法(Conjugate descent), 拟牛顿法(BFGS, L-BFGS)等高级优化方法
特点:
不需要设置 α(存在 Linear Search algorithm)
通常比梯度下降更快
但计算更加复杂

P6-6 多元分类--一对多

多分类: 输出的结果是多个
对于 n 分类问题,将其分为 n 个分类问题,对于每次分类,都将一种类别分出,直到最后只有一个类别,具体来讲,每次将要分类的类别设置为正样本,其余的设置为负样本,最后一共拟合出 n 个分类器 $h_{\theta }^{(i)}$

6 过拟合

P6-1 过拟合

欠拟合(underfitting) 没有很好的对数据进行拟合,同时具有较高的偏差
过拟合(overfitting) 有太多的特征,在训练集上表现很好,但是在测试集上表现没那么好(泛化能力很差),有着较高的方差
解决方法:
1 减少特征的数量:选择一些需要保留的特征,剔除掉一些多余的特征;采用模型选择算法
2 正则化(regularization):保留所有的特征,但是减少参数的大小

P6-2 损失函数

在损失函数中使用惩罚项并使部分θ非常小,因此更加不容易过拟合(less prone to overfitting)
因为不确定是哪个参数，因此对所有参数都进行月数
$J(\theta )=\frac{1}{2m}(\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^i{)}^2+\lambda \sum _{i=1}^m{\theta }_j^2)$， $\lambda$ 为正则化参数
当惩罚项，设置太大时候，相当于会将假设函数的参数都去除掉了，使得最后函数是一个水平直线(偏见性太强)

P6-3 线性回归正则化

Gradient Descent Algorithm
Repeat{
${\theta }_0={\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^i)x^{(i)}$ 因为不对 ${\theta }_0$ 正则化,因此需要单独进行优化
${\theta }_j={\theta }_j-\alpha [\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^i)x^{(i)}+\frac{\lambda }{m}{\theta }_j]={\theta }_j(1-\alpha \frac{\lambda }{m})-\alpha [\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^i)x^{(i)}]$ 每次在线性回归的基础上减少一点点
}

Normal Equation

如果在正规化方程中出现不可逆(样本数小于特征数)
如果 $\lambda$ 严格大于 0,则不会出现不可逆的问题

P6-4 Logistic 回归正则化

带有正则化的逻辑回归损失函数:
$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 _{i=1}^n{\theta }_j^2$
算法过程与 P6-3 线性回归正则化 形式相同，只是函数的表达式不一样

7 神经网络

P7-1 非线性假设

对于含有特征数量很多的数据,如果采用线性假设,会导致假设项非常多,很容易造成会过拟合现象,同时使得计算十分复杂,因此需要借助非线性假设

P7-2 神经元与大脑

神经重连接实验

P7-3 模型展示Ⅰ和Ⅱ

生物学中与 AI 中的神经元、神经网络

${\alpha }_i^{(j)}=$ activation of Unit i in layer j = sigmoid(input)

前向传播(forword propagation):从输入层开始,逐层计算隐藏层,最后计算出输出层

P7-4 例子与直观理解Ⅰ和Ⅱ

通过真值表可以看到神经元是如何进行计算的,以及通过设定相应的权值,使得能够实现一些逻辑运算.
对于异或操作,可以使用 A AND B, (NOT A) AND (NOT B)作为隐藏层的两个单元,A OR B 作为输出层单元

P7-5 多元分类

最后的输出是用多维向量来表示,而不是单一的数值

P7-6 代价函数

在二分类网络中,一般使用与逻辑回归相似的代价函数
Logistics Regression
$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 _{i=1}^n{\theta }_j^2$
Neural network
$J(\theta )=-\frac{1}{m}[\sum _{i=1}^m\sum _{k=1}^K{y}_k^{(i)}\log (h_{\theta }(x^{(i)}){)}_k-(1-y_k^{(i)})\log (1-h_{\theta }(x^{(i)}{)}_k)]+\frac{\lambda }{2m}\sum _{l=1}^{L-1}\sum _{i=1}^{s_l}\sum _{j=1}^{s_l+1}({\theta }_{ji}^{(l)}{)}^2$
前半部分只计算最后输出的损失函数,而后半部分的正则项则是计算所有参数的平方和

P7-7 反向传播算法

反向传播(BackPropagation)
当处于输出层时, ${\delta }_j^{(l)}={\alpha }_j^{(l)}-y_j$
当处于中间隐藏层时, ${\delta }_j^{(l)}=({\theta }^{(l)}{)}^T{\delta }^{l+1}\ast g^{\prime }(z^{(l)})$

反向传播算法
Training set {(x1, y1), (x2, y2)...(xm, ym)}
Set ${\theta }_{ij}^{(l)}=0$
For i = 1 to m
Set $a^{(1)}=x^{(1)}$
Perform forwaed propagation to compute $a^{(l)}$ for i = 2, 3, 4...
Using $y^{(i)}$ compute ${\delta }^{(L)}=a^{(L)}-y^{(i)}$
Compute ${\delta }^{(L-1)},{\delta }^{(L-2)}\dots {\delta }^{(2)}$
${\mathrm{\Delta }}_{ij}^{(l)}={\mathrm{\Delta }}_{ij}^{(l)}+a_j^{(l)}{\delta }_j^{(l+1)}$
$D_{ij}^{(l)}=\frac{1}{m}{\mathrm{\Delta }}_{ij}^{(l)}+\lambda {\theta }_{ij}^{(l)}$
其中 $$\delta_{j}^{(l)}=\frac{{\partial J(\theta)}}{\partial z_{j}^{(l)}}$$
此处可以参考李宏毅的视频反向传播(Backpropagation)

P7-8 梯度检验

采用某点的双侧微分进行对梯度近似：$$\frac {{\partial J(\theta)}} {\partial \theta}\approx\frac{J(\theta+\epsilon)-J(\theta-\epsilon)}{2\epsilon}$$
当θ是 n 维向量时,可以对θi 求偏导,第 i 处带有ε,其余位置没有ε
求的估计的梯度和算法求得的梯度如果近似,则说明是正确的

P7-9 随机初始化

• 全部初始化为 0
  • 当出现初始权重相等时,权重的更新值也会一样,导致存在高度冗余的情况(对称权重 symmetry weight)
• 随机初始化
  • 将θ初始化为[-ε,ε]内的值 -ε <= θ <=ε

P7-10 组合到一起

训练神经网络的步骤:

• 随机初始化权重
• 应用前向传播计算 $h_{\theta }(x^{(i)})$
• 计算损失函数
• 应用反向传播计算 $\frac{\partial J(\theta )}{\partial \theta }$
• 使用梯度检验来验证是否正确
• 使用梯度下降和高级算法来最小化 J(θ)

8 提升模型性能

P8-1 评估假设

1 数据集分割：
将 Dataset 分为 Training Set 和 Test Set,按照 7:3的比例随机选择

从 Training Set 学习参数(最小化训练误差),同时计算 Test Set 的误差
错误分类误差(Misclassfication error 0/1 错误分类):
Error(h(x), y) = 1 当且仅当判断错误
Error(h(x), y) = 0 当且仅当判断正确
Test error = (Σ error) / M

P8-2 模型的选择和训练,验证,测试集

将 Dataset 分为 Training Set ,Cross validation Set(交叉验证集)和 Test Set,按照 6:2:2的比例随机选择
模型选择:

• 在训练集上进行梯度下降，直到最小化损失函数,在交叉集上进行模型选择,得到最优的模型,之后再测试集上测试,得到模型的泛化能力
• 最优的模型: 考虑模型的多项式次数:1 次,2 次或者多次(d)

P8-3 方差与偏差

偏差(Bisa):用所有可能的训练数据集训练出的所有模型的输出的平均值与真实模型的输出值之间的差异
方差(Variance):不同的训练数据集训练出的模型输出值之间的差异
如果是训练集 error 与验证集 error 都高,则说明是欠拟合--高偏差
如果是训练集 error 上低,验证集 error 高,则说明过拟合--高方差

P8-4 正则化和方差,偏差

当正则化中的λ过大时,会导致拟合效果比较差,造成高 Bias
当正则化中的λ过小时,会导致拟合效果太好,造成高 Variance
如何确定λ的大小:
从小到大设置一些列的值,并将其带入到 J(θ)中,求得梯度下降后的θ,然后计算验证集中的损失大小,作为评估依据,选出最合适的λ

P8-5 学习曲线

当一个模型处于高偏差的时候,验证集损失和训练损失很接近,增大训练样本的数量对减少损失无益
当一个模型处于高方差的时候,验证集损失和训练损失之间有较大 gap,增大训练样本的数量对减少损失有帮助,会让损失下降

P8-6 总结

当发现模型不能很好的拟合数据时: (欠拟合---高偏差, 过拟合---高方差)

• 收集更多数据样本----高方差时有效
• 减少特征数量----高方差时有效
• 加入一些特征----高偏差时有效
• 增加多项式特征(x1x2, x^2 等)----高偏差时有效
• 增大λ----高方差时有效
• 减小λ----高偏差时有效
  对于神经网络而言:
• 隐藏层越少,越容易出现欠拟合,适合计算比较少的
• 隐藏层越多,越容易出现过拟合,适合计算比较大的

9 机器学习系统设计

P9-1 误差分析

推荐的方法:

• 从一个可以快速开始的简单算法开始,在验证集上进行测试
• 绘制学习曲线来决定是否是需要更多数据、更多特征
• 错误分析：检查出错的样本数据，分析是哪一类数据出现问题
  • 对错误进行分类整理
  • 考虑哪个特征会提升这一类的分类正确率

采用有数值量化的评估方法：数值反应该模型的性能和表现
大胆尝试新方法，并跟原有方法进行对比，通过量化进行取舍该 idea

P9-2 不对称性分类的误差评估

倾斜类(skewed class):数据集中每一类的数据量严重不均衡
如果数据集是倾斜类,那么分类正确率将变得意义不大.比如恶性肿瘤预测问题，假设数据集中有 0.5%的患者罹患恶性肿瘤，那么一个错误率为 1%的学习算法可能并不是一个好的算法

衡量标准:查准率(precision)和召回率(recall)

当某类结果比较少时,将该类定为 y=1(患有癌症)

P9-3 查准率和召回率的权衡

以检测癌症为例：
现在已经训练了一个能够正常检测癌症的逻辑回归模型，0 <= h(θ ) <=1
当阈值上设置比较高时, h(θ ) > 0.7 时,预测 1,否则预测 0
此时,在只有较大把握的时候才会对癌症进行预测,因此该模型会有高查准率, 低召回率

当阈值上设置比较低时,会 h(θ ) > 0.3 时,预测 1,否则预测 0
此时,在一旦有得癌症的概率, 就会对癌症进行预测,因此该模型会有高召回率, 低查准率

将查准率P和召回率R作为一个指标进行衡量,由此来自动的进行选择:

• 平均值 = (查准率 + 召回率) / 2
• F Score = $2\frac{PR}{P+R}$, 或者称为 F_1 值

P9-4 机器学习的数据

有用的自我反问: 如果给一个专家这一数据,他是否可以能够正确地预测出结果(如果不能, 那还缺一些什么必要的特征)

10 SVM

P10-1 优化目标

对于 logistics regression, 损失函数为 $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 _{i=1}^n{\theta }_j^2$
其中 $h(z)=\frac{1}{1+e^{-z}}$
当 y = 1 时,只有前半部分,是一个渐进到 0 的曲线,在 SVM 中,用一段折线代替
当 y = 0 时,只有前半部分,是一个渐进到∞的曲线,在 SVM 中,用一段折线代替

因此,SVM 的损失函数为
$J(\theta )=C[\sum _{i=1}^m{y}^{(i)}cos{t}_1({\theta }^T{x}^{(i)})-(1-y^{(i)})cos{t}_0({\theta }^T{x}^{(i)})]+\frac{1}{2}\sum _{i=1}^n{\theta }_j^2$
C 表示控制因子,如果希望正则化的力度要小一点,C 就大一些

在逻辑回归中,如果希望能够判定为正样本,只需要 ${\theta }^T{x}^{(i)}\ge 0$ 即可, 负样本则相反
在 SVM 中,如果希望能够判定为正样本,需要 ${\theta }^T{x}^{(i)}\ge 1$ 即可, 负样本则 ${\theta }^T{x}^{(i)}\le -1$ ,中间存在着一个安全距离
margin:最近样本点到决策边界的距离和

P10-2 SVM 产生最大间隔超平面的数学原理

当 C 很大时,为了使得 J 尽可能小,因此 $\sum _{i=1}^m{y}^{(i)}cos{t}_1({\theta }^T{x}^{(i)})-(1-y^{(i)})cos{t}_0({\theta }^T{x}^{(i)})$ 尽可能为 0,所以损失函数可以等效为 $min(\frac{1}{2}\sum _{i=1}^n{\theta }_j^2)$,其中需要满足
${\theta }^T{x}^{(i)}\ge 1$ 当 y = 1 是正样本
${\theta }^T{x}^{(i)}\le -1$ 当 y = 0 是负样本
根据向量内积的意义,进行变形, $\sum _{i=1}^n{\theta }_j^2={\left(\sqrt{{\theta }_1^2+{\theta }_2^2+{\theta }_3^2\cdots +{\theta }_n^2}\right)}^2$ = $\mid \mid \theta \mid {\mid }^2$
$p^i\mid \mid \theta \mid \mid \ge 1$ 当 y = 1 是正样本,其中 p 是特征 x 在参数θ上的投影长度
$p^i\mid \mid \theta \mid \mid \le -1$ 当 y = 0 是负样本
为了使得损失函数最小,因此 p 应当尽可能的大,才可以满足下面两个条件,因此等价于最大化样本到最大分隔平面的距离

P10-3 核函数

核函数(kernel function)主要用来解决非线性分类器
为了实现对非线性可分的数据集进行分类,因此需要利用很多高维特征,如 $x_1{x}_2,x_1^2,x_2^3\dots$,对每个高维度的特征用新的符号表示 $f_1,f_2\dots$,所以 $h(x)={\theta }_1{f}_1+{\theta }_2{f}_2\cdots +{\theta }_n{f}_n$
定义标记 $l^1,l^2\dots$,其中每个新符号 f 是通过特征 x 和标记l 计算得到的

...
其中 similarity 就成为核(kernel),这里使用到的是高斯核函数(Gaussian kernel)
当 x 与 l 很接近的时候,f 就会接近于 1; 当 x 与 l 距离很远的时候,f 就会接近于 0,即 f ∈ $[0,1]$,其中δ的含义是:当它很大时, 下降的就会很缓慢,当他很小时, 下降的很快
当计算出 f 以后,对于每一个靠近 f 的样本点,得到的 f 都会是 1,反之为 0

l 如何确定?
对于给定的样本数据 $(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)})\dots$
令 $l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},l^{(3)}=x^{(3)}\dots$
对于每个样本 $x^{(i)}$:
计算 $f^{(i)}=e^{(\frac{-\mid \mid (x-l^1)\mid {\mid }^2}{2{\delta }^2})}$,其中有一项一定为 1
因此,当预测是正样本(1)时,需要 ${\theta }^{T}f\ge 0$

训练的损失函数为 $\sum _{i=1}^m{y}^{(i)}cos{t}_1({\theta }^T{f}^{(i)})-(1-y^{(i)})cos{t}_0({\theta }^T{f}^{(i)})+\frac{1}{2}\sum _{j=1}^m{\theta }_j^2$

当选择较大的 C 时,也就是对于之前的表达式有更小的λ,对正则化限制力度小:
Bias 小, Variance 大
当选择较小的 C 时,也就是对于之前的表达式有更大的λ,对正则化限制力度大:
Bias 大, Variance 小
当选择较大的 δ 时,也就是对于 f 会更加平滑,对正则化限制力度小:
Bias 大, Variance 小
当选择较小的 δ 时,也就是对于 f 会更加陡峭,对正则化限制力度大:
Bias 小, Variance 大

P10-5 使用 SVM

不是所有的 similarity 都可以用作 kernel function,需要满足 mercer's Theorem
其他类型的核函数:

• 多项式核函数: $h(x,l)=(x^{T}l{)}^{2}or(x^{T}l+6{)}^{3}or(x^{T}l+constant{)}^{degree}$
• String kernel: 当输入的是字符串时
• Histogra kernel

多分类 SVM
训练 K 个 SVMs,将第 i 个从其他类别中分离出来

逻辑回归和 SVM 之间的选择
如果 n(特征)相对于 m(样本数)很大:
选择逻辑回归或者不带有核函数的 SVM
如果 n 小,m 是适中的:
选择带有高斯核函数的 SVM
如果 n 是小的,m 很大:
添加更多特征,选择逻辑回归或者不带有核函数的 SVM

11 K-Means

P11-1 无监督学习

有监督学习:样本数据有着一系列标签,用假设函数去拟合它
无监督学习:样本数据不带有标签,让算法找到数据集中隐含的结构
Clustering algorithm: 将属于一类的样本聚集在一起

P11-2 K-Means 算法

算法描述
输入的是 K 个聚类中心位置和样本数据
簇分配(cluster assignment)
首先计算各个样本到每个聚类中心的位置,选距离最小的那一个作为样本的类别
移动聚类中心(move centroid)
计算属于每个聚类中心的样本的均值,并作为该聚类中心的新位置
如果有聚类中心没有归属的样本,可以重新初始化聚类中心的位置

优化目标
$c^{(i)}$ 表示当前样本 $x^{(i)}$ 属于哪一个簇的序号,如样本 x1 属于第五簇,则 c1=5
${\mu }_k$ 表示第 k 个聚类中心
${\mu }_{c^{(i)}}$ 表示当前样本 $x^{(i)}$ 属于哪一个簇

优化目标

P11-3 随机初始化

一般做法:从 n 个样本数据中,随机挑选 K 个样本作为聚类中心
不同的随机初始化,会有着不同的聚类结果,因此会导致收敛到局部最优

• 解决方法:多次进行随机初始化,选择使得 J 最小的一组分类方法

P11-4 选择聚类数量

一: 肘部法则(Elbow Method)
刚开始损失函数下降很快,当到达一个位置后,下降速率很慢,因此较好的选择就是这一位置.但是在实际情况中,一般会很难出现像图一那样明显(图二)

二: 根据后续目的选择
如果后续需要更细致的划分,则聚类中心的数量应该多一些;反之亦然

12 主成分分析(PCA)

第二种无监督方式,称为降维

P12-1 数据压缩

如果数据高度相关,则需要考虑降维
采用低维度的数据表示可以减少内存使用的空间以及尽可能地可视化出来

P12-2 主成分分析

主成分分析(Principal Component Analysis):找到一个低维的平面,将样本投影到该平面上,使得样本到该平面的距离最短(最小化投影误差)
在进行主成分分析之前,首先应该进行归一化处理和特征规范化

注意: PCA 并不是线性回归
在线性回归中,最小化的是预测点和实际点之间误差的平方(竖直线段的平方),而不是投影

使用 PCA 将特征从 n 维减少到 k 维

• 第一步是均值归一化，计算出所有特征的均值和方向，利用归一化表达式进行计算
• 计算协方差矩阵，$\sum =\frac{1}{m}\sum _{i=1}^n(x^{(i)})(x^{(i)}{)}^T$
• 计算协方差矩阵的特征向量（利用奇异值分解 SVD进行求解）(U, S, V)=svd(sigma)
  • 对于 n x n 的矩阵，U 是一个具有与数据之间最小投射误差的方向向量构成的矩阵。如果希望从 n 维降到 k 维，秩序从 U 中选择前 k 项，获得一个 n x k 的矩阵，用 $U_{reduce}$ 表示，然后通过 $z^{(i)}=U_{reduce}^T\ast x^{(i)}$ 计算新的特征向量 $z^{(i)}=x_{approx}^{(i)}$

P12-3 主成分数量的选择

如何选择基才是最优的? 或者说，如果我们有一组 N 维向量，现在要将其降到 K 维（K 小于 N），那么我们应该如何选择 K 个基才能最大程度保留原有的信息？
希望投影后的投影值尽可能分散，因为如果重叠就会有样本消失
对于高维数据，用协方差进行约束，协方差可以表示两个变量的相关性。为了让两个变量尽可能表示更多的原始信息，我们希望它们之间不存在线性相关性，因为相关性意味着两个变量不是完全独立，必然存在重复表示的信息

选择最小特征数量 k，同时应该满足以下不等式：

分子表示投射的均方误差，也就是 99%的方差（特性）被保留下来

在机器学习框架中，可以使用 SVD(奇异值分解)来得到 $[U,S,V]=SVD(sigma)$
其中 S 是一个对角矩阵,可以用 S 对角线上的值来计算平均均方误差与训练集方差的比例

P12-4 如何重建原来的数据

考虑如下压缩过程: $z^{(i)}=U_{reduce}^T\ast x^{(i)}$
其中 $U_{reduce}^T\ast U_{reduce}=I$
因此 $x^{(i)}=U_{reduce}\ast z^{(i)}$

P12-5 应用 PCA 的建议

监督学习加速
对于所用数据集,在训练集上进行 PCA 进行降维,得到 x 到 z 的映射,运行 PCA 只需在训练集上进行,在测试和验证集上直接使用结果即可
将 PCA 误用于过拟合
应该使用更加恰当的方法进行避免过拟合(正则化 regularization)
是否应该直接使用 PCA?
首先在原始数据集上进行运行,当运行情况不满意时再去考虑使用 PCA,而不是一开始就直接使用PCA

13 异常检测

P13-1 问题引入

什么是异常检测(Anomaly detection)
异常检测主要用于无监督学习(unsupervised learning)中,判断一些数据样本是否是正常 or 异常

P13-2 利用高斯分布进行异常检测

高斯分布(Gaussian distribution) $p(x,\mu ,\delta )=\frac{1}{\sqrt{2\pi }\delta }{e}^{\frac{-(x-\mu {)}^2}{2{\delta }^2}}$
密度估计(Density estimation):
从一个数据集中,建立模型: $p(x)=p(x_1)p(x_2)\dots p(x_n)$
如果 $x\sim N(\mu ,\delta )$,那么上式可以写为 $p(x)=p(x_1,{\mu }_1,{\delta }_1)p(x_2,{\mu }_2,{\delta }_2)\dots p(x_n,{\mu }_n,{\delta }_n)$

异常检测算法:
对于给定的数据集 $x^{(1)}\dots x^{(m)}$, 针对每个特征计算它的 $\mu ,{\delta }^2$ 的估计值

当得到平均值和方差的估计值以后,给定一个训练实例,根据模型计算 $$p(x)=\prod\limits_{j=1}^np\left(x_j;\mu_j,\sigma_j^2\right)=\prod\limits_{j=1}^1\frac{1}{\sqrt{2\pi}\sigma_j}\exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})$$
当 $p(x)<ϵ$ 时为异常

P13-3 开发和评估异常检测系统

异常检测是无监督学习算法,因此无法根据结果变量 y 的值告诉我们数据是否是真的,所以需要有另一种方法检验算法的有效性: 将一部分正常样本构建 Train set, 将剩下的正常和异常数据构建出交叉验证集和测试集
例如：我们有 10000 台正常引擎的数据，有 20 台异常引擎的数据。我们这样分配数据：
6000 台正常引擎的数据作为训练集
2000 台正常引擎和 10 台异常引擎的数据作为交叉检验集
2000 台正常引擎和 10 台异常引擎的数据作为测试集

评价方法:
根据测试集数据,估计特征的平均值和方差,并构建 p(x)
对交叉检验集，我们尝试使用不同的𝜀值作为阀值，并预测数据是否异常，根据 F1 值或者查准率与查全率的比例来选择 $ϵ$ (因为正负样本差别太大,所以准确率不太能反映效果)
选出 𝜀 后，针对测试集进行预测，计算异常检验系统的𝐹1值，或者查准率与查全率之比

P13-4 异常检测和监督学习的对比

异常检测中也使用了带标记的数据,于监督学习有些相似:

P13-5 如何选择异常检测中所使用的特征

如如果数据的分布不是高斯分布，异常检测算法也能够工作，但是最好还是将数据转换成高斯分布，可以使用一些函数变换来变换这一特征，如 log，$\sqrt{}$ 等
误差分析：
某些异常的数据可能也会有较高的 P(x)值，因而被算法认为是正常的,这种情况下误差分析能够帮助我们，我们可以分析那些被算法错误预测为正常的数据，观察能否找出一些问题。我们可能能从问题中发现我们需要增加一些新的特征，增加这些新特征后获得的新算法能够帮助我们更好地进行异常检测。我们通常可以通过将一些相关的特征进行组合，来获得一些新的更好的特征（异常数据的该特征值异常地大或小）

P13-6 多元高斯分布

当有两个特征的时候，并且这两个特征的值域范围比较宽，一般的高斯分布可能不能很好的识别异常数据，原因在于，一般的高斯分布模型尝试去同时抓住两个两个特征的偏差，创造一个比较大的判定边界
在一般的高斯分布模型中，我们计算 P(X)的方法是： 通过分别计算每个特征对应的几率然后将其累乘起来（如果各个特征之间是相互独立的，那么就是一般的高斯分布模型）
在多元高斯分布模型中，我们将构建特征的协方差矩阵，用所有的特征一起来计算 P(X)。

上图是5个不同的模型，从左往右依次分析：

1. 是一个一般的高斯分布模型
2. 通过协方差矩阵，令特征1拥有较小的偏差，同时保持特征2的偏差
3. 通过协方差矩阵，令特征2拥有较大的偏差，同时保持特征1的偏差
4. 通过协方差矩阵，在不改变两个特征的原有偏差的基础上，增加两者之间的正相关性
5. 通过协方差矩阵，在不改变两个特征的原有偏差的基础上，增加两者之间的负相关性
   比较

14 推荐系统

P14-1 基于内容的推荐算法

推荐系统是一种信息过滤系统，用于预测用户对物品的“评分”或“偏好”。
${\theta }^{(j)}$ 用户 $j$ 的参数向量
$x^{(i)}$ 电影 $i$ 的特征向量
对于用户 $j$ 和电影 $i$，我们预测评分为：$({\theta }^{(j)}{)}^T{x}^{(i)}$
代价函数
针对用户 $j$，该线性回归模型的代价为预测误差的平方和，加上正则化项：

上面的代价函数只是针对一个用户的，为了学习所有用户，我们将所有用户的代价函数求和：

如果我们要用梯度下降法来求解最优解，我们计算代价函数的偏导数后得到梯度下降的更新公式为：$$\begin{aligned}\theta_k^{(j)}&:=\theta_k^{(j)}-\alpha\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)}&\text{(for}k=0)\\theta_k^{(j)}&:=\theta_k^{(j)}-\alpha\left(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)}+\lambda\theta_k^{(j)}\right)&\text{(for}k\neq0)\end{aligned}$$

P14-2 协同过滤

协同过滤（collaborative filtering）
在 14.1 节中，对于每部电影都有了可用的特征,因此可以根据这些特征去训练每一个用户的参数，同时，我们可以根据每一个用户的参数，结合用户对电影的评分，可以学习出每一个电影的参数特征

如果既没有电影的参数，也没有用户的参数，那么可以采用协同过滤算法，对二者进行同时学习，也就是由优化目标针对 x 和θ同时进行

对代价函数求偏导数的结果如下：

协同过滤算法使用步骤如下：
1 随机初始化 x 和 θ
2 使用梯度下降算法最小化代价函数
3 训练完成后，预测 $(({\theta }^{(j)}{)}^T{x}^{(i)}$ 给电影评分

P14-3 低秩矩阵分解

如果 X 是一个 m 行 n 列的数值矩阵，rank(X)是 X 的秩，假如 rank (X)远小于 m 和 n，则我们称 X 是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出，可见它包含大量的冗余信息。利用这种冗余信息，可以对缺失数据进行恢复，也可以对数据进行特征提取。
当学习到电影的，可以通过计算电影之间的向量距离，当该距离很小时，说明电影的相似度很高，可以进行推荐

P 14-4 均值归一化

当新增一个用户时，他对电影没有任何评分，如果采用上述方式进行预测，那么他得到的结果就是 0，这对评分没有任何意义，那么我们以什么为依据为Eve推荐电影呢？
首先对结果 Y 矩阵进行归一化处理，将每一个用户对电影的评分减去平均值，得到新的矩阵 Y‘，利用新的矩阵训练算法，如果利用新模型去训练算法，Eve 得到的评分为电影的均值 $({\theta }^{(j)}{)}^T{x}^{(i)}+{\mu }_i$
（前者是 0，后者是均值，因为在前面已经减去了均值，所以后面需要补回去）

15 大规模机器学习

P15-1 大数据集的学习

在进行训练之前，先考虑使用大规模数据集是否有意义，因此数据集越大，计算代价也越大，可能使用 1000 个随机选择的样本效果也不错，这点可以通过绘制学习曲线来判断

P15-2 随机梯度下降

如果我们一定需要一个大规模的训练集，我们可以尝试使用随机梯度下降法来代替批量梯度下降法（指每次梯度下降都需要对所有的数据进行计算 ）
在随机梯度下降法中，我们定义代价函数为一个单一训练实例的代价：$cost(\theta ,(x^{(i)},y^{(i)}))=\frac{1}{2}{(h_{\theta }\left(x^{(i)}\right)-y^{(i)})}^2$
算法步骤：
数据预处理：随机打乱数据（randomly shuffle）
进行随机梯度下降

每次进行迭代，随机梯度下降算法便已经走出了很远。但是这样的算法存在的问题是，不是每一步都是朝着”正确”的方向迈出的。因此算法虽然会逐渐走向全局最小值的位置，但是可能无法站到那个最小值的那一点，而是在最小值点附近徘徊。
与梯度下降的区别
梯度下降每次是计算所有的样本，作为一次更新；而随机梯度下降，是每个样本来迭代更新一次

P15-3 Mini-Batch 梯度下降

batch批量梯度下降：每次使用所有的样本对参数进行更新
stochastic随机梯度下降：每次使用一个样本对参数进行更新
Mini-Batch 梯度下降：每次使用 b 个样本对参数进行更新 （b 在 10 到 100 之间）

在使用随机梯度下降时，可以使用不断减小的α来使得震荡幅度减小，从而模型收敛到最小值处，如 $\frac{cons{t}_1}{iteration+cons{t}_2}$
对学习情况进行监测：
为了近似地监测出随机梯度下降算法在最优化代价函数中的表现，这种方法不需要定时地扫描整个训练集，来算出整个样本集的代价函数，而是只需要每次对最后 1000 个，或者多少个样本，求一下平均值。应用这种方法，你既可以保证随机梯度下降法正在正常运转和收敛，也可以用它来调整学习速率的大小

P15-4 在线学习

在线学习(online learning): 是指不适用固定的数据集,而是根据实时的用户流产生的用户数据进行学习,从而优化算法的能力,对算法进行梯度下降时,与随机梯度下降的方法有些类似:每次使用一个用户的数据进行更新参数,用完就可以不再考虑这个数据
好处在于，我们的算法可以很好的适应用户的倾向性，算法可以针对用户的当前行为不断地更新模型以适应该用户。

P15-5 映射化简和数据并行

化简映射(MapReduce):将我们的数据集分配给不多台计算机，让每一台计算机处理数据集的一个子集，然后我们将计所的结果汇总在求和。这样的方法叫做映射简化
将我们的数据集分配给不多台计算机，让每一台计算机处理数据集的一个子集，然后我们将计所的结果汇总在求和。这样的方法叫做映射简化

16 OCR

P16-1 OCR 引入

照片光学字符识别(Photo Optical Character Recognition):从一张给定的图片中识别文字
为了完成这样的工作，需要采取如下步骤：
1. 文字侦测（Text detection）——将图片上的文字与其他环境对象分离开来
2. 字符切分（Character segmentation）——将文字分割成一个个单一的字符
3. 字符分类（Character classification）——确定每一个字符是什么

P16-2 滑动窗口

滑动窗口是一项用来从图像中抽取对象的技术。假使我们需要在一张图片中识别行人，首先要做的是用许多固定尺寸的图片来训练一个能够准确识别行人的模型。然后我们用之前训练识别行人的模型时所采用的图片尺寸在我们要进行行人识别的图片上进行剪裁，然后将剪裁得到的切片交给模型，让模型判断是否为行人，然后在图片上滑动剪裁区域重新进行剪裁，将新剪裁的切片也交给模型进行判断，如此循环直至将图片全部检测完。

一旦完成后，我们按比例放大剪裁的区域，再以新的尺寸对图片进行剪裁，将新剪裁的切片按比例缩小至模型所采纳的尺寸，交给模型进行判断，如此循环。

滑动窗口技术也被用于文字识别，首先训练模型能够区分字符与非字符，然后，运用滑动窗口技术识别字符，一旦完成了字符的识别，我们将识别得出的区域进行一些扩展，然后将重叠的区域进行合并。接着我们以宽高比作为过滤条件，过滤掉高度比宽度更大的区域（认为单词的长度通常比高度要大）。下图中绿色的区域是经过这些步骤后被认为是文字的区域，而红色的区域是被忽略的。

下一步是训练一个模型来完成将文字分割成一个个字符的任务，需要的训练集由单个字符的图片和两个相连字符之间的图片来训练模型
最后一个阶段是字符分类阶段，利用神经网络、支持向量机或者逻辑回归算法训练一个分类器即可。

P16-3 获取大量数据和人工数据

如果模型是低偏差的,获取更多的数据,有助于训练模型;如果是高偏差的,首要任务是解决修改模型,使得拟合效果更好

如何获取更多的数据
以文字识别应用为例，我们可以字体网站下载各种字体，然后利用这些不同的字体配上各种不同的随机背景图片创造出一些用于训练的实例，这让我们能够获得一个无限大的训练集。这是从零开始创造实例。
另一种方法是，利用已有的数据，然后对其进行修改，例如将已有的字符图片进行一些扭曲、旋转、模糊处理。只要我们认为实际数据有可能和经过这样处理后的数据类似，我们便可以用这样的方法来创造大量的数据。
有关获得更多数据的几种方法：
1. 人工数据合成
2. 手动收集、标记数据
3. 雇人标记

P16-4 上限分析

如何能够知道哪一部分最值得我们花时间和精力去改善呢？这个问题可以通过上限分析来回答。
流程图中每一部分的输出都是下一部分的输入，上限分析中，我们选取一部分，手工提供100%正确的输出结果，然后看应用的整体效果提升了多少。假使我们的例子中总体效果为72%的正确率。

如果我们令文字侦测部分输出的结果100%正确，发现系统的总体效果从72%提高到了89%。这意味着我们很可能会希望投入时间精力来提高我们的文字侦测部分。

接着我们手动选择数据，让字符切分输出的结果100%正确，发现系统的总体效果只提升了1%，这意味着，我们的字符切分部分可能已经足够好了。

最后我们手工选择数据，让字符分类输出的结果100%正确，系统的总体效果又提升了10%，这意味着我们可能也会应该投入更多的时间和精力来提高应用的总体表现。