线性分类器

支持向量机 线性分类器 LinearClassifier 线性可分vs 非线性可分线性分类器 训练中确定所有的wi和参数决策规则 对于线性可分 必然存在线性分类面 N维空间下的二类线性分类器 N维超平面 一维 二维 三维 阈值逻辑单元 ThresholdLogicUnit TLU w1 w2 wn a i 1nwixi 1ifa qy 0ifa q y 输入 权重 激励函数 输出 q 激励函数 a y a y a y a y 阈值型 线性 分段线性 sigmoid 阈值也可以作为权重一并考虑 1ifa 0y 0ifa 0 w1 w2 wn wn 1 xn 1 1 a i 1n 1wixi y q wn 1 支持向量机 SupportVectorMachines 超平面的选择 所谓的超平面的的便把这两种不同类别的数据点分隔开来线性可分的情况下分类面有无穷多个 如上图的训练样本 在线性可分的情况下 存在多个超平面 Hyperplane 如 H1 H2 使得这两类被无误差的完全分开 超平面可以定义为 其中W 都是向量 W 是内积 b是标量 超平面定义 函数间隔Functionalmargin与几何间隔Geometricalmargin 一般而言 一个点距离超平面的远近可以表示为分类预测的确信或准确程度 在超平面w x b 0确定的情况下 w x b 能够相对的表示点x到距离超平面的远近 而w x b的符号与类标记y的符号是否一致表示分类是否正确 所以 可以用量y w x b 的正负性来判定或表示分类的正确性和确信度 函数间隔Functionalmargin 我们定义函数的间隔为 接着我们我们定义超平面 w b 关于训练数据集T的函数间隔为超平面 w b 关于T中所有样本点 xi yi 的函数间隔最小值 其中 x是特征 y是结果标签 i表示第i个样本 然与此同时 问题就出来了 上述定义的函数间隔虽然可以表示分类预测的正确性和确信度 但在选择分类超平面时 只有函数间隔还远远不够 因为如果成比例的改变w和b 如将他们改变为2w和2b 虽然此时超平面没有改变 但函数间隔的值f x 却变成了原来的2倍 几何间隔Geometricalmargin 几何间隔的基本定义 其中 w 为w的二阶范数 范数是一个类似于模的表示长度的概念 从上述函数间隔和几何间隔的定义可以看出 几何间隔就是函数间隔除以 w 而且函数间隔y wx b y f x 实际上就是 f x 只是人为定义的一个间隔度量 而几何间隔 f x w 才是直观上的点到超平面的距离 支持向量机 SupportVector OptimalSeparatingHyperplane 线性可分情况下 不仅要区分开 而且要使得间隔 Margin 最大 Margin H1 H2 小间隔vs 大间隔 支持向量积的原理 对一个数据点进行分类 当超平面离数据点的 间隔 越大 分类的确信度 confidence 也越大 所以 为了使得分类的确信度尽量高 需要让所选择的超平面能够最大化这个 间隔 值 这个间隔就是下图中的Gap的一半 求解最优超平面就相当于 在下列约束条件下 求目标函数的最小值 目标函数 约束条件 最优超平面 可以通过求解上述问题的对偶问题来得到最终的解 在对偶问题中 将原来需要求解的一系列wi转换成求解另一组变量 i 求解原始问题 为求解原始问题 根据最优化理论 我们转化为对偶问题来求解 为原始问题中与每个约束条件对应的Lagrange乘子 这是一个不等式约束条件下的二次函数寻优问题 存在唯一解 线性可分问题 计算 选择的一个正分量 并据此计算 事实上 的每一个分量都与一个训练点相对应 而分划超平面仅仅依赖于不为零的训练点 而与对应于为零的那些训练点无关 称不为零的这些训练点的输入为支持向量 SV 构造分划超平面 决策函数 根据最优解 求解结果 上述二次优化问题 采用Lagrange方法求解 可得相当于每个类别中选出若干支持向量组成 投票委员会 根据这些 委员 的加权投票 内积 结果得到最终的类别归属 支持向量 SupportVector 非线性可分情况下的处理方法一 广义最优分类面方法 在线性不可分的情况下 就是某些训练样本不能满足上面的约束条件 因此可以在条件中增加一个松弛项 这种做法也称引入SoftMargin 软边界 于是约束条件变成 此时的目标函数是求下式的最小值 这个二次优化问题 同样可以应用Lagrange方法求解 正则项 经验风险 最优超平面求解 变换到高维空间的支持向量机 采用如下的内积函数 核函数 核函数本质上是高维空间下的内积函数 但是输入为原始空间的向量 多项式核 径向基核 核 分类函数 一个SVM的例子 几何法求解 最大间隔权重向量将和两类中距离最短的那条线段 直线 平行 即与连接点 1 1 和 2 3 的直线平行 这可以得到权重向量 1 2 最优的分类直线与上述线段垂直并相交与其中点 中垂线 因此它经过点 1 5 2 于是 可以求得SVM的决策直线方程为 y x1 2x2 5 5 一个SVM的例子 代数法求解 在约束条件下 寻找最小的我们知道解的形式为 于是有 a 2a b 1 2a 6a b 1解得 a 2 5及b 11 5因此 最优超平面的参数为 b 11 5 此时间隔 为 SVM的多分类问题 将SVM推广解决多分类问题有两类方法 第一种方法是将多分类看作二分类的组合 最终将多分类问题转化为二分类问题 第二种方法是通过修改目标函数 从根本上解决SVM处理多分类问题 由于后者代价过高 只适用于小规模问题 目前多采用第一类方法 对于多类问题 给定样本集 一对多的分类方法 一对多的分类方法原理很简单 多于k分类问题 把1作为第一类 其余的k 1类看成一类 很自然的把k分类问题转化成二分类问题 这种分类方法在训练过程中 每个分类函数都需要所有的样本参与 分类函数为 上标表示第j个SVM分类器的决策函数 和分别为第j个支持向量的参数和类别编号 为偏移量 对于待测样本 若 则输入的样本属于l类 这种方法的训练时间与类别的数量成正比 并且未考虑多个分类器对测试错误率的影响 当训练样本较大时 训练较为困难 一对一SVM分类 一对一的解决方法是在K类问题中进行两两组合 构造个分类器 这种方法的确定是对于类别K过大时 产生的子分类器过多 相对于一对多分类子分类器明显增加 训练时间更长 由于测试时要任意两类进行比较 训练速度随着类别的增加成指数倍降低 有向无环图SVM分类 有向无环图SVM分类在训练阶段也是采用一对一SVM的任意两两组合的方式 也需要个子分类器 但在分类过程中 DAG将徐偶有子分类器构造成一个有向的无环图 包括个节点和k个叶子节点 其中每一个节点是一个子分类器 当对未知样本训练时 从根节点开始分类 只需k