進化戦略によるランキング学習手法についての論文の読書メモ

# 概要

ES-Rank evolution strategy learning to rank approach(進化戦略によるランキング学習手法)という論文を読んだので、メモを残す。論文は[こちら](http://eprints.nottingham.ac.uk/41540/)。
2017年のACM Symposium on Applied Computingで発表された、進化戦略で情報検索のランキング関数の重み探索を行う論文である。

ランキング関数とは、検索システムにおいて検索結果のドキュメントをユーザに提示する時の、ソートスコアを計算する関数である。たとえば動画の検索におけるランキング関数だと、単語関連度と再生数、お気に入り数の重み付き和とすることなどが考えられる。
ここでの各指標の重みを決めるために、進化戦略を利用する。

# 進化戦略とは
Genetic Algorithm(遺伝的アルゴリズム、進化的計算)と似た、メタヒューリスティックスの探索手法。
メタヒューリスティックスとは、ある暫定解からより良い解を発見的に探索する手法のことである。

ES-Rankでは、(1+1)-ESという進化戦略のアルゴリズムを使用している。
https://ja.wikipedia.org/wiki/%E9%80%B2%E5%8C%96%E6%88%A6%E7%95%A5
式的に、遺伝的アルゴリズムより早く収束するが、探索対象のモデルが複雑な場合は局所解に陥りやすそうに見える。

最近だとOpenAIが、ゲームなどのタスクで強化学習より効率的に学習できたとして、進化戦略を採用したことがニュースになっていた。
https://www.technologyreview.jp/s/34621/elon-musks-openai-unveils-a-simpler-way-for-machines-to-learn/
昔からある非常に単純な手法だが、実問題に適用してみると意外にも強力だったということで、見直されてきている印象。

# 以降論文のメモ
## 概要から関連研究まで
- Learning to rankのアルゴリズムはたくさん提案されているが、とても時間がかかる上、それほど効果的でないものもある。
- 進化戦略をランキング学習に応用することについて調査する。進化戦略を用いるのは、短い計算時間で良い質の解に収束するといわれているからである。
- MSLR-WEB10KとLETOR4(MQ2007, MQ2008)のデータセットでほかの14手法と比較したら、ES-Rankが全体として良い結果になった。

## アルゴリズム
入力：クエリとドキュメントの特徴ベクトルのペアの学習セットφ(q, d)
出力：ソートスコアを計算する、線形のランキング関数F(q, d)

```
1  Initialization
2  for (Gen_i  ParentCh) do
3    Gen_i = 0:0;
4  end
5  Good=FALSE;
6  OffspringCh = ParentCh;
7  for G = 1 to MaxGenerations do
8    if (Good==TRUE) then
9      Use the same mutation process of generation (G - 1) on OffspringCh to mutate OffspringCh, that is, mutate the same R genes using the same MutationStep.
       子染色体(OffspringCh)について、(G - 1)世代と同じ突然変異プロセスを使用する。つまり、R個の遺伝子を同じ突然変異ステップで突然変異させる。
10   else
11     Choose R at random, the number of genes to mutate;
       突然変異させる遺伝子の数Rをランダムで選ぶ。
12     for j = 1 to R do
13       Choose at random, Gen_i in OffSpringCh for mutation;
14       Mutate Gene_i using MutationStep according to equation (1)
         子染色体の遺伝子iをランダムで選び、式(1)に従った突然変異ステップを使用して遺伝子を突然変異させる。
15     end
16   end
17   if (Fitness(ParentCh, φ(q, d)) <Fitness(OffspringCh, φ(q, d))) then # 子のほうが適合度が高ければ、ParentChにOffspringChをセット
18     ParentCh = OffspringCh;
19     Good=TRUE;
20   else # 高くない場合は、OffspringChにParentChをセットしてやり直す。
21     OffspringCh = ParentCh;
22     Good=FALSE;
23   end
24 end
25 return the linear ranking function
```

### 解説（論文中記述より）

- 染色体のParantCh(親染色体),OffspringCh(子染色体)はM個の遺伝子のベクトルである。それぞれの遺伝子は各ドキュメントの特徴ベクトルの重要度を表す実数である。
- ステップ1-4は親染色体の遺伝子（ベクトル）を0で初期化する。
- Goodというブーリアンの変数は、過去世代の染色体に対して突然変異の処理を適用するかどうかを決める指標として使用される。Falseで初期化される。
- step6でParentChのコピーがOffspringChに作られる。
- step7-24のMaxGenerations世代までの進化処理がスタートする。
- step8-16は、突然変異対象の遺伝子を選び突然変異処理を制御する戦略と、突然変異処理を示す。突然変異のステップは式(1)で決定される。
    - ここでのgausian(0,1)は平均0、標準偏差1とした正規乱数である。
    - Cauchy(0,1)は累積分散cauchy関数に従って生成する乱数である。https://en.wikipedia.org/wiki/Cauchy_distribution
    - 式(1)で定義される突然変異のステップは、いくつかの方法で正規乱数とcauchy関数に従って生成する乱数を組み合わせたりしながら試行する予備実験で選んだ。
- G-1世代で成功した（より良いOffspringを作った）突然変異処理は、step 9で世代Gでも再度実行される。そうでなければ、step11-15で突然変異処理はリセットされる。
- step17-23は、MAPやNDCGを使用した適合度関数に従って、ParentChとOffspringChを評価する。
つまり親染色体によるランキング関数と子染色体のランキング関数で、クエリとドキュメントのペアφ(q, d)を計算した結果のMAPとNDCGを比べる。子が親より良くなってた場合は、子の染色体をもとに次の突然変異を行う。
- step25で、ES-rankはランキング関数を返す。

## 実験の結果
- MSLR-WEB10KとLETOR4(MQ2007, MQ2008)のデータセットでランキング学習の14手法と比較した
- MAPを適合度関数としたパターンと、NDCGを適合度関数としたパターンで2通り試してみる。
- 30通りの学習データとテストデータの組み合わせのうち、10個の組み合わせでベストなパフォーマンスを示した。平均したら、ES-Rankが一番良かった。
- 学習にかかる計算時間も、線形回帰、MARTの次に短かった。

## 思ったことと感想
- 適合度関数には、平均逆順位やケンドールの順位相関係数のようなクリックスルーログから直接計算可能なものを使用してみてもよさそう。論文中にも、適合度関数に平均逆順位なども使ってやってみたいと書いてあった。

- 通常の進化戦略では、正規乱数の標準偏差を更新していくが、ES-Rankでは固定のようだ。なんかもう、適当に乱数をちょっと足したりしながら局所探索してるだけのように見えるけど、これでも既存のアルゴリズムより良かったということか。目的関数が非常に単純なのかもしれない。ランキング関数が線形関数でない場合にはどのような結果になるのだろうか。