百面机器学习总结笔记

第三章 经典算法

第1节 支持向量机

场景描述
支持向量机( Support Vector Machie时 ， SVM )是众多监督学习万法中十分出色的 一种，几乎所有讲述经典机器学习方法的教材都会介绍 。 关于 SVM， 流传着一个关于天使与魔鬼的故事 。
传说魔鬼和天使玩了一个游戏 ，魔鬼在桌上放了两种颜色的球，如图 3.1 所示 。 魔鬼让天使用一根木棍将官们分开 。这对天使来说，似乎太容易了 。 天使不假思索地一摆，便完成了任务， 如图3.2所示。魔鬼又加入了更多的球。随着球的增多，似乎所有的球不能再
被原来的木棍正确分开，如图3.3所示

SVM 实际上是在为天使找到木棒的最佳放置位置 ，使得两边的球都离分隔他们的木棒足够远，如图3.4 所示 。 依照 SVM 为天使选择的木棒位置，魔鬼即使按照刚才的方式继续加入新球，木棒也能很好地将两类不同的球分开，如图3.5 所示。

看到天使已经很好地解决了用木棒线性分球的问题，魔鬼又给了天使一个新的挑战，如图 3.6 所示 。按照这种球的摆法，世界上貌似没高一根木棒可以将它们完美分开 。但天使毕竟有法力，他一拍桌子 ，便让这些球飞到了空中 ，然后凭借念力抓起一张纸片，插在了两类球的中间，如图 3.7 所示 。从魔鬼的角度看这些球，则像是被一条曲线完美的切开了，如图3.8所示：

后来’ “无聊”的科学家们把这些球称为“数据’，把木棍称为“分类面" '找到最 大间隔的木棒位置的过程称为 “优化”，拍桌子让球飞向空中的念力叫“核映射”在空中分隔球的纸片称为“分类超平面’’ 。这便是 SVM 的童话故事。
在现实世界的机器学习领域，SVM涵盖了各个方面的知识，也是面试题目中常见的基础模型 。本节的第 l 个问题考察 SVM 模型推导的基础知识;第2题 到 第4题则会侧重对核函数( Kernel Function )的理解。

知识点
SVM 模型推导，核函数 ， SMO (Sequential Minimal Optimization )算法

问题
在线性空间上线性可分的两类点，分别向 SVM 分类的超平面上做投影，这些点在超平面上的投影仍然是线性可分的吗?

分析与解答
首先明确下题目中的概念，线性可分的两类点，即通过一个超平面可以将两类点完全分开，如图 3.9 所示。假设绿色的超平面(对于二维空间来说，分类超平面退化为一维直线):为 SVM 算法计算得出的分类面，那么两类点就被完全分开 。我们想探讨的是:将这两类点向绿色平面上做投影，在分类直线上得到的黄棕两类投影点是否仍然线性可分，如图 3.10所示。

显然一眼望去，这些点在分类超平面(绿色直线)上相互间隔，并不是线性可分的。考虑一个更简单的反例，设想、三维空间中只有两个样本点，每个点各属于一类的分类任务，此时 SVM 的分类超平面(直线) 就是两个样本点连线的中垂线，两个点在分类面(直线)上的投影会落到这条直线上的同一个点，自然不是线性可分的 。
但实际上 ，对于任意线性可分的两组点， 它们在 SVM 分类的超平面上的投影都是线性不可分的 。 这昕上去高些不可思议，我们不妨从二维情况进行讨论 ，再推广到高维空间中 。

由于 SVM 的分类超平面仅由支持向量决定(之后会证明这结论)，我们可以考虑一个只含支持向量 SVM 模型场景 。 使用反证法来证明 。 假设存在一个 SVM 分类超平面使所有支持向 量在该超平面上的投影依然线性可分，如图 3.11 所示。 根据简单的初等几何知识不难发现，图中 AB 两点连线的中垂线所组成的超平面(绿色 虚线);是中日较于绿色实结起平面更优的解， 这与之前假设绿色实结起平面为最优的解相矛盾。考虑最优解对应的绿色虚线两组点经过投影后，并不是线性可分的 。我们的证明目前还奇不严谨之处，即 我们假设了仅有支持向量的情况，会不会在超平面的变换过程中支持向量发生了改变，原先的非支持向 量和支持向量发生了转化呢?下面我们]证明 SVM 的分类结果仅依赖于支持向量。 考虑 SVM 推导中的 KKT 条件要求

实际上，该问题也可以通过凸优化理论中的超平面分离定理 ( Separating Hyprplane Theorem, SHT )更加轻巧地解决 。该定理理描述的是，对于不相交的两个口集，存在一个超平面，将两个口集分离。对于二维的情况，两个凸集间距离最短两点连线的中垂线就是一个
将官们分离的超平面。
借助这个定理，我们可以先对统性可分的这两组点求各 自的凸包 。不难发现， SVM 求得的超平面就是两个凸包上距离最短的两点连线的中垂线 ， 也就是 SHT 定理二维情况中所阐释的分类超平面。根据凸包的性质容易知道，凸包上的点要么是样本点，要么处于两个样本点的连线上 。因此，两个凸包间距离最短的两个点可以分为三种情况，两边的点均为样本点 ， 如图3.12(a )所示，两边的点均在样本点的连线上，如图 3.12(b )所示； 一边的点为样本点，另一边的点在样本点的连线上， 如圄 3.12 (c )所示 。 从几何上分析即可知道，无论哪种情况两类点的投影均是统性不可分的 。

问题
是否存在一组参数使得SVM训练误差为零？

分析与解答

问题
训练误差为零的SVM分类器一定存在吗？

分析与解答

问题
加入松弛变量的SVM的训练 误差可以为零吗?

在实际应用中，如果使用 SMO 算法来训练一个加入松弛变量的线性 SVM 模型 ，并且惩罚因子 C 为任一未知常数 ，我们是否能得到训练误差为 0 的模型呢?
分析与解答

第2节 逻辑回归

场景描述
逻辑回归( Logistic Regression )可以说是机器学习领域最基础也是最常用的模型， 逻辑回归的原理推导以及扩展应用几乎是算法工程师的必备技能 。 医生病理诊断、银行个 人信用评估、邮箱分类 I主极邮件等，无不体现逻辑回归精巧而广泛的应用 。 本小节将从模 型与原理出发，涵盖扩展与应用，一探逻辑回归的真谛。

知识点
逻晤回归，线性回归，多标签分类， Softmax

问题：逻辑回归相比于线性回归，有何异同？

分析与解答

问题：当使用逻辑回归处理多标签的分类问题时，有哪些常见做法，分别应用于哪些场景，它们之间有怎样的关系？

分析与解答
使用哪一种办法来处理多分类的问题取决于具体问题的定义 。

如果一个样本只对应于一个标签，我们可以假设每个样本属于不同标签 的概率服从于几何分布，使用多项式逻辑回归( Softmax Regression ) 来进行分类

当存在样本可能居于多个标签的情况时，我们可以训练 k个二分类的逻辑回归分类器 。第 i 个分类器用以区分每个样本是否可以归为第 i 类，训练该分类器时，需要把标签重新整理为“第 i 类标签 ” 与”非第 i 类标签“两类遇过这样的刃、j去 3 我们就解决了每个样本可能拥有多个标签的情况 。

第3节 决策树

场景描述：

决策树是一种自上而下 ，对样本数据进行树开三分类的过程，由结点和有向边组成 。结点分为内部结点和叶结点，其中每个内部结点表示一个特征或属性，叶结点表示类别 。从顶部根结点开始，所有样本聚在一起 。经过根结点的划分 ，样本被分到不同的子结点中 。 再根据子结点的特征进一步划分，直至所有样本都被归到某一个类别(即叶结点)中 。

一般而言 ，决策树的生成包含了特征选择、树的构造、树的剪枝 三个过程 ，本节将在第一个问题中对几种常用的决策树进行对比，在第二个问题中探讨决策树不同剪枝方法之间的区别与联系 。

知识点：

信息论，树形数据结构，优化理论

问题：决策树有哪些常用的启发函数?

分析与解答
首先，我们回顾一下几种决策树构造时使用的特征选择准则
1、ID3



2、C4.5


3、CART

4、三种特征选择准则的对比
通过对比三种决策树的构造准则，以及在同一例子上的不同表现 ，
我们不难总结三者之间的差异 。

问题：如何对决策树进行剪枝？

分析与解答
预剪枝

后剪枝

此时共 5 个内部结点可供考虑，其中

最后

以上就是要减肥白昼为你收集整理的百面机器学习总结笔记（第三章 经典算法）百面机器学习总结笔记的全部内容，希望文章能够帮你解决百面机器学习总结笔记（第三章 经典算法）百面机器学习总结笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。