ElasticsearchのスクリプトソートでRankingSVMで求めたスコア計算式をもとにソートする

# 概要

ランキング学習のアルゴリズムの一つである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`

https://gist.github.com/ken57/4d89ad5295cee95d65b03fc57032c89b

|文書番号| クエリ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ソートのスコアと一致することがわかります。

# まとめ

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