0、

支持向量机：Support Vector Machine

 

1、什么是支持向量机SVM？

Support Vector Machine，是由Vladimir N. Vapnik和Alexey Ya. Chervonenkis在1936年提出。

当前版本soft margin是由Corinna Cortes和Vapnik在1993年提出，并在1995年发表。

被认为是深度学习出现以前（2012）最成功，表现最好的算法。

 

PS1：机器学习的一般框架：

训练集 ==> 提取特征向量 ==> 结合算法（分类器：比如决策树，KNN） ==> 得到结果

 

2、边际最大超平面

2.1 SVM寻找区分两类的超平面（hyper plane），使边际（margin）最大

如何选取使边际（margin）最大的超平面（Max Margin Hyperplane）？

超平面到一侧最近点的距离等于到另一侧最近点的距离，两侧的两个超平面平行。

 

2.2 线性可区分（linear separable）和线性不可区分（linear inseparable）

2.3 公式定义：

超平面可以定义为：W * X + b = 0

其中W表示权重向量（weight vector）：W = {w_1, w_2,..., w_n}

n是特征值的个数，X表示训练实例，b表示迁移量bias

2.3.1 假设2维特征向量：X =（x1，x2），并且把b定义为额外的weight：w0

那么超平面方程变为：w_0 + w_1x_1 + w_2x_2 = 0

所有超平面上方的点满足：w_0 + w_1x_1 + w_2x_2 > 0

下方的点满足：w_0 + w_1x_1 + w_2x_2 < 0

调整weight，使超平面定义边际的两边：

H_1 : w_0 + w_1x_1 + w_2x_2 >= 1 for y_i = +1

H_2 : w_0 + w_1x_1 + w_2x_2 <= -1 for y_i = -1

综合以上两式，得到：y_1(w_0 + x_1x_1 + w_2x_2) >= 1, \forall i.

所有落在边际的两边的超平面上的被称作“支持向量（support vector）”

分界的超平面和H1或H2上任意一点的距离为 \frac{1}{||w||}

其中||W||是向量的范数（norm），计算方法：

if W = {w_1, w_2,..., w_n} then \sqrt{W * W} = \sqrt{w_1^2 + w_2^2 + ... + w_n^2}

所以，最大边际距离为：\frac{2}{||w||}

 

3、求解

3.1 SVM如何找出最大边际的超平面呢(MMH)？

利用一些数学推倒，以上公式 （1）可变为有限制的凸优化问题(convex quadratic optimization)，利用 Karush-Kuhn-Tucker (KKT)条件和拉格朗日公式，可以推出MMH可以被表示为以下“决定边界 (decision boundary)” ，即我们使用建立的超平面来决定一个新的点是属于哪一类的。

d(X^T) = \sum_{i=1}^l y_i\alpha_iX_iX^T + b_0

其中，y_i是支持向量点X_i（support vector）的类别标记（class label）

X^T是要测试的实例

\alpha_i和b_0都是单一数值类型参数，由以上提到的最优算法得出

l是支持向量点的个数

3.2

对于任何测试（要归类的）实例，带入以上公式，得出的符号是正还是负决定

3.3 示例：

 

4、Python示例

1 sklearn简单例子

from sklearn import svm

X = [[2, 0], [1, 1], [2,3]]
y = [0, 0, 1]
clf = svm.SVC(kernel = 'linear')
clf.fit(X, y)  

print clf

# get support vectors
print clf.support_vectors_

# get indices of support vectors
print clf.support_ 

# get number of support vectors for each class
print clf.n_support_ 

2 sklearn画出决定界限

print(__doc__)

import numpy as np
import pylab as pl
from sklearn import svm

# we create 40 separable points
np.random.seed(0)
X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]
Y = [0] * 20 + [1] * 20

# fit the model
clf = svm.SVC(kernel='linear')
clf.fit(X, Y)

# get the separating hyperplane
w = clf.coef_[0]
a = -w[0] / w[1]
xx = np.linspace(-5, 5)
yy = a * xx - (clf.intercept_[0]) / w[1]

# plot the parallels to the separating hyperplane that pass through the
# support vectors
b = clf.support_vectors_[0]
yy_down = a * xx + (b[1] - a * b[0])
b = clf.support_vectors_[-1]
yy_up = a * xx + (b[1] - a * b[0])


print "w: ", w
print "a: ", a
# print " xx: ", xx
# print " yy: ", yy
print "support_vectors_: ", clf.support_vectors_
print "clf.coef_: ", clf.coef_

# In scikit-learn coef_ attribute holds the vectors of the separating hyperplanes for linear models. It has shape (n_classes, n_features) if n_classes > 1 (multi-class one-vs-all) and (1, n_features) for binary classification.
# 
# In this toy binary classification example, n_features == 2, hence w = coef_[0] is the vector orthogonal to the hyperplane (the hyperplane is fully defined by it + the intercept).
# 
# To plot this hyperplane in the 2D case (any hyperplane of a 2D plane is a 1D line), we want to find a f as in y = f(x) = a.x + b. In this case a is the slope of the line and can be computed by a = -w[0] / w[1].

# plot the line, the points, and the nearest vectors to the plane
pl.plot(xx, yy, 'k-')
pl.plot(xx, yy_down, 'k--')
pl.plot(xx, yy_up, 'k--')

pl.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
           s=80, facecolors='none')
pl.scatter(X[:, 0], X[:, 1], c=Y, cmap=pl.cm.Paired)

pl.axis('tight')
pl.show()

5、进阶

5.1 SVM算法特性

5.1.1 训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以SVM不太容易产生overfitting

5.1.2 SVM训练出来的模型完全依赖于支持向量(Support Vectors), 即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。

5.1.3 一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易被泛化。

5.2 线性不可分的情况

 

5.2.1 数据集在空间中对应的向量不可被一个超平面区分开

5.2.2 两个步骤来解决：

• 利用一个非线性的映射把原数据集中的向量点转化到一个更高维度的空间中
• 在这个高维度的空间中找一个线性的超平面来根据线性可分的情况处理

 

 

5.3 如何利用非线性映射把原始数据转化到高维中？

5.3.1 例子：

• 3维输入向量：X=(x_1, x_2, x_3)
• 转化到6维空间 Z 中去：\phi_1(X)=x_1, \phi_2(X)=x_2, \phi_3(X)=x_3, \phi_4(X)=(x_1)^2, \phi_5(X)=x_1x_2, and \phi_6(X)=x_1x_3
• 新的决策超平面：d(Z)=WZ+b, 其中W和Z是向量，这个超平面是线性的
• 解出W和b之后，并且带入回原方程：d(Z) = w_1x_1 + w_2x_2 + w_3x_3 + w_4(x_1)^2 + w_5x_1x_2 + w_6x_1x_3 + b = w_1z_1 + w_2z_2 + w_3z_3 + w_4z_4 + w_5z_5 + w_6z_6 + b

5.3.2 思考问题：

• 如何选择合理的非线性转化把数据转到高纬度中？
• 如何解决计算内积时算法复杂度非常高的问题？

5.3.3 使用核方法（kernel trick)

5.4. 核方法（kernel trick)

5.4.1 动机：在线性SVM中转化为最优化问题时求解的公式计算都是以内积(dot product)的形式出现的\phi(X_i)\phi(X_j)，其中\phi(X)是把训练集中的向量点转化到高维的非线性映射函数，因为内积的算法复杂度非常大，所以我们利用核函数来取代计算非线性映射函数的内积

5.4.2 以下核函数和非线性映射函数的内积等同

         K(X_i, X_j) = \phi(X_i)\phi(X_j)

5.4.3 常用的核函数(kernel functions)

• h度多项式核函数(polynomial kernel of degree h) : K(X_i, X_j) = (\phi(X_i)\phi(X_j) + 1)^h
• 高斯径向基核函数(Gaussian radial basis function kernel) : K(X_i, X_j) = e^{ - ||\phi(X_i) - \phi(X_j)||^2 / 2\sigma^2}
• S型核函数(Sigmoid function kernel) : K(X_i, X_j) = tanh( \kappa\phi(X_i)\phi(X_j) - \delta)

5.4.4 如何选择使用哪个kernel？

• 根据先验知识，比如图像分类，通常使用RBF，文字不使用RBF
• 尝试不同的kernel，根据结果准确度而定

5.4.5 核函数举例:

• 假设定义两个向量： x = (x1, x2, x3); y = (y1, y2, y3)
• 定义方程：f(x) = (x1x1, x1x2, x1x3, x2x1, x2x2, x2x3, x3x1, x3x2, x3x3)
• K(x, y ) = (<x, y>)^2
• 假设x = (1, 2, 3); y = (4, 5, 6). 
• f(x) = (1, 2, 3, 2, 4, 6, 3, 6, 9)
• f(y) = (16, 20, 24, 20, 25, 30, 24, 30, 36)
• <f(x), f(y)> = 16 + 40 + 72 + 40 + 100+ 180 + 72 + 180 + 324 = 1024
• K(x, y) = (4  + 10 + 18 ) ^2 = 32^2 = 1024

同样的结果，使用kernel方法计算容易很多

5.4.6 SVM扩展可解决多个类别分类问题

        对于每个类，有一个当前类和其他类的二类分类器（one-vs-rest)

 

5.5 利用SVM进行人脸识别实例：

from __future__ import print_function

from time import time
import logging
import matplotlib.pyplot as plt

from sklearn.cross_validation import train_test_split
from sklearn.datasets import fetch_lfw_people
from sklearn.grid_search import GridSearchCV
from sklearn.metrics import classification_report
from sklearn.metrics import confusion_matrix
from sklearn.decomposition import RandomizedPCA
from sklearn.svm import SVC

print(__doc__)

# Display progress logs on stdout
logging.basicConfig(level=logging.INFO, format='%(asctime)s %(message)s')

###############################################################################
# Download the data, if not already on disk and load it as numpy arrays

lfw_people = fetch_lfw_people(min_faces_per_person=70, resize=0.4)

# introspect the images arrays to find the shapes (for plotting)
n_samples, h, w = lfw_people.images.shape

# for machine learning we use the 2 data directly (as relative pixel
# positions info is ignored by this model)
X = lfw_people.data
n_features = X.shape[1]

# the label to predict is the id of the person
y = lfw_people.target
target_names = lfw_people.target_names
n_classes = target_names.shape[0]

print("Total dataset size:")
print("n_samples: %d" % n_samples)
print("n_features: %d" % n_features)
print("n_classes: %d" % n_classes)


###############################################################################
# Split into a training set and a test set using a stratified k fold

# split into a training and testing set
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25)


###############################################################################
# Compute a PCA (eigenfaces) on the face dataset (treated as unlabeled
# dataset): unsupervised feature extraction / dimensionality reduction
n_components = 150

print("Extracting the top %d eigenfaces from %d faces"
      % (n_components, X_train.shape[0]))
t0 = time()
pca = RandomizedPCA(n_components=n_components, whiten=True).fit(X_train)
print("done in %0.3fs" % (time() - t0))

eigenfaces = pca.components_.reshape((n_components, h, w))

print("Projecting the input data on the eigenfaces orthonormal basis")
t0 = time()
X_train_pca = pca.transform(X_train)
X_test_pca = pca.transform(X_test)
print("done in %0.3fs" % (time() - t0))


###############################################################################
# Train a SVM classification model

print("Fitting the classifier to the training set")
t0 = time()
param_grid = {'C': [1e3, 5e3, 1e4, 5e4, 1e5],
              'gamma': [0.0001, 0.0005, 0.001, 0.005, 0.01, 0.1], }
clf = GridSearchCV(SVC(kernel='rbf', class_weight='auto'), param_grid)
clf = clf.fit(X_train_pca, y_train)
print("done in %0.3fs" % (time() - t0))
print("Best estimator found by grid search:")
print(clf.best_estimator_)


###############################################################################
# Quantitative evaluation of the model quality on the test set

print("Predicting people's names on the test set")
t0 = time()
y_pred = clf.predict(X_test_pca)
print("done in %0.3fs" % (time() - t0))

print(classification_report(y_test, y_pred, target_names=target_names))
print(confusion_matrix(y_test, y_pred, labels=range(n_classes)))


###############################################################################
# Qualitative evaluation of the predictions using matplotlib

def plot_gallery(images, titles, h, w, n_row=3, n_col=4):
    """Helper function to plot a gallery of portraits"""
    plt.figure(figsize=(1.8 * n_col, 2.4 * n_row))
    plt.subplots_adjust(bottom=0, left=.01, right=.99, top=.90, hspace=.35)
    for i in range(n_row * n_col):
        plt.subplot(n_row, n_col, i + 1)
        plt.imshow(images[i].reshape((h, w)), cmap=plt.cm.gray)
        plt.title(titles[i], size=12)
        plt.xticks(())
        plt.yticks(())


# plot the result of the prediction on a portion of the test set

def title(y_pred, y_test, target_names, i):
    pred_name = target_names[y_pred[i]].rsplit(' ', 1)[-1]
    true_name = target_names[y_test[i]].rsplit(' ', 1)[-1]
    return 'predicted: %s\ntrue:      %s' % (pred_name, true_name)

prediction_titles = [title(y_pred, y_test, target_names, i)
                     for i in range(y_pred.shape[0])]

plot_gallery(X_test, prediction_titles, h, w)

# plot the gallery of the most significative eigenfaces

eigenface_titles = ["eigenface %d" % i for i in range(eigenfaces.shape[0])]
plot_gallery(eigenfaces, eigenface_titles, h, w)

plt.show()

 

PS：材料学习自麦子学院，如有雷同，纯属学习