imHo RSSフィード

2011-03-03

2.3 スキップポインタを使用した高速な位置リスト交差

Faster postings list intersection via skip pointers

  • この章の残りで、効率を上げるための位置リストデータ構造の拡張について述べる
    • 1.3節ではO(m+n)だったが、もっとよくできないか?
  • ひとつの方法はスキップリストを使うこと
    • リストを順に見ていくんじゃなくて、どこまで飛ばせるかのリストを持っておく
    • スキップリストが働くのはANDクエリのときだけ、ORクエリのときはダメ
  • どのくらいの間隔でスキップさせるか?
  • 逆インデクスの最適なエンコーディングの選択は、コンピュータのテクノロジとその速度とサイズに強く依存する
    • これまではCPUは遅かったので、強く圧縮する方法は最適ではなかった
    • 現在のCPUは速くディスクは遅いので、ディスクの位置リストサイズを減らすことが支配的
    • しかし、すべてをメモリ上で行うサーチエンジンではまた違ってくる。4.1節で、またシステムの速度に与えるインデクスサイズの影響は5章で。

例題:

  • なぜOR演算にはスキップポインタが効かないのか?
  • 16個のエントリと1個のエントリの比較の際、1) 普通の位置リストを使う場合と 2) 長さsqrt(P)のスキップリストを使う場合で比較しろ

2.2.4 幹と見出し語

Stemming and lemmatization

  • 文法によって単語は異なる形式で使われる
    • organize, organizes, organizing
  • また似た単語ファミリーがある
    • deocracy, democratic, democratization
  • Stemming: ポーターのアルゴリズム "http://www.cs.odu.edu/~jbollen/IR04/readings/readings5.pdf:An algorithm for suffix stripping.]"

2011-02-24

2.2.3 正規化

Normalization (equivalence classing of terms)

  • まったく同じじゃなくてもマッチして欲しい
    • USAとU.S.A.とか
  • トークンの正規化(Token normalization)
    • もっとも標準的な方法は等価クラス(equivalence classes)で、集合の1つの名前にする
    • 例えば、トークンanti-discriminatoryとantidiscriinatoryの両方を語句antidiscriminatoryにマップする場合、文書テキストとクエリの両方に行い、サーチすればどちらも復元できる
  • ハイフンなどの文字を削除するだけのマッピングルールは、ルールを簡単に書けるのは利点だけど、文字を足したりするのが簡単じゃない
    • 手動で類似語リストを作ると、carとautomobileというように拡張できる(9章)
  • 2種類の方法:
    1. 一般的な方法は、正規化していないトークンをインデクスし、複数ボキャブラリエントリのクエリ展開リストで正しいクエリ語句を考慮する
    2. インデクスの構築時に展開をする。文書がautomobileを含んでいたら、carとインデクスする(また通常、逆もしかり)、など
  • 両方とも等価クラスに比べると効率的ではない、がより柔軟
アクセントとdiacritics

Accents and diacritics.

  • ウムラウトとか
  • 意味が異なる単語もあるが、入力めんどいので一緒に扱う
大文字小文字

Capitalization/case-folding.

  • 一般的な戦略は、すべて小文字にする
  • 機械学習で頑張る手もあるが、どうせユーザは小文字でクエリを入力するので、あまり役に立たない
英語でのその他の問題

Other issues in English.

  • ne'er = never
  • 3/12/91 = Mar. 12 1991 (U.S.), or 3 Dec 1991 (Europe)
他の言語

Other languages.

  • 英語はWWWの主流で、ウェブページの60%が英語(2007)だが、今後英語以外も伸びるだろう
  • フランス語:女性形男性形、複数単数
  • ドイツ語:ウムラウト
  • 日本語:複数の表記法で、単語を分けない
  • 日本語は難しい表記法としてよく知られている

2011-02-01

2.2.2 一般語(停止語)の削除

Dropping common terms: stop words

  • 文書の選択に役立たない非常に一般的な単語がボキャブラリ全体から抽出される
    • これらの単語は停止語(stop words)と呼ばれる
    • 停止語を決定する一般的な戦略は収集頻度(collection frequency)の類(文書コレクション中に各語句が合計何回登場するか)
    • よく出る単語から手作業で取り出し、停止リスト(stop list)とする、インデクスするときには捨てられる
    • 停止リストの例:a an and are as at be by for from has he in is it its of on that the to was were will with
    • 停止リストはシステムが格納すべき位置の数を非常に減らすことができる
    • 弊害も:To be or not to be, Let it be, I don't want to be, ...
  • IRシステムの一般的なトレンドは、極めて多くのストップリスト(200-300語句)から始まって非常に少ないストップリスト(7-12語句)からストップリストなしになっている
    • ウェブサーチエンジンは一般的にストップリストを使わない
    • 最近のIRシステムは言語の統計を利用して共通単語をよりよい方法で扱う
    • 7.1.5でインパクトソートされたインデクスでどのようにして位置リストのスキャンを早めに打ち切り、共通単語でもそんなに処理コストがかからない方法を示す

2011-01-27

2.2.1 トークン化

Tokenization

  • 文字シーケンスが与えられ、文書ユニットが定義されたら、トークン化はそれをトークンというピースに切り分ける処理で、同時に句読点などの文字を捨てる
    • 型とトークンの区別は重要
    • トークン(token)はある文章中の文字シーケンスの実体で、処理するのに便利な意味単位でグループ化されたもの
    • 型(type)はすべてのトークンが同じ文字シーケンスを含むクラスである?
    • 語句(term)はIRシステムの辞書に含まれる型である
  • 使用する正しいトークンとは何か?
    • 英語でも、アポストロフィとか:aren't
  • トークン化のこれらの問題は言語ごとに変わる。言語特定(Language identification)が必要。
  • 普通じゃない特定のトークン:C++, C#, B-52, M*A*S*Hとか
    • メールアドレスとかURLとかIPアドレスとか積荷追跡番号とか
  • ハイフンの扱いとか
  • スペースが入るけど1つのトークンとして見たいものとか:San Francisco, Los Angeles, white space vs. whitespace
    • 1つの方法として、ユーザがハイフンを指定したら、システムは3つの全てのパターンに一般化する、というものがあるが、ユーザのトレーニングに依存し、ハイフンなしで書いた場合には一般化されない
  • フランス語:アポストロフィ l'ensemble
  • ドイツ語:複合名詞、スペースなしで結合 Lebensversicherungsgesellschaftsangestellter `life insurance company employee'
    • 複合スプリッター(compound-splitter)モジュール
    • この現象は東アジア語(中国語、日本語、韓国語、タイ語)の限定されたケース
    • 隠れマルコフモデルなどの機械学習によるヒューリスティックな方法
      • 間違う可能性もある
    • または単語ベースのインデクス化をやめて単語の区切りかどうかに関わらずすべて単に短い文字シーケンスのインデクス化にしてしまう(k-グラム)
      • このアプローチが魅力的な3つの理由

2011-01-24

2.1.2 文書ユニットの選択

Choosing a document unit

  • 次のフェーズはインデックスする文書ユニット(document unit)を決定すること
    • 例えば伝統的なメールファイルはメール列を1つのファイルに格納しているが、別々の文書として扱いたいだろう
    • メールに添付された文書やzipファイルなど
    • 逆にlatexなどの複数のファイルは1つとして扱いたい
  • より一般的に、非常に長い文書ではインデクスの粒度問題が起こる
    • 本のコレクションでは、本全体を1つの文書としてインデクスするのは悪いアイディア
    • 章や段落をミニ文書としたい、そうすればマッチがより適切になるだろう
    • でもなぜそこで止めるのか?個々の文をミニ文書として扱うこともできるのに。それは精度とリコールのトレードオフがある。ユニットをあまり小さくしすぎると重要なパッセージを見過ごす可能性がある。あまり大きくしすぎるとおかしなマッチが得られてしまい、ユーザが関連する情報を見つけるのが困難になる。
  • 大きな文書ユニットの問題は明示的または暗黙的な近傍サーチ(7.2.2)、トレードオフは8章で扱う。
    • インデクスの粒度や複数レベルの粒度での連続したインデクス文書の必要性は、XMLの復元で登場し、10章で取り上げる。
  • ここでは適切なサイズの文書ユニットが選ばれているものとする。

2011-01-20

2.1.1 文書中の文字シーケンスの獲得

Obtaining the character sequence in a document

  • ウェブサーバにあるファイルのバイトシーケンスから文字の線形シーケンスに変換する
    • プレーンの英語ASCIIエンコードだけなら簡単だけど、そう簡単じゃない
    • エンコード判定:機械学習での分類問題を13章で
  • Microsoftワードドキュメントやzipファイルなどの圧縮フォーマットのデコード
    • XMLや&などのデコードも
  • postscriptやpdfも扱いたいだろうけど、この本では扱わない
  • テキストが文字の線形シーケンスだというアイディアはある書式系、アラビア語など、ある2次元やミックスされた順序の文字などで疑問である

2. 語句ボキャブラリと位置リスト

The term vocabulary and postings lists

  • おさらい:逆インデクスの構築は
    1. インデクスする文書を集める
    2. トークン化する
    3. トークンに言語的な前処理を施す
    4. 各語句が登場する文書をインデクス

2011-01-16

1.4 拡張2値モデル対ランク付け復元

The extended Boolean model versus ranked retrieval

  • 2値復元モデルと対比して、ベクトルスペースモデル(6.3節)などのランク付け復元モデル(ranked retrieval models)自由テキストクエリ(free text queries)で広く使われていて、正確な言語と演算子でクエリを指定する代わりに何語か入力するだけで、システムはクエリを再考に満たす文書を決定する
  • 基本的なブーリアン演算子(AND, OR, NOT)だけでは、語順がめちゃくちゃな結果集合では、人々の情報ニーズは満たせない
  • 近傍演算子(proximity operator)で語句の近さを指定する
  • 動作例:コマーシャルブーリアンサーチ。www.westlaw.com
  • 多くのユーザ、特にプロフェッショナルはブーリアンクエリモデルを好む。ブーリアンクエリは正確だ
  • でも自由テキストクエリの方がいい結果を返す傾向がある

できた方がいいこと:

  1. スペルミスや一貫してない単語の選択も許してくれる
  2. 例えば"operating system"といった複数の単語やフレーズ
  3. 語句が何度出てきたか、重みを指定できる
  4. ブーリアンクエリはマッチした文書の集合を返すだけだけど、順序付けする有効な方法が欲しい

演習:

  • Westlaw文法でクエリを書け
  • メジャーなウェブサーチエンジンで、例えば(i)burglar (ii)burglar AND burglar (iii)burglar OR burglar を検索して結果を見てみよう。

2011-01-15

1.3 2値クエリの処理

Processing Boolean queries

  • 逆インデクスと基本的な2値復元モデルを使ってどのようにクエリを処理するか?
    • 簡単なクエリ:Brutus AND Calpurnia
    • 積集合(intersection)
def intersect(p1, p2):
  answer = []
  i1 = i2 = 0
  while i1 < len(p1) and i2 < len(p2):
    if p1[i1] == p2[i2]:
      answer.append(p1[i1])
      i1 += 1
      i2 += 1
    else:
      if p1[i1] < p2[i2]: i1 += 1
      else:               i2 += 1
  return answer
    • O(N)
  • もっと複雑なクエリ:(Brutus OR Caesar) AND NOT Calpurnia
  • クエリ最適化:AND の場合には、短いリストを含むANDから行えば、結果がそれ以上長くなることはない。
  • なので語句の出現頻度(frequency)をメモリに持っておけば即座にできる
def intersect_lists(ls):
  if len(ls) == 0:
    return []
  terms = sorted_by_increasing_frequency(ls)
  result = terms.pop(0)
  while len(terms) > 0 and len(result) > 0:
    result = intersect(result, terms.pop(0))
  return result

def sorted_by_increasing_frequency(ls):
  return sorted(ls, key = lambda a:[ len(a) ])
    • Pythonでソート順を指定するには、key = で lambda で与える
  • 非対称:積集合の途中の値はメモリ上なのに対して、語句からのものはディスクから読み込まれる
    • 長い位置リストはハッシュテーブルを使う、という代替案

演習

  • 下のクエリでも、まだ積集合はO(x+y)でできるか?
    • Brutas and not Caesar: できる
    • Brutus or not Caesar: できない? not Caesar だと文書全体になってしまう?
  • 任意の論理演算に対応すると、時間の複雑さはどうなるか?
    • OR: O(x+y)
    • AND NOT: O(x+y)
    • もっといい方法ない?
      • x < y + z のとき、x AND (y OR z) よりも (x AND y) OR (x AND z) のほうが速くなる?
  • 分配法則を使うと?
    1. 演習1.3を分配正規形で書け
      • (Brutus OR Caesar) AND NOT (Antony OR Cleopatra)
      • => (Brutus OR Caesar) AND (NOT Antony AND NOT Cleopatra)
      • => (Brutus AND (NOT Antony AND NOT Cleopatra)) OR (Caesar AND (NOT Antony AND NOT Cleopatra))
      • => *1 OR *2
      • => ((Brutus AND NOT Antony) OR ((Caesar AND NOT Antony) AND (Caesar AND NOT Cleopatra))) AND ((Brutus AND NOT Cleopatra) OR ((Caesar AND NOT Antony) AND (Caesar AND NOT Cleopatra)))
      • ...
    2. 元と比べて効率はどうか?
      • Brutus=x, Caesar=y, Antorny=z, Cleopatra=wとすると、元は (x+y)+(z+w)+(x+y+z+w) = 2(x+y+z+w)
      • 変形後は効率悪い?
    3. 展開せずにできるだけまとめた方がいいのかな?
  • どのクエリの順に処理したらいいか?
    • (kaleidoscope OR eyes), (tangerine OR trees), (marmalade OR skies)
  • NOTがついてるものはどういう順に処理するか?
    • 文書全体の数-(NOTのついてる語句の頻度)ではどう?
  • 結合クエリの場合、位置リストのサイズ順に処理するのが最適か?なぜか説明しろ、または反例をあげろ
    • 最適じゃないか?
  • 和集合演算を定義しろ
def union(p1, p2):
  answer = []
  i1 = i2 = 0
  while i1 < len(p1) and i2 < len(p2):
    if p1[i1] == p2[i2]:
      answer.append(p1[i1])
      i1 += 1
      i2 += 1
    else:
      if p1[i1] < p2[i2]:
        answer.append(p1[i1])
        i1 += 1
      else:
        answer.append(p2[i2])
        i2 += 1
  if i1 < len(p1): answer += p1[i1:]
  if i2 < len(p2): answer += p2[i2:]
  return answer
  • なぜ x AND NOT y をナイーブに評価すると高くつくのか?効率的な評価アルゴリズムを書け
    • NOT yが文書全体になってしまうから
def intersect_neg(p1, p2):
  answer = []
  i1 = i2 = 0
  while i1 < len(p1) and i2 < len(p2):
    if p1[i1] == p2[i2]:
      i1 += 1
      i2 += 1
    else:
      if p1[i1] < p2[i2]:
        answer.append(p1[i1])
        i1 += 1
      else:
        i2 += 1
  if i1 < len(p1): answer += p1[i1:]
  return answer
  • Pythonキモいよ〜
    • 配列の最後の要素はa[-1]で取れるとか。誰が見ても分かるのが特徴だったらこういう機能は入れない方がいいと思う。Rubyでもできるけど、Rubyはプログラマが楽するためだったら、という感じなので。
    • a[-100]とかだとエラーになる
    • a[i:i+n]とかすると部分リストが取れるけど、a[i:-1]だとi番目から最後の要素まで、じゃなくて最後の要素-1個めまで。最後の要素まではa[i:]。キモいよ〜。

1.2 逆インデクスの構築

A first take at building an inverted index

1.2 逆インデクスの構築

A first take at building an inverted index

  • まずインデクスを作る:
  • インデクスする文書を集める
    • "Friends, Romans, countrymen.", "So let it be with Caesar", ...
  • テキストをトークン化、各ドキュメントをトークンのリストに変換
    • Friends, Romans, countrymen, So, ...
  • 言語的なプリプロセス、トークンの正規化
    • friend, roman, countryman, so, ...
  • 文書をインデクスする
語句文書の頻度位置リスト
ambitious12
be12
brutus21,2
...
  • 文書の頻度(document frequency)は、基本的な2値サーチエンジンでは大したことないけど、クエリ時の効率を改善し、後でランク付けに使われる
  • 辞書はメモリに保持され、位置リストは通常ディスクに置かれる。なのでそれぞれのサイズは重要→5章でストレージとアクセス効率を最適化する
  • 位置リストの構造:固定長の配列は無駄。位置リストがメモリ上なら、単リンクリストや可変長配列。単リンクリストは挿入が容易、応用でスキップリスト(2.3節)。可変長配列のほうがスペース的にはよくて、連続領域へのアクセスもキャッシュが効いていい
    • ディスクに保存される場合、圧縮されポインタを取り除いた連続した位置にする。なので位置リストのサイズとディスクシークの回数が最小

演習:

  • 以下の文書集合の逆インデクスを描け:
  • 以下の文書について考察しろ:
  • 次のクエリの結果は?:
    • schizophrenia AND drug
    • for AND NOT(drug AND approach)
  • Pythonで
def build_inverted_index(docs):
  invidx = {}
  for i in range(len(docs)):
    for token in docs[i].split(' '):
      if token:
        if not token in invidx:
          invidx[token] = set()
        invidx[token].add(i)
  return invidx

def disp_inverted_index(invidx):
  for term in sorted(invidx.keys()):
    print term, ':', invidx[term]

def disp_matrix(invidx, num_of_docs):
  for term in sorted(invidx.keys()):
    print term, ':', str([x in invidx[term]
                          for x in range(0, num_of_docs)])

####

def exercise1():
  docs = [ '',  # for 1 origin
    'new home sales top forecasts',
    'home sales rise in july',
    'increase in home sales in july',
    'july new home sales rise',
  ]
  invidx = build_inverted_index(docs)
  disp_inverted_index(invidx)

def exercise2():
  docs = [ '',  # for 1 origin
    'breakthrough drug for schizophrenia',
    'new schizophrenia drug',
    'new approach for treatment of schizophrenia',
    'new hopes for schizophrenia patients',
  ]
  invidx = build_inverted_index(docs)
  disp_matrix(invidx, len(docs))
  print ''
  disp_inverted_index(invidx)
  return invidx

def exercise3(invidx):
  print 'schizophrenia AND drug:', invidx['schizophrenia'] & invidx['drug']
  print 'for AND NOT(drug OR approach):', invidx['for'] - (invidx['drug'] | invidx['approach'])

exercise1()
print '===='
invidx = exercise2()
print '===='
exercise3(invidx)
  • Python...
    • なんかあらゆることが直感的、直交してないように感じる…
    • リストの長さの取得が a.len() じゃなくて len(a) とか
    • a.sort()が破壊的、それでも戻り値で自分自身を返してくれれば for term in invidx.keys().sort(): とできるのに
      • 破壊的じゃないソートはsorted(a)
    • そもそも、リストといっても配列だとか

*1:Brutus AND NOT Antony) AND (Brutus AND NOT Cleopatra

*2:Caesar AND NOT Antony) AND (Caesar AND NOT Cleopatra