第六章 支持向量机
第六章 支持向量机
  6.1 间隔与支持向量
    核心思想
      支持向量机是一种分类学习方法
      基于训练集在样本空间中找到一个划分超平面，将不同类别的样本分开
    关键问题
      见 “举例说明”
      如何找到最合理的超平面？
        应该去找位于两类训练样本“正中间”的划分超平面
          找到具有“最大间隔”（maximum margin）的划分超平面
          ”正中间“：同时这种目的也存在一种使得模型泛化效果最大的目的
            因为该划分超平面对训练样本局部扰动的“容忍”性最好
              训练样本的局限性
              训练样本的噪声因素
              导致训练集以外的取值可能更接近分隔界
            这样的划分超平面的方式所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强
      如何求解最大间隔？
    举例说明
      训练集是二分类且取值仅为（-1，+1）的样例
      在样本空间中，划分超平面可通过如下线性方程来表示
        方程中是转置
        直线方程推导一下，可分别得x轴、y轴与原点的距离
        直线的斜截式方程表示
      假设超平面能够将所有训练样本正确分类
        概念
          距离到超平面最近的几个训练样本点使两条虚线等号成立，它们被称为“支持向量”（support vector）
          两个异类支持向量到超平面的距离之和为“间隔”（margin）
            例子中的间隔值为
      如何求解最大间隔？
        核心思想
        这个方程就是支持向量机（support vector machine）的基本型
        即，在本例中：
        即，在本例中：
  6.2 对偶问题
    凸优化问题（OPT，convex optimization problem）
      定义
      指定义在凸集中的凸函数的最优化的问题
      特性
        凸优化问题的局部最优解就是全局最优解
        很多非凸问题可以等价或近似转化为凸优化问题（比如拉格朗日对偶）
        凸优化问题的研究较为成熟，对应的求解方法也较为成熟
      形式化定义
        分类
          线性规划
            特征
            目标函数和约束函数均为线性函数
          二次规划
            特征
            无约束
            有约束
              等式约束凸二次优化
              不等式约束凸二次优化
              混合约束凸二次优化
              如何将有约束转化为无约束求解？
            目标函数为凸二次型，约束函数为线性函数
            梯度下降法解决问题
          二次约束的二次规划
            特征
            目标函数和约束函数均为凸二次型
    凸二次优化
      拉格朗日乘子法
        核心思想
        将有约束的凸二次优化问题转化为无约束的二次规划问题，然后用梯度下降法进行求解
        构造拉格朗日函数
          为什么可以转化为无约束的凸二次优化问题？
          通过求梯度就能看出来
            这里的解就是原问题的解
            分别对构造函数的自变量求偏导
              当使用梯度下降法求最小时，就可以发现第二个式子等于0即为原问题的约束条件
            联立两个梯度方程就可以求解，该问题的极值
      K.K.T.条件（Karush-Kuhn-Tucker）
        即在原问题为不等式约束时构造拉格朗日函数求解凸二次优化问题的时候，所形成的必要条件
        构造拉格朗日函数
          即从等式约束推广到不等式约束
          但是这里的对解的情况就要分两种情况了
            此时约束条件不起作用
        如何理解第二种情况时约束条件不起作用？
          因为在构造的拉格朗日函数中，偏导值为负时即为梯度下降的方向，因此纵使有约束条件，但约束条件为负，本身与优化过程要求一致，所以可以理解为约束条件不起作用
        一般形式
          假设原凸二次优化问题为
      对偶问题（dual problem）
        简单理解
        对偶问题只是将原始问题（primal problem）调换了min和max的位置
        即，形式为：
          从一堆胖子里挑一个最瘦的 要比 从一堆瘦子里挑一个最胖的 还胖！
        这里记 ：
          称之为拉格朗日对偶函数（Lagrange dual function）
          是原始问题的一个下界
    SVM对偶问题
      核心问题
      即多个不等约束的凸二次规划问题
      如何求解最大间隔？
      最大间隔基本型的方程：
      求解过程
        为每条约束添加拉格朗日乘子
        构造拉格朗日函数
          带入拉格朗日函数中，即可得原问题的对偶问题
        对偶问题为：
      K.K.T.条件
    特点
      该问题的规模正比于训练样本数量
      训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关
      其算法复杂度主要与支持向量的数目有关
  6.3 核函数
    异或问题与非线性映射
      问题
      解决方案
      原始样本空间内并不存在一个能正确划分两类样本的超平面
      将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分
        表示将原始样本映射后的特征向量
        在特征空间中划分超平面的模型为：
      问题转化
        SVM标准型转化为
        对偶问题转化为
    核函数（kernel function）
      产生的问题：特征空间维数可能很高，甚至是无穷
      定理
      定义函数：
      对偶问题
        转化为
        求解为
          即模型最优解可通过训练样本的核函数展开得到
支持向量展式（support vector expansion）
      核矩阵
      常见核函数
        性质
      含义
        只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用
        对一个半正定核矩阵，总能找到一个与之对应的映射函数
        任何一个核函数都隐式地定义了一个称为“再生核希尔伯特空间”（Reproducing Kernel Hilbert Space 简称RKHS）的特征空间
  6.4 软间隔与正则化
    软间隔
      产生原因
        在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分
        即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难确定这个貌似线性可分的结果是不是由于过拟合造成的
      对比概念
        软间隔（soft margin）
          允许某些样本不满足约束
        硬间隔（hard margin）
          所有样本都必须划分正确
        图示
      公式
              约束的原始条件是样本分类正确，即z式大于1，那么z式小于0时，即样本分类错误的情况
              对于当前这个损失函数，当分类正确时，相当于没有出现损失，所以记为0
            个人理解：当C无穷大时，迫使整个式子的要求最小值时，需要使得后半个式子值逼近0，则迫使了每个样本均分类正确才行
            个人理解：即整个式子的最小值取值情况不再依据后半个式子影响，因为其在有限样本的情况下，值为某个固定有限值
      替代损失（surrogate loss）
        存在问题
          非凸
          不连续
        常见的三种替代损失函数
          hinge损失:
          指数损失（exponential loss）：
          对率损失（logistic loss）：
          图示
        软间隔支持向量机标准型
          采用 hinge损失函数 替代原始的损失函数
            表示每一个样本不满足约束的程度
            标准型：
        若采用对率损失函数代替"0/1"损失函数则几乎得到了对率回归模型
          支持向量机与对率回归的优化目标相近，通常情形下它们的性能也相当
          对率回归的优势主要在于其输出具有自然的概率意义，即在给出预测标记的同时也给出了概率
          支持向量机的输出不具有概率意义，欲得到概率输出需进行特殊处理
          对率回归能直接用于多分类任务
          支持向量机则需要进行推广
    正则化（regularization）问题
      问题出发的原由
      从经验风险最小化的角度来看，第一项表述了我们希望获得具有何种性质的模型，这为引入领域知识和用户意图提供了途径；另一方面，该信息有助于削减假设空间，从而降低了最小化训练误差的过拟合风险
      SVM软间隔的一般形式
        第一项
          结构风险（structural risk）：用于描述模型的某些性质
          正则化项
        第二项
          经验风险（empirical risk）：用于描述模型与训练数据的契合程度
        常数系数
          用于进行两个风险的折中系数
          正则化常数
  6.5 支持向量回归
    支持向量回归（Support Vector Regression，简称SVR）
      对比
        传统回归模型是基于模型输出与真实输出之间的差别来计算损失，当且仅当两者完全相同时，损失才为零
        假设模型输出与真实输出之间最多有 ε 的偏差，即仅当模型输出与真实输出之间的差别绝对值大于 ε 时才统计损失
      相当于构建了宽度为 2ε 的间隔带
      公式
        形式化表示
      转化对偶问题进行求解
        拉格朗日乘子法求出的 SVR 解的形式
        性质
          SVR的支持向量仅是训练样本的一部分，即其解仍具有稀疏性
        如何确认b？
          得到
          理论上可以任意选取满足条件的样本求得b，但是为了更加鲁棒，通常会选取多个满足条件的样本求解b后取平均值
        最终解的形式
  6.6 核方法
    给定训练样本，若不考虑偏移项b，则无论SVM还是SVR，学得的模型总能表示成核函数的线性组合
    表示定理（representer theorem）
      优化问题
      解的形式
    核方法（kernel methods）
      一系列基于核函数的学习方法，统称为”核方法“
      通过”核化“（即引入核函数）来将线性学习器拓展为非线性学习器
      核线性判别分析（Kernelized Linear Discriminant Analysisi，简称KLDA）
        目标函数为：
        求解目标为：
          one-hot
          于是求解目标转化为：
    表示定理对损失函数没有限制，对正则化项仅要求单调递增，甚至不要求是凸函数，意味着对于一般的损失函数和正则化项，优化问题的最优解都可以表示为核函数的线性组合