织梦通用企业网站模板,咸阳网站建设,网页版微信怎么退出,在线磁力搜索神器data modeling and machine intelligence - FURTHER CLASSIFICATION 混淆矩阵评估指标#xff1a;灵敏度和特异度ROC 曲线文字说明部分 AUC#xff1a;ROC曲线下面积 支持向量机思路补充背景知识点积超平面#xff08;HYPERPLANES超平面的法向量到超平面的最小距离数据集与超… data modeling and machine intelligence - FURTHER CLASSIFICATION 混淆矩阵评估指标灵敏度和特异度ROC 曲线文字说明部分 AUCROC曲线下面积 支持向量机思路补充背景知识点积超平面HYPERPLANES超平面的法向量到超平面的最小距离数据集与超平面的间隔数据集与超平面的最大间隔进一步简化最大间隔问题 感知机PERCEPTRON感知机学习算法支持向量线性不可分数据集不可分情况 支持向量机 本节目标 能够计算模型的灵敏度和特异度。能够构建混淆矩阵。知道如何使用ROC曲线分析分类模型的性能。能够阐述由正确分类所有数据点且具有最大间隔的超平面所解决的优化问题。能够使用感知机算法计算分离超平面。能够向最大间隔问题中引入松弛变量以允许分类错误。对构建具有非线性边界条件的最大间隔问题有一定的见解。
回顾分类问题 上一节我们使用逻辑回归logistic regression计算标签出现的概率接下来会使用这些概率并通过 “阈值”thresholds来对标签进行预测。
阈值
在某些应用中需要做出预测而不仅仅是估计标签的概率。将条件概率 P ( y l ∣ x 0 ) \mathbb{P}(y l|x_0) P(yl∣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(yl∣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(yl∣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(y1∣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(y1∣x0)0.7otherwise 二分类问题中不同的阈值会导致产生不同的分类模型分析如下
二分类的混淆矩阵
行表示真实数据的标签 y t r u e 1 y_{true}1 ytrue1 和 y t r u e 0 y_{true}0 ytrue0 。列表示模型预测的标签 y ^ 1 \hat{y}1 y^1 和 y ^ 0 \hat{y}0 y^0 。当 y t r u e 1 y_{true}1 ytrue1 且 y ^ 1 \hat{y}1 y^1 时对应单元格内容为“# model correctly predicts positive label.”模型正确预测正标签的数量当 y t r u e 1 y_{true}1 ytrue1 且 y ^ 0 \hat{y}0 y^0 时对应单元格内容为“# model incorrectly predicts negative label.”模型错误预测负标签的数量。当 y t r u e 0 y_{true}0 ytrue0 且 y ^ 1 \hat{y}1 y^1 时对应单元格内容为“# model incorrectly predicts positive label.”模型错误预测正标签的数量当 y t r u e 0 y_{true}0 ytrue0 且 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 RateTPR。其计算公式为 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}} TPRSensitivity# truly positive data#model correctly predicts positive label 即模型正确预测为正标签的数量除以真实正例数据的数量。特异度是正确识别出的真实负例的百分比也称为真负率True Negative RateTNR。其计算公式为 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}} TNRSpecificity# 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\% 67742677719677≈0.94294.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}{75040}1 100\% 7504075041100%。
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\% 339338339677339≈0.50150.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\% 750421750475257504≈0.99799.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 TPR1且假正率 F P R 0 FPR 0 FPR0的分类器。
横轴为假正率FPR纵轴为真正率TPR。图中有一条从原点 ( 0 , 0 ) (0, 0) (0,0)到点 ( 1 , 1 ) (1, 1) (1,1)的虚线代表随机分类器的性能。即随机分类器的情况下真正率和假正率是相等的。图中有两条曲线紫色和绿色代表不同分类模型的ROC曲线。越靠近左上角 T P R 1 TPR 1 TPR1 F P R 0 FPR 0 FPR0的曲线对应的分类模型性能越好图中箭头指向“Better models”更好的模型表明朝着这个方向的模型性能更优。
AUCROC曲线下面积 图表横轴为假正率FPR纵轴为真正率TPR。图中有一条紫色曲线代表某个分类器的ROC曲线。还有一条红色折线意为理论最优分类。红色折线下方的区域用蓝色斜线填充该区域面积即为AUC,ROC曲线下面积。
AUC即ROC曲线下面积为分类器在所有阈值下的性能提供了一个度量指标。
- 理论上最好的分类器的AUC为1。
- 存在一个阈值$T0$此时真正率$TPR 1$所有真正例数据点都被预测为正类且假正率$FPR 0$所有真负例数据点都被预测为负类。
- 当把阈值降低到$T 0$时所有情况都被预测为正类所以曲线必须经过点$(FPR, TPR)(1, 1)$。支持向量机
思路
分离数据点 到目前为止我们把基于数据进行预测的问题当作一个函数拟合问题即尝试学习 y f ( x ) y f(x) yf(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θTx0}其中 θ 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 θ00那么超平面会经过原点。分类特性超平面将 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θTx0}和 { x ∈ R n : θ 0 θ T x 0 } \{x \in \mathbb{R}^n: \theta_0 \theta^T x 0\} {x∈Rn:θ0θTx0}。这对于分类是一个有用的性质。
示例
二维示例二维空间 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:12x13x20}但是它是一条直线所以这里就不放图了大家想想就行了三维示例下方图表展示了三维空间 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:12x13x24x30}图中呈现一个平面图形。
超平面的法向量 图中标注了两个位于超平面上的点 x 1 x_1 x1和 x 2 x_2 x2向量 v x 1 − x 2 v x_1 - x_2 vx1−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θTx0}。
回顾向量点积公式 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⋅y0那么 θ π 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 vx1−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θTxi0。由此推出 θ 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θTx0}蓝色直线代表超平面在二维空间的示意以及空间中的一点 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θTx0}的最小距离公式 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θTz0。 - 最小距离是连接点 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θTx0}蓝色直线示意超平面在二维空间的情况以及五个数据点 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}i1N间隔是每个数据点与超平面之间最小距离中的最小值。在左侧图表的情况下间隔可以计算为 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\} marginmin{∣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θTx0}蓝色直线示意其在二维空间的情形以及五个带标签的数据点 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 y11 y 2 1 y_2 1 y21 y 3 1 y_3 1 y31紫色点 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 yi1时 θ 0 θ T x i 0 \theta_0 \theta^T x_i 0 θ0θTxi0当 y i − 1 y_i -1 yi−1时 θ 0 θ T x i 0 \theta_0 \theta^T x_i 0 θ0θTxi0。这个条件可以简化为 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θTx0定义了一个超平面那么对于任意 γ ≠ 0 \gamma \neq 0 γ0 γ ( θ 0 θ T x ) 0 \gamma(\theta_0 \theta^T x) 0 γ(θ0θTx)0也定义同一个超平面。基于此不失一般性可以设置 ∥ θ ∥ 2 1 \|\theta\|_2 1 ∥θ∥21因为 ∥ θ ∥ 2 \|\theta\|_2 ∥θ∥2是一个标量相当于上面 γ \gamma γ中的一部分。
简化后的最大间隔问题
目标依然是在参数 θ 0 \theta_0 θ0和 θ \theta θ上最大化 M M M。约束条件变为 ∥ θ ∥ 2 2 1 \|\theta\|_2^2 1 ∥θ∥221以及 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)i1N其中 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∈Rn1可以是随机值或选择为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 yiy^i即预测错误只有当模型出现错误时才更新参数。则 w i 1 w i r y i x i w_{i 1} w_i r y_i x_i wi1wiryixi否则 w i 1 w i w_{i 1} w_i wi1wi。这里 r ∈ ( 0 , 1 ] r \in (0, 1] r∈(0,1]是学习参数通常设置为 r 1 r 1 r1 更新误差计算误差 e r r o r max i ∣ y i − y ^ i ∣ error \max_i |y_i - \hat{y}_i| errormaxi∣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)}i1N如果存在 θ ∈ R n 1 \theta \in \mathbb{R}^{n 1} θ∈Rn1使得当 y i 1 y_i 1 yi1时 θ 0 θ T x i 0 \theta_0 \theta^T x_i 0 θ0θTxi0当 y i − 1 y_i -1 yi−1时 θ 0 θ T x i 0 \theta_0 \theta^T x_i 0 θ0θTxi0则该数据集是线性可分的。 感知机算法与线性可分的关系如果数据是线性可分的那么可以证明感知机算法将收敛到一个能够正确分类数据的超平面。
不可分情况
线性不可分有两种情况以下是第一种
优化问题
目标是在参数 θ 0 \theta_0 θ0和 θ \theta θ上最大化 M M M。约束条件包括 ∥ θ ∥ 2 2 1 \|\theta\|_2^2 1 ∥θ∥221 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 ∑i1Nϵ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 ϵi0时数据点 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 ∥θ∥221,yi(θ0θTΦ(xi))≥M(1−ϵi),对于i∈{1,…,N},ϵi≥0且i1∑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)}k1m是一组基函数。例如多项式基函数 ϕ 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 mn。维度增加的影响一般来说增加决策变量的维度会使优化问题在计算上更难求解。支持向量机的引入在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)(1xTy)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 γ是超参数。
了解支持向量机的具体细节超出了本课程的范围只需要大概知道就行了。
