1/19 知能システム論第13回ノート
- 1/26 試験
- 40分くらい遅刻！
- 前半はCKYとかPCFGとかの話？
- 検索についての話
- 転置インデックス
- 単語が出てきた文書のインデックスを全部覚えておく
- Dictionary<string, List<int>>
- クエリ：おいしい or 食べた -> {2, 5} U {1, 2, 3} = {2}
- andやorも簡単に求められる
- 接尾辞配列
- 転置インデックスは単語区切りが必要なので、単語区切りをしない場合は使えない
- 単語区切りの間違いが困る場合
- 単語以外の文字列を検索したい場合
- 接尾辞配列
- 各位置から後ろの文字列をソートした配列
- テキスト中の任意の文字列を効率的に検索可能
- 例
- abracadabra
- すべての接尾辞とそれが登場した位置を対応付け、接尾辞を辞書順にソートする
- a => 10
- abra => 7
- abracaddabra => 0
- acadabra => 3
- adabra => 5
- ・・・
- racadabra => 2
- 検索コスト：O(logN)
- 配列作成コスト：O(NlogN)やO(N)のアルゴリズムが知られている
- ランキング
- マッチしたテキストを列挙するだけでなく、ユーザがほしそうなテキストを出力したい
- テキストにランキングを付けて出力する
- ランキングの２つの側面
- クエリとマッチしている度合
- テキストの重要度
- 「マイクロソフト」で検索
- マイクロソフトファンの個人ページより、マイクロソフト社のホームページがほしい
- ヒューリスティック？
- ベクトル空間モデル
- テキストの近さを計算するためのモデル
- 文書ベクトル：テキストをベクトルで表す
- ベクトルの類似度
- テキストの近さ＝ベクトルの近さ
- 検索だけでなくテキスト間の近さを図るときの有効
- ストップワード
- 多くのテキストに含まれる単語は検索にとって邪魔
- 「私」「思います」とかを検索する人は（あまり）いない
- ベクトル空間モデルだと、そのような単語がたくさん含まれるテキストが上位にランクされてしまう
- 検索に不要な単語をあらかじめ指定し、クエリ・検索対象から除外
- 主に機能語（助詞・接続詞）や一般的すぎる単語（私・昨日など）
- 昔の検索エンジンはこれ使ってた。今はさすがに使ってない
- 重みづけ
- 「おいしい 白桃」というキーワードのとき、「おいしい」と「白桃」のどちらが重要か
- 白桃 ＞ おいしい
- tf-idf
- 文書ベクトルの重みづけによくつかわれる手法
- ぶんしょdでの単語wの重み：
- tfidf(w, d) = tf(w, d) / df(w)
- tf(w, d):文書dでのwの頻度（ターム頻度）. term frequency ?
- df(w)：単語wが出てくる文書の数（文書頻度）. document frequency ?
- 直感的には珍しい単語の重みが大きくなる
- 普遍的な単語の重みは小さくなる（ストップワードの同様の効果）
- リンク解析
- ウェブページはお互いにリンクを張っている
- 重要なページとは？
- 多くの人から支持されているテキスト
- リンクを集めているウェブページ（インリンク・バックリンク）
- ページランク
- ランダムウォーク：リンクをランダムに歩く
- ページランク＝ランダムウォークしたとき、それぞれのページに到達する確率
- 遷移確率p[i, j]:ページiからページjにたどる確率
- 遷移確率行列P = (p[i, j])
- 各ページへの到達確率をｑとするとq∝Pq（不動点を求めたい）
- つまり、Pの固有ベクトルを求めればよい
- ページiのスコア：σ[i]
- ページiのインリンクのスコア：a[1], …, a[n]
- ページiのアウトリンクのスコア：b[1], …, b[m]
- σ[i] = Σaj = Σb[k], b[k] = σ[i] / m
- ページのスコア：インリンクのスコアの和＝アウトリンクのスコアの和
- 特徴
- インリンクが多い->ページのスコアが高い
- ページのスコアが高い->アウトリンクのスコアが高い
- アンカーテキスト
- リンク先をそのリンクの「意味」と考えると、アンカーテキストはその意味を指す「表現」
- アンカーテキストはユーザの要求を表す強い手がかり
- リンク解析の利用
- ウェブ検索以外にも、いろいろなネットワークの解析に使われている
- 論文のランキング（参考文献リストを使う）
- ブログ・ツイッターで有名人を見つける
- コミュニティの発見
- ランク学習
- 機械学習を適用してランキングする
- 学習データ
- アルバイトにお願いして検索結果にランキングをつけてもらう
- クリックスルーログ
- 人間が決めたランキングを再現するようなモデルを学習する
- ランク学習の手法
- 特長べく取りに変換、その関数としてランキングを定義
- ランク学習＝学習データを使って、適切なランキングを出力するような関数を学習する
- どのようにランキングを表すかはいろいろ
- スコアを出力->スコア順に並べる（cf：回帰分析）
- 並び順を直接出力
- いろいろな目的関数->いろいろなランク学習
- 特徴ベクトルをどうするか