第一章 绪论
:::info
本章：选择题 1 道，简答题 1 道。
:::
假设空间
特征属性的所有可能取值组合成的假设集合
比如，在西瓜数据集中，色泽有两种取值，根蒂有三种取值，敲声有三种取值，加上各自的通配项，以及极端情况的“好瓜的假设根本不成立”的空集，故假设空间的规模大小为 4 x 4 x 3 +1 = 49。
版本空间
搜索假设空间，找到和训练数据匹配的假设后，将正例相交，反例剔除，得到的最终 n 个假设构成的集合称为版本空间
归纳偏好
学习过程中对某种类型假设的偏好称为归纳偏好，存在多条曲线与有限样本训练一致。可以看作学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或价值观
第二章 模型评估与选择
:::info
本章：选择题 4 道，填空题 1 道，简答题 1 道。
:::
误差
实际预测输出与样本真是输出之间的差异
误差可以分为
方差与偏差
偏差：预测值与真实值之间的误差（学习算法本身的拟合能力）
方差：预测值之间的离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散。（数据扰动造成的影响）
泛化误差可以分解为：偏差、方差、噪声（学习任务本身的难度）之和
降低方法
- 降低偏差：更复杂的模型、Boosting、Staking、增加特征选择、多训练
- 降低方差：简单模型、正则化、Bagging、Stacking、增加训练数据、减少特征选择
- 降低噪声：改善数据
一般而言，偏差与方差存在冲突
- 训练不足时，学习器拟合能力不强，偏差主导。
- 随着训练程度加深，学习器拟合能力逐渐增强，方差逐渐主导。
- 训练充足后，学习器的拟合能力很强，方差主导。
过拟合与欠拟合
泛化性能越低，过拟合程度越高，欠拟合程度越低
过拟合：高方差、低偏差 训练集准确度接近 1，验证集差得远
欠拟合：高偏差、低方差 训练集、测试集准确率都低
评估方法
通常将包含 m 个样本的数据集 D 拆分为训练集 S 和测试集 T。
留出法
直接将数据集划分为两个互斥集合，一般若干次随即划分、重复实验取平均值
训练/测试集划分要尽可能保持数据分布的一致性
交叉验证法
将数据集分层采样划分为k个大小相似的互斥子集，每次用k-1个子集的并集作为训练集，余下的子集作为测试集，最终返回k个测试结果的均值，k最常用的取值是10
留一法
在交叉验证法的基础上，令k = m
自助法
以自助采样为基础，含 m 个样本的 D，对 D 进行有放回的抽取 m 个样本，形成 D'，D 的一部分会在 D'中重复出现，另一部分样本不出现
根据随机采样规律，存在约三分之一的数据不会出现在 D'中，所以使用这部分数据作为测试集，这样测试的结果称为包外估计。
优点：自助法在数据集较小、难以有效划分训练、测试集时很有用
能从初始数据集中产生多个不同的训练集，对集成学习有很大的好处
缺点：由于改变了数据集分布可能引入估计偏差，在数据量足够时，留出法和交叉验证法更常用
性能度量
用来衡量模型泛化能力的标准。要评估学习器f的性能，就要把学习器预测结果f(x)与真实标记 y进行比较.
回归任务常用性能度量：均方误差
$ E(f;D)=\frac{1}{m}\sum_{i=1}^m\left(f\left({x}_i\right)-y_i\right)^2 $
分类任务常用性能度量
错误率与精度
查准率、查全率与 F1
将样本根据其真实类别与学习器预测类别的组合划分为四个，下面的矩阵也就是混淆矩阵：
（TF：结果正确与否；PN：代表预测结果）
查准率 P（精确率）：检索出的信息中有多少是用户感兴趣的
$ P=\frac{TP}{TP+FP} $
查全率 R（召回率）：用户感兴趣的信息有多少被检测出来了
$ R=\frac{TP}{TP+FN} $
准确率：分类的准确度
$ 准确率=\frac{所有预测正确样本数}{样本总数} $
例题 1： 有100个正例，200 负例，正确预测了60个正例，180个负例，求 P、R？
根据题意，列混淆矩阵如下：
| 真实情况 | 预测结果 | |
|---|---|---|
| 正例 | 反例 | |
| 正例 | 60 | 40 |
| 反例 | 20 | 180 |
根据 P、R 计算公式可得： P = 0.75 R = 0.6
例题 2：
当阈值为0.8时，任何预测概率大于或等于0.8的实例将被分类为正类，低于0.8的将被分类为反类。
| 真实情况 | 预测结果 | |
|---|---|---|
| 正例 | 反例 | |
| 正例 | 1 | 1 |
| 反例 | 0 | 2 |
根据 P、R 计算公式可得： P = 100% R = 50%
PR 曲线
根据学习器的预测结果按正例可能性大小对样例进行排序，并按此顺序逐个把样本作为正例进行预测，则可得到 P-R 曲线。
利用 P-R 图比较学习器性能：
若曲线没有交叉，如 A > C , B > C
若曲线有交叉：
- BEP：平衡点，值越大学习器性能越好
- F1 度量：$ \frac{2\times TP}{\text{样例总数}+TP-TN} $
ROC 曲线
类似于 P-R 曲线，根据学习器的预测结果对样例排序，并逐个作为正例进行预测，以“假正例率”为横轴，“真正例率”为纵轴，ROC 全称为“受试者工作特征”。
（近似）ROC 曲线绘制：
给定 $ m^{+} $个正例和$ m^{-} $个反例，根据学习器预测结果对样例进行排序，然后把分类阈值设为最大，即把所有样例均预测为反例，此时真正例率和假正例率均为 0，在坐标$ (0,0) $处标记一个点.然后，将分类阈值依次设为每个样例的预测值，即依次将每个样例划分为正例. 设前一个标记点坐标为$ (x,y) $,当前若为真正例，则对应标记点的坐标为$ \left(x,y+\frac{1}{m^+}\right) $当前若为假正例，则对应标记点的坐标为$ \left(x,y+\frac{1}{m^-}\right) $,然后用线段连接相邻点即得.
重要数据点：
- (0, 0) 点：表示所有样本都被预测为反类。此时TPR和FPR均为0，意味着没有正类被正确识别。
- (1, 1) 点：表示所有样本都被预测为正类。此时TPR和FPR均为1，意味着所有的正类都被正确识别，但同时所有的反类也被错误地预测为正类。
- (0, 1) 点：这是理想情况，意味着TPR为1（所有正类都被正确识别），FPR为0（没有任何反类被错误识别）。这种情况很少见，但在理论上代表了完美的分类器。
- (0.5, 0.5) 点：这条线上的任何点都代表模型的表现等同于随机猜测。当ROC曲线位于这条线以下时，说明模型的性能比随机猜测还差。
$ \mathrm{真正例率TPR}=\frac{TP}{TP+FN},\mathrm{假正例率FPR}=\frac{FP}{TN+FP} $
第三章 线性模型
:::info
本章：选择题 5 道，填空题 1 道，简答题 1 道。
:::
线性回归
是一种通过特征的线性组合来进行预测的线性模型，其目的是找到一条直线或者一个平面或者更高维的超平面，使得预测值和真实值之间的误差最小化。
基本形式：
- 数学表达式：$ f(\boldsymbol{x})=w_1x_1+w_2x_2+\ldots+w_dx_d+b $
- 向量形式：$ f(\boldsymbol{x})=\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b $（比如：$ f_\text{好瓜 }(x)=0.2x_\text{色泽}+0.5x_\text{根条}+0.3x_\text{敲声} $）
为了确定 w 和 b 参数，我们可以试图让均化误差最小化，基于均化误差最小化来进行模型求解的方法称为“最小二乘法”。在线性回归中，最小二乘法就是试图找到一条直线，使所有样本到直线上的欧氏距离之和最小。求解 w 和 b 使得均方误差最小化的过程称为线性回归模型的最小二乘参数估计。下面的式子中，左侧是 w 和 b 的解：
$ \begin{aligned}(w^,b^)&=\arg\min_{(w,b)}\sum_{i=1}^m\left(f\left(x_i\right)-y_i\right)^2\&=\arg\min_{(w,b)}\sum_{i=1}^m(y_i-wx_i-b)^2\end{aligned} $
我们将下式对 w 和 b 分别求导：
$ \begin{aligned}&\frac{\partial E_{(w,b)}}{\partial w}=2\left(w\sum_{i=1}^mx_i^2-\sum_{i=1}^m\left(y_i-b\right)x_i\right),\&\frac{\partial E_{(w,b)}}{\partial b}=2\left(mb-\sum_{i=1}^m\left(y_i-wx_i\right)\right),\end{aligned} $
另左侧为 0，得出 w 和 b 的最优解：
$ \begin{aligned}w=\frac{\sum_{i=1}^{m}y_{i}(x_{i}-\bar{x})}{\sum_{i=1}^{m}x_{i}^{2}-\frac{1}{m}\left(\sum_{i=1}^{m}x_{i}\right)^{2}},\b=\frac{1}{m}\sum_{i=1}^m(y_i-wx_i),\end{aligned} $
多元线性回归
$ f(\hat{\boldsymbol{x}}_i)=\hat{\boldsymbol{x}}_i^\mathrm{T}\left(\mathbf{X}^\mathrm{T}\mathbf{X}\right)^{-1}\mathbf{X}^\mathrm{T}y $
广义线性模型
对数线性回归
$ \ln y=w^\mathrm{T}x+b $
实际是求输入空间到输出空间的非线性函数映射
更一般地，考虑单调可微函数$ g(\cdot) $，也叫联系函数，令：
$ y=g^{-1}(w^\mathrm{T}x+b) $
这就是广义线性模型，对数线性回归就是$ g(\cdot) = ln(\cdot) $时的特例。
例题：某国连续五年的个人消费支出和个人可支配收入的数据如下表所示，求个人消费支出关于个人可支配收入的线性回归方程
| y | 6.7 | 7.0 | 7.4 | 7.7 | 7.6 |
|---|---|---|---|---|---|
| x | 7.5 | 7.8 | 8.1 | 8.6 | 8.6 |
$ \begin{aligned}&\overline{x}=\frac{7.5+7.8+8.1+8.6+8.6}{5}=8.12,\overline{y}=\frac{6.7+7.0+7.4+7.7+7.6}{5}=7.28\end{aligned} $
$ \sum_{i=1}^5(x_i-\overline{x})(y_i-\overline{y})=0.802 $，$ \sum_{i=1}^5(x-\overline{x})^2 = 0.948 $
故$ {w}=\frac{\sum_{i=1}^5(x_i-\overline{x})(y_i-\overline{y})}{\sum_{i=1}^5\left(x_i-\overline{x}\right)^2}=\frac{0.802}{0.948}\approx0.85 $，$ b=\overline{y}-w\overline{x} = 0.378 $
所以，线性回归方程为：$ f(x)=0.85x+0.378 $。
对数几率回归
对于离散型的分类问题而言，我们可以使用单位阶跃函数将$ w^\mathrm{T}x+b $的值转换为 0、1 值，单位阶跃函数的形式如下：
$ y = \left{ \begin{matrix} 0, & z < 0; \ {0.5}, & z = 0; \ 1, & z > 0 \end{matrix}\right. $
从上图可以看出，单位阶跃函数并非连续，我们希望找到能在一定程度上近似单位阶跃函数的“替代函数”，对数几率函数正是一个常用的替代函数：
$ y= \frac {1}{1+e^ {-z}}
$
若将 y 视作正例的可能性，则 1-y 就是其反例的可能性，两者比值称为”几率“，取对数则称作”对数几率“。几率反应的是 x 为正例的相对可能性。
对数几率回归模型：
$ \ln\frac{y}{1-y}=\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b $
例题：
答案：极大拟然法
多分类学习
多分类学习的基础是拆解法，即将多分类任务拆解为若干个二分类任务求解。
对问题进行拆分，为拆出的每个二分类任务训练一个分类器。
对于每个分类器的预测结果进行集成以获得最终的多分类结果。
一对一（OVO）
将n个类别两两配对，从而产生n(n-1)/2个二分类任务，也即产生n(n-1)/2个二分类学习器，产生n(n-1)/2个分类结果，最终的多分类结果通过投票产生。其中单个二分类学习器就是对Ci和Cj进行分类的二分类学习器。
一对其余（OVR）
每次将一个类的样例作为正例，所有其他类的样例作为反例来训练n个分类器。
在测试时若仅有一个分类器的预测为正例，则把该分类器对应的预测类别标记作为最终的分类结果；若有多个分类器预测为正例，则通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果。
在类别很多时，OVO的训练时间开销通常比OVR更小。预测性能的表现则取决于具体的数据分布，多数情况下两者差别不大。
多对多（MVM）
每次将若干个类作为正类，若干个其他类作为反类。
MVM最常用的是纠错输出码(Error Correcting Output Codes,ECOC)。ECOC是将编码思想引入类别拆分，并尽可能在解码过程中具有容错性。
ECOC分为两步：
- 编码：将N个类别做M次划分，每次将一部分作为正例，其余作为反例，学习到M个分类器；
- 解码：新样本提交给M个分类器，得到M个结果，组成一个编码，将其和每个类别各自的编码进行比较，距离最小的类别作为最终结果
类别划分通过”编码矩阵“指定，常见的主要有二元码和三元码。前者将每个类别分别指定为正类和反类，后者在正、反类之外，还可指定 “停用类”
类别不平衡问题
解决不同类别的训练样例数目差别较大时带来的学习器性能很差的问题。（“小类”往往更重要）。
我们对新样本 x 进行分类时实际上是在将预测值 y 与一个阈值作比较，如果将阈值设定为 0.5 则说明分类器认为真实正反例可能性相同，即：
$ \text{若 }\frac{y}{1-y}>1\text{ 则 预测为正例} $
在训练集中正反例数量不一致时，令表示$ m^+ $正例数目，$ m^- $表示反例数目，则观测几率是$ m^+/m^- $，则：
$ \text{若 }\frac{y}{1-y}>\frac{m^+}{m^-}\text{ 则 预测为正例} $
一个基本的策略就是“再缩放”，也就是说在利用上面的公式时，实际上是在执行下面的式子，再缩放就可以实现：
$ \frac{y^{\prime}}{1-y^{\prime}}=\frac{y}{1-y}\times\frac{m^-}{m^+} $
常见的类别不平衡学习方法
过采样 SMOTE
增加一些样例，对训练集内的正例进行插值产生的额外正例
欠采样 EasyEnsemble
去除一些反例
阈值移动
第四章 决策树
:::color4
本章：选择题 1 道，填空题 1 道，计算题 1 道。
:::
决策树基本概念
- 非叶节点：一个属性测试
- 叶节点：决策结果
- 从根节点到每个叶节点的路径：一个判定测试序列
基本流程遵循的策略：分而治之
决策树学习的目的：产生一颗泛化能力强的决策树
决策树生成：
- 数据准备：通过数据清洗和数据处理，将数据整理为可以直接应用决策树的向量
- 寻找最佳特征：遍历每个特征的每一种划分方式，找到最好的划分特征
- 生成分支：划分成两个或多个节点
- 生成决策树：对分裂后的节点迭代执行，直到每个节点只有一个类别
- 决策分类：根据训练决策树模型，将预测数据进行分类
（了解）决策树生成算法
若遇到连续属性可以使用离散化技术，将连续属性转化为离散属性。
划分选择
我们希望随着划分的不断进行，决策树的分支结点所包含的样本尽可能属于同一类别。
信息熵
信息熵是度量样本集合纯度最常用的一种指标。在下面的公式中，$ p_{k} $代表在总共 y 类样本中，第 k 类所占比例，D 为样本集合：
$ \operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log {2} p{k} $
信息熵值越小，说明该集合纯度越高。
信息增益
对于某个拥有 v 个可能取值的离散属性 a，产生 v 个分支，考虑到各个分支所含的样本数量不同，给分支节点赋予权重$ |D^v|/|D| $
$ \mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}\mathrm{Ent}(D^v) $
- 样本数量越多的分支节点影响越大
- 选择信息增益最大的属性进行划分
- ID3 决策树学习算法就是以信息增益最大的属性为准则来选择划分属性
- 信息增益准则对可取值数目较多的属性有所偏好
例题 1：根据下面的数据集，计算各个属性的信息增益
根节点的信息熵为：$ \operatorname{Ent}(D)=-\sum_{k=1}^2p_k\log_2p_k=-\left(\frac{8}{17}\log_2\frac{8}{17}+\frac{9}{17}\log_2\frac{9}{17}\right)=0.998 $
对于色泽属性，分别计算用色泽划分之后的三个分支节点的信息熵：
$ \mathrm{Ent}(D_1)=-\left(\frac{3}{6}\log_2\frac{3}{6}+\frac{3}{6}\log_2\frac{3}{6}\right)=1.000\
\mathrm{Ent}(D_2)=-\left(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6}\right)=0.918\
\mathrm{Ent}(D_3)=-\left(\frac{1}{5}\log_2\frac{1}{5}+\frac{4}{5}\log_2\frac{4}{5}\right)=0.722 $
所以，根据信息增益的公式，可得属性色泽的信息增益为：
$ \begin{aligned}\mathrm{Gain}(D,\text{色泽})&=\mathrm{Ent}(D)-\sum_{v=1}^3\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)\&=0.998-\left(\frac{6}{17}\times1.000+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722\right)\&=0.109\end{aligned} $
对于其他属性，可得：
$ \mathrm{Gain}(D,\text{根蒂})=0.143;\quad\mathrm{Gain}(D,\text{敲声})=0.141;
\mathrm{Gain}(D,\text{纹理})=0.381;\quad\mathrm{Gain}(D,\text{脐部})=0.289;
\mathrm{Gain}(D,\text{触感})=0.006.
$
纹理属性的信息增益最大，我们选择它来作为划分属性：
例题 2：
根节点的信息熵为：$ \operatorname{Ent}(D)=-\sum_{k=1}^2p_k\log_2p_k=-\left(\frac{6}{10}\log_2\frac{6}{10}+\frac{4}{10}\log_2\frac{4}{10}\right)=0.971 $
对于敲声属性，分别计算用敲声划分之后的三个分支节点的信息熵：
$ \mathrm{Ent}(D_1)=-\left(\frac{3}{4}\log_2\frac{3}{4}+\frac{1}{4}\log_2\frac{1}{4}\right)=2.415\
\mathrm{Ent}(D_2)=-\left(\frac{0}{1}\log_2\frac{0}{1}+\frac{1}{1}\log_2\frac{1}{1}\right)=0.000\
\mathrm{Ent}(D_3)=-\left(\frac{2}{3}\log_2\frac{2}{3}+\frac{1}{3}\log_2\frac{1}{3}\right)=0.918 $
根据信息增益的公式，可得属性敲声的信息增益为：
$ \begin{aligned}\mathrm{Gain}(D,\text{敲声})&=\mathrm{Ent}(D)-\sum_{v=1}^3\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)\&=1-\left(\frac{4}{10}\times2.415+\frac{1}{10}\times0.000+\frac{3}{10}\times0.918\right)\&=0.696\end{aligned} $
增益率
增益率对可取值数目较少的属性有所偏好
C4.5 决策树算法使用信息增益率最大的作为划分的最优属性（启发式）
信息增益率定义为：
$ \mathrm{Gain_ratio}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)} $
其中：
$ \mathrm{IV}(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|} $
基尼指数
CART 决策树使用基尼指数最小的属性来选择划分属性。
$ \begin{aligned}\operatorname{Gini}(D)=&1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2.\end{aligned} $
其中，属性 a 的基尼指数为：
$ \mathrm{Gini_index}(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}\mathrm{Gini}(D^v) $
基尼指数越小，样本集合 D 纯度越高
反映了从数据集中随机抽取两个样本，其类别标记不一致的概率
例题：
决策树剪枝
剪枝是决策树对付过拟合的手段。判断决策树泛化性能：留出法。
预剪枝
基于此，生成的未经剪枝的决策树为：
基于信息增益准则，我们会选取属性“脐部”来对测试集进行划分，并产生三个分支。然而，是否应该进行这个划分呢？预剪枝要对划分前后的泛化性能进行估计。
若不做划分，所有测试样例集中在根节点，验证集精度为 3/7。在用属性“脐部”划分之后，验证集精度为 5/7.对于 2-4 三个结点执行上面的方法，可以得出只有 ④ 可以执行划分。
后剪枝
首先考虑结点⑥，若将其替换为叶结点，根据落在其上的训练样例{7，15}，将其标记为“好瓜”，测得验证集精度提高至 57.1%，于是决定剪枝：
然后考虑结点⑤，若将其替换为叶结点，根据落在其上的训练样例{6，7，15}，将其标记为“好瓜”，测得验证集精度仍为 57.1%，可以不剪枝。
对结点②，若将其替换为叶结点，根据落在其上的训练样例{1，2，3，14}，将其标记为“好瓜”，测得验证集精度提升至 71.4%，决定剪枝：
对结点③和①，先后替换为叶结点，均未测得验证集精度提升，于是不剪枝。
最终得到经过后剪枝的决策树：
各自优缺点
| 优点 | 缺点 | |
|---|---|---|
| 预剪枝 | 降低过拟合风险，显著减少训练时间和测试时间开销 | 欠拟合风险 |
| 后剪枝 | 降低欠拟合风险，泛化性能往往优于预剪枝决策树 | 训练时间开销大 |
第六章 支持向量机
:::info
本章：选择题 2 道，简答题 1 道。
:::
硬间隔支持向量机
SVM 的核心思想是基于训练集 D 在样本空间中寻找一个划分超平面，使得此超平面能将不同类别的样本分开。
为了找到“最好的”超平面，也就是对训练集的局限性或者噪声等因素容忍性（泛化能力）最好的超平面，Vapnik 提出了一种方法：对每个可能的超平面，将它进行平移，直到它与空间中的样本向量相交（我们称这两个向量为支持向量）。之后我们计算支持向量到该划分超平面的距离$ d $，分类效果最好的划分超平面应该使$ d $最大。
对于此距离，下面我们讲解一下计算的方法。
假设存在平面$ \psi:\mathrm{w}^T\mathrm{x}+b=0 $，其中，w 为该平面的法向量，b 为位移项（决定了超平面与原点之间的距离），为了计算距离，对于欧氏空间中的任意向量 α ，若将该向量与某个方向的单位方向向量进行点乘（内积），就能得到该向量在指定方向上的长度。例如向量$ \overrightarrow{\alpha}=(3,4,5) $在$ \overrightarrow{n}=(1,1,1) $方向上的长度为：
$ \left|\overrightarrow{\alpha}\cdot\overrightarrow{n_0}\right|=\left|\overrightarrow{\alpha}\cdot\frac{\overrightarrow{n}}{\left|\overrightarrow{n}\right|}\right|=\left|(3,4,5)\cdotp\frac{(1,1,1)}{|(1,1,1)|}\right|=\frac{|3\times1+4\times1+5\times1|}{\sqrt{3}}=\frac{12}{\sqrt{3}}=4\sqrt{3} $
因此，在平面中任选一点，则点 x 到指定平面 ψ 的距离为：
$ dist(\mathrm{x},\psi)=\left|\overrightarrow{\alpha}\cdot w_0\right|=\left|\left(\mathrm{x}-\mathrm{x}^{\prime}\right)\cdot\frac{w}{|w|}\right|=\left|\frac{w^T}{|w|}\left(\mathrm{x}-\mathrm{x}^{\prime}\right)\right|=\frac{|w^T\mathrm{x}-w^T\mathrm{x}^{\prime}}{|w|}=\frac{1}{|w|}\left|\left(w^T\mathrm{x}+b\right)\right| $
上式存在绝对值，因为对于任意一个样本集而言，其预测结果只可能属于$ {0,1} $的范围内，所以，式可以转化为：
$ d=y_i\times\left(\overrightarrow{\alpha}\cdot w_0\right)=y_i\times\left(\left(\mathrm{x}_i-\mathrm{x}^{^{\prime}}\right)\cdot\frac{w}{|w|}\right)=y_i\times\left(\frac{w^T}{|w|}\left(\mathrm{x}_i-\mathrm{x}^{^{\prime}}\right)\right)=y_i\times\left(\frac{w^T\mathrm{x}_i-w^T\mathrm{x}^{^{\prime}}}{|w|}\right)=\frac{y_i}{|w|}\left(w^T\mathrm{x}_i+b\right) $
支持向量机基本型
为了找到最优的超平面，我们需要将支持向量到超平面的距离最大化，也就是将下面的式子的值最大化：
$ max_{w,b}\left{min_{(\mathrm{x}_i,y_i)\in D}\frac{y_i}{|w|}\left(w^T\mathrm{x}_i+b\right)\right} $
我们假设超平面能将训练样本正确分类，那么对于任意一个样本，都符合以下规律：
$ \left.\left{\begin{array}{ll}\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b\geqslant+1,&y_i=+1;\\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b\leqslant-1,&y_i=-1.\end{array}\right.\right. $
如上面的图片所示，距离超平面最近的这几个训练样本点使得上式成立，它们被称为支持向量，所以两个异类的支持向量的到超平面的距离之和为：$ \gamma=\frac{2}{||\boldsymbol{w}||} $，也被称为间隔。
所以，最大化间隔问题其实就是一个凸二次规划问题，我们将$ ||\boldsymbol{w}|| $最小化，也就是最大化$ |w|^2 $，所以，支持向量机的基本型如下：
$ \begin{aligned}&min_{w,b}\frac{1}{2}w^{2}\&s.t.\quad y_i\left(w^T\mathrm{x}_i+b\right)\geq1\quad i=1,2,\ldots,n\end{aligned} $（s.t.指受限于）
拉格朗日乘子法与 KTT 条件
对上面的基本型使用拉格朗日乘子法即可得到相应的对偶问题，拉格朗日乘数法是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法，简单来说，接下来引入的系数就是为了强制使得不等式的所有条件被满足。
对上式采用拉格朗日乘子法，可得：
$ L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}|\boldsymbol{w}|^2+\sum_{i=1}^m\alpha_i\left(1-y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b)\right) $
对两个变量求偏导并回代结果可得对偶问题（得到的最小值是原来目标函数的下界）为：
$ \max_{\boldsymbol{\alpha}}\quad\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}i^\mathrm{T}\boldsymbol{x}_j\ \begin{aligned}\mathrm{s.t.}&\sum{i=1}^m\alpha_iy_i=0,\&\alpha_i\geqslant0,\quad i=1,2,\ldots,m.\end{aligned} $
可得最终模型：
$ \begin{aligned}f(\boldsymbol{x})&=\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b\&=\sum_{i=1}^m\alpha_iy_i\boldsymbol{x}_i^\mathrm{T}\boldsymbol{x}+b.\end{aligned} $
KTT 约束条件为：
$ \left.\left{\begin{array}{l}\alpha_i\geqslant0;拉格朗日基本要求\
\y_if(\boldsymbol{x}_i)-1\geqslant0原限制;\\\alpha_i\left(y_if(\boldsymbol{x}_i)-1\right)=0 \end{array}\right.\right. $
对于满足以上限制的解，具备以下特性：
$ \alpha_i=0\text{ 或 }y_if(\boldsymbol{x}_i)=1 $
若乘子等于 0，则说明该样本不会在最后预测的函数内出现，若$ y_if(\boldsymbol{x}_i)=1 $则说明当前点恰好在支持向量的边界上。
解的稀疏性：训练完成后，最终模型仅与支持向量相关。
回到上面的对偶问题，注意到下面的限制条件中只涉及到两个变量，若每次只考虑这两个变量，其余均作常数处理，SMO 方法就是这样的一个思路。
第一步：选取一对需更新的变量$ α_i $和$ α_j $（尽量选择违背 KTT 条件最多的）
第二步：固定$ α_i $和$ α_j $以外的参数，求解对偶问题更新$ α_i $和$ α_j $
按此操作，对偶问题能得到闭式解。
核函数
对于训练样本不可分时可以使用核函数，将样本映射到一个更高维的特征空间。
绕过显式考虑特征映射、以及计算高维内积的困难。
Mercer 定理：若一个对称函数所对应的核矩阵半正定，则它能作为核函数来使用。
半正定指的就是如果核函数对应的核矩阵恰好表达了某一个空间，即可以作为某一种空间上的距离函数。
常用的核函数：（记住名称）
对于高斯核函数而言，超参数越大，越容易过拟合。
软间隔支持向量机
在现实情况中，即使我们找到了一个看似合理的超平面，它可能也不能完全将样本分开，欲缓解该问题可以引入软间隔的概念。
在允许某些样本划分错误的前提下，软间隔支持向量机的优化目标是：
$ \min_{\boldsymbol{w},b}\frac{1}{2}|\boldsymbol{w}|^2+C\sum_{i=1}^m\ell_{0/1}(y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b)-1) $
其中，$ c $称为惩罚参数，C值大的时候对误分类的惩罚增大，C值小的时候对误分类的惩罚减小。$ \ell_{0/1} $是“0/1 损失函数”。当 C 无限大时，退化为硬间隔支持向量机。
然而，$ \ell_{0/1} $的数学性质不佳，我们选择其他损失替代函数来替代：
$ \begin{aligned}&\text{hinge 损失: }\ell_{hinge}(z)=\max(0,1-z);\&\text{指数损失(exponential loss): }\ell_{exp}(z)=\exp(-z);\&\text{对率损失(logistic loss): }\ell_{log}(z)=\log(1+\exp(-z))\end{aligned} $
第七章 贝叶斯分类器
:::color4
本章：选择题 1 道，填空题 1 道，计算题 1 道。
:::
贝叶斯决策论
概率框架下实施决策的基本理论
给定 N 个类别，令$ \lambda_{ij} $代表将第 j 类样本误分为第 i 类所产生的损失，则基于后验概率将样本分到第 i 类的条件风险为：
$ R(c_i\mid\boldsymbol{x})=\sum_{j=1}^N\lambda_{ij}P(c_j\mid\boldsymbol{x}) $
为了找到风险最小的一个，我们提出了贝叶斯判定准则：
$ h^*(\boldsymbol{x})=\arg\min_{c\in\mathcal{Y}}R(c\mid\boldsymbol{x}) $
$ h^* $通常被称为贝叶斯最优分类器，其总体风险称为贝叶斯风险。
反映了学习性能的理论上限。
判别式与生成式
$ P(c_j\mid\boldsymbol{x}) $往往难以获得，从这个角度来看，机器学习所要实现的是基于有限的训练样本尽可能准确地估计出后验概率。
两种基本策略：
接下来，我们来探讨一下生成式模型。
$ P(c_j\mid\boldsymbol{x}) $利用贝叶斯定理可以写成：
$ P(c\mid\boldsymbol{x})=\frac{P(c)P(\boldsymbol{x}\mid c)}{P(\boldsymbol{x})} $
极大拟然估计
估计类条件概率的一种常用策略是先假定其具有某种有特定的概率分布形式，再基于训练样本对概率分布的参数进行估计。令$ D_{c} $表示训练集 D 中第 c 类样本组成的集合，假设这些样本是独立同分布的，则参数$ \boldsymbol{\theta}{c} $对于数据集$ D{c} $的拟然是：
$ P(D_c\mid\boldsymbol{\theta}c)=\prod{\boldsymbol{x}\in D_c}P(\boldsymbol{x}\mid\boldsymbol{\theta}_c) $
Comments NOTHING