机器学习全局调查

这一系列源自西瓜书，目的是对机器学习全局有大概的把握，重点不在于数学推导的细节，而在于了解各个经典模型的核心思想与insight，形成一张自己的地图，企望日后按图索骥。

引言

机器学习是什么？从数据中学习，基于数据产生模型去预测未知数据

基本术语/假设

独立同分布：我们认为样本空间全体样本服从一个未知分布，我们获得的每一个样本都满足独立同分布，细细一想这一结果未必总是成立，样本之间高度共线性的情况

假设空间

归纳偏好

归纳偏好是算法本身的特征，当预测时遇到无法断言的情况，模型本身的偏好起到了重要结果。不同算法的偏好是好是坏很难界定，一个经典的原则是奥卡姆剃刀原则：如无必要，勿增实体。 - 在机器学习中理解，有点拟合和过拟合的滋味，比如用多项式函数拟合某一个线性函数，数据量有限的情况下，多项式函数次数越高越容易过拟合 - 在自然科学中理解，这是一种朴素的科研品味，费曼说过，你能一眼认出真理，因为她既美又简单。

NFL定理告诉我们，脱离具体问题，空泛的谈论什么算法更好毫无意义。算法的优劣总是针对于具体的问题而言

发展历程

上世纪五十年代到七十年代，人工智能处于推理期，著名的逻辑理论家程序证明了数学原理中的38条定理

随后，人们认识到仅仅有逻辑推理能力远远实现不了人工智能，要使机器具有智能，就要让他拥有知识，这一时期大量专家系统问世

再后来，人们意识到把知识总结出来教给计算机没有前途，能否让机器自己学习知识？机器学习在这一时期红极一时，持续至今

机器学习包括哪些思想？基于神经网络的连接主义，基于逻辑表示的符号主义，以决策论为基础的机器学习/强化学习，统计机器学习（svm）等等

对序言的摘要

三十年河东，三十年河西，如今神经网络

这一轮的大语言模型（Large Language Model, LLM）浪潮，即依托大量的数据和算法资源获得的进步。但是”连接主义”方法最大的局限性是其”试错性”，简单的说，其学习过程涉及大量参数，而参数的设置缺乏理论指导（可解释性差），主要依靠手动调参，夸张一点来说，参数调节上失之千里，学习结果可能谬以千里。

相比之下”符号主义”的逻辑性更强，通过逻辑表达式描述领域知识。然而，成也萧何，败也萧何，然而，由于表示能力太强，直接导致面临的假设空间太大、复杂度极高，因此，问题规模稍大就难以进行有效学习。

对于机器学习的发展前途，中科院数学与系统科学研究院陆汝铃老师在为南京大学周志华老师的《机器学习》一书作序时提出了六大问题。第一个问题就是”符号主义”与”连接主义”之争。在此我摘录总结陆老师的观点：

Q1：从二十世纪九十年代开始，“连接主义”迅速压倒并取代了”符号主义”的地位。人们可能会问，符号学习是否被彻底忽略了？他还能成为机器学习的研究对象吗？它是否能继续在统计学习的阴影里苟延残喘？

A：这个问题有三种可能：

1. 退出历史舞台——目前还没有人抱有这种想法。
2. 单纯的统计学习到了尽头之后，再想往前走就要和符号主义学习结合起来——王珏教授认为，现在机器学习已经到了一个转折点，统计学习要想进入一个更高级的形式，就应该和认知相结合，这是一种”螺旋式上升，进入更高级的形式”，否则就会停留于现状而止步不前。
3. 三十年河东三十年河西，符号学习还有翻身之日——Chandrasekaran 教授认为最近几年，人工智能在很大程度上集中于统计学和大数据，并取得一些成果。但总有一天会转向基于更基本的认知科学研究。有必要把统计技术和认知结构，连接主义和符合主义结合起来。 两位老师的观点基本一致，但不仅限于机器学习，而是涉及整个人工智能领域，知识王珏老师强调知识，而Chandrasekaran 教授强调更基本的”认知”。

Q2：为什么统计机器学习不会一帆风顺？

A：统计机器学习的算法都是基于样本数据独立同分布的假设，但自然界现象千变万化，哪里有那么多独立同分布？那么“独立同分布”条件对于机器学习来说是必须的吗？独立同分布的不存在一定是不可逾越的障碍吗？无独立同分布条件下的机器学习也许只是一个难题，而不是不可解决的。

Q4：机器学习研究出现以来，我们看到的主要是从符号方法到统计方法的演变，用到的数学主要是概率统计。但是今天数学之大，就像大海，难道只有统计方法适合于在机器学习方面的应用？

A：目前流形学习已经“有点意思了”，但数学理论的介入程度远远不够，有待更多数学家参与，开辟新的模式、理论和方法。

2.1经验误差和过拟合

误差error：实际预测输出与真是输出之间的差异，在训练集上的误差成为训练误差training error或经验误差empirical error，在新样本上的误差成为泛化误差generalization error， 训练的最终目标是获得较小的泛化误差
机器学习算法的难点在于克服过拟合

2.2评估方法

2.2.1留出法

直接将数据集D划分为两个互斥的集合，其中一个集合作为训练集S,另一个作为测试集T。

从釆样(sampling)的角度来看数据集的划分过程，一般进行保留类别比例的釆样方式，也就是“分层采样” (stratified sampling)。

单次使用留出法得到的估计结果往往不够稳定可靠，在使用留出法时，一般要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果。

测试集较小时，评估结果的方差较大；训练集小时，评估结果的偏差较大，常见做法 2/3 ~ 4/5 的样本作为训练集，剩余样本用于测试。事实上不咋用这个方法。

2.2.2交叉验证法

• 思路：将数据集划分为k个大小相似的互斥子集，每次用k-1个子集的并集作为训练集，余下的那个子集作为测试集，如此进行k次测试，最终用上全部的数据。

• p 次 k 折交叉验证：:与留出法相似，将数据集D划分为k个子集同样存在多种划分方式。为减小因样本划分不同而引入的差别，k折交叉验证通常要随机使用不同的划分重复p次，最终的评估结果是这p次k折交叉验证结果的均值，例如常见的有“10次10折交叉验证

• 特例:当k和数据集数量一致时，称之为留一法（Leave One Out）简称：LOO

2.2.3自助法

留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际评估的模型所使用的训练集在大小上比D小，而留一法的计算复杂度又太高。若希望评估用训练集全集D训练出的模型，可以使用自助法(bootstrapping)，其在数据集较小、难以有效划分训练/测试集时很有用。

给定包含 m 个样本的数据集D ,我们对它进行采样产生数据集D’：每次随机从D中挑选一个样本,将其拷贝放入D’,然后再将该样本放回初始数据集D中,使得该样本在下次釆样时仍有可能被釆到；这个过程重复执行m次后，我们就得到了包含m 个样本的数据集D,这就是自助釆样的结果。很有可能的，D中有一部分样本会在D中多次出现，而另一部分样本不出现。从数学期望的角度可以做一个简单的估计，样本在m次采样中始终不被釆到的概率是$(1 -\frac1m)^m$,取m趋于正无穷极限的得到 $$\lim_{m\mapsto\infty}\left(1-\frac1m\right)^m\mapsto\frac1e\approx0.368$$

通过自助釆样，从数学期望的角度来看，初始数据集D中约有36.8%的样本未出现在釆样数据集D中。于是可将D用作训练集,D’用作测试集。这样，实际评估的模型与期望评估的模型都使用m个训练样本，而我们仍有数据总量约1/3的、没在训练集中出现的样本用于测试。

2.2.4调参与最终模型

• 小数据集，数据不好划分的时候，用自助法

• 大部分时候，用k折

• 如何调参？:网格搜索参数

• 以上只是为了对比模型好坏，选出来最好模型后，最后提交给客户的模型参数应该是用训练集全集D训练出来的

2.3性能度量

对学习器的泛化性能进行评估，不仅需要有效可行的实验估计方法，还需要有衡量模型泛化能力的评价标准，这就是性能度量（performance measure）

回归问题常用均方误差做，下面着重讲一下分类问题的效果评估

2.3.2 查准率/查全率/F1

分类问题目的是什么？从一堆瓜中找出来所有的好瓜，你用自己的模型找出来了一堆瓜，不过其中有好有坏
你找出来的瓜有多少是好瓜？由此定义了查准率 P（precision）
$$P=\frac{TP}{TP+FP}$$ 所有好瓜里面你挑出来了多少？由此定义了查全率 R（recall）& 召回率 $$R=\frac{TP}{TP+FN}$$ 查准率和查全率是一对矛盾的度量. 一般来说，查准率高时，查全率往往偏低；而查全率高时，查准率往往偏低.例如，若希望将好瓜尽可能多地选出来， 则可通过增加选瓜的数量来实现，如果将所有西瓜都选上，那么所有的好瓜也必然都被选上了，但这样查准率就会较低；若希望选出的瓜中好瓜比例尽可能高，则可只挑选最有把握的瓜，但这样就难免会漏掉不少好瓜，使得查全率较低.通常只有在一些简单任务中，才可能使查全率和查准率都很高.

我们可以画个图（其实就是收益曲线） 怎么判断模型好坏？图中BC好判断，AB如何判断？
引入一个综合考虑查准率、查全率的性能度量：平衡点(Break-Event Point,简称BEP)，是查准率=查全率时的取值。这个值越大性能越好。

但BEP还是过于简化了些，更常用的是F1度量，一个基于查准率与查全率的调和平均

$$F1=\frac{2\times P\times R}{P+R}=\frac{2\times TP}{\text{样例总数}+TP-TN}$$

若任务场景是对查重率或查准率某一个有更高要求，可以对二者加以不同的权重，即F1度量的一般形式——Fβ $$F_{\beta}=\frac{(1+\beta^{2})\times P\times R}{(\beta^{2}\times P)+R}$$ 其中β> 0度量了查全率对查准率的相对重要性[VanRijsbergen, 1979]。β= 1时退化为标准的F1; β> 1时查全率有更大影响；β< 1时查准率有更大影响。

2.3.3 ROC 与 AUC

换了个说法让人一懵，细细一想只不过是另一种作图方式，定义
- 纵轴是好瓜的查全率（真正例率），即好瓜里面有多大比例被挑了出来
- 横轴是坏瓜的查全率（假正例率），即坏瓜里面有多大比例被不小心挑出来了。

画个图是这样的

1730819590980.png

最理想的情况肯定是坐标(0,1),好瓜全都挑出来了，坏瓜没有粗心选出来一个。同理最差情况是坐标(1,0).对角线实际上就是随机抽样。ROC围成的面积成为AUC，一般认为AUC越大模型效果越好

2.3.4 代价敏感错误率与代价曲线

分类问题中的错误可以分为两种，不小心选了坏瓜，漏选了好瓜，有时候这两种错误我们更重视某一种，因此自然地为二者引入不同的cost权重
如此一来，上面的ROC曲线就不管用了，考虑引入权重作图。
这一块不太好理解，我写一下个人的阐述
横轴为正例概率代价，其实是假设我们的模型就是随机取样，对总代价的归一化度量 $$P(+)cost=\frac{p\times cost_{01}}{p\times cost_{01}+(1-p)\times cost_{10}}$$ 纵轴为运用了我们提出的模型之后，代价的归一化度量 $$cost_{norm}=\frac{\mathrm{FNR}\times p\times cost_{01}+\mathrm{FPR}\times(1-p)\times cost_{10}}{p\times cost_{01}+(1-p)\times cost_{10}}$$ 自然可以理解，某一点的坐标纵坐标小于横坐标才能说明模型是有效的，纵坐标越比横坐标小就越有效，为此取无穷条曲线的下包络，围城面积越小则认为模型效果越好。个人感觉此处应该是有严格的数学证明推导这些统计意义。

2.4比较检验

我挺不喜欢这一部分的内容，这也是统计学总是被机器学习大佬诟病的一点–花了太多精力在各种推断与检验上，不过作为学生基本知识该有还是得有。再此我只做简单的了解，写论文最后需要用的时候再学。

统计假设检验(hypothesis test)为我们进行学习器性能比较提供了重要依据。

为什么这么说？我们上面提出了很多度量模型效果的标准，倘若在某种标准下模型A的泛化效果比B好，我们就可以断言A这个模型一定在此任务中优于B吗？显然不是。在这个测试集上A优于B，换个测试集就说不定了。大千世界无奇不有。

比较检验解决的就是这样的问题，我们用统计学方法探讨A的泛化性能是否在统计意义上优于B？以及这个结论的把握有多大。

2.4.1假设检验

及其不常用，而且周的阐述疑似有误，这里贴一个讨论博客 周志华《机器学习》38页关于二项检验的公式(2.27)是否有误？7 个回答 默认排序 politer politer 教师 49 人赞同了该回答

2.4.4 Friedman检验与Nemenyi后续检验

交叉验证t检验和McNemar检验都是在一个数据集上比较两个算法的性能，而在很多时候，我们会在一组数据集上对多个算法进行比较.当有多个算法参与比较时，这时候可以使用基于算法排序的 Friedman 检验。

2.5方差与偏差

泛化误差可分解为偏差、方差与噪声之和： E(f; D) = bias²(x) + var(x) + ε²

偏差（Bias）

• 含义：偏差衡量的是你的模型预测的平均值与真实房价之间的偏离程度。它反映了模型对数据的拟合能力。

• 例子：以房价预测为例子，如果你使用的模型非常简单（比如线性回归），它可能无法捕捉到房价与特征之间的复杂关系，导致预测结果普遍偏低或偏高。这就是高偏差的情况，意味着模型欠拟合，没有充分利用数据中的信息。

• 影响：高偏差会导致模型在训练集和测试集上的表现都不好，因为模型没有学习到数据的真实分布。

方差（Variance）

• 含义：方差衡量的是当你使用不同的训练集（但大小相同）来训练模型时，模型性能（如预测准确度）的变化程度。它反映了数据扰动对模型性能的影响。

• 例子：如果你使用的模型非常复杂（比如深度神经网络），它可能会过度拟合训练集，即记住训练集中的每一个细节，而不是学习到一般的规律。这样，当模型遇到新的测试数据时，它的预测结果可能会因为训练集的微小变化而大幅波动。这就是高方差的情况。

• 影响：高方差会导致模型在训练集上表现很好，但在测试集上表现很差，因为模型过于依赖训练集的具体细节，而不是数据的真实分布。

噪声（Noise）

• 含义：噪声是数据本身固有的、无法通过学习算法来减少的误差。它表示了在当前任务上，任何学习算法所能达到的期望泛化误差的下界。

• 例子：在房价预测中，噪声可能来自于房屋价格的随机波动、数据收集过程中的误差、或者某些无法量化的特征（如房屋的“风水”好坏）。这些因素都会导致房价的不确定性，使得即使是最优的模型也无法完全准确地预测房价。

• 影响：噪声限制了模型性能的上限。无论模型多么复杂或精细，它都无法超越噪声所设定的泛化误差下界。

1730822103884.png

3.1基本形式

f(x) = w^Tx + b

线性模型形式简单，易于建模，蕴含着机器学习中重要的思想，而且可解释性强，

3.2线性回归

$$\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}$$

求导之后可以得到简单的封闭解，拓展到矩阵形式也是一样的。

任何函数内套上一层线性回归，称之为广义线性模型 y = g⁻¹(w^Tx + b)

3.3对数几率回归

$$y=\frac1{1+e^{-(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b)}} .$$

这是sigmod函数，一般取y=0.5位分界判断点，上一个式子可以改写成 $$\ln\frac y{1-y}=\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b .$$ 也就是说我们在用线性回归去学习对数几率，显然有 $$p(y=1\mid\boldsymbol{x})=\frac{e^{\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b}}{1+e^{\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b}} ,\\p(y=0\mid\boldsymbol{x})=\frac{1}{1+e^{\boldsymbol{w}^\mathrm{T}\boldsymbol{x}+b}} .$$ 用极大似然法、或者对偶理论，可以得到需要去最优化的函数 $$\ell(\boldsymbol{\beta})=\sum_{i=1}^m\left(-y_i\boldsymbol{\beta}^\mathrm{T}\hat{\boldsymbol{x} }_i+\ln\left(1+e^{\boldsymbol{\beta}^\mathrm{T}\hat{\boldsymbol{x} }_i}\right)\right)$$

3.4线性判别

LDA 的思想非常朴素：给定训练样例集，设法将样例投影到一条直线上， 使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别.图 3.3 给出了一个二维示意图.

具体的推导可以参见暑期的统计机器学习笔记

3.5多分类学习

• 一对一（OvO）：将N个类别两两配对，产生N * (N − 1)/2个二分类任务，最终的结果通过每个二分类器投票产生
• 一对其余（OvR）：将一个类别作为正例，将其他类别作为反例来训练N个分类器，最终结果由置信度最大的一个分类器决定
• 多对多（MvM）：常用纠错输出码方法（ECOC），训练时编码，对N个类别进行M次划分，训练M个二分类器。测试时解码，使用M个分类器对其预测，将生成的编码与每个类别的编码比较，距离最小的即为预测结果

1730907077041.png

3.6类别不平衡问题

常用三种解决方法

• 欠采样 (undersampling):也称下采样，去除一些比例高的数据
• 过采样 (oversampling):也称上采样，通过插值增加一些比例少的数据
• 阈值移动 (threshold-moving):用原始训练集训练，但在预测时令$\frac{y^{\prime}}{1-y^{\prime}}=\frac{y}{1-y}\times\frac{\text{反例数量}}{\text{正例数量}}$

第三条的意义在于，我们往往假设训练集是真实样本的无偏采样，因此判断阈值应当是大于观测几率的。

4.1基本流程

决策树模仿人类的决策处理机制，利用树结构进行预测

4.2划分选择

决策树的关键在于划分选择，也就是选择合适的划分标准，使得树的节点包含类别的纯度越来越高

下面给出几种常用的划分依据 ## 4.2.1 信息增益 引入信息熵来度量样本集合的纯度，假设当前样本集合D中第k类样本所占的比例为p_k,则定义此集合的信息熵为 $$\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_2p_k .$$ 利用属性a对样本进行划分之后的信息增益定义为 $$\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)$$ ## 4.2.2 增益率 有了信息增益还不够，如果我们将类似于编号之类的东西也作为划分依据，他的信息增益可以很大，但是不具有泛化能力，也就是说信息增益对可以取值的数目较多的属性有偏好，为了解决这个问题，引入信息增益率 $$\text{Gain ratio}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)} ,\\\text{其中}\\\mathrm{IV}(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}\log_{2}\frac{|D^{v}|}{|D|}$$ 称为属性a的固有值，a的可取值越多，固有值越大，增益率对分类效果好同时可取值数目少的特征有所偏好

4.2.3基尼系数

定义基尼值为随机抽取两个值，类别标记不一致的概率 $$\begin{aligned}\operatorname{Gini}(D)&=\sum_{k=1}^{|\mathcal{Y}|}\sum_{k^{\prime}\neq k}p_{k}p_{k^{\prime}}\\&=1-\sum_{k=1}^{|\mathcal{Y}|}p_{k}^{2} .\end{aligned}$$ 相应的，定义划分之后的基尼系数 $$\mathrm{Gini_index}(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|_.}\mathrm{Gini}(D^v)$$ 我们选取使得基尼系数最小的特征作为划分依据

4.3剪枝

剪枝的思路大致分为两种，预剪枝，后剪枝，剪枝是决策树防止过拟合的主要方法

4.4 连续与缺失值

4.4.1 如何处理连续值？

连续值的可取值数目不再有限，我们一般把出现的属性数值排序，然后利用二分或者什么其他方法搜索使得信息增益最大的分界点。 $$\begin{aligned} \mathrm{Gain}(D,a)& =\max_{t\in T_{a}} \mathrm{Gain}(D,a,t) \\ &=\max_{t\in T_a} \mathrm{Ent}(D)-\sum_{\lambda\in\{-,+\}}\frac{|D_t^\lambda|}{|D|}\mathrm{Ent}(D_t^\lambda) \end{aligned}$$

4.4.2 如何处理缺失值？

如何在属性值缺失的情况下进行数据划分？

核心的处理思路就是用无缺样本代替总体来进行计算

4.5多变量决策树

多变量决策树 (multivariate decision tree) 的非叶结点是形如$\sum_{i=1}^dw_ia_i=t$的线性分类器，不 再仅对某个属性，而是对所有属性的线性组合进行测试，其中w_i, t都可以通过样本学习得到

5.1神经元模型

$$y=f\left(\sum_{i=1}^nw_ix_i-\theta\right)$$ 激活函数常用 以及RELU

5.2感知机

1731055763592.png

举个例子

我们要解决的问题是：二分类N个样本点(x_i, y_i)，其中x_i ∈ R^p
引入： $$sign(a)=\left\{\begin{matrix}+1,a\geq0\\-1,a<0\end{matrix}\right.$$

感知机的思路是把线性回归的结果填充到激活函数中：
f(x) = sign(w^Tx)

这样f(x)即为预测结果。
此时，问题变为如何求解w。我们使用梯度下降的策略，那么自然的需要引入loss函数。为了引入合适的loss函数，做一些必要的讨论

我们考虑一个被正确分类的点(x_i, y_i)，若 w^Tx_i > 0，则 y_i = +1,若w^Tx_i < 0，则 y_i = −1,因此对于正确分类的点(x_i, y_i)，总有y_iw^Tx_i > 0

1722854448587.png

综上所述，我们引入形如下式的loss函数 L(w) = ∑_{xi ∈ 𝒟wrong} − y_iw^Tx_i

应用梯度下降法可得

$$\frac\partial{\partial w}L(w)=\sum_{x_i\in\mathcal{D}_{wrong}}-y_ix_i$$

w^t + 1 ← w^t + λy_ix_i

感知机由两层神经元组成，只有输入层神经元进行激活函数处理，学习能力十分有限。他只能在现行线性可分问题上收敛，甚至不能解决疑惑异或问题这样的简单非线性可分问题。

要解决非线性可分问题需要考虑使用多层神经元

5.3误差逆传播算法/BP算法

BP算法是训练多层神经网络的有效方式，具体可参见矩阵求导技术

数学上可以证明，只需要一个包含足够多神经元的隐藏层，多层前馈网络就可以以任意精度逼近任意复杂度的连续函数。不过如何设计神经网络结构是一个未知问题。

因为强大的学习能力和表示能力，神经网络容易过拟合，解决过拟合的方法有两种

• 早停：训练集误差减小但是测试集误差上升的时候停止训练
• 正则化，在loss函数中加一个用于描述网络复杂度的部分

比如，令E_k表示第k个样例上的误差，w_i表示连接权重，误差函数改变为 $$E=\lambda\frac1m\sum_{k=1}^mE_k+(1-\lambda)\sum_iw_i^2$$ 超参数λ使用交叉验证来估计

5.4全局最小与局部最小

神经网络的训练应当避免陷入局部最优解，利用梯度搜索方法找到某个最小值之后，人们会采用一些策略跳出可能存在的局部最小，进一步接近全局最小

• 不同参数值初始化多个神经网络，训练后取误差最小的解作为最终解
• 模拟退火，在每一步都已一定概率接受比当前更差的结果，迭代过程中接受次优解的概率应该逐渐降低
• 使用随机梯度下降法
• 遗传算法

5.5其他神经网络

6.1 间隔与支持向量

支持向量机用于解决二分类问题，希望找到一个超平面对平面中的点进行合理划分
$$\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=\frac2{||\boldsymbol{w}||}$$ 目标是找到最大间隔的超平面 $$\begin{aligned}&\max_{\boldsymbol{w},b} \frac{2}{||\boldsymbol{w}||}\\&\mathrm{s.t.} y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b)\geqslant1,\quad i=1,2,\ldots,m.\end{aligned}$$ 这等价于 $$\begin{aligned}&\min_{\boldsymbol{w},b} \frac{1}{2} \|\boldsymbol{w}\|^{2}\\&\mathrm{s.t.} y_{i}(\boldsymbol{w}^{\mathrm{T} }\boldsymbol{x}_{i}+b)\geqslant1,\quad i=1,2,\ldots,m.\end{aligned}$$

6.2对偶化简

拉格朗日函数为 $$L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac12 \|\boldsymbol{w}\|^2+\sum_{i=1}^m\alpha_i\left(1-y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b)\right)$$

令L(w, b, α)对w和b的偏导为零可得

$$\boldsymbol{w}=\sum_{i=1}^m\alpha_iy_i\boldsymbol{x}_i\:,$$

$$0=\sum_{i=1}^m\alpha_iy_i\:.$$

转为对偶问题 $$\max_{\boldsymbol{\alpha} }\quad\sum_{i=1}^m\alpha_i-\frac12\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}$$ 如何求解？一般来说可以用通用的二次规划方法求解，也可以用SMO算法
SMO 的基本思路是先固定α_i之外的所有参数，然后求α_i上的极值.由于存在约束$\sum_{i=1}^m\alpha_iy_i=0$,若固定α_i之外的其他变量，则α_i可由其他变量导出. 于是，SMO 每次选择两个变量α_i和α_j,并固定其他参数. 这样，在参数初始化后，SMO 不断执行如下两个步骤直至收敛：

选取一对需更新的变量 α_i 和 α_j; 固定 α_i 和 α_j 以外的参数, 求解式(6.11)获得更新后的 α_i 和 α_j

具体的： $$\alpha_{i}y_{i}+\alpha_{j}y_{j}=c , \alpha_{i}\geqslant0 , \alpha_{j}\geqslant0 ,\\c=-\sum_{k\neq i,j}\alpha_ky_k$$

为此我们可以求出每一步优化问题的闭式解 偏移项可以利用kkt条件求出 y_s(∑_i ∈ Sα_iy_ix_i^Tx_s + b) = 1

6.3 核函数

原始的假设基于线性可分的思路，分割函数如下

$$\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}$$

核函数的引入使得svm拥有了拟合非线性边界的问题，核函数把x映射到了高维空间 f(x) = w^Tϕ(x) + b 最终要求解的对偶问题变为了 $$\max_{\alpha} \sum_{i=1}^{m}\alpha_{i}-\frac{1}{2} \sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\phi(\boldsymbol{x}_{i})^{\mathrm{T}}\phi(\boldsymbol{x}_{j})$$

为了避免高维内积的困难，引入核函数 κ(x_i, x_j) = ⟨ϕ(x_i), ϕ(x_j)⟩ = ϕ(x_i)^Tϕ(x_j) 给出一些常用核函数

6.4 软间隔与正则化

允许svm在一些样本上出错，引入软间隔概念
比如，采用hinge损失，将目标函数改为 $$\min_{\boldsymbol{w},b} \frac{1}{2}\|\boldsymbol{w}\|^2+C\sum_{i=1}^m\max\left(0,1-y_i\left(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b\right)\right)$$ 引入松弛变量，将上式子改写为 $$\min_{\boldsymbol{w},b,\xi_i}\quad\frac12\|\boldsymbol{w}\|^2+C\sum_{i=1}^m\xi_i$$ $$\mathrm{s.t.}\quad y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b)\geqslant1-\xi_i\\\xi_{i}\geqslant0 , i=1,2,\ldots,m.$$ 注：约束条件就是变量代换的恒等式
拉格朗日乘子法求解出对偶问题 $$\begin{aligned} \underset{\boldsymbol{\alpha}}{\operatorname*{max}}& \sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^\mathrm{T}\boldsymbol{x}_j \\ \text{s.t.}& \sum_{i=1}^m\alpha_iy_i=0 , \\ &0\leqslant\alpha_i\leqslant C ,\quad i=1,2,\ldots,m . \end{aligned}$$

6.5支持向量回归SVR

支持向量回归(Support Vector Regression, 简称 SVR)假设我们能容忍 f(x) 与y之间最多有ϵ的偏差，即仅当f(x)与y之间的差别绝对值大于ϵ时才计算损失.如图 6.6 所示，这相当于以f(x)为中心，构建了一个宽度为 2ϵ的间隔带，若训练样本落入此间隔带，则认为是被预测正确的.

6.6 核方法