infosearch

03: 検索のためのテキスト処理

単語の出現頻度の分布は統計的性質に従う
検索モデルやランキングアルゴリズムは統計的性質を考慮した設計が必要
- ex. ) 重要な単語は，テキスト中の出現頻度が多いが，テキストの集合全体においては出現頻度は高くない

単語の出現頻度の分布は，一様でなく語彙による偏りが存在している
- the, ofは、全単語の出現数の1割を占める
- 一部の単語は突出して出現頻度が高いが多くの単語はめったに出現しない
Zipfの法則とは:
- 定数k ≒ ある単語の出現頻度f * 順位
  - 出現頻度が k 番目に大きい要素が、1位のものの頻度と比較して 1/k に比例するという経験則(ジップ分布)
  - ここでの順位とは、単語の出現頻度の多い順
- n回出現する単語の順位r(n)はk/nと推定できる
- 出現頻度がn回の単語数r(n)-r(n+1)はk/n(n+1)
- 出現頻度がn回の単語の出現割合は1/(k=n(n+1))
  - ex) 単語数500000で:
    - 出現1回の単語数はk=1*2=2として500000/2=250000(TRECで204357)
    - 出現2回の単語数はk=2*3=6として83333(67082)
    - 出現3回の単語数はk=3*4=12として41667(35083)

ヒット数を見積もりたい
クエリ”a b c”に対するヒット数f(a,b,c)=(Πf)/N^2
- 単純にa, b, cが独立で存在しているページを含んでしまう
- 共起確率がわかれば精度を高められる
途中まで順位付けした結果数からの推定
- 全てのクエリを含む文書C/順位付けされた文書の全体に占める割合s
２つの単語が独立と仮定しての推定
- f(word1) * f(word2) / f(word1∧word2)
- 実際は当然、推定より少ない

ストップワード
- それ自体意味を持たない機能語(冠詞，前置詞など)
- 高出現頻度がち(the, a, of)
- 検索には不要だしデータ容量も削減したいので除く
- 例外) to be or not to be
方法は標準的なストップワードリストを参照する
- しかしアプリケーションやドメイン、文書の種類によって差異がある
- すべての単語を索引語とし、どの単語を利用するかをクエリの処理の際に判断したい

単語の形態変化/活用を共通の語幹(基本形)に変換し正規化したい
- 索引語付けまたは，クエリ処理のタイミングで行う
- 言語によって効果に差がある(英語: 5~10%UP, アラブ系: 50%)
手法は:
- 関連語辞書ベース
- アルゴリズムベース
  - xxxs->xxx, yyyed->yyy
  - 単純な方法だと検出漏れや誤検出に
    - Porter Stemerの語幹生成
- 辞書+アルゴ
  - Krovetz Stemer(単語生成, 辞書になければ，アルゴリズムで接尾辞を除去)
  - 検出誤りは少ないが，検出漏れは多い．

クエリが慣用句や決まり言葉などのフレーズの場合を考えたい
- バラバラに検索するより1つの塊で検索したほうが良い
- クエリがフレーズかどうかを判定したい
  - 品詞タグ付け or N-gram or 近接性オペレータを

品詞タグ付けは大規模な文書集合には時間がかかりすぎる
フレーズはn語の単語列（N-グラム）
N-グラム（ある長さまで）を索引とすると高速な検索ができる
- しかし文書のサイズは肥大する(1000語1文書は2~5gramで約4倍に)
- データセット: Google N-gram

HTMLタグによる文書構造の解析
- ヘッダ，アンカーテキスト，強調されたテキスト
- メタデータ(head.meta)も重要．
- リンク
  - aタグ中のhrefとテキストノード(アンカーテキスト)

リンク解析アルゴリズムでウェブページの重要度を測る
被リンクで人気を測る(論文の被引用=IFと同じ)
リンクスパムのデータが弱点(無意味なサイトへのリンク)
Web上の各ページをグラフノードとし、その重要度を確率として表す
- あるWebページ集合でのページランクの和は1
- ページランクの値はそのページへアクセスする確率を表す

ページランクが採用しているWeb探索アルゴリズム
- 定数0<λ<1, r=rand[0,1]
- r<λ ? ランダムなページに飛ぶ : 現在ページのリンク先からランダムに進む
- これを繰り返す