我一直觉得 SVM 是个很有趣的东西.doc

我一直觉得 SVM 是个很有趣的东西，不过也一直没办法 (mostly 冲堂 ) 去听 林智仁老师 的 Data mining 跟 SVM 的课； 后来看了一些网络上的文件跟听 kcwu 讲了一下 libsvm 的用法后，就想整理一下，算是对于并不需要知道完整 SVM 理论的人提供使用 libsvm 的入门。 原始 libsvm 的 README 跟 FAQ 也是很好的文件， 不过你可能要先对 svm 跟流程有点了解才看得懂 ( 我在看时有这样的感觉 ) ； 这篇入门就是为了从零开始的人而写的。后来还有一些人提供意见，所以在此要感谢：不过请记得底下可能有些说法不一定对，但是对于只是想用 SVM 的人来说我觉得这样说明会比较易懂。 这篇入门原则上是给会写基本程序的人看的，也是给我自己一个备忘 , 不用太多数学底子，也不用对 SVM 有任何先备知识。 还看不懂的话有三个情形 , 一是我讲的不够清楚 , 二是你的常识不足 , 三是你是小白 ; 我自己是以完全不懂的角度开始的，这篇入门也有不少一样不懂 SVM 的人 看过、而且看完多半都有一定程度的理解，所以假设情况一不会发生， 那如果不懂一定是后两个情况 :P 也所以 , 有问题别问我。SVM, Support Vector Machine , 简而言之它是个起源跟类神经网络有点像的东西， 不过现今最常拿来就是做分类 (classification) 。 也就是说，如果我有一堆已经分好类的东西 （可是分类的依据是未知的！） ，那当收到新的东西时， SVM 可以预测 (predict) 新的数据要分到哪一堆去。 SVM, Support Vector Machine , 听起来是很神奇的事（如果你觉得不神奇，请重想一想这句话代表什么： 分类的依据是未知的！ ，还是不神奇的话就请你写个程序 解解看这个问题）， 也很像要 AI 之类的高等技巧 . 不过 SVM 基于 统计学习理论 可以在合理的时间内漂亮的解决这个问题。 以图形化的例子来说明 (by SVMToy), 像假定我在空间中标了一堆用颜色分类的点 , 点的颜色就是他的类别 , 位置就是他的数据 , 那 SVM 就可以找出区隔这些点的方程式 , 依此就可以分出一区区的区域 ; 拿到新的点 ( 数据 ) 时 , 只要对照该位置在哪一区就可以 (predict) 找出他应该是哪一颜色 ( 类别 ) 了 : 当然 SVM 不是真的只有画图分区那么简单 , 不过看上面的例子应该可以了解 SVM 大概在作什么 . 要对 SVM 再多懂一点点，可以参考 cjlin 在 data mining 课的 slides: pdf or ps 。 底下我试着在不用看那个 slide 的情况 解释及使用 libsvm 。 所以 , 我们可以把 SVM 当个黑盒子 , 数据丢进去让他处理然后我们再来用就好了 . How do I get SVM? 林智仁(cjlin) 老师 的 libsvm 当然是最完美的工具 . Download libsvm 下载处 : Download Location: url=.tw/cjlin/cgi-bin/libsvm.cgi?+.tw/%7Ecjlin/libsvm+ziplibsvm.zip /urlor url=.tw/cjlin/cgi-bin/libsvm.cgi?+.tw/%7Ecjlin/libsvm+tar.gzlibsvm.tar.gz /url.zip 跟 .tar.gz 基本上是一样的 , 只是看你的 OS; 习惯上 Windows 用 .zip 比较方便 ( 因为有 WinZIP, 不过我都用 WinRAR), UNIX 则是用 .tar.gzThe programs 解释一下几个主要执行档的作用 : (UNIX/Windows 下檔名稍有不同 , 请用常识理解我在讲哪个 ) Train ( 训练 ) data. 跑 SVM 被戏称为 开火车 也是由于这个程序名而来 . train 会接受特定格式的输入 , 产生一个 Model 檔 . 这个 model 你可以想象成 SVM 的内部数据 , 因为 predict 要 model 才能 predict, 不能直接吃原始数据 . 想想也很合理 , 假定 train 本身是很耗时的动作 , 而 train 好可以以某种形式存起内部数据 , 那下次要 predict 时直接把那些内部数据 load 进来就快多了 . svmpredict 依照已经 train 好的 model, 再加上给定的输入 ( 新值 ), 输出 predict ( 预测 ) 新值所对应的类别 (class). svmscale Rescale data. 因为原始数据可能范围过大或过小 , svmscale 可以先将数据重新 scale ( 缩放 ) 到适当范围 . File Format 档案格式要先交代一下 . 你可以参考 libsvm 里面附的 一行一笔资料，如 One record per line, as: +1 1:0.708 2:1 3:1 4:-0.320 5:-0.105 6:-1 label 或说是 class, 就是你要分类的种类，通常是一些整数。 index 是有顺序的索引，通常是放连续的整数。 value 就是用来 train 的数据，通常是一堆实数。 每一行都是如上的结构 , 意思就是 : 我有一排资料 , 分别是 value1, value2, . valueN, ( 而且它们的顺序已由 indexN 分别指定 ) ，这排数据的分类结果就是 label 。或许你会不太懂，为什么会是 value1,value2,. 这样一排呢？ 这牵涉到 SVM 的原理。你可以这样想（我没说这是正确的）， 它的名字就叫 Support Vector Machine ，所以输入的 training data 是 Vector( 向量 ), 也就是一排的 x1, x2, x3, . 这些值就是 valueN ，而 xn 的 n 就是 由 indexN 指定。这些东西又称为 attribute 。 真实的情况是， 大部份时候我们给定的数据可能有很多 特征 (feature) 或说 属性 (attribute) ，所以输入会是 一组的。举例来说，以前面 画点分区的例子 来说，我们不是每个点都有 X 跟 Y 的坐标吗？ 所以它就有 两种 attribute 。 假定我有两个点： (0,3) 跟 (5,8) 分别在 label(class) 1 跟 2 ，那就会写成 1 1:0 2:3 2 1:5 2:8 同理，空间中的三维坐标就等于有三组 attribute 。这种档案格式最大的好处就是可以使用 sparse matrix ， 或说有些 data 的 attribute 可以不存在。 To Run libsvm 来解释一下 libsvm 的程序怎么用。 你可以先拿 libsvm 附的 heart_scale 来做输入，底下也以它为例： 看到这里你应该也了解，使用 SVM 的流程大概就是： 1. 准备数据并做成指定 格式 ( 有必要时需 svmscale) 2. 用 svmtrain 来 train 成 model 3. 对新的输入，使用 svmpredict 来 predict 新数据的 svmtrain svmtrain 的语法大致就是 : The syntax of svmtrain is basically: svmtrain options training_set_file model_file training_set_file 就是之前的格式，而 model_file 如果不给就会 叫 training_set_file.model 。 options 可以先不要给。 下列程序执行结果会产生 heart_scale.model 檔： ( 屏幕输出不是很重要，没有错误就好了 ) ./svm-train heart_scale optimization finished, #iter = 219 nu = 0.431030 obj = -100.877286, rho = 0.424632 nSV = 132, nBSV = 107 Total nSV = 132 svmpredict svmpredict 的语法是 : The syntax to svm-predict is: svmpredict test_file model_file output_file test_file 就是我们要 predict 的数据。它的格式跟 svmtrain 的输入，也就是 training_set_file 是一样的！不过每行最前面的 label 可以省略 ( 因为 predict 就是要 predict 那个 label) 。 但如果 test_file 有 label 的值的话， predict 完会顺便拿 predict 出来的值跟 test_file 里面写的值去做比对，这代表： test_file 写的 label 是真正的分类结果，拿来跟我们 predict 的结果比对就可以 知道 predict 有没有猜对了。 也所以，我们可以拿原 training set 当做 test_file 再丢给 svmpredict 去 predict ( 因为格式一样 ) ，看看正确率有多高， 方便后面调参数。 其它参数就很好理解了： model_file 就是 svmtrain 出来 的档案， output_file 是存输出结果的档案。 输出的格式很简单，每行一个 label ，对应到你的 test_file 里面的各行。下列程序执行结果会产生 我们把原输入丢回去 predict ， 第一行的 Accuracy 就是预测的正确率了。 如果输入没有 label 的话，那就是真的 predict 了。 看到这里，基本上你应该已经可以利用 svm 来作事了： 你只要写程序输出正确格式的数据，交给 svm 去 train ， 后来再 predict 并读入结果即可。 Advanced Topics 后面可以说是一些稍微进阶的部份，我可能不会讲的很清楚，因为我的重点是想表达一些观念和解释一些你看相关文件时 很容易碰到的名词。 Scaling svm-scale 目前不太好用，不过它有其必要性。因为 适当的 scale 有助于参数的选择 ( 后述 ) 还有解 svm 的速度。 svmscale 会对每个 attribute 做 scale 。 范围用 -l, -u 指定， 通常是 0,1 或是 -1,1 。 输出在 stdout 。 另外要注意的 ( 常常会忘记 ) 是 testing data 和 training data 要一起 scale 。 而 svm-scale 最难用的地方就是没办法指定 testing data/training data( 不同档案 ) 然后一起 scale 。Arguments 前面提到，在 train 的时候可以下一些参数。 ( 直接执行 svm-train 不指定输入档与参数会列出所有参数及语法说明 ) 这些参数对应到原始 SVM 公式的一些参数，所以会影响 predict 的正确与否。 举例来说，改个 c=10: ./svm-train -c 10 heart_scale 再来 predict ，正确率马上变成 92.2% (249/270) 。 Cross Validation 一般而言， SVM 使用的方式 ( 在决定参数时 ) 常是这样： 1. 先有已分好类的一堆资料 2. 随机数拆成好几组 training set 3. 用某组参数去 train 并 predict 别组看正确率 4. 正确率不够的话，换参数再重复 train/predict 等找到一组不错的参数后，就拿这组参数来建 model 并用来做最后对未知数据的 predict 。 这整个过程叫 cross validation ， 也就是交叉比对。 在我们找参数的过程中，可以利用 svmtrain 的内建 cross validation 功能来帮忙： -v n: n-fold cross validation n 就是要拆成几组，像 n=3 就会拆成三组，然后先拿 1 跟 2 来 train model 并 predict 3 以得到正确率； 再来拿 2 跟 3 train 并 predict 1 ，最后 1,3 train 并 predict 2 。其它以此类推。 如果没有交叉比对的话，很容易找到只在特定输入时好的参数。像前面我们 c=10 得到 92.2% ，不过拿 -v 5 来看看： ./svm-train -v 5 -c 10 heart_scale . Cross Validation Accuracy = 80.3704% 平均之后才只有 80.37% ，比一开始的 86 还差。 通常而言，比较重要的参数是 gamma (-g) 跟 cost (-c) 。而 cross validation (-v) 的参数常用 5 。 cost 默认值是 1, gamma 默认值是 1/k ， k 等于输入 数据笔数。 那我们怎么知道要用多少来当参数呢？ 用 试 的 是的，别怀疑，就是 Try 参数找比较好的值。 Try 参数的过程常用 exponential 指数成长的方式来增加与减少参数的数值，也就是 2n (2 的 n 次方 ) 。因为有两组参数，所以等于要 try n*n=n2 次。 这个过程是不连续的成长，所以可以想成我们在一个 X-Y 平面上指定的范围内找一群格子点 ( grid ， 如果你不太明白，想成方格纸或我们把平面上所有 整数交点都打个点，就是那样 ) ，每个格子点的 X 跟 Y 经过换算 ( 如 2x, 2y) 就拿去当 cost 跟 gamma 的值来 所以现在你应该懂得 libsvm 的 python 子目录下面 有个 grid.py 是做啥的了： 它把上面的过程自动化， 在你给定的范围内呼叫 svm-train 去 try 所有的参数值。 python 是一种语言，在这里我不做介绍，因为我会了 :P (just a joke ，真正原因是 - 这是 libsvm 的 tutorial) 。 grid.py 还会把结果 plot 出来，方便你寻找参数。 libsvm 有很多跟 python 结合的部份，由此可见 python 是强大方便的工具。很多神奇的功能，像自动登入多台 机器去平行跑 grid 等等都是 python 帮忙的。不过 SVM 本身可以完全不需要 python ，只是会比较方便。跑 grid ( 基本上用 grid.py 跑当然是最方便，不过 如果你不懂 python 而且觉得很难搞，那你要自己产生 参数来跑也是可以的 ) 通常好的范围是 c,g=2-10,210*2-10,210 另外其实 grid 用 -8,8 也很够了。 另一个值得一提的是 regression 。 简单来说，前面都是拿 SVM 来做分类 (classification), 所以 label 的值都是 discrete data 、或说已知的固定值。 而 regression 则