计算机科学与技术 开题报告 网站建设,如何实现输入域名访问网站首页,安徽水安建设集团网站,南昌百度快速排名提升继续是机器学习课程的笔记#xff0c;这节课的内容是介绍支持向量机#xff08;SVM#xff09;的内容。SVM是一个非常强大且流行的算法#xff0c;在一些情况下#xff0c;面对一些复杂的非线性问题可以提供比逻辑回归或神经网络更加简洁更加有效的结果。
优化目标
首先…继续是机器学习课程的笔记这节课的内容是介绍支持向量机SVM的内容。SVM是一个非常强大且流行的算法在一些情况下面对一些复杂的非线性问题可以提供比逻辑回归或神经网络更加简洁更加有效的结果。
优化目标
首先是以逻辑回归为例展开讨论逻辑回归的模型是hθ(x)11e−θTxh_\theta(x)=\frac{1}{1+e^{-\theta^Tx}},这里分y1y=1和y0y=0两种情况讨论
y1y=1时希望假设的hθ(x)≈1h_\theta(x) \approx 1,也就是令zθTx≫0z=\theta^Tx \gg 0y0y=0时希望假设的hθ(x)≈0h_\theta(x) \approx 0,也就是令zθTx≪0z=\theta^Tx \ll 0
从代价函数来看逻辑回归的代价函数如下所示
J(θ)−1m[∑i1my(i)loghθ(x(i))(1−y(i)log(1−hθ(x(i)))]J(\theta) = -\frac{1}{m} [\sum_{i=1}^my^{(i)}logh_\theta(x^{(i)})+(1-y^{(i)}log(1-h_\theta(x^{(i)}))]对于任意训练集中的一个实例对总的代价的影响为 −(yloghθ(x)(1−y)log(1−hθ(x)))−ylog11e−θTx−(1−y)log(1−11e−θTx)-(ylogh_\theta(x)+(1-y)log(1-h_\theta(x))) \\
= -ylog\frac{1}{1+e^{-\theta^Tx}}-(1-y)log(1-\frac{1}{1+e^{-\theta^Tx}})为了让每个实例造成的代价都尽可能地小这里也说分y1y=1和y0y=0两种情况讨论如下图所示最佳的情况是代价为0但由下图中曲线可以看出代价始终会存在且不为0。 而在SVM中我们将曲线的代价函数转变成由两条线段构成的折线如下图所示
y1y=1时希望构建的新代价函数如cost1(z)cost_1(z)所示当z≥1z \ge 1时cost1(z)0cost_1(z)=0y0y=0时希望构建的新代价函数如cost0(z)cost_0(z)所示当z≤−1z \le -1时cost0(z)0cost_0(z)=0 用两个新构建的代价函数替换原来逻辑回归的代价函数得到
1m[∑i1my(i)cost1(z)(1−y(i))cost0(z)]λ2m∑j1nθ2j\frac{1}{m} [\sum_{i=1}^my^{(i)}cost_1(z)+(1-y^{(i)})cost_0(z)]+\frac{\lambda}{2m}\sum_{j=1}^{n} \theta_j^2这里对上面的代价函数作如下调整
因为1m\frac{1}{m}实际上不影响最优化的结构将其去掉因为归一化参数λ\lambda控制的是归一化这一项在整个代价函数中占的比例对于SVM我们想要控制的新构建的代价函数部分因此我们去掉λ\lambda的同时给第一项乘以一个常数C相当于我们将整个代价函数除以了λ\lambda且C1λC=\frac{1}{\lambda}
我们依旧是希望能找出使得该代价函数最小的参数。注意调整后的代价函数是一个凸函数而非之前逻辑回归那样的非凸函数这意味着求解的过程中不会陷入局部最小值而错过全局最小值的情况修改后的代价函数如下
minθC∑i1m[y(i)cost1(θTx(i))(1−y(i))cost0(θTx(i))]12∑j1nθ2jmin_\theta C \sum_{i=1}^m [y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum_{j=1}^{n} \theta_j^2最后给出SVM的假设为
hθ(x){1if θTx≥00if θTx0h_\theta(x) =
\begin{cases}
1\quad if\ \theta^Tx \ge 0 \\
0\quad if\ \theta^Tx \lt 0
\end{cases}注意这里给出的假设在预测时是以z与0的大小关系作为依据的但是在训练函数时我们是以正负1为依据的这是SVM与逻辑回归的一个关键区别且导致了后面将介绍的支持向量机的特性。
支持向量机的判定边界
SVM有的时候也被称为最大间隔分类器(Large Margin Classifer)其原因是SVM可以尝试发现一个与样本数据集之间有着最大间隔的判定边界。
上一小节得到了SVM的代价函数表达式并且其跟逻辑回归的区别是新构建了两个函数cost1(z)和cost0(z)cost_1(z)和cost_0(z)其图像分别如下所示 由此可以得知,为了最小化代价函数
y1y=1时希望z≥1z \ge 1时即θTx≥1\theta^Tx \ge 1y0y=0时希望z≤−1z \le -1时即θTx≤−1\theta^Tx \le -1
下图是一个可以用直线来区分的分类问题实例图中绿色和红色的两条线代表作两条逻辑回归的判定边界而黑色的线代表的则是SVM的判定边界从图上可以看出黑色的线似乎是更加合理蓝色的两条线代表的是SVM的判定边界与样本数据之间的间隔从这幅图也可以看出SVM被称为最大间隔分类器的原因。 接下来是考虑下在SVM中归一化常数C的作用。
假设选择的C是一个非常大的值那么在最小化代价函数的过程中我们希望找出在y1y=1和y0y=0两种情况下都使得代价函数中第一项尽量为0的参数如果我们找到这样的参数则我们的最小化问题便转变成
min12∑j1nθ2js.t{θTx(i)≥1 if y(i)1θTx(i)≤−1 if y(i)0min \frac{1}{2}\sum_{j=1}^n \theta_j^2\quad s.t
\begin{cases}
\theta^Tx^{(i)} \ge 1\ \quad if\ y^{(i)}=1 \\
\theta^Tx^{(i)} \le -1\ \ if\ y^{(i)}=0
\end{cases}在这种情况下我们得出的SVM判定边界就是上面黑线那样具有尝试使得判定边界与样本数据间间隔最大的特性。但是使得判断边界与样本数据之间间隔最大并总是好事假设我们的数据集如下图所示 也就是在数据集中间有一个较为明显的异常值即图中左侧在圆圈处下方的红色叉数据此时如果选择较大的常数C会得到图中红色的直线这样并非很合理但如果选择较小的C可能会得到图中黑色直线所示的判定边界。也就是说C值越小SVM对异常值越不敏感。
回顾C1λC=\frac{1}{\lambda},有
C较大时相当于λ\lambda较小可能会导致过拟合高偏倚C较小时相当于λ\lambda较大可能会导致低拟合高偏差
核函数
接下来是介绍如何修改SVM算法来解决一些非线性分类的问题。
首先是回顾之前讨论的一个使用高次的多项式模型来解决的一个无法用直线进行分类的问题其样本集如下图所示 为了获得上图所示的判定边界使用的模型可能是θ0θ1x1θ2x2θ3x1x2θ4x21θ5x22⋯\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_1x_2+\theta_4x_1^2+\theta_5x_2^2+\cdots的形式。
这里使用一系列新的特征ff来替换模型中的每一项，如令：f1=x1,f2=x2,f3=x1x2,f4=x21,f5=x22,…f_1=x_1,f_2=x_2,f_3=x_1x_2,f_4=x_1^2,f_5=x_2^2,\ldots,那么得到新的模型形式为hθ(x)θ0θ1f1θ2f2…θnfnh_\theta(x)=\theta_0+\theta_1 f_1+\theta_2 f_2+\ldots+\theta_n f_n。但除了对原有的特征进行组合外能否有更好的办法来构造新的特征f1,f2,f3f_1,f_2,f_3。
使用核函数计算出新的特征
给定一个训练实例x可以利用x的各个特征与预先选定的地标(landmarks)l(1),l(2),l(3)l^{(1)},l^{(2)},l^{(3)}的近似程度来选取新的特征f1,f2,f3f_1,f_2,f_3。如下图所示 这里可以使用如相似度函数来计算新的特征如令f1similarity(x,l(1))exp(−||x−l(1)||22σ2)f_1 = similarity(x,l^{(1)})=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2}),其中||x−l(1)||2∑nj1(xj−l(1)j)2||x-l^{(1)}||^2=\sum_{j=1}^n(x_j-l_j^{(1)})^2表示实例x中所有的特征与地标l(1)l^{(1)}之间的距离的和。
这里的相似度函数similarity(x,l(1))similarity(x,l^{(1)})就是核函数实质上这就是一个高斯核函数注意这个函数与正态分布没有什么实际上的关系只是看上去像而已。
这些地标的作用是什么呢如果一个训练实例x与地标L之间的距离近似于0则新特征f近似于e−01e^{-0}=1;而如果x与L之间距离非常远则f近似于0。
这里假设训练实例含有两个特征[x1,x2][x_1,x_2]给定地标l(1)l^{(1)}与不同的σ\sigma如下图所示: 上图中水平面的坐标为x1,x2x_1,x_2垂直坐标代表f。可以看出只有当x与l(1)l^{(1)} 重合时f才具有最大值随着x的改变f值改变的速率受到σ2\sigma^2的控制。
下图是另外一个例子图中有3个地标模型hθ(x)θ0θ1f1θ2f2θ1f3h_\theta(x)=\theta_0+\theta_1f_1+\theta_2 f_2+\theta_1 f_3,令θ0−0.5,θ1θ21,θ30\theta_0=-0.5,\theta_1=\theta_2=1,\theta_3=0当实例处于红色的点位置时因为离l(1)l^{(1)}更近但是离l(2)和l(3)l^{(2)}和l^{(3)}较远,则有f1≈1,f2f3≈0f_1 \approx 1, f_2 = f_3 \approx 0,因此hθ(x)≥1h_\theta(x) \ge 1预测y1y=1。同理可以求出对于离l(2)l^{(2)}较近的绿色点也预测y1y=1但对于青蓝色的点距离三个点都比较远所以预测y0y=0从而可以得到图中红色的封闭曲线的范围内都是预测y1y=1而曲线外部就是预测y0y=0。
因此在预测的时候我们采用的特征不是训练实例本身的特征而是通过核函数计算出的新特征f1,f2,f3f_1,f_2,f_3。
选择地标
一般是根据训练集的数量来选择地标的数量即如果训练集有m个实例则选择m个地标并且令l(1)x(1),l(2)x(2),…,l(m)x(m)l^{(1)}=x^{(1)},l^{(2)}=x^{(2)},\ldots,l^{(m)}=x^{(m)}。这样做的好处是得到的新特征是建立在原有特征与训练集中所有其他特征之间的距离的基础之上的即 下面将核函数应用到SVM到修改SVM的假设为 给定x计算新特征f当θTf≥0\theta^Tf \ge 0时预测y1y=1,否则反之。
相应地修改代价函数为minθC∑mi1[y(i)cost1(θTf(i))(1−y(i))cost0(θTf(i))]12∑nmj1θ2jmin_\theta C \sum_{i=1}^m [y^{(i)}cost_1(\theta^Tf^{(i)})+(1-y^{(i)})cost_0(\theta^Tf^{(i)})]+\frac{1}{2}\sum_{j=1}^{n=m} \theta_j^2
而在具体实施过程中对最后一项需要做点调整计算∑nmj1θ2jθTθ\sum_{j=1}^{n=m} \theta_j^2=\theta^T\theta时使用θTMθ\theta^TM\theta代替θTθ\theta^T\theta其中MM是根据选择的核函数而不同的一个矩阵，这样做的原因是为了简化运算。理论上讲，我们也可以在逻辑回归中使用核函数，但是上面使用MM来简化计算的方法不适合逻辑回归计算会非常耗费时间。
这里不介绍最小化SVM的代价函数的方法可以使用现有的软件包如liblinearlibsvm等。在使用这些软件包最小化我们的代价函数的时候通常需要编写核函数并且如果我们使用高斯核函数在使用前进行特征缩放是非常必要的。
另外SVM也可以不用核函数不使用核函数又称为线性核函数当不采用非常复杂的函数或者训练集特征非常多而实例非常少的时候可以使用这种不带核函数的SVM。
下面是SVM的两个参数C和σC和\sigma的影响
C较大时相当于λ\lambda较小可能会导致过拟合高偏倚C较小时相当于λ\lambda较大可能会导致低拟合高偏差σ\sigma较大时特征f会比较平滑导致低拟合高偏差σ\sigma较小时特征f会相对没有那么平滑导致过拟合高偏倚
在高斯核函数外还有其他一些核函数如
多项式核函数(Polynomial Kernel)字符串核函数(String Kernel)卡方核函数(chi-square kernel)直方图交集核函数(histogram intersection kernel)etc…
这些核函数的模板也都是根据训练集和地标之间的距离来构建新的特征这些核函数需要满足Mercer’s定理才能被SVM的优化软件正确处理。
多类分类
在之前的逻辑回归这节课中曾接受一对多的方法来解决一个多类分类问题。即如果一共有k个类则需要使用k个模型以及k个参数向量θ\theta。
同样地我们也可以训练k个SVM来解决多类分类问题。但是现在大多数SVM软件包都有内置的多类分类功能可以直接使用。
逻辑回归和SVM
对于逻辑回归和SVM两种算法应该如何根据不同问题来选择下面给出选择的准则
如果相较于m而言n要大很多即训练集数据量不够支持训练一个复杂的非线性模型则选择使用逻辑回归模型或者不带核函数的SVM如果n较小而且m大小中等例如n在1-1000之间而m在10-10000之间可以使用带高斯核函数的SVM如果n较小而m较大例如n在1-1000之间而m大于50000则使用SVM会比较慢解决方案是创造、增加更多的特征然后使用逻辑回归或者不带核函数的SVM
值得一提的是神经网络在以上三种情况下都可能会有较好的表现但是训练神经网络可能会非常慢选择SVM的原因主要在于它的代价函数是凸函数不存在局部最小值。
小结
本节课主要介绍一个非常流行的算法–支持向量机(SVM)不过要真正弄懂这个算法的原理单纯看完这节课其实感觉还是不太够的还需要更深入了解并且要顺便用代码实现下通过实践来促进理解。
