ランキングを学ぶ

ランキングは、文書検索、協調フィルタリング、感情分析、オンライン広告など、多くの情報検索問題の中心的な要素です。

機械学習型検索エンジンの考えられるアーキテクチャを添付の図に示す。

トレーニング データは、クエリとそれに一致するドキュメント、および各一致の関連性度で構成されます。これは、人間の評価者( Google では評価者と呼んでいます) が手動で準備し、一部のクエリの結果をチェックして、各結果の関連性を判断します。すべてのドキュメントの関連性をチェックすることは現実的ではないため、通常はプーリングと呼ばれる手法が使用されます。これは、既存のランキング モデルによって取得された上位のドキュメントのみをチェックするものです。この手法は選択バイアスを引き起こす可能性があります。あるいは、クリック スルー ログ(つまり、ユーザーからクリックされた検索結果)、^{[ 3 ]}クエリ チェーン、^{[ 4 ]}または Google (現在は置き換えられている) SearchWiki などの検索エンジンの機能の分析によって、トレーニング データを自動的に取得することもできます。クリック スルー ログは、ユーザーが上位の検索結果がすでに上位にランクされていると想定してクリックする傾向があるため、バイアスがかかる可能性があります。

学習アルゴリズムは、トレーニングデータを使用してランキングモデルを作成し、実際のクエリに対する文書の関連性を計算します。

通常、ユーザーは検索クエリが短時間（Web検索の場合は数百ミリ秒など）で完了することを期待しているため、コーパス内の各ドキュメントに対して複雑なランキングモデルを評価することは不可能であり、そのため2段階のスキームが使用されます。^{[ 5 ]}まず、ベクトル空間モデル、ブールモデル、重み付きAND ^{[ 6 ]} 、またはBM25などの、クエリ評価を高速化できるより単純な検索モデルを使用して、潜在的に関連のある少数のドキュメントが特定されます。この段階はトップ-${\displaystyle k}$文書検索を高速化するために、文献では文書の静的品質スコアや階層型インデックスの使用など、多くのヒューリスティックが提案されている。^{[ 7 ]}第2段階では、より正確だが計算コストの高い機械学習モデルを使用して、これらの文書を再ランク付けする。

学習型ランキングアルゴリズムは、情報検索以外の分野にも応用されている。

• 機械翻訳では、仮説的な翻訳のセットをランク付けします。^{[ 8 ]}
• 計算生物学では、タンパク質構造予測問題における候補3D構造のランキングに使用されます。^{[ 8 ]}
• 推薦システムでは、ユーザーが最新のニュース記事を読んだ後に、関連するニュース記事のランキングリストを特定してユーザーに推薦します。^{[ 9 ]}

この場合、トレーニングデータ内の各クエリとドキュメントのペアには、数値または順序スコアがあると仮定します。すると、ランキング学習問題は回帰問題、つまり単一のクエリとドキュメントのペアが与えられたときにそのスコアを予測するという問題に近似できます。形式的には、ポイントワイズアプローチは関数を学習することを目的としています。${\displaystyle f(x)}$文書の実数値または順序スコアを予測する${\displaystyle x}$損失関数を使用する${\displaystyle L(f;x_{j},y_{j})}$。

この目的には、既存の教師あり機械学習アルゴリズムを多数利用できます。順序回帰アルゴリズムや分類アルゴリズムも、単一のクエリと文書のペアのスコアを予測する場合、少数の有限個の値を用いるポイントワイズアプローチで使用できます。

この場合、ランキング学習問題は分類問題、つまり二値分類器の学習によって近似される。${\displaystyle h(x_{u},x_{v})}$与えられた文書ペアのうち、どちらの文書が優れているかを判断できる分類器。分類器は2つの文書を入力として受け取り、損失関数を最小化することを目標とする。${\displaystyle L(h;x_{u},x_{v},y_{u,v})}$損失関数は通常、誘導されたランキングにおける逆転の数と大きさを反映します。

多くの場合、バイナリ分類器${\displaystyle h(x_{u},x_{v})}$スコアリング関数で実装されています${\displaystyle f(x)}$例えば、RankNet ^{[ 15 ]}は確率モデルを採用し、${\displaystyle h(x_{u},x_{v})}$文書の推定確率として${\displaystyle x_{u}}$より高品質${\displaystyle x_{v}}$:

${\displaystyle P_{u,v}(f)={\text{CDF}}(f(x_{u})-f(x_{v})),}$

どこ${\displaystyle {\text{CDF}}(\cdot )}$は累積分布関数であり、例えば標準ロジスティックCDFである。

${\displaystyle {\text{CDF}}(x)={\frac {1}{1+\exp \left[-x\right]}}.}$

これらのアルゴリズムは、トレーニング データ内のすべてのクエリにわたって平均化された、上記の評価尺度の 1 つの値を直接最適化しようとします。ほとんどの評価尺度はランキング モデルのパラメータに関して連続関数ではないため、これは実際には困難な場合が多く、評価尺度の連続近似または境界を使用する必要があります。たとえば、SoftRank アルゴリズム。^{[ 16 ]} LambdaMART は、リストワイズ目的関数を近似することが経験的に示されているペアワイズ アルゴリズムです。^{[ 17 ]}

以下に、発表済みの学習型ランキングアルゴリズムの一部と、各手法の初発表年を示します。

注：ほとんどの教師あり学習によるランキングアルゴリズムは、ポイントワイズ、ペアワイズ、リストワイズのいずれのケースにも適用できるため、上記ではランキングを念頭に置いて特別に設計された手法のみを示しています。

商用ウェブ検索エンジンは、 2000年代から機械学習によるランキングシステムを使用し始めた。最初にこれを使用した検索エンジンの1つはAltaVista （後にその技術はOverture、そしてYahooに買収された）で、2003年4月に勾配ブースティングで学習したランキング機能を導入した。^{[ 51 ] [ 52 ]}

2009年のローンチ時、Microsoft Bingの検索エンジンは、 2005年にMicrosoft Researchで発明されたRankNetアルゴリズム^{[ 53 ]}によって駆動されていました。

2009年11月、ロシアの検索エンジンYandexは^{[ 54 ]} 、独自の新しいMatrixNetアルゴリズム（オブリビアス決定木を使用する勾配ブースティング法の変種）を導入したことにより、検索品質が大幅に向上したと発表した。 ^{[ 55 ]}また最近では、自社の検索エンジンの運用データに基づいて、機械学習によるランキングコンテスト「Internet Mathematics 2009」^{[ 56 ]}を主催した。Yahooも2010年に同様のコンテストを発表している。^{[ 57 ]}

2008年時点で、Googleのピーター・ノーヴィグは、同社の検索エンジンが機械学習によるランキングのみに依存していることを否定した。^{[ 58 ]} CuilのCEOであるトム・コステロは、クリック率やランディングページ滞在時間などの指標で測定した場合、機械学習モデルよりも手動構築モデルの方が優れているため、手動構築モデルを好むと示唆している。これは、機械学習モデルが「人々が実際に好きなものではなく、人々が好きだと言うものを学習する」ためである。^{[ 59 ]}

2017年1月、この技術はオープンソースの検索エンジンApache Solrに組み込まれました。^{[ 60 ]}また、オープンソースのOpenSearchとElasticsearchでも利用可能です。^{[ 61 ] [ 62 ]}これらの実装により、ランキング学習がエンタープライズ検索で広く利用できるようになりました。