SVM-rankを使ってRankSVMをサクッと試してみる

この記事はランク学習（Learning to Rank） Advent Calendar 2018 - Adventarの7本目の記事です。

この記事は何？

以下の記事でランク学習手法の1つであるRankSVMを紹介しました。
szdr.hatenablog.com

この記事では、SVM-rankというRankSVMライブラリを紹介します。
SVM-rank: Support Vector Machine for Ranking

インストール

SVM-rank: Support Vector Machine for Rankingに従ってコンパイルすると、svm_rank_learnとsvm_rank_classifyという実行ファイルが生成されます。

とりあえず使ってみる

SVM-rank: Support Vector Machine for RankingのGetting startedに沿って実行してみます。

まずは例題となるデータセットをダウンロード＆展開します。

$ wget http://download.joachims.org/svm_light/examples/example3.tar.gz
$ tar -zxvf example3.tar.gz

example3というディレクトリに、train.datとtest.datという訓練データ・テストデータが入っています。
train.datの中身を確認します。

# query 1
3 qid:1 1:1 2:1 3:0 4:0.2 5:0
2 qid:1 1:0 2:0 3:1 4:0.1 5:1
1 qid:1 1:0 2:1 3:0 4:0.4 5:0
1 qid:1 1:0 2:0 3:1 4:0.3 5:0
# query 2
1 qid:2 1:0 2:0 3:1 4:0.2 5:0
2 qid:2 1:1 2:0 3:1 4:0.4 5:0
1 qid:2 1:0 2:0 3:1 4:0.1 5:0
1 qid:2 1:0 2:0 3:1 4:0.2 5:0
# query 3
2 qid:3 1:0 2:0 3:1 4:0.1 5:1
3 qid:3 1:1 2:1 3:0 4:0.3 5:0
4 qid:3 1:1 2:0 3:0 4:0.4 5:1
1 qid:3 1:0 2:1 3:1 4:0.5 5:0

1行が1データ点を表しています。

1列目の値はラベルを表しています。以前の記事でも紹介しましたが、ランク学習ではデータ点毎に関連度を表すラベルが振られており、よく「Perfect(4)・Excellent(3)・Good(2)・Fair(1)・Bad(0)」といった5段階指標が使われます。今回のtrain.datは4段階評価のラベルが振られているようです。
2列目のqidから始まる値はクエリIDを表しています。こちらも以前の記事で紹介しましたが、ランク学習における学習データは「検索キーワード」と「検索キーワードに対応する検索結果リスト」のペアで表されます。クエリIDは、各「検索キーワードに対する検索結果リスト」にそれぞれIDを振ったものになります。
3列目以降は特徴量を表します。今回は5つの特徴量を用います。

さて、train.datを用いて、RankSVMによるランキングモデルを作ってみます。
例に従って、コストパラメータ $C=3$ として学習してみます。

$ ${svm_rank_learn_path} -c 3 example3/train.dat example3/model

Reading training examples...done
Training set properties: 5 features, 3 rankings, 12 examples
NOTE: Adjusted stopping criterion relative to maximum loss: eps=0.004667
Iter 1: ...*(NumConst=1, SV=1, CEps=4.6667, QPEps=0.0000)
Iter 2: ...*(NumConst=2, SV=2, CEps=0.9849, QPEps=0.0000)
Iter 3: ...*(NumConst=3, SV=2, CEps=0.8366, QPEps=0.0000)
Iter 4: ...*(NumConst=4, SV=2, CEps=0.4767, QPEps=0.1262)
Iter 5: ...*(NumConst=5, SV=3, CEps=0.0509, QPEps=0.0041)
Iter 6: ...*(NumConst=6, SV=4, CEps=0.0316, QPEps=0.0124)
Iter 7: ...*(NumConst=7, SV=4, CEps=0.0279, QPEps=0.0094)
Iter 8: ...*(NumConst=8, SV=4, CEps=0.0048, QPEps=0.0015)
Iter 9: ...(NumConst=8, SV=4, CEps=0.0015, QPEps=0.0015)
Final epsilon on KKT-Conditions: 0.00146
Upper bound on duality gap: 0.00499
Dual objective value: dval=2.23257
Primal objective value: pval=2.23756
Total number of constraints in final working set: 8 (of 8)
Number of iterations: 9
Number of calls to 'find_most_violated_constraint': 27
Number of SV: 4
Norm of weight vector: |w|=1.88386
Value of slack variable (on working set): xi=0.15290
Value of slack variable (global): xi=0.15437
Norm of longest difference vector: ||Psi(x,y)-Psi(x,ybar)||=3.87313
Runtime in cpu-seconds: 0.05
Compacting linear model...done
Writing learned model...done

学習できたようです。モデルファイルの中身を見てみます。

SVM-light Version V6.20
0 # kernel type
3 # kernel parameter -d
1 # kernel parameter -g
1 # kernel parameter -s
1 # kernel parameter -r
empty# kernel parameter -u
6 # highest feature index
8 # number of training documents
2 # number of support vectors plus 1
0 # threshold b, each following line is a SV (starting with alpha*y)
1 1:1.521512 2:-0.057497051 3:-0.52151203 4:-0.17125149 5:0.96401501 #

上の方は学習時のパラメータ*1が書かれていますが、重要なのは一番下のランキングモデルにおける重みパラメータです。

今回は5つの特徴量を用いたため、5つの特徴量それぞれに対する重みパラメータが得られています。

得られたモデルを使ってtest.datに対する予測を行ってみます。

$ ${svm_rank_classify_path} example3/test.dat example3/model example3/predictions

Reading model...done.
Reading test examples...done.
Classifying test examples...done
Runtime (without IO) in cpu-seconds: 0.00
Average loss on test set: 0.0000
Zero/one-error on test set: 0.00% (1 correct, 0 incorrect, 1 total)
NOTE: The loss reported above is the fraction of swapped pairs averaged over
      all rankings. The zero/one-error is fraction of perfectly correct
      rankings!
Total Num Swappedpairs  :      0
Avg Swappedpairs Percent:   0.00

予測時に精度（順序を間違って予測してしまったペア数）を報告してくれています。

予測結果ファイルを見てみます。

2.45127674
1.41263953
0.92976471
-0.55576233

今回test.datには4つのデータ点が存在し、上の予測結果はそれぞれランキングモデルによるスコアを表しています。
値が大きければ大きいほどスコアが高いため、検索結果上位に出現します。

せっかくモデルファイルの中身を覗いて重みパラメータの値を確認したので、上の予測結果を検算してみます。
テストデータtest.datの中身は以下のようになってます。

4 qid:4 1:1 2:0 3:0 4:0.2 5:1
3 qid:4 1:1 2:1 3:0 4:0.3 5:0
2 qid:4 1:0 2:0 3:0 4:0.2 5:1
1 qid:4 1:0 2:0 3:1 4:0.2 5:0

1つ目のデータについて、
$\begin{align} 1.521512 * 1 - 0.057497051 * 0 \\ - 0.52151203 * 0 - 0.17125149 * 0.2 + 0.96401501 * 1 \\ = 2.451276712 \end{align}$
となるので、予測結果ファイルと（ほぼ）一致していることが分かります。

まとめ

この記事ではSVM-rankを触ってみて、RankSVMによるランキングモデルを作ってみる話を紹介しました。
モデルファイルの中身も確認することで、よりランキングモデルが何をしているのか理解できるんじゃないかなと思います。

*1:カーネルの設定など。今回は線形カーネルなのでkernel type=0となっています。