机器学习初等指南(2)

这是基于吴恩达机器学习》课程的笔记第二部分(监督学习:神经网络、优化设计、支持向量机),也包括其它一些可能的学习资源。

第一部分(监督学习1)传送门:Here

第三部分(无监督学习)传送门:Here

References

机器学习周志华) “西瓜书”,教材

机器学习实战 基于Python的编程练习册

统计学习方法李航) 算法的数理分析

机器学习训练秘籍吴恩达) 面向工程应用的指南

机器学习笔记1吴晓军)重点参考笔记

机器学习笔记2 面向软件的介绍手册

机器学习训练营

机器学习的一些资料

神经网络与深度学习

《动手学深度学习》 深度学习进阶

AiLearning

機器學習基石机器学习技法林轩田) 进阶教学视频

神经网络

非线性假设

通过多项式特征,我们可以令逻辑回归支持非线性的分类问题。

上图中,房屋的特征由原来的 2 维增加到 100 维,进行二次多项式扩展后,特征个数达到了约 5000 维,对计算机的性能提出了很大的挑战。一个方法是只考虑$x_i^2$平方项,但是这样会损失决策边界的刻画能力,无法适应复杂的边界。
假定我们现在有 n 维特征,需要进行非线性分类,仅扩展特征为二次多项式,特征个数就为 $n+C_n^2≈\frac{n^2}{2}$ 个,空间复杂度就为 O(n^2)。如果扩展到三次多项式,则空间复杂度能达到 O(n^3)。

计算机视觉(CV)领域,很多人不理解为什么困难。事实上图像的特征往往都是高维的。下图中,我们想要区分一幅图像是否是汽车图像,假定图像分辨率为 50×50,且每个像素的灰度都为一个特征,那么一副图像的特征维度就高达 2500 维(考虑RGB时7500维),进行二次多项式扩展后,特征维度更是达到了约 3百万维

为了处理高维特征的非线性分类问题,引入了一个新的机器学习模型——神经网络。

神经网络基础

推荐教学视频Part 1, Part 2, Part 3。(3Blue1Brown or WelchLab

下图来自Here,展示了一个典型的二分类四层人工神经网络(多层感知机)的运作方式:

以及多元分类的神经网络:

EnviousNiftyCorydorascatfish-size_restricted

神经网络是模拟人脑功能的算法。人工神经网络(ANN:Artificial Neural Network),简称神经网络(NN:Neural Network)。迄今为止,人工神经网络尚无统一定义,它是一种模拟了人体神经元构成的数学模型,依靠系统的复杂程度,通过调整内部大量节点之间相互连接的关系,从而达到处理信息的目的。

The “one learning algorithm” hypothesis,一个算法解决一切。
如下图,你甚至可以将任何传感器接入神经系统,大脑将自动学会如何分辨事物。

大脑将自动学会如何分辨事物

神经网络曾经在上世纪80、90年代被广泛应用,但在90年代后期遭受冷落。

感知机是最简单的神经网络。当时,Minsky指出感知机无法解决异或问题。(More

可以认为神经网络是一种特殊的有向图(90度左旋后的篱笆网络(Lattice))。(More

  • 所有节点分层,每一层通过有向弧指向上一层节点
  • 但同一层无弧连接(并行),不跨层连接(局部性)【特征存在视界】
  • 每条弧有一个权重

神经元

神经元

神经元可以分为四个区域:

  • 接收区(receptive zone)树突(输入)接收到输入信息。
  • 触发区(trigger zone):位于轴突和细胞体交接的地方,决定是否产生神经冲动。
  • 传导区(conducting zone):由轴突(输出 )进行神经冲动的传递。
  • 输出区(output zone):神经冲动的目的就是要让神经末梢/突触的神经递质/电力释出,才能影响下一个接受的细胞(神经元、肌肉细胞或是腺体细胞),此称为突触传递。

More:贝叶斯网络。(从贝叶斯方法谈到贝叶斯网络

神经元按照传输方向及功能为三种:

感知机

Ex: (Perceptron in 2D, 此处为线性分类器)

1547233129090

感知机算是最早期的Hypothesis模型了。(参考林轩田老师的视频
一个感知机的简洁算法称为Perceptron Learning AlgorithmPLA,感知机学习算法)。如下图:
1547234017119

注意W是决策边界的法向量。该原理是矢量叉乘判断方向(左/右)。(计算几何

证明:我们有评价分数为$ynW{t}^{T}x_n$(同向正值),并且

则等价为下式,其中红色部分$\geq0​$

故每次评价都不会变差。(详细的证明可以参考:Here,,或参看《统计学习方法》P31)

对于一个线性不可分的点集(比如,有噪声),可以退而求其次,求分错误差最小的情况。
(这个解法将是一个NP-Hard问题。利用Pocket算法贪心地更新算法【每次更新时要比较】可以迭代一个还不错的结果)


一个神经元可以(在计算机上)被实现为一个简单的逻辑单元——

感知机:最简单的神经网络。一个输出层,一个输入层。一个计算夹层(图中的有向边)。

向量形式为:($x_0$是偏置单元(bias unit),其值常设为1,相当于函数中的常数项)

激活函数

其中,$h_\theta(x)=g(\theta x)$中的g称为神经元的激活函数(Activation function):(如,线性整流函数

激活函数:$g(z)$,为线性模型增加一次非线性变换,从而增强神经网络的分类能力。(More

更具体的形式为:

详细内容直接参考Here吧。

神经网络

对于更复杂的多层神经网络,逻辑上一般可以分为三层:(忽略计算夹层)

  • 输入层:输入层接收特征向量 x。
  • 输出层:输出层产出最终的预测 h。
  • 隐含层:隐含层介于输入层与输出层之间,之所以称之为隐含层,是因为当中产生的值并不像输入层使用的样本矩阵 X 或者输出层用到的标签矩阵 y 那样直接可见。

图中神经元之间的边如何连接,称为神经网络的架构(architecture)。
不过架构一般是指神经网络有多少层、每层多少个神经元。

典型的传播(计算)过程如下:

传播算法

神经网络的计算过程写为向量形式:(偏置$a_0^{(i)}=x_0=1$)

这个计算过程称为前向传播算法(Forward Propagation)。

神经网络每层都包含有若干神经元,层间的神经元通过权值矩阵 $\Theta^{l}$ 连接。一次信息传递过程可以如下描述:

  1. 第j层神经元接收上层传入的刺激(神经冲动):

  2. 该刺激经激活函数(activation function)g 作用后,会产生一个激活向量 $a^{(j)}$。其表示的就是 j层第 i 个神经元获得的激活值(activation)

这个过程的发生顺序是不断地将刺激由前一层传向下一层——前向传播。

为了基于线性分类实现复杂的非线性分类,多层的神经网络采用复杂函数拟合,利用隐藏层完成非线性空间到线性的变换。

一般来说,层数越多,神经网络的效果越好。(如下图

多层神经网络

神经网络入门

神经网络浅讲:从神经元到深度学习

逻辑运算拟合

:(非线性分类问题,XOR/XNOR

1546655609880

为了实现上述的能拟合XNOR运算的神经网络。

$\longrightarrow$我们可以先看一个简化的例子:实现AND运算。

不如令权重$\Theta^{(1)} = \begin{bmatrix} -30 & 20 & 20 \end{bmatrix}$,得到一个构建好的神经网络如下:

AND

向量形式为:

采用Sigmoid激活函数:(g(4)≈1, g(-4)≈0)

最后前向传播运算的结果为:

可以基于这些简单的网络来生成更复杂的逻辑运算:

我们目前掌握了三种逻辑神经网络:AND(NOT)AND(NOT),和OR

现在可以着手解决XNOR运算的拟合了!过程如下图:

XOR异或运算也能被拟合,只须将图中对应换为OR(NOT)OR(NOT),和AND

多元分类

Handwritten Digit Classification - Yann Lecun:(更复杂的例子——手写识别)


:(假定我们需要将图像分为四类——行人车辆摩托车卡车。)

这是一个多分类问题,由于图像特征较多,因此我们可以考虑设计含有多个隐含层的神经网络来完成特征优化(扩展):

注意,我们设计了一个含有多个输出的神经网络,亦即,我们会用不同的激活状态来定义分类:

这样容易利用上简单的 sigmoid 函数来进行预测:

整个网络的数学表达则描述为

代价函数

符号标记:

神经网络的层与层之间都可以看做构成了一个多个逻辑回归问题(根据神经元的数量),因此,其代价函数与逻辑回归的代价函数类似,其中 K 代表类别,l 表示层级,并且考虑了正则化

矩阵形式为:

其中.∗ 代表点乘操作,$A∈R^{(K×m)}$ 为所有样本对应的输出矩阵,其每一列对应一个样本的输出。

$Y∈R^{(m×K)}$ 为标签矩阵,其每行对应一个样本的类型。

反向传播

相当于链式梯度下降。(从一个空间过渡到下一个临近空间,每一个空间都梯度下降即可)

与回归问题一样,我们也需要通过最小化代价函数 J(Θ) 来优化预测精度的,但是,由于神经网络允许多个隐含层,即,各层的神经元都会产出预测,因此,就不能直接利用传统回归问题的梯度下降法来最小化 J(Θ),而需要逐层考虑预测误差,并且逐层优化。为此,在多层神经网络中,使用反向传播算法(Backpropagation Algorithm)来优化预测,首先定义各层的预测误差为向量 $δ^{(l)}$:

其中激活函数g的导数为

推导:

反向传播中的反向二字也正是从该公式中得来,本层的误差 δ(l) 需要由下一层的误差 δ(l+1) 反向推导。在忽略正则因子$\lambda$的情况下, 我们将能够推导出偏导项

不过对于误差向量,在数学上也有,


训练过程

假定有训练集 ${(x^{(1)}, y^{(1)}),…,(x^{(m)},y^{(m)})}$,使用了反向传播的神经网络训练过程如下:

  • for all l,i,j,初始化权值梯度:(用来计算$\frac{\partial}{\partial\theta_j^{(l)} }J(\theta)$)
  • for i=1 to m:(前向传播激活,反向传播误差)
  • 求各层权值的更新增量 $D^{(l)}$(连接偏置的权值不进行正则化):
  • 更新各层的权值矩阵 $\Theta^{(l)}$(其中 α 为学习率):

参数展开

我们之前在Logistic回归部分介绍过高级优化算法,比如

1
2
3
4
function [jVal, gradient] = costFunction(theta)
……………………
endfunction
[optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options)

不同于Logistic回归的向量,在神经网络中,这里面临的工作对象是一些矩阵
这对于编程里面一些的 API (接口)是不友善的,例如 matlab 或者 octave 的 fminunc() 方法,scipy 中的 minimize 方法等,这些方法都支持传递代价函数costFunction()。但代价函数只支持传递向量作为参数。
因此,我们需要先将矩阵元素展开(Unroll)为一个长向量。具体操作如下:

1
2
3
4
5
6
thetaVector = [ Theta1(:); Theta2(:); Theta3(:); ]
deltaVector = [ D1(:); D2(:); D3(:) ]
#假定:Θ(1)∈R10×11,Θ(2)∈R10×11,Θ(3)∈R1×11
Theta1 = reshape(thetaVec(1:110),10,11)
Theta2 = reshape(thetaVec(111:220),10,11)
Theta3 = reshape(thetaVec(221:231),1,11)

梯度检测

在实现神经网络时可能产生许多微小的BUG,可能看起来好像是正常运行,尽管代价函数在不断减小,但最后得到的神经网络的误差可能比无BUG情况下高1个数量级。

因此,需要使用称为梯度校验(Gradient Checking)的手段。

我们可以在点Θ附近的小区间 [ Θϵ, Θ+ϵ],构造下图所示直角三角形来近似$J(Θ)$在Θ处的导数:

通常,ϵ 取较小值,如 $10^{-4}$。

对于更多参数,

1
2
3
4
5
6
7
for i  = 1:n,
thetaPlus = theta;
thetaPlus(i) = thetaPlus(i) + EPSILON;
thetaMinus = theta;
thetaMinus = thetaMinus(i) - EPSILON;
gradApprox(i) = (J(thetaPlus) - J(thetaMinus)) / (2*EPSILON);
endfor

则$J(Θ)$梯度近似为:

利用反向传播也可获得一个梯度:

比较gradApproxDVec相似度(比如可以用欧式距离余弦相似性):

如果上式成立,则证明网络中BP算法有效。

  • 在正式训练之前,请关闭梯度校验算法(因为梯度的近似计算效率很慢

Θ随机初始化

在逻辑回归中,我们通常会初始化所有权值为 0,假如在如下的神经网络也采用 0 值初始化:

你将很容易看出,每次迭代,所有权值的数值都一样,这意味着,隐含层的神经元激活值也将一样,也就是无论隐含层层数有多少,各层的神经元有多少,由于各层的神经元激活值大小一样,也就相当于各层只有一个有效神经元(特征),这就失去了神经网络进行特征扩展和优化的本意了。

相当于退化为了马尔可夫链

固定值初始化将会让神经网络丧失其特性。因此,对于各层的权值矩阵,应该采用随机初始化策略。随机值产生的区间我们定义为 [−ϵ,+ϵ]。(假定$\Theta^{(1)} \in R^{10 \times 11}, \Theta^{(2)} \in R^{1 \times 11}$)

1
2
Theta1 = rand(10,11) * (2 * INIT_EPSILON) - INIT_EPSILON;
Theta2 = rand(10,11) * (2 * INIT_EPSILON) - INIT_EPSILON;

总结

  • 选择一个神经网络的架构
    • 多少层
      • 一般1个隐藏层
    • 每层几个神经元
      • 输入层的单元数等于样本特征数
      • 输出层的单元数等于分类的类型数
      • 多个隐藏层一般采用相同数量的神经元(>=输入输出层)
      • 每个隐层的单元数通常是越多分类精度越高,但是也会带来计算性能的下降,因此,要平衡质量和性能间的关系
  • 随机初始化权值$[−ϵ,+ϵ]$
  • 前向传播计算激活值$h_\Theta(x)$
  • 计算代价函数$J(\Theta)$
  • 反向传播计算误差,获得$\frac{\partial}{\partial\theta_j^{(l)} }J(\theta)$
    • 梯度检验,比较反向传播和梯度的数值解,Disabled
  • 利用梯度下降(或高级优化算法)优化$J(\Theta)$

最后,一个神经网络在无人驾驶中的应用视频:

优化设计

玄学调参?

:(House Price Prediction)

我们在房屋价格预测中使用上述的代价函数。但实际中可能预测并不准确,有很大的误差。

想要降低预测误差,即提高预测精度,我们往往会采用这些手段:(Debugging)

手段 评价
获得更多的样本 见多识广会让人变得聪明,也会让人变得优柔寡断,聪明反被聪明误?
减少特征数量 也许被降掉的维度会是非常有用的知识。
采集更多的特征 增加了计算负担,可能导致过拟合。
高次多项式回归 很可能造成过拟合。
调试正则因子 λ 这个调节策略缺乏指导,只能是猜测性调节。

可以看到,这些手段不总是那么美好,而且每个手段的尝试都会花费我们大量时间去调代码,跑测试,也许还出力不讨好

泛化能力评测

在线性回归的章节中,我们已经知道,仅仅具备一个很小的训练误差并不能保证我们的预测函数就是优秀的,因为这种“优秀”仅仅体现在了对于已知的训练样本的假设上,而无法保证见到新的样本时候还能做出足够好的预测,过拟合就是当中的典型例子。

因此,预测准不准应当反映在对于新样本的泛化(generalization)能力。我们考虑将数据集划分为:

  • 训练集(Training set):70%
  • 测试集(Test set):30%

在对数据集进行训练集和测试集的划分前,最好先对数据集进行乱序,防止类似样本聚到一起

引入如下符号:

  • $(x^{(1)},y^{(1)})$:训练样本
  • $(x{test}^{(1)},y{test}^{(1)})$:测试样本
  • $m$:训练集样本容量
  • $m_{test}$:测试集样本容量

线性回归的测试误差

在线性回归中,我们就通过计算测试集的代价函数(误差)来评估参数 θ 的泛化能力:

逻辑回归的测试误差

在逻辑回归中,测试集的代价函数为:

由于逻辑回归处理的是 0/1 分类问题,其预测结果只有正确与错误之分,所以引入误分率(Misclassification Error):(形式更简单)

则逻辑回归中的测试误差也可以表示为:

交叉验证

在多项式回归中,我们引入多项式次数(degree)作为一个新的参数,形成了不同的预测模型:

对每一个模型,我们都可以计算各个模型对应的训练集误差,并优化出参数向量$\theta$。

接着,我们可以基于获得的参数向量,计算测试集误差从而选出最优模型。

假设 degree=5 时,测试误差最小,我们就选出了以下模型来迎接新的样本:

但是!实际上我们只是用训练集来拟合了一个额外的参数degree
这时在测试集上获得的泛化误差很可能是过于乐观的(an overly optimistic estimate)。

对于 degree 的确定,是我们对于模型的选择(Model Selection),正如我们在线性回归中确定 θ 一样。在线性回归中,我们通过训练集确定模型,测试集来评估模型的泛化能力。在多项式回归中,我们通过训练集获得了参数 θ,而通过测试集确定了模型,那么,这两个集合用完了,我们就缺少评估模型泛化能力的数据集。

鉴于此,引入了交叉验证集(Cross Validation Set)“交叉”二字体现了一种承上启下的关系——通过训练集获得的结果,选择了模型,并将该模型交给测试集进行评估:

  • 训练集:60%,确定参数 θ
  • 交叉验证集20%,进行模型选择。
  • 测试集:20%,评价模型泛化能力。

说实话,感觉这时候测试集并没有什么卵用。啥也不能做,就评价一下?

可能需要循环验证?

更多的交叉验证解释可以看这里:交叉验证

应用最多的是S折交叉验证(S-fold cross validation)

  • 首先随机地将已给数据划分为S个大小相同的子集
  • 利用S-1个子集训练模型,用1个子集测试
  • 对S中可能的选择重复,选出平均测试误差最小的模型

这样似乎可以在小样本中剔除一些异常/不合理数据带来的规律误导。

偏差与方差

在机器学习中,

  • 偏差(bias)反映了模型无法描述数据规律【欠拟合
  • 方差(variance)反映了模型对训练集过度敏感,而丢失了数据规律【过拟合

高偏差和高方差都会造成模型泛化能力弱,从而无法作出对新样本的准确预测。

通过诊断(Diagnose)模型是出现了高偏差问题还是高方差问题,我们就能对症下药,采取不同的解决策略。


多项式次数

下图反映了训练集、交叉验证集误差随多项式次数 d 的变化规律:

在前面的章节中,我们知道,多项式回归中,如果多项式次数较高,则容易造成过拟合,此时训练误差很低,但是对于新数据的泛化能力较差,导致交叉验证集和测试集的误差都很高,此时模型出现了高方差

而当次数较低时,又易出现欠拟合的状况,此时无论是训练集,交叉验证集,还是测试集,都会有很高的误差,此时模型出现了高偏差


正则因子

正则化(Regularization)能帮我们解决过拟合问题,λ 取值越大,对参数 θ 的惩罚力度就越大,能够帮助解决过拟合问题,但是,如果惩罚过重,也会造成欠拟合问题,即会出现高偏差。如果 λ 取值较小,则意味着没有惩罚 θ,也就不能解决过拟合问题,会出现高方差

下图反映了正规化过程中,训练集、交叉验证集误差随 λ 变化的曲线:


训练集大小

训练样本的数目m较小时,意味着可供学习的知识较少,则模型在训练阶段不容易犯错误(训练集误差极低),但也发现不了数据的规律(交叉验证集误差极高);而当样本数目增多时,意味着需要学习的知识增多,则模型虽然在训练阶段容易犯一些错(训练集误差开始增高),但也更容易探测出数据规律(交叉验证集误差降低):

如果模型出现了高偏差,即出现了欠拟合,学习曲线随样本数目的变化曲线如下图所示,即增加样本数目,仍无法显著降低交叉验证集误差,即无法提高模型的泛化能力:(训练集交叉验证集

如果模型出现了高方差,即出现了过拟合,学习曲线随着样本数目变化的曲线如下图所示,即增加样本数目,可以显著降低交叉验证集的误差,提高模型的泛化能力:(训练集交叉验证集


神经网络的架构

当神经网络的结构简单时,则易出现高偏差

当神经网络的结构过于复杂时,则易出现高方差,此时可以通过增大 λ 来解决:

总结

场景 解决手段
高方差 样本++
高方差 特征维度- -
高方差 正则因子 λ++
高偏差 特征数++
高偏差 正则因子 λ- -
高偏差 多项式次数++
高偏差 模型复杂度- -

系统设计

垃圾邮件分类器

假定我们现有一封邮件,其内容如下:

1
2
3
4
5
6
7
8
9
From: cheapsales@buystufffromme.com
To: ang@cs.stanford.edu
Subject: Buy now!

Deal of the week!Buy now!
Rolex w4ches - $100
Med1cine (any kind) - $50
Also low cost M0rgages
available.

充斥着各种诱人的促销信息,很有可能是一封垃圾邮件(Spam)。
假定我们有一个垃圾邮件的数据集,想通过机器学习的方式来学会鉴定邮件是否是垃圾邮件。

我们令向量 x 表示垃圾邮件的特征向量,该向量包含了 100 个按字母序排序的单词特征,这些单词通常为垃圾邮件常出现的词汇:discount,deal,now 等等:(通常可以根据词汇频率表来自动选择特征)

令 y 标签表示该邮件是否是垃圾邮件:

那么垃圾邮件分类就是一个 0/1 分类问题,可以用逻辑回归完成。

我们考虑如何降低分类错误率:

  • 尽可能的扩大数据样本Honypot 做了这样一件事,把自己包装成一个对黑客极具吸引力的机器,来诱使黑客进行攻击,就像蜜罐(honey pot)吸引密封那样,从而记录攻击行为和手段。
  • 添加更多特征:例如我们可以增加邮件的发送者邮箱作为特征,可以增加标点符号作为特征(垃圾邮件总会充斥了?,!等吸引眼球的标点)。
  • 预处理样本:正如我们在垃圾邮件看到的,道高一尺,魔高一丈,垃圾邮件的制造者也会升级自己的攻击手段,如在单词拼写上做手脚来防止邮件内容被看出问题,例如把 medicine 拼写为 med1cinie 等。因此,我们就要有手段来识别这些错误拼写,从而优化我们输入到逻辑回归中的样本。(相似哈希

但很多情况下,大家都是随机地选择一个方向进行探索。下一将使用误差分析的工具优化这个决策过程。

误差分析

Recommended approach

  • 一开始先快速实现一个简单算法,尽量不要将问题复杂化(不要提前优化),然后通过交叉验证集评估模型。
  • 通过绘制学习曲线(learning curve),确定面临的问题是高偏差还是高方差,来决定是添加更多训练样本,还是添加更多特征。
  • 误差分析:甚至可以手工检查交叉验证集中误差较大的样本,观察错误的来源、规律以形成解决策略。

:(垃圾邮件分类)假定交叉验证集有 500 个样本,即 mcv=500,我们的模型错分了其中 100 个样本,那么我们会通过下述手段进行错误分析。(有点像DEBUG

  1. 哪些邮件被错分了,是假冒伪劣的推销邮件?医药邮件?还是钓鱼邮件?
    • 在这 100 个错分样本中,我们发现有 53 个样本是钓鱼邮件,因此,我们就需要考虑为模型注入识别的钓鱼邮件的能力
  2. 提供什么线索(特征)能帮助模型区分出这些邮件?
    • 继续观察,我们发现,在这 53 封钓鱼邮件中,故意使用错误拼写的邮件有 5 封,来源可疑(发送人可疑)的邮件有 16 封,使用了大量煽动性标点符号的邮件有 32 封。因此,对于识别钓鱼邮件来说,我们更适合将煽动性标点符号添加为特征,而不用再考虑去识别错误拼写。

The importance of numerical evaluation

  • 应该将discount/discounts/discounted/discounting视为同一个词吗?
  • 比如,利用stemming词干提取软件进行分析(尽管误差分析不确保性能提高,但不妨一试)
  • 这样,一个对算法性能数值化的评估就显得尤为重要【Automatically判断性能是否提高】

偏斜类(Skewed Classes)

假定我们通过逻辑回归来预测病人是否患有癌症:

并且,令人欣喜的是,测试集的错误率只有 1%。别着急高兴,假如我们的测试样本中只有 0.5% 患有癌症,那么我们何不直接让预测函数为$h_{\theta}(x) = 0​$?即,我们永远预测病人不患病,那么准确率会高达 99.5%。但这可不是一件好事儿,我们追求高准确率牺牲的是病人的利益。引起这个问题的原因是样本中出现了偏斜类(Skewed Classes),偏斜即倾斜,大量样本倾斜向了某一类型悬殊】。

从上面的例子我们知道,单纯地使用误差(Error)并不能完善地评价模型好坏,我们可能要采用新的方式来度量误差。(精准、平衡)

现在引入两个重要的评价指标:(1)查准率(Precision);(2)召回率(Recall),并定义:

  • 阳性(Positive):表示正样本。当预测和实际都为正样本时,表示真阳性(True Positive);如果预测为正样本,而实际为负样本,则表示假阳性(False Positive)。
  • 阴性(Negative):表示负样本。当预测和实际都为负样本时,表示真阴性(True Negative);如果预测为负样本,而实际为正样本,则表示假阴性(False Negative)。
真值1 真值0
预测1 True Positive False Positive
预测0 False Negative True Negative
  • 查准率(Precision)

在上例中,查准率就描述了:在我们预测患癌的病人中,确实患了癌症的病人的比例。从公式中我们也可以得出,要想得到提高查准率,我们就要降低假阳性的出现的频次,即,我们只有在拥有十足的把握是,才预测一个样本为正样本。

  • 召回率(Recall)

在上例中,召回率就描述了:在患癌的病人中,有多少病人被我们预测到了。从公式中我们也可以得出,要想提高召回率,我们就要降低假阴性出现的频次,即,尽可能不放过任何可能为正样本的样本。

权衡

理想状况下,我们希望假设函数能够同时具备高准确率(High Precision)及高召回率(High Recall)。但是往往鱼和熊掌不可兼得。回到预测病人患癌的例子中,假定我们的预测函数为:

即,我们设定的预测阈值为 0.5。这么做似乎风险不小,很多没有患癌的病人被我们认为患有癌症而接受了不必要的治疗(Even get a shock),因此,我们调高我们的阈值为 0.7:(甚至0.9)

此时,必须有较高的把握,我们才会预测一个病人患有癌症,避免非癌症患者接受到了不必要的治疗,假阳性样本少,此时我们也获得了高查准率。然而,这么预测的代价是,有些癌症病患体征不明显,就被我们认为没有患癌,从而得不到治疗,假阴性样本多,即我们的召回率偏低。如下图所示:

能不能把权衡的过程自动化呢?
当我们尝试构建了不同的算法模型(不同阀值),并且获得了不同的查准率和召回率:

Precision Recall
算法 1 0.5 0.4
算法 2 0.7 0.1
算法 3 0.02 1.0

那么选择哪个算法是最好的呢,假定我们使用平均值来权衡查准率和召回率:

Precision Recall Average
算法 1 0.5 0.4 0.45
算法 2 0.7 0.1 0.4
算法 3 0.02 1.0 0.51

按照平均值,我们会选择算法 3,但是这并不是一个好的算法,因为其查准率太低了,我们希望有一个指标能选出查准率和召回率都高的算法,为此,引入了$ F_1Score$:

从公式中也可以看到,分子是查准率和召回率的乘积,只有二者都较高时,$ F_1Score$ 才会较高,特别地:

Precision Recall F1Score
算法 1 0.5 0.4 0.444
算法 2 0.7 0.1 0.175
算法 3 0.02 1.0 0.0392

$ F_1Score$ 帮我们选出了算法1,事实也确实如此,算法1的查准率和召回率都较高。

大数据

:(Designing a high accuracy learning system)

  • 自动完形填空:(Classify between confusable words)
    • For breakfast I ate _ eggs.(to/two/too)

Algorithms:(可选算法)

  • Perceptron(Logistic Regression)
  • Winnow
  • Memory-based
  • Naive-Bayes

这些算法在训练数据量提升以后都表现得越来越优异,性能都提升了

在机器学习领域,流传着这样一句话:

It’s not who has the best algorithm that wins.
It’s who has the most data.

所以商业社会中,互联网公司都不遗余力地先收集一波大数据再说,没有数据,再多的手段也是空谈。

什么时候采用大规模的数据集呢

  • 一定要保证模型拥有足够的参数(线索),对于线性回归/逻辑回归来说,就是具备足够多的特征,而对于神经网络来说,就是更多的隐层单元。这样,足够多的特征避免了高偏差(欠拟合)问题,而足够大数据集避免了多特征容易引起的高方差(过拟合)问题。

SVM(支持向量机)

代价函数

在正式讲述SVM之前,我们将回顾逻辑回归

在Logistic回归中,我们的预测函数为:$h_{\theta}(x) = \frac{1}{1+e^{-\theta^T x} }$。

代价函数为:$cost = -ylogh{\theta}(x)+(1-y)log(1-h{\theta}(x))$。

同时,当预测值 y=1 时,代价函数就为:(其实之前本来就是下面这个表达式推出来上面的)

此时,代价函数随 z 的变化曲线如下图:

不难看出,当 y=1 时,随着 z 取值变大,预测代价变小,因此,逻辑回归想要在面对正样本 y=1 时,获得足够高的预测精度,就希望 $z=θ^Tx≫0$。

而 SVM 则将上图的曲线拉直为下图中的折线,构成了 y=1 时的代价函数曲线 cost1(z):(近似化,并获得更简单的数值

当 y=1 时,为了预测精度足够高,SVM 希望 $θ^Tx≥1$。

当 y=0 时,SVM 定义了代价函数 cost0(z),为了预测精度足够高,SVM 希望 $θ^Tx≤−1$:


在Logistic回归中,最小化预测代价的过程为:

SVM定义其最小化预测代价的过程为:

事实上,我们可以将逻辑回归的代价函数简要描述为:

而 SVM 的代价函数描述为:

即,在逻辑回归中,我们通过正规化参数 λ 调节 A、B 所占的权重,且 A 的权重与 λ 取值成反比。而在 SVM 中,则通过参数 C 调节 A、B 所占的权重,且 A 的权重与 C 的取值成反比。亦即,参数 C 可以被认为是扮演了 $\frac{1}{λ}$ 的角色。(C通常取值较大)

当我们根据上述的SVM代价函数训练得到 θ 之后,可以代入下面的 SVM 预测函数进行预测:

大间距分类器

由上节,SVM的代价函数优化式为

并且,当 y=1 时,SVM 希望 θx≥1;而当 y=0 时,SVM 希望 θx≤−1。

容易推出SVM代价函数的优化目标为:

SVM 最终找出的决策边界会是下图中黑色直线所示的决策边界,而不是绿色或者紫色的决策边界。该决策边界保持了与正、负样本都足够大的距离,因此,SVM 是典型的大间距分类器(Large margin classifier)

这个时候,与Logistic回归不同的是,SVM的决策边界将张成一个与原空间同维的空间,相当于给出了一个补空间
补空间记录了既不属于正类也不属于负类的额外可能。(有点像无监督学习了)

数学原理

假定两个2维向量:$u=\left(\begin{matrix}u_1 \ u_2\end{matrix}\right),v=\left(\begin{matrix}v_1 \ v_2\end{matrix}\right)$。
令 p 为 v 投影到 u 的线段长(该值可正可负),如下图所示:

则 u、v 的内积为:$ u^Tv = p \cdot ||u|| = u_1v_1+u_2v_2 $。(||u|| 为 u 的范数,这里是 u 的长度。)

假定我们的 $\theta=\left(\begin{matrix}\theta_1 \ \theta_2\end{matrix}\right)$,且令 θ_0=0,以使得向量 θ 过原点,则优化约束可写为:

由向量内积公式可得:

其中,p(i) 为特征向量 x(i) 在 θ 上的投影:(x和θ被向量化)

当 y(i)=1 时,我们希望 $θ^Tx^{(i)}≥1$,亦即希望 p(i)⋅||θ||≥1,此时考虑两种情况:

  1. p(i)很小(一些X点接近绿色线,其投影狭窄),则需要 ||θ|| 很大,与 $min_θ\frac{1}{2}||θ||^2$ 矛盾。

  1. p(i)很大,如下图所示,即样本与决策边界的距离足够大,此时我们才能在既要 ||θ|| 足够小的情况下,又能有 $θ^Tx^{(i)}≥1$,保证预测精度够高。

这就解释了为什么 SVM 的模型会具有大间距分类器的性质了。
左右两边的边界都会相互尽量远离

核函数

在逻辑回归中,我们会通过多项式扩展来处理非线性分类问题:

则预测函数为:

多项式回归所带来的高阶项不一定作用明显
针对这一问题,SVM 不会引入高阶项来作为新的特征,而是会选择一些地标(landmark,并将样本 x 与标记点 $l^{(i)}$ 的相似程度作为新的训练特征 f_i:(Similarity Function

距离度量的方式就称之为核函数Kernel,最常见的核函数是高斯核函数(Gaussian Kernel)

1
2
3
4
5
6
7
function f = kernel(x1,x2)
Delta = 5;
f = exp(-(x1-x2)'*(x1-x2)/(2*Delta^2));
endfunction
x1 = [1; 2; 3; 4];
x2 = [1; 2; 3; 4];
kernel(x1,x2)

在高斯核中,注意到:

  • 如果样本与标记点足够接近,即 $x \approx l^{(i)}$,则:

  • 如果样本远离标记点,则:

这一关系可以被如下的热力图所反映:(正态分布

注:在使用高斯核函数前,需要做特征缩放(feature scaling),以使 SVM 同等程度地关注到不同的特征。

:假设选取了3个点作为地标,并且当$\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3\geq0$时预测为1。

给定$\theta_0=-0.5,\theta_1=1,\theta_2=1,\theta_3=0$。

预测点1:$\theta_0+\theta_1\times1+\theta_2\times0+\theta_3\times0\approx0.5>0$,预测为1

预测点2:$\theta_0+\theta_1\times0+\theta_2\times0+\theta_3\times0\approx-0.5<0$,预测为0

可以看出这三个新引入的$l^{(1)},l^{ {(2)} },l^{(3)}$的作用与新加入了特征无异。

地标选取

假定我们有如下的数据集:$(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),(x^{(3)},y^{(3)}) \cdots (x^{(m)},y^{(m)})$。

我们就将每个样本作为一个标记点:$l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},l^{(3)}=x^{(3)} \cdots l^{(m)}=x^{(m)}$。

则对于样本 $(x^{(i)}, y^{(i)})$,我们计算其与各个标记点的距离:

得到新的特征向量:$f∈R^{m+1}$

则具备核函数的 SVM 的优化式如下:(相当于用特征 f 替换了原特征 x

这时特征数m=样本数n。

在实际SVM使用时,$\sum\limits_{j=1}^{n}\theta_j^2=\theta^T\theta\rightarrow \theta^TM\theta$,其中M取决于Kernel,相当于一个缩放。可以让SVM运行更有效率。(能够适应更大的训练集,有效控制大矩阵乘法的消耗)

使用建议

SVM的更多补充:Here

使用流行库

作为当今最为流行的分类算法之一,SVM 已经拥有了不少优秀的实现库,如 libsvm 等,因此,我们不再需要自己手动实现 SVM(要知道,一个能用于生产环境的 SVM 模型并非课程中介绍的那么简单)。

在使用这些库时,我们通常需要声明 SVM 需要的两个关键部分:

  1. 参数 C
  2. 核函数(Kernel)

由于 C 可以看做与正规化参数 λ 作用相反,则对于 C 的调节:

  • 低偏差高方差,即遇到了过拟合时:减小 C 值。
  • 高偏差低方差,即遇到了欠拟合时:增大 C 值。

而对于核函数的选择有这么一些 tips:

  • 当特征维度 n 较高,而样本规模 m 较小时,不宜使用核函数(即linear kernel),否则容易引起过拟合。

  • 当特征维度 n 较低,而样本规模 m 足够大时,考虑使用高斯核函数。不过在使用高斯核函数前,需要进行特征缩放(feature scaling)。另外,当核函数的参数 δ 较大时,特征 fi 较为平缓,即各个样本的特征差异变小,此时会造成欠拟合(高偏差,低方差)

  • 当 δ 较小时,特征 fi 曲线变化剧烈,即各个样本的特征差异变大,此时会造成过拟合(低偏差,高方差)

不是所有的相似度评估手段都能被用作SVM核函数,他们需要满足 Mercer 理论

Ploynominal kernel, string kernel, chi-square kernel, histogram intersection kernel,……

多分类问题

通常,流行的SVM库已经内置了多分类相关的 api,如果其不支持多分类,则与逻辑回归一样,使用 One-vs-All 策略来进行多分类:

  1. 轮流选中某一类型 i ,将其视为正样本,即 “1” 分类,剩下样本都看做是负样本,即 “0” 分类。
  2. 训练 SVM 得到参数 $θ^{(1)},θ^{(2)},…,θ^{(K)}$ ,即总共获得了 K−1 个决策边界。

分类模型的选择

目前,我们学到的分类模型有:(1)逻辑回归;(2)神经网络;(3)SVM。怎么选择在这三者中做出选择呢?我们考虑特征维度 n样本规模 m

  • 若 $n \gg m$ ,例如 n=10000,而 m∈(10,1000):此时选用逻辑回归或者无核的 SVM。
  • 如果 $n \ll m \ll \infty$ ,如 n∈(1,1000),而 m∈(10,10000):此时选用核函数为高斯核函数的 SVM。
  • 若 $n \ll m$ ,如 n∈(1,1000),而 m>50000:此时,需要创建更多的特征(比如通过多项式扩展),再使用逻辑回归或者无核的 SVM。

神经网络对于上述情形都有不错的适应性,但是计算性能上较慢。

SVM面临的是凸函数优化,不必担心收敛到局部极值。


0%