downhill simplexでNDCG最適化
ここのところ、周囲でランキング学習への興味が高まっているような気がする。
ランキング学習の一手法として、A Stochastic Learning-To-Rank Algorithm and its Application to Contextual Advertisingでは、ランキングの評価指標の一つであるNDCGを最大化するようなパラメータを推定するアプローチを取っている。この手法では、NDCGは微分することができないのでdownhill simplexを用いて最適化を行うのだが、その際に局所解に陥りにくくするためsimulated annealingの考えを取り入れている。
このannealingの部分の具体的なアルゴリズムが良くわからなかったので、単純なdownhill simplexではどれほどの結果が出るか試してみた。
データセットとしては先の論文と同じLETOR 3.0を、パラメータの推定には以下のPerlスクリプトを用いた。
それぞれのデータセットのQueryLevelNormのデータを用いた。それぞれのFoldのtrain.txtでNDCG@10を最大化するパラメータを推定し、そのパラメータを用いてtest.txtをランキング、評価した。downhill simplexのパラメータは全て初期値を使ったので、vail.txtは用いていない。
結果評価には配布されている評価ツール（Eval-Score-3.0.pl）を用いた。ただし、そのままでは動作しなかったため、以下の変更を加えている。
$ diff Eval-Score-3.0.pl{.orig,}
193c193
< if ($lnFea =~ m/^(\d+) qid\:([^\s]+).*?\#docid = ([^\s]+)$/)
---
> if ($lnFea =~ m/^(\d+) qid\:([^\s]+).*?\#docid = ([^\s]+)/)
以下がTD2004, NP2004, HP2004, OHSUMEDでの結果である。TD2003, NP2003, HP2003は時間の関係上行っていない。他手法の結果はBaselines on LETOR3.0で見ることができる。
印象としては良くもなく悪くもないといったところ。NDCG annealingの具体的な評価値はわからないが、論文のグラフから読み取れる限りでは、やはりannealingを加えることにより、より良い結果を得られているようだ。ただしdownhill simplex単体でも、初期の頂点集合の選び方を賢くやることによってある程度良い値が得られるのではないかと考える。
TD2004
Folds NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10 Fold1 0.5333 0.4333 0.3774 0.3571 0.3443 0.3286 0.3221 0.3218 0.3045 0.2938 Fold2 0.4667 0.3667 0.3747 0.3787 0.3824 0.3819 0.3672 0.3765 0.3674 0.3558 Fold3 0.4000 0.3667 0.3107 0.2717 0.2682 0.2675 0.2725 0.2828 0.2779 0.2887 Fold4 0.2667 0.2667 0.2986 0.3335 0.3505 0.3353 0.3423 0.3402 0.3476 0.3539 Fold5 0.4667 0.3333 0.3173 0.2880 0.2963 0.2879 0.3036 0.3212 0.3319 0.3257 average 0.4267 0.3533 0.3357 0.3258 0.3283 0.3202 0.3216 0.3285 0.3259 0.3236 Folds P@1 P@2 P@3 P@4 P@5 P@6 P@7 P@8 P@9 P@10 Fold1 0.5333 0.4333 0.3556 0.3167 0.2933 0.2667 0.2571 0.2583 0.2296 0.2133 Fold2 0.4667 0.3667 0.3778 0.3833 0.3867 0.3778 0.3429 0.3500 0.3259 0.3000 Fold3 0.4000 0.3667 0.2889 0.2333 0.2267 0.2222 0.2286 0.2417 0.2296 0.2400 Fold4 0.2667 0.2667 0.3111 0.3500 0.3600 0.3222 0.3238 0.3083 0.3111 0.3067 Fold5 0.4667 0.3333 0.3111 0.2667 0.2800 0.2667 0.2952 0.3167 0.3259 0.3067 average 0.4267 0.3533 0.3289 0.3100 0.3093 0.2911 0.2895 0.2950 0.2844 0.2733 Folds MAP Fold1 0.2015 Fold2 0.2237 Fold3 0.1967 Fold4 0.2290 Fold5 0.2155 average 0.2133
NP2004
Folds NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10 Fold1 0.2667 0.6000 0.6421 0.7421 0.7421 0.7421 0.7421 0.7421 0.7421 0.7421 Fold2 0.6000 0.6333 0.6674 0.7134 0.7530 0.7659 0.7659 0.7659 0.7659 0.7659 Fold3 0.5333 0.8667 0.8667 0.9000 0.9000 0.9258 0.9258 0.9258 0.9258 0.9258 Fold4 0.6000 0.7333 0.7333 0.7667 0.7667 0.7667 0.7904 0.7904 0.7904 0.7904 Fold5 0.5333 0.6667 0.7508 0.7841 0.7841 0.7841 0.7841 0.7841 0.7841 0.7841 average 0.5067 0.7000 0.7321 0.7813 0.7892 0.7969 0.8017 0.8017 0.8017 0.8017 Folds P@1 P@2 P@3 P@4 P@5 P@6 P@7 P@8 P@9 P@10 Fold1 0.2667 0.3000 0.2222 0.2167 0.1733 0.1444 0.1238 0.1083 0.0963 0.0867 Fold2 0.6000 0.3333 0.2444 0.2167 0.2000 0.1778 0.1524 0.1333 0.1185 0.1067 Fold3 0.5333 0.4333 0.2889 0.2333 0.1867 0.1667 0.1429 0.1250 0.1111 0.1000 Fold4 0.6000 0.3667 0.2444 0.2000 0.1600 0.1333 0.1238 0.1083 0.0963 0.0867 Fold5 0.5333 0.3667 0.2889 0.2333 0.1867 0.1556 0.1333 0.1167 0.1037 0.0933 average 0.5067 0.3600 0.2578 0.2200 0.1813 0.1556 0.1352 0.1183 0.1052 0.0947 Folds MAP Fold1 0.5109 Fold2 0.6742 Fold3 0.7278 Fold4 0.6937 Fold5 0.6619 average 0.6537
HP2004
Folds NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10 Fold1 0.6000 0.7000 0.7000 0.7833 0.7833 0.8091 0.8091 0.8091 0.8091 0.8091 Fold2 0.6000 0.7333 0.7594 0.7786 0.7786 0.8044 0.8239 0.8239 0.8239 0.8239 Fold3 0.6667 0.8667 0.8667 0.8667 0.8667 0.8667 0.8667 0.8667 0.8667 0.8667 Fold4 0.6000 0.6333 0.7385 0.8052 0.8052 0.8052 0.8052 0.8052 0.8052 0.8052 Fold5 0.4000 0.6333 0.6333 0.6833 0.6833 0.7091 0.7329 0.7329 0.7329 0.7329 average 0.5733 0.7133 0.7396 0.7834 0.7834 0.7989 0.8075 0.8075 0.8075 0.8075 Folds P@1 P@2 P@3 P@4 P@5 P@6 P@7 P@8 P@9 P@10 Fold1 0.6000 0.3667 0.2444 0.2333 0.1867 0.1667 0.1429 0.1250 0.1111 0.1000 Fold2 0.6000 0.4000 0.2889 0.2500 0.2000 0.1778 0.1714 0.1500 0.1333 0.1200 Fold3 0.6667 0.4667 0.3111 0.2333 0.1867 0.1556 0.1333 0.1167 0.1037 0.0933 Fold4 0.6000 0.3333 0.2889 0.2500 0.2000 0.1667 0.1429 0.1250 0.1111 0.1000 Fold5 0.4000 0.3333 0.2222 0.2000 0.1600 0.1444 0.1333 0.1167 0.1037 0.0933 average 0.5733 0.3800 0.2711 0.2333 0.1867 0.1622 0.1448 0.1267 0.1126 0.1013 Folds MAP Fold1 0.6955 Fold2 0.7065 Fold3 0.7731 Fold4 0.7028 Fold5 0.5715 average 0.6899
OHSUMED
Folds NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10 Fold1 0.3939 0.4242 0.4163 0.4113 0.4025 0.3753 0.3842 0.3786 0.3695 0.3766 Fold2 0.5079 0.4722 0.5136 0.5196 0.4976 0.4886 0.4828 0.4719 0.4685 0.4663 Fold3 0.6349 0.5000 0.4996 0.4786 0.4745 0.4633 0.4555 0.4626 0.4585 0.4497 Fold4 0.5873 0.5476 0.4886 0.4707 0.4633 0.4673 0.4725 0.4741 0.4711 0.4760 Fold5 0.6508 0.6190 0.5886 0.5757 0.5549 0.5394 0.5328 0.5264 0.5115 0.5114 average 0.5550 0.5126 0.5013 0.4912 0.4786 0.4668 0.4656 0.4627 0.4558 0.4560 Folds P@1 P@2 P@3 P@4 P@5 P@6 P@7 P@8 P@9 P@10 Fold1 0.5455 0.5455 0.5152 0.4773 0.4455 0.3939 0.3961 0.3807 0.3586 0.3591 Fold2 0.6667 0.5952 0.6190 0.6071 0.5619 0.5317 0.5102 0.4881 0.4762 0.4667 Fold3 0.7619 0.6429 0.6508 0.6310 0.6286 0.6111 0.5986 0.5952 0.5714 0.5429 Fold4 0.7143 0.6905 0.6032 0.5952 0.5714 0.5873 0.5850 0.5833 0.5767 0.5810 Fold5 0.7143 0.7143 0.6825 0.7024 0.6667 0.6270 0.6190 0.6131 0.5873 0.5810 average 0.6805 0.6377 0.6141 0.6026 0.5748 0.5502 0.5418 0.5321 0.5140 0.5061 Folds MAP Fold1 0.3434 Fold2 0.4488 Fold3 0.4684 Fold4 0.5067 Fold5 0.4631 average 0.4461
2011-08-14追記
HP2003, NP2003, TD2003の結果を追加した。
HP2003
Folds NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10 Fold1 0.7333 0.7333 0.7438 0.7438 0.7438 0.7438 0.7438 0.7438 0.7649 0.7649 Fold2 0.8333 0.9000 0.8920 0.8920 0.8920 0.8920 0.9039 0.9039 0.9039 0.9039 Fold3 0.8333 0.8667 0.8467 0.8406 0.8650 0.8632 0.8632 0.8632 0.8632 0.8632 Fold4 0.7000 0.8000 0.8210 0.8324 0.8467 0.8467 0.8527 0.8527 0.8527 0.8527 Fold5 0.6000 0.6167 0.6533 0.6699 0.6986 0.6986 0.7031 0.7031 0.7137 0.7137 average 0.7400 0.7833 0.7914 0.7958 0.8092 0.8089 0.8133 0.8133 0.8197 0.8197 Folds P@1 P@2 P@3 P@4 P@5 P@6 P@7 P@8 P@9 P@10 Fold1 0.7333 0.4000 0.2778 0.2083 0.1667 0.1389 0.1190 0.1042 0.1000 0.0900 Fold2 0.8333 0.5167 0.3444 0.2583 0.2067 0.1722 0.1524 0.1333 0.1185 0.1067 Fold3 0.8333 0.5167 0.3444 0.2583 0.2267 0.1889 0.1619 0.1417 0.1259 0.1133 Fold4 0.7000 0.4500 0.3222 0.2500 0.2067 0.1722 0.1524 0.1333 0.1185 0.1067 Fold5 0.6000 0.3500 0.2667 0.2167 0.1867 0.1556 0.1381 0.1208 0.1111 0.1000 average 0.7400 0.4467 0.3111 0.2383 0.1987 0.1656 0.1448 0.1267 0.1148 0.1033 Folds MAP Fold1 0.7489 Fold2 0.8638 Fold3 0.8002 Fold4 0.7671 Fold5 0.6476 average 0.7655
NP2003
Folds NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10 Fold1 0.4333 0.5333 0.6385 0.6552 0.6695 0.6695 0.6933 0.6933 0.6933 0.6933 Fold2 0.5000 0.6667 0.7298 0.7464 0.7608 0.7608 0.7727 0.7727 0.7727 0.7727 Fold3 0.5667 0.6667 0.7087 0.7254 0.7326 0.7455 0.7692 0.7692 0.7692 0.7792 Fold4 0.6000 0.7667 0.8087 0.8087 0.8087 0.8087 0.8206 0.7873 0.7873 0.7873 Fold5 0.6333 0.6833 0.7569 0.7986 0.7986 0.7986 0.8105 0.8105 0.8105 0.8105 average 0.5467 0.6633 0.7285 0.7469 0.7540 0.7566 0.7732 0.7666 0.7666 0.7686 Folds P@1 P@2 P@3 P@4 P@5 P@6 P@7 P@8 P@9 P@10 Fold1 0.4333 0.2667 0.2333 0.1833 0.1533 0.1278 0.1190 0.1042 0.0926 0.0833 Fold2 0.5000 0.3333 0.2556 0.2000 0.1667 0.1389 0.1238 0.1083 0.0963 0.0867 Fold3 0.5667 0.3500 0.2556 0.2000 0.1667 0.1444 0.1333 0.1167 0.1037 0.0967 Fold4 0.6000 0.3833 0.2778 0.2083 0.1667 0.1389 0.1238 0.1042 0.0926 0.0833 Fold5 0.6333 0.3500 0.2778 0.2333 0.1867 0.1556 0.1381 0.1208 0.1074 0.0967 average 0.5467 0.3367 0.2600 0.2050 0.1680 0.1411 0.1276 0.1108 0.0985 0.0893 Folds MAP Fold1 0.5714 Fold2 0.6427 Fold3 0.6734 Fold4 0.7133 Fold5 0.7230 average 0.6648
TD2003
Folds NDCG@1 NDCG@2 NDCG@3 NDCG@4 NDCG@5 NDCG@6 NDCG@7 NDCG@8 NDCG@9 NDCG@10 Fold1 0.3000 0.2500 0.2140 0.2019 0.1821 0.1819 0.1817 0.1943 0.2069 0.2138 Fold2 0.3000 0.3500 0.3740 0.3702 0.3435 0.3340 0.3457 0.3345 0.3253 0.3322 Fold3 0.4000 0.2500 0.3055 0.3116 0.3058 0.3238 0.3313 0.3382 0.3512 0.3873 Fold4 0.2000 0.3000 0.3315 0.3536 0.3797 0.3689 0.3607 0.3726 0.3760 0.3727 Fold5 0.6000 0.4000 0.3281 0.2757 0.2462 0.2546 0.2540 0.2537 0.2534 0.2591 average 0.3600 0.3100 0.3106 0.3026 0.2915 0.2926 0.2947 0.2986 0.3026 0.3130 Folds P@1 P@2 P@3 P@4 P@5 P@6 P@7 P@8 P@9 P@10 Fold1 0.3000 0.2500 0.2000 0.1750 0.1400 0.1333 0.1286 0.1375 0.1556 0.1600 Fold2 0.3000 0.3500 0.3667 0.3500 0.3000 0.2667 0.2571 0.2250 0.2000 0.2000 Fold3 0.4000 0.2000 0.2333 0.2000 0.1600 0.1667 0.1571 0.1500 0.1556 0.1600 Fold4 0.2000 0.2500 0.2333 0.2250 0.2400 0.2000 0.1714 0.1625 0.1556 0.1400 Fold5 0.6000 0.4000 0.3000 0.2250 0.1800 0.2000 0.1857 0.1875 0.1889 0.1900 average 0.3600 0.2900 0.2667 0.2350 0.2040 0.1933 0.1800 0.1725 0.1711 0.1700 Folds MAP Fold1 0.1623 Fold2 0.2528 Fold3 0.3392 Fold4 0.2882 Fold5 0.1650 average 0.2415
