ランキング（情報検索）

クエリのランキングは、検索エンジンを支える科学/工学分野である情報検索(IR) ^[1]における基本的な問題の 1 つです。^[2]クエリqとクエリに一致するドキュメントのコレクションDが与えられた場合、問題は、何らかの基準に従ってD内のドキュメントをランク付け、つまり並べ替えて、ユーザーに表示される結果リストの早い段階で「最良」の結果が表示されるようにすることです。情報検索におけるランキングは、コンピューター サイエンスの重要な概念であり、検索エンジン クエリやレコメンデーション システムなど、さまざまなアプリケーションで使用されています。^[3]検索エンジンの大部分は、ランキング アルゴリズムを使用して、ユーザーに正確で関連性の高い結果を提供します。^[4]

ページランクの概念は1940年代に遡り、経済学の分野で生まれました。1941年、ワシリー・レオンチェフは、国のセクターを、その国に資源を供給する他のセクターの重要性に基づいて評価する反復的な方法を開発しました。1965年、カリフォルニア大学サンタバーバラ校のチャールズ・H・ハッベルは、個人を支持する人々の重要性に基づいて個人の重要性を決定する手法を発表しました。^[5]

ガブリエル・ピンスキーとフランシス・ナリンは、ジャーナルをランク付けするアプローチを考案しました。^[6]彼らのルールは、他の重要なジャーナルによって引用されているジャーナルが重要であるというものでした。コーネル大学のコンピューター科学者であるジョン・クラインバーグは、ハイパーテキスト誘導トピック検索またはHITSと呼ばれるPageRankとほぼ同じアプローチを開発し、 Webページを「ハブ」および「オーソリティ」として 扱いました。

GoogleのPageRankアルゴリズムは、1998年にGoogleの創設者であるセルゲイ・ブリン氏とラリー・ペイジ氏によって開発され、検索結果でウェブページをランク付けするGoogleの方法の重要な部分となっています。^[7]上記の方法はすべてリンクの構造を利用し、反復的なアプローチを必要とするため、多少似ています。^[8]

ランキング関数はさまざまな方法で評価されます。最も単純な方法の 1 つは、ある固定されたkに対して上位k個の結果の精度を決定することです。たとえば、多くのクエリの平均で、関連する上位 10 件の結果の割合などです。

IRモデルは、ブールモデル（BIR）、ベクトル空間モデル、確率モデルの3種類に大別できます。^[9]検索モデル間のさまざまな比較は文献で見つけることができます（例：^[10]）。

ブールモデル (BIR) は、各クエリが代数式を使用したリレーショナル代数の基本原理に従い、ドキュメントが互いに完全に一致しない限り取得されない、シンプルなベースライン クエリ モデルです。クエリはドキュメントを取得する (1) か、ドキュメントを取得しないか (0) のいずれかであるため、それらをランク付けする方法はありません。

ブールモデルは完全一致のみを取得するため、部分的に一致するドキュメントの問題には対処できません。ベクトル空間モデルは、それぞれ重みが割り当てられたインデックス項目のベクトルを導入することでこの問題を解決します。ドキュメントが存在する場合、重みは正（完全にまたはある程度一致した場合）から負（一致しない場合または完全に反対に一致した場合）の範囲になります。用語頻度 - 逆ドキュメント頻度（tf-idf）は、重みが用語（単語、キーワード、フレーズなど）で、次元がコーパス内の単語数である、最も一般的な手法の 1 つです。

クエリとドキュメント間の類似度スコアは、コサイン類似度を使用してクエリ重みベクトルとドキュメント重みベクトル間のコサイン値を計算することで見つけることができます。 類似度スコアに従ってランク付けし、スコアが最も高い、またはクエリベクトルに最も関連性の高い上位 k 個のドキュメントを取得することで、目的のドキュメントを取得できます。

確率モデルでは、確率理論は検索プロセスを数学的にモデル化するための主要な手段として使用されています。情報検索の確率モデルは、1960 年に Maron と Kuhns によって導入され、Roberston と他の研究者によってさらに開発されました。Spack Jones と Willett (1997) によると、確率概念を導入する根拠は明らかです。IR システムは自然言語を扱っていますが、これはあまりに不正確であるため、特定のクエリに関連するドキュメントをシステムが確実に示すことはできません。

このモデルは、確率理論を情報検索に適用します (イベントの発生可能性は 0 パーセントから 100 パーセントです)。つまり、確率モデルでは、関連性は確率で表現されます。ここでは、ドキュメントは関連性の確率の降順でランク付けされます。IR プロセスにおける不確実性要素、つまり、システムによって取得されたドキュメントが特定のクエリに関連しているかどうかに関する不確実性を考慮します。

確率モデルは、いくつかの方法に基づいて、ドキュメントが特定のクエリに関連する確率を推定および計算することを目的としています。情報検索のこのコンテキストでの「イベント」は、クエリとドキュメント間の関連性の確率を指します。他の IR モデルとは異なり、確率モデルは関連性を正確な一致または不一致の測定として扱いません。

このモデルは、クエリとドキュメント間の関連性の確率を決定するためにさまざまな方法を採用しています。確率モデルにおける関連性は、クエリとドキュメント間の類似性に基づいて判断されます。類似性の判断は、用語の頻度にも依存します。

したがって、1 つの用語 (B) のみで構成されるクエリの場合、特定のドキュメント (Dm) が関連していると判断される確率は、クエリ用語 (B) を送信し、ドキュメント (Dm) が関連していると考えるユーザーと、用語 (B) を送信したユーザーの数との比率です。Maron と Kuhn のモデルで表されているように、特定のクエリ用語 (B) を送信するユーザーが個々のドキュメント (Dm) を関連していると判断する確率として表すことができます。

ジェラルド・サルトンとマイケル・J・マギルによれば、このモデルの本質は、関連文書におけるさまざまな用語の出現確率の推定値を計算できれば、文書が関連しているかどうかにかかわらず、文書が検索される確率を推定できるという点にある。^[11]

いくつかの実験では、確率モデルが良い結果をもたらすことが示されています。しかし、そのような結果はブールモデルやベクトル空間モデルを使用して得られた結果よりも十分に優れているわけではありません。^{[12] [13]}

最も一般的な評価尺度は、精度、再現率、および f スコアです。これらは、順序付けされていない文書セットを使用して計算されます。現代の検索エンジンで標準となっているランク付けされた検索結果を評価するには、これらの尺度を拡張するか、新しい尺度を定義する必要があります。ランク付けされた検索コンテキストでは、検索された文書の適切なセットは、検索された上位 k 個の文書によって自然に与えられます。このようなセットごとに、精度と再現率の値をプロットして、精度-再現率曲線を作成できます。^[14]

精度は、検索プロセスの正確さを測定します。実際の関連文書セットが I で示され、検索された文書セットが O で示される場合、精度は次のように表されます。 $${\displaystyle {\text{精度}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{O}}\}|}}}$$

再現率は、IR プロセスの完全性の尺度です。実際の関連文書セットを I で表し、取得された文書セットを O で表すと、再現率は次のように表されます。 $${\displaystyle {\text{想起}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{I}}\}|}}}$$

F1 スコアは、精度と再現率の測定を組み合わせようとします。これは 2 つの調和平均です。P が精度で R が再現率の場合、F スコアは次のように表されます。

${\displaystyle F_{1}=2\cdot {\frac {\mathrm {P} \cdot \mathrm {R} }{\mathrm {P} +\mathrm {R} }}}$

PageRankアルゴリズムは、リンクをランダムにクリックした人が特定のページに到達する可能性を表すために使用される確率分布を出力します。 PageRank は、任意のサイズのドキュメント コレクションに対して計算できます。 いくつかの研究論文では、計算プロセスの開始時に、分布がコレクション内のすべてのドキュメント間で均等に分割されると想定されています。 PageRank の計算では、コレクションを複数回通過して、おおよその PageRank 値を調整し、理論上の真の値をより正確に反映する必要があります。 計算式は次のとおりです。

${\displaystyle PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}}$

つまり、ページuの PageRank 値は、セットB _u (ページuにリンクしているすべてのページを含むセット) に含まれる各ページvの PageRank 値を、ページvからのリンクの量L ( v )で割った値に依存します。

PageRankと同様に、HITSはリンク分析を使用してページの関連性を分析しますが、（ウェブグラフ全体ではなく）サブグラフの小さなセットでのみ機能し、クエリに依存します。サブグラフはハブとオーソリティの重みに従ってランク付けされ、最も高いランクのページが取得されて表示されます。^[15]

• ランキングの学習：ランキング問題への機械学習の応用
• セマンティック検索