Coda

概要

Yahoo! Labsで開発されたランキングのための能動学習の論文である。 提案手法は、Yahoo!検索エンジンでの採用実績がある。 手法は、Expected Loss Optimization(ELO)とよばれ、ベイズ決定則によって識別したときの損失の期待値が最大になるデータを選ぶ。 ELOに用いる損失関数にDCGを採用したExpected DCG Loss Optimization(ELO-DCG)を提案し、実験で評価した。

Query level Active Learning

集める対象がクエリか文書かによって損失関数がことなるので、集める対象によってアルゴリズムがかわる。 ベイズ決定則は、誤って識別したときの損失を最小にするよう識別する。 \(D\)を学習データ、クエリ\(q\)に対応する\(n\)件の文書の特徴ベクトルを\(\mathrm{X}_q:=(x_1,\dots x_n)\), そのラベルを\(Y:=(y_1,\dots ,y_n)\), \(\pi\)を長さ\(n\)の順列、\(l(\pi, Y)\)を損失とすると、損失の期待値は $$ \text{EL}(q):=\underset{\pi}{\operatorname{min}}\int_Y l(\pi, Y)P(Y\mid X_q , D)dY $$ であり、\(\text{EL}(q)\)が最大となる\(q\)をラベルを与えるべきクエリと判定される。 ELO-DCGの場合、DCGにもとづく損失関数は $$ l(\pi, Y) = \underset{\pi ‘}{\operatorname{max}}\text{DCG}(\pi ‘, Y) - \text{DCG}(\pi, Y) $$ となる。このとき $$ \text{EL}(q)=\int_Y \underset{\pi}{\operatorname{max}}\text{DCG}(\pi, Y)P(Y\mid X_q , D)dY - \underset{\pi}{\operatorname{max}}\int_Y\text{DCG}(\pi, Y)P(Y\mid X_q , D)dY $$ となる。\(\pi(i)\)を\(i\)番目の文書における順位、利得関数\(G\)を\(G(s)=2^s-1\), \(<\cdot>\)を平均、\(\text{BDCG}\)を利得の集合\(\{g_j\}\)でつくれる最も高いDCGの値を返す関数とすると、Query level ELO-DCGを次のアルゴリズムで実装できる。

Document level Active Learning

学習すべき文書を選ぶ場合、クエリ\(q\)に関連する\(i\)番目の文書を選んだときの損失の期待値\(\text{EL}(q,i)\)を $$ \begin{align} \text{EL}(q, i)&=\int_{Y^i}\underset{\pi}{\operatorname{min}}\int_{y_i}l(\pi, Y)P(Y\mid X_q , D)dy_idY^i\
&=\int_{Y^i}\left(\int_{y^i}\underset{\pi}{\operatorname{max}}\text{DCG}(\pi, Y)P(Y\mid X_q, D)dy_i - \underset{\pi}{\operatorname{max}}\int_{y^i}\text{DCG}(\pi, Y)P(Y\mid X_q, D)dy_i\right)dY^i \end{align} $$ とする。ただし、\(Y^i\)は\(Y\)から\(y^i\)を除いたベクトルである。 このとき、Document Level ELO-DCGを次のアルゴリズムで実装できる。

備考

Uncertaintyによる能動学習をはじめて提案した論文と能動学習のサーベイ論文が参考文献にある。

• 論文へのリンク
• 画像の引用元はすべて上の論文です。