第5回ランキング学習（Ranking SVM）

この演習課題ページでは，Ranking SVMの実装であるSVM-rankの使い方を説明します．この演習ページの目的は，SVM-rankを用いてモデルの学習，テストデータに対するランク付けが可能になることです．

この演習ページでは以下のツールを使用します．

SVM-rank (by Prof. Thorsten Joachims)
- https://www.cs.cornell.edu/people/tj/svm_light/svm_rank.html

1. SVM-rankのインストール

SVM-rankのページに従って，SVM-rankをインストールします．

まずは，svm_rank.tar.gzをダウンロードします．

http://download.joachims.org/svm_rank/current/svm_rank.tar.gz

ダウンロードしたらファイルを解凍し，コンパイルしてください．以下はその一例です．

$ mkdir svm_rank # 解凍するファイルを入れるフォルダを作成
$ mv svm_rank.tar.gz svm_rank #ダウンロードしたアーカイブを今作成したフォルダに移動 
$ cd svm_rank
$ tar xzvf svm_rank.tar.gz  #ファイルを解凍
$ make

正しくコンパイルができていれば， svm_rank_learn と svm_rank_classify　という2つのファイルが生成されているはずです．

作成したsvm_rank_learn と svm_rank_classifyを適当な場所にコピーします．この演習ページでは， h29iro/bin/にコピーした前提でコードを進めます．

2.サンプルファイルの実行

h29iro/data/svmrank_sample/ にサンプルファイルを置いています．これは，SVM-rankのページで配布されている以下のファイルをコピーしたものです．

http://download.joachims.org/svm_light/examples/example3.tar.gz

このサンプルファイルには，training.dat（訓練データ）と test.dat（テストデータ）が含まれています．

2.1 訓練データ

訓練データ(../data/svmrank_sample/train.dat)の中身はこのようになっています

3 qid:1 1:1 2:1 3:0 4:0.2 5:0 # 1A
2 qid:1 1:0 2:0 3:1 4:0.1 5:1 # 1B 
1 qid:1 1:0 2:1 3:0 4:0.4 5:0 # 1C
1 qid:1 1:0 2:0 3:1 4:0.3 5:0 # 1D  
1 qid:2 1:0 2:0 3:1 4:0.2 5:0 # 2A  
2 qid:2 1:1 2:0 3:1 4:0.4 5:0 # 2B 
1 qid:2 1:0 2:0 3:1 4:0.1 5:0 # 2C 
1 qid:2 1:0 2:0 3:1 4:0.2 5:0 # 2D  
2 qid:3 1:0 2:0 3:1 4:0.1 5:1 # 3A 
3 qid:3 1:1 2:1 3:0 4:0.3 5:0 # 3B 
4 qid:3 1:1 2:0 3:0 4:0.4 5:1 # 3C 
1 qid:3 1:0 2:1 3:1 4:0.5 5:0 # 3D

詳しいフォーマットの中身は，SVM-rankのページを参照してください．各行1列目の数値が，その文書のクエリqidに対する重要性を表しており，SVM-rankはこの値を元にpairwise preference集合を生成し，学習データとします．たとえば，上記訓練データは，下記のpairwise preference集合を訓練データとして与えていることになります．

1A>1B, 1A>1C, 1A>1D, 1B>1C, 1B>1D, 2B>2A, 2B>2C, 2B>2D, 3C>3A, 3C>3B, 3C>3D, 3B>3A, 3B>3D, 3A>3D 
(SVM-rankのページより引用）

また， 3列目以降の x:y という文字列は特徴量を表しており，x次元目の値がyであることを示しています．

たとえば，1行目のデータは，クエリ$q_1$に対して， $f_1 = 1.0, f_2=1.0, f_3=0.0, f_4=0.2, f_5=0.0$という特徴ベクトルを持った文書1Aの重要性が3であることを示しています．

2.2 訓練データの学習

訓練データを学習し，モデルを生成するには， svm_rank_learn を用います．



In [1]:

    
! ../bin/svm_rank_learn -c 0.03 ../data/svmrank_sample/train.dat ../data/svmrank_sample/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=1, CEps=4.2166, QPEps=0.0000)
Iter 3: ...(NumConst=2, SV=1, CEps=0.0000, QPEps=0.0000)
Final epsilon on KKT-Conditions: 0.00000
Upper bound on duality gap: -0.00000
Dual objective value: dval=0.13325
Primal objective value: pval=0.13325
Total number of constraints in final working set: 2 (of 2)
Number of iterations: 3
Number of calls to 'find_most_violated_constraint': 9
Number of SV: 1 
Norm of weight vector: |w|=0.11619
Value of slack variable (on working set): xi=4.21663
Value of slack variable (global): xi=4.21663
Norm of longest difference vector: ||Psi(x,y)-Psi(x,ybar)||=3.87313
Runtime in cpu-seconds: 0.00
Compacting linear model...done
Writing learned model...done

正しく学習できていれば， ../data/svmrank_sample/model というファイルが生成されているはずです．



In [2]:

    
!cat  ../data/svmrank_sample/model









    



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 
2 # 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:0.099999994 2:-0.010000001 3:-0.049999997 4:-0.0010000003 5:0.029999999 #

2.3 テストデータへの適用

先ほど学習したモデルを使って，実際にテストデータに対してランキングを行うには，svm_rank_classifyを利用します．



In [3]:

    
!cat ../data/svmrank_sample/test.dat

なお，テストデータ中の1列目の値は，正解順位(正確には重要度）です．テストデータに対する精度（テストデータ中のペアの順序関係をどれだけ正しく再現できたか）を計算する際に利用されます．



In [4]:

    
! ../bin/svm_rank_classify ../data/svmrank_sample/test.dat ../data/svmrank_sample/model ../data/svmrank_sample/prediction









    



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

テストデータに対する実際のランキングはpredictionファイルを確認します．



In [5]:

    
!cat ../data/svmrank_sample/prediction









    



0.12979999
0.08969999
0.02980000
-0.05020000

実際にテストデータに対してランキングを作成する場合は，この値の降順にランク付けします．（この例だと，[$d_1, d_2, d_3, d_4$]がSVM-rankが出力したランキング）

演習課題その4（ランキング学習・検索結果多様化）

必須課題（１）Ranking SVM

サンプルファイルとは別のテストデータを用意し，サンプルファイルの訓練データで学習したモデルをそのテストデータに適用してみよ．また，訓練データを観察し，どのような特徴量をもった文書が上位にランク付けされそうか自分で推測し，テストデータに対するランキング結果がその自分の推測と近いかどうか考察せよ．

任意課題（１）実際のデータに対するRanking SVM

演習課題1で扱った文書コレクションおよびクエリに対して，適宜特徴量を自分で考え，訓練データ・学習データを用意せよ．そして，SVM-rankを適用し，テストデータに対するランキング結果を分析することでどのような特徴量が重要と判定されたか考察せよ．

任意課題（２）検索結果多様化

講義で扱ったMMR，もしくはIA-SELECTを実装せよ．そして，演習課題1で扱ったコーパス・クエリに対してアルゴリズムを適用することで，多様化しない場合のランキングと多様化したランキングがどのように異なっているか考察せよ．

課題の提出方法

いずれかの方法で，ipython notebookのページ（.ipynbファイル）とそのhtml版を提出すること．

添付ファイルで山本に送信．
- 送付先 tyamamot at dl.kuis.kyoto-u.ac.jp
各自のgithubやgithub gistにアップロードし，そのURLを山本に送信．この場合はhtml版を用意する必要はない．
上記以外で，山本が実際に.ipynbファイルを確認できる方法．

締切

2017年1月31日（水）23:59
締切に関する個別の相談は受け付けます．

第5回 ランキング学習（Ranking SVM）