SVM

Profile

FullName: Support Vector Machine

vs Logistic Regression

Logistic Regression

$声明损失函数: L(\theta)=\sum_{i=1}^N(y_i(1-\ln{(\sigma(\theta·X_b^{(i)}})) + (1-y_i)(\ln{(\sigma{(\theta·X_b^{(i)})})}))$
$其中:\hat{y} = \sigma(t) = \frac{1}{1+exp(-t)}$
$求解:argmin_{\theta}L({\theta})$
Logistic回归的决策边界可以使得向量 $(ln(\hat{y})-ln(y))$ 的范数尽可能小,即尽可能保证阳性事件的预测概率尽可能大,阴性事件的预测概率尽可能小

Support Vector Machine

hard-margin:找到一个超平面f(θ),使这个超平面两边的最近的两个点(Support Vector)与这个超平面的距离(margin/2)最远,f(θ)作为分类边界,并且不允许有点落在margin区域内

soft-margin:允许部分向量落在margin区域或者margin对岸,并将这些点距离margin的距离作为损失函数的一部分.

svm的数学表达

hard-margin-SVM

$二维空间中(x_0,y_0)到直线l(Ax+By+C=0)的距离 d = \frac{(Ax_0+By_0+C)}{\sqrt{A^2+B^2}}$
$拓展到N维空间,向量x_b到超平面\theta^T·x=0的距离d_b = \frac{| w_0^Tx+b_0|}{\|w_0\|}$
设 margin = 2d
$\begin{equation} \begin{cases} \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|}>=d & \forall y^{(i)} =1\\ \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|}<=-d & \forall y^{(i)}=-1 \end{cases} \end{equation}$ => $\begin{cases} \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|d} >= 1 & \forall y^{(i)} = 1 \\ \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|d}<=-1 & \forall y^{(i)}=-1 \end{cases}$ => $\frac{y^{(i)}(w_0^Tx^{(i)}+b_0)}{\|w_0\|d} >= 1$
$令w = \frac{w_0^T}{\|w_0\|d},b=\frac{b_0}{\|w_0\|d},约束条件可表示为y^{(i)}(w·x^{(i)}+b) >= 1$
$对于任意支撑向量x_s,x_s到l的距离d = \frac{|w·x_s+b|}{\|w\|}=\frac{1}{\|w\|}$
$d=d_{max} 时w= \|w\|_{min},所以svm问题可转化为有条件的最优值问题$
$min\frac{1}{2}\|w\|^2 \\ s.t. \quad\forall(x^{(i)},y^{(i)}) \in trainDataSet \quad y^{(i)}(w·x^{(i)}+b)>=1$

soft-margin-SVM

允许部分点越过支撑向量,越过的部分会作为损失函数的一部分,最优值问题转化为
$min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^m\eta_i) \\ s.t.\qquad y^{(i)}(w·x^{(i)}+b) >= 1-\eta_i\qquad (\eta_{i} >=0)\\ 特别的,当C\to+∞时,soft-margin-SVM会转化为hard-margin-SVM$
以上模型成为L1正则,L2正则目标表达式为
$min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^{m}\eta_i^2)$

Kernel Function(核函数,Kernel Check)

SVM可以视为求解
$min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^{m}\eta_i) \\ s.t. \qquad y^{{i}}(w^Tx^{(i)}+b) \ge 1-\eta_i\quad (\eta_i\ge0)$
的最优化问题,这个问题可以等价于它的对偶问题
$max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_ix_j \qquad(1)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0$
有时分类边界是非线性的,需要对x,y进行某种变形
$def\ function\ K:(x,y)\rightarrow (x'y') ,其中x',y'是x,y进行某种变形后的结果$
目标问题可转化为
$max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jK(x_i,x_j) \qquad(2)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0$

多项式核函数

最高系数为2的多项式核函数为例,
$K(x,y)=(x·y+1)^2=(\sum_{i=1}^{n}x_iy_i+1)^2\\=\sum_{i=1}^{n}(x_i^2)(y_i^2)+\sum_{i=2}^{n}\sum_{j=1}^{i-1}(\sqrt2x_ix_j)(\sqrt2y_iy_j)+\sum_{i=1}^{n}(\sqrt2x_i)(\sqrt2y_i)+1=x'·y'\qquad(3)\\ 其中x'=(x_n^2,...,x_1^2,\sqrt2x_nx_{n-1},...,\sqrt2x_n,...,\sqrt2x_1,1),\\y'=(y_n^2,...,y_1^2,\sqrt2y_ny_{n-1},...,\sqrt2y_n,...,\sqrt2y_1,1)$
(3)带入(2)可得
$max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j(x_iy_i+1)^2 \qquad(4)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0$
将二次核函数推广到一般情况,
$K_{c,d}(x,y)=(x·y+c)^d$
特别地,当c=0,d=1时候,多项式核函数可称为线性核函数
$K_{0,1}(x,y)=x·y$
多项式核函数可以认为是向量点乘推广到更一般的形式
$x·y=K_{0,1}(x,y)=\sum_{i=1}^{m}x_iy_i \\ K_{c,d}(x,y)=(x·y+c)^d$

高斯核函数

$高斯分布(正态分布)\qquad g(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x-\mu}{\sigma})^2}=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{1}{\sigma})^2({x-\mu})^2}$
又称RBF核(Radial Basis Function Kernel),形态如下
$K_{\gamma}(x,y)=e^{-\gamma\|x-y\|^2}$
其中y是每一个数据点,即每一个数据点都作为landmark
由于和高斯分布的形态一致,所以得名高斯核函数
高斯核函数可以将一个m*n的样本映射为一个m*m的样本,是一种维度拓展的方法
$\gamma$ 越大,高斯分布越窄,越容易过拟合
$\gamma$ 越小,高斯分布越宽,越容易欠拟合
可以认为 $\gamma$ 和模型复杂度正相关

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 218,284评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,115评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,614评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,671评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,699评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,562评论 1赞 305
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,309评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,223评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,668评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,859评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,981评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,705评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,310评论 3赞 330
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,904评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,023评论 1赞 270
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,146评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,933评论 2赞 355

SVM