1.算法仿真效果
matlab2022a仿真结果如下：
2.算法涉及理论知识概要
SVM通常用对偶问题来求解，这样的好处有两个：1、变量只有N个（N为训练集中的样本个数），原始问题中的变量数量与样本点的特征个数相同，当样本特征非常多时，求解难度较大。2、可以方便地引入核函数，求解非线性SVM。求解对偶问题，常用的算法是SMO，彻底地理解这个算法对初学者有一定难度，本文尝试模拟算法作者发明该算法的思考过程，让大家轻轻松松理解SMO算法。文中的“我”拟指发明算法的大神。
序列最小优化算法（Sequential minimal optimization, SMO）是一种用于解决支持向量机训练过程中所产生优化问题的算法。SMO由微软研究院的约翰·普莱特于1998年发明，被广泛使用于SVM的训练过程中，并在通行的SVM库LIBSVM中得到实现。1998年，SMO算法发表在SVM研究领域内引起了轰动，因为先前可用的SVM训练方法必须使用复杂的方法，并需要昂贵的第三方二次规划工具。而SMO算法较好地避免了这一问题 。
SMO算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。
对偶函数最后的优化问题：
要解决的是在参数上求最大值W的问题，至于和都是已知数。C由我们预先设定，也是已知数。按照坐标上升的思路，我们首先固定除以外的所有参数，然后在上求极值。等一下，这个思路有问题，因为如果固定以外的所有参数，那么将不再是变量（可以由其他值推出），因为问题中规定了。
3.MATLAB核心程序
function alpha = smo(X,y,C,kernel_type,max_iter,epsilon,tolerate)
if (nargin<4)
kernel_type = 'linear';
end
if (nargin<5)
max_iter = 20;
end
if (nargin<6)
epsilon = 1e-3;
end
if (nargin<7)
tolerate = 1e-5;
end
N = size(y,1);
iter_counts = 0;
alpha_change = 100; % a large number
alpha = C*rand(N,1);
while (iter_counts < max_iter && alpha_change>epsilon)
iter_counts = iter_counts + 1;
i = choose_work_set(X,y,alpha,C,kernel_type);
alpha_prev = alpha; % use in check convergence
for j=1:size(alpha,1) % second index
if j==i
continue
end
xi = X(i,:);
xj = X(j,:);
yi = y(i);
yj = y(j);
kappa = K(xi,xi,kernel_type) + K(xj,xj,kernel_type) - 2*K(xi,xj,kernel_type);
if kappa == 0
continue
end
[U,V] = compute_UV(C,alpha(i),alpha(j),yi,yj);
idx = find(alpha>0 & alpha<C);
if isempty(idx)
idx = 1;
else
idx = idx(1);
end
b = y(idx) - sum(alpha.*y.*K(X,X(idx,:),kernel_type));
Ei = sum(alpha.*y.*K(X,xi,kernel_type)) + b - yi;
Ej = sum(alpha.*y.*K(X,xj,kernel_type)) + b - yj;
alpha_j_unc = alpha(j) + (yj*(Ei - Ej))/kappa;
% Fix
if alpha_j_unc > V
alpha_j_new = V;
elseif alpha_j_unc < U
alpha_j_new = U;
else
alpha_j_new = alpha_j_unc;
end
alpha_i_new = alpha(i) + yi*yj*(alpha(j) - alpha_j_new);
alpha(i) = alpha_i_new;
alpha(j) = alpha_j_new;
end
% Check convergence
alpha_change = norm(alpha - alpha_prev);
end
end