QxRed » 2008年 » 1月
svm中的x,y与f(x,y)的对应关系
风暴红QxRed 发表于 2008-01-30 09:52:16
在multi-class kernel based vector machines中用的是M,x,y
在max margin markov networks中用的是f(x,y),w
这两者之间的对应关系如下：
w'f(x,y)=My' x
f1(x,y)
f2(x,y)
...
fn(x,y)
相当于
x
f(x,yi)=
0 //f1(x,y1)
0 //f2(x,y1)
...
0 //fn(x,y1)
...
f1(x,yi)
f2(x,yi)
...
fn(x,yi)
...
0 //f1(x,yk)
0 //f2(x,yk)
...
0 //fn(x,yk)
w=
My1
My2
...
Myk
在max margin markov networks中用的是f(x,y),w
这两者之间的对应关系如下：
w'f(x,y)=My' x
f1(x,y)
f2(x,y)
...
fn(x,y)
相当于
x
f(x,yi)=
0 //f1(x,y1)
0 //f2(x,y1)
...
0 //fn(x,y1)
...
f1(x,yi)
f2(x,yi)
...
fn(x,yi)
...
0 //f1(x,yk)
0 //f2(x,yk)
...
0 //fn(x,yk)
w=
My1
My2
...
Myk
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
经典序列标注算法
风暴红QxRed 发表于 2008-01-29 15:57:36
HMM
MEMM
McCallum, A., Freitag, D., & Pereira, F. (2000). Maximum entropy Markov models for information extraction and segmentation. Proc. ICML 2000 (pp. 591–598). Stanford, California.
Conditional Random Fields
Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. International Conference on Machine Learning.
Averaged Perceptron
Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms.(2002)
MIRA
K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2003. Online passive aggressive algorithms. In Proc. NIPS.
Max Margin Markov Networks
Taskar, B., Guestrin, C., & Koller, D. (2003). Maxmargin markov networks. Advances in Neural Information Processing System
Hidden Markov Support Vector Machines
Yasemin Altun Ioannis Tsochantaridis Thomas Hofmann. Hidden Markov Support Vector Machines Proceedings of the 20th International Conference on Machine Learning (ICML 2003).
SVM struct
Tsochantaridis, I., Joachims, T., Hofmann, T., & Altun, Y. (2005). Large margin methods for structured and interdependent output variables.
SearN
Daum´e III, H., Langford, J., & Marcu, D. (2006). Search based structured prediction
MEMM
McCallum, A., Freitag, D., & Pereira, F. (2000). Maximum entropy Markov models for information extraction and segmentation. Proc. ICML 2000 (pp. 591–598). Stanford, California.
Conditional Random Fields
Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. International Conference on Machine Learning.
Averaged Perceptron
Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms.(2002)
MIRA
K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2003. Online passive aggressive algorithms. In Proc. NIPS.
Max Margin Markov Networks
Taskar, B., Guestrin, C., & Koller, D. (2003). Maxmargin markov networks. Advances in Neural Information Processing System
Hidden Markov Support Vector Machines
Yasemin Altun Ioannis Tsochantaridis Thomas Hofmann. Hidden Markov Support Vector Machines Proceedings of the 20th International Conference on Machine Learning (ICML 2003).
SVM struct
Tsochantaridis, I., Joachims, T., Hofmann, T., & Altun, Y. (2005). Large margin methods for structured and interdependent output variables.
SearN
Daum´e III, H., Langford, J., & Marcu, D. (2006). Search based structured prediction
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
一个简单的实验
风暴红QxRed 发表于 2008-01-27 17:20:41
数据：CRF++ 中的 basenp 的 train.data, template, test.data
所用版本：CRF++ 0.49, pocket crf 0.41, pocket M3N 0.10
评测程序：CoNLL 2000 shared task中的评测程序,conlleval.txt
实验一：CRF中 L2范式(高斯先验)对结果的影响
这里pocket crf和crf++结果完全相同
当sigma=10000时效果最好。
实验二：CRF中 L1范式对结果的影响
由于CRF++中直接将L1范式优化的结果作为最后的结果，而pocket crf再L1优化后继续用L2优化，所以两者没有直接可比性。这里只比较同一算法下，不同参数的影响。
注：pocket crf和CRF++的L1优化算法不一样，所以有时候pocket crf会learning failed,而CRF++不会，反之亦然。
CRF++
pocket crf,这里sigma=10000
实验三：M3N
参数：松弛向量惩罚因子C=1,max iter为最大迭代次数
去掉%y[-1]%y[0]，(M3N实际上变成了SVM)
实验四：M3N训练情况
使用3种kernel 所用时间差不多，迭代50次大约都为半小时。下图给出了目标函数随迭代次数的变化，所用算法为Struct SMO
所用版本：CRF++ 0.49, pocket crf 0.41, pocket M3N 0.10
评测程序：CoNLL 2000 shared task中的评测程序,conlleval.txt
实验一：CRF中 L2范式(高斯先验)对结果的影响
这里pocket crf和crf++结果完全相同
| 高斯先验(sigma) | F-Value |
| 0.1 | 84.42 |
| 1 | 86.17 |
| 10 | 86.41 |
| 100 | 86.42 |
| 1000 | 86.56 |
| 10000 | 86.65 |
| 100000 | 86.57 |
| 1000000 | 86.59 |
| 10000000 | 86.24 (learning failed) |
| 100000000 | 85.91 (learning failed) |
当sigma=10000时效果最好。
实验二：CRF中 L1范式对结果的影响
由于CRF++中直接将L1范式优化的结果作为最后的结果，而pocket crf再L1优化后继续用L2优化，所以两者没有直接可比性。这里只比较同一算法下，不同参数的影响。
注：pocket crf和CRF++的L1优化算法不一样，所以有时候pocket crf会learning failed,而CRF++不会，反之亦然。
CRF++
| L1 | F-Value |
| 0.1 | (learning failed) |
| 1 | 84.97 |
| 10 | 85.54 |
| 100 | 84.90 |
| 1000 | 86.12 |
| 10000 | 85.96 |
| 100000 | 85.84 |
| 1000000 | (learning failed) |
| 10000000 | 85.88 |
| 100000000 | (learning failed) |
pocket crf,这里sigma=10000
| L1 | F-Value |
| 0.1 | 78.05 |
| 1 | 82.14 |
| 10 | 85.85 |
| 100 | 87.08 |
| 1000 | 86.70 |
| 10000 | 87.01 |
| 100000 | 87.08 |
| 1000000 | 87.19 |
| 10000000 | 86.63 (learning failed) |
| 100000000 | 86.84 (learning failed) |
实验三：M3N
参数：松弛向量惩罚因子C=1,max iter为最大迭代次数
| kernel | max iter | F value |
| linear | 50 | 86.87 |
| <a,b>^2 | 50 | 87.36 |
| <a,b>^3 | 50 | 85.50 |
| <a,b>^4 | 50 | 84.05 |
| tanh(0.1*<a,b>) | 10 | 86.97 |
| tanh(<a,b>) | 10 | 15.39 |
| exp{-0.01*||a-b||^2} | 10 | 16.49 |
| (<a,b>+1)^2 | 50 | 87.57 |
去掉%y[-1]%y[0]，(M3N实际上变成了SVM)
| Kernel | F-Value |
| linear | 86.94 |
| quad | 86.92 |
| cubic | 85.42 |
| <xi,xj>^4 | 84.05 |
实验四：M3N训练情况
使用3种kernel 所用时间差不多，迭代50次大约都为半小时。下图给出了目标函数随迭代次数的变化，所用算法为Struct SMO
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
pocket crf 0.41 released
风暴红QxRed 发表于 2008-01-26 17:12:57
http://sourceforge.net/project/showfiles.php?group_id=201943
- Pocket CRF 0.41
- Refine feature count cut off method
- Can perform L1 norm regularization for feature selection
- Can perform multi-thread training
- Old APIs in version 0.40 are remained, can read version 0.40 model file
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
pocket M3N居然正确运行了
风暴红QxRed 发表于 2008-01-23 15:24:17
虽然并不确定完全正确，但是目前状况良好。本来想低调一点的，可是今天能够调通实在让我太激动了，而且blog就是自己的地盘，随意填涂的，哈哈！不过目前速度很慢，一句长度为6的句子需要迭代1600多次，下面要花心思在速度方面，要设计好kernel cache。相比于CRF，关于M3N的paper实在不多，不知道那些大牛们是如何让M3N跑完的。就和inwidth说的一样，在实践方面，不知道这玩意是否真的管用，总之很神秘。
我想M3N是我最后一个需要写的分类器了，因为就我所知，这是目前结构化机器学习中效果最好的分类器，而且功能和CRF一样，可以用来做序列标注、projective tree parsing, non projective tree parsing, word alighment。等弄好这东西，在米国剩下的时间就看convex吧。
，睡觉啦
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
程序失败了，郁闷
风暴红QxRed 发表于 2008-01-19 12:47:34
pocket M3N收敛太慢，几乎不收敛。不知道哪里有问题。目标函数不单调（只有在所有句子长度为1的时候单调），两个长度为5的句子就要迭代29000多次。郁闷。
Ben Taskar的M3N到我的手里就只能做SVM用了
Ben Taskar的M3N到我的手里就只能做SVM用了
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
M3N中定理1的证明
风暴红QxRed 发表于 2008-01-16 14:56:06
\Pi_{t=0}^l mu(y_{t-c},...,y_t)
--------------------------------------
\Pi_{t=0}^{l-1} mu(y_{t-c+1},...,y_t)
\Pi_{t=0}^l [a(y_{t-c},...,y_{t-1})*b(y_{t-c+1},...,y_t)*phi(y_{t-c},...,y_t)/Z]
= ------------------------------------------------------------------------------------------------------
\Pi_{t=0}^{l-1} [\sum_{y_{t-c}}a(y_{t-c},...,y_{t-1})*b(y_{t-c+1},...,y_t)*phi(y_{t-c},...,y_t)/Z]
1 a(y_{t-c},...,y_{t-1})*phi(y_{t-c},...,y_t)
= --- * \Pi_{t=0}^{l-1}-------------------------------------------------------------------- * a(y_{l-c},...,y_{l-1}) * b(y_{l-c+1},...,y_l) * phi(y_{l-c},...,y_l)
Z \sum_{y_{t-c}}a(y_{t-c},...,y_{t-1})*phi(y_{t-c},...,y_t)
1 ; a(y_{t-c},...,y_{t-1})
= [--- * \Pi_{t=0}^l phi(y_{t-c},...,y_t)] * \Pi_{t=0}^{l-1} ----------------------------------------------------------- * a(y_{l-c},...,y_{l-1}) * b(y_{l-c+1},...,y_l)
Z \sum_{y_{t-c}}a(y_{t-c},...,y_{t-1})*phi(y_{t-c},...,y_t)
a(y_{t-c},...,y_{t-1})
= p(y) * \Pi_{t=0}^{l-1} ------------------------- * a(y_{l-c},...,y_{l-1}) * b(y_{l-c+1},...,y_l)
a(y_{t-c+1},...,y_t)
b(y_{l-c+1},...,y_l) * \Pi_{t=0}^l a(y_{t-c},...,y_{t-1})
= p(y) * -----------------------------------------------------------
\Pi_{t=1}^l a(y_{t-c},...,y_{t-1})
= p(y) * b(y_{l-c+1},...,y_l) * a(y_{-c},...,y_{-1})
= p(y)
(since b(y_{l-c+1},...,y_l) = a(y_{-c},...,y_{-1}) = 1)
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
training SVM, cutting plane SMO vs SMO
风暴红QxRed 发表于 2008-01-14 15:07:35
cutting plane SMO, see
"Large Margin Methods for Structured and Interdependent Output Variables"
一开始constraint为空，然后逐步加入约束。
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 1000 kkt violation: 0.00306138
iter: 2000 kkt violation: 7.47682e-005
iter: 3000 kkt violation: 0.081229
iter: 4000 kkt violation: 2.31152e-005
iter: 5000 kkt violation: 0.0259311
iter: 6000 kkt violation: 0.109375
iter: 7000 kkt violation: 0.0972222
iter: 8000 kkt violation: 0.00520834
elapse: 16.125 s
1881.61
Press any key to continue . . .
稀疏度：3543/5688=62.3%
SMO:
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 1000 kkt violation: 0.0435863
iter: 2000 kkt violation: 0.00907374
iter: 3000 kkt violation: 0.00207684
iter: 4000 kkt violation: 0.000510923
iter: 5000 kkt violation: 0.000115157
iter: 6000 kkt violation: 2.56447e-005
iter: 7000 kkt violation: 5.75994e-006
iter: 8000 kkt violation: 1.32601e-006
total iter: 8191
elapse: 1.281 s
1879.83
Press any key to continue . . .
稀疏度：2148/5688=37.8%
可见cutting plane逐步引入约束使得支持向量变少，只用少量的约束进行训练，这在机构化机器学习中可以大大提高速度
"Large Margin Methods for Structured and Interdependent Output Variables"
一开始constraint为空，然后逐步加入约束。
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 1000 kkt violation: 0.00306138
iter: 2000 kkt violation: 7.47682e-005
iter: 3000 kkt violation: 0.081229
iter: 4000 kkt violation: 2.31152e-005
iter: 5000 kkt violation: 0.0259311
iter: 6000 kkt violation: 0.109375
iter: 7000 kkt violation: 0.0972222
iter: 8000 kkt violation: 0.00520834
elapse: 16.125 s
1881.61
Press any key to continue . . .
稀疏度：3543/5688=62.3%
SMO:
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 1000 kkt violation: 0.0435863
iter: 2000 kkt violation: 0.00907374
iter: 3000 kkt violation: 0.00207684
iter: 4000 kkt violation: 0.000510923
iter: 5000 kkt violation: 0.000115157
iter: 6000 kkt violation: 2.56447e-005
iter: 7000 kkt violation: 5.75994e-006
iter: 8000 kkt violation: 1.32601e-006
total iter: 8191
elapse: 1.281 s
1879.83
Press any key to continue . . .
稀疏度：2148/5688=37.8%
可见cutting plane逐步引入约束使得支持向量变少，只用少量的约束进行训练，这在机构化机器学习中可以大大提高速度
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
training SVM, EG vs SMO
风暴红QxRed 发表于 2008-01-06 13:14:09
用两种方法训练SVM:
exponentiated gradient(EG)
see "Exponentiated Gradient Algorithms for Large-margin Structured Classification"
sequential minimal optimization(SMO)
see "On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines"
两者都不用kernel cache，我用的是EG 的batch learning
result of EG:
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 1 obj: 1900.52 diff: 1
iter: 2 obj: 1938.86 diff: 0.0201721
iter: 3 obj: 1917.06 diff: 0.0087053
iter: 4 obj: 1895.35 diff: 0.0027177
iter: 5 obj: 1922.48 diff: 0.0143142
iter: 6 obj: 1896.13 diff: 0.000406889
iter: 7 obj: 1894.29 diff: 0.000562769
iter: 8 obj: 1893.08 diff: 0.000637795
iter: 9 obj: 1891.95 diff: 0.000596919
iter: 10 obj: 1891.93 diff: 8.33736e-006
iter: 11 obj: 1891.86 diff: 3.68613e-005
iter: 12 obj: 1891.69 diff: 9.33662e-005
iter: 13 obj: 1891.68 diff: 4.54609e-006
iter: 14 obj: 1891.67 diff: 5.42689e-006
iter: 15 obj: 1891.64 diff: 1.65731e-005
iter: 16 obj: 1891.49 diff: 7.53615e-005
iter: 17 obj: 1890.94 diff: 0.000294901
iter: 18 obj: 1890.63 diff: 0.000161916
iter: 19 obj: 1890.61 diff: 1.14287e-005
iter: 20 obj: 1890.59 diff: 8.47771e-006
iter: 21 obj: 1890.57 diff: 1.07317e-005
iter: 22 obj: 1890.52 diff: 2.75828e-005
iter: 23 obj: 1890.4 diff: 6.12167e-005
iter: 24 obj: 1890.37 diff: 1.7569e-005
iter: 25 obj: 1890.36 diff: 5.4169e-006
iter: 26 obj: 1890.33 diff: 1.49593e-005
iter: 27 obj: 1890.21 diff: 6.4439e-005
iter: 28 obj: 1889.89 diff: 0.000171372
iter: 29 obj: 1889.83 diff: 2.78297e-005
iter: 30 obj: 1889.83 diff: 4.692e-006
iter: 31 obj: 1889.81 diff: 6.75482e-006
iter: 32 obj: 1889.76 diff: 3.00348e-005
iter: 33 obj: 1889.6 diff: 8.08114e-005
iter: 34 obj: 1889.6 diff: 3.40063e-006
iter: 35 obj: 1889.59 diff: 2.5943e-006
iter: 36 obj: 1889.59 diff: 2.54369e-006
iter: 37 obj: 1889.58 diff: 2.13015e-006
iter: 38 obj: 1889.58 diff: 2.01479e-006
iter: 39 obj: 1889.58 diff: 2.0389e-006
iter: 40 obj: 1889.57 diff: 2.47227e-006
iter: 41 obj: 1889.57 diff: 3.0054e-006
iter: 42 obj: 1889.56 diff: 3.23708e-006
iter: 43 obj: 1889.55 diff: 2.89656e-006
iter: 44 obj: 1889.55 diff: 2.68346e-006
iter: 45 obj: 1889.54 diff: 3.93563e-006
iter: 46 obj: 1889.52 diff: 8.62622e-006
iter: 47 obj: 1889.48 diff: 2.19426e-005
iter: 48 obj: 1889.35 diff: 6.996e-005
iter: 49 obj: 1889.12 diff: 0.000123365
iter: 50 obj: 1889.11 diff: 4.93146e-006
iter: 51 obj: 1889.11 diff: 1.32571e-006
iter: 52 obj: 1889.1 diff: 1.03493e-006
iter: 53 obj: 1889.09 diff: 5.62609e-006
iter: 54 obj: 1889.03 diff: 3.35345e-005
iter: 55 obj: 1888.89 diff: 7.3654e-005
iter: 56 obj: 1888.88 diff: 3.33146e-006
iter: 57 obj: 1888.88 diff: 2.26343e-006
iter: 58 obj: 1888.86 diff: 1.13558e-005
iter: 59 obj: 1888.75 diff: 5.73086e-005
iter: 60 obj: 1888.63 diff: 6.65348e-005
iter: 61 obj: 1888.56 diff: 3.42201e-005
iter: 62 obj: 1888.56 diff: 1.93583e-006
iter: 63 obj: 1888.55 diff: 2.25024e-006
iter: 64 obj: 1888.53 diff: 1.14799e-005
iter: 65 obj: 1888.42 diff: 5.98892e-005
iter: 66 obj: 1888.23 diff: 0.000100497
iter: 67 obj: 1888.22 diff: 4.95326e-006
iter: 68 obj: 1888.21 diff: 3.6531e-006
iter: 69 obj: 1888.17 diff: 2.00749e-005
iter: 70 obj: 1888.06 diff: 6.04446e-005
iter: 71 obj: 1888.06 diff: 1.32682e-006
iter: 72 obj: 1888.06 diff: 7.04471e-007
elapse: 31.875 s
Press any key to continue . . .
result of SMO:
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 100 kkt violation: 0.5
iter: 200 kkt violation: 0.1875
iter: 300 kkt violation: 0.140625
iter: 400 kkt violation: 0.131226
iter: 500 kkt violation: 0.09375
iter: 600 kkt violation: 0.086585
iter: 700 kkt violation: 0.0710734
iter: 800 kkt violation: 0.0567286
iter: 900 kkt violation: 0.0495178
iter: 1000 kkt violation: 0.0435863
iter: 1100 kkt violation: 0.0393621
iter: 1200 kkt violation: 0.0349528
iter: 1300 kkt violation: 0.029359
iter: 1400 kkt violation: 0.0257769
iter: 1500 kkt violation: 0.0204468
iter: 1600 kkt violation: 0.016479
iter: 1700 kkt violation: 0.0141611
iter: 1800 kkt violation: 0.014291
iter: 1900 kkt violation: 0.0105183
iter: 2000 kkt violation: 0.00907374
iter: 2100 kkt violation: 0.0102539
iter: 2200 kkt violation: 0.00646792
iter: 2300 kkt violation: 0.00534058
iter: 2400 kkt violation: 0.00439922
iter: 2500 kkt violation: 0.00401126
iter: 2600 kkt violation: 0.00360624
iter: 2700 kkt violation: 0.00285684
iter: 2800 kkt violation: 0.00263466
iter: 2900 kkt violation: 0.00224431
iter: 3000 kkt violation: 0.00207684
iter: 3100 kkt violation: 0.00163039
iter: 3200 kkt violation: 0.00146387
iter: 3300 kkt violation: 0.00140585
iter: 3400 kkt violation: 0.00111531
iter: 3500 kkt violation: 0.000976563
iter: 3600 kkt violation: 0.000868589
iter: 3700 kkt violation: 0.000729904
iter: 3800 kkt violation: 0.000641928
iter: 3900 kkt violation: 0.000586512
iter: 4000 kkt violation: 0.000510923
iter: 4100 kkt violation: 0.000466275
iter: 4200 kkt violation: 0.000387957
iter: 4300 kkt violation: 0.000339057
iter: 4400 kkt violation: 0.00028483
iter: 4500 kkt violation: 0.000235835
iter: 4600 kkt violation: 0.000200396
iter: 4700 kkt violation: 0.000175159
iter: 4800 kkt violation: 0.000152007
iter: 4900 kkt violation: 0.000132584
iter: 5000 kkt violation: 0.000115157
iter: 5100 kkt violation: 0.000107332
iter: 5200 kkt violation: 8.61312e-005
iter: 5300 kkt violation: 6.89474e-005
iter: 5400 kkt violation: 5.89669e-005
iter: 5500 kkt violation: 5.24652e-005
iter: 5600 kkt violation: 4.69723e-005
iter: 5700 kkt violation: 4.23036e-005
iter: 5800 kkt violation: 3.65207e-005
iter: 5900 kkt violation: 2.98291e-005
iter: 6000 kkt violation: 2.56447e-005
iter: 6100 kkt violation: 2.0747e-005
iter: 6200 kkt violation: 1.95289e-005
iter: 6300 kkt violation: 1.62609e-005
iter: 6400 kkt violation: 1.39023e-005
iter: 6500 kkt violation: 1.25233e-005
iter: 6600 kkt violation: 1.05384e-005
iter: 6700 kkt violation: 9.46028e-006
iter: 6800 kkt violation: 7.65634e-006
iter: 6900 kkt violation: 6.65475e-006
iter: 7000 kkt violation: 5.75994e-006
iter: 7100 kkt violation: 5.09167e-006
iter: 7200 kkt violation: 4.33819e-006
iter: 7300 kkt violation: 3.86928e-006
iter: 7400 kkt violation: 3.41425e-006
iter: 7500 kkt violation: 2.96802e-006
iter: 7600 kkt violation: 2.52498e-006
iter: 7700 kkt violation: 2.02438e-006
iter: 7800 kkt violation: 1.81505e-006
iter: 7900 kkt violation: 1.63168e-006
iter: 8000 kkt violation: 1.32601e-006
iter: 8100 kkt violation: 1.36257e-006
total iter: 8191
elapse: 1.531 s
obj: 1879.83
Press any key to continue . . .
可见EG远远慢于SMO，其原因在于EG每次迭代需要遍历所有kernel，而SVM只需要遍历1列kernel。正因为如此，EG才用了online learning算法，但是其存在随机因素，训练速度可能不稳定。
恩！还是SMO好！
exponentiated gradient(EG)
see "Exponentiated Gradient Algorithms for Large-margin Structured Classification"
sequential minimal optimization(SMO)
see "On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines"
两者都不用kernel cache，我用的是EG 的batch learning
result of EG:
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 1 obj: 1900.52 diff: 1
iter: 2 obj: 1938.86 diff: 0.0201721
iter: 3 obj: 1917.06 diff: 0.0087053
iter: 4 obj: 1895.35 diff: 0.0027177
iter: 5 obj: 1922.48 diff: 0.0143142
iter: 6 obj: 1896.13 diff: 0.000406889
iter: 7 obj: 1894.29 diff: 0.000562769
iter: 8 obj: 1893.08 diff: 0.000637795
iter: 9 obj: 1891.95 diff: 0.000596919
iter: 10 obj: 1891.93 diff: 8.33736e-006
iter: 11 obj: 1891.86 diff: 3.68613e-005
iter: 12 obj: 1891.69 diff: 9.33662e-005
iter: 13 obj: 1891.68 diff: 4.54609e-006
iter: 14 obj: 1891.67 diff: 5.42689e-006
iter: 15 obj: 1891.64 diff: 1.65731e-005
iter: 16 obj: 1891.49 diff: 7.53615e-005
iter: 17 obj: 1890.94 diff: 0.000294901
iter: 18 obj: 1890.63 diff: 0.000161916
iter: 19 obj: 1890.61 diff: 1.14287e-005
iter: 20 obj: 1890.59 diff: 8.47771e-006
iter: 21 obj: 1890.57 diff: 1.07317e-005
iter: 22 obj: 1890.52 diff: 2.75828e-005
iter: 23 obj: 1890.4 diff: 6.12167e-005
iter: 24 obj: 1890.37 diff: 1.7569e-005
iter: 25 obj: 1890.36 diff: 5.4169e-006
iter: 26 obj: 1890.33 diff: 1.49593e-005
iter: 27 obj: 1890.21 diff: 6.4439e-005
iter: 28 obj: 1889.89 diff: 0.000171372
iter: 29 obj: 1889.83 diff: 2.78297e-005
iter: 30 obj: 1889.83 diff: 4.692e-006
iter: 31 obj: 1889.81 diff: 6.75482e-006
iter: 32 obj: 1889.76 diff: 3.00348e-005
iter: 33 obj: 1889.6 diff: 8.08114e-005
iter: 34 obj: 1889.6 diff: 3.40063e-006
iter: 35 obj: 1889.59 diff: 2.5943e-006
iter: 36 obj: 1889.59 diff: 2.54369e-006
iter: 37 obj: 1889.58 diff: 2.13015e-006
iter: 38 obj: 1889.58 diff: 2.01479e-006
iter: 39 obj: 1889.58 diff: 2.0389e-006
iter: 40 obj: 1889.57 diff: 2.47227e-006
iter: 41 obj: 1889.57 diff: 3.0054e-006
iter: 42 obj: 1889.56 diff: 3.23708e-006
iter: 43 obj: 1889.55 diff: 2.89656e-006
iter: 44 obj: 1889.55 diff: 2.68346e-006
iter: 45 obj: 1889.54 diff: 3.93563e-006
iter: 46 obj: 1889.52 diff: 8.62622e-006
iter: 47 obj: 1889.48 diff: 2.19426e-005
iter: 48 obj: 1889.35 diff: 6.996e-005
iter: 49 obj: 1889.12 diff: 0.000123365
iter: 50 obj: 1889.11 diff: 4.93146e-006
iter: 51 obj: 1889.11 diff: 1.32571e-006
iter: 52 obj: 1889.1 diff: 1.03493e-006
iter: 53 obj: 1889.09 diff: 5.62609e-006
iter: 54 obj: 1889.03 diff: 3.35345e-005
iter: 55 obj: 1888.89 diff: 7.3654e-005
iter: 56 obj: 1888.88 diff: 3.33146e-006
iter: 57 obj: 1888.88 diff: 2.26343e-006
iter: 58 obj: 1888.86 diff: 1.13558e-005
iter: 59 obj: 1888.75 diff: 5.73086e-005
iter: 60 obj: 1888.63 diff: 6.65348e-005
iter: 61 obj: 1888.56 diff: 3.42201e-005
iter: 62 obj: 1888.56 diff: 1.93583e-006
iter: 63 obj: 1888.55 diff: 2.25024e-006
iter: 64 obj: 1888.53 diff: 1.14799e-005
iter: 65 obj: 1888.42 diff: 5.98892e-005
iter: 66 obj: 1888.23 diff: 0.000100497
iter: 67 obj: 1888.22 diff: 4.95326e-006
iter: 68 obj: 1888.21 diff: 3.6531e-006
iter: 69 obj: 1888.17 diff: 2.00749e-005
iter: 70 obj: 1888.06 diff: 6.04446e-005
iter: 71 obj: 1888.06 diff: 1.32682e-006
iter: 72 obj: 1888.06 diff: 7.04471e-007
elapse: 31.875 s
Press any key to continue . . .
result of SMO:
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 100 kkt violation: 0.5
iter: 200 kkt violation: 0.1875
iter: 300 kkt violation: 0.140625
iter: 400 kkt violation: 0.131226
iter: 500 kkt violation: 0.09375
iter: 600 kkt violation: 0.086585
iter: 700 kkt violation: 0.0710734
iter: 800 kkt violation: 0.0567286
iter: 900 kkt violation: 0.0495178
iter: 1000 kkt violation: 0.0435863
iter: 1100 kkt violation: 0.0393621
iter: 1200 kkt violation: 0.0349528
iter: 1300 kkt violation: 0.029359
iter: 1400 kkt violation: 0.0257769
iter: 1500 kkt violation: 0.0204468
iter: 1600 kkt violation: 0.016479
iter: 1700 kkt violation: 0.0141611
iter: 1800 kkt violation: 0.014291
iter: 1900 kkt violation: 0.0105183
iter: 2000 kkt violation: 0.00907374
iter: 2100 kkt violation: 0.0102539
iter: 2200 kkt violation: 0.00646792
iter: 2300 kkt violation: 0.00534058
iter: 2400 kkt violation: 0.00439922
iter: 2500 kkt violation: 0.00401126
iter: 2600 kkt violation: 0.00360624
iter: 2700 kkt violation: 0.00285684
iter: 2800 kkt violation: 0.00263466
iter: 2900 kkt violation: 0.00224431
iter: 3000 kkt violation: 0.00207684
iter: 3100 kkt violation: 0.00163039
iter: 3200 kkt violation: 0.00146387
iter: 3300 kkt violation: 0.00140585
iter: 3400 kkt violation: 0.00111531
iter: 3500 kkt violation: 0.000976563
iter: 3600 kkt violation: 0.000868589
iter: 3700 kkt violation: 0.000729904
iter: 3800 kkt violation: 0.000641928
iter: 3900 kkt violation: 0.000586512
iter: 4000 kkt violation: 0.000510923
iter: 4100 kkt violation: 0.000466275
iter: 4200 kkt violation: 0.000387957
iter: 4300 kkt violation: 0.000339057
iter: 4400 kkt violation: 0.00028483
iter: 4500 kkt violation: 0.000235835
iter: 4600 kkt violation: 0.000200396
iter: 4700 kkt violation: 0.000175159
iter: 4800 kkt violation: 0.000152007
iter: 4900 kkt violation: 0.000132584
iter: 5000 kkt violation: 0.000115157
iter: 5100 kkt violation: 0.000107332
iter: 5200 kkt violation: 8.61312e-005
iter: 5300 kkt violation: 6.89474e-005
iter: 5400 kkt violation: 5.89669e-005
iter: 5500 kkt violation: 5.24652e-005
iter: 5600 kkt violation: 4.69723e-005
iter: 5700 kkt violation: 4.23036e-005
iter: 5800 kkt violation: 3.65207e-005
iter: 5900 kkt violation: 2.98291e-005
iter: 6000 kkt violation: 2.56447e-005
iter: 6100 kkt violation: 2.0747e-005
iter: 6200 kkt violation: 1.95289e-005
iter: 6300 kkt violation: 1.62609e-005
iter: 6400 kkt violation: 1.39023e-005
iter: 6500 kkt violation: 1.25233e-005
iter: 6600 kkt violation: 1.05384e-005
iter: 6700 kkt violation: 9.46028e-006
iter: 6800 kkt violation: 7.65634e-006
iter: 6900 kkt violation: 6.65475e-006
iter: 7000 kkt violation: 5.75994e-006
iter: 7100 kkt violation: 5.09167e-006
iter: 7200 kkt violation: 4.33819e-006
iter: 7300 kkt violation: 3.86928e-006
iter: 7400 kkt violation: 3.41425e-006
iter: 7500 kkt violation: 2.96802e-006
iter: 7600 kkt violation: 2.52498e-006
iter: 7700 kkt violation: 2.02438e-006
iter: 7800 kkt violation: 1.81505e-006
iter: 7900 kkt violation: 1.63168e-006
iter: 8000 kkt violation: 1.32601e-006
iter: 8100 kkt violation: 1.36257e-006
total iter: 8191
elapse: 1.531 s
obj: 1879.83
Press any key to continue . . .
可见EG远远慢于SMO，其原因在于EG每次迭代需要遍历所有kernel，而SVM只需要遍历1列kernel。正因为如此，EG才用了online learning算法，但是其存在随机因素，训练速度可能不稳定。
恩！还是SMO好！
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
开始写多类SVM toolkit
风暴红QxRed 发表于 2008-01-06 06:31:06
pocket SVM 0.10版 ：）
输入格式和pocket CRF一样，但不支持sequece labeling.和pocket CRF一样，只支持binary feature，支持多类分类。所用算法来自
On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines
目前只写了训练部分，SMO在小数据集上收敛。程序很简陋，还没有kernel cache。
挺好玩的 ：）
o(∩_∩)o...
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 100 kkt violation: 0.5
iter: 200 kkt violation: 0.1875
iter: 300 kkt violation: 0.140625
iter: 400 kkt violation: 0.131226
iter: 500 kkt violation: 0.09375
iter: 600 kkt violation: 0.086585
iter: 700 kkt violation: 0.0710734
iter: 800 kkt violation: 0.0567286
iter: 900 kkt violation: 0.0495178
iter: 1000 kkt violation: 0.0435863
iter: 1100 kkt violation: 0.0393621
iter: 1200 kkt violation: 0.0349528
iter: 1300 kkt violation: 0.029359
iter: 1400 kkt violation: 0.0257769
iter: 1500 kkt violation: 0.0204468
iter: 1600 kkt violation: 0.016479
iter: 1700 kkt violation: 0.0141611
iter: 1800 kkt violation: 0.014291
iter: 1900 kkt violation: 0.0105183
iter: 2000 kkt violation: 0.00907374
iter: 2100 kkt violation: 0.0102539
iter: 2200 kkt violation: 0.00646792
iter: 2300 kkt violation: 0.00534058
iter: 2400 kkt violation: 0.00439922
iter: 2500 kkt violation: 0.00401126
iter: 2600 kkt violation: 0.00360624
iter: 2700 kkt violation: 0.00285684
iter: 2800 kkt violation: 0.00263466
iter: 2900 kkt violation: 0.00224431
iter: 3000 kkt violation: 0.00207684
iter: 3100 kkt violation: 0.00163039
iter: 3200 kkt violation: 0.00146387
iter: 3300 kkt violation: 0.00140585
iter: 3400 kkt violation: 0.00111531
iter: 3500 kkt violation: 0.000976563
iter: 3600 kkt violation: 0.000868589
iter: 3700 kkt violation: 0.000729904
iter: 3800 kkt violation: 0.000641928
iter: 3900 kkt violation: 0.000586512
iter: 4000 kkt violation: 0.000510923
iter: 4100 kkt violation: 0.000466275
iter: 4200 kkt violation: 0.000387957
iter: 4300 kkt violation: 0.000339057
iter: 4400 kkt violation: 0.00028483
iter: 4500 kkt violation: 0.000235835
iter: 4600 kkt violation: 0.000200396
iter: 4700 kkt violation: 0.000175159
iter: 4800 kkt violation: 0.000152007
iter: 4900 kkt violation: 0.000132584
iter: 5000 kkt violation: 0.000115157
iter: 5100 kkt violation: 0.000107332
iter: 5200 kkt violation: 8.61312e-005
iter: 5300 kkt violation: 6.89474e-005
iter: 5400 kkt violation: 5.89669e-005
iter: 5500 kkt violation: 5.24652e-005
iter: 5600 kkt violation: 4.69723e-005
iter: 5700 kkt violation: 4.23036e-005
iter: 5800 kkt violation: 3.65207e-005
iter: 5900 kkt violation: 2.98291e-005
iter: 6000 kkt violation: 2.56447e-005
iter: 6100 kkt violation: 2.0747e-005
iter: 6200 kkt violation: 1.95289e-005
iter: 6300 kkt violation: 1.62609e-005
iter: 6400 kkt violation: 1.39023e-005
iter: 6500 kkt violation: 1.25233e-005
iter: 6600 kkt violation: 1.05384e-005
iter: 6700 kkt violation: 9.46028e-006
iter: 6800 kkt violation: 7.65634e-006
iter: 6900 kkt violation: 6.65475e-006
iter: 7000 kkt violation: 5.75994e-006
iter: 7100 kkt violation: 5.09167e-006
iter: 7200 kkt violation: 4.33819e-006
iter: 7300 kkt violation: 3.86928e-006
iter: 7400 kkt violation: 3.41425e-006
iter: 7500 kkt violation: 2.96802e-006
iter: 7600 kkt violation: 2.52498e-006
iter: 7700 kkt violation: 2.02438e-006
iter: 7800 kkt violation: 1.81505e-006
iter: 7900 kkt violation: 1.63168e-006
iter: 8000 kkt violation: 1.32601e-006
iter: 8100 kkt violation: 1.36257e-006
total iter: 8191
Press any key to continue . . .
输入格式和pocket CRF一样，但不支持sequece labeling.和pocket CRF一样，只支持binary feature，支持多类分类。所用算法来自
On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines
目前只写了训练部分，SMO在小数据集上收敛。程序很简陋，还没有kernel cache。
挺好玩的 ：）
o(∩_∩)o...
pocket svm
version 0.10
copyright(c)2008 qian xian, all rights reserved
templates loaded
100.. 200.. 300.. 400.. 500.. 600.. 700.. 800.. 900.. 1000.. 1100.. 1200.. 1300.
. 1400.. 1500.. 1600.. 1700.. 1800.. lambda size: 887
beta: 1
eta: 1e-006
iter: 0 kkt violation: 1
iter: 100 kkt violation: 0.5
iter: 200 kkt violation: 0.1875
iter: 300 kkt violation: 0.140625
iter: 400 kkt violation: 0.131226
iter: 500 kkt violation: 0.09375
iter: 600 kkt violation: 0.086585
iter: 700 kkt violation: 0.0710734
iter: 800 kkt violation: 0.0567286
iter: 900 kkt violation: 0.0495178
iter: 1000 kkt violation: 0.0435863
iter: 1100 kkt violation: 0.0393621
iter: 1200 kkt violation: 0.0349528
iter: 1300 kkt violation: 0.029359
iter: 1400 kkt violation: 0.0257769
iter: 1500 kkt violation: 0.0204468
iter: 1600 kkt violation: 0.016479
iter: 1700 kkt violation: 0.0141611
iter: 1800 kkt violation: 0.014291
iter: 1900 kkt violation: 0.0105183
iter: 2000 kkt violation: 0.00907374
iter: 2100 kkt violation: 0.0102539
iter: 2200 kkt violation: 0.00646792
iter: 2300 kkt violation: 0.00534058
iter: 2400 kkt violation: 0.00439922
iter: 2500 kkt violation: 0.00401126
iter: 2600 kkt violation: 0.00360624
iter: 2700 kkt violation: 0.00285684
iter: 2800 kkt violation: 0.00263466
iter: 2900 kkt violation: 0.00224431
iter: 3000 kkt violation: 0.00207684
iter: 3100 kkt violation: 0.00163039
iter: 3200 kkt violation: 0.00146387
iter: 3300 kkt violation: 0.00140585
iter: 3400 kkt violation: 0.00111531
iter: 3500 kkt violation: 0.000976563
iter: 3600 kkt violation: 0.000868589
iter: 3700 kkt violation: 0.000729904
iter: 3800 kkt violation: 0.000641928
iter: 3900 kkt violation: 0.000586512
iter: 4000 kkt violation: 0.000510923
iter: 4100 kkt violation: 0.000466275
iter: 4200 kkt violation: 0.000387957
iter: 4300 kkt violation: 0.000339057
iter: 4400 kkt violation: 0.00028483
iter: 4500 kkt violation: 0.000235835
iter: 4600 kkt violation: 0.000200396
iter: 4700 kkt violation: 0.000175159
iter: 4800 kkt violation: 0.000152007
iter: 4900 kkt violation: 0.000132584
iter: 5000 kkt violation: 0.000115157
iter: 5100 kkt violation: 0.000107332
iter: 5200 kkt violation: 8.61312e-005
iter: 5300 kkt violation: 6.89474e-005
iter: 5400 kkt violation: 5.89669e-005
iter: 5500 kkt violation: 5.24652e-005
iter: 5600 kkt violation: 4.69723e-005
iter: 5700 kkt violation: 4.23036e-005
iter: 5800 kkt violation: 3.65207e-005
iter: 5900 kkt violation: 2.98291e-005
iter: 6000 kkt violation: 2.56447e-005
iter: 6100 kkt violation: 2.0747e-005
iter: 6200 kkt violation: 1.95289e-005
iter: 6300 kkt violation: 1.62609e-005
iter: 6400 kkt violation: 1.39023e-005
iter: 6500 kkt violation: 1.25233e-005
iter: 6600 kkt violation: 1.05384e-005
iter: 6700 kkt violation: 9.46028e-006
iter: 6800 kkt violation: 7.65634e-006
iter: 6900 kkt violation: 6.65475e-006
iter: 7000 kkt violation: 5.75994e-006
iter: 7100 kkt violation: 5.09167e-006
iter: 7200 kkt violation: 4.33819e-006
iter: 7300 kkt violation: 3.86928e-006
iter: 7400 kkt violation: 3.41425e-006
iter: 7500 kkt violation: 2.96802e-006
iter: 7600 kkt violation: 2.52498e-006
iter: 7700 kkt violation: 2.02438e-006
iter: 7800 kkt violation: 1.81505e-006
iter: 7900 kkt violation: 1.63168e-006
iter: 8000 kkt violation: 1.32601e-006
iter: 8100 kkt violation: 1.36257e-006
total iter: 8191
Press any key to continue . . .
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
