Loading article…
Ranking of query is one of the fundamental problems in information retrieval (IR),[1] the scientific/engineering discipline behind search engines.[2] Given a query q and a collection D of documents that match the query, the problem is to rank, that is, sort, the documents in D according to some criterion so that the "best" results appear early in the result list displayed to the user. Ranking in terms of information retrieval is an important concept in computer science and is used in many different applications such as search engine queries and recommender systems.[3] A majority of search engines use ranking algorithms to provide users with accurate and relevant results.[4]
The notion of page rank dates back to the 1940s and the idea originated in the field of economics. In 1941, Wassily Leontief developed an iterative method of valuing a country's sector based on the importance of other sectors that supplied resources to it. In 1965, Charles H Hubbell at the University of California, Santa Barbara, published a technique for determining the importance of individuals based on the importance of the people who endorse them.[5]
Gabriel Pinski and Francis Narin came up with an approach to rank journals.[6] Their rule was that a journal is important if it is cited by other important journals. Jon Kleinberg, a computer scientist at Cornell University, developed an almost identical approach to PageRank which was called Hypertext Induced Topic Search or HITS and it treated web pages as "hubs" and "authorities".
Google's PageRank algorithm was developed in 1998 by Google's founders Sergey Brin and Larry Page and it is a key part of Google's method of ranking web pages in search results.[7] All the above methods are somewhat similar as all of them exploit the structure of links and require an iterative approach.[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%まであります）。つまり、確率モデルでは、関連性は確率で表されます。ここでは、文書は関連性の確率が高い順にランク付けされます。このモデルは、情報検索プロセスにおける不確実性要素を考慮に入れています。つまり、システムによって取得された文書が特定のクエリに関連しているかどうかについての不確実性です。
確率モデルは、いくつかの手法に基づいて、文書が特定のクエリに関連する確率を推定および計算することを目的としています。情報検索の文脈における「イベント」とは、クエリと文書間の関連性の確率を指します。他の情報検索モデルとは異なり、確率モデルは関連性を正確な一致か不一致かの尺度として扱いません。
このモデルは、クエリとドキュメント間の関連性の確率を決定するために様々な手法を採用しています。確率モデルにおける関連性は、クエリとドキュメント間の類似性に基づいて判断されます。さらに、類似性の判断は用語の出現頻度にも依存します。
したがって、1つの用語（B）のみで構成されるクエリの場合、特定の文書（Dm）が関連性があると判断される確率は、クエリ用語（B）を送信し、文書（Dm）が関連性があるとみなしたユーザーの数と、クエリ用語（B）を送信したユーザーの数の比率になります。MaronとKuhnのモデルで示されているように、これは、特定のクエリ用語（B）を送信したユーザーが個々の文書（Dm）が関連性があると判断する確率として表すことができます。
ジェラード・サルトンとマイケル・J・マクギルによれば、このモデルの本質は、関連文書における様々な用語の出現確率の推定値を計算できれば、文書が関連性があるか否かにかかわらず、文書が検索される確率を推定できるということである。[ 11 ]
いくつかの実験では、確率モデルが良好な結果をもたらすことが示されています。しかし、そのような結果は、ブールモデルやベクトル空間モデルを使用した結果よりも十分に優れているわけではありません。[ 12 ] [ 13 ]
最も一般的な評価尺度は、精度、再現率、およびF値です。これらは、順序付けされていない文書セットを使用して計算されます。現代の検索エンジンで標準となっている順位付けされた検索結果を評価するには、これらの尺度を拡張するか、新しい尺度を定義する必要があります。順位付けされた検索のコンテキストでは、適切な検索文書セットは、上位 k 個の検索文書によって自然に与えられます。このような各セットについて、精度と再現率の値をプロットして、精度-再現率曲線を作成できます。[ 14 ]
精度は、検索プロセスの正確さを測る指標です。関連する文書の実際のセットをI、検索された文書のセットをOとすると、精度は次のように表されます。
再現率は、情報検索プロセスの完全性を測る指標です。実際の関連文書セットをI、検索された文書セットをOとすると、再現率は次のように表されます。
F1スコアは、精度と再現率という2つの指標を組み合わせようとするものです。これは両者の調和平均です。精度をP、再現率をRとすると、Fスコアは次のように表されます。
PageRankアルゴリズムは、ユーザーがリンクをランダムにクリックした場合に特定のページに到達する可能性を表す確率分布を出力します。Pag eRankは、任意のサイズの文書コレクションに対して計算できます。いくつかの研究論文では、計算プロセスの開始時に、コレクション内のすべての文書間で分布が均等に分配されていると仮定されています。PageRankの計算では、近似PageRank値を理論上の真の値により近い値に調整するために、コレクションを複数回走査する必要があります。計算式は以下のとおりです。
つまり、ページuの PageRank 値は、セットB u (ページuにリンクしているすべてのページを含むセット) に含まれる各ページvの PageRank 値を、ページvからのリンク数L ( v ) で割った値に依存します。
PageRankと同様に、HITSはリンク分析を使用してページの関連性を分析しますが、Webグラフ全体ではなく、サブグラフの小さなセットのみで機能し、クエリに依存します。サブグラフは、ハブとオーソリティの重みに従ってランク付けされ、最もランクの高いページが取得されて表示されます。[ 15 ]
再ランキングとは、情報の関連性などの主要なランキング基準と、情報の鮮度や多様性などの追加の目的/制約とのバランスを取るために、アイテムの元のランキングを調整することを意味します。[ 16 ] 最終的なアイテムランキングを構築する際に複数の目的を考慮すると、時間のかかる最適化問題になります[ 17 ] [ 18 ]。そのため、ユーザーがランキングを取得する際の知覚される遅延を抑えるために、最適化を高速化することに多くの研究努力が注がれてきました。[ 19 ] [ 20 ] [ 21 ]
