本节目的：
- 能够计算模型的灵敏度和特异度。
- 能够构建混淆矩阵。
- 知道如何使用ROC曲线分析分类模型的性能。
- 能够阐述由正确分类所有数据点且具有最大间隔的超平面所解决的优化问题。
- 能够使用感知机算法计算分离超平面。
- 能够向最大间隔问题中引入松懈变量以允许分类错误。
- 对构建具有非线性边界条件的最大间隔问题有肯定的看法。
回首：分类问题
上一节，我们使用逻辑回归（logistic regression）计算标签出现的概率，接下来会使用这些概率并通过 “阈值”（thresholds）来对标签进行预测。
阈值
在某些应用中，必要做出预测，而不但仅是估计标签的概率。将条件概率 P ( y = l ∣ x 0 ) \mathbb{P}(y = l|x_0) P(y=l∣x0)转换为标签预测的一种简单方法是 f ( x 0 ) = arg max l P ( y = l ∣ x 0 ) f(x_0)=\underset{l}{\arg\max}\mathbb{P}(y = l|x_0) f(x0)=largmaxP(y=l∣x0)
符号含义
- x 0 x_0 x0 ：可以把它想象成某个具体的东西大概事件的一系列特征信息。比如在判断一个水果是不是苹果时， x 0 x_0 x0 大概包含了这个水果的颜色、形状、巨细等特征。
- y y y ：代表这个东西大概事件的类别标签。照旧以水果为例， y y y 大概的取值有“苹果”“香蕉”“橘子”等。
- l l l ：是 y y y 所有大概取值中的一个具体类别。比如在水果分类里， l l l 可以是“苹果” 这个具体类别。
- P ( y = l ∣ x 0 ) \mathbb{P}(y = l|x_0) P(y=l∣x0) ：它表示在已知特征信息是 x 0 x_0 x0 的环境下，这个东西属于类别 l l l 的概率。比如已知一个水果的颜色、形状、巨细等特征（ x 0 x_0 x0 ），它是苹果（ l l l ）的概率。
- arg max l \underset{l}{\arg\max} largmax ：这部分是核心操纵。“ arg max \arg\max argmax” 可以理解为“找到那个能使后面概率值最大的 l l l ”。
二分类问题
在二分类（类别为 { 0 , 1 } \{0, 1\} {0,1}）的环境下，这等同于设置：当 P ( y = 1 ∣ x 0 ) > 0.7 \mathbb{P}(y = 1|x_0)>0.7 P(y=1∣x0)>0.7时， f ( x 0 ) = 1 f(x_0)=1 f(x0)=1；否则 f ( x 0 ) = 0 f(x_0)=0 f(x0)=0。这里必要指出，0.7这个阈值虽然直观，但也是一个任意的选择。
f ( x 0 ) = { 1 if P ( y = 1 ∣ x 0 ) > 0.7 0 otherwise f(x_0)=\begin{cases} 1 & \text{if } \mathbb{P}(y = 1|x_0) > 0.7 \\ 0 & \text{otherwise} \end{cases} f(x0)={10if P(y=1∣x0)>0.7otherwise
二分类问题中，不同的阈值会导致产生不同的分类模型，分析如下：
二分类的混淆矩阵
- 行表示真实数据的标签（ y t r u e = 1 y_{true}=1 ytrue=1 和 y t r u e = 0 y_{true}=0 ytrue=0 ）。
- 列表示模型预测的标签（ y ^ = 1 \hat{y}=1 y^=1 和 y ^ = 0 \hat{y}=0 y^=0 ）。
- 当 y t r u e = 1 y_{true}=1 ytrue=1 且 y ^ = 1 \hat{y}=1 y^=1 时，对应单元格内容为“# model correctly predicts positive label.”（模型正确预测正标签的数目）；当 y t r u e = 1 y_{true}=1 ytrue=1 且 y ^ = 0 \hat{y}=0 y^=0 时，对应单元格内容为“# model incorrectly predicts negative label.”（模型错误预测负标签的数目）。
- 当 y t r u e = 0 y_{true}=0 ytrue=0 且 y ^ = 1 \hat{y}=1 y^=1 时，对应单元格内容为“# model incorrectly predicts positive label.”（模型错误预测正标签的数目）；当 y t r u e = 0 y_{true}=0 ytrue=0 且 y ^ = 0 \hat{y}=0 y^=0 时，对应单元格内容为“# model correctly predicts negative label.”（模型正确预测负标签的数目）。
- “Total”行和列分别是对应行和列的总和。
显然，改变阈值 T ，将会改变模型的性能，因为这会对分类边界产生影响：
- 通常以 0.5 作为阈值来判断样本属于正类照旧负类。若将阈值提高，比如从 0.5 提升到 0.7，那么模型判断为正类的标准变得更严酷，只有预测概率非常高的样本才会被判断为正类，这会使分类边界向正类方向移动。
混淆矩阵
混淆矩阵是机器学习中用于评估分类模型性能的紧张工具，尤其在二分类和多分类使命里广泛应用。
在给定阈值 T ∈ N T\in\mathbb{N} T∈N 和分类模型 p ( x ) p(x) p(x) 时:
指标计算公式
真正率（TPR）、假负率（FNR）、假正率（FPR）和真负率（TNR）的计算公式：
- T P R = model correctly predicts positive label truly positive data TPR=\frac{\text{model correctly predicts positive label}}{\text{ truly positive data}} TPR= truly positive datamodel correctly predicts positive label
- F N R = model incorrectly predicts negative label truly positive data FNR=\frac{\text{model incorrectly predicts negative label}}{\text{ truly positive data}} FNR= truly positive datamodel incorrectly predicts negative label
- F P R = model incorrectly predicts positive label truly negative data FPR=\frac{\text{model incorrectly predicts positive label}}{\text{ truly negative data}} FPR= truly negative datamodel incorrectly predicts positive label
- T N R = model correctly predicts negative label truly negative data TNR=\frac{\text{model correctly predicts negative label}}{\text{ truly negative data}} TNR= truly negative datamodel correctly predicts negative label
评估指标：灵敏度和特异度
回首一下回归问题和分类问题的评估指标：
- 在回归问题中，通常通过均方误差（MSE）、决定系数（R - squared）等来衡量拟合优度（goodness of fit）。
- 在分类问题中，通常关注衡量特定类别的性能（class - specific performance）。
在二分类或多分类问题中，存在其他指标：
- 灵敏度：是正确辨认出的真实正例的百分比，也称为真正率（True Positive Rate，TPR）。其计算公式为 T P R = S e n s i t i v i t y = #model correctly predicts positive label # truly positive data TPR = Sensitivity=\frac{\text{\#model correctly predicts positive label}}{\text{\# truly positive data}} TPR=Sensitivity=# truly positive data#model correctly predicts positive label ，即模型正确预测为正标签的数目除以真实正例数据的数目。
- 特异度：是正确辨认出的真实负例的百分比，也称为真负率（True Negative Rate，TNR）。其计算公式为 T N R = S p e c i f i c i t y = #model correctly predicts negative label # truly negative data TNR = Specificity=\frac{\text{\#model correctly predicts negative label}}{\text{\# truly negative data}} TNR=Specificity=# truly negative data#model correctly predicts negative label ，即模型正确预测为负标签的数目除以真实负例数据的数目。
在评判模型时，优先思量灵敏度照旧特异度，取决于应用场景以及数据科学家的偏好：
- 以癌症筛查为例，高假阴性率大概是劫难性的，因为这会遗漏真正患癌的患者。所以在这种环境下，宁可出现假阳性效果，以便推荐进一步的检查。
- 在刑事司法系统中，高假阳性率则是欠好的，因为这大概导致无辜的人被错误定罪。
例子
这里展示了一个关于聚合酶链式反应（PCR）和侧向流检测（LFD）的新冠病毒（COVID）检测效果的混淆表：
行和列的含义：行表示LFD检测效果（阳性“LFD +ve”和阴性“LFD -ve”），列表示PCR检测效果（阳性“PCR +”和阴性“PCR -”），同时另有对应PCR和COVID的总计列和行。
请你分别计算PCR和LFD的灵敏度和特异度。
PCR检测的灵敏度和特异度计算：
- 灵敏度（True - Positive Rate, TPR）：
- 灵敏度的计算公式为 T P R = 真正例 真正例 + 假负例 TPR=\frac{\text{真正例}}{\text{真正例}+\text{假负例}} TPR=真正例+假负例真正例。
- 在表格中，真正例（PCR检测为阳性且实际为阳性）的数目是 677 677 677，假负例（实际为阳性但PCR检测为阴性）的数目是 42 42 42。
- 所以PCR检测的灵敏度 = 677 677 + 42 = 677 719 ≈ 0.942 = 94.2 % =\frac{677}{677 + 42}=\frac{677}{719}\approx0.942 = 94.2\% =677+42677=719677≈0.942=94.2%。
- 特异度（True - Negative Rate, TNR）：
- 特异度的计算公式为 T N R = 真负例 真负例 + 假正例 TNR=\frac{\text{真负例}}{\text{真负例}+\text{假正例}} TNR=真负例+假正例真负例。
- 在表格中，真负例（PCR检测为阴性且实际为阴性）的数目是 7504 7504 7504，假正例（实际为阴性但PCR检测为阳性）的数目是 0 0 0。
- 所以PCR检测的特异度 = 7504 7504 + 0 = 1 = 100 % =\frac{7504}{7504+0}=1 = 100\% =7504+07504=1=100%。
LFD检测的灵敏度和特异度计算：
- 灵敏度（True - Positive Rate, TPR）：
- 真正例（LFD检测为阳性且实际为阳性）的数目是 339 339 339，假负例（实际为阳性但LFD检测为阴性）的数目是 338 338 338。
- 所以LFD检测的灵敏度 = 339 339 + 338 = 339 677 ≈ 0.501 = 50.1 % =\frac{339}{339 + 338}=\frac{339}{677}\approx0.501 = 50.1\% =339+338339=677339≈0.501=50.1%。
- 特异度（True - Negative Rate, TNR）：
- 真负例（LFD检测为阴性且实际为阴性）的数目是 7504 7504 7504，假正例（实际为阴性但LFD检测为阳性）的数目是 21 21 21。
- 所以LFD检测的特异度 = 7504 7504 + 21 = 7504 7525 ≈ 0.997 = 99.7 % =\frac{7504}{7504 + 21}=\frac{7504}{7525}\approx0.997 = 99.7\% =7504+217504=75257504≈0.997=99.7%。
ROC 曲线
笔墨分析部分
分类模型的性能通常通过绘制受试者工作特征（ROC）曲线来分析。
对于给定的分类模型，针对不同的阈值取值 { T 1 , … , T l } ⊂ [ 0 , 1 ] \{T_1, \ldots, T_l\} \subset [0, 1] {T1,…,Tl}⊂[0,1]，绘制真正率（TPR）与假正率（FPR）的关系图，从而得到ROC曲线。
我们期望找到一个真正率 T P R = 1 TPR = 1 TPR=1且假正率 F P R = 0 FPR = 0 FPR=0的分类器。
- 横轴为假正率（FPR），纵轴为真正率（TPR）。
- 图中有一条从原点 ( 0 , 0 ) (0, 0) (0,0)到点 ( 1 , 1 ) (1, 1) (1,1)的虚线，代表随机分类器的性能。即随机分类器的环境下，真正率和假正率是相称的。
- 图中有两条曲线（紫色和绿色），代表不同分类模型的ROC曲线。越靠近左上角（ T P R = 1 TPR = 1 TPR=1， F P R = 0 FPR = 0 FPR=0）的曲线，对应的分类模型性能越好，图中箭头指向“Better models”（更好的模型），表明朝着这个方向的模型性能更优。
AUC：ROC曲线下面积
- 图表横轴为假正率（FPR），纵轴为真正率（TPR）。图中有一条紫色曲线，代表某个分类器的ROC曲线。另有一条赤色折线，意为理论最优分类。
- 赤色折线下方的地区用蓝色斜线填充，该地区面积即为AUC,ROC曲线下面积。
AUC，即ROC曲线下面积，为分类器在所有阈值下的性能提供了一个度量指标。
- - 理论上，最好的分类器的AUC为1。
- - 存在一个阈值$T>0$，此时真正率$TPR = 1$（所有真正例数据点都被预测为正类）且假正率$FPR = 0$（所有真负例数据点都被预测为负类）。
- - 当把阈值降低到$T = 0$时，所有情况都被预测为正类，所以曲线必须经过点$(FPR, TPR)=(1, 1)$。
思绪
分离数据点
到目前为止，我们把基于数据进行预测的问题看成一个函数拟合问题，即实验学习 y = f ( x ) y = f(x) y=f(x)。
让我们实验一种不同的方法！
对于二分类问题，可以从几何角度来对待这个问题。我们必要将空间分成两部分，分别代表不同的类别标签。并且提到有很多方法可以分割 R n \mathbb{R}^n Rn空间（ n n n 维实数空间）。
思绪：找到具有最大“间隔”的线
我们希望找到一条与数据之间具有最大“间隔”的直线。为了实现这一点，我们将构建一个优化问题。
为了构建这个优化问题，我们必须使用线性代数来刻画这个“间隔”。
补充配景知识
点积
- 上方图示中有两个向量 x ⃗ \vec{x} x 和 y ⃗ \vec{y} y ，它们之间的夹角为 θ \theta θ。
- 下方图示同样有向量 x ⃗ \vec{x} x 和 y ⃗ \vec{y} y ，从 y ⃗ \vec{y} y 的终点向 x ⃗ \vec{x} x 作垂线，赤色箭头表示 y ⃗ \vec{y} y 在 x ⃗ \vec{x} x 上的向量投影，其长度标注为 d = ∥ y ⃗ ∥ 2 cos ( θ ) d = \|\vec{y}\|_2\cos(\theta) d=∥y ∥2cos(θ)。
- 对于向量 x ⃗ , y ⃗ ∈ R n \vec{x}, \vec{y} \in \mathbb{R}^n x ,y ∈Rn，定义点积为 x ⃗ ⋅ y ⃗ = ∥ x ⃗ ∥ 2 ∥ y ⃗ ∥ 2 cos θ \vec{x} \cdot \vec{y} = \|\vec{x}\|_2\|\vec{y}\|_2\cos\theta x ⋅y =∥x ∥2∥y ∥2cosθ，此中 θ \theta θ是 x ⃗ \vec{x} x 与 y ⃗ \vec{y} y 之间的夹角。
- 通过三角学可以证实，内积也可以等价地定义为 x ⃗ ⋅ y ⃗ = x ⃗ T y ⃗ \vec{x} \cdot \vec{y} = \vec{x}^T\vec{y} x ⋅y =x Ty 。
- 使用内积可以求出 y ⃗ \vec{y} y 在 x ⃗ \vec{x} x 上的向量投影的巨细，公式为 d = x ⃗ T y ⃗ ∥ x ⃗ ∥ 2 d = \frac{\vec{x}^T\vec{y}}{\|\vec{x}\|_2} d=∥x ∥2x Ty 。
超平面（HYPERPLANES
- 定义：在 R n \mathbb{R}^n Rn空间中，超平面是一个维度为 n − 1 n - 1 n−1的平展子空间。数学上，超平面被形貌为集合 { x ∈ R n : θ 0 + θ T x = 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x = 0\} {x∈Rn:θ0+θTx=0}，此中 θ 0 ∈ R \theta_0 \in \mathbb{R} θ0∈R是一个标量， θ ∈ R n \theta \in \mathbb{R}^n θ∈Rn是一个向量。
- 特征： θ 0 ∈ R \theta_0 \in \mathbb{R} θ0∈R和 θ ∈ R n \theta \in \mathbb{R}^n θ∈Rn共同刻画了超平面。注意，如果 θ 0 = 0 \theta_0 = 0 θ0=0，那么超平面会经过原点。
- 分类特性：超平面将 R n \mathbb{R}^n Rn空间切割成两部分，即 { x ∈ R n : θ 0 + θ T x > 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x > 0\} {x∈Rn:θ0+θTx>0}和 { x ∈ R n : θ 0 + θ T x < 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x < 0\} {x∈Rn:θ0+θTx<0}。这对于分类是一个有用的性质。
示例
- 二维示例：二维空间（ R 2 \mathbb{R}^2 R2）中的超平面，表达式为 { x ∈ R 2 : 1 + 2 x 1 + 3 x 2 = 0 } \{x \in \mathbb{R}^2: 1 + 2x_1 + 3x_2 = 0\} {x∈R2:1+2x1+3x2=0}，但是它是一条直线，所以这里就不放图了，各人想想就行了
- 三维示例：下方图表展示了三维空间（ R 3 \mathbb{R}^3 R3）中的超平面示例，表达式为 { x ∈ R 2 : 1 + 2 x 1 + 3 x 2 + 4 x 3 = 0 } \{x \in \mathbb{R}^2: 1 + 2x_1 + 3x_2 + 4x_3 = 0\} {x∈R2:1+2x1+3x2+4x3=0}，图中呈现一个平面图形。
超平面的法向量
图中标注了两个位于超平面上的点 x 1 x_1 x1和 x 2 x_2 x2，向量 v = x 1 − x 2 v = x_1 - x_2 v=x1−x2是超平面的切线向量。绿色箭头表示超平面的法向量 θ ∥ θ ∥ 2 ∈ R n \frac{\theta}{\|\theta\|_2} \in \mathbb{R}^n ∥θ∥2θ∈Rn，它垂直于超平面。超平面的数学表达式为 { x ∈ R n : θ 0 + θ T x = 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x = 0\} {x∈Rn:θ0+θTx=0}。
回首向量点积公式 x ⋅ y = ∥ x ∥ 2 ∥ y ∥ 2 cos θ x \cdot y = \|x\|_2\|y\|_2 \cos\theta x⋅y=∥x∥2∥y∥2cosθ，如果 x ⋅ y = 0 x \cdot y = 0 x⋅y=0，那么 θ = π 2 \theta = \frac{\pi}{2} θ=2π或 3 π 2 \frac{3\pi}{2} 23π，即向量 x x x和 y y y正交。
- 推导超平面法向量：
- 假设 x 1 x_1 x1和 x 2 x_2 x2位于超平面上，那么向量 v = x 1 − x 2 v = x_1 - x_2 v=x1−x2与超平面相切。
- 因为 x 1 , x 2 ∈ R n x_1, x_2 \in \mathbb{R}^n x1,x2∈Rn位于超平面上，所以对于 i ∈ { 1 , 2 } i \in \{1,2\} i∈{1,2}，有 θ 0 + θ T x i = 0 \theta_0 + \theta^T x_i = 0 θ0+θTxi=0。
- 由此推出 θ T ( x 1 − x 2 ) ∥ θ ∥ 2 = 0 \frac{\theta^T (x_1 - x_2)}{\|\theta\|_2} = 0 ∥θ∥2θT(x1−x2)=0。
- 进而得出 θ ∥ θ ∥ 2 ∈ R n \frac{\theta}{\|\theta\|_2} \in \mathbb{R}^n ∥θ∥2θ∈Rn是超平面的法向量（与超平面外貌正交且为单元向量）。
到超平面的最小距离
在 R n \mathbb{R}^n Rn空间中，一个超平面 { x ∈ R n : θ 0 + θ T x = 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x = 0\} {x∈Rn:θ0+θTx=0}（蓝色直线代表超平面在二维空间的示意），以及空间中的一点 y ∈ R n y \in \mathbb{R}^n y∈Rn（紫色点）。
超平面的法向量为 θ ∥ θ ∥ 2 ∈ R n \frac{\theta}{\|\theta\|_2} \in \mathbb{R}^n ∥θ∥2θ∈Rn（棕色箭头）。从点 y y y到超平面上的点 z ∈ R n z \in \mathbb{R}^n z∈Rn（紫色点）形成向量 y − z ∈ R n y - z \in \mathbb{R}^n y−z∈Rn（绿色箭头），赤色箭头表示点 y y y到超平面的最小距离 d ∈ R d \in \mathbb{R} d∈R。
由此推断：在 R n \mathbb{R}^n Rn空间中，点 y y y到超平面 { x ∈ R n : θ 0 + θ T x = 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x = 0\} {x∈Rn:θ0+θTx=0}的最小距离公式： d = 1 ∥ θ ∥ 2 ( θ 0 + θ T y ) d = \frac{1}{\|\theta\|_2}(\theta_0 + \theta^T y) d=∥θ∥21(θ0+θTy)
证实过程：
- 思量超平面上的任意一点 z ∈ R n z \in \mathbb{R}^n z∈Rn，则有 θ 0 + θ T z = 0 \theta_0 + \theta^T z = 0 θ0+θTz=0。
- 最小距离是毗连点 z z z和 y y y的向量 y − z y - z y−z在法向量 θ ∥ θ ∥ 2 ∈ R n \frac{\theta}{\|\theta\|_2} \in \mathbb{R}^n ∥θ∥2θ∈Rn上的投影。
- 通过内积计算投影，得出 d = ( θ ∥ θ ∥ 2 ) T ( y − z ) = 1 ∥ θ ∥ 2 ( θ 0 + θ T y ) d = (\frac{\theta}{\|\theta\|_2})^T (y - z) = \frac{1}{\|\theta\|_2}(\theta_0 + \theta^T y) d=(∥θ∥2θ)T(y−z)=∥θ∥21(θ0+θTy) 。
数据集与超平面的间隔
在 R n \mathbb{R}^n Rn空间中的一个超平面 { x ∈ R n : θ 0 + θ T x = 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x = 0\} {x∈Rn:θ0+θTx=0}（蓝色直线示意超平面在二维空间的环境），以及五个数据点 x 1 , x 2 , x 3 , x 4 , x 5 ∈ R n x_1, x_2, x_3, x_4, x_5 \in \mathbb{R}^n x1,x2,x3,x4,x5∈Rn（紫色点）。从每个数据点到超平面都有一个最小距离，分别用 d 1 , d 2 , d 3 , d 4 , d 5 d_1, d_2, d_3, d_4, d_5 d1,d2,d3,d4,d5（赤色箭头）表示。
- 距离定义：定义 d i ∈ R d_i \in \mathbb{R} di∈R为点 x i ∈ R n x_i \in \mathbb{R}^n xi∈Rn与超平面之间的最小距离。
- 间隔定义：给定一个超平面和一组点 { x i } i = 1 N \{x_i\}_{i = 1}^N {xi}i=1N，间隔是每个数据点与超平面之间最小距离中的最小值。在左侧图表的环境下，间隔可以计算为 m a r g i n = min { ∣ d i ∣ } = min { ∣ 1 ∥ θ ∥ 2 ( θ 0 + θ T x i ) ∣ } margin = \min\{|d_i|\} = \min\left\{\left|\frac{1}{\|\theta\|_2}(\theta_0 + \theta^T x_i)\right|\right\} margin=min{∣di∣}=min{ ∥θ∥21(θ0+θTxi) } 。
- 距离取值分析： d i d_i di可以取正值或负值，这取决于 θ 0 + θ T x i \theta_0 + \theta^T x_i θ0+θTxi的符号，即数据点位于超平面的哪一侧。
数据集与超平面的最大间隔
上图展示了一个超平面 { x ∈ R n : θ 0 + θ T x = 0 } \{x \in \mathbb{R}^n: \theta_0 + \theta^T x = 0\} {x∈Rn:θ0+θTx=0}（蓝色直线示意其在二维空间的情形），以及五个带标签的数据点 x 1 , x 2 , x 3 , x 4 , x 5 ∈ R n x_1, x_2, x_3, x_4, x_5 \in \mathbb{R}^n x1,x2,x3,x4,x5∈Rn。
此中， y 1 = + 1 y_1 = +1 y1=+1， y 2 = + 1 y_2 = +1 y2=+1， y 3 = + 1 y_3 = +1 y3=+1（紫色点）， y 4 = − 1 y_4 = -1 y4=−1， y 5 = − 1 y_5 = -1 y5=−1（绿色点）。从每个数据点到超平面都有一个距离，分别用 d 1 , d 2 , d 3 , d 4 , d 5 d_1, d_2, d_3, d_4, d_5 d1,d2,d3,d4,d5（赤色箭头）表示。
假设数据点被标记为两类 y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi∈{−1,+1}。为了使超平面正确分类数据点，要求当 y i = + 1 y_i = +1 yi=+1时， θ 0 + θ T x i > 0 \theta_0 + \theta^T x_i > 0 θ0+θTxi>0；当 y i = − 1 y_i = -1 yi=−1时， θ 0 + θ T x i < 0 \theta_0 + \theta^T x_i < 0 θ0+θTxi<0。这个条件可以简化为 y i ( θ 0 + θ T x i ) > 0 y_i(\theta_0 + \theta^T x_i) > 0 yi(θ0+θTxi)>0，进一步修改为 y i d i = y i ∥ θ ∥ 2 ( θ 0 + θ T x i ) > 0 y_id_i = \frac{y_i}{\|\theta\|_2}(\theta_0 + \theta^T x_i) > 0 yidi=∥θ∥2yi(θ0+θTxi)>0。
我们希望找到一个既能正确分类数据点，又具有最大间隔的超平面。因此，必要求解一个优化问题：在约束条件 y i ∥ θ ∥ 2 ( θ 0 + θ T x i ) ≥ M \frac{y_i}{\|\theta\|_2}(\theta_0 + \theta^T x_i) \geq M ∥θ∥2yi(θ0+θTxi)≥M（对于 i ∈ { 1 , … , N } i \in \{1, \ldots, N\} i∈{1,…,N}）下，最大化 M M M，此中 M M M代表间隔。
进一步简化最大间隔问题
- 目的是在参数 θ 0 \theta_0 θ0和 θ \theta θ上最大化 M M M(公式表示： max θ 0 , θ M \max_{\theta_0,\theta} M maxθ0,θM)。
- 约束条件为 y i ∥ θ ∥ 2 ( θ 0 + θ T x i ) ≥ M \frac{y_i}{\|\theta\|_2}(\theta_0 + \theta^T x_i) \geq M ∥θ∥2yi(θ0+θTxi)≥M，此中 i ∈ { 1 , … , N } i \in \{1, \ldots, N\} i∈{1,…,N}。这里 y i y_i yi是数据点 x i x_i xi的标签，取值为 { − 1 , + 1 } \{-1, +1\} {−1,+1}， N N N是数据点的数目。
简化的依据：
- 如果 θ 0 + θ T x = 0 \theta_0 + \theta^T x = 0 θ0+θTx=0定义了一个超平面，那么对于任意 γ ≠ 0 \gamma \neq 0 γ=0， γ ( θ 0 + θ T x ) = 0 \gamma(\theta_0 + \theta^T x) = 0 γ(θ0+θTx)=0也定义同一个超平面。
- 基于此，不失一样寻常性，可以设置 ∥ θ ∥ 2 = 1 \|\theta\|_2 = 1 ∥θ∥2=1（因为 ∥ θ ∥ 2 \|\theta\|_2 ∥θ∥2是一个标量相称于上面 γ \gamma γ中的一部分）。
简化后的最大间隔问题：
- 目的依然是在参数 θ 0 \theta_0 θ0和 θ \theta θ上最大化 M M M。
- 约束条件变为 ∥ θ ∥ 2 2 = 1 \|\theta\|_2^2 = 1 ∥θ∥22=1以及 y i ( θ 0 + θ T x i ) ≥ M y_i(\theta_0 + \theta^T x_i) \geq M yi(θ0+θTxi)≥M，此中 i ∈ { 1 , … , N } i \in \{1, \ldots, N\} i∈{1,…,N}。
感知机（PERCEPTRON）
上方展示了感知机的布局示意图：
- 最左边是表示数据点的输入节点，标记为 x 1 , ⋯ , x N x_1, \cdots, x_N x1,⋯,xN。
- 中间是权重节点，标记为 w 1 , ⋯ , w 1 w_1, \cdots, w_1 w1,⋯,w1，每个输入 x i x_i xi都毗连到对应的权重 w i w_i wi。
- 权重节点的输出汇总到一个求和节点（Sum）。
- 求和节点的输出进入一个阶跃/符号函数（Step/sign function）模块，终极产生输出（Output）。
- 感知机是一个形如 f ( x ) = s g n ( w T x ) f(x) = sgn(w^T x) f(x)=sgn(wTx)的函数。显然，感知机形貌了超平面的分类规则。此中， s g n sgn sgn是符号函数， w T x w^T x wTx是权重向量 w w w和输入向量 x x x的内积。
- 感知机的灵感来自生物学。大脑中的神经元之间存在毗连，如果通过这些毗连的输入总和凌驾某个阈值，神经元就会从激活状态转变为非激活状态（或反之）。
感知机学习算法
为了符号表示的方便，通过在数据中添加一行1来吸取 θ 0 \theta_0 θ0，并定义 w : = ( θ 0 θ ) w := \begin{pmatrix} \theta_0 \\ \theta \end{pmatrix} w:=(θ0θ)。此时分类模型为 f ( x ) = s g n ( w T x ) f(x) = sgn(w^T x) f(x)=sgn(wTx)，这个模型通常被称为感知机。
感知机学习算法的流程：
- 初始化：对于数据集 D = ( x i , y i ) i = 1 N D = (x_i, y_i)_{i = 1}^N D=(xi,yi)i=1N，此中 y i ∈ { − 1 , 1 } y_i \in \{-1, 1\} yi∈{−1,1}。将 w 0 w_0 w0初始化为 c ∈ R n + 1 c \in \mathbb{R}^{n + 1} c∈Rn+1，可以是随机值或选择为0向量。
- 循环条件：当误差（error）大于0时，实行循环。
- 样本遍历：对于数据集中的每个样本 i ∈ { 1 , … , N } i \in \{1, \ldots, N\} i∈{1,…,N} ：
- 计算 y ^ i : = s g n ( w T x i ) \hat{y}_i := sgn(w^T x_i) y^i:=sgn(wTxi)。
- 判断与更新：如果 y i ≠ y ^ i y_i \neq \hat{y}_i yi=y^i（即预测错误，只有当模型出现错误时才更新参数。），则 w i + 1 = w i + r y i x i w_{i + 1} = w_i + r y_i x_i wi+1=wi+ryixi；否则 w i + 1 = w i w_{i + 1} = w_i wi+1=wi。（这里 r ∈ ( 0 , 1 ] r \in (0, 1] r∈(0,1]是学习参数，通常设置为 r = 1 r = 1 r=1）
- 更新误差：计算误差 e r r o r = max i ∣ y i − y ^ i ∣ error = \max_i |y_i - \hat{y}_i| error=maxi∣yi−y^i∣。
支持向量
展示了一个二维平面（示意 R n \mathbb{R}^n Rn空间），此中有：
- 一个超平面（绿色直线），其法向量为 θ ∈ R n \theta \in \mathbb{R}^n θ∈Rn（绿色箭头）。
- 两类数据点，蓝色点和棕色点，此中标记为“S”的数据点是支持向量。
- 超平面两侧与超平面距离为 γ \gamma γ的地区表示间隔（Margin），用浅棕色阴影表示。从超平面到支持向量的距离用紫色虚线箭头标注为 γ \gamma γ。
- 支持向量的定义：假设我们已经找到了具有最大间隔 γ > 0 \gamma > 0 γ>0且能正确分类所有点的超平面。支持向量是与超平面距离为 γ > 0 \gamma > 0 γ>0的数据点。对于 x ∈ R n x \in \mathbb{R}^n x∈Rn，如果 ∣ 1 ∥ θ ∥ 2 ( θ 0 + θ T x ) ∣ = γ \left|\frac{1}{\|\theta\|_2}(\theta_0 + \theta^T x)\right| = \gamma ∥θ∥21(θ0+θTx) =γ，则 x x x是一个支持向量。
- 支持向量的特性：支持向量完全刻画了具有最大间隔的超平面。改变非支持向量的位置对最优超平面没有影响。
线性不可分数据集
- 线性可分示例：左上方图表展示了一个线性可分数据集的例子，蓝色点代表“Class 1”（类别1），棕色点代表“Class 2”（类别2），存在一条玄色直线能够将两类数据点完全分开。
- 线性不可分示例：右上方图表展示了一个线性不可分数据集的例子，同样是蓝色点代表“Class 1”，棕色点代表“Class 2”，但从图中可见，不存在一条直线能将两类数据点完全分开。
- 线性可分定义：给定一个数据集 D : = { ( x i , y i ) } i = 1 N \mathcal{D} := \{(x_i, y_i)\}_{i = 1}^N D:={(xi,yi)}i=1N，如果存在 θ ∈ R n + 1 \theta \in \mathbb{R}^{n + 1} θ∈Rn+1，使得当 y i = + 1 y_i = +1 yi=+1时， θ 0 + θ T x i > 0 \theta_0 + \theta^T x_i > 0 θ0+θTxi>0；当 y i = − 1 y_i = -1 yi=−1时， θ 0 + θ T x i < 0 \theta_0 + \theta^T x_i < 0 θ0+θTxi<0，则该数据集是线性可分的。
- 感知机算法与线性可分的关系：如果数据是线性可分的，那么可以证实感知机算法将收敛到一个能够正确分类数据的超平面。
不可分环境
线性不可分有两种环境，以下是第一种：
优化问题：
- 目的是在参数 θ 0 \theta_0 θ0和 θ \theta θ上最大化 M M M。
- 约束条件包罗： ∥ θ ∥ 2 2 = 1 \|\theta\|_2^2 = 1 ∥θ∥22=1； y i ( θ 0 + θ T x i ) ≥ M ( 1 − ϵ i ) y_i(\theta_0 + \theta^T x_i) \geq M(1 - \epsilon_i) yi(θ0+θTxi)≥M(1−ϵi)，对于 i ∈ { 1 , … , N } i \in \{1, \ldots, N\} i∈{1,…,N}； ϵ i ≥ 0 \epsilon_i \geq 0 ϵi≥0且 ∑ i = 1 N ϵ i ≤ C \sum_{i = 1}^{N} \epsilon_i \leq C ∑i=1Nϵi≤C。
- 这里 y i y_i yi是数据点 x i x_i xi的标签， ϵ i \epsilon_i ϵi是松懈变量， C C C是一个调节参数。我们可以选择它来控制间隔违反和误分类的水平。
松懈变量 ϵ i \epsilon_i ϵi分析：
- 当 ϵ i = 0 \epsilon_i = 0 ϵi=0时，数据点 x i x_i xi在间隔之外。
- 当 ϵ i ≥ 0 \epsilon_i \geq 0 ϵi≥0时，数据点 x i x_i xi违反了间隔条件。
- 当 ϵ i ≥ 1 \epsilon_i \geq 1 ϵi≥1时，数据点 x i x_i xi被误分类。
线性不可分第二种：非线性决策边界
优化问题照旧在参数 θ 0 \theta_0 θ0和 θ \theta θ上最大化 M M M。
约束条件： ∥ θ ∥ 2 2 = 1 , y i ( θ 0 + θ T Φ ( x i ) ) ≥ M ( 1 − ϵ i ) , 对于 i ∈ { 1 , … , N } , ϵ i ≥ 0 且 ∑ i = 1 N ϵ i ≤ C \|\theta\|_2^2 = 1,y_i(\theta_0 + \theta^T \Phi(x_i)) \geq M(1 - \epsilon_i),\text{对于}i \in \{1, \ldots, N\},\epsilon_i \geq 0\text{且}\sum_{i = 1}^{N} \epsilon_i \leq C ∥θ∥22=1,yi(θ0+θTΦ(xi))≥M(1−ϵi),对于i∈{1,…,N},ϵi≥0且i=1∑Nϵi≤C
表明 Φ ( x ) \Phi(x) Φ(x)： Φ ( x ) : = [ ϕ 1 ( x ) , … , ϕ m ( x ) ] T \Phi(x) := [\phi_1(x), \ldots, \phi_m(x)]^T Φ(x):=[ϕ1(x),…,ϕm(x)]T，此中 { ϕ k ( x ) } k = 1 m \{\phi_k(x)\}_{k = 1}^{m} {ϕk(x)}k=1m是一组基函数。比方，多项式基函数 ϕ k ( x ) = x k \phi_k(x) = x^k ϕk(x)=xk。
对于这种环境，我们将原始状态空间 x ∈ R n x \in \mathbb{R}^n x∈Rn扩展为 z = Φ ( x ) ∈ R m z = \Phi(x) \in \mathbb{R}^m z=Φ(x)∈Rm。以求在更高维度中求解最优分离超平面，并将决策边界投影回原始维度。可以通过添加更多基函数，类似于在线性回归中的做法，能够捕获非线性的真实模型。
可视化高维增强状态如下图：
支持向量机
- 非线性基函数扩展：使用非线性基函数 Φ ( x ) : = [ ϕ 1 ( x ) , … , ϕ m ( x ) ] T ∈ R m \Phi(x): = [\phi_1(x), \ldots, \phi_m(x)]^T \in \mathbb{R}^m Φ(x):=[ϕ1(x),…,ϕm(x)]T∈Rm 来扩展动态，这会将分类问题的参数（决策变量）维度从 R n \mathbb{R}^n Rn增加到 R m \mathbb{R}^m Rm，此中 m > n m > n m>n。
- 维度增加的影响：一样寻常来说，增加决策变量的维度会使优化问题在计算上更难求解。
- 支持向量机的引入：在20世纪90年代，一种名为支持向量机（SVMs）的新方法被引入，它可以在不产生如此高计算本钱的环境下提供非线性分类决策边界。
- 支持向量机的模型情势：SVMs拟合的分类模型情势为 f ( x ; θ ) = θ 0 + ∑ i ∈ S θ i K ( x , x i ) f(x; \theta) = \theta_0 + \sum_{i \in S} \theta_i K(x, x_i) f(x;θ)=θ0+∑i∈SθiK(x,xi)，此中 S = { 支持向量的索引 } S = \{支持向量的索引\} S={支持向量的索引}， K : R n × R n → R K: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R} K:Rn×Rn→R 是提供距离度量的核函数（kernel functions）。所以在SVM模型中，只有支持向量决定分类，这涉及的参数要少得多。
核函数（kernel functions）是用于度量两个向量之间的距离。以下是三种常见核函数的表达式：
- 线性核函数（Linear Kernel）： K ( x , y ) = x T y K(x, y) = x^T y K(x,y)=xTy。
- 多项式核函数（Polynomial Kernel）： K ( x , y ) = ( 1 + x T y ) d K(x, y) = (1 + x^T y)^d K(x,y)=(1+xTy)d，此中 d d d是多项式的次数。
- 径向基核函数（Radial Kernel）： K ( x , y ) = exp ( − γ ∥ x − y ∥ 2 2 ) K(x, y) = \exp (-\gamma \|x - y\|_2^2) K(x,y)=exp(−γ∥x−y∥22)，此中 γ \gamma γ是超参数。
相识支持向量机的具体细节超出了本课程的范围，只必要大概知道就行了。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
