Using an Inverted Index Synopsis for Query Latency and Performance Prediction - HigashiKed/patent_prior-art_search GitHub Wiki

Using an Inverted Index Synopsis for Query Latency and Performance Prediction
https://dl-acm-org.remote.library.osaka-u.ac.jp:8443/doi/pdf/10.1145/3389795
クエリの待ち時間とパフォーマンスの予測に転置インデックスの概要を使用する

最新のだと，Using an Inverted Index Synopsis for Query Latency and Performance Prediction, ACM TOIS, 2020. の11章(QPP: Query Performance Predictors). 例えば，AvIDF [20] などでは iDF をベースに使っています．他は，QueryScope [20], Clarity Score [13] など，2006年の論文と同じ様子．結局のところ，特にnDCG20 の場合は iDFだけではダメで，TF的な要素が必要という印象．nDCG1000だとコンパラ． 若干の詳細： NDCG@20 の結果を見ると iDF ベースのものは良く無くて，SCQ が良い結果になっている（指標値とnDCGの相関が比較的高い）．NDCG@1000だとどの手法も似たような状況． タスクは 200 TREC Web track queries

SCQ [41]: predictor measures the similarity between the query and the document collection

最も性能が良いのは既存のアルゴリズムの上位互換になっているWPM

WPM [29]. This is a family of predictors proposed by Roitman et al., based around the Weighted Product Model, which can generate various predictors and subsume others in the literature. F

多くの商用検索エンジンの基礎となる動的プルーニング手法では、クエリの待機時間を正確に予測することは困難

11 USE CASE: PREDICTING QUERY PERFORMANCE

index synoposisの最終的なユースケースは、Query Performance Predictors（QPP）に関係しており、パフォーマンスは検索システムの有効性に関係しています[9]。 実際、QPPは、特定のクエリについて、その検索エンジンの有効性（MAPやNDCGなどの評価指標で測定）を予測することを目的として、長年IRで研究されてきました。 そのため、多くのクエリパフォーマンス予測子が文献で提案されています。 ほとんどの既存の作品は、検索前（つまり、クエリが実行される前）と検索後の予測子を対比しています。 さらに、計算時に予測子が必要とする情報を明確に強調表示します。

  • Pre-retrieval
    これらのクエリパフォーマンス予測子は、クエリの実行がまだ開始されていないことを前提としているため、利用可能な情報は、IDFなどのIRシステムのレキシコンに記録されている情報のみです[19]。 他の事前に計算された用語レベルの情報は、このグループで特徴付けることができます。 たとえば、非常に頻繁なクエリ用語のみを含むクエリは、予測子の平均逆収集用語頻度によって測定される可能性があるため、うまく機能しないと予想される場合があります[20]。
  • Post-retrieval (retrieval scores)
    このファミリに属する予測子は、クエリに対して取得されたドキュメントのスコア分布を調べます。 単純なレベルでは、このような予測子は、検索された上位のドキュメントの平均スコアが高いクエリが、関連するドキュメントを取得する可能性が高いと想定する場合があります。
  • Post-retrieval (document contents)
    一部の予測子は、取得したドキュメントの内容を調べる場合があります。 たとえば、取得したドキュメントが単一のコヒーレントに焦点を合わせているクエリは、パフォーマンスが高くなる可能性が高くなります。対照的に、ドキュメント内でランダムに発生する情報の少ない単語（ストップワードなど）のみを含むクエリは、さまざまなトピックをカバーします。
  • Post-retrieval (term co-occurrence)
    一部の予測子は、コーパス内のクエリ用語の共起を調べる場合があります。コーパスでn-gram言語モデルが使用できない場合（デフォルトでユニグラム位置にインデックスを付ける多くの検索エンジンで一般的）、そのような 予測子は、転置インデックス投稿リストのパス中にのみ計算できます。 このため、このような予測子は、検索前と見なされていた以前の作業ではなく、検索後として特徴付けられます。

注意：クエリ効率予測とは対照的に、取得が終了した後に計算されるクエリパフォーマンス予測子は、システムでは利用できない関連性を予測するため、依然として有用です。これは、クエリが実行されるとシステムの正確な応答時間がわかるため、本質的に事前取得であるクエリ効率予測とは対照的です。第1段階の検索後のクエリパフォーマンス予測子は、さまざまなクエリの定式化の重要性を選択する際に使用でき[31]、または後の段階で学習したランキングモデル内の機能として使用できます[24]。このセクションでは、最初に、インデックスの概要を使用して計算する際の、取得後のクエリパフォーマンス予測子の精度を調べます。 特に、検索前の予測子を計算するコストが安価であることを考えると、検索後の焦点は当然です。 次に、インデックスの概要に関する最良の検索後クエリパフォーマンス予測子のパフォーマンスを、3つの検索前予測子と比較します。

11.1 Query Performance Predictors

  • AvIDF [20].
    この検索前予測子は、クエリを構成する用語の平均逆ドキュメント頻度が平均精度と正の相関関係にあることを前提としています。
  • AvICTF [20].
    この検索前予測子はAvIDFに似ていますが、平均はクエリ用語の逆収集用語頻度で計算されます。
  • SCQ 41.
    この検索前予測子は、ドキュメントコレクションとクエリをベクトルとしてモデル化します。コサイン距離の点でコレクションベクトルに類似しているクエリベクトルは、処理が簡単であると見なされます。
  • NSCQ [41].
    この検索前予測子は、SCQスコアを語彙内クエリ用語の数で割ったものに対応します。
  • AvPMI [18].
    クエリ用語間の強い関係は、成功する可能性が高い整形式のクエリを示していると見なされます。 この予測子では、クエリ用語間の平均的なポイントごとの相互情報量が調べられます。 これには、クエリ用語の各ペアが存在するドキュメントの数に関する知識が必要なため、これを検索後の予測子として特徴付けます。
  • EnIDF [24].
    この予測子は、すべてのクエリ用語に一致するドキュメントの数を考慮します。これは、すべてのクエリ用語の投稿リストの共通部分のサイズのIDFとして定義されます。 これにはクエリの投稿リストを通過する必要があるため、この予測子は本質的に検索後のものと見なされます。
  • QueryScope [20].
    EnIDFと同様に、この予測子は、（すべてのクエリ用語ではなく）クエリ用語のいずれかに一致するドキュメントの数を考慮します。 これは、すべてのクエリ用語の投稿リストの和集合のサイズの-ログとして定義されます。
  • Clarity Score [13].
    この予測子は、取得したドキュメントの内容を調べて、それらのドキュメントでの言語使用の一貫性を測定します。 各ドキュメントのコンテンツを（たとえば、フォワードインデックスまたはダイレクトインデックスから）ロードする必要があるため、この予測子は本質的にコストがかかる可能性があります。 それでも、インデックスの概要からの結果がコンテンツの観点からどれほど代表的であるかを示しているので、実験に含めることは興味深いことです。
  • WPM [29].
    これは、加重積モデルに基づいてRoitman et al。によって提案された予測子のファミリーであり、さまざまな予測子を生成し、他の予測子を文献に含めることができます。 このため、検索後のスコアベースの予測子の数の基礎として使用します。 実際、著者はさまざまな証拠を単一の識別予測子に組み合わせるための学習フレームワークを提案しましたが、さまざまな予測子を生成して評価します。 特に、WPMは、平均検索スコア（特定のランクカットオフまで）がクエリパフォーマンス予測の優れた推定量であるという前提に基づいています。 ただし、検索スコアは多くのバイアスの影響を受けます。 したがって、彼らはいくつかの正規化を提案しています。
  1. invQLen:各ドキュメントの検索スコアは、クエリの長さの平方根の逆数で正規化されます。
  2. invDocLen:各ドキュメントの取得スコアは、ドキュメントの長さの逆数1で正規化されます。
  3. invCS: これにより、コーパスとクエリの類似性に応じて、すべてのドキュメントのスコアが調整されます。
  4. invCd:これは、ドキュメントと（おそらく）関連するコーパス全体との関連付けの強さをキャプチャします。
  5. invSD:これにより、すべてのドキュメントの平均スコアからの絶対的な相違に応じて、ドキュメントのスコアが調整されます。

私たちの実験では、これらの正規化のそれぞれを使用してWPMを適用し、平均スコアが計算されるランクカットオフも変更します。

手法のまとめ　

  • AvIDF:idfの平均に基づいてクエリの難易度を決定する手法 1, 2
  • AvIcTF:idfを使用する代わりにクエリのTFを使用する手法1, 2

11.2 Experimental Setup

以下では、完全なインデックスと比較して、概要インデックスを使用したクエリパフォーマンス予測の精度がどの程度類似しているかを評価することを目的としています。 実際、概要インデックスで効果的なクエリパフォーマンス予測を達成すると、たとえば、完全なインデックスでの検索戦略を調整できる可能性があります。たとえば、効果がないと予測されるクエリは、疑似関連性フィードバッククエリの拡張には役立ちません[1]。
私たちの実験では、ClueWeb09Bで計算されたものと同じ概要インデックスを使用しています。 ただし、既知の有効性の値が必要なため、関連性の評価がある200のTREC Web2009-2012トラックトピックを使用します。 したがって、クエリパフォーマンス予測タスクは、BM25を使用するIRシステムの相対的な有効性を予測するものとして定義されます。 短いカットオフと長いカットオフ（NDCG @ 20およびNDCG @ 1000）および平均精度（AP @ 1000）での正規化された割引累積ゲインを使用して、クエリの有効性を測定します。 クエリのパフォーマンス予測は、次を使用して定量化できます。 ケンドールのτなどの相関測定。 以下では、クエリパフォーマンス予測子と実際のNDCG @ 1000の有効性との相関関係、および概要と完全なインデックス予測子の間の相関関係を定量化します。 表11にリストされている、合計21の検索前および検索後の予測子を実験します。これには、上記のクエリパフォーマンス予測子のすべてのファミリが含まれます。

11.3 Results

以下の表12に、完全なインデックスを使用して計算された使用済みクエリパフォーマンス予測子と、完全なインデックスで得られた結果のBM25のNDCG @ 20、NDCG @ 1000、およびAP @ 1000に関する有効性との相関関係を示します。 表13に、概要インデックスで計算されたクエリパフォーマンス予測子と完全インデックスで計算されたクエリパフォーマンス予測子の相関関係を示します。
表12の結果は、200のTRECWebトラッククエリでNDCG @ 1000と比較して、正確なクエリパフォーマンス予測を達成することの難しさの全体像を示しています。予測子とさまざまな評価指標の間で観察された最も高い相関は0.293です。示されたこれらの低い相関関係は、Web検索タスクでのクエリパフォーマンスの認識された難しさと一致しています[39]。実際、AP @ 1000のτ= 0.259の相関は、同じトピックのセットについて参考文献[39]で報告されている未学習の予測子のいずれかで得られた相関よりも高く、で提案されている深層学習ベースの教師ありQPP手法よりもさらに高くなっています。その紙。表12の検索前予測子の中で、最も高いτ相関がSCQとNSCQによって示されます。最初の予測子はクエリとドキュメントコレクション間の類似性を測定し、2番目の予測子はクエリの長​​さによってSCQスコアを正規化します。検索後の予測子間の最も高いτ相関は、WPM（invCS、100）とWPM（invCd、100）によって示されます。これらの予測子は、検索された上位100のドキュメントの平均スコアを測定し、コーパス全体に対するクエリの類似性によって正規化されます。文書と（おそらく）関連するコーパス全体との関連の強さによってそれぞれ。 ClarityScoreの低い有効性は、参考文献[39]で報告されている結果とも一致しています。

次に、表13は、完全なインデックスと比較した概要インデックスで計算された検索後の予測子12間で観察された相関関係を示しています。 全体として、観察される相関はさまざまですが、常に正であり、相関の大きさはγが増加するにつれて増加します。

興味深いことに、用語の共起QPP（AvPMI、EnIDF、QueryScope）は、最も高い相関（τ> 0.9）を示します。概要インデックスが0.1％の場合でも、用語の共起情報は完全なインデックスの情報と同等です。 これは、これらの予測子が完全なインデックスと同様に概要インデックスでも有効であることを示していますが、表12で観察された相関は、クエリの有効性との相関が低いことを示しています。

ただし、表13では、WPMとクラリティスコアの相関関係がより変動します。表12で効果的なパフォーマンス予測ではないことが示された、完全なインデックスのクラリティスコアは、小さい概要インデックスのクラリティスコアと中程度の相関関係があります。 γが増加すると増加します。 WPMはγによって異なりますが、正規化によっても異なります。興味深いことに、表12のWPMの最も効果的な正規化であるinvCSは、より小さな概要インデックスと著しく相関しています（たとえば、WPM（10、invCS、1）はγに対してτ= 0.769を達成します。 = 0.001であり、γ= 0.05の場合はτ= 0.924に増加します。

表14では、完全なインデックス（つまり、表12のSCQ、NSCQ、WPM（invCS、100）、およびWPM（invCd、100））で最もパフォーマンスの高い検索前および検索後のQPPと、最も相関性の高いQPPを比較しています。 インデックスの概要に関する検索後のQPP（つまり、表13のAvPMI、WPM（invCS、10）、およびWPM（invCd、10））は、NDCG @ 20、NDCG @ 1000、およびAP @ 1000の観点から有効です。 フルインデックスで得られたBM25の結果。 表12でパフォーマンスの低下をすでに特定しているため、EnIDFおよびQueryScopeQPPは考慮しません。13NDCG@ 20の場合、インデックス概要の取得後QPPは、γ<0.01の取得前予測子よりも優れていません。 ただし、γ≥0.01および0.05の場合、WPM（invCd、100）およびWPM（invCS、10）予測子はSCQよりも優れています

次に、NDCG @ 1000の場合、WPM（invCS、10）およびWPM（invCS、100）予測子は、サンプリング確率が非常に小さい場合（たとえば、γ= 0.001）でも、最良の検索前予測子、つまりNSCQを上回ります。 実際、γ= 0.001のインデックス概要での検索後予測子WPM（invCS、10）は、検索前予測子を73％（0.137→0.241）、γ= 0.05（0.137→0.287）で109％上回っています。 同じ検索後の予測子は、γ= 0.005から始まる、AP @ 1000メトリックによると、検索前の予測子よりも優れています。 両方のメトリックについて、γ= 0.05のこれらの検索後予測子は、完全なインデックスで計算されたものと同等のパフォーマンスを示し、表13に報告されている結果を確認します。

したがって、全体として、RQ8に対処する際に、検索後の予測子の多く、特にドキュメントのスコアを正規化する最近のWPMフレームワークからの予測子は、非常に小さな概要インデックスで計算すると、同じものと高い相関関係を示すため、効果的であると結論付けます。 完全なインデックスで計算された予測子。 さらに、それらは最良の検索前予測子よりも効果的であり、それらの計算には、概要インデックスのクエリを処理するためにほとんど無視できる時間が必要です。 全体として、これはクエリパフォーマンス予測に概要インデックスを使用することの価値を示していると結論付けます。 実際、私たちの結果は、初回通過検索戦略の調整において、検索後のクエリパフォーマンス予測子（インデックスの概要を使用して計算）の新しい潜在的なアプリケーションを開きます。