概要

ランキング学習のアルゴリズムの一つであるRanking SVMで求めたスコア計算式を、
Elasiticsearchのスクリプトソートで使用する例を説明します。
なお、Ranking SVMの学習データはjoachimらの「Optimizing Search Engines using Clickthrough Data」という論文で説明されている方法を参考にクリックスルーログから作ります。
https://www.cs.cornell.edu/people/tj/publications/joachims_02c.pdf

ランキング学習とは

ランキング学習とは、教師あり機械学習を使用して検索のソート順を最適化する技術です。
検索システムでドキュメントをソートする際には、クエリとドキュメントの関連度のみでなく、ドキュメントの重要度（ページランクやお気に入り数や表示回数など）などのパラメータを統合したスコアを利用してソートすることが多くなってきています。
ドキュメントとクエリの特徴を表現するパラメータと、ソートするときのスコアとの対応関係を表現するスコア計算モデルを構築するために、教師あり機械学習を使用します。

下記の資料などが詳しいです。
https://www.slideshare.net/sleepy_yoshi/dsirnlp1

使用したソフトウェアのバージョンなど

ソフトウェア	バージョン	備考	URL
Elasticsearch	2.1.1	--	https://www.elastic.co/jp/
SVMRank	1.0.0	RankingSVMの実装	https://www.cs.cornell.edu/people/tj/svm_light/svm_rank.html

準備

文書の準備

blogを想定したインデックスを作ります。
「タイトル」と「お気に入り数（favoriteCount）」「お気に入り数（viewCount）」のフィールドがあります。

curl -XPUT 'http://localhost:9200/blog' -d '
{
    "settings": {
        "number_of_shards": 1,
        "number_of_replicas": 0
    },
    "mappings": {
        "item": {
            "_all": {
                "enabled": false
            },
            "_source": {
                "enabled": true
            },
            "_routing": {},
            "properties": {
                "title": {
                    "type": "string",
                    "analyzer": "whitespace"
                },
                "favoriteCount": {
                    "type": "integer"
                },
                "viewCount": {
                    "type": "integer"
                }
            }
        }
    }
}'

文書を10個登録します。
https://gist.github.com/ken57/ba76ab8a07f9c32e03edf3d5044cd92b

クリックスルーログから学習データを生成する

まず、クリックスルーログを疑似的に作ります。
クエリと文書の関連度のみでソートした結果をもとに、適当に「再生数が多いドキュメントがクリックされやすい」ということを想定してクリックスルーログを作ってみます。

タームクエリで検索して、関連度でソートされた結果を得ます。

curl -XGET "http://localhost:9200/blog/_search?pretty" -d '{
  "query" : {
    "term" : {
      "title":"hoge"
     }
  }
}'

結果は下記になります。
https://gist.github.com/ken57/2d360995b177fda50662eb534c2459e3

上記のタームクエリhogeの時、ドキュメントb,e,hをクリックしたものとします。
クエリと特徴量とクリックされたかどうかを表にまとめます。

文書番号	クエリhogeとの関連度	favoriteCount	viewCount	クリック
e	0.90468985	10	1000	〇
j	0.90468985	6	1
b	0.7996404	10	100	〇
i	0.7996404	5	5
a	0.63971233	1	10
c	0.63971233	0	200
d	0.63971233	6	1
g	0.63971233	6	100
h	0.3958018	25	500	〇
f	0.3392587	0	1

ここでは、joachimらの「Optimizing Search Engines using Clickthrough Data」という論文で説明されている方法を参考にSVMRank用の学習データを作ります。
この論文では、「人間は検索結果の上位にあるものをその内容にかかわらずクリックしがちである」という性質を考慮し、このバイアスを除去するためにクリックの相対的な位置関係を使用して学習データを作成しています。
例えば、ランキング2位のものを飛ばして、3位のものをクリックした場合は、3位のものが2位のものよりも好まれていると判断します。
つまり、上記の例では、
b>j, h>i, h>a, h>c, h>d, h>g
の関係を学習データとして使用することになります。

同様にクエリがfugaの時ドキュメントc、クエリpiyoの時ドキュメントgをクリックしたものとして学習データを生成します。

クエリfugaの時のパラメータ
https://gist.github.com/ken57/07440e33a9a527aa729cad80e575fda2

文書番号	クエリfugaとの関連度	favoriteCount	viewCount	クリック
a	1.5584441	1	10
c	1.1019864	0	200	〇

得られる学習データは a>c

文書番号	クエリpiyoとの関連度	favoriteCount	viewCount	クリック
h	0.93477565	25	500
c	0.7554128	0	200
d	0.7554128	6	1
g	0.7554128	6	100	〇
f	0.5665596	0	1

得られる学習データは g>h,g>c,g>d

上記で得られた関係をSVMRankの学習データの形式にすると下記のようになります。
https://www.cs.cornell.edu/people/tj/svm_light/svm_rank.html

なお、各特徴量はフィールドの最大値で割って0.0-1.0の範囲に正規化しています。
qidはクエリのidで、同じqidのデータは同じクエリから生成された学習データであることを意味します。

training_data.txt

1 qid:1 1:0.58 2:0.06 3:0.00
2 qid:1 1:0.51 2:0.10 3:0.10
1 qid:1 1:0.51 2:0.05 3:0.01
1 qid:1 1:0.41 2:0.00 3:0.01
1 qid:1 1:0.41 2:0.00 3:0.20
1 qid:1 1:0.41 2:0.06 3:0.00
1 qid:1 1:0.41 2:0.06 3:0.10
2 qid:1 1:0.25 2:0.25 3:0.50
1 qid:2 1:1.00 2:0.01 3:0.01
2 qid:2 1:0.71 2:0.00 3:0.20
1 qid:3 1:0.60 2:0.25 3:0.5
1 qid:3 1:0.48 2:0.0  3:0.2
1 qid:3 1:0.48 2:0.06 3:0.0
2 qid:3 1:0.48 2:0.06 3:0.1

学習

このデータを使用して下記のコマンドで学習すると下記のようなモデルが生成されます。

./svm_rank/svm_rank_learn -c 1 training_data.txt svm_model.dat

svm_model.dat

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 
4 # 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:-0.60051519 2:0.90340906 3:1.3645355 #

線形モデルなので、最後の行の1:,2:,3:の値はそれぞれ特徴量の重みを表しており、Elasticsearchのスクリプトソートだとそのまま下記のように使用できます。

curl -XGET "http://localhost:9200/blog/_search?pretty" -d '{
    "query" : {

        "function_score" : {
            "query":{
                 "match": {
                      "title": "aaa"
                 }
            },
            "boost_mode": "replace",
            "script_score" : {
                "script" : "_score/1.56 * -0.60051519 + doc[\"favoriteCount\"].value/100.0 * 0.90340906 + doc[\"viewCount\"].value/1000.0 * 1.3645355"
            }
        }
    }
}'

確認

確認用データの生成

確認用のデータを作ります。

curl -XPUT "http://localhost:9200/blog/item/1" -d '{
"title": "aaa bbb ccc",
"favoriteCount": 10,
"viewCount": 20
}'

curl -XPUT "http://localhost:9200/blog/item/2" -d '{
"title": "ccc aaa",
"favoriteCount": 10,
"viewCount": 30
}'

curl -XPUT "http://localhost:9200/blog/item/3" -d '{
"title": "aaa aaa bbb bbb yyy",
"favoriteCount": 0,
"viewCount": 200
}'

クエリaaaで関連度でソートしてみる
https://gist.github.com/ken57/bceca6332ed808c2ad23efeab4d7d554
クエリaaaでスクリプトソートしてみる
https://gist.github.com/ken57/f85f3952ddf2844da11b355771273446
viewCountが優先されてソートされていることがわかります。

文書番号	クエリaaaとの関連度	favoriteCount	viewCount	スコア
2	1.3616593	10	30	-0.39288783
3	1.347974	0	200	-0.24598959
1	1.0893275	10	20	-0.30170023

検算

テスト用のデータを用意します

test_data.txt

1 qid:1 1:0.872858526 2:0.1 3:0.03
1 qid:1 1:0.864085897 2:0   3:0.2
1 qid:1 1:0.698286859 2:0.1 3:0.02

ranksvmの分類機能を使ってテストします。

./svm_rank/svm_rank_classify test_data.txt svm_model.dat result.txt

result.txtに結果が出力されます。

result.txt

-0.39288783
-0.24598962
-0.30170023

上記Elasticsearchのscriptソートのスコアと一致することがわかります。

まとめ

学習データ生成のところ、本当にこうでよいのか不安なので間違っていたらご指摘いただけるとありがたいです・・・。