論文読みメモ： GBrank（その2）

以下の論文を読みます。

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

※ キャラクターは架空のものです。解釈誤りは筆者に帰属します。何もわかっていないのでおかしな点はご指摘ください。

前回：その1 ／次回：まだ

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

検索エンジンさんはユーザが検索したフレーズを受け取ってウェブサイトを関連の強そうなものから順に並べて提示するということをしなければなりません。そのためのモデル（ランキング関数）は、検索フレーズ-ウェブサイト対を受け取って、その対の関連度を返します。しかし、そのような関連度の教師データなどというものは存在しません（人手で優先度をラベリングした場合はありますが）。では何を目標に学習するかですが、過去のデータから、「同じ検索フレーズで表示されたウェブサイトの中でもクリックされた確率に有意差があったペア」をなるべくかき集めてくることはできるでしょう。これらのペアたちの相対的優先度にしたがうような関連度スコアを出すことを目指します。「チーズタルト」というフレーズで検索したデータから「専門店Xのサイト（クリック率相対的に大）、専門店Xのサイト（クリック率相対的に小）」というペアが抽出されたならば、モデルは「チーズタルト-専門店Xのサイト」に20.0、「チーズタルト-専門店Yのサイト」に15.0などというようなスコアを付けていれば正解です。これを実現するには、勾配ブースティング回帰木で、相対的優先度を誤ったペアについて判定を取り換えっこすることを目指す…？

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

前提の確認も兼ねて 2.1 節の一般的な回帰モデルに対する勾配降下法からみていこう。いま学習データ $\{ (x_i, g_i) \}_{i=1}^N$ があって、 $g_i \approx h(x_i)$ になるような関数 $h$ を手に入れたい。2乗誤差を採用するならば以下の最適化問題を解きたいと。 $\mathcal{H}$ は予め定めた関数クラスだね。

$\displaystyle \underset{h \in \mathcal{H}}{\rm min} \; L(h) \equiv \frac{1}{2} \sum_{i=1}^N \bigl( g_i - h(x_i) \bigr)^2$ これを勾配降下法で解くというのは、 $h$ を以下のように更新していくということだね。 $h_{k+1}(x) = h_k(x) - \alpha_k \nabla L\bigl( h_k(x) \bigr)$ ここで $\nabla L\bigl( h_k(x) \bigr)$ というのは $h$ という関数をどの方向に更新するべきかってことだけど、以下のように各学習サンプル点でのみ値が得られる。現在の出力と正解との誤差として。 $\nabla L\bigl( h_k(x) \bigr) = - \bigl(g_i - h_k(x_i) \bigr) \qquad i = 1, \cdots, N$ これらの学習サンプル点での値をもとに $\nabla L\bigl( h_k(x) \bigr)$ の近似値を得て更新するんだね。

「関数を更新」というのはニューラルネットなどであったら、各重み係数について、損失関数の重み係数に関する偏微分の値を計算して（誤差を伝播させて）、全ての重み係数を更新するべき方向を求めて、その方向に少し更新するということですよね。でも回帰木のブースティングの場合は、そもそもその誤差を目的変数にした新しい回帰木を重ねることができるのですよね。

そうだね。その勾配ブースティング回帰木の具体的な手続きは以下だ。

$h_0(x) = \sum_{i=1}^N g_i / N$ とする（全ての学習サンプル点の値の平均値で初期化する）。
$k$ ステップ目（ $k=1, \cdots, M$ ）の更新では、更新前の誤差 $r_{i, k}=g_i = h_{k-1}(x_i) \; (i = 1, \cdots, N)$ を求めて、これを目的変数に回帰木を学習し、木の終端ノードの値 $R_{j,k} \; (j = 1, \cdots, J_k)$ を得る。そして、各ノードの平均残差 $\gamma_{j,k}=\sum_{x_i \in R_{j,k}} \bigl(g_i - h_{k-1}(x_i) \bigr) / |i : x_i \in R_{j,k}|$ を算出し、各ノードに対応する長方形の領域をこの平均残差だけ更新する。 $\displaystyle h_k(x) = h_{k-1}(x) + \eta \left( \sum_{j=1}^{J_k} \gamma_{j,k} I(x \in R_{j,k}) \right)$

この $\eta$ は shrinkage factor といって過学習抑制のために $0 < \eta \leqq 1$ に設定するみたいだね。木の数 $M$ と shrinkage factor $\eta$ がハイパーパラメータで、通常は交差検証で決めるとある。

一般的な勾配ブースティング回帰木の話はわかります。別件でかじりましたから。でも、今回やりたい学習は回帰とは少し違います。与えられているのは「学習データ内の各ペアの優劣」で、その優劣を正しく表現するようなスコア付けを学ばなければなりません。そのように学ぼうとすることが、なぜ相対的優先度を誤ったペアについて「判定を交換」していくことになるのでしょうか？

まず、検索フレーズ-ウェブサイト対 $x$ と別の検索フレーズ-ウェブサイト対 $y$ について、 $x$ の方が関連が強い対であるとラベリングされていることを $x \succ y$ と表記するよ。そして、全ての「相対的優先度が与えられているペア」を以下のようにかく。

$\mathcal{S} = \{ \langle x_i, y_i\rangle \, | \, x_i \succ y_i, \, i = 1, 2, \cdots, N \}$ いまほしいモデル $h(x)$ は、なるべく多くの $i$ について $h(x_i) > h(y_i)$ となるものだ。学習の目的関数は、その目的関数を小さくする方向にモデルを更新していくことでほしいモデルに近づいていくようなものであってほしいよね。この論文で提案されている目的関数は以下だ。 $\displaystyle \mathcal{R}(h) = \frac{1}{2} \sum_{i=1}^N \left( \max \{0, \, h(y_i) - h(x_i) \} \right) ^2$
$\displaystyle \mathcal{R}(h, \tau) = \frac{1}{2} \sum_{i=1}^N \left( \max \{0, \, h(y_i) - h(x_i) + \tau \} \right) ^2 - \lambda \tau ^2$

つづきは後で