JavaScriptで全文検索の関連性スコアリング機能を実装する方法_基礎知識

全文検索は、機械学習分野の他のほとんどの問題とは異なり、Web プログラマーが日常業務で頻繁に遭遇する問題です。顧客がどこかに検索ボックスを提供するように要求する場合は、WHERE title LIKE %:query% のような SQL ステートメントを記述して検索機能を実装します。最初は問題ありませんでしたが、ある日、お客様から「検索にエラーがありました!」と連絡がありました。

もちろん、実際に検索に「問題」があるわけではなく、検索結果が顧客の望むものではないというだけです。一般のユーザーは完全一致の方法を知らないため、得られる検索結果の品質は低くなります。この問題を解決するために、全文検索を使用することにしました。退屈な学習期間の後、MySQL の FULLTEXT インデックスを有効にし、「MATCH() ... AGAINST()」などのより高度なクエリ構文を使用しました。

さて、問題は解決し、花は完成しました。データベースのサイズが小さい場合は問題ありません。

しかし、データが増えると、データベースの速度がどんどん遅くなることに気づくでしょう。 MySQL は、あまり使いやすい全文検索ツールではありません。そこで、ElasticSearch を使用し、コードをリファクタリングし、Lucene を利用した全文検索クラスターをデプロイすることにしました。非常にうまく、速く、正確に機能することがわかります。

この時点で、「Lucene はなぜこれほど素晴らしいのでしょうか?」と疑問に思わずにはいられません。

この記事 (主に TF-IDF、Okapi BM-25、および通常の関連性スコアリングの紹介) と次の記事 (主にインデックス作成の紹介) では、全文検索の背後にある基本概念について説明します。

関連性

検索クエリごとに、各ドキュメントの「関連性スコア」を簡単に定義します。ユーザーが検索するとき、ドキュメントの出現時間の代わりに関連性スコアを使用して並べ替えることができます。こうすることで、作成された時間がどれだけ前であっても、最も関連性の高いドキュメントが最初にランク付けされます (もちろん、ドキュメントの作成時間に関係する場合もあります)。

単語間の相関関係を計算する方法はたくさんありますが、最も単純な統計ベースの方法から始めます。この方法では、言語自体の理解は必要ありませんが、単語の使用数をカウントし、一致し、文書内の固有の単語の蔓延に基づいて重み付けすることによって「関連性スコア」を決定します。

このアルゴリズムは、単語が名詞であるか動詞であるか、また単語の意味を気にしません。重要なのは、どの単語が一般的で、どの単語が珍しいかということだけです。検索クエリに一般的な単語と珍しい単語の両方が含まれている場合は、珍しい単語を含むドキュメントに高いスコアを与え、一般的な単語の重みを下げることをお勧めします。

このアルゴリズムは Okapi BM25 と呼ばれます。これには 2 つの基本概念が含まれています。用語頻度 (用語頻度) (用語頻度 (「TF」) と略称) と逆文書頻度 (逆文書頻度 (略称「IDF」) ) です。これらをまとめて「TF-IDF」と呼ばれます。文書内での用語の重要性を示すために使用される統計的尺度。

TF-IDF

用語頻度 (略して「TF」) は、文書内に特定の単語が出現する回数という非常に単純な指標です。この値を文書内の総単語数で割ると、スコアが得られます。たとえば、文書内に 100 単語があり、「the」という単語が 8 回出現する場合、「the」の TF は 8 または 8/100、つまり 8% になります (表現方法によって異なります)。

逆ドキュメント頻度 (略して「IDF」) はもう少し複雑です。単語がまれであればあるほど、この値は高くなります。これは、文書の総数をその用語を含む文書の数で割り、商の対数を取ることによって得られます。単語がレアであればあるほど、生成される「IDF」は高くなります。

これら 2 つの数値を掛け合わせると (TF*IDF)、文書内の単語の重みが得られます。 「重み」は次のように定義されます: その単語はどれくらいまれで、文書内にどのくらいの頻度で出現しますか?

この概念は、ドキュメントの検索クエリに使用できます。クエリ内のキーワードごとに、TF-IDF スコアを計算し、それらを加算します。最も高いスコアを持つドキュメントが、クエリ ステートメントに最もよく一致するドキュメントです。

なんてクールなんだろう！

オカピ BM25

上記のアルゴリズムは使用可能なアルゴリズムですが、完全ではありません。これにより、統計に基づいた相関スコア アルゴリズムが得られ、さらに改善することができます。

Okapi BM25 は、これまでのところ最も高度なランキング アルゴリズムの 1 つと考えられています (そのため、 ElasticSearch という名前が付けられています)。 okapi BM25 は、TF-IDF に基づいて 2 つの調整可能なパラメータ k1 と b を追加します。これらはそれぞれ「ターム周波数飽和」と「フィールド長仕様」を表します。これは一体何ですか？

「単語の頻度の飽和」を直感的に理解するには、野球について論じた同様の長さの 2 つの記事を想像してください。また、すべての文書 (これら 2 つを除く) には野球関連のコンテンツがあまり含まれていないと仮定します。そのため、「野球」という単語の IDF が高くなります。これは非常にまれで重要です。 どちらの記事も野球について論じており、かなりのスペースを割いていますが、一方の記事は他方の記事よりも「野球」という言葉を多く使用しています。この場合、ある記事のスコアは本当に別の記事と大きく異なるのでしょうか?どちらの文書も野球全般について論じているため、「野球」という単語が 40 回出現するか 80 回出現するかは問題ではありません。実際には 30 回が上限です。

これは「単語頻度の飽和」です。ネイティブの TF-IDF アルゴリズムには飽和の概念がないため、「baseball」が 80 回出現するドキュメントは、40 回出現するドキュメントのスコアの 2 倍になります。場合によっては、これが必要な場合があります。しかし、時にはそれを望まないこともあります。

さらに、Okapi BM25 には、彩度の変化率を調整するために使用される k1 パラメーターもあります。 k1 パラメータの値は通常 1.2 ～ 2.0 の間です。値が低いほど、飽和プロセスが速くなります。 (つまり、上の 2 つのドキュメントには「野球」という単語が多く含まれているため、同じスコアになります)

フィールド長の正規化により、ドキュメントの長さがすべてのドキュメントの平均長に短縮されます。これは、単一フィールドのコレクション (私たちのコレクションなど) で、異なる長さのドキュメントを同じ比較基準に統合するのに役立ちます。 2 つのフィールド コレクション (「タイトル」と「本文」など) の場合は、タイトル フィールドと本文フィールドも同じ比較基準に統合されるため、より合理的です。フィールド長の削減は b で表され、0 から 1 までの値を持ちます。1 は完全な削減を意味し、0 は削減なしを意味します。

アルゴリズム

Okapi アルゴリズムの公式については、Okapi BM25 Wikipedia で学ぶことができます。式の各項が何であるかがわかったので、理解するのは簡単でしょう。したがって、式については触れずにコードに直接進みましょう:

BM25.Tokenize = function(text) {
  text = text
    .toLowerCase()
    .replace(/\W/g, ' ')
    .replace(/\s+/g, ' ')
    .trim()
    .split(' ')
    .map(function(a) { return stemmer(a); });
 
  // Filter out stopStems
  var out = [];
  for (var i = 0, len = text.length; i < len; i++) {
    if (stopStems.indexOf(text[i]) === -1) {
      out.push(text[i]);
    }
  }
 
  return out;
};

文字列をトークンの配列に解析するための単純な静的メソッド Tokenize() を定義します。それだけです。(エントロピーを減らすために) すべてのトークンを小文字にします。 Porter Stemmer アルゴリズムを実行して、エントロピーの量を削減しながら、一致度を向上させます (「歩行」一致と「歩行」一致は同じです)。また、エントロピーをさらに削減するために、ストップ ワード (非常に一般的な単語) もフィルターで除外します。私が書く概念について深く掘り下げる前に、このセクションで説明しすぎた場合はご容赦ください。

BM25.prototype.addDocument = function(doc) {
  if (typeof doc.id === 'undefined') { throw new Error(1000, 'ID is a required property of documents.'); };
  if (typeof doc.body === 'undefined') { throw new Error(1001, 'Body is a required property of documents.'); };
 
  // Raw tokenized list of words
  var tokens = BM25.Tokenize(doc.body);
 
  // Will hold unique terms and their counts and frequencies
  var _terms = {};
 
  // docObj will eventually be added to the documents database
  var docObj = {id: doc.id, tokens: tokens, body: doc.body};
 
  // Count number of terms
  docObj.termCount = tokens.length;
 
  // Increment totalDocuments
  this.totalDocuments++;
 
  // Readjust averageDocumentLength
  this.totalDocumentTermLength += docObj.termCount;
  this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments;
 
  // Calculate term frequency
  // First get terms count
  for (var i = 0, len = tokens.length; i < len; i++) {
    var term = tokens[i];
    if (!_terms[term]) { 
      _terms[term] = {
        count: 0,
        freq: 0
      }; 
    };
    _terms[term].count++;
  }
 
  // Then re-loop to calculate term frequency.
  // We'll also update inverse document frequencies here.
  var keys = Object.keys(_terms);
  for (var i = 0, len = keys.length; i < len; i++) {
    var term = keys[i];
    // Term Frequency for this document.
    _terms[term].freq = _terms[term].count / docObj.termCount;
 
    // Inverse Document Frequency initialization
    if (!this.terms[term]) {
      this.terms[term] = {
        n: 0, // Number of docs this term appears in, uniquely
        idf: 0
      };
    }
 
    this.terms[term].n++;
  };
 
  // Calculate inverse document frequencies
  // This is SLOWish so if you want to index a big batch of documents,
  // comment this out and run it once at the end of your addDocuments run
  // If you're only indexing a document or two at a time you can leave this in.
  // this.updateIdf();
 
  // Add docObj to docs db
  docObj.terms = _terms;
  this.documents[docObj.id] = docObj;
};

ここで addDocument() メソッドが魔法のように現れます。基本的に、this.documents と this.terms という 2 つの同様のデータ構造を構築し、維持します。

This.documentsis は、すべての文書を保存するデータベースです。文書のすべての原文、文書の長さ情報、文書内のすべての単語とその出現頻度を保存するリストが保存されます。言葉。このデータ構造を使用すると、次の質問に簡単かつ迅速に答えることができます (はい、非常に高速です。所要時間は O(1) の時間計算量のハッシュ テーブル クエリだけです)。 ドキュメント #3 では、これを「ウォーク」します。言葉が出てくる？

別のデータ構造である this.terms も使用します。これはコーパス内のすべての単語を表します。このデータ構造を通じて、次の質問に O(1) 時間で答えることができます。「walk」という単語はいくつの文書に出現しますか?彼らのIDは何ですか?

最後に、各文書の長さを記録し、コーパス全体にわたる文書の平均長を記録します。

上記のコードでは、idf が 0 に初期化され、updateidf() メソッドがコメント化されていることに注意してください。これは、このメソッドの実行が非常に遅く、インデックス作成後に 1 回だけ実行する必要があるためです。 1 回実行すればニーズを満たすことができるため、5,000 回実行する必要はありません。最初にコメントアウトし、大量のインデックス作成操作の後で実行すると、時間を大幅に節約できます。この関数のコードは次のとおりです:

BM25.prototype.updateIdf = function() {
  var keys = Object.keys(this.terms);
  for (var i = 0, len = keys.length; i < len; i++) {
    var term = keys[i];
    var num = (this.totalDocuments - this.terms[term].n + 0.5);
    var denom = (this.terms[term].n + 0.5);
    this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01);
  }
};

これは非常に単純な関数ですが、コーパス全体のすべての単語を走査し、すべての単語の値を更新する必要があるため、動作が少し遅くなります。この方法は、逆ドキュメント頻度の標準公式 (この公式は Wikipedia で見つけることができます) を使用して実装されます。つまり、ドキュメントの総数をその単語を含むドキュメントの数で割って、その商の対数を求めます。戻り値が常に 0 より大きくなるようにいくつかの変更を加えました。

BM25.prototype.search = function(query) {
 
  var queryTerms = BM25.Tokenize(query);
  var results = [];
 
  // Look at each document in turn. There are better ways to do this with inverted indices.
  var keys = Object.keys(this.documents);
  for (var j = 0, nDocs = keys.length; j < nDocs; j++) {
    var id = keys[j];
    // The relevance score for a document is the sum of a tf-idf-like
    // calculation for each query term.
    this.documents[id]._score = 0;
 
    // Calculate the score for each query term
    for (var i = 0, len = queryTerms.length; i < len; i++) {
      var queryTerm = queryTerms[i];
 
      // We've never seen this term before so IDF will be 0.
      // Means we can skip the whole term, it adds nothing to the score
      // and isn't in any document.
      if (typeof this.terms[queryTerm] === 'undefined') {
        continue;
      }
 
      // This term isn't in the document, so the TF portion is 0 and this
      // term contributes nothing to the search score.
      if (typeof this.documents[id].terms[queryTerm] === 'undefined') {
        continue;
      }
 
      // The term is in the document, let's go.
      // The whole term is :
      // IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength))
 
      // IDF is pre-calculated for the whole docset.
      var idf = this.terms[queryTerm].idf;
      // Numerator of the TF portion.
      var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1);
      // Denomerator of the TF portion.
      var denom = this.documents[id].terms[queryTerm].count 
        + (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength)));
 
      // Add this query term to the score
      this.documents[id]._score += idf * num / denom;
    }
 
    if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) {
      results.push(this.documents[id]);
    }
  }
 
  results.sort(function(a, b) { return b._score - a._score; });
  return results.slice(0, 10);
};

最後に、search() メソッドはすべてのドキュメントを走査し、各ドキュメントの BM25 スコアを取得して降順に並べ替えます。もちろん、検索中にコーパス内のすべての文書を調べるのは賢明ではありません。この問題については、パート 2 (逆インデックスとパフォーマンス) で説明します。

上記のコードには十分なコメントが付けられており、その要点は次のとおりです。 各文書および各単語の BM25 スコアを計算します。単語の IDF スコアは事前に計算されているため、使用するときにクエリを実行するだけで済みます。単語の頻度もドキュメント プロパティの一部として事前に計算されます。その後は、単純な四則演算のみが必要になります。最後に、一時変数 _score を各ドキュメントに追加し、スコアに従って降順に並べ替えて、上位 10 件の結果を返します。
例、ソースコード、メモ、次のステップ

上記の例を最適化する方法はたくさんあります。それらについては「全文検索」の第 2 部で紹介します。楽しみにしていてください。数週間以内に完成できればと思います。以下は次回言及するリストです:

• 逆インデックスと高速検索
• クイックインデックス
• より良い検索結果

このデモンストレーションのために、私はかなりの数 (85,000) の Wikipedia 記事の最初の段落までクロールする小さな Wikipedia クローラーを作成しました。すべての 85,000 ファイルのインデックス作成には約 90 秒かかるため、私のコンピュータではその時間を半分に短縮しました。単純な全文プレゼンテーションのためだけにラップトップのパワーを無駄にしてほしくないのです。

インデックス作成はモジュール式の重い CPU 操作であるため、私はこれをネットワーク ワーカーとして扱います。インデックス作成はバックグラウンド スレッドで実行されます --完全なソース コードはここにあります。ステミングアルゴリズムと私のストップワードリストへのソースコードリファレンスも見つかります。コードライセンスに関しては、教育目的であれば引き続き無料であり、商業目的には無料です。

最後にデモです。インデックスが完成したら、ランダムなものや語句を探してみると、Wikipedia がそれを認識します。インデックス付けされているセグメントは 40,000 のみであるため、いくつかの新しいトピックを試してみることをお勧めします。