[编程经验] TensorFlow实现非线性支持向量机

上一次说的是线性支持向量机的原理和tf实现问题,把SVM的原理简单用公式推导了一下,SVM这块还有几个问题没有解释,比如经验风险,结构风险,VC维,松弛变量等。今天主要是解释几个概念然后实现非线性的支持向量机。

  1. 风险最小化

期望风险

对于一个机器学习模型来说,我们的目的就是希望在预测新的数据的时候,准确率最高,风险最小,风险函数可以定义为:

其中L是损失函数,P(x,y)是训练数据和label标签的联合概率密度函数。这个风险函数的存在的问题是,我们无法知道x和y的联合概率密度,为什么?

想一下,如果能知道所有x和y的联合概率密度,我们还需要去做预测吗?显然不需要了。

对于机器学习任务来说,训练集其实就相当于是样本,测试集也是样本,总体是我们无法穷尽的一个东东,x和y的联合概率密度就是对总体的一个描述,所以上面那个风险函数是无法计算的,期望风险由此得来。想一想概率统计中的平均值和期望的区别,这里你就能想明白了。

既然期望风险无法得到,那么机器学习算法就转化为求经验风险最小,经验就对应的是训练集,训练集是我们可以获得的东西,所以可以称为经验。

经验风险:

上式就是经验风险,L是损失函数,xi和yi是训练集,w是参数,对比一下这个式子和上面那个式子,就发现,区别在于一个是求积分,一个是求和,显然简单多了。其实最小二乘估计就是采用的经验风险最小为优化目标的,甚至说大多数的机器学习算法都是求经验风险最小的那一个模型。

2. VC维,Vapnik-Chervonenkis dimension

首先VC维描述了一族函数的复杂程度,而且并不是模型越复杂那么它的泛化能力就越好。如果一个模型在训练集上表现的很好,那么它的泛化能力一般较差,也就是说,如果一个简单的模型在训练集表现好,那么它的泛化能力往往比较好。

考虑一个二分类问题,假设现在有D维实数空间中的N个点,每个点有两种可能情况,+1和-1。那么N个点就有2^N中可能,举个栗子,N=3的时候,就有{(000), (001), (010), (011), (100), (101), (110), (111) } 。

一般对VC维的解释都是函数集可以打乱(shattered)的最大数据集的数目,怎么理解这句话呢? 我觉得是,假如一个函数集f(a)的VC维为h, 那么至少存在一个包含h个样本的数据集,可以被函数集f(a)分开。注意这里是至少存在一个,所以不是说只要是包含h个样本的数据,都可以被shatter!

还是不能理解? 举个栗子

假如在二维平面内有3个点,那么我们可以找到一个线性分类器,不论是哪一种可能的情况,都可以将这三个点正确分类。所以这个分类器的VC维就是3.

3. 结构风险最小化

结构风险一般表示为经验风险和置信风险的和

其中h是VC维,N是训练样本个数。当N/h变大的时候,N变大,h变小,置信风险趋于0,这时候结构风险约等于经验风险。也就是说当给定足够的样本的时候,结构风险就是经验风险。

而支持向量机是基于结构风险最小的,即使的经验风险和VC置信风险的和最小。

然后看下下面这个图,

下面的S1,S2,...,Sk表示的是不同VC维的函数族,当VC维增加的时候,经验风险在降低,置信风险却在增加,所以需要找到一个平衡点,这个平衡点就是最佳的模型。

到这里似乎问题已经解决了,但是VC维一般是很难计算的,尤其是对于像神经网络这样的非线性函数,Vapnik在1998年证明了下面这个公式:

其中m表示间隔(margin),D表示输入空间的维度,R是包含所有输入样本的组成的一个球体的最小的半径。上面这个式子说明,VC维最小等价于使得间隔最大,间隔最大也就是最小化经验风险的上界。

到这里其实是想说明,要使得结构风险最小,就要使得间隔最大。这就是为什么会提出支持向量机。

4. 松弛变量

上一次讲的时候,对于线性可分情况下,优化目标的约束条件是这个:

对于非线性可分情况下,就无法找到一个超平面来分类,为了实现最终分类,我们设计一种方法,使得用某一个超平面来分类的时候,误差最小。基于此,引入松弛变量,它表示了样本点与间隔的偏离,通俗点的理解是,对于非线性可分情况,有2种可能,一种是正类样本位于超平面的正确的一侧,虽然被正确分类,但是在间隔之内;还有一种可能是正类样本完全在负类样本中。下图是一个直观的解释,看图应该更容易理解。

上图中,凡是样本点在正类之外,松弛变量都是0,超平面右侧松弛变量小于1,左侧大于1。

引入松弛变量以后,约束条件就变为:

优化目标为:

其中C用来控制间隔和松弛变量之间的平衡关系;

还是用拉格朗日乘子法求解上述优化问题,只不过这里的乘子有2个,一个是a,一个是mu。

KKT条件:

分别令偏导数为0:

对偶形式:

对偶约束:

然后对KKT条件中第三个式子做个移项:

对于支持向量来说,松弛变量都是0,此时满足:

即:

求解上式就可以得到:

对比一下,线性可分情况:

其中Ns表示的是所有的支持向量。

我们发现,对于 非线性可分情况,其实就是为了去掉那些不是支持向量的点,使得最终还是满足线性可分。

最后大家可能对核函数怎么算的,不是很清楚,这里贴一个公式:

其中的函数fai,表示特征空间中的非线性映射关系;

常用的核函数,比如高斯核函数RBF:

对于怎么选择核函数,可以参考下面的参考文献。。。

下面就是如何用TF来实现非线性SVM了

# coding: utf-8
import numpy as np
import tensorflow as tf
from sklearn import datasets

x_data = tf.placeholder(shape=[None, 2], dtype=tf.float32)
y_target = tf.placeholder(shape=[None, 1], dtype=tf.float32)
prediction = tf.placeholder(shape=[None, 2], dtype=tf.float32)


def get_data():
    iris = datasets.load_iris()
    x_vals = np.array([[x[0], x[3]] for x in iris.data])
    y_vals = np.array([1 if y == 0 else -1 for y in iris.target])
    return x_vals, y_vals


def Gaussian_kernel(gamma):
    g = tf.constant(gamma)
    # 2 * (x_data * x_data^T)
    sq_dists = tf.multiply(2.,
         tf.matmul(x_data, tf.transpose(x_data)))
    # exp(g * abs(sq_dists))
    out = tf.exp(tf.multiply(g, tf.abs(sq_dists)))
    return out


def non_linea_svm(my_kernel, batch_size, prediction, gamma=-25.0):
    b = tf.Variable(tf.random_normal(shape=[1, batch_size]))
    first_term = tf.reduce_sum(b)
    b_vec_cross = tf.matmul(tf.transpose(b), b)
    # 偏置的内积, b的转置乘以b
    y_target_cross = tf.matmul(y_target, tf.transpose(y_target))
    # label的内积,y乘以y的转置
    second_term = tf.reduce_sum(tf.multiply(my_kernel,
             tf.multiply(b_vec_cross, y_target_cross)))
    # 偏置的内积乘以label 的内积,结果再乘以核函数
    loss = tf.negative(tf.subtract(first_term, second_term))
    # 第一项和第二项做差,然后添加一个负号,
    # negative是取相反数的意思
    rA = tf.reshape(tf.reduce_sum(tf.square(x_data), 1),
                                  [-1, 1])
    rB = tf.reshape(tf.reduce_sum(tf.square(prediction), 1), 
                              [-1, 1])
    stra = tf.subtract(rA, tf.multiply(2., 
            tf.matmul(x_data, tf.transpose(prediction))))
    pred_sq_dist = tf.add(stra, tf.transpose(rB))
    # (rA-2*x_data*预测值的转置)+rB的转置
    pred_kernel = tf.exp(tf.multiply(gamma, 
                      tf.abs(pred_sq_dist)))

    prediction_output = tf.matmul(tf.multiply(
                tf.transpose(y_target), b), pred_kernel)
    prediction = tf.sign(prediction_output -
                     tf.reduce_mean(prediction_output))
    accuracy = tf.reduce_mean(
        tf.cast(tf.equal(tf.squeeze(prediction), 
                tf.squeeze(y_target)), tf.float32))
    my_opt = tf.train.GradientDescentOptimizer(0.01)
    train_step = my_opt.minimize(loss)
    return loss, accuracy, train_step


def train_svm(sess, batch_size):
    kernel = Gaussian_kernel(-25.0)
    loss_vec = []
    batch_accuracy = []
    for i in range(300):
        x_vals, y_vals = get_data()
        loss, accuracy, train_step = non_linea_svm(
            kernel, batch_size=batch_size, 
                    prediction=prediction)
        init = tf.global_variables_initializer()
        sess.run(init)
        rand_index = np.random.choice(len(x_vals),
                       size=batch_size)
        rand_x = x_vals[rand_index]
        rand_y = np.transpose([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: rand_x})
        batch_accuracy.append(acc_temp)

        if (i + 1) % 100== 1:
            print('Loss = ' + str(temp_loss))


def main(_):
    with tf.Session() as sess:
        train_svm(sess, batch_size=30)


if __name__ == "__main__":
    tf.app.run()

最后说一下,哪里有看不懂的,欢迎与我交流~~

参考文献:

1. Pattern Recognition and Machine Learning

2. machine Learning A Probabilistic Perspective

3. Introduction to Machine Learning

4. https://www.zhihu.com/question/21883548

原文发布于微信公众号 - 机器学习和数学(ML_And_Maths)

原文发表时间:2017-08-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏瓜大三哥

竞争型神经网络

自组织神经网络(self-Organization Mapping net,SOM)是基于无监督学习方法的神经网络的一种重要类型。自组织神经网络是神经网络最富有...

3725
来自专栏机器之心

训练深度神经网络失败的罪魁祸首不是梯度消失,而是退化

2415
来自专栏新智元

何恺明抛出重磅炸弹!ImageNet并非必要

刚刚,何恺明等人在arxiv贴出一篇重磅论文,题为《重新思考“ImageNet预训练”》,让似乎本已经平静的ImageNet湖面,再掀波澜!

844
来自专栏算法channel

logistics判别与线性模型中的4个问题

之前说过,机器学习的两大任务是回归和分类,上章的线性回归模型适合进行回归分析,例如预测房价,但是当输出的结果为离散值时,线性回归模型就不适用了。我们的任务是:将...

1450
来自专栏魏晓蕾的专栏

【机器学习】CS229课程笔记notes2翻译-Part IV生成学习算法

      到目前为止,我们主要谈论建模p(y|x;θ)的学习算法,给定x的y的条件分布。例如,logistic回归建模p(y|x;θ)为hθ(x)=g(θTx...

2526
来自专栏AI科技评论

总结 | 优必选悉尼AI研究院何诗怡:基于课程学习的强化多标签图像分类算法

与单标签图像分类相比,多标签图像分类是一种更符合真实世界客观规律的方法,尤其在图像和视频的语义标注,基于内容的图像检索等领域有着广泛的应用。

1903
来自专栏SIGAI学习与实践平台

Large scale GAN training for high fidelity natural image synthesis解读

尽管最近几年在生成式图像建模上取得了进步,但从ImageNet这样的复杂数据集生成高分辨率、多样化的图像仍然是一个具有挑战性的工作。为了达到这一目标,本文作者训...

1863
来自专栏新智元

Adobe 写实深度摄影风格迁移,局部仿射解决画面扭曲

【新智元导读】康奈尔大学和 Adobe 团队的这项图像风格迁移研究,解决了神经网络风格迁移中由于参考图像风格夸张而产生的的输出图像“扭曲”的问题,在各种场景下得...

3205
来自专栏奇点大数据

神经网络:问题与解决方案

尽管人工神经网络的概念从20世纪50年代就已经存在,但是直到最近我们才有能力将理论转化为实践。神经网络应该能够模仿任何连续的功能。但是,很多时候,我们都陷入了网...

3266
来自专栏机器学习算法工程师

《机器学习》笔记-降维与度量学习(10)

如今机器学习和深度学习如此火热,相信很多像我一样的普通程序猿或者还在大学校园中的同学,一定也想参与其中。不管是出于好奇,还是自身充电,跟上潮流,我觉得都值得试一...

1404

扫码关注云+社区

领取腾讯云代金券