論文読みメモ: GBrank(その1)

以下の論文を読みます。

Zhaohui Zheng, Keke Chen, Gordon Sun, Hongyuan Zha. A Regression Framework for Learning Ranking Functions Using Relative Relevance Judgments. In SIGIR, pages 287-294, 2007. https://www.cc.gatech.edu/~zha/papers/fp086-zheng.pdf
※ キャラクターは架空のものです。解釈誤りは筆者に帰属します。何もわかっていないのでおかしな点はご指摘ください。

f:id:cookie-box:20190101155733p:plain:w60

「相対的な関連度判定を用いた、ランキング関数学習のための回帰のフレームワーク」ですか。ランキング関数とは何でしょうか。

f:id:cookie-box:20190101160814p:plain:w60

アブストラクト冒頭に「商用検索エンジンにとって、効果的なランキング関数は不可欠だ」とあるね。ここでいうランキング関数とは、「ユーザが検索したフレーズを受け取って、提示可能な全てのウェブサイトにその検索フレーズとの関連度(relevance)を割り当てる」ような関数みたいだね。検索フレーズ-ウェブサイト対を受け取ってその関連の強さを返す関数といった方が入出力がはっきりするかな。検索エンジンの向こう側では何らかのランキング関数がユーザの検索フレーズと全てのウェブサイトとの関連度を計算して、その関連度が大きい順にウェブサイトが検索結果画面に並べられて提示されるわけだ。例えば「チーズタルト」とGoogle検索すると、1位にクックパッドのレシピ検索結果、2位にチーズタルト専門店のサイト、3位にまた別のチーズタルト専門店のサイトが表示されるけど、これはGoogle検索が使用しているランキング関数が「『チーズタルト』とレシピサイトの関連度 > 『チーズタルト』と専門店Xサイトの関連度 > 『チーズタルト』と専門店Yサイトの関連度」と関連度を算出したんだね。

f:id:cookie-box:20190101155733p:plain:w60

なるほど…私たちが普段検索している裏ではそんなことが…想像したことがありませんでした。しかし、そのようなランキング関数をどうやって学習するんでしょう。

f:id:cookie-box:20190101160814p:plain:w60

まず全ての「検索フレーズ-ウェブサイト対」は特徴ベクトルで表現されるみたいだね(論文3.1.1節)。その特徴ベクトルは検索フレーズのみに依存する特徴ウェブサイトのみに依存する特徴検索フレーズとウェブサイトの両方に依存する特徴を含むらしい。例えば以下だと挙げられているね。あくまで例だとは思うけど、でもこんな感じの特徴をつかっているんだろうね。

  • 検索フレーズが何単語からなるか
  • 検索フレーズが人名を含むか
  • そのウェブサイトに張られているリンクがいくつ存在するか
  • そのウェブサイト内にアンカーテキストか何バイトあるか
  • そのウェブサイトが何語のサイトか
  • そのウェブサイト内に検索フレーズ内の各単語が何回登場するか
  • そのウェブサイト内のアンカーテキストに検索フレーズ内の各単語が何回登場するか
ただこれらの特徴を用意しても、何を目指すべきかがないと学習はできない。この「検索フレーズ-ウェブサイト対」とこの「検索フレーズ-ウェブサイト対」ではどちらを上に表示するべきか、とかの情報がほしいよね。これについては、「人手で付けた優先度ラベル」を用いるやり方と、「ユーザの実績クリックデータ」を用いるやり方があるみたいだね。「人手で付けた優先度ラベル」はそのままの意味で、人手で「検索フレーズ-ウェブサイト対」に 0, 1, 2, 3, 4 のグレードを付けていくものらしい。ランキング関数がやるべきことは、よりグレードの高い「検索フレーズ-ウェブサイト対」により高い関連度を出力することだね。「ユーザの実績クリックデータ」の方は、実際の検索結果のログからクリック率(クリックされた回数 ÷ その検索結果が表示された回数)に有意差があると認められる「検索フレーズ-ウェブサイト対」のペア(対のペアってややこしいね)を抽出するらしい。ランキング関数はそれらのペアに対してクリック率が高い方により高い関連度を出力することを目指して学習する。

f:id:cookie-box:20190101155733p:plain:w60

人手でラベリングとは…人海戦術なんでしょうか。「そのウェブサイト内に検索フレーズ内の各単語が何回登場するか」などはわかりやすい特徴ですね。「チーズタルト」と検索した人が求める情報があるサイトには、「チーズタルト」と書いてあるでしょうし。サイト内のアンカーテキストというのも特徴として重視されているんですね。アンカーテキストがたくさんあるサイトは「これについて知りたい人はこちら」と道案内してくれる、優良なサイトということなんでしょうか。…なんと、数々のSEO対策記事にアンカーテキストの重要性が説かれていますね。このブログのアクセス数が伸びないのは、アンカーテキストが足りないということだったんですね…アンカーテキストを増やして検索順位を上昇させなければ…。

f:id:cookie-box:20190101160814p:plain:w60

やめて! このブログのアクセス数が伸びないのは単純に意味わかんないからだよ!

f:id:cookie-box:20190101155733p:plain:w60

この論文でやりたいことはわかってきた気がします。でも、例えばその人手でラベリングした 0, 1, 2, 3, 4 のグレードに合致したランキングになるように関連度を出力したいというのは、単純にその 0, 1, 2, 3, 4 を目的変数にして特徴ベクトルで回帰すれば済む話ではないでしょうか。特別に「ランキングの学習」なるものが必要なんでしょうか。

f:id:cookie-box:20190101160814p:plain:w60

それはどうかな。私も詳しくないしまだこの論文の中身を読んでないからわかんないけど、「0, 1, 2, 3, 4 を目的変数にして誤差2乗和が最小になる関連度を出力する」と、「0, 1, 2, 3, 4 のグレードと大小関係が合致するような関連度を出力する(グレード0からグレード4が等間隔に並ぶような関連度がほしいわけではない)」というのは少し違う話な気がするよ。それに、「チーズタルト」という検索フレーズの場合の「0, 1, 2, 3, 4」と「パンケーキ」という検索フレーズの場合の「0, 1, 2, 3, 4」は同じ座標系でなくてもいいし。ディープラーニングで座標変換ごと学習するなら一緒かもしれないけどね。

f:id:cookie-box:20190101155733p:plain:w60

確かに。…となると、評価指標がわからなくなってきました。どのようなランキング関数であればよいランキング関数といえるのでしょうか。出力する関連度とグレードとの誤差2乗和が小さい、というわけにはいきませんよね?

f:id:cookie-box:20190101160814p:plain:w60

論文の3.2節が「評価指標」だね。この論文では以下の3つの指標を用いるとあるよ。

  • Number of contradicting pairs: 優先順位付けを誤ってしまった(関連度の大小を正しい優先順位と逆にしてしまった)「検索フレーズ-ウェブサイト対」ペア数だね。
  • Precision at K%: まず全ての「検索フレーズ-ウェブサイト対」ペアに対してランキング関数が出力する関連度の差の絶対値を計算する。この絶対値が大きい方からK%のペアたちを取ってきて、優先順位付けの正解率をみる。それが Precision at K% みたいだね。これは、「ランキング関数が特に自信をもって関連度が違うと判定しているペアたち」に絞って判定の正確さをみるといった感じの指標だね(自信をもって、というのは誤解を招くかもしれない表現だけど)。
  • Discounted Cumulative Gain (DCG): これは真の適合度(人手でラベリングしたグレードと似ているけど、0, 1, 2, 3, 4 じゃなくて 0, 0, 3, 7, 10 みたいにもっとコントラストを付けたものかな。人間の実感に合った重みにしたものだと思う。グレードと対応しているとも限らないかもしれない)を何か決めて、各検索フレーズに対する検索結果内で真の適合度が大きいウェブサイトをより上に並べたかどうかをみる指標だ。具体的には、検索結果のウェブサイトの真の適合度を足していくんだけど、1位は一番大きい重みで、2位はもう少し小さい重みで、3位はさらに少し小さい重みで…というように、重みを変化させながら足す(具体的には、i 位のウェブサイトの真の適合度は  1/ \log_2 (i+1) の重みで足す)。これが DCG だ。ばっちり真の適合度の降順に並べていれば最大の DCG が達成される。「よいウェブサイトをより上の方に並べたか」ともいうべき指標だね。
この内最後の DCG は「絶対的優先度」が所与な場合にしか計測できない。つまり、人手で決めたグレードとか真の適合度とかがある場合はそれを利用して DCG が計算できるけど、ユーザの実績クリックデータから抽出したクリック率に有意差がある検索フレーズ-ウェブサイト対のペアしかないような場合は、ぺア間の「相対的優先度」があるだけで、「絶対的優先度」はわからないから、DCG は計算できないんだよね。

f:id:cookie-box:20190101155733p:plain:w60

3つも指標があるんですか? ランキングのよさの指標とは一本化できないものなんですね…。DCG が最も総合的な指標である感じもしますが、常には計測できないと。であればペア間の相対的優先度をどれだけ正しく当てたかくらいしか計測できませんが、しかし誤ったとしてもランキング関数が予測した関連度は僅差だったかもしれません。それも考慮するならば、Precision at K% がほしくなりますね。…うーん、やはり複数の指標があった方がよさそうです。でも何となくわかってきましたよ。おそらくランキング関数はこの「ペア間の相対的優先度をどれだけ正しく当てたか」を目的関数に学習するのでしょう? 論文タイトルにも「相対的な」とありましたし。ですから、相対的優先度が判明している全てのペアに対してペアの1つ目が優先されるなら +1、ペアの2つ目が優先されるなら -1 となるように2値分類すれば…あ、いえ、ほしいのはペアを入力して優先度を判定するモデルではありません。ペアの片割れだけを入力して、それに対して関連度スコアを出力してくれるモデルでなければ…いったいどうすれば…。

f:id:cookie-box:20190101160814p:plain:w60

少しテクニカルだからね。この論文では関連度を学習するのに勾配ブースティング木をつかう。1時点前の強学習器が相対優先度の判定を誤ったペアに対して、1時点前の関連度の判定を取り換えっこして、取り換えっこした判定を目的変数に弱学習器を学習する。

f:id:cookie-box:20190101155733p:plain:w60

なるほど。そういわれれば確かに強学習器の誤りは是正されていきそうですが…しかし、そのような学習をすることは結局何を目指しているのでしょうか。

(次回があれば)つづく