1. 数学优化算法实现
1.1 线搜索
线搜索是一种迭代的求得某个函数的最值得方法,对于每次迭代,线搜索会计算得到搜索的方向以及沿这个方向移动的步长。下降方向可以通过多种方法计算,比如说:梯度下降法,牛顿法和拟牛顿法,计算的步长不一定是精确的。
1.1.1 二分法
二分法是最简单的线搜索方法,其主要的思想是在给定范围内取中点,在给定的足够小的值ε左右偏移并计算,然后更新搜索范围。 \[ λ_k = \frac{a_k+b_k}{2} - ε \\ μ_k = \frac{a_k+b_k}{2} + ε \\ if \ \ f(λ) > f(μ_k) \ \ \ a_{k+1}=λ_k \ \ \ b_{k+1}=b_k\\ else \ if \ \ f(λ) < f(μ_k) \ \ \ a_{k+1}=λ_k \ \ \ b_{k+1}=b_k \] 实现二分法的代码如下:
1 | def bisection_search(f, def_field, epsilon): |
1.1.2 四等分搜索
四等分搜索的思想和二分思想相近,取中间三个点的最小值,该点两边两个点为新的区间,最小值落在该区间中。如果有两个相同的最小值,则最小值就在这两个最小值点之间。
实现代码如下
1 | def equal_interval_search(f, def_field, epsilon): |
1.1.3 fibonacci搜索
Fibonacci搜索的主要算法流程如下:
斐波那契搜索的时间复杂度: \(O(n) = log_2n\) 设查找的数组array的大小为m, 查询的值为value
1. 先构建一个”数组元素符合斐波那契数列要求的且第一个大于等于要搜索的数组的大小“的数组F[n]即F[n]-1>=m, F[n]为斐波那契数列
2. 将要查找的数组大小为m的数组array扩展成数组大小为F[n]-1的数组temp。
3. 将array中的值复制给temp,当temp的数组大小大于array时,temp中超出的元素全部复制为array[m-1]
4. 设k=n, low = 0, high = n-1, middle = low + F[n-1]-1
5. 如果temp[middle] == value,则找到需要找的值
6. 如果temp[middle] > value, 则high = middle-1, n = n-1, middle = low + F[n-1]-1
7. 如果 temp[middle] < value, 则low = middle +1,n = n-2, middle = low + F[n-1]-1
8. 重复5、6、7,直到找到或者low>high。
代码实现:
1 | def fibonacci_search(f, def_field, epsilon): |
1.1.4 黄金分割法
三个原则(1)对称取点原则:选取\(x_1,x_2\)使得\(x_1-a=b-x_2\).(2)等比收缩原则:每次迭代时,让被删除的部分与原来区间的比值保持一个定值。(3)单点计算原则:每次迭代都只计算一次函数值。
- step1:给定\(a<b,ε>0\).
- step2:计算\(x_1:=a+0.382(b-a),x_2:=a+b-x_1\).
- step3:计算\(f_1:=f(x_1),f2:=f(x_2)\).
- step4:如果\(f_1>f_2\),则令\(a:=x_1\),若\(b-a<ε\),则转step5;否则令\(f_1:=f_2,x_1:=x_2,x_2:=a+0.618(b-a),f_2:=f(x_2)\),转step4. 否则令\(b:=x2\),若\(b-a<ε\),则转step5;否则令\(f_2:=f_1,x_2:=x_1,x_1:=a+0.382(b-a),f_1:=f(x_1)\),转step4.
- step5:停止,输出\(x^*=(a+b)/2\).
代码实现
1 | def golden_section_search(f, def_field, epsilon, args=None): |
1.1.5 非精确搜索
这里使用的是多项式拟合法,多项式\(y=a_0+a_x+a_2x^2+...+a_nx^n=\sum_{i=0}^na_ix^i\)
考虑输入样本数据如下: \[ x={[x_1,x_2,...,x_m]}^T\\ y={[y_1,y_2,...,y_n]}^T\\ \] 构建方程组: \[ y_1=a_0+a_1x_1+a_2x_1^2+...+a_nx_1^n\\ y_2=a_0+a_1x_2+a_2x_2^2+...+a_nx_2^n\\ ...\\ y_m=a_0+a_1x_m+a_2x_m^2+...+a_nx_m^n\\ \] 令: \[ A=\left(\begin{array}{ccccc}1 & x_{1} & x_{1}^{2} & \cdots & x_{1}^{n} \\ 1 & x_{2} & x_{2}^{2} & \cdots & x_{2}^{n} \\ \vdots & \vdots & \vdots & \cdots & \vdots \\ 1 & x_{m} & x_{m}^{2} & \cdots & x_{m}^{n}\end{array}\right)\\ b=\left(\begin{array}{c}a_{0} \\ a_{1} \\ \vdots \\ a_{n}\end{array}\right)\\ f=\left(\begin{array}{c}y 1 \\ y_{2} \\ \vdots \\ y_{m}\end{array}\right) \] 令\(Ab=f\),拟合的过程就是求解b,按照数学表达式来看,\(b=A^{-1}f\),A可逆的时候可以直接求解,当不可逆的时候可以考虑正交分解:\(A_{[m,n+1]}=Q_{[m,n+1]}R_{[n+1,n+1]}\)
代码实现如下:
1 | def quadratic_polynomial(f, x0, v): |
1.1.6 对比分析
这里对二分搜索和四等分搜索使用的函数是\(f_1(x)=8x^3-2x^2-7x+3\),Fibonacci搜索使用的函数是\(f_2(x)=x^2-6x+2\),黄金分割法使用的函数是\(f_4(x)=e^x-5x\),对于非精确线搜索检验了\(f_1(X),f_3(x)\)。得到的结果如下图所示。
1.2 牛顿法的实现
1.2.1 牛顿法
牛顿法的基本思想是用一个二次函数去近似目标函数f(x),然后精确地求出这个二次函数的极小点作为新的迭代点。
二次函数的选取:\(f(x_k+s)≈f(x_k)+▽f(x_k)^Ts+\frac{1}{2}s^T▽^2f(x_k)s=:m_k(s)\)
迭代方向的选择:\(d_k^N:=arg \ min\ m_k(s)\)
牛顿方程:\(▽^2f(x_k)s+▽f(x_k)=0\)
牛顿方向:\(d_k^N=-{[▽^2f(x_k)]}^{-1}▽f(x_k)=0\)
牛顿步:\(x_{k+1}x_k-G_k^{-1}g_k\)
牛顿法的基本步骤:
- 取初始点\(x_0\)及精确参数\(ε≥0\),令\(k=0\)
- 若\(||g_k||≤ε\),算法终止,否则进入下一步
- 令\(x_{k+1}=x_k-G_k^{-1}g_k,k=k+1\),转步骤2
1.2.2 拟牛顿法
牛顿法的搜索方向是\(d^{t}=-G_k^{-1}g_t\),拟牛顿法要做的就是不计算二阶导及其逆矩阵,设法构造一个矩阵U,使得其逼近\(G_k^{-1}\)。假设\(f(x)\)是二次函数,于是Hesse矩阵的G是个常数矩阵,任意两点\(x^{(k)}\)和\(x^{(k+1)}\)处的梯度之差是: \[ \nabla f\left(x^{(k+1)}\right)-\nabla f\left(x^{(k)}\right)=G \cdot\left(x^{(k+1)}-x^{(k)}\right)\\ => \ x^{(k+1)}-x^{(k)}=G^{-1} \cdot\left[\nabla f\left(x^{(k+1)}\right)-\nabla f\left(x^{(k)}\right)\right]\\ => \ x^{(k+1)}-x^{(k)}=G_{k+1} \cdot\left[\nabla f\left(x^{(k+1)}\right)-\nabla f\left(x^{(k)}\right)\right]\\ or \ \Delta x_{k}=G_{k+1} \cdot \Delta g_{k} \] 这就是拟牛顿法,不同的拟牛顿法区别就在于如何确定U。
- DFP法
令G=D,假设已知\(D_t\),希望用叠加的方式求\(D_{t+1}\),即\(D_{t+1}=D_t+ΔD_t\),带入得到:\(\Delta D_{t} \Delta g_{t}=\Delta x_{t}-D_{t} \Delta g_{t}\)
假设满足这个等式的:\(\Delta D_{t}=\Delta x_{t} \cdot q_{t}^{T}-D_{t} \Delta g_{t} \cdot w_{t}^{T}\)
首先,通过对比发现:\(q_{t}^{T} \cdot \Delta g_{t}=w_{t}^{T} \cdot \Delta g_{t}=I_{n}\)
其次,要保证\(ΔD_t\)是对称的,参照\(ΔD_t\)的表达式,最简单的是令:\(q_{t}=\alpha_{t} \Delta x_{t}\),\(w_{t}=\beta_{t} D_{t} \Delta g_{t}\)
第二个条件带入第一个得到:
\(\begin{aligned} \alpha_{t} &=\frac{1}{\Delta g_{t}^{T} \Delta x_{t}} \\ \beta_{t} &=\frac{1}{\Delta g_{t}^{T} D_{t} \Delta g_{t}} \end{aligned}\)
然后带回\(ΔD_t\)的表达式:\(\Delta D_{t}=\frac{\Delta x_{t} \Delta x_{t}^{T}}{\Delta g_{t}^{T} \Delta x_{t}}-\frac{D_{t} \Delta g_{t} \Delta g_{t}^{T} D_{t}}{\Delta g_{t}^{T} D_{t} \Delta g_{t}}\)
以上算法的复杂度是\(O(n^2)\)
DFP算法的流程:
给定初始点\(x^{(0)}\),误差ε,令\(D_0=I_n,t=0\)
计算搜索方向\(d^{(t)}=-D_t^{-1}g_t\)
从点\(x^{(t)}\)出发,沿着\(d^{(t)}\)做一维搜索,获得最优步长并更新参数: \[ \lambda_{t}=\arg \min _{\lambda} f\left(x^{(t)}+\lambda \cdot d^{(t)}\right)\\ x^{(t+1)}=x^{(t)}+\lambda_{t} \cdot d^{(t)} \]
若\(|g_{t+1}|<ε\),就停止迭代,否则转5
计算\(Δg=g_{t+1}-g_t,Δx=x^{(t+1)}-x^{(t)}\),更新G \[ D_{t+1}=D_{t}+\frac{\Delta x \Delta x^{T}}{\Delta g^{T} \Delta x}-\frac{D_{t} \Delta g \Delta g^{T} D_{t}}{\Delta g^{T} D_{t} \Delta g} \]
令\(t=t+1\),转2
- BFGS
拟牛顿条件是: \[ \Delta x_{t}=B_{t+1}^{-1} \cdot \Delta g_{t} \\ \Delta g_{t}=B_{t+1} \cdot \Delta x_{t} \] BFGS与BFP是对偶的,所以迭代公式只要把\(Δx_t\)和\(Δg_t\)调换一下就好。 \[ \Delta B_{t}=\frac{\Delta g_{t} \Delta g_{t}^{T}}{\Delta x_{t}^{T} \Delta g_{t}}-\frac{B_{t} \Delta x_{t} \Delta x_{t}^{T} B_{t}}{\Delta x_{t}^{T} B_{t} \Delta x_{t}} \] 为了不计算求逆,引入Sherman-Morrison公式: \[ \left(A+u v^{T}\right)^{-1}=A^{-1}-\frac{\left(A^{-1} u\right)\left(v^{T} A^{-1}\right)}{1+v^{T} A^{-1} u}\\ => B_{t+1}^{-1}=\left(I_{n}-\frac{\Delta x_{t} \Delta g_{t}^{T}}{\Delta x_{t}^{T} \Delta g_{t}}\right) B_{t}^{-1}\left(I_{n}-\frac{\Delta g_{t} \Delta x_{t}^{T}}{\Delta x_{t}^{T} \Delta g_{t}}\right)+\frac{\Delta x_{t} \Delta x_{t}^{T}}{\Delta x_{t}^{T} \Delta g_{t}} \] 以下是BFGS的算法步骤:
给定初始点\(x^{(0)}\),误差ε,令\(B_0=I_n,t=0\)
计算搜索方向\(d^{(t)}=-B_t^{-1}g_t\)
从点\(x^{(t)}\)出发,沿着\(d^{(t)}\)做一维搜索,获得最优步长并更新参数: \[ \lambda_{t}=\arg \min _{\lambda} f\left(x^{(t)}+\lambda \cdot d^{(t)}\right)\\ x^{(t+1)}=x^{(t)}+\lambda_{t} \cdot d^{(t)} \]
若\(|g_{t+1}|<ε\),就停止迭代,否则转5
计算\(Δg=g_{t+1}-g_t,Δx=x^{(t+1)}-x^{(t)}\),更新\(B^{-1}\),然后 \[ B_{t+1}^{-1}=\left(I_{n}-\frac{\Delta x_{t} \Delta g_{t}^{T}}{\Delta x_{t}^{T} \Delta g_{t}}\right) B_{t}^{-1}\left(I_{n}-\frac{\Delta g_{t} \Delta x_{t}^{T}}{\Delta x_{t}^{T} \Delta g_{t}}\right)+\frac{\Delta x_{t} \Delta x_{t}^{T}}{\Delta x_{t}^{T} \Delta g_{t}} \]
令\(t=t+1\),转2
1.2.3 代码实现
代码实现见'.py',测试所用的函数为\(f=4x_1x_2+2x_1x_2+2x_2^2+x_1+x_2\)
1.3 最速下降法
最速下降法的原理相较于牛顿法更简单,它是使用函数的一阶特性的,搜索方向是\(d_k=-▽f(x_k)\),算法的基本框架如下:
- 取初始点\(x_0\)及精确参数\(ε≥0\),令\(k=0\)
- 若\(||g_k||≤ε\),算法终止,否则进入下一步
- 取\(d_k=-g_k\),利用线搜索步长规则选取步长\(α_k\)
- 令\(x_{k+1}=x_k+α_kd_k,k=k+1\),转步骤2
代码实现见'.py',测试所用的函数为\(f=\frac{1}{2}(x_1^2+2x_2^2)\),得到结果如下所示
1.4 共轭梯度法
1.4.1 线性共轭方向法
共轭方向:设A是nxn对称正定矩阵,若非零向量\(d_1,d_2,...,d_n\)关于A共轭,那么满足\(d_i^TAd_j=0,i≠j\)
线性共轭方向法基本框架:
- 取初始点\(x_0\)和搜索方向\(d_0\)满足\((d_0,g_0)<0\),精度参数\(ε≥0\),令\(k=0\)
- 若\(||g_k||≤ε\),算法终止,否则进入下一步
- 计算步长\(α_k=arg \ min \ f(x_k+αd_k)\)
- 令\(x_{k+1}=x_{k}+α_kd_k\)
- 求\(d_{k+1}\),使得\(d_{k+1}\)与\(d_0,d_1,...,d_k\)关于A共轭,令\(k=k+1\),返回步骤2
1.4.2 线性共轭梯度法
迭代公式有:
线性组合系数:\(\beta_{k-1}=\frac{g_{k}^{T} g_{k}}{g_{k-1}^{T} g_{k-1}}\)
共轭搜索方向:\(d_{k}=-g_{k}+\beta_{k-1} d_{k-1}\)
精确线搜索步长:\(\alpha_{k}=\frac{g_{k}^{T} g_{k}}{d_{k}^{T} A d_{k}}\)
新的迭代点:\(x_{k+1}=x_{k}+\alpha_{k} d_{k}\)
算法的整体框架如下:
- 取初始点\(x_0\)及终止参数\(ε≥0\),计算\(g_0=Ax_0-b,d_0=-g_0\),令k=0
- 若\(||g_k||≤ε\),算法终止,否则进入下一步
- 依次计算:\(\alpha_{k}=\frac{g_{k}{ }^{T} g_{k}}{d_{k}{ }^{T} A d_{k}}, x_{k+1}=x_{k}+\alpha_{k} d_{k}\),\(g_{k+1}=A x_{k+1}-b, \beta_{k}=\frac{g_{k+1}^{T} g_{k+1}}{g_{k}^{T} g_{k}}, d_{k+1}=-g_{k+1}+\beta_{k} d_{k}\),令\(k=k+1\),转到步骤2.
1.4.3 实现
代码实现见'.py',测试的函数是\(f=1+x_1-x_2+x_1^2+2x_2^2\),测试的结果如下所示。
2. 机器学习优化器的实现
一般地,机器学习优化器中定义的参数有:待优化的参数θ,目标函数\(J(θ)\),以及学习率α。优化算法的分类主要有固定学习率和自适应学习率两种算法。固定学习率的算法主要有:BGD、SGD、SGDM、NAG;自适应学习率算法主要有:AdaGrad、AdaDelta、Adam、Nadam。目前使用的最多的两种优化器是SGD和Adam。
以下是各种算法的对比:
算法 | 优点 | 缺点 | 适用情况 |
---|---|---|---|
BGD | 目标函数为凸函数时,可以找到全局最优解 | 收敛速度慢,需要用到全部数据,内存消耗大 | 不适用于大规模数据集,不能在线更新 |
SGD | 避免冗余数据的干扰,收敛速度加快,能过够在线学习 | 更新值的方差较大,收敛过程中可能落入鞍点,选择合适的学习率可能比较困难 | 适用于需要在线更新的模型,适用于大规模训练样本的情况(在NLP和网络表示学习很常用) |
Momentum | 能够在相关方向加速SGD,抑制震荡,从而加快收敛 | 需要人工设定学习率 | 适用于有可靠的初始化参数 |
Adagrad | 实现学习率的自动更改 | 仍依赖于人工设置一个全局学习率,中后期的梯度接近于0,使得训练提前结束 | 需要加快收敛,训练复杂网络时,适用于处理稀疏梯度 |
Adadelta | 不需要预设一个默认的学习率,训练初中期加速效果不错,可以避免参数更新时两边单位不统一的问题 | 在局部极小值附近震荡,可能不收敛 | 需要加快收敛,训练复杂网络时 |
Adam | 速度快,对内存需求较小,为不同的参数计算不同的自适应学习率 | 在局部极小值附近震荡,可能不收敛 | 需要加快收敛,训练复杂网络时,善于处理稀疏梯度和处理非平稳目标的优点,也适用于大多非凸优化的问题,适用于大数据集和高维空间 |
以下实现几种常见的优化器。
2.1 BGD(批量梯度下降)
假设训练样本的总数为m,样本为\({(x^1,y^1),...,(x^n,y^n)}\),模型参数为\(θ\),损失函数为\(J(θ)\),在第i个样本\(x^i,y^i\)上损失函数关于参数的梯度为\(▽_θJ_i(θ,x^i,y^i)\),学习率为α,使用BGD更新参数为: \[ \theta_{t+1}=\theta_{t}-\frac{1}{m}\alpha_{t} \cdot \sum_{i=1}^{n} \nabla_{\theta} J_{i}\left(\theta, x^{i}, y^{i}\right) \] 由于每一次进行参数的更新,将计算整个数据集样本上的所有数据,导致运算速度很慢,尤其是对于大样本的数据集。但是由于下降的方向是总体的平均梯度,所以将会得到一个全局最优解。
代码实现,这里测试的优化目标函数是\(y=x_1+2x^2\)这一凸优化问题。
1 | def bgd_multi(): |
2.2 SGD(随机梯度下降)
随机梯度下降不像SGD那样每次对全部的样本进行运算,而是每次更新时只选择一个样本\((x^i,y^i)\)计算其梯度,参数更新公式为: \[ \theta_{t+1}=\theta_{t}-\alpha \cdot \nabla_{\theta} J_{i}\left(\theta, x^{i}, y^{i}\right) \] SGD由于每次参数更新仅仅需要一个样本的梯度,训练速度很快,由于每次迭代并不是都向着整体最优的方向,导致梯度的波动非常大,更容易从一个局部最优跳到另一个局部最优,准确率下降。所以对于SGD,学习率选择比较困难,学习率太高的话就会波动过大,所有的参数都是用的相同的学习率
代码实现:
1 | def sgd(): |
2.3 Momentum-SGD(带动量的SGD)
Momentum的算法思想是:参数更新时在一定程度上保留之前更新的方向,同时又利用当前batch的梯度微调最终的更新方向,简言之就是通过积累之前的动量来加速当前的梯度。其算法的迭代公式为: \[ g= momentum * g+\alpha\left(h_{\theta}\left(x^{i}\right)-y^{i}\right) x^{i}\\ \theta_{j}=\theta_{j}-g \] 代码实现:
1 | def Momentum_sgd(): |
2.4 Adam算法
Adam是一种自适应学习率的方法,在Momentum的一阶矩估计的基础上加上了二阶矩估计。利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。
Adam的算法流程如下,具体可以见论文《Adam : A Method for Stochastic Optimization》。
1 | def adam(): |
2.5 对比
对同一个函数\(y=x_1+2x^2\)进行这四种优化器的测试,得到如下的结果:
将损失函数画在同一副图中,得到以下的结果:
3. 最优化在机器学习中的应用
这里主要介绍的是SVM算法的实现。支持向量机(SVM)是一种监督学习方式对数据进行二元分类的广义线性分类器,其决策边界时对学习样本求解的最大边距超平面。
超平面是在样本空间中的一个平面,在多维空间中,超平面可以用向量的形式表现为\(\vec{w} \vec{x}+b=0\),记作\((\vec{w},b)\)的形式,其中\(\vec{w}\)是法向量,而b为移位项。考虑任意一点\(\vec{x}\)到超平面之间的距离,可以表示为:\(γ=\frac{\vec{w} \cdot \vec{x} + b}{||\vec{w}||}\),超平面能将样本空间划分为两个部分。假设超平面\((\vec{w},b)\)将所有的样本正确分类,即对于任意的\((\vec{x_i},y_i)∈D\),若\(y_i=+1\),那么\(\vec{w} \cdot \vec{x}+b<0\)。
对于\((\vec{x_i},y_i)∈D\),可以将上面的距离公式的分子部分带入\(y_i\)改写成:\(\gamma_{i}=\frac{y_{i}(\vec{w} \cdot \vec{x}+b)}{\|\vec{w}\|}\),定义间隔γ为所有样本中离超平面最近的那个,即\(γ=min \ γ_i\),那么\(γ_i≥γ\)总是成立的,带入上式可得:\(\frac{y_{i}(\vec{w} \cdot \vec{x}+b)}{\|\vec{w}\|} \geq \gamma\)。
因此,SVM的问题就变成了找到最大间隔的超平面,使得γ最大,即: \[ \max _{(\vec{w}, b)} \min _{i} \frac{1}{\|\vec{w}\|}\left|\vec{w} \cdot \vec{x}_{i}+b\right|\\ s.t. \quad y_{i}\left(\vec{w} \cdot \vec{x}_{i}+b\right)>0, \quad i=1,2, \ldots, m \] 因为间隔始终大于0.即\(|\vec{w} \cdot \vec{x_i}+n|>0\),则可以通过缩放\((\vec{w},b)\)使得:\(\min _{i}\left|\vec{w} \cdot \vec{x}_{i}+b\right|=1\),那么上面的问题就变成了\(max \ \frac{1}{||\vec{w}||}\),上式可以重写为: \[ \min \frac{1}{2}\|\vec{w}\|^{2}\\ s.t. \quad y_{i}\left(\vec{w} \cdot \overrightarrow{x_{i}}+b\right) \geq 1, \quad i=1,2, \ldots, m \] 是一个凸二次规划问题,这样就能用现有的求解优化问题的方法。
将SVM的问题用拉格朗日函数的形式重写为: \[ \mathcal{L}(\vec{w}, b, \vec{\alpha})=\underbrace{\frac{1}{2}\|\vec{w}\|^{2}}_{f(\vec{w}, b)}+\sum \alpha_{i} \underbrace{\left(1-y_{i}\left(\vec{w} \cdot \vec{x}_{i}-b\right)\right)}_{h_{i}(\vec{w}, b) \leq 0} \] 令\(L(\vec{w},b,\vec{α})\)对于\(\vec{w}\)和\(b\)的偏导数等于0: \[ \left\{\begin{array}{l}\frac{\partial \mathcal{L}}{\partial \vec{w}}=\vec{w}-\sum \alpha_{i} y_{i} \vec{x}_{i}=0 \\ \frac{\partial \mathcal{L}}{\partial b}=\sum \alpha_{i} y_{i}=0\end{array}\right. \] 可得: \[ \begin{aligned} \vec{w} &=\sum \alpha_{i} y_{i} \vec{x}_{i} \\ 0 &=\sum \alpha_{i} y_{i} \end{aligned} \] 将上式带入\(L(\vec{w},b,\vec{α})\)可得: \[ \begin{aligned} \mathcal{L}(\vec{w}, b, \vec{\alpha})=& \frac{1}{2}\left(\sum \alpha_{i} y_{i} \vec{x}_{i}\right) \cdot\left(\sum \alpha_{i} y_{i} \overrightarrow{x_{i}}\right) \\ &\left.+\sum \alpha_{i}\left(1-y_{i}\left(\left(\sum \alpha_{i} y_{i} \overrightarrow{x_{i}}\right) \cdot \overrightarrow{x_{i}}-b\right)\right)\right) \\=& \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\overrightarrow{x_{i}} \cdot \overrightarrow{x_{j}}\right) \end{aligned} \] 这样对偶问题就变成: \[ \begin{aligned} & \max _{\vec{\alpha} \geq 0} \min _{\vec{z}} \mathcal{L}(\vec{z}, \vec{\alpha}) \\ \Longrightarrow & \max _{\vec{\alpha} \geq 0} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\vec{x}_{i} \cdot \vec{x}_{j}\right) \\ & \text { s.t. } \quad \sum \alpha_{i} y_{i}=0, \alpha_{i} \geq 0 \end{aligned} \] 解出\(\vec{α}\)后,求出\(\vec{w}\)与b即可得到模型: \[ \begin{aligned} f(\vec{x}) &=\vec{w} \cdot \vec{x}+b \\ &=\sum_{i=1}^{m} \alpha_{i} y_{i}\left(\vec{x}_{i} \cdot \vec{x}\right)+b \end{aligned} \] 还需要满足上面提到的KKT条件: \[ \left\{\begin{array}{l}\alpha_{i} \geq 0 \\ y_{i} f\left(\vec{x}_{i}\right)-1 \geq 0 \\ \alpha_{i}\left(y_{i} f\left(\vec{x}_{i}\right)-1\right)=0\end{array}\right. \]
软间隔
上面我们考虑的都是数据可以分隔的情况,那么当数据集并不是完全能被超平面分隔,即有些点不满足约束\(y_i(\vec{w} \cdot \vec{x_i}+b)≥1\),那么可以设定一个惩罚项: \[ \xi_{i}=\max \left\{1-y_{i}\left(\vec{w} \cdot \vec{x}_{i}+b\right), 0\right\} \] 那么原来的 SVM 的优化问题就会变成: \[ \min _{\vec{w}, b} \frac{1}{2}\|\vec{w}\|^{2}+C \sum_{i=1}^{m} \max \left\{1-y_{i}\left(\vec{w} \cdot \vec{x}_{i}+b\right), 0\right\}\\ s.t. \quad 1-y_{i}\left(\vec{w} \cdot \vec{x}_{i}+b\right) \leq 0, \quad i=1,2, \ldots, m \] 其中的 \(\max(1-z, 0)\) 称为“折页损失”(hinge loss)。接着引入“松弛变量” \(ξ_i≥0\),将上式重写为: \[ \begin{array}{ll} & \min _{\vec{w}, b} \frac{1}{2}\|\vec{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ \text { s.t. } & y_{i}\left(\vec{w} \cdot \vec{x}_{i}+b\right) \geq 1-\xi_{i} \\ & \xi_{i} \geq 0, i=1,2, \ldots, m\end{array} \]
核方法
当遇到样本是非线性可分时,一般的线性 SVM 就无法很好的分类,这时候可以采用核技巧(kernel trick),将样本映射至高维空间,变成高维空间中线性可分的即可。
考虑一个映射函数$ ()$,将 dd 维特征映射至 m 维: \[ \phi(\vec{x}): \mathbb{R}^{d} \rightarrow \mathbb{R}^{m} \] 定义核函数: \[ K\left(\vec{x}_{i}, \vec{x}_{j}\right)=\phi\left(\vec{x}_{i}\right) \cdot \phi\left(\vec{x}_{j}\right) \] 核技巧的思想是用核函数 K 避免在高维 mm 空间中计算映射函数的内积,这样能够极大简化运算。函数 K 能够满足成为核函数的充分必要条件是 K是半正定,即: \[ \sum_{i, j=1}^{m} c_{i} c_{j} K\left(\vec{x}_{i}, \overrightarrow{x_{j}}\right) \geq 0 \] 常用的核函数有多项式核函数(Polynomial function): \[ K\left(\vec{x}_{i}, \vec{x}_{j}\right)=\left(\overrightarrow{x_{i}} \cdot \overrightarrow{x_{j}}+1\right)^{d} \] 以及高斯核函数(Guassian radial basis function),通常称为 RBF Kernel: \[ K\left(\vec{x}_{i}, \vec{x}_{j}\right)=\exp \left(-\frac{\left\|\vec{x}_{i}-\vec{x}_{j}\right\|^{2}}{2 \sigma^{2}}\right) \]
代码实现
这里使用SVM实现了一个简单的二分类问题,使用的数据集如下图所示,标签只有(-1,1),两个维度表示其特征。
实现的代码位于'OptimizationHomework-Demo',实验的结果如下所示,SVM能很好的分类数据集中的数据。