Jubatus Casual Talks #1でランク学習について発表しました

Jubatus Casual Talks #1で、「Jubatusでオンラインランク学習」というタイトルの発表を行いました。会場を提供してくださったフューチャーアーキテクト株式会社さま、運営をされたJubatus開発者の皆さま、また素晴らしい発表をしてくださった発表者の皆さまに、お礼を言いたいと思います。本当にありがとうございました。

発表資料はslideshareで公開しています。

Jubatusでオンラインランク学習 from Yukihiro Tagami

今回の発表では、以前書いた「Jubatusでオンラインランク学習」で全く触れなかったオンラインランク学習のモチベーションについて話したかったのですが、はっきりしない内容になった気もしていて少し反省しています。あと、いろいろと間違っているところもありそうなので、こっそり教えていただけると嬉しいです。

ちなみに資料の作成と発表はUbuntu 12.04のLibreOffice 3.5.7.2（Impress）で行いました。地のフォントはUbuntu標準のTakaoPGothic、数式にはTimes New Romanを使用しています。Texとは比較になりませんが、LibreOfficeの数式エディタ（Math）もなかなか良いのでおすすめです。

Jubatusでオンラインランク学習

もう二か月以上前のことだが、とあるところで、Jubatusでオンライン分類ができるならペアワイズのランク学習もできそうだという話をした。いろいろあって時間がかかってしまったが、実装と簡単な評価をしたのでまとめておく。

以下の評価で用いた実装は"y-tag/jubatus"のrankingブランチにある。現時点では、このブランチは0.4.3のリリース直後をベースとしている。

今回の実装の参考文献として、2009年のNIPSで発表された以下の論文が挙げられる。

• Large Scale Learning to Rank

また、以下の資料も非常に参考になる。

• Large Scale Learning to Rankを読んだ - 射撃しつつ前転
• Confidence Weightedで ランク学習を実装してみた
• DSIRNLP#1 ランキング学習ことはじめ

データセットとして、LETORのOHSUMED, MQ2007, MQ2008を選択し、OHSUMEDはQueryLevelNormを、MQ2007とMQ2008はSupervised rankingのものを用いた。標準的な評価と同じように、既に5分割されているデータを用いて評価を行った。

評価では、今回実装したrankingと、比較のためにクライアント側でペアを作成してclassifierサーバを用いて学習するものを対象とした。classifierを用いる学習法は2種類行った。一つ目はランダムにクエリを選択し、そのクエリに紐付いたペアをすべて一度に学習するもの。二つ目はランダムにクエリを選択するのは同じだが、更にそのクエリに紐付いたペアの中から一つのみ選択することを繰り返すものである。これ以降では、一つ目をclassifierQueryと呼び、二つめの選択方法は先述した論文でStochastic Pairwise Descent（SPD）という名前がつけられていたため、classifierSPDと呼ぶ。今回実装したrankingとclassifierQueryはペアの差分をとる場所がサーバかクライアントかの違いがあるが、それ以外はほぼ同じものだと思って構わない。三つの手法すべてが、サーバ側ではJubatusのオンライン分類器を用いている。今回は分類器としてPA, CW, AROW, NHERDを選択し、AROW, NHERDのハイパーパラメータ（設定ファイルのregularization_weight）は1、CWでは1.036433を用いた。設定ファイルは以前用いたgenerate_conf.plで生成したものを用いた。事前の実験で、今回実装したrankingでは、データを1パスで学習しただけでは収束していないようだったので、クエリ数の10倍の回数、ランダムにクエリを選択して学習した。一方でclassifierQueryとclassifierSPDは、元論文と同じように10,000のペアを選択するように学習を行った（この数は全体の有効なペア数と比較して少ない）。そのため、先述したようにrankingとclassifierQueryはロジックとしてはほぼ同じものなので、学習するサンプル数の違いによる影響が分かる。その他の詳細な実験設定等は、実験スクリプトを参照していただきたい。

なお、実験中、classifierを用いてtrainをクライアント側から呼び出す際に、例外が投げられることが多々あった。とりあえず何度か試すと問題なくなるようだったので、外部のスクリプトでリトライをかけることで対処した。そのため、classifierのプログラムはどこかおかしいようであることを注記しておく。

評価スクリプトであるEval-Score-3.0.plとEval-Score-4.0.plは、「downhill simplexでNDCG最適化」と「LETOR4.0 Downloads」を元に、それぞれ該当行を以下のように修正して用いた。

193c193
<         if ($lnFea =~ m/^(\d+) qid\:([^\s]+).*?\#docid = ([^\s]+)$/)
---
>         if ($lnFea =~ m/^(\d+) qid\:([^\s]+).*?\#docid = ([^\s]+)/)

216c216
<         if ($lnFea =~ m/^(\d+) qid\:([^\s]+).*?\#docid = ([^\s]+) inc = ([^\s]+) prob = ([^\s]+)$/)
---
>         if ($lnFea =~ m/^(\d+) qid\:([^\s]+).*?\#docid = ([^\s]+) inc = ([^\s]+) prob = ([^\s]+).$/)

結果は以下。比較のためにLETORのBaselineから、OHSUMEDではRankSVMを、MQ2007とMQ2008ではRankSVM-Structを選択した（Baselines on LETOR3.0, LETOR4.0 Baselines）。

OHSUMED               NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10
rankingPA             0.3045 0.2940 0.2709 0.2680 0.2585 0.2521 0.2500 0.2451 0.2441 0.2471
rankingCW             0.5326 0.5040 0.4956 0.4811 0.4740 0.4637 0.4569 0.4540 0.4526 0.4499
rankingAROW           0.5670 0.5193 0.4975 0.4819 0.4630 0.4590 0.4524 0.4503 0.4417 0.4392
rankingNHERD          0.4727 0.4725 0.4581 0.4400 0.4227 0.4229 0.4211 0.4206 0.4180 0.4131
classifierQueryPA     0.1571 0.1470 0.1573 0.1489 0.1496 0.1542 0.1578 0.1583 0.1573 0.1608
classifierQueryCW     0.4377 0.4032 0.3980 0.4052 0.3979 0.3943 0.3900 0.3893 0.3866 0.3878
classifierQueryAROW   0.3227 0.2872 0.2954 0.2989 0.2895 0.2886 0.2849 0.2844 0.2858 0.2880
classifierQueryNHERD  0.3782 0.3607 0.3572 0.3497 0.3420 0.3320 0.3343 0.3334 0.3331 0.3291
classifierSPDPA       0.4431 0.4087 0.3886 0.3865 0.3824 0.3782 0.3737 0.3759 0.3708 0.3735
classifierSPDCW       0.5046 0.4689 0.4414 0.4454 0.4420 0.4445 0.4411 0.4365 0.4322 0.4303
classifierSPDAROW     0.5584 0.5147 0.5045 0.4860 0.4749 0.4622 0.4606 0.4572 0.4530 0.4495
classifierSPDNHERD    0.4799 0.4510 0.4200 0.4123 0.4033 0.3992 0.4019 0.4000 0.3980 0.3961
RankSVM               0.4958 0.4331 0.4207 0.424  0.4164 0.4159 0.4133 0.4072 0.4124 0.414

MQ2007                NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10
rankingPA             0.2644 0.2754 0.2814 0.2862 0.2927 0.2988 0.3067 0.3120 0.3182 0.3236
rankingCW             0.3889 0.3930 0.3959 0.4026 0.4086 0.4153 0.4192 0.4229 0.4289 0.4345
rankingAROW           0.4073 0.4053 0.4041 0.4082 0.4145 0.4206 0.4234 0.4295 0.4358 0.4424
rankingNHERD          0.3358 0.3401 0.3474 0.3549 0.3588 0.3644 0.3695 0.3747 0.3802 0.3857
classifierQueryPA     0.2694 0.2813 0.2912 0.2985 0.3041 0.3088 0.3144 0.3195 0.3248 0.3297
classifierQueryCW     0.3795 0.3849 0.3883 0.3958 0.3979 0.4032 0.4085 0.4134 0.4180 0.4230
classifierQueryAROW   0.3873 0.3857 0.3897 0.3939 0.3994 0.4059 0.4112 0.4163 0.4225 0.4287
classifierQueryNHERD  0.3280 0.3404 0.3461 0.3521 0.3564 0.3621 0.3665 0.3734 0.3808 0.3876
classifierSPDPA       0.2641 0.2776 0.2872 0.2945 0.3033 0.3103 0.3176 0.3244 0.3301 0.3360
classifierSPDCW       0.3970 0.4041 0.4060 0.4104 0.4148 0.4188 0.4232 0.4284 0.4338 0.4392
classifierSPDAROW     0.3976 0.4050 0.4070 0.4082 0.4120 0.4187 0.4230 0.4300 0.4359 0.4419
classifierSPDNHERD    0.3297 0.3372 0.3416 0.3495 0.3546 0.3603 0.3656 0.3718 0.3781 0.3853
RankSVM-Struct        0.4096 0.4074 0.4063 0.4084 0.4143 0.4195 0.4252 0.4306 0.4362 0.4439

MQ2008                NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10
rankingPA             0.2970 0.3419 0.3574 0.3700 0.3833 0.4060 0.4212 0.3646 0.1605 0.1639
rankingCW             0.3745 0.3995 0.4240 0.4510 0.4706 0.4839 0.4888 0.4560 0.2212 0.2260
rankingAROW           0.3674 0.4015 0.4222 0.4488 0.4686 0.4818 0.4882 0.4546 0.2226 0.2277
rankingNHERD          0.3478 0.3890 0.4132 0.4353 0.4570 0.4742 0.4814 0.4476 0.2119 0.2167
classifierQueryPA     0.2405 0.2605 0.2831 0.3107 0.3339 0.3529 0.3678 0.3465 0.1492 0.1540
classifierQueryCW     0.3767 0.3933 0.4210 0.4469 0.4674 0.4792 0.4877 0.4545 0.2211 0.2258
classifierQueryAROW   0.3767 0.3998 0.4266 0.4478 0.4694 0.4802 0.4872 0.4553 0.2237 0.2281
classifierQueryNHERD  0.3278 0.3759 0.4017 0.4320 0.4496 0.4636 0.4723 0.4390 0.2140 0.2178
classifierSPDPA       0.2818 0.3176 0.3453 0.3772 0.3976 0.4181 0.4294 0.4008 0.1863 0.1900
classifierSPDCW       0.3656 0.4069 0.4266 0.4499 0.4716 0.4833 0.4937 0.4586 0.2235 0.2275
classifierSPDAROW     0.3694 0.4027 0.4289 0.4526 0.4742 0.4856 0.4925 0.4584 0.2241 0.2294
classifierSPDNHERD    0.2972 0.3403 0.3705 0.3989 0.4236 0.4429 0.4517 0.4189 0.1983 0.2026
RankSVM-Struct        0.3627 0.3985 0.4286 0.4509 0.4695 0.4851 0.4905 0.4564 0.2239 0.2279

OHSUMED               P@1    P@2    P@3    P@4    P@5    P@6    P@7    P@8    P@9    P@10
rankingPA             0.4242 0.4195 0.3711 0.3702 0.3473 0.3367 0.3292 0.3188 0.3169 0.3164
rankingCW             0.6515 0.6327 0.6170 0.5950 0.5762 0.5543 0.5373 0.5268 0.5188 0.5086
rankingAROW           0.6801 0.6513 0.6167 0.5923 0.5590 0.5400 0.5264 0.5186 0.4999 0.4905
rankingNHERD          0.6043 0.5950 0.5854 0.5645 0.5273 0.5198 0.5157 0.5045 0.4928 0.4728
classifierQueryPA     0.2645 0.2597 0.2772 0.2526 0.2437 0.2424 0.2427 0.2383 0.2378 0.2423
classifierQueryCW     0.5571 0.5197 0.5196 0.5431 0.5215 0.5055 0.4952 0.4854 0.4755 0.4696
classifierQueryAROW   0.4606 0.4095 0.4335 0.4264 0.4000 0.3885 0.3735 0.3682 0.3693 0.3655
classifierQueryNHERD  0.4922 0.4872 0.4889 0.4752 0.4541 0.4352 0.4312 0.4293 0.4257 0.4164
classifierSPDPA       0.5381 0.5379 0.5065 0.5053 0.4985 0.4817 0.4698 0.4641 0.4484 0.4528
classifierSPDCW       0.6056 0.5909 0.5577 0.5670 0.5519 0.5449 0.5319 0.5221 0.5115 0.4983
classifierSPDAROW     0.6528 0.6468 0.6266 0.5976 0.5820 0.5481 0.5307 0.5248 0.5095 0.4993
classifierSPDNHERD    0.6061 0.5870 0.5304 0.5115 0.4963 0.4892 0.4925 0.4889 0.4830 0.4783
RankSVM               0.5974 0.5494 0.5427 0.5443 0.5319 0.5253 0.5097 0.4933 0.492  0.4864

MQ2007                P@1    P@2    P@3    P@4    P@5    P@6    P@7    P@8    P@9    P@10
rankingPA             0.3262 0.3212 0.3191 0.3154 0.3149 0.3123 0.3128 0.3094 0.3082 0.3053
rankingCW             0.4528 0.4386 0.4254 0.4189 0.4100 0.4027 0.3932 0.3838 0.3787 0.3739
rankingAROW           0.4735 0.4489 0.4323 0.4220 0.4152 0.4089 0.3993 0.3940 0.3895 0.3846
rankingNHERD          0.3960 0.3854 0.3789 0.3746 0.3655 0.3603 0.3560 0.3512 0.3474 0.3438
classifierQueryPA     0.3292 0.3287 0.3322 0.3317 0.3301 0.3250 0.3226 0.3193 0.3158 0.3132
classifierQueryCW     0.4433 0.4288 0.4141 0.4087 0.3974 0.3894 0.3834 0.3776 0.3707 0.3653
classifierQueryAROW   0.4480 0.4256 0.4155 0.4075 0.4017 0.3945 0.3892 0.3834 0.3784 0.3738
classifierQueryNHERD  0.3931 0.3868 0.3812 0.3750 0.3689 0.3640 0.3581 0.3555 0.3527 0.3494
classifierSPDPA       0.3216 0.3196 0.3220 0.3200 0.3222 0.3231 0.3232 0.3219 0.3204 0.3181
classifierSPDCW       0.4628 0.4475 0.4297 0.4186 0.4114 0.4017 0.3929 0.3878 0.3814 0.3754
classifierSPDAROW     0.4628 0.4475 0.4297 0.4186 0.4114 0.4017 0.3929 0.3878 0.3814 0.3754
classifierSPDNHERD    0.3919 0.3845 0.3747 0.3712 0.3641 0.3591 0.3562 0.3527 0.3489 0.3457
RankSVM-Struct        0.4746 0.4496 0.4315 0.4194 0.4135 0.4048 0.3994 0.3931 0.3868 0.3833

MQ2008                P@1    P@2    P@3    P@4    P@5    P@6    P@7    P@8    P@9    P@10
rankingPA             0.3202 0.3023 0.2926 0.2813 0.2732 0.2666 0.2577 0.2435 0.2296 0.2171
rankingCW             0.4426 0.4069 0.3839 0.3670 0.3449 0.3225 0.2981 0.2792 0.2615 0.2462
rankingAROW           0.4311 0.4120 0.3852 0.3641 0.3411 0.3201 0.2994 0.2793 0.2625 0.2476
rankingNHERD          0.4183 0.3967 0.3711 0.3501 0.3337 0.3154 0.2961 0.2776 0.2571 0.2422
classifierQueryPA     0.2983 0.2849 0.2775 0.2728 0.2632 0.2553 0.2483 0.2380 0.2225 0.2095
classifierQueryCW     0.4464 0.4030 0.3865 0.3654 0.3441 0.3199 0.3008 0.2812 0.2612 0.2465
classifierQueryAROW   0.4438 0.4100 0.3878 0.3642 0.3431 0.3191 0.2988 0.2806 0.2634 0.2480
classifierQueryNHERD  0.4043 0.3864 0.3673 0.3527 0.3339 0.3127 0.2943 0.2739 0.2568 0.2409
classifierSPDPA       0.3481 0.3386 0.3218 0.3179 0.3015 0.2893 0.2748 0.2595 0.2433 0.2284
classifierSPDCW       0.4362 0.4094 0.3818 0.3600 0.3424 0.3195 0.3001 0.2796 0.2620 0.2464
classifierSPDAROW     0.4400 0.4145 0.3869 0.3670 0.3456 0.3223 0.3007 0.2809 0.2620 0.2479
classifierSPDNHERD    0.3736 0.3616 0.3482 0.3361 0.3217 0.3078 0.2890 0.2704 0.2540 0.2393
RankSVM-Struct        0.4273 0.4069 0.3903 0.3696 0.3474 0.3265 0.3021 0.2822 0.2647 0.2491

MAP                     OHSUMED MQ2007  MQ2008
rankingPA               0.3193  0.3710  0.3812
rankingCW               0.4470  0.4569  0.4737
rankingAROW             0.4433  0.4642  0.4687
rankingNHERD            0.4270  0.4169  0.4625
classifierQueryPA       0.2827  0.3773  0.3612
classifierQueryCW       0.4159  0.4479  0.4723
classifierQueryAROW     0.3556  0.4536  0.4715
classifierQueryNHERD    0.3897  0.4187  0.4557
classifierSPDPA         0.4040  0.3781  0.4110
classifierSPDCW         0.4455  0.4611  0.4726
classifierSPDAROW       0.4443  0.4620  0.4770
classifierSPDNHERD      0.4176  0.4212  0.4332
RankSVM/RankSVM-Struct  0.4334  0.4645  0.4696

まず分類器の違いに着目すると、不思議なことに、三つの方法すべてでPAを用いた場合の結果が著しく悪かった。そのため、グラフからはその三つは省いている。評価指標やデータセットによらず、全体的にAROWを用いた場合に良い結果が得られた。AROWと比較するとCWやNHERDを用いた場合はやや劣る結果となった。

三つの手法を比較すると、rankingやclassifierSPDに比べて、classifireQueryがやや劣る結果となった。先述したように、rankingとclassifierQueryはほぼ同じロジックであり、classifierQueryは学習の回数が少ないため、その違いが結果に反映されたのだと考えられる。一方でclassifierSPDはclassifierQueryと同じ学習の回数で良い結果を得られたため、クエリを選択した後にそれに紐付いたペアを選択するSPDの手法の方が収束速度が優れていると言える。一方でrankingの手法でも学習回数を増やせばパフォーマンスが出るようである。

RankSVMやRankSVM-Structと比較すると、OHSUMEDではRankSVMを越える結果も得られ、他の二つのデータセットでもRankSVM-Structに近い結果が得られた。

詳細な結果は以下にある。

• OHSUMED.txt
• MQ2007.txt
• MQ2008.txt

今回も実験で使ったスクリプトをGistに貼り付けておいた。

• 前準備
  • make_pairwise.pl
  • generate_conf.pl
• 評価（classifier1がclassifierQueryに、classifier2がclassfierSPDに対応）
  • batch_eval_classifier1.pl
  • batch_eval_classifier2.pl
  • batch_eval_ranking.pl
  • eval_classifier1.cpp
  • eval_classifier2.cpp
  • eval_ranking.cpp
• 結果まとめ
  • aggregate_result_LETOR3.0.pl
  • aggregate_result_LETOR4.0.pl

マルチクラスSCW評価メモ

昨年のICML2012で、オンライン分類器であるSoft Confidence-Weighted Learningが提案された（"Exact Soft Confidence-Weighted Learning"）。この際に提案されたのは基本的な二値分類だったが、今までのオンライン分類器と同じように、マルチクラスへの拡張も可能である。詳しくは以下の記事を参照していただきたい。

• Exact Soft Confidence-Weighted Learning (ICML2012) 読んだ - kisa12012の日記
• オンライン線形分類器とSCW - Sideswipe

そんなマルチクラスSCWをJubatusに実装してみた。コードは"y-tag/jubatus"のscwブランチにある。このブランチは0.4.2のリリース直後をベースとしている。

ただ単純な分類器の追加だけなら話は簡単なのだが、分類器の設定を保持するclassfier_configクラスは設定値を1種類しか保持できない一方で、SCWは2種類のハイパーパラメータを必要とする。そのため、configクラスを拡張する必要があり、それはコード全体が多少なりとも複雑にする。ここで気になるのは、コードを追加することによって増加する複雑さに、SCWの分類精度は見合うのかどうかということである。そのため、簡単ではあるが、マルチクラスSCWと既存の分類器の比較実験を行うことにした。

評価は"Exact Soft Confidence-Weighted Learning"の5章の実験設定を参考に行った。まず各データセットの学習データを用いて5-foldのcross validationを行い、各学習器のハイパーパラメータを決定した。PA1, PA2, AROW, NHERDのハイパーパラメータは{2^-4, 2^-3, ..., 2^3, 2^4}の範囲で変化させ、一番高いAccuracyを示したものを選択した。CWは元々の\etaの範囲{0.5, 0.55, ..., 0.9, 0.95}に対応した、{0.0, 0.125661, 0.253347, 0.385320, 0.524401, 0.674490, 0.841621, 1.036433, 1.281552, 1.644854}の範囲でハイパーパラメータを変化させた。SCW1とSCW2のハイパーパラメータも同様に、上記の二つの範囲内で探索を行った。ハイパーパラメータの決定後、学習データの順序をランダムにシャッフルして学習を行い、学習時の学習データでの誤分類率と、学習後のテストデータでの誤分類率を計測した。順序のランダムシャッフルは20回行い、平均と標準偏差を結果として得た。

データセットはLIBSVM DATAからマルチクラスのデータとしてnews20, usps, letterを対象とし、2クラスのデータセットとしては、元論文でも用いられていたijcnn1, w7aを選択した。

以下がその結果である。

news20	mistake rate in train	mistake rate in test	hyper parameters
pecetpron	0.31393(0.00195)	0.23138(0.00577)	-
PA	0.23127(0.00271)	0.16853(0.00270)	-
PA1	0.22574(0.00214)	0.16142(0.00199)	0.5
PA2	0.22827(0.00177)	0.16489(0.00242)	0.0625(1)
CW	0.21639(0.00208)	0.14931(0.00197)	1.644854
AROW	0.22226(0.00191)	0.15759(0.00216)	4
NHERD	0.21542(0.00275)	0.14986(0.00191)	0.5
SCW1	0.22248(0.00216)	0.15662(0.00252)	0.841621, 0.5
SCW2	0.22104(0.00190)	0.15523(0.00215)	1.644854, 0.5

usps	mistake rate in train	mistake rate in test	hyper parameters
pecetpron	0.15021(0.00201)	0.13956(0.02299)	-
PA	0.11767(0.00258)	0.11796(0.01202)	-
PA1	0.11767(0.00258)	0.11796(0.01202)	0.0625
PA2	0.11811(0.00264)	0.11921(0.01631)	0.0625(1)
CW	0.09960(0.00205)	0.10750(0.01127)	0.125661
AROW	0.11154(0.00271)	0.11131(0.01160)	0.0625
NHERD	0.13674(0.00562)	0.12972(0.01099)	0.125
SCW1	0.09674(0.00181)	0.10085(0.00655)	1.281552, 0.0625
SCW2	0.10296(0.00193)	0.10523(0.00967)	0.253347, 0.125

letter	mistake rate in train	mistake rate in test	hyper parameters
pecetpron	0.48895(0.00243)	0.41516(0.02527)	-
PA	0.52939(0.00397)	0.48201(0.03677)	-
PA1	0.41159(0.00217)	0.32184(0.01077)	0.0625
PA2	0.51170(0.00362)	0.45725(0.02690)	0.0625(1)
CW	0.43403(0.00338)	0.40431(0.02596)	0.253347
AROW	0.33970(0.00228)	0.27292(0.00410)	16
NHERD	0.34401(0.00502)	0.30952(0.00437)	0.25
SCW1	0.31376(0.00320)	0.24707(0.00385)	0.841621, 1
SCW2	0.32867(0.00262)	0.26821(0.00366)	0.841621, 2

ijcnn1	mistake rate in train	mistake rate in test	hyper parameters
pecetpron	0.10590(0.00076)	0.11283(0.03072)	-
PA	0.10280(0.00101)	0.10257(0.02067)	-
PA1	0.08116(0.00061)	0.08332(0.01250)	0.25
PA2	0.09769(0.00090)	0.09832(0.01657)	0.0625(1)
CW	0.10263(0.00074)	0.10835(0.02168)	0.125661
AROW	0.07712(0.00051)	0.08104(0.00061)	8
NHERD	0.08129(0.00401)	0.08608(0.00540)	8
SCW1	0.07363(0.00044)	0.07164(0.00069)	0.674490, 0.0625
SCW2	0.07347(0.00049)	0.07615(0.00086)	0.674490, 0.0625

w7a	mistake rate in train	mistake rate in test	hyper parameters
pecetpron	0.11713(0.00073)	0.11404(0.00885)	-
PA	0.10866(0.00066)	0.10887(0.00365)	-
PA1	0.10404(0.00043)	0.10369(0.00071)	0.0625
PA2	0.10791(0.00069)	0.10786(0.00324)	0.0625(1)
CW	0.10786(0.00109)	0.11033(0.00457)	1.644854
AROW	0.10256(0.00042)	0.10226(0.00064)	0.0625
NHERD	0.12052(0.00708)	0.11465(0.00739)	0.5
SCW1	0.10252(0.00030)	0.10244(0.00017)	1.644854, 0.0625
SCW2	0.10371(0.00062)	0.10262(0.00137)	1.644854, 0.0625

結果を見ると、SCW1, SCW2の精度はなかなか良さそうである。しかしながら、今回の実験設定ではこの二つのハイパーパラメータは他の分類器と異なり2種類あり、そのため探索にも多くの時間がかかったことは注記しておく。ちなみに、PA2のハイパーパラメータは設定ファイルから読み込んでおらず、常に初期値の1のままになっていたことに実験後、気づいた（#302）。そのため、PA2の結果は参考値としてとらえていただきたい。また、CWやSCWで用いた\etaが0.5に対応するハイパーパラメータの設定も意味がなかった気がする。

そんなわけで、ハイパーパラメータのチューニングをそれなりにやった場合にはSCWは良い結果を示すことは確認できた。しかし既に書いたように、他の分類器も同じくらいのコストをかけてチューニングを行って比較しないとフェアではない。ということで、実験設定がいけてなかったので、結論は先延ばしということにしたい。

実験に用いたスクリプトはGistに貼り付けておいた。勢いで書いて、きちんと確認していないのでいろいろと間違っているかもしれない。

• 前準備
  • phi.cpp
  • generate_conf.pl
• cross validation(ハイパーパラメータ探索)
  • batch_cv.pl
  • eval_svmdata.cpp
• 評価
  • batch_evaluate.pl
  • choose_best_conf.pl
  • eval_svmdata2.cpp
• 結果まとめ
  • calc_mean_and_deviation.pl

テストが通らなかったことのメモ 続き

「64bit環境で通るテストが32bit環境で通らなかったことのメモ」の続き。なぜあのような計算結果になるかを調べてみた。もはや完全にJubatusとは関係ない。

前回も用いたコード。#1から#3の三つの計算をしている。

#include <cstdio>
#include <cmath>

double mixed_entropy(double e, double n) {
  if (n == 0.0) {
    return 0.0;
  }
  return log(n) - e / n;
}

int main(int argc, char** argv) {
  double n = 3;
  double e_d = 3 * log(3);
  double e_e = - e_d / 3 + log(3);

  double d = 0.0;

  d = e_e;
  fprintf(stdout, "d = %g\n", d); // #1

  d = (n == 0.0) ? 0.0 : (log(n) - e_d / n);
  fprintf(stdout, "d = %g\n", d); // #2

  d = mixed_entropy(e_d, n);
  fprintf(stdout, "d = %g\n", d); //#3

  return 0;
}

https://gist.github.com/y-tag/5127284

前回試したコンパイル環境と実行結果は以下。

記号	コンパイル条件	#1	#2	#3	アセンブリ言語
A	g++ 64bit	0	0	0	mixed_entropy.64.s
B	g++ 64bit -O2	0	0	0	mixed_entropy.64.O2.s
C	g++ 32bit	7.4051e-17	-1.65883e-17	-1.65883e-17	mixed_entropy.32.s
D	g++ 32bit -O2	0	0	-1.65883e-17	mixed_entropy.32.O2.s
E	g++ 32bit -ffloat-store	0	0	0	mixed_entropy.32.store.s
F	g++ 32bit -O2 -ffloat-store	0	0	0	mixed_entropy.32.O2.store.s
G	clang++ 64bit	0	0	0	mixed_entropy.clang.64.s
H	clang++ 64bit -O2	0	0	0	mixed_entropy.clang.64.O2.s
I	clang++ 32bit	0	0	0	mixed_entropy.clang.32.s
J	clang++ 32bit -O2	0	0	0	mixed_entropy.clang.32.O2.s

以下は出力されたアセンブラやウェブ上で調べたことから推測したことである。そのため間違っているかもしれない。

32bit環境で-ffloat-storeオプションを用いた場合の結果（EとF）から、x87 FPUを用いて80bit長の計算をすると（CとD）、結果が0にならないことが推測される。-ffloat-storeを用いると80bit長のFPUから64bit長のメモリに値がロードされ、64bit長の計算を行っていることになるらしい。

一方で64bit環境（AとB）の結果が0になるのは、どうやらSSE2を用いて64bit長の計算をしているからのようで、出力されたアセンブリ言語を見るとxmmレジスタを用いてdivsdなどの計算を行っていた。32bit環境でclang++(llvm)を用いた場合も同様にSSE2を用いて計算していたようだ。

32bit環境で最適化のあるなし（CとD）を比較すると、最適化を行った場合（D）に#1と#2の結果が0となっている。これはコンパイル時の最適化で64bit計算が行われ、定数になったと推測される。実際に出力されたアセンブリ言語を見てみると、FPUにfldzで定数0をロードした後、fstlでメモリにストアして__fprintf_chkで表示するだけになっていた。

	movl	stdout, %eax
	fldz
	fstl	12(%esp)
	movl	$.LC2, 8(%esp)
	fstps	32(%esp)
	movl	$1, 4(%esp)
	movl	%eax, (%esp)
	call	__fprintf_chk
	movl	stdout, %eax
	movl	$.LC2, 8(%esp)
	movl	$1, 4(%esp)
	movl	%eax, (%esp)
	flds	32(%esp)
	fstpl	12(%esp)
	call	__fprintf_chk

64bit環境で通るテストが32bit環境で通らなかったことのメモ

大した話ではないのだがメモ。

Jubatusのビルドが64bit環境（x86_64）では通るのだが、32bit環境（i686）では通らなかったので、いろいろと調べていた。二つの環境は以下のとおりで、ビルドにはg++が用いられていた（どちらもvagrantでUbuntu 12.04を用いている）。

$ uname -a
Linux vagrant-ubuntu 3.2.0-32-generic #51-Ubuntu SMP Wed Sep 26 21:33:09 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux

$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.6.3-1ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.6 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)

$ uname -a
Linux precise32 3.2.0-23-generic-pae #36-Ubuntu SMP Tue Apr 10 22:19:09 UTC 2012 i686 athlon i386 GNU/Linux

$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/i686-linux-gnu/4.6/lto-wrapper
Target: i686-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.6.3-1ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.6 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --enable-objc-gc --enable-targets=all --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=i686-linux-gnu --host=i686-linux-gnu --target=i686-linux-gnu
Thread model: posix
gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)

もともとサポートされているのは64bitのUbuntuかRHELなので、動かしたいなら自分で何とかするしかない。どうやらテストでこけているようで、テスト結果やコンパイラの警告を見ると、原因の一つはsize_tとuint64_tを同じものとみなして用いていたためだった（g++で-Wallオプションをつけても、関数の32bit長の引数に64bit長の値を渡しても警告がでないことを始めて知った）。もう一つは、どうやら計算結果の値自体が二つの環境で異なることが原因のようだった。

32bit環境でテストが失敗しているのは、以下の場所。
https://github.com/jubatus/jubatus/blob/c97cd385ab1a3a4b7625d74eaddcf684d87eee11/src/stat/mixable_stat_test.cpp#L41

[----------] 1 test from mixable_stat_test
[ RUN      ] mixable_stat_test.mixed_entropy
../src/stat/mixable_stat_test.cpp:41: Failure
Value of: p.mixed_entropy()
  Actual: -1.6588293239028218e-17
Expected: e_e
Which is: 0
[  FAILED  ] mixable_stat_test.mixed_entropy (1 ms)
[----------] 1 test from mixable_stat_test (1 ms total)

doubleの値の比較で、その誤差もDBL_EPSILON以下なのだが、問題は先に述べたように64bit環境ではテストが通ることである。なお、gtestのASSERT_DOUBLE_EQは4ULP以内であることを求められるらしい（なのでテストを通すだけなら、ASSERT_NEARを使って許容できる誤差を指定すれば良いが、なんだか気持ち悪い）。

ということで、該当場所だけ切り出して見てみることにした。用いたコードは以下。

#include <cstdio>
#include <cmath>

double mixed_entropy(double e, double n) {
  if (n == 0.0) {
    return 0.0;
  }
  return log(n) - e / n;
}

int main(int argc, char** argv) {
  double n = 3;
  double e_d = 3 * log(3);
  double e_e = - e_d / 3 + log(3);

  double d = 0.0;

  d = e_e;
  fprintf(stdout, "d = %g\n", d);

  d = (n == 0.0) ? 0.0 : (log(n) - e_d / n);
  fprintf(stdout, "d = %g\n", d);

  d = mixed_entropy(e_d, n);
  fprintf(stdout, "d = %g\n", d);

  return 0;
}

https://gist.github.com/y-tag/5127284

やっていることは非常に単純で、 log(3) - (3 * log(3)) / 3 = 0となる計算を三通り行っている。一つ目と三つ目がJubatusのテストに相当するもので、二つ目は比較のために追加しておいた。これを64bit/32bitで、最適化なし/あり（-O2）の4通りを試してみた。

64bit最適化なし

$ g++ -o mixed_entropy mixed_entropy.cc -Wall
$ file mixed_entropy
mixed_entropy: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0xbe62c1afe97c19748e2b4833c9dd364dfc374190, not stripped
$ ./mixed_entropy 
d = 0
d = 0
d = 0

64bit最適化あり（-O2）

$ g++ -o mixed_entropy mixed_entropy.cc -Wall -O2
$ file mixed_entropy
mixed_entropy: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x8366a118eeb230a9f47333860b4b8420154eb07e, not stripped
$ ./mixed_entropy 
d = 0
d = 0
d = 0

32bit最適化なし

$ g++ -o mixed_entropy mixed_entropy.cc -Wall -m32
$ file mixed_entropy
mixed_entropy: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x084dd508b45190267b1784c8f2852092a085e29e, not stripped
$ ./mixed_entropy 
d = 7.4051e-17
d = -1.65883e-17
d = -1.65883e-17

32bit最適化あり（-O2）

$ g++ -o mixed_entropy mixed_entropy.cc -Wall -m32 -O2
$ file mixed_entropy
mixed_entropy: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0xde2ff7db9369c204b6a658224a5123e9ef17e72a, not stripped
$ ./mixed_entropy 
d = 0
d = 0
d = -1.65883e-17

g++でコンパイルすると、32bitの場合は結果が0とならない場合があった。これによって先に述べた32bit環境でのテストが失敗しているようだ。

比較としてclang（llvm）で同じようにやってみた。

$ clang++ -v
Ubuntu clang version 3.0-6ubuntu3 (tags/RELEASE_30/final) (based on LLVM 3.0)
Target: x86_64-pc-linux-gnu
Thread model: posix

64bit最適化なし

$ clang++ -o mixed_entropy mixed_entropy.cc -Wall
$ file mixed_entropy
mixed_entropy: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x30bf4081a60fe446a1aef61cd32c5891076f4fa1, not stripped
$ ./mixed_entropy 
d = 0
d = 0
d = 0

64bit最適化あり（-O2）

$ clang++ -o mixed_entropy mixed_entropy.cc -Wall -O2
$ file mixed_entropy
mixed_entropy: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x06d00baf787e1dfd4eb41b50d0475773fe527ef7, not stripped
$ ./mixed_entropy 
d = 0
d = 0
d = 0

32bit最適化なし

$ clang++ -o mixed_entropy mixed_entropy.cc -Wall -m32
$ file mixed_entropy
mixed_entropy: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0xc09935d66e58df9a96e28a5db6768d0780d15ab0, not stripped
$ ./mixed_entropy
d = 0
d = 0
d = 0

32bit最適化あり（-O2）

$ clang++ -o mixed_entropy mixed_entropy.cc -Wall -m32 -O2
$ file mixed_entropy
mixed_entropy: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x326d06160c7bbc3b28c1bca9c0296afcf8a728db, not stripped
$ ./mixed_entropy 
d = 0
d = 0
d = 0

clangでコンパイルした場合は、すべての結果が正しく0となった。

これだと「やってみた」というところに留まってしまうので、出力されたアセンブラを見てみたのだが、残念ながらアセンブラを理解することができなかった。そんなわけでここまで。

2013/3/11 追記

[twitter:@tkng]さんにご指摘いただいたように、x86の浮動小数点計算の精度が80bitで行われていることに関係しているようだ。g++で-ffloat-storeオプションをつけると期待通りの結果になった。

32bit最適化なし

$ g++ -o mixed_entropy mixed_entropy.cc -Wall -m32 -ffloat-store
$ file mixed_entropy
mixed_entropy: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x79827eadda9ce03809f6cb9d5946756d93f638b2, not stripped
$ ./mixed_entropy 
d = 0
d = 0
d = 0

32bit最適化あり（-O2）

$ g++ -o mixed_entropy mixed_entropy.cc -Wall -m32 -O2 -ffloat-store
$ file mixed_entropymixed_entropy: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=0x112c34eebd1447b77ff6af302601c9ec91ee4226, not stripped
$ ./mixed_entropy
d = 0
d = 0
d = 0

Apache PigのUDFで機械学習するアレを作りました

N番煎じ感が強いが、SIGMOD 2012で発表されたTwitterの論文のアレを作ってみた。

https://github.com/y-tag/java-pig-MyUDFs

アレとはApache Pigのユーザー定義関数（UDF）を使って分類問題を扱うというもの。オリジナルの論文は以下。

Large-Scale Machine Learning at Twitter

この実装でも、元の論文と同じようにstorage functionで学習を行うようにしている。現状では、簡単なオンライン二値分類、オンラインマルチクラス分類、オンライン線形回帰、バッチ二値分類などがある。

ビルドの際に依存するライブラリはmavenを使えば自動的に取って来てくれる。

$ mvn build

あとはPig LatinからUDFを呼び出して用いる。

学習のサンプルは以下。

register target/pig_udfs-0.0.1.jar;
define Random myorg.pig.evaluation.MyRandom('$RANDOMSEED');
training = load '$TRAINFILE' using myorg.pig.storage.SVMLightLoader() as (label: int, features: map[]);
training = foreach training generate label, features, Random() as random;
training = order training by random parallel $PARTITIONS;
training = foreach training generate label, features;
store training into '$MODELDIR' using myorg.pig.storage.FeaturesPABuilder('$FEATUREBIT', '$FEATURECONVERT', 'PA2', '1.0');

ちなみに'$'から始まる大文字（$TRAINFILEや$MODELDIRなど）は、Pig Latinの変数みたいなものである。この例では、学習ファイルはSVMLightのフォーマットで記述されており、ラベルは+1か-1である。学習データを読み込んだ後、順序をシャッフルしてデータを分割し、複数（$PARTITIONS）の学習器に渡している。学習器としてはオンライン二値分類のPA2を用い、正規化パラメータCは1.0である。$FEATUREBITは素性のパラメータ空間を表現する値であり、例えばこの値に20を指定すると、2の20乗個のパラメータを扱うことができる。

予測のサンプルは以下。テストファイルを読み出して予測を行い、予測と正解がどれだけマッチしていたかを表示するものである。

register target/pig_udfs-0.0.1.jar;
define Classify myorg.pig.evaluation.ClassifyWithBinaryOnlineClassifier('$MODELDIR');
test = load '$TESTFILE' using myorg.pig.storage.SVMLightLoader() as (label: int, features: map[]);
predict = foreach test generate label, (Classify(features) > 0 ? 1 : -1) as prediction;
results = foreach predict generate (label == prediction ? 1 : 0) as matching;
cnt = group results by matching;
cnt = foreach cnt generate group, COUNT(results);
dump cnt;

以前作成したモデルパラメータを用いて学習を再開することも可能なので、以下のようにすれば、オンライン学習器で同じデータを複数パスで学習することもできる。

store training into '$MODELDIR' using myorg.pig.storage.FeaturesPABuilder('$PREVMODELDIR');

これらの例では、あらかじめSVMLightフォーマットで作成しておいた学習データやテストデータを用いているが、実際にはTSV形式などのデータを読み込んだ後で、Pig上で素性を作って学習する流れになると思う。SVMLightフォーマットのように、素性のキーが数字であれば$FEATURECONVERTに'PARSING'を用い、キーが文字列の場'HASHING'を用いる。

以下の場所にいくつかのサンプルスクリプトが置いてある。オンライン二値分類器以外にも、オンラインマルチクラス分類器、オンライン線形回帰、バッチ二値分類器のスクリプトがある。
https://github.com/y-tag/java-pig-MyUDFs/tree/master/src/main/scripts

サンプルスクリプトで用いた、SVMLightフォーマットのデータは、以下の場所から取得できる。
LIBSVM Data

オリジナルの論文に書かれていたロジスティック回帰+SGDを行う場合は、少し面倒くさい。FeaturesSVMSGDBuilderの損失関数として'LOG'を指定して学習し、予測値を'Sigmoid'というUDFで0から1の範囲の数に変換する必要がある。

今回、SVM+SGDだけでなくPerceptronやPassiveAggressiveを実装したのはSGDの学習率の設定を間違えると精度が大きく下がると思ったからである。学習率に比べれば、正規化パラメータの設定は比較的簡単で、とりあえずデフォルト値でもそれなりに動くと思う。論文と同じく、機械学習の詳細を知らなくても、Hadoop上にあるデータをとりあえず分類してみるか、くらいの気持ちでさくっと使えるとうれしいツールを考えていたので、あまり設定が面倒でないようにしたいと考えていた。とはいえ、ここらへんは思い込みによるもので、実際はそんなに難しくないのかもしれない。

いろいろと機能を追加することはできるが、オリジナルの論文に書かれているように、誰も使わないのに高機能なツールを作っても仕方ないので、これくらいにしておく。

良くある損失関数の勾配

NIPS 2012の"A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets"（pdf）を読んで思い出したのでメモ。

上記の論文では、stochastic gradient (SG) methodを高速化したstochastic average gradient (SAG) methodを提案している。大雑把な説明をすると、SAGではiterationごとに全てのサンプルに対する勾配の和を用いてパラメータ（重み）ベクトルを更新するのだが、その時にSGと同じようにランダムに選択したサンプルに対する勾配のみを計算してアップデートし、そのほかの勾配は前のiterationで計算したものを用いる（詳細は論文の式(5)のあたりを参照）。単純な実装では、各サンプルに対する勾配とそれらの和が必要になり、スパースベクトルを用いてもデータ量と同じメモリを必要とする。しかし4章の"Implementation Details"に記されているように、多くの損失関数でサンプルに対する勾配は、サンプルのベクトルのスカラ倍で表現できるため、このスカラと全ての勾配の和のみを保持すればよい（サンプルのベクトルは保持しているものと仮定）。

話が回りくどくなってしまったが、以下では良くある損失関数の勾配についてメモしておく（とても簡単な計算だが実装しようとした時によく忘れているため）。

二値分類の目的変数yは+1/-1をとるものとする。以下のx, u, vはサンプル（データ）をあらわすベクトルである。

パラメータ（重み）wがベクトルもしくは行列のとき、zをそれぞれ以下のように定義する。

wがベクトルの時（よくある線形分類の場合）
z = y w^T x
∂z/∂w = y x

wが行列の時
z = y u^T w v
∂z/∂w = y u v^T

hinge lossの場合、

L(w) = max(0, 1 - z)

z < 1の時
∂L(w)/∂w = -∂z/∂w

hinge lossの2乗の場合、

L(w) = max(0, 1 - z)^2

(1 - z)^2 = 1 - 2z + z^2

z < 1の時
∂L(w)/∂w
= -2 ∂z/∂w + 2z ∂z/∂w
= -2 (1 - z) ∂z/∂w

logistic lossの場合、

L(w) = - log (1 / (1 + exp(-z)))
     = log(1 + exp(-z))

∂L(w)/∂w
= (exp(-z) / (1 + exp(-z))) ∂(-z)/∂w
= - (1 / (1 + exp(z))) ∂z/∂w

上の3つの例では、wがベクトルの場合に∂z/∂w = y xのスカラ倍となっており、勾配はサンプルベクトルxのスカラ倍で表せるということが分かる。

ベクトルや行列の計算は以下を参照。

• http://en.wikipedia.org/wiki/Matrix_calculus
• http://orion.uwaterloo.ca/~hwolkowi/matrixcookbook.pdf