infosearch

08: 検索モデル その２－確率モデル－

確率を利用したランキング

• Robertson (1977)
  • 「サーチエンジンが，データに基づき推定された適合性の確率が低くなる順番に文書をランクづけすれば，ユーザにとっての検索効果は最良となるだろう」
  • 情報検索は、適合文書とそうでない文書を分類するものである側面

テキスト分類

• 対象コーパス中の文書をクラスに分類したい
• 色々な応用が考えられる
  • 電子メールがスパムかどうか決定
    • 対象コーパス：電子メール
    • 分類クラス: スパムクラス or 非スパムクラス
  • ニュース記事を対象に，「スポーツ」「政治」といった分野の中から属する分野を決定
    • 対象コーパス：ニュース記事
    • 分類クラス（多値分類）: スポーツ,政治,科学,…

ナイーブベイズモデル

• 単純な確率的生成モデルを利用した分類器

利点

• 確率値を出力
• 理論，実装が簡単
• 問題によっては高い分類精度
• 学習は非常に効率的
• 分類も高速
• 半教師あり学習に簡単に拡張可能

欠点

• 属性間の条件付独立性を仮定
  • 依存関係のある複数の素性の効果を独立に扱ってしまう
  • 複数回定型句が登場すると効果はそのたびに倍になるお
• クラスにおける出現確率がゼロのものをかけるとゼロになってしまう
  • 確率が0とならない工夫

ベイズ分類

• クラスx, 文書dがあるとき文書dが属する確率P(c

  d)が最大となるクラスcを求めたい

  • ベイズの定理を適応できる
  • P(c|d) = P(c)* P(d|c)/ P(d)
  • P(c)*P(d|c) = P(c) * Π P(w∈{V(d)},c) * Π(1-p(w∈{V-V(d)},c))
    • ΠP(w,c)はあるクラスCに単語wを含む文書が出現する確率の全単語についての総積

ネガポジ分類

• 肯定意見クラス：
  • d1: good bad
  • d2: exciting
  • d3: good exciting boring
• 否定意見クラス：
  • d4: bad boring
  • d5: bad good
  • d6: bad boring exciting
• クラスごとの各単語の出現確率(多項分布と呼ぶ)
  • P(bad, 肯定)=1/3，P(bad，否定)=3/3
  • P(boring, 肯定)=1/3，P(boring，否定)=2/3
  • P(exciting, 肯定)=2/3，P(exciting，否定)=1/3
  • P(good, 肯定)=2/3，P(good，否定)=1/3
  • d7: good bad boringは肯定意見？否定意見？
    • V={bad, boring, exciting, good}
    • V(d)={good, bad, boring}
    • V-V(d)={exciting}

    • P(肯定)*(d7

      肯定)=3/6 * (1/31/32/3) * (1-2/3)=23/(23^5)=1/3^4=.01234…

    • P(否定)*P(d7

      否定)=3/6* (3/32/31/3) * (1-1/3)=(3^22^2)/(23^5)=2/3^3=.07407…

    • d7は否定

NLTK

• 自然言語ツールキット
  • ペンシルバニア大学において，計算言語学コースの教材として作成
  • 自然言語処理の教育に広く使われている
  • Python のモジュール集合として実装されている
  • コーパス分析，品詞タグ付，テキスト分類，構文解析など

import random
from typing import Any, Dict, List, Literal, Tuple, Union

import nltk

try:
    nltk.data.find('corpora/movie_reviews')
except LookupError:
    nltk.download('movie_reviews')

from nltk.corpus import movie_reviews as mr

MR_ALL_WORDS = nltk.FreqDist(w.lower()
                             for w in mr.words())
WORD_FEATURES = list(MR_ALL_WORDS.keys())[:2000]


def doc_features(doc) -> Dict[str, bool]:
    """素性抽出器"""
    doc_words = set(doc)
    features = {}
    for w in WORD_FEATURES:
        features['contains(%s)' % w] = w in doc_words
    return features


AccResults = Tuple[Union[Any, float, Literal[0]],
                   nltk.NaiveBayesClassifier]


def cal_accuracy(docs: List[Tuple[list, str]]) -> AccResults:
    """正解率計算"""
    feat_sets = [(doc_features(d), c) for d, c in docs]
    train_set, time_set = feat_sets[100:], feat_sets[:100]
    classifier = nltk.NaiveBayesClassifier.train(train_set)
    return (nltk.classify.accuracy(classifier, time_set), classifier,)


def main() -> None:
    docs = [(list(mr.words(id_)), category,)
            for category in mr.categories()
            for id_ in mr.fileids(category)]
    random.shuffle(docs)
    acc, clsfier = cal_accuracy(docs)
    print("Accuracy:", acc)
    clsfier.show_most_informative_features(5)


if __name__ == '__main__':
    main()

ベイズ分類

• ベイズの決定規則
  • 文書Dが適合している確率P(R|D)>文書Dが不適合の確率P(NR|D)なら文書Dは適合
  • P(R|D)=P(D|R)P(R)/P(D)

P(D|R)の推定

• P(D|R)=ΠP(d(i)|R)
  • P(d(i)|R)は単語iの適合文書中の出現確率
  • d(i)=D∋単語i ? 1 : 0

二項独立モデル

• 簡単な仮定をおくことで，文書/クエリの類似性確率の推定を可能にする確率的情報検索手法
• 文書は単語の出現/非出現の2値のベクトルで表現できる

BM25

• 二項独立モデルに基づくランキングアルゴリズムのうちよく使われ効果的なやつ
  • 検索エンジンがクエリとの関連性に応じてランク付け
• score(D,Q)=〈クエリの各単語IDF ･ {(Dにおけるqiの出現頻度･k++)/(Dにおけるqiの出現頻度 + k･(1-b+b･文書サイズの平均))}〉の総和
  • k=1,2~2.0, b=0.75がよく使われる値

言語モデル

• 文書あるいはクエリ中のトピック（話題）は，言語モデルとして表現できる
  • 1-gram言語モデル
    • ある言語の単語集合に関する確率分布
    • テキストは確率分布に応じて単語を選択して構成

Web 検索と機械学習による検索モデル