临近毕业的学习笔记
这是一篇隐藏日志。您需要以合适的身份登入后才能查看。
初稿交了上去，被导师批的体无完肤······
SVM里面涉及的数学要求太高了.我一时半会也没看懂.看了看一些概念性的东西.做的笔记贴上来. SVM算法学习笔记： SVM算法是用于机器学习和机器训练的一个有效算法。 Support Vector Machine 第一章:学习方法 1.1 监督学习 学到的概念有: 监督学习:当样例是由输入/输出对给出时,成为监督学习. 有关输入输出关系的样例称为训练数据. 输入/输出对通常反映了把输入映射到输出的一种函数关系. 当输入到输出存在内在函数时,该函数称为目标函数. 由学习算法输出的对目标函数的估计成为学习的解. 对于分类问题,该函数有时称为决策函数. 在学习区分赛车的例子中,输出为简单的是/否,它就可看作是二元输出值.对于识别蛋白质类型的问题,输出值为有限数量的类别之一;对于化学反应的问题输出值为实数值的表示的反应化合物的浓度. 有二元输出的问题成为 二类问题.有多个类别的问题成为多类问题.而实数值输出的问题称为回归问题. 非监督学习问题:数据不包含输出值,学习的任务是理解数据产生的过程.这种类型的学习包括密度估计,分布类型的学习和聚类等. 本书着重于在批量学习的设置下,根据有输出值的数据来学习输入/输出映射,即应用监督学习方法到批量训练数据上. 1.2 学习和泛化性 而当前情形下,学习的目标是输出一个假设以正确分类训练数据,早期的学习算法目标也是寻找对数据的精确拟合,这样寻找到的假设称为一致假设. 然而生成 可验证的一致性假设这一目标存在两个问题: 一个问题是待学习的目标函数可能简单的表示,因此不能很容易地加以验证,例如在DNA序列中定位基因.某些子序列是基因,某些不是.但没有一种简单的方法来区分两者. 第二个问题是,通常训练数据是有噪音的.因此不能保证存在一个目标函数能够正确地映射训练数据.很明显信用检测是其中一例,因为偿债能力可以取决于其他一些系统无法获知的因素.另一个例子是网页分类的问题,这也是一个不精确的科学问题. 还有一个更基为基本的问题在于,及时能够找到与训练数据一致的假设,他也可能无法对未见数据进行分类.一个假设正确分类训练集之外数据的能力称为泛化性,这正是要优化的属性. 如果一个假设能给出正确的输出,它就满足泛化性准则. 1.3 提高泛化性 过拟合: 许多经典的机器学习算法能够表示任意函数,并且对于困难的训练数据集会得到一个类似机械式学习器的假设.所谓机械式学习器是指能够正确分类训练数据,但对于所有未见数据会做出根本无关联性的预测.例如,决策树有可能过度增长直至针对每个训练样例有一叶子节点.为了得到一致假设变得过度复杂成为 过拟合. 控制此问题的一种方法是限制假设的规模,例如对于决策树可进行修剪操作.奥卡姆(Ockham)剃刀是该类方法的准则之一,它建议如无必要,不必增加复杂性,或者说更精细的复杂性必须有利于显著提高训练数据的分类正确性. 1.5 用于学习的支持向量机 支持向量机(SVM,Support Vector Machine)是在高维特征空间使用线性函数假设空间的学习系统,它由一个来自最优化理论的学习算法训练,该算法实现了一个由统计学习理论到处的学习偏置.此学习策略由Vapnik和他的合作者提出,是一个准则性的 并且强有力的方法.在它提出来的若干年来,在范围广大的应用中,SVM的性能胜过其他大多数的学习系统. 第二章 线性学习器 对监督学习来说，学习器会输入一个带有标记（或者输出值）的样例（或输入）的训练集。 样例通常是以属性向量的形式给出，因此输入空间是R^n的子集。一旦给定输入向量，就可以为问题选择一定数目的假设函数集。其中，线性函数最容易理解并且应用最简单。 学习方法意味着一定要从数据中学习到这些参数。 在从样例中研究监督学习问题前，首先要介绍一些再本书中都要用到的符号，比如输入、输出、训练集，等等。 20世纪60年代就已经提出了几个简单的迭代算法来优化代价函数，这些代价函数使用超平面把点分为两类。下面将回顾一些最著名的算法。感知机是有趣的，这不仅是因为历史原因，还因为在如此简单的一个系统内可以找到研究SVM理论所需要的绝大多数核心概念。注意有一些算法，比如最小二乘，既可以做回归也可用来作分类。 2.1.1 Rosenblatt感知机 它是一个“在线”和“错误驱动“的程序，从一个初始权重向量w0(通常w0=0,一个全零的向量)开始，每次当一个训练点被现在的权重误分的时候都调整权重。算法见下，这个算法直接更新权重向量和偏置。 如果存在一个超平面能够正确分类训练数据，并且这个程序保证收敛，这种情况称为线性可分。如果这样的超平面不存在，则数据称为不可分。 2.2 线性回归 线性回归的问题就是求线性函数：f(x) = +b使其能够最好地拟合一个给定标记为的训练点集Ｓ。从几何角度讲是寻找一个立定给定点的超平面。 这个问题最著名的解是最小二乘法，它能在线性目标被高斯噪音干扰的情况下获得最优结果。
支持向量机的发展
自从90年代初经典SVM的提出，由于其完整的理论框架和在实际应用中取得的很多好的效果，在机器学习领域受到了广泛的重视。其理论和应用在横向和纵向上都有了发展。
理论上：1.模糊支持向量机，引入样本对类别的隶属度函数，这样每个样本对于类别的影响是不同的，这种理论的应用提高了SVM的抗噪声的能力，尤其适合在未能完全揭示输入样本特性的情况下。
2．最小二乘支持向量机。这种方法是在1999年提出，经过这几年的发展，已经应用要很多相关的领域。研究的问题已经推广到：对于大规模数据集的处理；处理数据的鲁棒性；参数调节和选择问题；训练和仿真。
3．加权支持向量机（有偏样本的加权，有偏风险加权）。
4．主动学习的支持向量机。主动学习在学习过程中可以根据学习进程，选择最有利于分类器性能的样本来进一步训练分类器，特能有效地减少评价样本的数量。也就是通过某种标准对样本对分类的有效性进行排序，然后选择有效样本来训练支持向量机。
5．粗糙集与支持向量机的结合。首先利用粗糙集理论对数据的属性进行约简，能在某种程度上减少支持向量机求解计算量。
6．基于决策树的支持向量机。对于多类问题，采用二岔树将要分类的样本集构造出一系列的两类问题，每个两类构造一个SVM。
7．分级聚类的支持向量机。基于分级聚类和决策树思想构建多类svm，使用分级聚类的方法，可以先把n-1个距离较近的类别结合起来，暂时看作一类，把剩下的一类作为单独的一类，用svm分类，分类后的下一步不再考虑这单独的一类，而只研究所合并的n-1类，再依次下去。
8．算法上的提高。
l Vapnik在95年提出了一种称为”chunking”的块算法，即如果删除矩阵中对应Lagrange乘数为0的行和列，将不会影响最终结果。
l Osuna提出了一种分解算法，应用于人脸识别领域。
l Joachims在1998年将Osuna提出的分解策略推广到解决大型SVM学习的算法
l Platt于1998年提出了序贯最小优化（Sequential Minimal Optimization）每次的工作集中只有2个样本。
9．核函数的构造和参数的选择理论研究。基于各个不同的应用领域，可以构造不同的核函数，能够或多或少的引入领域知识。现在核函数广泛应用的类型有：多项式逼近、贝叶斯分类器、径向基函数、多层感知器。参数的选择现在利用交叉验证的方法来确认。
10．支持向量机从两类问题向多类问题的推广：
n Weston在1998年提出的多类算法为代表。在经典svm理论的基础上，直接在目标函数上进行改进，重新构造多值分类模型，建立k分类支持向量机。通过sv方法对新模型的目标函数进行优化，实现多值分类。这类算法选择的目标函数十分复杂，变量数目过多，计算复杂度也非常高，实现困难，所以只在小型问题的求解中才能使用。Weston,Multi-class support vector machines
n 一对多（one-against-rest）----- Vapnik提出的,k类---k个分类器，第m个分类器将第m类与其余的类分开，也就是说将第m类重新标号为1，其他类标号为-1。完成这个过程需要计算k个二次规划，根据标号将每个样本分开，最后输出的是两类分类器输出为最大的那一类。不足：容易产生属于多类别的点（多个1）和没有被分类的点（标号均为-1）--不对，训练样本数据大，训练困难，推广误差无界.
n 一对一（one-against-one）---Kressel 对于任意两个分类，构造一个分类器，仅识别这两个分类，完成这个过程需要k(k-1)/2个分类器，计算量是非常庞大的。对于每一个样本，根据每一个分类器的分类结果，看属于哪个类别的次数多，最终就属于哪一类(组合这些两类分类器并使用投票法，得票最多的类为样本点所属的类)。不足：如果单个两类分类器不规范化，则整个N类分类器将趋向于过学习；推广误差无界；分类器的数目K随类数急剧增加，导致在决策时速度很慢。
n 层（数分类方法），是对一对一方法的改进，将k个分类合并为两个大类，每个大类里面再分成两个子类，如此下去，直到最基本的k个分类，这样形成不同的层次，每个层次都用svm来进行分类------1对r-1法，构建k-1个分类器，不存在拒绝分类区。
应用上：人脸检测，汽轮发电机组的故障诊断，分类，回归，聚类，时间序列预测，系统辨识，金融工程，生物医药信号处理，数据挖掘，生物信息，文本挖掘，自适应信号处理，剪接位点识别，基于支持向量机的数据库学习算法，手写体相似字识别，支持向量机函数拟合在分形插值中的应用，基于支持向量机的惯导初始对准系统，岩爆预测的支持向量机，缺陷识别，计算机键盘用户身份验证，视频字幕自动定位于提取，说话人的确认，等等。
主要研究热点
从上面的发展中，我们可以总结出，目前支持向量机有着几方面的研究热点：核函数的构造和参数的选择；支持向量机从两类问题向多类问题的推广；更多的应用领域的推广；与目前其它机器学习方法的融合；与数据预处理（样本的重要度，属性的重要度，特征选择等）方面方法的结合，将数据中脱离领域知识的信息，即数据本身的性质融入支持向量机的算法中从而产生新的算法；支持向量机训练算法的探索。
自从90年代初经典SVM的提出，由于其完整的理论框架和在实际应用中取得的很多好的效果，在机器学习领域受到了广泛的重视。其理论和应用在横向和纵向上都有了发展。
理论上：1.模糊支持向量机，引入样本对类别的隶属度函数，这样每个样本对于类别的影响是不同的，这种理论的应用提高了SVM的抗噪声的能力，尤其适合在未能完全揭示输入样本特性的情况下。
2．最小二乘支持向量机。这种方法是在1999年提出，经过这几年的发展，已经应用要很多相关的领域。研究的问题已经推广到：对于大规模数据集的处理；处理数据的鲁棒性；参数调节和选择问题；训练和仿真。
3．加权支持向量机（有偏样本的加权，有偏风险加权）。
4．主动学习的支持向量机。主动学习在学习过程中可以根据学习进程，选择最有利于分类器性能的样本来进一步训练分类器，特能有效地减少评价样本的数量。也就是通过某种标准对样本对分类的有效性进行排序，然后选择有效样本来训练支持向量机。
5．粗糙集与支持向量机的结合。首先利用粗糙集理论对数据的属性进行约简，能在某种程度上减少支持向量机求解计算量。
6．基于决策树的支持向量机。对于多类问题，采用二岔树将要分类的样本集构造出一系列的两类问题，每个两类构造一个SVM。
7．分级聚类的支持向量机。基于分级聚类和决策树思想构建多类svm，使用分级聚类的方法，可以先把n-1个距离较近的类别结合起来，暂时看作一类，把剩下的一类作为单独的一类，用svm分类，分类后的下一步不再考虑这单独的一类，而只研究所合并的n-1类，再依次下去。
8．算法上的提高。
l Vapnik在95年提出了一种称为”chunking”的块算法，即如果删除矩阵中对应Lagrange乘数为0的行和列，将不会影响最终结果。
l Osuna提出了一种分解算法，应用于人脸识别领域。
l Joachims在1998年将Osuna提出的分解策略推广到解决大型SVM学习的算法
l Platt于1998年提出了序贯最小优化（Sequential Minimal Optimization）每次的工作集中只有2个样本。
9．核函数的构造和参数的选择理论研究。基于各个不同的应用领域，可以构造不同的核函数，能够或多或少的引入领域知识。现在核函数广泛应用的类型有：多项式逼近、贝叶斯分类器、径向基函数、多层感知器。参数的选择现在利用交叉验证的方法来确认。
10．支持向量机从两类问题向多类问题的推广：
n Weston在1998年提出的多类算法为代表。在经典svm理论的基础上，直接在目标函数上进行改进，重新构造多值分类模型，建立k分类支持向量机。通过sv方法对新模型的目标函数进行优化，实现多值分类。这类算法选择的目标函数十分复杂，变量数目过多，计算复杂度也非常高，实现困难，所以只在小型问题的求解中才能使用。Weston,Multi-class support vector machines
n 一对多（one-against-rest）----- Vapnik提出的,k类---k个分类器，第m个分类器将第m类与其余的类分开，也就是说将第m类重新标号为1，其他类标号为-1。完成这个过程需要计算k个二次规划，根据标号将每个样本分开，最后输出的是两类分类器输出为最大的那一类。不足：容易产生属于多类别的点（多个1）和没有被分类的点（标号均为-1）--不对，训练样本数据大，训练困难，推广误差无界.
n 一对一（one-against-one）---Kressel 对于任意两个分类，构造一个分类器，仅识别这两个分类，完成这个过程需要k(k-1)/2个分类器，计算量是非常庞大的。对于每一个样本，根据每一个分类器的分类结果，看属于哪个类别的次数多，最终就属于哪一类(组合这些两类分类器并使用投票法，得票最多的类为样本点所属的类)。不足：如果单个两类分类器不规范化，则整个N类分类器将趋向于过学习；推广误差无界；分类器的数目K随类数急剧增加，导致在决策时速度很慢。
n 层（数分类方法），是对一对一方法的改进，将k个分类合并为两个大类，每个大类里面再分成两个子类，如此下去，直到最基本的k个分类，这样形成不同的层次，每个层次都用svm来进行分类------1对r-1法，构建k-1个分类器，不存在拒绝分类区。
应用上：人脸检测，汽轮发电机组的故障诊断，分类，回归，聚类，时间序列预测，系统辨识，金融工程，生物医药信号处理，数据挖掘，生物信息，文本挖掘，自适应信号处理，剪接位点识别，基于支持向量机的数据库学习算法，手写体相似字识别，支持向量机函数拟合在分形插值中的应用，基于支持向量机的惯导初始对准系统，岩爆预测的支持向量机，缺陷识别，计算机键盘用户身份验证，视频字幕自动定位于提取，说话人的确认，等等。
主要研究热点
从上面的发展中，我们可以总结出，目前支持向量机有着几方面的研究热点：核函数的构造和参数的选择；支持向量机从两类问题向多类问题的推广；更多的应用领域的推广；与目前其它机器学习方法的融合；与数据预处理（样本的重要度，属性的重要度，特征选择等）方面方法的结合，将数据中脱离领域知识的信息，即数据本身的性质融入支持向量机的算法中从而产生新的算法；支持向量机训练算法的探索。
假设x、x0∈RN，以x0为中心，x到x0的径向距离为半径所形成的‖x-x0‖构成的函数系满足k(x)＝O。‖x-x0‖称为径向基函数。
考虑径向基函数插值在一些不同领域的来源.
最早可能是Krige ,他在1951 年把矿藏的沉积看成是一个各向同性的稳定的随机函数的实现. 从而导出了广泛应用于矿藏分析的Kriging 方法. 在这方面的进一步深入的理论工作主要是由Mathron 完成的.
1971 年Hardy 用径向基函数Multi-Quadric来处理飞机外形设计曲面拟合问题, 取得了非常好的效果.
1975 年Duchon 从样条弯曲能最小的理论出发导出了多元问题的薄板样条. 这些从不同领域导出的方法, 事实上都是径向基函数的插值方法,
他们所用的径向基函数有:
1)Kriging 方法的Gauss 分布函数
2)Hardy 的Multi2Quadric 函数
3)Duchon 的薄板样条
考虑径向基函数插值在一些不同领域的来源.
最早可能是Krige ,他在1951 年把矿藏的沉积看成是一个各向同性的稳定的随机函数的实现. 从而导出了广泛应用于矿藏分析的Kriging 方法. 在这方面的进一步深入的理论工作主要是由Mathron 完成的.
1971 年Hardy 用径向基函数Multi-Quadric来处理飞机外形设计曲面拟合问题, 取得了非常好的效果.
1975 年Duchon 从样条弯曲能最小的理论出发导出了多元问题的薄板样条. 这些从不同领域导出的方法, 事实上都是径向基函数的插值方法,
他们所用的径向基函数有:
1)Kriging 方法的Gauss 分布函数
2)Hardy 的Multi2Quadric 函数
3)Duchon 的薄板样条
