MultiClass SVM尝试分类的问题

最近拿到一些数据, 是从Image中提取出来的训练数据和测试样本, 训练数据共有120W左右的训练样本, 1K维特征, 1K个类别. 4G的数据量分成了11个子文件按类别进行顺序存储(注: 不是随即采样存储, 这也给后面的训练带来了麻烦). 然后尝试进行Linear SVM训练, 或者说只是做一个测试, 因为直观上来讲如此多类别进行传统分类器效果肯定不好. 这里还是把测试中遇到的一些问题都记录下来, 做为后期尝试改进的一个起点吧:-). 然后就开始测试的第一步, 考虑如此高维特征, 那么把线性超平面\(f({\bf{x}}) = {\bf{w}} \cdot {\bf{x}} + b\)中的\(b\)去掉也不会对结果有大的影响, 而且带L2损失的目标函数在求取梯度和Hessian矩阵时会简化很多. \[\begin{array}{l} \nabla {\rm{ = }}\left[ {\begin{array}{*{20}{c}} {\frac{{df}}{{d{\bf{w}}}}}\\ {\frac{{df}}{{db}}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {2{\bf{w}} + 2C\sum\limits_{i … 继续阅读

共轭梯度法在SVM原问题参数优化中的应用

1. 共轭性 关于共轭先了解一下其基本性质, 共轭性的定义为: 设\(A \in {R^{n \times n}}\)是对称正定矩阵. 称\({{\bf{p}}_1},{{\bf{p}}_2}\)是 -共轭的, 是指 \({\bf{p}}_1^TA{{\bf{p}}_2}{\rm{ = }}0,\begin{array}{*{20}{c}} {} \end{array}{\bf{p}}_1^TA{{\bf{p}}_1} > 0,\begin{array}{*{20}{c}} {} \end{array}{\bf{p}}_2^TA{{\bf{p}}_2} > 0\) 那么它的性质有: 1). 设有\({{\bf{p}}_1},{{\bf{p}}_2},…,{{\bf{p}}_m}(m < n)\)是彼此共轭的\(n\)维向量, 即 \[{\bf{p}}_i^TA{{\bf{p}}_j}\left\{ {\begin{array}{*{20}{c}} { = 0,\begin{array}{*{20}{c}} {} \end{array}i \ne j,}\\ { > … 继续阅读

牛顿法在SVM原问题参数优化中的应用

1. 牛顿法 牛顿法又称为二次函数法或二阶梯度法. 梯度法的缺点是有可能使搜索过程收敛很慢. 因此, 在某些情况下, 它并非是有效的迭代方法. 牛顿法在搜索方向上比梯度法有所改进, 这一方法不仅利用了准则函数在搜索点的梯度, 而且还利用了它的二次导数, 就是说利用了搜索点所能提供的更多信息, 使搜索方向能更好地指向最优点. 牛顿的基本思想是企图一步达到最优点, 即一步达到\(J({\bf{w}})\)的最小值. 仍然考虑\(J({\bf{w}})\)的二阶泰勒展开式 \[J({\bf{w}}){\rm{\dot = }}J({{\bf{w}}_k}) + \nabla {J^{\rm{T}}}({\bf{w}} - {{\bf{w}}_k}) + \frac{1}{2}{({\bf{w}} - {{\bf{w}}_k})^{\rm{T}}}D({\bf{w}} - {{\bf{w}}_k})\] 若令\({\bf{w}} = {{\bf{w}}_{k + 1}}\)得 \[J({{\bf{w}}_{k{\rm{ + }}1}}){\rm{\dot = }}J({{\bf{w}}_k}) + … 继续阅读

Reading Paper: Support Vector Machines in the primal

Author: Olivier Chapelle (France)   criteo labs Personal Website:  http://olivier.chapelle.cc/ • Yahoo! Research, Machine Learning group. (Oct.2006 – present) Senior Research Scientist Main projects are on machine learning applied to web search ranking and display advertising. • Max Planck Institute, Tubingen, … 继续阅读

LibSVM 3.12的源码分析Svm-train.c

共涉及3个文件: Svm-train.c, Svm.cpp, Svm.h. 建议使用Source Insight软件对这3个文件建立工程. 方便代码阅读. 下面从Svm-train.c文件中的main()函数切入. int main(int argc, char **argv) { char input_file_name[1024]; //训练样本文件名 char model_file_name[1024]; //输出模型的文件名 const char *error_msg; parse_command_line(argc, argv, input_file_name, model_file_name); //解析运行程序时,命令行输入的参数 read_problem(input_file_name); //读入训练样本,存入到struct svm_problem prob结构体中 error_msg = svm_check_parameter(&prob,&param); //检查训练样本数据格式是否正确 if(error_msg) { fprintf(stderr,“ERROR: %s\n”,error_msg); … 继续阅读

libsvm的使用

1: 了解libsvm工具包 LIBSVM是台湾大学林智仁(Lin Chih-Jen)教授等2001年开发设计的一个简单, 易于使用和快速有效的SVM模式识别与回归的软件包, 他不但提供了编译好的可在Windows系列系统的执行文件, 还提供了源代码, 方便改进, 修改以及在其它操作系统上应用; 该软件对SVM所涉及的参数调节相对比较少, 提供了很多的默认参数, 利用这些默认参数可以解决很多问题; 并提供了交互检验(Cross Validation)的功能. 该软件包可在http://www.csie.ntu.edu.tw/~cjlin/ 免费获得. 该软件可以解决C-SVM, ν-SVM, ε-SVR和ν-SVR等问题, 包括基于一对一算法的多类模式识别问题. 这套库可以从http://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html免费获得, 目前已经发展到3.12版(2012.4.1更新).下载.tar.gz格式的版本, Windows下也可以直接解压, 主要有6个文件夹和一些源码文件. Java: 主要是应用于java平台; matlab: windows下64位matlab平台; python: 是用来参数优选的工具, 稍后介绍; svm-toy: 一个可视化的工具, 用来展示训练数据和分类界面, 里面是源码, 其编译后的程序在windows文件夹下; tools: 主要包含四个python文件, 用来数据集抽样(subset), 参数优选(grid), … 继续阅读

最优化理论与KKT条件

1. 最优化理论(Optimization Theory) 最优化理论是研究函数在给定一组约束条件下的最小值(或者最大值)的数学问题. 一般而言, 一个最优化问题具有如下的基本形式: \[\min .:f({\bf{x}})\] \[\begin{array}{*{20}{c}} {{\rm{s}}{\rm{.t}}{\rm{.:}}} & {{g_i}({\bf{x}}) \le 0,i = 1,2,...,p,} \\ {} & {{h_j}({\bf{x}}) = 0,k = 1,2,...,q,} \\ {} & {{\bf{x}} \in \Omega \subset {{\bf{R}}^n}} \\ \end{array}\] 其中. \(f({\bf{x}})\)为目标函数, \({g_i}({\bf{x}}) \le 0,i = … 继续阅读

支持向量机导论3: 核函数特征空间

Chapter 3: 核函数特征空间(Kernel-Induced Feature Spaces) 现实世界复杂的应用需要有比线性函数更富有表达能力的假设空间. 核表示(Kernel representations)方法提供了一条解决途径, 即将数据映射到高维空间来增加线性学习器的计算能力. 线性学习器对偶空间的表达方式使得这个步骤的隐式操作成为可能. 本章的目的就是展示如何映射到高维空间使得线性分类更容易. 3.1 特征空间中的学习(Learning in Feature Space) 需要学习的目标函数的复杂程度取决于它的表示方式. 因此, 在机器学习中一个普通的预处理策略包括改变数据的表达形式: \({\bf{x}} = \left( {{x_1},…,{x_n}} \right) \to \phi \left( {\bf{x}} \right) = \left( {{\phi _1}({\bf{x}}),…,{\phi _N}({\bf{x}})} \right)\). 这个步骤等价于将输入空间\(X\)映射到一个新的空间, \(F = \left( {\phi … 继续阅读

支持向量机导论2: 线性学习器

Chapter 2: 线性学习器(Linear Learning Machines) 2.1 线性分类(Linear Classification) 两类问题函数可以写成: \(f({\bf{x}}) = \left\langle {{\bf{w}}\cdot{\bf{x}}} \right\rangle  + b = \sum\limits_{i = 1}^n {{w_i}{x_i}}  + b \). 这里\(\left( {{\bf{w}},b} \right) \in {{\rm{R}}^{\rm{n}}} \times {\rm{R}}\)是控制函数的参数, 决策规则由\({\mathop{\rm sgn}} (f({\bf{x}}))\)给出, 惯例, \({\mathop{\rm sgn}} (0) = 1\). … 继续阅读

支持向量机导论1: 学习方法

中文名: [支持向量机导论] 英文名:[An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods] 中/英文版电子书下载连接: http://download.csdn.net/detail/jacoxu/4434131 本书作者Nello和John建立了SVM网站http://www.support-vector.net/ 提供在线的参考文献和一些软件的连接.  对于刚入门了解SVM的读者可先参看July整理的[支持向量机通俗导论(理解SVM的三层境界)] http://blog.csdn.net/v_july_v/article/details/7624837 .  SVM是在统计学习理论基础上发展起来的新一代学习算法. 是机器学习领域若干标准技术的集大成者. 它集成了最大间隔平面, Mercer核, 凸二次规划, 稀疏解和松弛变量等多项技术. SVM的理论体系涵盖了对偶表示(dual representations), 特征空间(feature spaces), 学习理论(learning theory), 优化理论(optimization theory)和算法(algorithms)等. 本书从学习方法到超平面, 核函数, 泛化性理论, 最优化理论, 最后到SVM. 循序渐渐, … 继续阅读