支持向量机(SVM)中相关问题的思考

zz/2024/5/21 21:41:53

相关问题

  1. SVM的基本想法就是求解能正确划分训练样本并且其几何间隔最大化的超平面。

  2. 引入对偶算法求解支持向量机的参数:

  • 对偶问题往往更加容易求解;
  • 可以自然的引用核函数(拉格朗日表达式里面有内积,而核函数也是通过内积进行映射的);
  • 基于KKT条件的互补松弛条件,训练样本集中只有支持向量所对应的拉格朗日乘子不为0,而支持向量占比较小,降低了模型在后续问题的计算量。
  1. 使用核函数:将输入特征(线性不可分)映射到高维特征空间,可以在高维空间上让进行线性分类。如高斯核函数,其中包含指数函数,可以利用泰勒级数将其展开至无限维,从而实现将输入特征映射到无穷维。

  2. SMO算法思想:它选择凸二次规划的两个变量,其它的变量保持不变,然后根据这两个变量构建一个二次规划问题,这个二次规划关于这两个变量解会更加的接近原始二次规划的解,通过这样的子问题划分可以大大增加整个算法的计算速度。关于这两个变量,其中一个是严重违反KKT条件的一个变量,另一个变量是根据自由约束确定

  3. 关于最大化几何间隔的目标函数中,将函数间隔直接设置为1的理由:
    Andrew Ng在CS229中解释为:
    w w w b b b添加了隐含的放缩限制,即使 w w w 2 ∗ w 2*w 2w b b b 2 ∗ b 2*b 2b,最后的预测值只依据于正负,所以不影响结果。
    在寻找几何间隔最大值的过程中,因为寻找最大几何间隔和寻找令几何间隔达到最大的超平面是一回事,所以当给出一个超平面,无论它的几何间隔是多少,只要是正值(因为是在正负样本区域中间,所以肯定是正值),我都可以令这个超平面的 ∣ ∣ w ∣ ∣ = 1 / γ ⇒ γ ^ = 1 ||w||=1/\gamma\Rightarrow \hat{\gamma}=1 w=1/γγ^=1
    或者说给出一个超平面,然后规定它的 γ ^ = 1 \hat{\gamma}=1 γ^=1,那么如果它的 γ = 0.1 \gamma=0.1 γ=0.1,那么 ∣ ∣ w ∣ ∣ = 10 ||w||=10 w=10;如果 γ = 1 \gamma=1 γ=1,那么 ∣ ∣ w ∣ ∣ = 1 ||w||=1 w=1,也就是说, γ \gamma γ越大,||w||越小。既然如此,那么原先寻找 γ \gamma γ的最大值就变成了寻找 ∣ ∣ w ∣ ∣ ||w|| w的最小值,即 max ⁡ γ \max\gamma maxγ等价于 max ⁡ 1 ∣ ∣ w ∣ ∣ \max\frac{1}{||w||} maxw1


推导过程注意点

  1. h(x) = wTx + b,向量w为超平面的法向量(其中 w 1 x 1 + w 2 y 1 + b = 0 , w 1 x 2 + w 2 y 2 = 0 = > w 1 ( x 1 − x 2 ) + w 2 ( y 1 − y 2 ) = 0 w_1x_1 + w_2y_1 + b = 0, w_1x_2 + w_2y_2 = 0 => w_1(x_1 - x_2) + w_2(y_1- y_2) = 0 w1x1+w2y1+b=0,w1x2+w2y2=0=>w1(x1x2)+w2(y1y2)=0,所以 w为超平面的法向量 );
  2. 最大化样本集的几何间隔,同时使得所有样本的几何间隔都大于这个间隔,由于w和b可随意缩放,这里假设 ∣ ∣ w ∣ ∣ = 1 ||w|| = 1 w=1使得样本集的几何间隔等于函数间隔;
  3. 在凸集上寻找凸函数的全局最值的过程称为凸优化,即目标函数(objective function)是凸函数,可行集(feasible set)为凸集, ∣ ∣ w ∣ ∣ = 1 ||w|| = 1 w=1的条件会导致可行集为非凸集;
  4. ∣ ∣ w ∣ ∣ = 1 ||w|| = 1 w=1的条件去掉,并替换限制条件中的几何间隔为函数间隔,因为这个限制条件原本是为了保证数据集的几何间隔等于函数间隔;
  5. 由于目标函数仍然不是凸函数(双曲线),而函数间隔通过缩放 w w w b b b可以是任何值。将数据集的函数间隔设置为1,这个约束可以成立是因为无论函数间隔等于多少,都可以让 w w w b b b同时除以函数间隔使得函数间隔等于1,这是一个隐含的缩放条件。

http://www.ngui.cc/zz/2727394.html

相关文章

Linux内核架构演化

Linux内核架构演化 [外链图片转存失败(img-ytRvRQQ5-1565429920094)(https://img-blog.csdn.net/20170210195344197?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdGx6aGF0YW8/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA/dissolve/70/gravity/SouthEast)]

通往奥格瑞玛的道路 最短路的综合应用

通往奥格瑞玛的道路 题目链接 通往奥格瑞玛的道路 题目描述 在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士,他是部落的中坚力量 有一天他醒来后发现自己居然到了联盟的主城暴风城 在被众多联盟的士兵攻击后,他决定逃回自己的家乡奥格瑞玛 在艾泽拉…

B. Array Walk

传送门 分析 这题的题意大概就是有1-n个点,每个点赋值为a[i],现在可以移动k次,不过只能向左移动z次,并且不能连续向左移动,问你最后走过所有点的和最大是多少 这题很明显思路是一个dp,但是怎么进行状态转…

Codeforces 954E:Water Taps 贪心

传送门 题目描述 ∀ x i ∈ [ 1 , a i ] , \forall x_i\in[1,a_i], ∀xi​∈[1,ai​],对于所有满足 ∑ i 1 n x i ( t i − T ) 0 \sum_{i1}^nx_i(t_i-T)0 ∑i1n​xi​(ti​−T)0的情况,求 ∑ i 1 n x i \sum_{i1}^nx_i ∑i1n​xi​的最大值 分析 我们可以计算大于m和小…

CodeForces 792C :Divide by Three DP + 路径还原

传送门 题目描述 在一个黑板上写着一个正整数 n 。它有不超过10^5位(话说黑板上是怎么写下这个数的) 。老师给你了一个任务,把它魔改成一个 美丽数 ,而且因为你很懒,你非常非常的想用最小的步数把它改成一个 美丽数 …

CodeForces 372C :Watching Fireworks is Fun DP + 单调队列

传送门 题目描述 给出N个位子,排成一列,现在有M个烟花,每秒人的速度d,每个烟花有三个元素:a,b,t,表示在时刻t会绽放,如果我们在位子x观看到了的话,会获得b-…

CodeForces 961D:Pair Of Lines 思维

传送门 题目描述 在平面直角坐标系上给出n个点,求是否存在两条直线穿过所有点。 分析 前面三个点中,任意两个点必成一条直线,所以我们去枚举三个点中的两个,然后去判断其他的点是否在这条直线上,然后再判断不在这条…

CodeForces 319B :Psychos in a Line 单调栈

传送门 题目描述 有编号为1~N的N个人站成一排(顺序是乱的),每人手中拿着一把枪。每一个时刻,每个人同时瞄准右边的人(如果存在的话),然后如果这个人编号比自己大,则开枪将他打死。…

Wireless Password :ac自动机 + 状压DP

分析 f[i][j][k]表示第i位的情况下,在trie图上的位置位j的情况下匹配情况位k,状态转移方程就比较好写了 dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] (dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] dp[i][j][l]) % mod注意一下减去不合法的状态,节…

CodeForces 1367E :Necklace Assembly 思维

传送门 题目描述 给你一个字符串,你从中挑选一些让它们成为一个环,使得这个环朝一个方向转 k k k下,与原来看起来一样,找到你能够满足这个条件的可以挑选的最多的字符数量。 分析 我们去枚举 k k k的因子,那么我转…