多分类支持向量机是由k个支持向量机构成，当输入一个样本，分别输出k个概率，样本属于概率最大的那个类。

 

1.多分类支持向量机Multiclass Support Vector Machine (SVM)


其评分函数为:$f(\omega)=\omega x+b$
在此用到的都是支持向量机的原始形式，没有核方法也没有使用SMO算法。无约束原始优化问题。
常用的多分类支持向量机有One-Vs-All(OVA)，All-Vs-All,Structured SVM，其中OVA比较简单。
多分类支持向量机对第i个类的损失函数是$L_i=\sum\limits_{j\neq y_i}max({0,s_j-s_{y_i}-\Delta})$,若$s_j$不是比$s_{y_i}$还小$\Delta$，或者 $s_j$比$s_{y_i}$还大，那就要对其评分进行惩罚。这样就是说,到最后，正确类别的分数要比错误分类的分数至少大$\Delta$。 阈值为0的max(0,-)函数也被称为合页损失函数(hingle loss)。 

$L =  \underbrace{ \frac{1}{N} \sum_i L_i }_\text{data loss} + \underbrace{ \lambda R(W) }_\text{regularization loss}$
data loss中的超参数$\Delta$和正则化前面的超参数$\lambda$看似无关，其实它们两个之间相互影响。使用小的间隔$\Delta$时，将会压缩$\omega$的值在较小的区间上，正则化损失也就会变小，反之亦然。
和二分类支持向量机之间的关系，二分类支持向量机的损失函数$L_i = C \max(0, 1 - y_i w^Tx_i) + R(W)$,C也是一个超参数，$C \propto \frac{1}{\lambda}$.




2.Python 实现


  
训练数据获取地址:https://raw.githubusercontent.com/lxrobot/General-source-code/master/SVM/data216x197.npy


#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 29 17:15:25 2018
@author: rd
"""
from __future__ import division
import numpy as np
"""
This dataset is part of MNIST dataset,but there is only 3 classes,
classes = {0:'0',1:'1',2:'2'},and images are compressed to 14*14 
pixels and stored in a matrix with the corresponding label, at the 
end the shape of the data matrix is 
num_of_images x 14*14(pixels)+1(lable)
"""
def load_data(split_ratio):
    tmp=np.load("data216x197.npy")
    data=tmp[:,:-1]
    label=tmp[:,-1]
    mean_data=np.mean(data,axis=0)
    train_data=data[int(split_ratio*data.shape[0]):]-mean_data
    train_label=label[int(split_ratio*data.shape[0]):]
    test_data=data[:int(split_ratio*data.shape[0])]-mean_data
    test_label=label[:int(split_ratio*data.shape[0])]
    return train_data,train_label,test_data,test_label

"""compute the hingle loss without using vector operation,
While dealing with a huge dataset,this will have low efficiency
X's shape [n,14*14+1],Y's shape [n,],W's shape [num_class,14*14+1]"""
def lossAndGradNaive(X,Y,W,reg):
    dW=np.zeros(W.shape)
    loss = 0.0
    num_class=W.shape[0]
    num_X=X.shape[0]
    for i in range(num_X):
        scores=np.dot(W,X[i])        
        cur_scores=scores[int(Y[i])]
        for j in range(num_class):
            if j==Y[i]:
                continue
            margin=scores[j]-cur_scores+1
            if margin>0:
                loss+=margin
                dW[j,:]+=X[i]
                dW[int(Y[i]),:]-=X[i]
    loss/=num_X
    dW/=num_X
    loss+=reg*np.sum(W*W)
    dW+=2*reg*W
    return loss,dW

def lossAndGradVector(X,Y,W,reg):
    dW=np.zeros(W.shape)
    N=X.shape[0]
    Y_=X.dot(W.T)
    margin=Y_-Y_[range(N),Y.astype(int)].reshape([-1,1])+1.0
    margin[range(N),Y.astype(int)]=0.0
    margin=(margin>0)*margin
    loss=0.0
    loss+=np.sum(margin)/N
    loss+=reg*np.sum(W*W)
    """For one data,the X[Y[i]] has to be substracted several times"""
    countsX=(margin>0).astype(int)
    countsX[range(N),Y.astype(int)]=-np.sum(countsX,axis=1)
    dW+=np.dot(countsX.T,X)/N+2*reg*W
    return loss,dW

def predict(X,W):
    X=np.hstack([X, np.ones((X.shape[0], 1))])
    Y_=np.dot(X,W.T)
    Y_pre=np.argmax(Y_,axis=1)
    return Y_pre

def accuracy(X,Y,W):
    Y_pre=predict(X,W)
    acc=(Y_pre==Y).mean()
    return acc

def model(X,Y,alpha,steps,reg):
    X=np.hstack([X, np.ones((X.shape[0], 1))])
    W = np.random.randn(3,X.shape[1]) * 0.0001
    for step in range(steps):
        loss,grad=lossAndGradNaive(X,Y,W,reg)
        W-=alpha*grad
        print"The {} step, loss={}, accuracy={}".format(step,loss,accuracy(X[:,:-1],Y,W))
    return W

train_data,train_label,test_data,test_label=load_data(0.2)
W=model(train_data,train_label,0.0001,25,0.5)
print"Test accuracy of the model is {}".format(accuracy(test_data,test_label,W))

>>>python linearSVM.py
The 0 step, loss=2.13019790746, accuracy=0.913294797688
The 1 step, loss=0.542978231611, accuracy=0.924855491329
The 2 step, loss=0.414223869196, accuracy=0.936416184971
The 3 step, loss=0.320119455456, accuracy=0.942196531792
The 4 step, loss=0.263666138421, accuracy=0.959537572254
The 5 step, loss=0.211882339467, accuracy=0.959537572254
The 6 step, loss=0.164835849395, accuracy=0.976878612717
The 7 step, loss=0.126102746496, accuracy=0.982658959538
The 8 step, loss=0.105088702516, accuracy=0.982658959538
The 9 step, loss=0.0885842087354, accuracy=0.988439306358
The 10 step, loss=0.075766608953, accuracy=0.988439306358
The 11 step, loss=0.0656638756563, accuracy=0.988439306358
The 12 step, loss=0.0601955544228, accuracy=0.988439306358
The 13 step, loss=0.0540709950467, accuracy=0.988439306358
The 14 step, loss=0.0472173965381, accuracy=0.988439306358
The 15 step, loss=0.0421049154242, accuracy=0.988439306358
The 16 step, loss=0.035277229437, accuracy=0.988439306358
The 17 step, loss=0.0292794459009, accuracy=0.988439306358
The 18 step, loss=0.0237297062768, accuracy=0.994219653179
The 19 step, loss=0.0173572330624, accuracy=0.994219653179
The 20 step, loss=0.0128973291068, accuracy=0.994219653179
The 21 step, loss=0.00907220930146, accuracy=1.0
The 22 step, loss=0.0072871437553, accuracy=1.0
The 23 step, loss=0.00389257560805, accuracy=1.0
The 24 step, loss=0.00347981408653, accuracy=1.0
Test accuracy of the model is 0.976744186047

1、导入必要的编程库；
import matplotlib.pyplot as plt
import numpy as np
import tensorflow as tf
from sklearn import datasets

sess = tf.Session()

2、加载iris数据集并为每类分离目标值；
iris = datasets.load_iris()
x_vals = np.array([[x[0], x[3]] for x in iris.data])
y_vals1 = np.array([1 if y==0 else -1 for y in iris.target])
y_vals2 = np.array([1 if y==1 else -1 for y in iris.target])
y_vals3 = np.array([1 if y==2 else -1 for y in iris.target])
y_vals = np.array([y_vals1, y_vals2, y_vals3])
class1_x = [x[0] for i,x in enumerate(x_vals) if iris.target[i]==0]
class1_y = [x[1] for i,x in enumerate(x_vals) if iris.target[i]==0]
class2_x = [x[0] for i,x in enumerate(x_vals) if iris.target[i]==1]
class2_y = [x[1] for i,x in enumerate(x_vals) if iris.target[i]==1]
class3_x = [x[0] for i,x in enumerate(x_vals) if iris.target[i]==2]
class3_y = [x[1] for i,x in enumerate(x_vals) if iris.target[i]==2]


3、设置占位符等；
batch_size = 50
x_data = tf.placeholder(shape=[None, 2], dtype=tf.float32)
y_target = tf.placeholder(shape=[3, None], dtype=tf.float32)
prediction_grid = tf.placeholder(shape=[None, 2], dtype=tf.float32)
b = tf.Variable(tf.random_normal(shape=[3,batch_size]))


4、计算高斯核函数；
gamma = tf.constant(-10.0)
dist = tf.reduce_sum(tf.square(x_data), 1)
dist = tf.reshape(dist, [-1,1])
sq_dists = tf.multiply(2., tf.matmul(x_data, tf.transpose(x_data)))
my_kernel = tf.exp(tf.multiply(gamma, tf.abs(sq_dists)))

5、最大变化是批量矩阵乘法
def reshape_matmul(mat):
    v1 = tf.expand_dims(mat,1)
    v2 = tf.reshape(v1,[3,batch_size,1])
    return (tf.matmul(v2,v1))

6、计算对偶损失函数
first_term = tf.reduce_sum(b)
b_vec_cross = tf.matmul(tf.transpose(b), b)
y_target_cross = reshape_matmul(y_target)

second_term = tf.reduce_sum(tf.multiply(my_kernel, tf.multiply(b_vec_cross,y_target_cross)))
loss = tf.negative(tf.subtract(first_term, second_term))

7、创建预测函数
rA = tf.reshape(tf.reduce_sum(tf.square(x_data),1),[-1,1])
rB = tf.reshape(tf.reduce_sum(tf.square(prediction_grid),1),[-1,1])
pred_sq_dist = tf.add(tf.subtract(rA, tf.multiply(2., tf.matmul(x_data, tf.transpose(prediction_grid)))),tf.transpose(rB))
pred_kernel = tf.exp(tf.multiply(gamma, tf.abs(pred_sq_dist)))

prediction_output = tf.matmul(tf.multiply(y_target,b), pred_kernel)
prediction = tf.arg_max(prediction_output-tf.expand_dims(tf.reduce_mean(prediction_output,1), 1), 0)
accuracy = tf.reduce_mean(tf.cast(tf.equal(prediction, tf.argmax(y_target,0)), tf.float32))


8、初始化优化器，开始迭代

my_opt = tf.train.GradientDescentOptimizer(0.01)
train_step = my_opt.minimize(loss)
init = tf.global_variables_initializer()
sess.run(init)

loss_vec = []
batch_accuracy = []

for i in range(1000):
    rand_index = np.random.choice(len(x_vals), size=batch_size)
    rand_x = x_vals[rand_index]
    rand_y = y_vals[:,rand_index]
    sess.run(train_step, feed_dict={x_data: rand_x, y_target: rand_y})
    
    temp_loss = sess.run(loss, feed_dict={x_data: rand_x, y_target: rand_y})
    loss_vec.append(temp_loss)
    
    acc_temp = sess.run(accuracy, feed_dict={x_data: rand_x,
                                             y_target: rand_y,
                                             prediction_grid:rand_x})
    batch_accuracy.append(acc_temp)
    
    if (i+1)%25==0:
        print('Step #' + str(i+1))
        print('Loss = ' + str(temp_loss))

9、创建数据点的预测网络，运行预测网络
x_min, x_max = x_vals[:, 0].min() - 1, x_vals[:, 0].max() + 1
y_min, y_max = x_vals[:, 1].min() - 1, x_vals[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
                     np.arange(y_min, y_max, 0.02))
grid_points = np.c_[xx.ravel(), yy.ravel()]
grid_predictions = sess.run(prediction, feed_dict={x_data: rand_x,
                                                   y_target: rand_y,
                                                   prediction_grid: grid_points})
grid_predictions = grid_predictions.reshape(xx.shape)

10、绘制训练结果
plt.contourf(xx, yy, grid_predictions, cmap=plt.cm.Paired, alpha=0.8)
plt.plot(class1_x, class1_y, 'ro', label='I. setosa')
plt.plot(class2_x, class2_y, 'kx', label='I. versicolor')
plt.plot(class3_x, class3_y, 'gv', label='I. virginica')
plt.title('Gaussian SVM Results on Iris Data')
plt.xlabel('Pedal Length')
plt.ylabel('Sepal Width')
plt.legend(loc='lower right')
plt.ylim([-0.5, 3.0])
plt.xlim([3.5, 8.5])
plt.show()

plt.plot(batch_accuracy, 'k-', label='Accuracy')
plt.title('Batch Accuracy')
plt.xlabel('Generation')
plt.ylabel('Accuracy')
plt.legend(loc='lower right')
plt.show()


plt.plot(loss_vec, 'k-')
plt.title('Loss per Generation')
plt.xlabel('Generation')
plt.ylabel('Loss')
plt.show()

11、运行结果

                    

                    
                    
                    
                    
前言
本篇文章是个人对于从感知机到支持向量机的整个过程的思考和推理：
❝
感知机--->缺陷--->加入约束/优化策略（为什么可行）--->支持向量机
❞
不涉及支持向量机的学习过程（从原始凸二次规划问题转化为拉格朗日对偶问题）以及线性可分、线性、非线性支持向量机的讨论（本文采用线性可分的前提条件）。从支持向量机的定义出发，解释「最大间隔化的由来」、「支持向量的概念」以及「如何解决多分类任务」。支持向量机的内容较多，分多篇来梳理。
本文约1.7k字，预计阅读8分钟。
概要
首先给出支持向量机的定义：
❝
支持向量机（SVM）是一个「二分类模型」，是定义在特征空间上的「间隔最大」的分类器。
❞
可以发现，与感知机的区别在于【间隔最大】这个概念。首先，从几何角度来说，感知机就是在特征空间上找到一个超平面，这个超平面能刚好将分布在特种空间上的正负两类点给区分开来。那么「不做任何的约束」，这个超平面就会有无穷多个（线性可分的前提下）。那么就存在一个「关键问题」：如何挑选一个最优的超平面（也可以理解为如何让模型更加的健壮）？这就需要找到找到一个新的学习策略/约束。
将其公式化，对于感知机来说，定义一个超平面：
相对应的决策函数为：
通过对「误分类点到超平面的距离的总和」这一损失函数进行建模，通过SGD等方法进行优化。
以上是「经验风险最小化」，存在的缺陷：
解不唯一（超平面不唯一）；
容易受数据集影响；
那么就需要加入一个新的学习策略/约束，即「间隔最大化」，可以使其「结构风险最小」。学习的目标就是来找到一个最优超平面。
再将间隔最大化给剥离出来，存在两个问题：
最大间隔化指的是什么？
为什么最大间隔化可以找到一个唯一的超平面？
对于第1个问题，一个点（样本）到超平面的远近可以表示分类预测的确信程度（离超平面越远越准确，超平面附近的点不确定性更大）。点到平面距离的公式为：，假设两种分类点的标签为，那么每个样本的确信程度可以表示为：，对其进行简化，如果某个点的确信程度大于等于0的话，则就分类正确，。
以上就是「函数间隔」的定义，
❝
对于给定的训练集和超平面【超平面由法向量和截距所确定，因此可以用来表示超平面】，定义超平面关于样本点的函数间隔为：
定义「超平面关于训练集T的函数间隔」为超平面关于中所有样本点的函数间隔的最小值，即
❞
我们知道，如果等比例改变，超平面不变，但函数间隔会变化，所以又定义了一个「几何间隔」（添加规范化约束）。
❝
对于给定的训练集和超平面，定义超平面关于样本点的几何间隔为：
定义「超平面关于训练集T的几何间隔」为超平面关于中所有样本点的几何间隔的最小值，即
❞
所以最大间隔化指的就是「在能够正确划分训练数据集条件下，使得几何间隔最大化」，这就是支持向量机的学习策略/思想。
因此，可以公式化为：
通过一系列简化（参考《统计学习方法》），最终得到：
这个公式，就是整个支持向量机模型的构建。
【注】这里是线性可分支持向量机的定义。
对于第2个问题，存在定理（这里先考虑线性可分的情况）：
❝
最大间隔分离超平面的存在唯一性：若训练数据集线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面是存在且唯一的。
❞
证明参考《统计学习方法》P117-P118。
为什么称为支持向量机？
（支持向量机）模型定义，训练数据样本点与分离超平面最近的样本点称为「支持向量」（support vector），可以形象的理解为支撑起了整个分离超平面的构建。支持向量分布在两个超平面上：
和
可以得到一个重要的结论：**支持向量决定了最优超平面，与其他点无关。**所以这个依靠支持向量构建的模型称为支持向量机。
支持向量机如何解决多分类问题？
定义中，支持向量机是一个二分类模型，那么如何实现多分类任务？可以通过多个支持向量机来构建多分类器，具体比较好理解的有两种：
一对多（one vs rest）：即把某一个类别归为1类，其他类别归为另一类，假设有个类别，这样就构造了个分类器；
一对一（one vs one）：即任意两个类别构造一个支持向量机，需要个分类器，通过投票决定样本类别，LIBSVM就是这样实现的；
总结
以上是个人对感知机到支持向量机演化的一个思考，如有问题或者异议的地方欢迎联系我指出。