斯坦福大学《Machine Learning》第7周学习笔记
Support Vector Machines 支持向量机
Large Margin Classification大间距分类器
Optimization Objective优化目标
到目前为止, 你已经接触过多种不同的学习算法. 在监督学习领域中, 各类学习算法的表现往往相当接近. 因此，在监督学习领域中, 重要的是应用这些算法时所生成的数据质量. 具体来说，则取决于你在构建模型时所选择的特征工程方案以及正则化参数的设置. 另外一个更为强大的方法广泛应用于工业界和学术研究领域，并被称为支持向量机（SVM）.
在逻辑回归模型中，在面对一个y=1的样本实例时 我们的首要目标是使h(x)尽可能接近真实标签值1 这一目标要求我们确保当h(x)趋向于最大值时 其线性组合θ^T x必须远超过零值 从而使得该模型预测结果趋向于最大值1
逻辑回归的代价函数中 每个样本 (x, y) 都会为总代价函数 增加这里的一项
正在构建支持向量机模型，并采用紫色曲线替代原有曲线。在这一过程中，我们采用了新的代价函数：左边采用cost1(z)，右边则采用cost0(z)。其中y取值为1或0时的情况分别由这两个函数来描述。
基于这些定义后我们现在开始搭建支持向量机。这相当于我们在逻辑回归模型中应用了代价函数J(θ)。
在逻辑回归模型中，我们的目标是在目标函数中最小化A + \lambda \times B。我们所做的是通过选择不同的正则化系数\lambda来实现这一优化目标。这种情况下，我们可以根据模型对训练数据的拟合程度以及对 regularization term 的影响来决定如何分配权重。也就是说，在平衡这两者之间时，我们需要确定是否优先最小化A（即提高模型对训练数据的拟合度），还是让\lambda保持足够小以避免过强地惩罚B项。
但对于支持向量机来说，我们按照惯例采用另一个参数C（相当于λ倒数的效果），并将其优化目标设定为C×A+B的形式。由此可见，在逻辑回归中，当λ被赋予一个极大的值时，则意味着给予B更大的权重；而这一做法实际上对应于将C设为极小值的情况。此时相应的结果将是B相对于A获得更大的权重。由此可见，这仅仅是一种不同的方式来调节这种权衡关系；或者说是通过参数的选择来决定是更加关注第一项的优化问题还是第二项的优化问题。
该目标函数通过SVM学习获得参数C来区分与逻辑回归不同的地方在于其输出概率的方式。当最小化代价函数以获得参数θ时，支持向量机通过直接预测y值为1还是0来进行分类。因此，在θT*x大于或等于0时该假设函数会预测y=1；而当θT*x小于0时则预测y=0。由此可知，在这种情况下学习得到的参数θ即构成了支持向量机的假设函数形式。
Large Margin Intuition大间距分类器
在某些情况下, 支持向量机 被视为最大间隔分类器。本节将阐述其内涵, 以便我们直观地掌握SVM模型的基本假设。这也构成了我所构建的支持向量机模型的成本函数。
如果一个正样本y=1，则本质上我们仅需θ^T x≥0即可将该样本正确分类这是因为如果θ^T x>0的话我们的模型代价函数值为零类似地 如果存在一个负样本 则同样只需θ^T x≤0即可实现对负例的有效分离然而支持向量机的要求更为严格 它不仅要求能够正确划分输入样本即不仅要求θ^T x>0还需要其与零值有较大的差距例如≥1我也希望对于负样本的情况能够做到与零值有相同的较大差距即≤-1这样的设定实际上相当于在支持向量机中引入了一个额外的安全间隔因子或者说是保障间距的因素当然逻辑回归也采取了类似的做法让我们进一步探讨在支持向量机中这一因子将会产生什么样的影响
具体地说，在这种情况下我将考虑一个具体的例子为此目的我们需要将常数C设定为其极大值例如我们可以设定其数值为一百万或者更大的其他极端数值之后再通过观察支持向量机的行为来分析其输出结果
当参数C非常大时，在最小化代价函数的过程中我们希望能够找到一个θ值使得第一项等于零从而获得最优解输入一个训练样本标签为y=1我们需要令这一项等于零为此我们需要选择θ使得θ^T x ≥ 1类似地 对于标签为y=0的一个训练样本为了使cost_0(z)等于零我们需要选择θ使得θ^T x ≤ -1因为我们将选择参数以确保第一项等于零这样一来我们的优化问题就转化为如图右下角所示的形式当我们在最小化关于θ的函数时会发现决策边界非常有趣
具体来说，在考察这样一个线性可分的数据集时，默认情况下红色与绿色之间的角色边界并非最佳选择。支持向量机会选择这个黑色的决策边界，并且可以看出，在这种情况下，默认情况下使用的这个黑色决策边界具有更稳健性和优越性，并且拥有更大的几何距离。这一特定的距离被定义为“间距”（margin），这也是支持向量机具备鲁棒性的根本原因。因为它致力于通过最大化间距来实现对样本的分离，并因此而得名的大间距分类器（Support Vector Machine, SVM）。事实上，这一策略正是源于求解上一页幻灯片中所展示的优化问题。
在该案例中，在该案例的前提条件下（即当正则化参数C被设定得相当高时），实际上，支持向量机的表现已经较之较大间隔分类器而言更为成熟。
如图所示的一个样本集中，在左下角存在一个异常值。当正则化参数C被设置得非常大的时候，在支持向量机模型中发现了一条明显的分界线——粉红色线条。然而，在仅凭这一个异常点就将我的决策边界从这条黑色界限调整至粉红色界限的做法实在不够明智。
如果将参数 C 调整得稍微小一些，则你将能够观察到这条黑色线条。这表明当参数 C 被恰当地选择时，在支持向量机中会忽略掉一些异常点的影响，并形成一个更为精确的决策边界。然而，在实际应用中讨论的大间距分类器的概念仅限于那种情况下：即当正则化参数 C 设置得非常大时。
其背后的核心数学理论涉及大间隔分类这一分类方法所依赖的基础理论
在复习向量内积的相关知识时，请注意u的转置与v的乘积结果即为向量u与v的点积。
u.v = ||u||||v||cosθ = p||u|| (其中p = ||v||*cosθ，也就是v在u上的投影，它是有正负的，由夹脚θ决定)
这是围绕向量内积的概念进行讨论。接下来我们将利用这些与向量内积相关的属性来进行深入分析，并试图通过这一过程来理解支持向量机中目标函数的本质。这正是我们在前面所述的支持向量机模型中所提出的优化目标（当参数C趋向于无穷大时）。为了简化讲解过程，在后续分析中我们将截距项忽略，并设定θ₀等于零。同时假设特征空间的维度n设为2。
让我们来分析一下目标函数——支持向量机的目标函数。当n=2时，这个表达式就可以表示为：(½)·(二次项 θ₁² + 二次项 θ₂²)；仅有两个参数——即参数组(θ₁, θ₂)，因此我们的目标函数最终表现为右图所示的情况：决策边界与向量之间存在垂直关系（具体来说，在决策边界方程中：系数比例决定了其斜率为-α/β；而该比例对应的向量方向则决定了其斜率为β/α）
首先观察右图左边的那个决策边界线，在深入探讨支持向量机模型的选择机制时发现其无法被该模型所采纳的原因在于其不具备足够的分类间隔性
支持向量机的主要任务是通过最小化参数向量\theta范数平方的方式来实现分类过程。具体而言，在满足约束条件p\cdot\|\theta\| \geq 1（当y=+1）以及p\cdot\|\theta\| \leq -1（当y=-1）的情况下，则需要使\theta范数尽可能的小。其中x在\theta方向上的投影值即为变量p；因此希望这个投影值越大越好，并且如前所述，在SVM中参数向量\theta的方向与决策边界线相互垂直；类似地，在y=-1$的情况下也能够得到相同结论。
Kernels核函数
Kernels I核函数
我们对支持向量机算法进行一定程度的优化 以构建高阶复杂分类器 借助于'kernel spaces(核函数空间)'这一技术实现这一目标
让我们了解什么是核函数及其应用方法。核函数是一种将低维数据映射到高维空间的函数技术，在支持向量机中被广泛采用。假设你有一个训练数据集（例如像这样的一组样本），然后试图拟合一个非线性判别边界来区分正负样本类别。一种常用的方法是引入多项式特征变量，在新的空间中求解线性可分问题。当θ₀加上θ₁乘以x₁以及其他多项式项的总和大于零时，则预测结果为正类；反之，则预测结果为负类。
该模型的一个替代表述为：θ_0 + θ_1·f_1 + θ_2·f_2 + θ_3·f_3其中各基函数定义如下：f_1对应于x_1、f_2对应于x_2、f_3对应于x₁x₂、而f₄和f₅分别由x₁²和x₂²生成。我们之前观察到，在引入这些高阶基函数后能够显著丰富特征空间
问题是 如何构造这些高阶项来最好的拟合我们的数据
**
**
这里有一个新的特征构造方法论f₁, f₂, f₃的想法。人工选择一些特定的数据点，并分别以l(1)、l(2)、l(3)的形式定义这些标记点。对于第n个特征变量fn来说，则表示一种相似度指标。具体而言，在计算样本x与第n个标记之间的相似程度时所采用的公式如上图所示。这个相似度函数被定义为核函数K(x, l(n))的形式，在本例中我们使用高斯核函数作为标准形式进行计算。当样本x与某个标记点l(n)非常接近时，则该核函数值K(x, l(n))将趋近于1；反之，则会趋近于0。
σ²是高斯核函数中的一个关键参数。当调整σ²的数值时，会产生略微不同的结果。当σ²数值较小时，在概率密度曲线上表现为更加尖锐的峰值；同时，在等高线图中也会呈现出更为紧凑的形态。随着σ²数值的变化，在数据空间中各特征变量的变化速率也会随之调整。
基于所获得的参数值θ₀=-₀.₅、θ₁=₁、θ₂=₁、θ₃=₀（如图所示），当样本x接近l(₁)时，则有f₁趋近于₁；由于x远离l(₂)和l(₃)，则有f₂及f₃均趋近于零。对于另一个不同的点x进行同样的计算后会发现f₁、f₂、f₃都趋近于零。经过大量点的处理后，我们得到了这个预测函数的结果边界：位于判别边界内部的所有点会有y=₁的结果，在外部则会得到y=₀。
这就是核函数这部分的内容以及我们在支持向量机中如何利用它们。具体来说，我们通过将标记点与相似性函数结合来构建新的特征空间以训练复杂的非线性分类器。
Kernels II核函数
上一节遗留问题 我们如何得到这些标记点？
我们直接 将训练样本 作为标记点 整个过程的大纲如下
主要涉及n等于m时特征的数量与样本数量之间的关系。具体来说, 优化函数中的第二项即θj从1到m的所有平方和可以表示为θ转置乘以θ, 在开始优化前, 请确保先忽略θ0
在实现过程中通常会替代θ转置与θ的乘积，并使用θ转置与某个核函数相关的矩阵相乘。其计算过程受所选核函数的影响，并随后与θ相乘。这相当于采用了另一种不同的度量方式。我们采用了与直接计算θ模平方不同的度量方法，并不直接使用它来进行最小化而是最小化了另一种类似的目标函数。这种优化策略本质上是基于变尺度的方法，并且其设计与所选核函数密切相关。这种数学特性使得支持向量机在处理复杂分类问题时表现出更高的效率。
采用支持向量机的方法进行这种调整的原因在于这种调整方式能够有效适应超大的训练集。比如当训练数据规模达到1万样本时这种方法的优势就更加明显。
比如为什么我们不将 核函数这个想法 应用到其他算法 比如逻辑回归 上 事实证明 如果愿意的话 确实可以将核函数 这个想法用于定义特征向量 将标记点之类的技术用于逻辑回归算法 但是支持向量机 的计算技巧 不能较好的推广到其他算法诸如逻辑回归上 所以 将核函数用于 逻辑回归时 会变得非常缓慢 相比之下 这些计算技巧 比如具体化技术 对这些细节的处理 以及支持向量软件的实现细节 使得支持向量机 可以与核函数相得益彰 而逻辑回归和核函数 则运行得十分缓慢 更何况它们还不能 使用那些高级优化技巧 因为这些技巧 是人们专门为 使用核函数的支持向量机开发的
在应用支持向量机的过程中
SVMs in Practice练习SVMs
Using An SVM使用SVM
在使用支持向量机模型时，核心环节主要包括首先需确定参数C的值；其次应选择合适的核函数。
其中一种选择是我们考虑采用不带任何核函数的方法。这种做法被称为线性核函数这一版本的支持向量机（SVM）仅基于θ转置乘以x来进行判断。当θ₀ + θ₁x₁ + ... + θₙxₙ大于等于零时，默认预测结果y=1。对于线性核函数这一术语你也可以理解为这一版本的支持向量机它仅仅提供了一个标准的线性分类器（什么时候不用核函数？）。因此在某些特定问题中这是一种合理的选择而且你知道有许多现成的软件库比如liblinear就是一个例子它们专门用于训练不带任何核函数的支持向量机模型。那么你为什么要这样做呢？如果你的数据集中特征变量数量较多而样本数据量却相对较小那么你知道在这种情况下拟合一个简单的线性边界可能更加合适不要试图拟合复杂的非线性模式因为数据不足可能导致过拟合现象的发生因此这可能是你决定使用不带任何核函数或等价地采用线性核函数的一个合理依据。
当采用高斯核函数作为核函数时，另一个需要考虑的决定是确定一个参数σ²。
在什么情况下应选用高斯核函数？当原始特征向量x具有n维空间时，如果n值较小，并且在理想条件下当样本数量m较大时
假设我们有一个二维的数据集，在之前的例子中已经展示过类似的情形；其中n=2；然而我们的训练数据量非常庞大；我已经绘制了大量具有代表性的样本点；为了更好地划分这些点所处的空间区域；建议使用核函数来构建更为复杂的非线性分类边界；而高斯核内核函数因其良好的非线性映射能力而备受青睐；
如果你选择使用 Octave 或 Matlab 来实现 支持向量机 的话 那么它会要求你设计一个特定的内核函数来计算其相关特征 它会自动完成所有特征变量的生成 利用你的自定义内核函数 将输入样本 x 转换为对应的 f1 f2 直至 fm 这些特征值 然后开始训练支持向量机模型 但有时候 如果你选择使用高斯内核 几乎所有的SVM实现都会包含这一内核 出于其作为最常用内核之一的原因 此时你需要自行编写这一内核功能
当你的数据集包含规模显著不一的特征变量时，在应用高斯核函数之前，归一化变得尤为关键。
假设你正在处理一组特征变量，并希望理解它们在不同场景下的表现。以房价预测为例，在这个任务中你会遇到不同类型的特征变量。例如，在你的数据集中包含与房屋相关的信息时，请注意以下几点：其中x₁的取值范围可能达到数千平方英尺（x_1），而另一个变量x₂则表示卧室数量（x_2），其可能落在一至五间（1 \leq x_2 \leq 5）。
其中x₁-l₁可能会变得非常大,其数值可能达到上千数量级,并且是平方的形式。相比之下,x₂-l₂可能会变得非常小。在这种情况下,在这一公式中,这些间距几乎完全由房间尺寸决定,从而忽视了卧室数量的影响。为了避免上述情况的发生,确保支持向量机能够正常运作,必须对各个特征变量进行标准化处理。这将确保支持向量机能够等比例地考虑所有不同类型的特征变量,而不是像示例分析中那样只关注房屋尺寸这一单一因素。
并不是所有被提出的相似度函数都能成为有效的核函数。例如像高斯核、线性核以及其他被某些人偶尔采用的其他类型的核函数虽然存在但它们都必须满足一个技术条件即被称为**默塞尔定理 (Mercer's Theorem)**这一条件之所以必要是因为支持向量机算法（SVM）或其他机器学习模型中由于拥有众多巧妙的数值优化技巧因此在求解参数θ的过程中需要特别关注并只关注那些能够满足默塞尔定理要求的特定类型 of 核 function这样做不仅能够确保各种基于 SVM 的软件包能够有效地利用这些优化方法而且还能迅速地获得所需的参数θ值
一些其他的核函数：包括多项式型核函数、字符串特征型核函数、χ²特征型核函数以及基于直方图的交叉特征型核函数等
探讨以下两个关键点：首先是在多分类场景下（具体而言，在4个类别或K个类别的情况下），如何使SVM能够输出各类别间的合适判别边界？其次是大多数SVM软件包都预装了支持多分类的功能；如果使用这样的工具包，则可以直接调用内置函数来实现目标；这种方法通常效果良好；如果遇到困难，则可考虑采用一对一策略（one-vs-all）。我们之前曾在介绍逻辑回归时详细探讨了这一方法；具体来说，在拥有K个类别的情况下需要训练K个SVM模型；每个模型将其中一个特定类别与其他所有类别区分开来；这将产生K组参数向量θ^{(1)}, θ^{(2)}, …, θ{(K)}；其中θ{(j)}用于区分第j类与其他所有类别之间的判别边界；那么在这种情况下我们应该采用哪种方法呢？
当 特征变量的个数 n 相对于你的训练数据量而言较大时 常用的方法包括 逻辑回归、不带核函数的支持向量机（SVM）以及应用线性核函数的SVM。
当n相对较小且m处于中等规模时
第三种值得探讨的情况是：当n相对较小而m非常大时，在这种数据分布下采用高斯核函数的支持向量机（SVM）在这样的数据规模下可能会遇到性能瓶颈。当前主流的SVM实现若采用高斯核函数，在这种情况下可能会遇到性能瓶颈。对于约5万个样本的情况来说，这样的表现已经足够理想；但对于一百万个甚至更高的训练样本数量（即m值很大），情况就会变得较为吃力。在这种情况下，常见的做法是手动增加更多特征变量，并尝试使用非核化版本的支持向量机（如线性SVM）或者逻辑回归模型来提升性能。
观察一下这个幻灯片上提到逻辑回归模型或者未引入核函数的支持向量机（SVM）。在这两种场景下都出现了这些方法，并将它们放在一起进行比较的原因在于了解它们之间的异同点及其适用性差异。我们发现逻辑回归和未带核函数的支持向量机是非常类似的算法它们的功能相似并且在应用中表现出类似的效果但具体实现时其中一种可能在某些情况下表现更为出色如果其中一种方法在某个场景下适用则另一种方法也可能表现出良好的效果然而支持向量机的强大之处在于通过引入不同的核函数来处理复杂的非线性问题
神经网络的应用场景及适用时机是什么时候？就上述问题而言，就这些区间而言，在什么情况下应用神经网络会更有效？经过精心设计的神经网络通常表现出色。
其主要缺点在于 或者说在某些情况下 人们可能不选择使用 神经网络的原因。然而，在大多数情况下 神经网络训练速度较慢。不过 如果拥有一个高效的SVM实现库 则其运行速度显著快于神经网络。尽管我们尚未证明这一观点 但实际情况表明 SVM的最优化问题是凸优化问题 因此优秀的SVM优化软件通常能够找到全局最优解或接近该解的值
在实际应用中, local optimum for neural networks is not particularly large but also not negligible. Depending on your problem, neural networks would be expected to perform less efficiently than the support vector machine.
算法的重要性确实不容忽视。然而，在某些情况下（比如数据量、技术熟练度以及对误差分析等环节的掌握程度），你需要考虑以下几点：一是如何设计新的特征变量；二是如何选择并输入其他相关特征变量到学习算法中；三是这些能力相比仅仅选择逻辑回归或SVM来说更为关键。然而，在某些情况下（比如特定领域需求），SVM仍然是最强大的选择之一；它在一个特定区间内能够有效地学习复杂的非线性函数关系。因此，在我的知识库中逻辑回归、神经网络与SVM共同构成了我的核心技能储备；这些技术可以让你在构建前沿机器学习系统方面具备卓越的能力——这是一项强大的工具，并广泛应用于多个领域。
参考资料