机器学习—支持向量机理论详细推导（含例题讲解）（四）

╰+攻爆jí腚メ 2023-10-05 23:04 3阅读 0赞

## 12.非线性支持向量机与核函数 ##

线性可分:用一个分离超平面 ω ⋅ x + b \\omega\\cdot x+b ω⋅x\+b将数据集完全分开；

非线性可分:用一个超曲面分开数据集。

![bc4db724c6424ccfb506b907995df49e.png][]

非线性问题往往不好求解，所以希望能用解线性分类间题的方法解决这个问题。

采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。

即:怎么将原空间上的点映射到新空间上的点！

## 13.核函数有什么用？ ##

原空间:输入空间  min ⁡    ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t .    ∑ i = 1 N α i y i = 0    ,    α i ≥ 0    ,    i = 1 , 2 , ⋯   , N \\begin\{split\} &\\min\\;\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\alpha\_i\\alpha\_jy\_iy\_j(x\_i\\cdot x\_j)-\\sum\_\{i=1\}^\{N\}\\alpha\_i\\\\ &s.t.\\;\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\;,\\;\\alpha\_i\\geq0\\;,\\;i=1,2,\\cdots,N \\end\{split\} mini=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαis.t.i=1∑Nαiyi=0,αi≥0,i=1,2,⋯,N

在上式中 x i ⋅ x j x\_i\\cdot x\_j xi⋅xj是内积，新空间中可能变为 z z z，对应希尔伯特空间，要能计算 z i ⋅ z j z\_i\\cdot z\_j zi⋅zj。

希望找到一个映射 ϕ ( x ) : χ → \\phi(x):\\chi\\rightarrow ϕ(x):χ→  H H H  z i = ϕ ( x i )    ,    z j = ϕ ( x j ) z i ⋅ z j = ϕ ( x i ) ⋅ ϕ ( x j ) = K ( x i , x j ) \\begin\{split\} &z\_i=\\phi(x\_i)\\;,\\;z\_j=\\phi(x\_j)\\\\ &z\_i\\cdot z\_j=\\phi(x\_i)\\cdot \\phi(x\_j)=K(x\_i,x\_j) \\end\{split\} zi=ϕ(xi),zj=ϕ(xj)zi⋅zj=ϕ(xi)⋅ϕ(xj)=K(xi,xj)

如果可以实现，非线性支持向量机变为:  
 min ⁡    ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i \\min\\;\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\alpha\_i\\alpha\_jy\_iy\_jK(x\_i,x\_j)-\\sum\_\{i=1\}^\{N\}\\alpha\_i mini=1∑Nj=1∑NαiαjyiyjK(xi,xj)−i=1∑Nαi

接下来我们看一个例子:

K ( x , z ) = ( x ⋅ z ) 2    ,    x    z ∈ R 2 K(x,z)=(x\\cdot z)^2\\;,\\;x\\;z\\in R^2 K(x,z)=(x⋅z)2,xz∈R2

请问: ϕ → H \\phi\\rightarrow H ϕ→H?

**解:  x = ( x ( 1 ) , x ( 2 ) ) T    ,    z = ( z ( 1 ) , z ( 2 ) ) T x=(x^\{(1)\},x^\{(2)\})^T\\;,\\;z=(z^\{(1)\},z^\{(2)\})^T x=(x(1),x(2))T,z=(z(1),z(2))T  
 K ( x , z ) = ( x ( 1 ) z ( 1 ) + x ( 2 ) z ( 2 ) ) 2 = ( x ( 1 ) z ( 1 ) ) 2 + 2 x ( 1 ) x ( 2 ) z ( 1 ) z ( 2 ) + ( x ( 2 ) z ( 2 ) ) 2 \\begin\{split\} K(x,z)&=(x^\{(1)\}z^\{(1)\}+x^\{(2)\}z^\{(2)\})^2\\\\ &=(x^\{(1)\}z^\{(1)\})^2+2x^\{(1)\}x^\{(2)\}z^\{(1)\}z^\{(2)\}+(x^\{(2)\}z^\{(2)\})^2 \\end\{split\} K(x,z)=(x(1)z(1)\+x(2)z(2))2=(x(1)z(1))2\+2x(1)x(2)z(1)z(2)\+(x(2)z(2))2**

我们尝试 H = R 3 H=R^3 H=R3  
 ϕ ( x ) = ( ( x ( 1 ) ) 2 , 2 x ( 1 ) x ( 2 ) , ( x ( 2 ) ) 2 ) T \\phi(x)=((x^\{(1)\})^2,\\sqrt\{2\}x^\{(1)\}x^\{(2)\},(x^\{(2)\})^2)^T ϕ(x)=((x(1))2,2x(1)x(2),(x(2))2)T

1) ϕ : R 2 → R 3 \\phi:R^2\\rightarrow R^3 ϕ:R2→R3  
 ϕ ( x ) ⋅ ϕ ( z ) = ( x ( 1 ) z ( 1 ) ) 2 + 2 x ( 1 ) x ( 2 ) z ( 1 ) z ( 2 ) + ( x ( 2 ) z ( 2 ) ) 2 = K ( x , z ) \\phi(x)\\cdot \\phi(z)=(x^\{(1)\}z^\{(1)\})^2+2x^\{(1)\}x^\{(2)\}z^\{(1)\}z^\{(2)\}+(x^\{(2)\}z^\{(2)\})^2=K(x,z) ϕ(x)⋅ϕ(z)=(x(1)z(1))2\+2x(1)x(2)z(1)z(2)\+(x(2)z(2))2=K(x,z)

2)  ϕ ( x ) = 1 2 ( ( x ( 1 ) ) 2 − ( x ( 2 ) ) 2    ,    2 x ( 1 ) x ( 2 )    ,    ( x ( 1 ) ) 2 + ( x ( 2 ) ) 2 ) T ϕ ( x ) ⋅ ϕ ( z ) = K ( x , z ) \\begin\{split\} &\\phi(x)=\\frac\{1\}\{\\sqrt\{2\}\}((x^\{(1)\})^2-(x^\{(2)\})^2\\;,\\;2x^\{(1)\}x^\{(2)\}\\;,\\;(x^\{(1)\})^2+(x^\{(2)\})^2)^T\\\\ &\\phi(x)\\cdot \\phi(z)=K(x,z) \\end\{split\} ϕ(x)=21((x(1))2−(x(2))2,2x(1)x(2),(x(1))2\+(x(2))2)Tϕ(x)⋅ϕ(z)=K(x,z)

对于同一个核函数，有多个不同的映射！

我们总结一下:

原空间:  χ ∈ R 2    ,    x = ( x ( 1 ) , x ( 2 ) ) T ∈ χ \\chi\\in R^2\\;,\\;x=(x^\{(1)\},x^\{(2)\})^T\\in \\chi χ∈R2,x=(x(1),x(2))T∈χ

新空间:  Z ∈ R 2    ,    z = ( z ( 1 ) , z ( 2 ) ) T ∈ Z z = ϕ ( x ) = ( ( x ( 1 ) ) 2 , ( x ( 2 ) ) 2 ) T ⇒ ω 1 ( x ( 1 ) ) 2 + ω 2 ( x ( 2 ) ) 2 + b = 0 ⇒ ω 1 z ( 1 ) + ω 2 z ( 2 ) + b = 0 \\begin\{split\} &Z\\in R^2\\;,\\;z=(z^\{(1)\},z^\{(2)\})^T\\in Z\\\\ &z=\\phi(x)=((x^\{(1)\})^2,(x^\{(2)\})^2)^T\\\\ \\Rightarrow &\\omega\_1(x^\{(1)\})^2+\\omega\_2(x^\{(2)\})^2+b=0\\\\ \\Rightarrow &\\omega\_1z^\{(1)\}+\\omega\_2z^\{(2)\}+b=0 \\end\{split\} ⇒⇒Z∈R2,z=(z(1),z(2))T∈Zz=ϕ(x)=((x(1))2,(x(2))2)Tω1(x(1))2\+ω2(x(2))2\+b=0ω1z(1)\+ω2z(2)\+b=0

用线性分类方法求解非线性分类问题分为两步:

首先使用一个变换将原空间的数据映射到新空间;

然后在新空间里用线性分类学习方法从训练数据中学习分类模型。

核技巧就属于这样的方法。

核技巧应用到支持向量机，其基本想法:

通过一个非线性变换将输入空间(欧氏空间R”或离散集合)对应于一个特征空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机)。分类问题的学习任务通过在特征空间中求解线性支  
持向量机就可以完成.

## 14.如何找正定核 ##

原: x i ⋅ x j x\_i\\cdot x\_j xi⋅xj

新: ϕ ( x i ) ⋅ ϕ ( x j ) = K ( x i , x j ) \\phi(x\_i)\\cdot \\phi(x\_j)=K(x\_i,x\_j) ϕ(xi)⋅ϕ(xj)=K(xi,xj)核函数

我们要替换原来的内积定义，同一个向量它的内积一定大于等于0，所以找正定核是最合适不过的。

**解: 第一步:我们希望找到对称函数 K ( x , z ) K(x,z) K(x,z)**

x , z ∈ χ x,z\\in\\chi x,z∈χ，为输入空间。

需要对 ∀ x 1 , x 2 , ⋯   , x m ∈ χ \\forall x\_1,x\_2,\\cdots,x\_m\\in\\chi ∀x1,x2,⋯,xm∈χ， K ( x , z ) K(x,z) K(x,z)对应的 G r a m Gram Gram矩阵半正定。

为什么要任意选取呢？因为训练数据集不确定。

我们的 G r a m Gram Gram矩阵为:

原来的:  \[ x 1 ⋅ x 1 x 1 ⋅ x 2 ⋯ x 1 ⋅ x m x 2 ⋅ x 1 x 2 ⋅ x 2 ⋯ x 2 ⋅ x m ⋯ ⋯ ⋯ ⋯ x m ⋅ x 1 x m ⋅ x 2 ⋯ x m ⋅ x m \] \\begin\{bmatrix\} x\_1\\cdot x\_1 & x\_1\\cdot x\_2 & \\cdots & x\_1\\cdot x\_m \\\\ x\_2\\cdot x\_1 & x\_2\\cdot x\_2 & \\cdots & x\_2\\cdot x\_m \\\\ \\cdots & \\cdots & \\cdots & \\cdots \\\\ x\_m\\cdot x\_1 & x\_m\\cdot x\_2 &\\cdots &x\_m\\cdot x\_m \\end\{bmatrix\} ⎣⎡x1⋅x1x2⋅x1⋯xm⋅x1x1⋅x2x2⋅x2⋯xm⋅x2⋯⋯⋯⋯x1⋅xmx2⋅xm⋯xm⋅xm⎦⎤

新的:  \[ K ( x 1 ⋅ x 1 ) K ( x 1 ⋅ x 2 ) ⋯ K ( x 1 ⋅ x m ) K ( x 2 ⋅ x 1 ) K ( x 2 ⋅ x 2 ) ⋯ K ( x 2 ⋅ x m ) ⋯ ⋯ ⋯ ⋯ K ( x m ⋅ x 1 ) K ( x m ⋅ x 2 ) ⋯ K ( x m ⋅ x m ) \] \\begin\{bmatrix\} K(x\_1\\cdot x\_1) & K(x\_1\\cdot x\_2) & \\cdots & K(x\_1\\cdot x\_m) \\\\ K(x\_2\\cdot x\_1) & K(x\_2\\cdot x\_2) & \\cdots & K(x\_2\\cdot x\_m) \\\\ \\cdots & \\cdots & \\cdots & \\cdots \\\\ K(x\_m\\cdot x\_1) & K(x\_m\\cdot x\_2) &\\cdots & K(x\_m\\cdot x\_m) \\end\{bmatrix\} ⎣⎡K(x1⋅x1)K(x2⋅x1)⋯K(xm⋅x1)K(x1⋅x2)K(x2⋅x2)⋯K(xm⋅x2)⋯⋯⋯⋯K(x1⋅xm)K(x2⋅xm)⋯K(xm⋅xm)⎦⎤

我们的新矩阵需要满足半正定。

半正定的定义:关于矩阵 A A A，对 ∀ x \\forall x ∀x（非零）存在， x T A x ≥ 0 x^TAx\\geq0 xTAx≥0，则称矩阵 A A A是半正定。

半负定的定义: x T A x ≤ 0 x^TAx\\leq0 xTAx≤0

正定的定义: x T A x > 0 x^TAx>0 xTAx>0

负定的定义: x T A x < 0 x^TAx<0 xTAx<0

我们的判定方法如下:

第一种方法:  x T A x = y T D y ≥ 0 x^TAx=y^TDy\\geq0 xTAx=yTDy≥0

其中 D D D为对角矩阵，所有元素均大于等于0。

找 A A A的特征根，全部都是大于等于0

第二种方法:

所有主子行列式大于等于0

## 15.映射下的新空间 ##

我们回顾之前学习的欧式空间的定义:

我们最初的空间叫做向量空间或者线性空间，这个空间的特点是加法运算（+）和数乘运算（ × \\times ×）是封闭的。

我们在此基础上定义内积定义，使得加法运算（+）、数乘运算（ × \\times ×）和内积运算（ ⋅ \\cdot ⋅）是封闭的。形成内积空间。

如果我们想知道向量的长度，我们引入范数的定义，形成赋范线性空间。

上面的向量空间、内积空间、赋范线性空间构成我们常见的欧式空间。

进一步，想要研究收敛性和极限，所有点都在空间内，叫做 B a n a c h Banach Banach空间。

如果不是在我们熟知的欧氏空间中研究上面的内容，我们换了一个空间，定义了新的内积及范数，并且空间是完备的，称为希尔伯特空间。

具体的实现步骤:

**解: 1):**

构成向量空间（找到向量空间）

ϕ \\phi ϕ表示为: x → K ( ⋅ , x ) x\\rightarrow K(\\cdot,x) x→K(⋅,x)

对于 ∀ x i ∈ χ    ,    α i ∈ R    ,    i = 1 , 2 , ⋯   , m \\forall x\_i\\in\\chi\\;,\\;\\alpha\_i\\in R\\;,\\;i=1,2,\\cdots,m ∀xi∈χ,αi∈R,i=1,2,⋯,m

定义:  f ( ⋅ ) = ∑ i = 1 m α i K ( ⋅ , x i ) f(\\cdot)=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(\\cdot,x\_i) f(⋅)=i=1∑mαiK(⋅,xi)

f f f构成集合 S S S， S S S变成一个向量空间。

验证: 从 S S S中 ∀ f , g \\forall f,g ∀f,g，有:  f = ∑ i = 1 m α i K ( ⋅ , x i ) g = ∑ j = 1 v β j K ( ⋅ , z j ) \\begin\{split\} &f=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(\\cdot,x\_i)\\\\ &g=\\sum\_\{j=1\}^\{v\}\\beta\_jK(\\cdot,z\_j)\\\\ \\end\{split\} f=i=1∑mαiK(⋅,xi)g=j=1∑vβjK(⋅,zj)  f + g = ∑ i = 1 m α i K ( ⋅ , x i ) + ∑ j = 1 v β j K ( ⋅ , z j ) = ∑ i = 1 m + l a i K ( ⋅ , μ i ) ∈ S a f = ∑ i = 1 m a α i K ( ⋅ , x i )    ,    a α i ∈ R \\begin\{split\} f+g&=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(\\cdot,x\_i)+\\sum\_\{j=1\}^\{v\}\\beta\_jK(\\cdot,z\_j)\\\\ &=\\sum\_\{i=1\}^\{m+l\}a\_iK(\\cdot,\\mu\_i)\\in S\\\\ af&=\\sum\_\{i=1\}^\{m\}a\\alpha\_iK(\\cdot,x\_i)\\;,\\;a\\alpha\_i\\in R \\end\{split\} f\+gaf=i=1∑mαiK(⋅,xi)\+j=1∑vβjK(⋅,zj)=i=1∑m\+laiK(⋅,μi)∈S=i=1∑maαiK(⋅,xi),aαi∈R

综上所述， S S S对加法运算和数乘运算是封闭的。

2）在集合 S S S上定义内积（内积空间）

定义 ∗ \* ∗，对 ∀ f , g ∈ S \\forall f,g\\in S ∀f,g∈S，我们定义:  
 f ∗ g = ∑ i = 1 m ∑ j = 1 l α i β j K ( x i , z j ) f\*g=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{l\}\\alpha\_i\\beta\_jK(x\_i,z\_j) f∗g=i=1∑mj=1∑lαiβjK(xi,zj)

内积必须满足四个条件:  \{ ( 1 ) : ( c f ) ∗ g = c ( f ∗ g )    ,    c ∈ R ( 2 ) : ( f + g ) ∗ h = f ∗ h + g ∗ h    ,    h ∈ S ( 3 ) : f ∗ g = g ∗ f ( 4 ) : f ∗ f ≥ 0 ; f ∗ f = 0 ⇒ f = 0 \\left\\\{ \\begin\{split\} &(1):(cf)\*g=c(f\*g)\\;,\\;c\\in R\\\\ &(2):(f+g)\*h=f\*h+g\*h\\;,\\;h\\in S\\\\ &(3):f\*g=g\*f\\\\ &(4):f\*f\\geq0\\quad \\quad ;f\*f=0\\Rightarrow f=0 \\end\{split\} \\right. ⎩⎨⎧(1):(cf)∗g=c(f∗g),c∈R(2):(f\+g)∗h=f∗h\+g∗h,h∈S(3):f∗g=g∗f(4):f∗f≥0;f∗f=0⇒f=0

我们接下来验证是否满足四个条件:

首先是第一个:  l e f t    :    c f = c ∑ i = 1 m α i K ( ⋅ , x i ) = ∑ i = 1 m c α i K ( ⋅ , x i ) ( c f ) ∗ g = ∑ i = 1 m ∑ j = 1 l ( c α i ) β j K ( x i , z j ) = c ∑ i = 1 m ∑ j = 1 l α i β j K ( x i , z j ) = c ( f ∗ g ) = r i g h t \\begin\{split\} left\\;:\\;&cf=c\\sum\_\{i=1\}^\{m\}\\alpha\_iK(\\cdot,x\_i)=\\sum\_\{i=1\}^\{m\}c\\alpha\_iK(\\cdot,x\_i)\\\\ (cf)\*g&=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{l\}(c\\alpha\_i)\\beta\_jK(x\_i,z\_j)\\\\ &=c\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{l\}\\alpha\_i\\beta\_jK(x\_i,z\_j)\\\\ &=c(f\*g)=right \\end\{split\} left:(cf)∗gcf=ci=1∑mαiK(⋅,xi)=i=1∑mcαiK(⋅,xi)=i=1∑mj=1∑l(cαi)βjK(xi,zj)=ci=1∑mj=1∑lαiβjK(xi,zj)=c(f∗g)=right

接着是第二个:

首先我们定义:  h = ∑ q = 1 t b q K ( ⋅ , v q ) h=\\sum\_\{q=1\}^\{t\}b\_qK(\\cdot,v\_q) h=q=1∑tbqK(⋅,vq)

令 a i    ,    i = 1 , 2 , ⋯   , m + l a\_i\\;,\\;i=1,2,\\cdots,m+l ai,i=1,2,⋯,m\+l代替 α 1 , α 2 , ⋯   , α m , β 1 , β 2 , ⋯   , β l \\alpha\_1,\\alpha\_2,\\cdots,\\alpha\_m,\\beta\_1,\\beta\_2,\\cdots,\\beta\_l α1,α2,⋯,αm,β1,β2,⋯,βl。

令 μ i    ,    i = 1 , 2 , ⋯   , m + l \\mu\_i\\;,\\;i=1,2,\\cdots,m+l μi,i=1,2,⋯,m\+l代替 x 1 , x 2 , ⋯   , x m , z 1 , z 2 , ⋯   , z l x\_1,x\_2,\\cdots,x\_m,z\_1,z\_2,\\cdots,z\_l x1,x2,⋯,xm,z1,z2,⋯,zl。  
 l e f t    :    ( f + g ) ∗ h = ∑ i = 1 m + l ∑ q = 1 t a i b q K ( μ i , v q ) r i g h t    :    ∑ i = 1 m ∑ q = 1 t α i b q K ( α i , v q ) + ∑ j = 1 l ∑ q = 1 t β j b q K ( z j , v q ) ⇒ l e f t = r i g h t \\begin\{split\} &left\\;:\\;(f+g)\*h=\\sum\_\{i=1\}^\{m+l\}\\sum\_\{q=1\}^\{t\}a\_ib\_qK(\\mu\_i,v\_q)\\\\ &right\\;:\\;\\sum\_\{i=1\}^\{m\}\\sum\_\{q=1\}^\{t\}\\alpha\_ib\_qK(\\alpha\_i,v\_q)+\\sum\_\{j=1\}^\{l\}\\sum\_\{q=1\}^\{t\}\\beta\_jb\_qK(z\_j,v\_q)\\\\ \\Rightarrow &left=right \\end\{split\} ⇒left:(f\+g)∗h=i=1∑m\+lq=1∑taibqK(μi,vq)right:i=1∑mq=1∑tαibqK(αi,vq)\+j=1∑lq=1∑tβjbqK(zj,vq)left=right

我们看第三个:很明显已经成立，因为 α i \\alpha\_i αi和 β j \\beta\_j βj可以交换， K ( x i , z j ) K(x\_i,z\_j) K(xi,zj)是对称的，也可以换位置。

最后来看第四个:

我们首先来看第一个部分: f ∗ f ≥ 0 f\*f\\geq0 f∗f≥0  
 f ∗ f = ∑ i = 1 m ∑ j = 1 m α i α j K ( x i , x j ) f\*f=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{m\}\\alpha\_i\\alpha\_jK(x\_i,x\_j) f∗f=i=1∑mj=1∑mαiαjK(xi,xj)

因为 K ( x i , z j ) K(x\_i,z\_j) K(xi,zj)是对称的，所以 G r a m Gram Gram矩阵是半正定的，有 x T A x ≥ 0 x^TAx\\geq0 xTAx≥0。

所以有 f ∗ f ≥ 0 f\*f\\geq0 f∗f≥0

接下来我们看第二部分:

首先看充分性，即如果有 f = 0 f=0 f=0。  f = ∑ i = 1 m α i K ( ⋅ , x i ) → α i = 0 ⇒ f ∗ f = ∑ i = 1 m ∑ j = 1 m α i α j K ( x i , x j ) = 0 \\begin\{split\} &f=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(\\cdot,x\_i)\\rightarrow \\alpha\_i=0\\\\ \\Rightarrow &f\*f=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{m\}\\alpha\_i\\alpha\_jK(x\_i,x\_j)=0 \\end\{split\} ⇒f=i=1∑mαiK(⋅,xi)→αi=0f∗f=i=1∑mj=1∑mαiαjK(xi,xj)=0

充分性得证！

在证明必要性之前，我们先证明接下来一个:

问题:  ∀ f    ,    g ∈ S    ,    ( f ∗ g ) 2 ≤ ( f ∗ f ) ( g ∗ g ) \\forall f\\;,\\;g\\in S\\;,\\;(f\*g)^2\\leq(f\*f)(g\*g) ∀f,g∈S,(f∗g)2≤(f∗f)(g∗g)

**解: 取 λ ∈ R \\lambda\\in R λ∈R  f + λ g ∈ S ⇒ ( f + λ g ) ∗ ( f + λ g ) ≥ 0 ⇒ f ∗ f + 2 λ ( f ∗ g ) + λ 2 ( g ∗ g ) ≥ 0 \\begin\{split\} f+\\lambda g\\in S&\\Rightarrow (f+\\lambda g)\*(f+\\lambda g)\\geq0\\\\ &\\Rightarrow f\*f+2\\lambda(f\*g)+\\lambda^2(g\*g)\\geq0\\\\ \\end\{split\} f\+λg∈S⇒(f\+λg)∗(f\+λg)≥0⇒f∗f\+2λ(f∗g)\+λ2(g∗g)≥0**

我们不妨换一下:  ( g ∗ g ) λ 2 + 2 ( f ∗ g ) λ + f ∗ f ≥ 0 (g\*g)\\lambda^2+2(f\*g)\\lambda+f\*f\\geq0 (g∗g)λ2\+2(f∗g)λ\+f∗f≥0

我们上式是不是很贴近二次函数的问题，要想恒大于0，只需要让判别式 Δ \\Delta Δ的值小于等于0即可。

即我们得知:  4 ( f ∗ g ) 2 − 4 ( g ∗ g ) ( f ∗ f ) ≤ 0 ⇒ ( f ∗ g ) 2 ≤ ( f ∗ f ) ( g ∗ g ) \\begin\{split\} &4(f\*g)^2-4(g\*g)(f\*f)\\leq0\\\\ \\Rightarrow &(f\*g)^2\\leq (f\*f)(g\*g) \\end\{split\} ⇒4(f∗g)2−4(g∗g)(f∗f)≤0(f∗g)2≤(f∗f)(g∗g)

至此，我们的结论得证。接下来，我们回到原问题。  
 f = ∑ i = 1 m α i K ( ⋅ , x i ) f=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(\\cdot,x\_i) f=i=1∑mαiK(⋅,xi)

因为 f    ,    g f\\;,\\;g f,g是任意取，不妨取特别的 g g g，令 g = K ( ⋅ , x ) g=K(\\cdot,x) g=K(⋅,x)  f ∗ g = ∑ i = 1 m α i K ( x , x i ) ( f ∗ g ) 2 = ∑ i = 1 m ∑ j = 1 m α i α j K ( x , x i ) K ( x , x j ) f ∗ f = ∑ i = 1 m ∑ j = 1 m α i α j K ( x i , x j ) g ∗ g = K ( x , x ) ( f ∗ f ) ( g ∗ g ) = ∑ i = 1 m ∑ j = 1 m α i α j K ( x i , x j ) K ( x , x ) ( f ∗ g ) 2 ≤ ( f ∗ f ) ( g ∗ g ) = 0 \\begin\{split\} &f\*g=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(x,x\_i)\\\\ &(f\*g)^2=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{m\}\\alpha\_i\\alpha\_jK(x,x\_i)K(x,x\_j)\\\\ &f\*f=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{m\}\\alpha\_i\\alpha\_jK(x\_i,x\_j)\\\\ &g\*g=K(x,x)\\\\ &(f\*f)(g\*g)=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{m\}\\alpha\_i\\alpha\_jK(x\_i,x\_j)K(x,x)\\\\ &(f\*g)^2\\leq (f\*f)(g\*g)=0 \\end\{split\} f∗g=i=1∑mαiK(x,xi)(f∗g)2=i=1∑mj=1∑mαiαjK(x,xi)K(x,xj)f∗f=i=1∑mj=1∑mαiαjK(xi,xj)g∗g=K(x,x)(f∗f)(g∗g)=i=1∑mj=1∑mαiαjK(xi,xj)K(x,x)(f∗g)2≤(f∗f)(g∗g)=0

因为平方 ( f ∗ g ) 2 ≥ 0 (f\*g)^2\\geq0 (f∗g)2≥0，所以我们可以得到:  ( f ∗ g ) 2 = 0 ⇒ f ∗ g = 0 ⇒ ∑ i = 1 m α i K ( x , x i ) = 0 ⇒ α i = 0 ⇒ f = 0 \\begin\{split\} &(f\*g)^2=0\\\\ \\Rightarrow &f\*g=0\\Rightarrow \\sum\_\{i=1\}^\{m\}\\alpha\_iK(x,x\_i)=0\\Rightarrow \\alpha\_i=0\\Rightarrow f=0 \\end\{split\} ⇒(f∗g)2=0f∗g=0⇒i=1∑mαiK(x,xi)=0⇒αi=0⇒f=0

综上所述， ∗ \* ∗代表内积运算。此时我们的向量空间变为内积空间。

我们定义 f f f和 g g g的内积为:  
 f ⋅ g = ∑ i = 1 m ∑ j = 1 l α i β j K ( x i , z j ) f\\cdot g=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{l\}\\alpha\_i\\beta\_jK(x\_i,z\_j) f⋅g=i=1∑mj=1∑lαiβjK(xi,zj)

3)在集合S上定义范数，升级希尔伯特空间

定义:  ∣ ∣ f ∣ ∣ = f ⋅ f ||f||=\\sqrt\{f\\cdot f\} ∣∣f∣∣=f⋅f

此时空间转换为赋范线性空间。

新空间中K的特点:再生性！如:  f ( ⋅ ) = ∑ i = 1 m α i K ( ⋅ , x i ) K ( ⋅ , x ) ⋅ f = ∑ i = 1 m α i K ( x , x i ) = f ( x ) \\begin\{split\} &f(\\cdot)=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(\\cdot,x\_i)\\\\ &K(\\cdot,x)\\cdot f=\\sum\_\{i=1\}^\{m\}\\alpha\_iK(x,x\_i)=f(x) \\end\{split\} f(⋅)=i=1∑mαiK(⋅,xi)K(⋅,x)⋅f=i=1∑mαiK(x,xi)=f(x)

再比如: K ( ⋅ , x ) ⋅ K ( ⋅ , z ) = K ( x , z ) K(\\cdot,x)\\cdot K(\\cdot,z)=K(x,z) K(⋅,x)⋅K(⋅,z)=K(x,z)

总结:我们此处做的是如何从原始空间中找到一个希尔伯特空间！

## 16.正定核函数的充要条件 ##

设 K : χ × χ → R K:\\chi\\times \\chi\\rightarrow R K:χ×χ→R是对称函数，则 K ( x , z ) K(x,z) K(x,z)为正定核的充要条件是 ∀ x i ∈ χ    ,    i = 1 , 2 , ⋯   , m \\forall x\_i\\in\\chi\\;,\\;i=1,2,\\cdots,m ∀xi∈χ,i=1,2,⋯,m， K ( x , z ) K(x,z) K(x,z)对应的 G r a m Gram Gram矩阵 K = \[ K ( x i , x j ) \] m × m K=\[K(x\_i,x\_j)\]\_\{m\\times m\} K=\[K(xi,xj)\]m×m是半正定矩阵。

接下来我们证明一下这个结论:

首先看一下充分性:

K K K是半正定矩阵，我们的映射为:  ϕ    :    x → K ( ⋅ , x ) χ → H \\begin\{split\} \\phi\\;:\\;&x\\rightarrow K(\\cdot,x)\\\\ &\\chi\\rightarrow H \\end\{split\} ϕ:x→K(⋅,x)χ→H

K ( ⋅ , x ) ⋅ K ( ⋅ , z ) = K ( x , z ) K(\\cdot,x)\\cdot K(\\cdot,z)=K(x,z) K(⋅,x)⋅K(⋅,z)=K(x,z)说明具有再生性，所以此时 K ( x , z ) K(x,z) K(x,z)为正定核。

必要性:

K ( x , z ) K(x,z) K(x,z)为正定核,所以存在下面的映射:  χ → H x → ϕ ( x )    ,    z → ϕ ( z ) \\begin\{split\} &\\chi\\rightarrow H\\\\ &x\\rightarrow \\phi(x)\\;,\\;z\\rightarrow \\phi(z) \\end\{split\} χ→Hx→ϕ(x),z→ϕ(z)

我们有: K ( ⋅ , x ) ⋅ K ( ⋅ , z ) = K ( x , z ) K(\\cdot,x)\\cdot K(\\cdot,z)=K(x,z) K(⋅,x)⋅K(⋅,z)=K(x,z)

怎么判断矩阵为半正定矩阵呢?  ∀ x 1 , x 2 , ⋯   , x m ∈ χ ∀ c 1 , c 2 , ⋯   , c m ∈ R c = ( c 1 , c 2 , ⋯   , c m ) T \\begin\{split\} &\\forall x\_1,x\_2,\\cdots,x\_m\\in \\chi\\\\ &\\forall c\_1,c\_2,\\cdots,c\_m\\in R\\\\ &c=(c\_1,c\_2,\\cdots,c\_m)^T \\end\{split\} ∀x1,x2,⋯,xm∈χ∀c1,c2,⋯,cm∈Rc=(c1,c2,⋯,cm)T

K = \[ K ( x 1 , x 1 ) K ( x 1 , x 2 ) ⋯ K ( x 1 , x m ) K ( x 2 , x 1 ) K ( x 2 , x 2 ) ⋯ K ( x 2 , x m ) ⋯ ⋯ ⋯ ⋯ K ( x m , x 1 ) K ( x m , x 2 ) ⋯ K ( x m , x m ) \] K=\\begin\{bmatrix\} K(x\_1,x\_1) & K(x\_1,x\_2) & \\cdots & K(x\_1,x\_m) \\\\ K(x\_2,x\_1) & K(x\_2,x\_2) & \\cdots & K(x\_2,x\_m) \\\\ \\cdots &\\cdots & \\cdots &\\cdots\\\\ K(x\_m,x\_1) & K(x\_m,x\_2) & \\cdots & K(x\_m,x\_m) \\end\{bmatrix\} K=⎣⎡K(x1,x1)K(x2,x1)⋯K(xm,x1)K(x1,x2)K(x2,x2)⋯K(xm,x2)⋯⋯⋯⋯K(x1,xm)K(x2,xm)⋯K(xm,xm)⎦⎤

如果有:  c T K c ≥ 0 c^TKc\\geq0 cTKc≥0 则表示 K K K是半正定的矩阵。此时有:  
 c T K c = ( c 1 , c 2 , ⋯   , c m ) \[ K ( x 1 , x 1 ) K ( x 1 , x 2 ) ⋯ K ( x 1 , x m ) K ( x 2 , x 1 ) K ( x 2 , x 2 ) ⋯ K ( x 2 , x m ) ⋯ ⋯ ⋯ ⋯ K ( x m , x 1 ) K ( x m , x 2 ) ⋯ K ( x m , x m ) \] \[ c 1 c 2 ⋯ c m \] c^TKc=(c\_1,c\_2,\\cdots,c\_m) \\begin\{bmatrix\} K(x\_1,x\_1) & K(x\_1,x\_2) & \\cdots & K(x\_1,x\_m) \\\\ K(x\_2,x\_1) & K(x\_2,x\_2) & \\cdots & K(x\_2,x\_m) \\\\ \\cdots &\\cdots & \\cdots &\\cdots\\\\ K(x\_m,x\_1) & K(x\_m,x\_2) & \\cdots & K(x\_m,x\_m) \\end\{bmatrix\} \\begin\{bmatrix\} c\_1\\\\ c\_2\\\\ \\cdots\\\\ c\_m \\end\{bmatrix\} cTKc=(c1,c2,⋯,cm)⎣⎡K(x1,x1)K(x2,x1)⋯K(xm,x1)K(x1,x2)K(x2,x2)⋯K(xm,x2)⋯⋯⋯⋯K(x1,xm)K(x2,xm)⋯K(xm,xm)⎦⎤⎣⎡c1c2⋯cm⎦⎤

方法一:我们通过内积运算  ( c 1 , c 2 , ⋯   , c m ) \[ ϕ ( x 1 ) ⋅ ϕ ( x 1 ) ϕ ( x 1 ) ⋅ ϕ ( x 2 ) ⋯ ϕ ( x 1 ) ⋅ ϕ ( x m ) ϕ ( x 2 ) ⋅ ϕ ( x 1 ) ϕ ( x 2 ) ⋅ ϕ ( x 2 ) ⋯ ϕ ( x 2 ) ⋅ ϕ ( x m ) ⋯ ⋯ ⋯ ⋯ ϕ ( x m ) ⋅ ϕ ( x 1 ) ϕ ( x m ) ⋅ ϕ ( x 2 ) ⋯ ϕ ( x m ) ⋅ ϕ ( x m ) \] \[ c 1 c 2 ⋯ c m \] \\ (c\_1,c\_2,\\cdots,c\_m) \\begin\{bmatrix\} \\phi(x\_1)\\cdot \\phi(x\_1) & \\phi(x\_1)\\cdot \\phi(x\_2) & \\cdots & \\phi(x\_1)\\cdot \\phi(x\_m) \\\\ \\phi(x\_2)\\cdot \\phi(x\_1) & \\phi(x\_2)\\cdot \\phi(x\_2) & \\cdots & \\phi(x\_2)\\cdot \\phi(x\_m) \\\\ \\cdots &\\cdots & \\cdots &\\cdots\\\\ \\phi(x\_m)\\cdot \\phi(x\_1) & \\phi(x\_m)\\cdot \\phi(x\_2) & \\cdots & \\phi(x\_m)\\cdot \\phi(x\_m) \\end\{bmatrix\} \\begin\{bmatrix\} c\_1\\\\ c\_2\\\\ \\cdots\\\\ c\_m \\end\{bmatrix\} (c1,c2,⋯,cm)⎣⎡ϕ(x1)⋅ϕ(x1)ϕ(x2)⋅ϕ(x1)⋯ϕ(xm)⋅ϕ(x1)ϕ(x1)⋅ϕ(x2)ϕ(x2)⋅ϕ(x2)⋯ϕ(xm)⋅ϕ(x2)⋯⋯⋯⋯ϕ(x1)⋅ϕ(xm)ϕ(x2)⋅ϕ(xm)⋯ϕ(xm)⋅ϕ(xm)⎦⎤⎣⎡c1c2⋯cm⎦⎤  = ( c 1 , c 2 , ⋯   , c m ) \[ ϕ ( x 1 ) ϕ ( x 2 ) ⋯ ϕ ( x m ) \] \[ ϕ ( x 1 ) , ϕ ( x 2 ) , ⋯   , ϕ ( x m ) \] \[ c 1 c 2 ⋯ c m \] = ∣ ∣ ∑ i = 1 m c i ϕ ( x i ) ∣ ∣ 2 ≥ 0 =(c\_1,c\_2,\\cdots,c\_m) \\begin\{bmatrix\} \\phi(x\_1)\\\\ \\phi(x\_2)\\\\ \\cdots\\\\ \\phi(x\_m) \\end\{bmatrix\} \[\\phi(x\_1),\\phi(x\_2),\\cdots,\\phi(x\_m)\] \\begin\{bmatrix\} c\_1\\\\ c\_2\\\\ \\cdots\\\\ c\_m \\end\{bmatrix\} =||\\sum\_\{i=1\}^\{m\}c\_i\\phi(x\_i)||^2\\geq0 =(c1,c2,⋯,cm)⎣⎡ϕ(x1)ϕ(x2)⋯ϕ(xm)⎦⎤\[ϕ(x1),ϕ(x2),⋯,ϕ(xm)\]⎣⎡c1c2⋯cm⎦⎤=∣∣i=1∑mciϕ(xi)∣∣2≥0

方法二:直接表示二次型  ∑ i , j = 1 m c i c j K ( x i , x j ) = ∑ i , j = 1 m c i c j ϕ ( x i ) ⋅ ϕ ( x j ) = ∑ i = 1 m ∑ j = 1 m \[ c i ϕ ( x i ) \] ⋅ \[ c j ϕ ( x j ) \] = \[ c 1 ϕ ( x 1 ) + c 2 ϕ ( x 2 ) + ⋯ + c m ϕ ( x m ) \] ⋅ \[ c 1 ϕ ( x 1 ) + c 2 ϕ ( x 2 ) + ⋯ + c m ϕ ( x m ) \] = ∣ ∣ ∑ i = 1 m c i ϕ ( x i ) ∣ ∣ 2 2 \\begin\{split\} \\sum\_\{i,j=1\}^\{m\}c\_ic\_jK(x\_i,x\_j)&=\\sum\_\{i,j=1\}^\{m\}c\_ic\_j\\phi(x\_i)\\cdot \\phi(x\_j)\\\\ &=\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{m\}\[c\_i\\phi(x\_i)\]\\cdot \[c\_j\\phi(x\_j)\]\\\\ &=\[c\_1\\phi(x\_1)+c\_2\\phi(x\_2)+\\cdots+c\_m\\phi(x\_m)\]\\cdot \[c\_1\\phi(x\_1)+c\_2\\phi(x\_2)+\\cdots+c\_m\\phi(x\_m)\]\\\\ &=||\\sum\_\{i=1\}^\{m\}c\_i\\phi(x\_i)||\_2^2 \\end\{split\} i,j=1∑mcicjK(xi,xj)=i,j=1∑mcicjϕ(xi)⋅ϕ(xj)=i=1∑mj=1∑m\[ciϕ(xi)\]⋅\[cjϕ(xj)\]=\[c1ϕ(x1)\+c2ϕ(x2)\+⋯\+cmϕ(xm)\]⋅\[c1ϕ(x1)\+c2ϕ(x2)\+⋯\+cmϕ(xm)\]=∣∣i=1∑mciϕ(xi)∣∣22

正定核的等价定义:

设 χ ∈ R n    ,    K ( x , z ) \\chi\\in R^n\\;,\\;K(x,z) χ∈Rn,K(x,z)是定义在 χ × χ \\chi\\times\\chi χ×χ上的对称函数，如果对 ∀ x i ∈ χ    ,    i = 1 , 2 , ⋯   , m \\forall x\_i\\in\\chi\\;,\\;i=1,2,\\cdots,m ∀xi∈χ,i=1,2,⋯,m， K ( x , z ) K(x,z) K(x,z)对应的 G r a m Gram Gram矩阵 K = \[ K ( x i , x j ) \] m × m K=\[K(x\_i,x\_j)\]\_\{m\\times m\} K=\[K(xi,xj)\]m×m是半正定矩阵，则称 K ( x , z ) K(x,z) K(x,z)是正定核。

## 17.常用核函数 ##

:定义在欧式空间上

1）多项式核函数  K ( x , z ) = ( x ⋅ z + 1 ) p K(x,z)=(x\\cdot z+1)^\{p\} K(x,z)=(x⋅z\+1)p

它的一般形式为:  ( x ⋅ z + c ) p (x\\cdot z+c)^\{p\} (x⋅z\+c)p 其中 c c c是常量。

决策函数:  
 f ( x ) = s i g n ( ∑ i = 1 N a i ∗ y i ⋅ ( x i ⋅ x + 1 ) p + b ∗ ) f(x)=sign(\\sum\_\{i=1\}^\{N\}a\_i^\{\*\}y\_i\\cdot(x\_i\\cdot x+1)^\{p\}+b^\{\*\}) f(x)=sign(i=1∑Nai∗yi⋅(xi⋅x\+1)p\+b∗)

2）高斯核函数  K ( x , z ) = e x p ( − ∣ ∣ x − z ∣ ∣ 2 2 σ 2 ) K(x,z)=exp(-\\frac\{||x-z||^2\}\{2\\sigma^2\}) K(x,z)=exp(−2σ2∣∣x−z∣∣2)

决策函数:  
 f ( x ) = s i g n ( ∑ i = 1 N a i ∗ y i e x p ( − ∣ ∣ x − x i ∣ ∣ 2 2 σ 2 ) + b ∗ ) f(x)=sign(\\sum\_\{i=1\}^\{N\}a\_i^\{\*\}y\_i\{exp\}(-\\frac\{||x-x\_i||^2\}\{2\\sigma^2\})+b^\{\*\}) f(x)=sign(i=1∑Nai∗yiexp(−2σ2∣∣x−xi∣∣2)\+b∗)  
:定义在离散数据集合上

字符串对应的空间映射到高维空间:  
 \[ ϕ n ( s ) \] μ = ∑ i , s ( i ) = μ λ ( i ) \[\\phi\_n(s)\]\_\{\\mu\}=\\sum\_\{i,s(i)=\\mu\}\\lambda^\{(i)\} \[ϕn(s)\]μ=i,s(i)=μ∑λ(i)

n n n表示字符串长度， s s s是字符串， l ( i ) l(i) l(i)表示小的字符串对应的长度。

例子:一个文本\[’big’,’pig’,’bag’\]

长度为2的子字符串为\[’bi’,’bg’,’ig’,’pi’,’pg’,’ba’,’ag’\]

投影的特征空间取 R 7 R^7 R7，计算长度:（最后一个元素位置）-（最前一个位置）+1

bi            bg            ig            pi            pg            ba            ag

--------------------

big  λ 2 \\lambda^2 λ2  λ 3 \\lambda^3 λ3  λ 2 \\lambda^2 λ2 0 0 0 0  
pig 0 0  λ 2 \\lambda^2 λ2  λ 2 \\lambda^2 λ2  λ 3 \\lambda^3 λ3 0 0  
bag 0  λ 3 \\lambda^3 λ3 0 0 0  λ 2 \\lambda^2 λ2  λ 2 \\lambda^2 λ2

我们得出结果:  K ( b i g    ,    p i g ) = λ 4    ,    K ( b i g    ,    b a g ) = λ 6 K(big\\;,\\;pig)=\\lambda^4\\;,\\;K(big\\;,\\;bag)=\\lambda^6 K(big,pig)=λ4,K(big,bag)=λ6

度量两个字符串之间的相似度的方法可以使用—余弦相似度:  
 cos ⁡ θ = x ⋅ y ∣ ∣ x ∣ ∣ ∣ ∣ y ∣ ∣ \\cos\\theta=\\frac\{x\\cdot y\}\{||x||||y||\} cosθ=∣∣x∣∣∣∣y∣∣x⋅y

比较两个文本之间的相似度，如:  K ( b i g , p i g ) ∣ ∣ K ( b i g , b i g ) ∣ ∣ ∣ ∣ K ( p i g , p i g ) ∣ ∣ = λ 4 λ 6 + 2 λ 4 λ 6 + 2 λ 4 = λ 4 λ 6 + 2 λ 4 = 1 2 + λ 2 \\begin\{split\} &\\frac\{K(big,pig)\}\{||K(big,big)||||K(pig,pig)||\}\\\\ =&\\frac\{\\lambda^4\}\{\\sqrt\{\\lambda^6+2\\lambda^4\}\\sqrt\{\\lambda^6+2\\lambda^4\}\}\\\\ =&\\frac\{\\lambda^4\}\{\\lambda^6+2\\lambda^4\}=\\frac\{1\}\{2+\\lambda^2\} \\end\{split\} ==∣∣K(big,big)∣∣∣∣K(pig,pig)∣∣K(big,pig)λ6\+2λ4λ6\+2λ4λ4λ6\+2λ4λ4=2\+λ21

2）字符串核函数  \[ ϕ n ( s ) \] μ = ∑ i , s ( i ) = μ λ ( i ) \[\\phi\_n(s)\]\_\{\\mu\}=\\sum\_\{i,s(i)=\\mu\}\\lambda^\{(i)\} \[ϕn(s)\]μ=i,s(i)=μ∑λ(i)

## 18.总结 ##

### 线性支持向量机 ###

\[线性支持向量机\]\{\}

输入:训练集 T = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) \} T=\\\{(x\_1,y\_1),(x\_2,y\_2),\\cdots,(x\_N,y\_N)\\\} T=\{(x1,y1),(x2,y2),⋯,(xN,yN)\}，其中， x i ∈ χ ∈ R n    ,    y i ∈ \{ − 1 , + 1 \} x\_i\\in\\chi\\in R^n\\;,\\;y\_i\\in\\\{-1,+1\\\} xi∈χ∈Rn,yi∈\{ −1,\+1\}。

输出:分离超平面与分类决策函数

算法:

给定惩罚系数 c ≥ 0 c\\geq0 c≥0，构造优化问题  min ⁡ α    1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t .    ∑ i = 1 N α i y i = 0    ,    0 ≤ α i ≤ c    ,    i = 1 , 2 , ⋯   , N \\begin\{split\} &\\min\_\{\\alpha\}\\;\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\alpha\_i\\alpha\_jy\_iy\_j(x\_i\\cdot x\_j)-\\sum\_\{i=1\}^\{N\}\\alpha\_i\\\\ &s.t.\\;\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\;,\\;0\\leq\\alpha\_i\\leq c\\;,\\;i=1,2,\\cdots,N \\end\{split\} αmin21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαis.t.i=1∑Nαiyi=0,0≤αi≤c,i=1,2,⋯,N

求解最优化问题，得到最优解  
 α ∗ = ( α 1 ∗ , α 2 ∗ , ⋯   , α N ∗ ) T \\alpha^\{\*\}=(\\alpha\_1^\{\*\},\\alpha\_2^\{\*\},\\cdots,\\alpha\_N^\{\*\})^T α∗=(α1∗,α2∗,⋯,αN∗)T

根据 α ∗ \\alpha^\{\*\} α∗求解  ω ∗ = ∑ i = 1 N α i ∗ y i x i \\omega^\{\*\}=\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_ix\_i ω∗=i=1∑Nαi∗yixi

挑出符合 0 < α i ∗ < c 0<\\alpha\_i^\{\*\}<c 0<αi∗<c的点 ( x j , y j ) (x\_j,y\_j) (xj,yj)计算:  
 b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) b^\{\*\}=y\_j-\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_i(x\_i\\cdot x\_j) b∗=yj−i=1∑Nαi∗yi(xi⋅xj)

分离超平面为:  ω ∗ ⋅ x + b ∗ = 0 \\omega^\{\*\}\\cdot x+b^\{\*\}=0 ω∗⋅x\+b∗=0

决策函数为:  f ( x ) = s i g n ( ω ∗ ⋅ x + b ∗ ) f(x)=sign(\\omega^\{\*\}\\cdot x+b^\{\*\}) f(x)=sign(ω∗⋅x\+b∗)

### 非线性支持向量机 ###

**\[非线性支持向量机\]**

算法:

给定惩罚系数 c ≥ 0 c\\geq0 c≥0，构造优化问题  min ⁡ α    1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i s . t .    ∑ i = 1 N α i y i = 0    ,    0 ≤ α i ≤ c    ,    i = 1 , 2 , ⋯   , N \\begin\{split\} &\\min\_\{\\alpha\}\\;\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\alpha\_i\\alpha\_jy\_iy\_jK(x\_i,x\_j)-\\sum\_\{i=1\}^\{N\}\\alpha\_i\\\\ &s.t.\\;\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\;,\\;0\\leq\\alpha\_i\\leq c\\;,\\;i=1,2,\\cdots,N \\end\{split\} αmin21i=1∑Nj=1∑NαiαjyiyjK(xi,xj)−i=1∑Nαis.t.i=1∑Nαiyi=0,0≤αi≤c,i=1,2,⋯,N

根据 α ∗ \\alpha^\{\*\} α∗求解  
 ω ∗ = ∑ i = 1 N α i ∗ y i K ( ⋅ , x i ) \\omega^\{\*\}=\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_iK(\\cdot,x\_i) ω∗=i=1∑Nαi∗yiK(⋅,xi)

挑出符合 0 < α i ∗ < c 0<\\alpha\_i^\{\*\}<c 0<αi∗<c的点 ( x j , y j ) (x\_j,y\_j) (xj,yj)计算:  
 b ∗ = y j − ∑ i = 1 N α i ∗ y i K ( x i , x j ) b^\{\*\}=y\_j-\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_iK(x\_i,x\_j) b∗=yj−i=1∑Nαi∗yiK(xi,xj)

决策函数:  f ( x ) = s i g n ( ∑ i = 1 N α i ∗ y i K ( x , x i ) + b ∗ ) f(x)=sign(\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_iK(x,x\_i)+b^\{\*\}) f(x)=sign(i=1∑Nαi∗yiK(x,xi)\+b∗)

其中 x x x为新的实例。

[bc4db724c6424ccfb506b907995df49e.png]: https://img-blog.csdnimg.cn/bc4db724c6424ccfb506b907995df49e.png