Ranking Relevance In Yahoo Search(2016)
概要
Yahooの検索エンジンを解説するKDD16の論文である。 論文におけるランキングの課題は、クエリと文書の語彙がことなること、ほとんどのクエリは滅多に入力されないこと、クエリの意味の解釈が難しいことである。 これらの課題に対する手法として、ランキングのモデル、特徴のつくりかた、クエリを文書によせる翻訳モデルを解説する。
Yahooの検索エンジンを解説するKDD16の論文である。 論文におけるランキングの課題は、クエリと文書の語彙がことなること、ほとんどのクエリは滅多に入力されないこと、クエリの意味の解釈が難しいことである。 これらの課題に対する手法として、ランキングのモデル、特徴のつくりかた、クエリを文書によせる翻訳モデルを解説する。
Dual Embedding Space Model(DESM)は、word2vecによるランキング学習である。 word2vecは、単語ごとに、入力と出力それぞれに近い重みから、2つの分散表現を生成できる。 DESMは、入力側の重みでクエリを、出力側の重みで文書を、それぞれ分散表現に変換する。
実験では、BM25と比較して評価した。 DESMだけで順位づけをすると偽陽性が高くなるが、DESMとBM25の加重平均をとるとBM25よりも高いNDCG値になった。 アルゴリズムを実装し公開した。
ネットワークの複雑化、バッチ正則化、重み減衰を使わない、負の対数尤度の過学習が汎化精度を上げるが、予測確率と精度のズレを大きくすることを実験的に示した。 予測確率を補正する6つの手法を19種類のクラス分類のデータセットに適用した結果、 最も補正できたものは、温度つきソフトマックスの出力を予測確率にする場合であった。
Trinary-Projection Trees(TP trees)は、kd木のように、ユークリッド空間の分割を二分木で表現できるデータ構造である。 超平面は1または-1の重みのついた少数の座標軸で定義される。 これにより、探索時の分岐にかかる計算が、加算と減算だけからなる\(O(1)\)となる。 また、射影されたデータの分散の大きい超平面を探し、同じ分割にある点同士の距離を小さくすることで、精度を向上させている。
ある確率でデータに誤ったラベルをふるlabelerでデータにラベルをふるときに、 既にラベルのあるデータに重ねてラベルをふるべきか調査した。 12種類のラベルつきデータセットを使い、 正解ラベルを誤ったラベルに置換する割合や同一のデータのもつラベルの数を変化させ、モデルの精度の違いを観察した。 加えて、ラベルをふるべきデータを推定する手法も提案している。
ActiveCleanは、教師データの誤りを修正し、モデルの精度を改善する手法である。 優先して修正すべきデータを推定し、データが修正されたら修正されたデータでモデルを学習する。 この修正と学習を条件を満たすまでくりかえす。 反復的な学習で大域的最適解をえられるモデルであれば、最適解への収束が保証される。 データの修正件数が等しい場合に、先行研究と比べて最大2.5倍の精度改善を達成した。
Web上の表から抽出した大量の関係モデルを対象にした検索を提案・評価した。 検索の他にも、一部の属性を入力とするスキーマの補完、入力した属性ないしスキーマに類似のものを推定するアルゴリズムの議論もある。 ここのスキーマは属性のリストである。論文の著者らは研究時にGoogleに在籍しており、論文で使われたコーパスはグーグルの汎用ウェブクローラで集めた141億のHTMLの表から抽出した高精度な154百万の関係モデルである。 コーパスに使うものはHTML形式の表から抽出した関係モデルのみである。 手法の新規性は、1億以上もの大量のテーブルを対象にしていることにある。
機械学習に使う教師データに関するサーベイ論文であり、機械学習や自然言語処理などのデータの応用分野だけでなく、データの管理にまつわる分野の調査も含まれているところに特徴がある。 データの管理に着目している理由は、深層学習の発展によって必要な教師データが増えたことで、データの管理の課題が顕在化してきたからである。
表題の論文は、マルコフ確率場をなす無向グラフとグラフの構造を反映した逆共分散行列の間の対応関係を証明し、 観測した確率変数の値からグラフの構造を復元する実験を通じて、対応関係を確認した。 この手法はSnorkelというWeak supervisionの手法において、 正解データのない環境で、ノイズつきの教師データを生成する異なるソース間の相関関係を推定するために応用された。
分類すべきデータには、正例と負例どちらか一方にのみ顕著にみられる特徴がある。 特徴選択をする場合、正例だけでなく負例の選択された顕著な特徴の割合も性能に影響する。 不均衡データの文書分類で、選択する割合を調整するほうが、予測性能を向上できたことを実験的に示した。 情報利得やオッズ比など単変量統計にもとづく特徴選択の場合、統計量の値によって暗黙的に決められた割合と異なる割合の場合の方が予測性能が高かった。