概要

情報検索 :検索エンジンの実装と評価を勉強会でやった時の自分用メモ。

目次

Part 1 基礎

1 イントロダクション
2 基本技術
3 トークンとターム

Part 2 インデクシング

4 静的転置インデックス
5 クエリ処理
6 インデックス圧縮
7 動的転置インデックス

Part 3検索とランキング

8 確率的情報検索
9 言語モデルと関連分野
10 分類とフィルタ
11 融合・メタ機械学習

Part 4評価

12 有効性の評価
13 効率の評価

Part 5大規模情報検索システムの構築方法

14 並列情報検索
15 Web検索
16 XML検索

メモ

2.1 転置インデックス

辞書 → コレクション中の語彙 V に含まれるタームを並べた部分
ポスティングリスト → 対応するタームの出現場所を示す番号
スキーマ非依存型インデックス
- フラットな番号が振られているだけのインデックス
- 最もシンプルな構造
4つのメソッド
- first(t) タームtが最初に出現する位置を返す
- last(t) タームtが最後に出現する位置を返す
- next(t, current) タームtが位置currentより後で最初に出現する位置を返す
- prev(t, current) タームtが位置currentより前で最後に出現する位置を返す
シーケンシャルアクセスと非シーケンシャルアクセス

💡 **メモ**

多分僕らが想像する転置インデックスとは異なる構造が出てきている
ちなみに類似画像検索でも転置インデックスは用いられる
- 局所特徴量がタームに相当する

2.1.1: 技術的な拡張: フレーズ検索

"first witch"のような検索のこと
nextPhraseの特徴
- 再帰関数
- 12行目で渡しているのはvではなく、u
- 一回のnextPhraseの呼び出しでO(n)のnextとprevメソッドの呼び出しが発生
- 最悪のケースでメソッドの呼び出し回数はO(nl)(ただし、lは各タームの最小のポスティングリストの長さ)
- 実際は適応的特性がある
  - 扱うデータの特性に依存する
- 9行目で得られる区間[u, v]のことを候補とし、κをコレクション中の数とすると、メソッドの呼び出し回数はO(nκ)となる

2.1.2: 転置インデックスの実装

next()やprev()をどのように実装すべきかの話

バイナリサーチによる実装
- next()の計算量はO(logL)
- nextPhraseメソッドがどのような計算量になるか
  - 出現回数の多いタームと少ないタームがあると効率は良くなる
  - nl回のnext()とprev()の呼び出しがあるので
  - 最悪計算量はO(nllogL)
シーケンシャルスキャンによる実装
- nextPhraseメソッドのcurrentは順に増加している
- 主なアイデアは「キャッシュしようよ！」というもの
- nextPhraseメソッドがどのような計算量になるか
  - 全てのタームが同じくらいの場合に適している
  - 最悪ケースでポスティングリストを全てスキャンし、タームがn個あるので
  - 最悪計算量はO(nL)
ギャロップサーチによる実装
- バイナリサーチの良さ（O(logL)に抑えられる）とシーケンシャルスキャンの良さ（キャッシュする）を組み合わせる
- nextPhraseメソッドがどのような計算量になるか
  - O(nllog(L/l))
  - l << Lの時はバイナリサーチと同様
  - l ≒ Lの時はシーケンシャルスキャンと同様
    - え、そうなの？
    - log1って0やけど
      - log(L/l)が定数となるから計算量はO(nL)

💡 **メモ**

計算量の算出ロジックが凝ってる
- キャッシュが出てくるとやっぱりとたんに複雑になってる

2.1.3: 検索の区切り

IRシステムやアルゴリズムは検索対象としてドキュメントを単位としている
- アプリケーションによってドキュメントって違ってくるよね
- 多くのアプリケーションではドキュメントの定義は明白
軽量な構造が必要になる状況が頻繁にある
- 何が言いたいのかよくわからなかった
- 軽量な構造がよく必要になるのに、ドキュメントを検索するという話だけしていればいいのは何故なのか
- 5章で詳しくやるらしい
ドキュメント指向インデックス
- ドキュメントを中心に添えて効率化したインデックス
スキーマ依存型転置インデックス
- 転置インデックスを作成する際にテキストの検索単位（スキーマ）への分割が決定される
- 通常はドキュメント指向の統計量を保持
- 以下のメソッドをADTに追加
  - docid(position)
  - offset(position)
  - firstDoc(t)
  - lastDoc(t)
  - nextDoc(t, current)
  - prevDoc(t, current)
1. ドキュメント番号インデックス
  - それぞれのタームについて、出現するドキュメント番号
  - 最もシンプルで最小のデータ量になる
2. 頻度インデックス
  - それぞれのタームについて、ドキュメント番号とターム頻度
3. ポジションインデックス
  - それぞれのタームについて、ドキュメント番号とターム頻度とオフセットを記録
  - 4つのインデックスで最大のデータ量
スキーマ非依存型転置インデックス
- 検索時にドキュメントを定義
- ドキュメント指向の最適化は行われないが、それ以外ではポジションインデックスと同様の応用が可能

2.2検索とランキング

論理検索とランキング検索
- 商用web検索エンジンは2段階の実装（論理検索で絞り込んでから、ランキングをつける）
- 関連するページであっても、検索タームを一つでも含まれないページは検索結果が除かれてしまうと、検索タームをクエリに付け加えていくと検索結果が悪くなるというパラドックス的な問題が起こる
ランキング手法の特徴量
- ターム頻度
- ターム近接度
- ドキュメント頻度
- ドキュメントの長さ
- ドキュメント構造
- 静的なランキング
- userのアクティビティ（clickログの利用）

💡 **メモ・余談**

userのアクティビティはかなり効くらしい
- https://www.wantedly.com/companies/wantedly/post_articles/169261

2.2.1 ベクトル空間モデル

ドキュメントとクエリをベクトル化し、二つのベクトルのなす角度が小さいほど関連度が高いと考える
コサイン類似度
TF-IDF
- 面白かった点
- TF関数はf_{t,d}について、必ずしも線形である必要はないということ
- https://ja.wikipedia.org/wiki/Tf-idf は線形
TF-IDFが「ドキュメントの長さ」と「ターム近接度」を使ってない。この特性を補うためにbag of wordsというベクトル空間モデルが考案された
- そうなの？？
- 謎

2.2.2 近接度ランキング

誤植多い？
- 71pの「1行目では、タームベクトルの要素のすべて含む最小の区間[position, v]を決定する」
  - 最小ではなく最大？
  - vが最小という意味
- 図2.11の1行目は∞ではなく、-∞では？
rankProximity()の計算量について
- なぜO(n^2llog(L/l))？
  - カバーの数だけnextCover()が呼び出される
  - カバーの数のオーダーはO(nl)
  - nextCover()はO(n)のnext()およびprev()の呼び出しがある
  - next()およびprev()の呼び出し回数はO(n^2*l)となる
  - ギャロッピングサーチで実装すればnext()をl回を呼び出した時の計算量はO(l*log(L/l))
  - よって、O(n^2llog(L/l))

2.2.3 論理検索

ランキングリストではなく、ドキュメント集合を返す
タームtはそのタームを含むドキュメントを指定するための条件として使われる
nextSolution()の計算量について
- O(nl)オーダーのnextDoc()の呼び出し
- nextDoc()はl回の呼び出しで、ギャロッピングサーチならO(l*log(L/l))
- よってO(nllog(L/l))
docRight(NOT t,u)
- どういう挙動なの、、
- u, (tを含まないdoc), (tを含むdoc)
  - ってあったらu+1が答えになるのではないか？

2.3.1 再現率と適合率

recall, precistion, F値の定義

2.3.2 ランキング検索の有効性評価

平均適合率
- PR曲線と軸が囲む面積
  - relavance(i)という関数が無ければそうだと思うが、switchする関数があるので、そうはならない気がする
ベクトルの正規化はそれぞれのドキュメントの長さが異なる時は、ドキュメントの長さがうまく反映できず、うまくいかない

💡 **メモ・余談**

平均適合率
- 物体検出でよく評価される指標で、その時は補間されて、再現率が[0, 0.1, 0.2,...,1.0]の時の適合率を使って、平均適合率としていることが多い
- こちらはちゃんと囲む面積になっている（2.23でrelavance(i)がない）

2.3.3 試験用コレクションの構築

よく分からず

2.3.4 効率の評価

応答時間
- ユーザーがクエリを入力してから結果を得るまでの時間
スループット
- 一定の時間内に処理できるクエリ数
平均応答時間
- クエリ集合のすべてのクエリを実行し、かかった時間をクエリの総数で割ったもの
- ディスクアクセスやネットワークの転送時間が無視できなくなる可能性があるので、得られた結果は破棄する
- 実行の前に検索システムをリスタートする
  - メモリをリセットするため

2.5 さらに学習を進めるために

転置インデックスは柔軟性と一般性を持っていて、他の手法を圧倒した
- シグネチャファイル
  - フィルタ検索に使えるが、間違う可能性あり
  - フレーズ検索やランキング検索に応用しづらい
- 接尾辞木
  - ランキング検索に向いてない
ベクトル空間モデル
- 長い間IRに影響を与えた

3 トークンとターム

トークンの定義について
- 情報検索第一章: イントロダクションでは「トークンには位置情報がある」としているがこれは正しいのか
- 「語彙Vの中にあるのはターム（これはクラスっぽい）、実際にドキュメントに出てくるのがトークン（これはインスタンスっぽい）」
トークン化
- ドキュメントを語に切り分けること

3.1 英語

3.1.1 句読法と大文字

結局句読法に対する良いアプローチはなんなのか？
- なんかスルーされてるような気がしている
大文字に対しては二重インデックスが機能することは理解した

3.1.2 語幹抽出

語幹抽出と見出し語化の違いはなに？
- 見出し語化は結果で、howの部分が語幹抽出
語幹抽出は再現率を上げてくれるので、基本的には良い改善となる

3.1.3 ストップワード

機能語は高い近接度を示しがちなので、クエリに必要ない
- 機能語はストップワードになる
- 最後のまとめ「検索ターム間の近接度を考慮しないランキングでは、ストップワードを削除しても構わない。検索ターム間の近接度を考慮するランキングでは特にフレーズでの出現を検索する場合には、ストップワードを維持するのが適切である」

3.2 文字エンコーディング

多くのドキュメントがUnicode以外でエンコードされているが、これらはUnicoeeへの変換を行ってから処理することができる
- これはUnicodeに対応してない文字コード（shift jisとか）Unicode対応文字コード（UTF-8とか）に変換できるよってこと？
  - Unicodeはjis規格から持ってきてるので、ある程度同じだと思われるから、変換も簡単そう

3.3 Nグラム法

Nグラムの効用は言語によって様々

💡 **メモ**

subwordという概念がNLPではよく出てきます
- https://qiita.com/taku910/items/7e52f1e58d0ea6e7859c

3.4 その他のヨーロッパ言語

区別的発音記号は英語にはない
- アクセント記号を排除し同一のタームとして扱う
- 二重インデックス
- 対応する言語の細部にわたる詳細とIRシステムの応用分野に依存した解決方法
名詞の結合
複数の言語が存在するIRシステム

3.5 CJK言語

日本語
- ある文字セットで書かれたクエリは他の文字セットで書かれたドキュメント内タームにもマッチする必要がある
中国語
- 文字セットは2つ
- 分割が困難
- 2グラムでのインデックスが良い性能を示す
- ピンインを使っても曖昧さが存在している

3.6 さらに学習を進めるために

ロブ・ピケ、、、
この章での話はトークン化の話
- 語幹抽出
- Nグラム
- コスト関数を使った分割法
- クラスタリングを使う手法
スペル訂正

4 静的転置インデックス

ほとんどのデータがハードディスクに格納され、その一部分がメモリに格納されている構成

4.1 インデックスの構成要素とライフサイクル

構造的な視点
- 辞書とポスティングリスト
- データ構造をどうするべきか的な視点かな？
動作的な視点
- インデックス作成とクエリ処理
- どういう風に使われるか的な視点かな？

4.2 辞書

ソート配列辞書
- 文字列辞書
  - これどうやって使うんだろう？って思った（任意のタームが与えられてどう効率的に処理する？）
- 探索木
ハッシュ辞書
- linked listを用いるチェイン法
基本ハッシュ辞書の方が早い
ターム数が小さいとなぜハッシュテーブルのサイズが大きくなると遅くなる？（CPUキャッシュがどのように動作してるのか）
- 2^18だとCPUのキャッシュに全部入ってる可能性さえある
接頭辞クエリの計算量でO(m)はなぜ必要？
- 最初と最後のタームさえ分かればいいのではないか？（チェックでもしてるのか？）
- 「inform」でバイナリサーチして、「inforn」でバイナリサーチして、間のタームをシーケンシャルスキャンで得るから
インデックス作成時には検索スピードが早くないといけない
- なぜなのかがよく分かってない
  - 単語が1万個あるドキュメントを追加するときは辞書を10000回引く必要がある

4.3 ポスティングリスト

ディスクのどこに格納するかというのが重要になってくる
パータームインデックス
- 直接バイナリサーチでやるよりも処理時間が大幅に短縮できる
- 圧縮したポスティングリストを扱えること
接頭辞クエリ
- ちゃんとソートしてディスクに格納せよ
個別ポジションインデックス
- (doc_id, position)のデータと(doc_id, term_frequency)のデータを分けることによりディスクアクセスを低減できる

4.4 インターリービング辞書とポスティングリスト

タームとポスティングリスト
- 複合主キーのようなイメージ
  - (term, posting, diskへのポインター)を保持している
- 欠点について
  - 複合主キーのようなものなので、使用するメモリーの量が増える

前回の疑問

インターリービング辞書+パータームインデックス
- 最悪ケースで3回（ブロックサイズの読み込み→パータームインデックスの読み込み→欲しいデータ）のディスクアクセス
最後のターム+ポスティングをメモリにもつ場合
- 1回の読み込みで十分だと思った
- パータームインデックスに相当する情報はメモリ上に存在しているため
- でも本文中には「ただし、パータームインデックスを主記憶メモリに読み込むための時間は考慮していない」とあるが、この方法でもパータームインデックスは必要なのか？
- そう信じてこれからの人生を歩む

4.5 インデックスの作成

インデックス作成はタプルの再配置の問題
- コレクション中でのタームの順番→タームを基礎とした順序
インデックスの作成手法
- インメモリインデックス
- ディスクベースインデックス
この本で出てきた、ディスクへの格納の仕方のフォーマットは基本的には同一なのか？
- 4.4までではインデックスの活用の方法が述べられていた
- その活用方法を考えると、基本的にはディスクへの格納方法は一緒だと思った
- 例えばインターリーグング辞書を使わないからディスクへの格納のフォーマットが異なる、みたいなことはあり得るのか？
  - yes

4.5.1 インメモリインデックス

4.2の辞書のデータ構造（文字列辞書、ハッシュテーブル）とは多分違う
- 4.2のデータ構造は最終的にディスク上のポスティングリストへのポインターを持っていたが、インデックス作成時にはディスク上にポスティングリストは存在してない
今回出てくる二分探索木やハッシュテーブルはメモリ上のポスティングリストへのポインターを保持しているんだよね？
ジップの法則の活用
- ハッシュテーブルのチェインの追加方法をどうするか
  - よく出てくるタームをチェインの前の方に置きたい
- 「新しいタームを後方に挿入していく」のと「後方挿入+前に移動」するのが早くて良い
- 特に「前方移動」が良さそう
- ちなみにC++言語のライブラリだと先頭挿入らしく、これは今回の用途には向いてない
ポスティングリスト
- 単方向linked listで実装する
  - このとき増加量に幅があるのはなぜだろう？
    - OSやコレクションの大小というパラメータがある
  - メモリ消費量が大きいというデメリットがある
- 2パスインデックス
  - 時間がかかる
- realloc
  - 足りなくなったら動的に割り当てる
  - reallocの実行回数がポスティングリストのサイズに対して対数的に減少する
    - これは導出できるもの？
    - できる
    - 2,4,8,16みたいな感じで配列のサイズが増加していくから
- linked list(グルーピング)
  - 速度はシンプルなlinked listよりも高速
  - 理由は「CPUキャッシュが効率よく動作すること」と「内部断片が少ないこと」
    - 内部断片が少ないことはどう速度に影響する？（結局CPUキャッシュに関係してくる気がするが）
    - 「内部断片が少ないこと」はおそらくreallocとの比較ではないか？
- 実際にはOSの機能（ハッシュテーブルのエントリー数の調整やメモリのallocateなど）を使った方がいい可能性もある
4.5.2 分類インデックス
- 順番通りの(term_id, position)→タームごとでソートされたデータが欲しい
- まずは適当に分割して小さなソートを実施し、それからマルチウェイマージ or カスケードマージという手法でまとめていく
  - これらの手法の詳細が分からないが、全てのデータをメモリに載せずにソートが可能なのか？（最後の方のソートはものすごく巨大なデータ量になりそうだが、、）
  - 可能そう。RDBが巨大なデータをソートするときに使うっぽい
- デメリット
  - 小さなソートの結果をディスクに格納するので、大量のディスク容量が必要となる
  - タームIDがグローバルな変数である必要があり、辞書全体がメモリに乗っている必要がある（インターリービング辞書はだめってこと？）
    - 結果としてメモリが多く必要
4.5.3 統合型インデックス
- 図4.13の擬似コードについて
  - $I_{K}$は全てメモリに乗るという前提？
    - これは全部のる前提ではなさそう
    - 先読みバッファ分は全部のインデックスで乗りそう
  - heapの話について
    - 7~11行目は一番小さいタームを取得している。これをheapを使えば簡単にできる、ということを言ってそう
- 先読みバッファ
  - これは非同期に先読みしているということ？
  - 不明
- 主記憶メモリに対してセンシティブ
  - メモリが減ると
    - 部分インデックスの数が増加
    - 先読みバッファのメモリ量が減少
  - 対策は2つ
    - マルチウェイマージの代わりにカスケードマージを使う
    - ポスティングリストを圧縮することにより作成する部分インデックスの数を減らす
- ソートインデックスに対して優れている点
  - ソートインデックス=分類インデックスだと思われる
    - 図4.10がbuildIndex_sortBasedになっているため
  - タームIDをグローバル変数にしなくても良い点
  - 直ちにクエリにも応答できる点
    - ソートインデックスも応答できるのではないか？
    - 7章を見れば分かるでしょう

5. クエリ処理

大規模な検索エンジンでもデスクトップの検索エンジンでも基本的な考え方とアルゴリズムは同じ
検索モデル
- 論理検索
- ランキング検索
- 軽快な実装

5.1 ランキングのためのクエリ処理

基本ORでつなげていく
- 関連するタームをクエリに付け加えることによって、検索結果を悪化してはならないという立場
- ANDで繋げるよりも再現率は良い
- ただしスコアリングするドキュメントの数は増えるので速度は遅くなる
Okapi BM25
- k_1の値でTFの上限を抑えることができる
- クエリタームが一つだけ出現するドキュメントより、二つの異なったクエリタームが出現するドキュメントの方がはるかに高いスコアを得ることができる

5.1.1 ドキュメントごとクエリ処理

計算量はO(mn + mlog(m))
問題点
- クエリタームの全てが、それらが現在処理中のドキュメントに出現しているかどうかに関わらず、出現している
- 上位k個のみに興味があるので、全部をソートする必要はない
ヒープ
- 配列で表現可能
- (a)でちゃんと配列に入れれて、(b)で最後の方の要素の並びがfixするというイメージ？
ヒープによる効率的なクエリ処理
- ドキュメントごとに必要なクエリタームについてのみ計算する
- 上位k個のみをヒープの要素として保持
MAXSCORE
- 連言検索と比べると1桁多くのドキュメントのスコアを計算しなければならない
- クエリあたりの平均CPU時間は50%しか増加していない
  - なぜ？
  - MAXSCOREを使ってないANDの方は式5.12になって、MAXSCOREの方は式5.12にtermsヒープから削除されたタームのscoreを追加する処理が追加されそう（だが、これはあんまり変わらない気がするが、高速化の理由とは思えない）
    - 不明

5.1.2 タームごとクエリ処理

ドキュメントごとのクエリ処理だとクエリタームのポスティングリストがメモリ上に展開されていることが要求されるので、先読みバッファが十分に確保できなければ、ディスクへのアクセス回数が増える
タームごとのクエリ処理だと、タームごとにスコアを計算していって、前回までの結果に積算していくので、同時に多くのタームを処理する必要がなくなる
図5.4について
- なぜ二つ必要？
- acc[inPos]って何が帰ってくるの？→ 多分doc_id
- accを配列からハッシュテーブルに置き換えることでO(N_q* n + N_q * log(k))からO(N_q + N_q * log(k))になるのはなぜ？
閾値を使うアプローチについて
- 第一段階では全ポスティングのスコア寄与度を採点し、ソートして閾値を得る
- 第二段階では再度スコアリングして閾値と比較
- tfStatsらへんは何をしているのか

5.1.3 スコアの予備計算

スコアの事前計算をしてインデックスに保持しておけば計算が高速化できる
- ただし、スコアに割り当てるビット数を増大させていくと、ディスクI/Oが増加し、計算が逆に遅くなる

5.1.4 影響度順並べ替え

2^B個の区分に分けるアプローチ
- アクセスの最悪計算量は2^B倍になるのか？
- 定数倍だから良いのでは？

5.1.5 静的インデックスの刈込

多くのポスティングがスコアに全く寄与しないとしても、検索エンジンはそれらの大部分を読み出して解凍し、スコアへの寄与をもつポスティングにアクセスしなければならない
- a_maxを超えるか超えないかのループの時の話？
静的インデックスの刈込
- ポスティングの重要度を予測し、検索処理において重要な役割を持たないと考えられるポスティングをあらかじめ削除する
- 欠点
  - 上位ドキュメントを検索できるという保証がない
  - フレーズクエリには対応できない
- 後の袋処理（式5.16）とは相性が良いとのこと
- ターム中心刈り込み
  - タームのポスティングから考えていく
- ドキュメント中心刈り込み
  - ドキュメントから考えていく
ターム中心刈り込み
- L_tの全てのポスティングを選んだスコア関数によるスコア寄与度順に並び替え、上位K_tポスティングをインデックス内容とするために残し、その他のL_t上の要素を全て破棄する
  - BM25だとf_(t,d)順ってこと？
- εでK位以下のポスティングについて、どれだけ借り込むかを決める
ドキュメント中心刈込
- query expansionのこと言ってる、、
- 擬似適合性フィードバックによって選択されたタームが、最初のクエリに含まれているタームと一致することは頻繁に起こる。したがってインデックス作成時において、各ドキュメントごとにクエリとは独立な擬似適合性フィードバックアルゴリズムを実行することが考えられる。これによって各ドキュメントが高スコアを得やすいタームを選んでおく
  - query expansionを活用して、ドキュメント刈り込みを行うということ？
  - 意味わからない、、
- KL divergenceを使ったドキュメント刈り込み
  - 検索エンジンが実行するスコア関数とは独立
パフォーマンス差について
- どういうことだろう？
- ドキュメント刈り込みだとタームを減らすわけではないが、ターム刈り込みだとポスティングリストが減少する
- 結果、ドキュメント刈り込みだとポスティングリストが長めになって、計算時間が増大するのでは？
正当性の保証
- ターム中心刈り込みの閾値を使って、推定される最大値を使ってとりあえずの結果を出せる
- 図5.11
  - 二段階クエリ処理アーキテクチャ
    - 刈り込まれた可能性がある場合、オリジナルインデックスを使うのであれば、ドキュメント中心刈り込みでもできるのではないか？（どうせもう一回オリジナルで計算するから）
    - k=10の時に10位と11位のさを考えた時に、安心してこの順いで良いというためにはv_tが必要となるため

5.2 軽快な実装

領域台数
- 第二章のADTの拡張
- これでフレーズ検索や論理検索を統一的なメソッドを使って記述できるようになる

5.2.3 例

色んなクエリや要求が領域代数の演算子を使って表現できるよ

5.2.4 実装

領域代数の演算子のためには4つのメソッドを定義すればよい
領域代数を使えば画面遷移の情報をうまく読み取れるのではないか

5.3 さらに学習を進めるために

領域代数は1990年代中盤のYahoo!の検索サービス機能を提供

7. 動的転置インデックス

動的テキストコレクション
1. 挿入
2. 削除
3. 編集
- が可能
インデックス保守戦略
- データが変動するという性質を考慮しながら、テキストコレクションとインデックスの内容が一致している状態を保つ必要がある
半静的テキストコレクション
- 挿入・削除が可能（＝編集も可能）
- 変更内容は少々遅延しても良い
増分テキストコレクション
- ドキュメントの追加は可能だが、変更・削除はできない
- 高い頻度でドキュメントが更新される場合でも、インデックスを最新の状態に保つことができる
非増分テキストコレクション
- 挿入・削除・編集に対応
- 遅延削除
  - 削除のマークをつけておいて、ガベージコレクションでインデックスの整理と不要なポスティングの削除を行う
  - postgreSQLみたいな戦略
- 変更がインデックスにどのような変更を及ぼすのか
  - 一般的な検索エンジンがドキュメントの直接的な変更に対応しておらず、ドキュメントを削除と再挿入の組み合わせで処理しているかの理由

7.1 バッチの更新

バッチ更新
- REBUILD
  - ゼロからインデックスを構築
- REMERGE
  - 統合インデックス構築
REBUILDとREMERGEの比較
- 以下の仮定を置く
  - 統合インデックス処理で、削除されたポスティングを解放する時間は無視できる
  - 挿入と削除の数が等しい
- 全ドキュメントの60%以上が削除され、かつそれらのドキュメントが新しいインデックスに現れない場合、REBUILDはREMERGEよりも効率的となる
  - この言い方何だろう？
  - 「それらのドキュメントが新しいインデックスに現れない場合」ってわざわざいう必要ある？
  - 分からない
- ほとんどの場合REMERGEの方が良い
  - バッチ更新間における相対的な削除数は60%よりもずっと少ない
    - 削除されたドキュメントばかりになるとUXが下がるため、頻繁なインデックス更新を行うため
- 統合インデックスの処理は基本的にはインデックスを作成する時点で必要となるため、REMERGEに特別な処理は必要ない
  - ドキュメントの削除をケアする必要はある

7.2 増分インデックスの更新

NO MERGEインデックス更新戦略
- 合計mn回のディスクへのランダムアクセスを要する
  - これは「タームのポスティングの結合」の話にあったデータ構造がメモリにあるのが前提となっている？
    - 複合主キーではなくても、別のデータ構造でもディスクへの一回アクセスは実現可能だろう

7.2.1 連続的転置リスト

IMMEDIATE MERGE
- インデクサがメモリを使い果たすたびにディスク上のインデックスとメモリ上のインデックスをマージする
- こうすることによって、ディスクへのアクセス回数を減らすことができる
- だが、インデックスの更新コストは増大する
- 図7.3について
  - 横軸は何を指している？
  - インデックス処理が終わったドキュメント数を指している
INPLACE
- 各タームをディスク上の定位置に配置し、事前に割り当ててることでディスクへのアクセス回数を減らす
- ディスク上の既存のインデックスは読み込んでソートしないのか？
  - ソートしないとディスクへの効率的なアクセスができない気がするが
  - よく分からない、、
- このアルゴリズムはどのタイミングでメモリ上のポスティングリストをディスクに書き込むんだろう？
  - おそらく自由に決められる（図7.2から類推するに任意のタイミングでできそう）けど、よく分からない
- 例えば、1件1件が非常に短い10万件のポスティングリストを定位置方式で更新すると、（リストあたり1回のディスクシークを行うと仮定した場合）約20分の時間がかかるが、同じポスティングリストをシーケンシャルな読み取り/書き込み処理で（統合更新の一環として）更新すると、わずか数秒で完了する
  - これは「同じポスティングリストをシーケンシャルな読み取り/書き込み処理」はIMMEDIATE MERGEを指している？
  - いいと思います
ハイブリッドインデックス保守
- INPLACEの欠点はディスクシーク数が比較的多くなること
- IMMEDIATE MERGEの主な欠点はメモリを使い果たすたびにディスク上のインデックス全体のread/writeが必要になること
- これらをポスティングリストに応じて使い分ける戦略
- リストを更新するために2回のディスクシークが必要と仮定して（バイブリッドインデックス保守戦略では、1回のシーケンシャルな統合演算を中断するため）
  - なぜ2回必要？
  - 基本的にはシーケンシャルな統合演算（IMMEDIATE MERGE）がほとんど、でたまにINPLACEがあると言う前提
  - だから、INPLACEの処理を行う時にシーケンシャルな場所から定位置にシークを移動させて、戻る必要がある
- 15行目
  - 最初の一回だけで、2回目以降は要らないように見える
- IMMEDIATE MERGEとINPLACEの計算量の損益分岐点に応じてどちらの戦略かを使い分ける
- 計算量はIMMEDIEATE MERGEよりも50%少なくなった
- 図7.6
  - IMMEDIATE MERGEの方に対応する部分はターム一つずつの処理になっているように見えるが、それでもIMMEDIATE MERGEよりも早いのか
    - 厳密にはシークは発生しているが、INPLACEの場合と違って、ほとんど動かないような位置にあるので、シークの移動のコストは無視できると言う前提がありそう
  - 15行目で毎回IMMEDIATE MERGEの方のインデックスからINPLACEのインデックスに足すのはおかしいのではないか？
big-thetaとbig-o
- big-thetaは最悪も最良もそのオーダーだよ
- big-oは最悪計算量だよ

7.2.2 非連続的転置リスト

ハイブリッドインデックス手法はメモリ資源が乏しい場合には更新性能に若干の不満が残り検索エンジンの主なボトルネックになりやすい
- なぜメモリ性能？
  - 計算量の式の中にメモリ性能に関するMが現れてます
- 計算量はO(N^2 / M) vs O(N*log(N / M) )で、単純に計算量の問題では？
分割インデックス方式
- 転置インデックスの微小な一部分を含んでいる複数のディスク上転置ファイルを保守する戦略
LOGARITHMIC MERGE
- OSSでも採用されているインデックス保守戦略
- 手続きは以下
  - メモリを使い果たした時のメモリのインデックスに世代番号1を与える
  - 今まで作成した分割インデックスを点検して、同一のラベルを持っているかどうかを確認
  - ラベルが重複しているものは統合する
  - これを衝突が無くなるまで繰り返す
- 衝突を予測することで改善可能
計算量
- ディスクに書き込まれる合計数は (log_2[N / M] + 1) N
- よって計算量はO(N*log(N / M))
インデックス更新処理
- NO MERGEとそんなに変わらない
クエリ応答時間
- IMMEDIATE MERGEとそんなに変わらない

7.3 ドキュメントの削除

削除の頻度が比較的小さく、ごく一部の検索結果が存在しないドキュメントを参照していても許容できるような場合はREBUILDが妥当
- 基本的にはREMERGEが良いとのことだったが、なぜREBUILDが良いとしているのか？
- REBUILDが有効な場合は削除されたドキュメントが60%以上のケースなので、これは誤植なのか、、

7.3.1 無効化リスト

ドキュメントが削除されるたびにポスティングから削除する
- 実質不可能
無効化リストを使えば良い
- 無効化リストIとポスティングリストPに対して、領域代数を行う
- 無効化リストを任意のクエリにどのように適用するかは難しいテーマっぽい
  - 最初に適用するんじゃなくて、最後に適用した方が良い例（ex. to be or not to be）
  - リレーショナルデータベースの最適化の先行研究に従うと、削除されたドキュメントに多く出現しがちなタームに関しては、無効化リストをそのポスティングリストに適用するべき
- ANDクエリは一個のタームだけに無効化リストを適用すれば良い可能性がある
  - 可能性なのはなぜ？
  - ANDやORが多い複雑なケースでは可能性になるケースもあるかもしれない
- ORクエリ
  - クエリ木のなるべく上位に制限を適用することが望ましいとしている
    - これはPに無効化リストを適用するということ？
    - 先に計算する方を下位、最後に計算する方を上位だとして、最終結果に対してIを適用するのが良い、ということを言ってるのではないか

7.3.2 ガベージコレクション

クエリ処理に必要なポスティングと同じポスティングブロックに含まれているというだけの理由で、多数の無効ポスティングをクエリ処理中にメモリに読み込み展開しなければならない可能性がある
削除されたドキュメントが多くなると、無効ポスティングが性能に与える影響はもはや許容できないレベルになる
ある時点で無効ポスティングを全てインデックスから削除して、存在するドキュメントに関するポスティングのみを含んだ新鮮なインデックスを維持する必要がある
- この処理のことをガベージコレクションと呼ぶ
図7.9
- output P[i] は何もしないということ？
  - 多分yes
- 第二章のnext()の第一引数はタームだが、今回の第一引数は何に対応する？
  - Iは二つのリストを持ってます
  - next()メソッドでポスティングリストを受け取るとして扱っている
  - なので、16行目でキャッシュしたc_I.endをstartのインデックスに指定してやれば、対応する開始位置が返ってくる
- ギャロップサーチを使ってるのは無効化リストで効率よく次の範囲を得るためだという理解で正しいか
もともと比較的高い統合更新のコストを、さらに30~40%増加させることになる
- 統合更新のコストはマルチウェイマージもしくはカスケードマージのこと？
  - 最後の方にIMMEDIATE MERGEという話が出てくるので、マルチウェイマージ
- 増加分はリスト交差計算であり、これが大体30%程度という理解でoK?
  - 多分yes。後半に記述ありだが、、
閾値ρ
- 入力インデックスというのはメモリがいっぱいになる時にディスクに書き込まれるインデックスのことでいいのか？
  - yes。IMMEDIATE MERGEなので
- ρが小さいとGCが頻繁に起こり、更新性能が低下するが、クエリの性能は保証される
- ρが大きいとGC時の処理が重くなり、更新性能が低下するし、クエリの性能の劣化も大きくなりうる
- ρ=(0.00, 0.10, 0.25)で実験すると、0.10が最も更新性能が良かった
最適な閾値ρを決めたい
- GC処理を加えることで30~40%増加するのに、入力ポスティングにかかる係数はなぜ1.6なのか？
  - 全体のコストが30~40%増加し、かつI_outのコストが変わらないと考えると、I_inの係数が増大するほかない
  - I_out = I_inの時を考えると、(7.21)は2cとなるので、(7.22)は2.6cになる必要がある
  - そうすると、I_inの係数は1.6になる必要がある
- C_{merge+gc} = C_merge + O_{merge+gc}とならないのはいいのか？
  - 分からない、、
- 適当な仮定を置いて計算していくと、最適なρの値は出せる
  - 実験値とも合う
  - ポスティングが増えるにつれて、だんだん小さくなっていくべきで、定数はオススメしない
2段階ガベージコレクション方式
- 基本は部分インデックスに対してGCを実施し、ある閾値を超えた場合は全体インデックスに対してGCを行う
- インデックスに大量の不要ポスティングが存在すると、統合演算の出力分割インデックスが入力分割インデックスよりも小さくなることがあり、その場合インデックスの盛大の概念そのものが意味をなさなくなる。
  - これはサイズ的に極端に小さいものを含めて分割することに意味がないということを言ってる？
    - yes。サイズを考えてやる必要がある

7.4 ドキュメントの変更

ほとんどの検索エンジンは変更操作の取り扱いに特化した戦略を用いるのではなく、古いドキュメントを削除してから修正した新しいドキュメントを再挿入することで変更を実現している
大きなドキュメントに小さな編集を加える場合、望ましい結果は得られなくなる
統合演算時にログファイルに対して行われた変更の種類を反映できるような仕組みがあると都合が良さそうである
- どういう意味だろう？
- 色々な操作を指していて、具体例として追加操作がある
ファイルの追加操作への反応が新しいトークンのインデックス化とポスティングのディスクへの書き込みのみの時
- 分割インデックスがn個あれば、nextメソッドでディスクへのn回のランダムアクセスが発生する
- GCを単一の分割インデックスではなく、インデックス全体に対して行う必要がある
- この2つってLOGARITHMIC MERGEの時も一緒では？
  - 多分そんな気がする
デスクトップ検索システム
- 各ファイル・ドキュメントの最初の数KBのみにインデックス付けを行い、残りを無視する
- これによってファイルの変更を削除と挿入の組み合わせとして扱うことが可能となり、数MBの大きさのテキストに対して再度インデックス化を行う必要がなくなる

7.5 さらに学習を進めるために

基本INPLACEよりもIMMEDIATE MERGEの方が良い
分割インデックス方式は純粋な転置インデックスのみの話
- 複数のドキュメントが相互作用しあうような場合においては使えない
圧縮率の高い暗号化手法の方がインデックスの更新性能は上がるが、GCはポスティングリストの展開と再圧縮が主なので、圧縮率ではなく、符号化・復号化の処理の効率さの方が大事
- 交差比較ではなかったのか？
  - 交差処理だけではなくて、無効化リストを復号化する必要があり、それのことを言ってるのではないか

8 確率的情報検索

モデルという言葉は二つの重要な意味をもつ
- 情報検索作業そのものの抽象化
  - 分かる
- 統計的モデル
  - 関連性モデルやドキュメントモデル
  - 具体的には何を指している？
  - TF-IDFとか？
BM25の開発過程を説明していく

8.1 関連性のモデル化

関連性と特異性、網羅性の関係ってどうなってるんだっけ、、
- 関連性は「関連しているか」
- 特異性は「どれだけ無関係な情報が入ってないか」
  - 1文だけクエリに関連していれば、「関連している」と考えることができるが、特異性は低い
- 網羅性は「クエリに対してどれだけの情報を持っているか」
  - 情報量がリッチかどうかは関連性には関係しない
8.12の第二項
- クエリの難易度？
- 「クエリが定まった時に関連性がある」と判断される確率のことではないか？
- theだと値が大きくなり、shakespereninsmだと値が小さくなるので、クエリの難易度的なものを表現してそう
- ランキングのためには
  - log{p(D|Q,r) / p(D|Q, r_)}
  - 「クエリが定まって、かつ関連性があると判断される時のドキュメントである確率」
  - 確率的情報検索モデルの中核

8.2 バイナリ独立モデル

「関連性が与えられたとき、タームは統計的に独立である」
- (8.14)
  - 全部の語彙について掛け合わせている
  - p(d_i | Q,r)はドキュメントではなく、タームについて確率になっている
  - この確率分布は全範囲（つまりボキャブラリー全体）で0にはならないということか？
「あるタームのドキュメントへの出現は、クエリにそのタームが出現している場合にのみ、関連性に依存する」
- 言葉ではよく分からないが、式を見ると少しわかる
クエリタームが全く出現しないとき式(8.18)の値は定数となる
- なぜ？
定数を引いてもランキングには影響を与えないため
- 定数部分を構成するタームはドキュメントによって異なるのではないか？
- そうすると、定数の値も異なってしまうのではないか？
- (8.20)を見ると右側が0となっているので、定数って0のこと？
- 突然全部のタームについて、D_t=0となる確率の総和を引いたということ
(8.20)
- こんな式変形していいんだっけ？
- (8.19)から簡単に計算できる

8.3 ロバートソン/スパルク・ジョーンズ重み付け関数

バイナリ独立モデルの結果を使う
関連性情報がなければIDF、あれば(8.26)の式を使う
IR研究では直感的アプローチと理論的アプローチが同様な結果を得ることがよくある

8.4 ターム頻度

タームの出現からターム頻度に拡張したい
elite
- あるドキュメントが何らかの観点であるタームに関連づけられたトピックについてのものであるとき、そのドキュメントはそのタームについてeliteである

8.4.1 ブックステインの2ポアソンモデル

与えられた期間に事象が何回発生するかを表すのによく使われる分布
- 事象の発生頻度をタームの出現頻度、時間区切りをそのドキュメントとする

8.4.2 2ポアソンモデルの近似

(8.41)
- (8.37)の近似
- 基本的な性質は(8.37)と同一
- TF-IDFに属するが、term_frequencyが飽和する特性がある

8.4.3 クエリターム頻度

ターム頻度だけでなく、クエリターム頻度もモデル化した
- あるドキュメントに似ているドキュメントを探すことができる

8.5 ドキュメントの長さ:BM25

（前回の復習）(8.37)で得られた式だが、elitenessが直接観測することができない変数であるため、パラメータを適切に設定することが難しい。
- そこで(8.41)で近似してみる
- よくよく考えてみると文章の長さを正規化した方が良さそう→ (8.46)
(8.46)では「あるドキュメント」と「長さが2倍で出現頻度も2倍のドキュメント」に同じ値を与える
- 長いドキュメントにはより高いスコアをつけたほうが良い可能性がある
  - (8.48)はそうなっているのか？
  - というか(8.48)はそれを踏まえた(8.47)の拡張として考えていいのか？
    - (8.44)は出現回数ベースで(8.47)は出現回数のパーセンテージベースでこれらの中間を取ったのがBM25
    - 「長いドキュメントにはより高いスコアをつけたほうが良い可能性がある」は「可能性がある」と言ってて、あくまで可能性なのでbをパラメータとしている
    - (8.47)では「あるドキュメント」と「長さが2倍で出現頻度も2倍のドキュメント」に同じ値を与えるので、(8.44)の式とbを使って混ぜれば同じ比率のドキュメントでも長いドキュメントに高いスコアを与えることができる（本文）
(8.48)は現在でも競争力がある
- これは感覚的にもそう
- 情報検索の論文のベンチマークとして今でも見る
表2.1の計算例
- ドキュメント5のほうが高いスコアを得ている
  - 長いドキュメントにはより高いスコアをつけたほうが良い可能性がある、じゃなかったの？
  - あくまでパーセンテージが一緒だったらの話

8.6 適合性フィードバック

関連性に関する情報が得られればw_{t}の推定精度の向上が期待できる
- 関連性の判断が少ない場合でも、こうした指示を(8.26)のn_{r}とn_{t,r}の設定に使うことができる
  - 少なくてもいいのか？
  - 精度はどうであれ、k=5とかでもできるよねっていう話かな
クエリ拡張
- 1回目の結果を利用して、拡張されたクエリを最終的な2回目の検索に用いる手法
- 仮定Qを否定している
  - ドキュメントのあるタームはクエリに出現してなくても関連性に影響を与えるため
- 適合性フィードバック
  1. ユーザーの最初のクエリを処理する
  2. 検索結果をユーザーに提示し、ユーザーに関連性があるドキュメントを指示させる
  3. ユーザーが関連性ありと指示したドキュメントに出現するタームにスコアを付け、上位m位までのタームを拡張タームとする。この時、最初のクエリに含まれていたタームは考慮しない。
  4. 最初のクエリタームに拡張タームを加え、w_{t}を調整し、結果のクエリ（拡張クエリ）を実行する
  5. 最終検索結果をユーザーに提示する
  - 仕方のないことだが、n_{r}に含まれないけど、関連性のあるドキュメントは存在してると思った

8.6.1 タームの選択

式(8.22)において、tをクエリに付け加えたとすると、関連するドキュメントのスコアはp_{t}w_{t}の平均値分増加する。そして関連しないドキュメントのスコアはp-{t}w{t}の平均値分減少する
- 関連しないドキュメントの「平均値分減少する」は「増加する」の間違い
タームtが関連ドキュメントと非関連ドキュメントの区別に役立つかどうかで上位m位のタームを決めていく

8.6.2 擬似適合性フィードバック

擬似適合性フィードバック
- ユーザーからのフィードバック手順を省いた適合性フィードバックの亜種
- 単純に上位k位の検索結果ドキュメントは全て適合していると考える
- 基本的には改善をもたらす
一回の擬似適合性フィードバックの実施でも検索の有効性を台無しにしてしまうこともある
- 平均をとって評価すれば大きな改善が得られるのだが、ユーザーを不快にさせる検索結果が1回の不具合で引き起こされてしまう
複数のドキュメントを解析する手間と、2回目のクエリを実行する必要がある
- コストがかかりすぎる
- 検索結果の改善に対して増加する検索時間のデメリットがある
クエリ拡張には適合性フィードバックと擬似適合性フィードバックがあるということ？
- この本の内容ではそう
- 適合性フィードバックのフィードバックにクエリを拡張する、という方法以外の方法が存在するのであれば、含まれなくなる
現実的には「これじゃない？」みたいな検索ワードとして拡張したキーワードをユーザーに示す、などがある

8.7 ドキュメント内フィールドによる重み付け:BM25F

BM25(8.48)との比較
- 一つのフィールドしかない場合、BM25と同じになる？
  - アイデアは同一のものを使っているが、式としては同じにならないよね？
    - 同じになる

8.8 実験による比較

(8.22)はIDFを使っているということでいいのか？
- yes
IDF → 2ポアソンモデルの近似（ターム頻度が式に導入された）→ ドキュメント長を考慮（BM25） → PRFの活用
- こんな流れ？

8.9 さらに学習を進めるために

確率的モデルと言語モデルによるアプローチの比較がある
ロバートソン/スパルく・ジョーンズ確率モデル
- バイナリ独立モデルから(8.26)(関連性がわかれば適切な重みが分かる式)が得られる
- 適切な仮定があればバイナリ独立モデルの式からIDFが得られる
擬似適合性フィードバックはMAPの改善に役立つ
- 実用上の利点は明確に示されてない
BM25
- 理論的に確立されたのはランキング式としてトップの評価を確立してからかなり経ってのこと
- ターム近接度やドキュメント中の位置などを取り入れる拡張がある

9 言語モデルと関連分野

第8章の内容（復習）
- 確率的ランキング原理からの内容はいくつかの仮定を置いて確率を使って定式化していった
- 必要に応じて近似を使用した
9章では確率的ランキング原理から先に言語モデルを使用する
言語モデルによるアプローチ
- 狭い意味での「言語モデルアプローチ」
  - クエリの生成モデル
  - 1998年のSIGIRの論文から2001まで
余談
- SIGIRはとても有名な学会・雑誌
- 言語モデルはNLPの分野で非常に有名
  - https://en.wikipedia.org/wiki/GPT-3
  - GPT-3のwikiがあった
  - 始まりはTransformerというモデルで、これがNLPの歴史を変えた
    - https://ruder.io/a-review-of-the-recent-history-of-nlp/
      - それ以前についての歴史を軽くまとめたページ
    - これ以降はTransformerをベースにしたモデル
    - Transformer → GPT → BERT → GPT-2 → GPT-3みたいな感じだったと思う

9.1 ドキュメントからのクエリ生成

確率的ランキング原理から出発
p(Q=q|D=d, r_)について
- 非関連であるサンプルが一つ得られるが、関連性のある場合については、やはり推測せざるを得ない
  - わからない
- 結果的にはこの確率がdと独立だと仮定することは合理的である
  - どういうこと？
(9.11)
- p(D)ってなんの確率を指すんだろう？
  - ドキュメントの出現確率
  - クエリとドキュメントが同時に出現しているというのは暗に関連しているでしょってこと
- rが省略されていると考えて良いのか
- その場合は関連性がある確率を指している？

9.2 言語モデルと平滑化

第1章ではシェイクスピアなどのコレクションにおける単語の分布を検討し、基本的な言語モデルアプローチを紹介した
- 言語モデルの導入
  - 語彙中のシンボルの固定出現確率分布
- 未知語への対応
  - 適当な確立を割り振る
  - 確かこのアプローチも平滑化と呼んだような（英語ではsmoothing）
- 高次モデル
  - n次の高次モデルは(n-1)次のモデルを使って平滑化することができる
  - これによって未知のパターンに対応可能
言語モデルの基本的な使い方
- 予測を行うこと
- 情報検索では「このようなドキュメントをユーザーが検索したい時に、タームtが入力される確率はいくらか」という質問に答えられなければならない
単純なモデル(9.12)では、短いドキュメントだと推定値がかなり不正確なことと出てこない単語がある点
- コレクションモデルの利用
Jelinek-Mercer smoothing
- (9.12)とコレクションモデルの単純な線型結合
ディリクり平滑化
- 仮想的にμ個のタームを追加し、言語モデルを計算
- ディリクリ分布から導出することができるらしい
どちらの平滑化でもドキュメントに出現しない単語に割り当てられる単語は全て同じ

9.3 言語モデルによるランキング

仮定Q
- あるタームのドキュメントへの出現は、クエリにそのタームが出現している場合にのみ、関連性に依存する
- クエリとドキュメントに出現しているタームが関連性に影響を与えるということ
- 仮定Qは明示的に採用されているが、仮定Tも採用されているよね？
  - yes
(9.19)
- 指数でq_tがあるのはなぜ？
- クエリタームのクエリ内での頻度だった、納得
これらの式（(9.21)と(9.22)）はTF-IDFの形式ではない
- IDFがないということ？
  - TF-IDFを(TFに関する増加関数)*IDFという風に見てます
  - yes
(9.31)
- より長いクエリにはより大きな値が適していると考えられる
  - なぜ？
  - λが大きい→ smoothingの効果が大きい→クエリが長くなると、ドキュメント中にないタームも多く含まれるので、smoothingしてないとスコアが小さくなってしまう
式変形の結果
- (9.31)が得られる
- l_C / l_t というIDFっぽい存在が現れる
- 「また、これはf_t,dと密接な関係にあるため、TF-IDFとの関連も暗に示されている」
  - (9.31)の式の対数の真数の分子にf_t,dがあることを言ってる？
    - yes
ここにl_C / l_tをかけた結果はコレクション言語モデルにおける出現数の期待値に対する、実際のトークンごとの出現回数の比であると考えられる
- どういう意味？
  - 「コレクション言語モデルにおける出現数の期待値 ← $l_t/l_C$」に対する、「実際のトークンごとの出現回数 ← $f_{t,d}$」の比
  - $\frac{f_{t,d}}{l_t/l_C}$
  - $f_{t,d} * l_C/l_t$

9.4 カルバック-ライブラー情報量

KL-divergence
- 機械学習では色んな場面に出てくる
- lossの定式化
- TRPOのフィッシャー情報行列の解釈
  - https://qiita.com/KazuyaTomita/items/00fd6df3a93f1447062e
  - こんな記事書いてたけど、全く記憶にないです
この非対称性からKL情報量は真の分布を他の分布と比較しているとみなされる場合がある
- なぜ？
- fの方が登場頻度が多いから基準という意味なのかも
- 少なくともfとgは対等では無い
式を展開していけば (9.20)に到達する
ランダムウォーク
- 単語瀕死もしくは他の因子による重みで選択される。そしてM_d,tに従い~
  - どっちに従うのか
- 全体的にどういうステップになるのか
  - もう一度考える

9.5 ランダム性からの距離

ドキュメント中に見られる実際のターム分布が偶発的に発生する確率を考慮することでランク付けする
ドキュメントの最後まで読み終える前に、tの出現回数f_t,d - 1を数えることになるだろう
- なぜ f_t,dではなく、 f_t,d - 1 ?
P_2はtが少なくとも1回出現する確率ということが分かる
- なぜ？
- 9.5.2でようやく定義が現れる
(9.41)はどうやって導出されたのか
- なぜか分からないけど現れている

9.5.1 ランダム性モデル

場合の数を計算して、P_1を計算していく
(9.48)は近似かな？

9.5.2 eliteness

連続の法則
- m-1回連続して日の出を見た
- 明日も太陽が昇る確率は m / (m + 1)
- (f_t,d - 1)回タームが出現した時にあと1回タームが出現する確率は f_t,d / (f_t,d + 1)

9.5.3 ドキュメント長の正規化

f_t,dをドキュメント長を考慮したターム頻度に調整

9.6 パッセージ検索とランキング

いったんm-カバーの適切な集合が決まると、それぞれおのm-カバーを最も近い文の区切りを含むように拡張し、決められたスペースに適合するように調整する
- どういう意味
- m-カバーを含む文章を切り取るということを言ってる？
- よく分からない
最近の言語モデルを使うと質問文をそのまま入力するという使い方になる

9.6.1 パッセージ評価

負号をつけて対数っていいんだっけ？
- 負の値にlogを取ってもいいんだっけ、、
- 多分ダメだから、対数を取って負号をつける、が正しいのかな

9.6.2 実装

mカバーを見つけるアルゴリズム
これと9.6.1の内容を踏まえて最良のパッセージを見つけ出すことが可能

9.8 さらに学習を進めるために

平滑化
- NLPでもよく見られる

10 分類とフィルタ

検索と似ているけど、ちょっとだけ違う情報要求の形がある
- 言語を識別したい
- スパムを識別したい
- 特定のトピックのものを継続的に見たい（これは検索と結構近い）
分類とフィルタ
- 分類
  - なんらかの情報要求を満たすためにドキュメントをラベル付けするプロセス
- フィルタ
  - なんらかの定常的な情報要求に応じて継続的にドキュメントを評価するプロセス
分類およびフィルタ
- 与えられたドキュメントが属するカテゴリを検索する
検索
- 与えられた情報要求に従ってドキュメントを探索し、ドキュメントを関連するかしないかのどちらかにカテゴリ分けする
自動的アプローチの方が望ましい
- 機械学習

10.1 詳細例

トピック指向フィルタ
言語の分類
スパムフィルタ

10.1.1 トピックによるバッチフィルタ

バッチフィルタ
- インデックスをつけ、コレクションに対して検索エンジンで検索する
- さらに、ドキュメントの到着を待ち、新しいドキュメントの束について同様に繰り返していく
- バッチ処理に伴う遅延が許されるのであれば許容される
ユーザーが平均速度ρでドキュメントを確認できると仮定してみよう。つまり、十分長い時間が経った後に、フィルタによって処理されたN個のドキュメントのうちρN個を確認できるとする。これらのドキュメントの適合率はユーザーに提示するバッチあたりのドキュメント数がρN個であることから最もよい値ではない
- 状況がよく分からない
- 複数バッチのどのバッチを選ぶかという話なのか
  - yes
任意のkに対して、k=ρN個のドキュメントがスコアs > tを持つようなtの値が存在する
- バッチごとにtは同一なのか？
  - 多分そうだと思う
凝集P@k
- 合計k個のドキュメントを選んだ時のtの値に応じた各バッチのP@k’ということか？

10.1.2 オンラインフィルタ

優先度付き待ち行列
- 媒体の能力よりもユーザーの処理能力が問題になってくる
- ドキュメントをランキングする
- レコメンデーションとかかな？
適切な数のドキュメントが配信されるように閾値tを設定
- 優先順位付けが不可能な場合
- 多分これがスパムフィルタとか？
BM25はドキュメントのコレクションが必要となる
- フィルタされる一つのドキュメントのみからなる、ほとんど空のコレクションにBM25を適用した時にもバッチフィルタに対してそれほど劣らない凝集結果を得ることができる
  - 凝集結果ということは凝集P@kを使ってそう

10.1.3 過去のサンプルからの学習

過去のデータがあるらしい
過去のコレクションの統計
- 2次的な効果として、バッチあたりのドキュメント数としてk個を返すだけではなく、リストの上位からk’ > k個までのドキュメントを返すことができる
  - どういう意味？
  - 過去ドキュメントと比べて、対象バッチのドキュメントのランクが非常に優秀だったら、多めに返そう的な話？
    - yes
- 過去コレクションを利用する（IDFを使う）と単一バッチと同程度のパフォーマンスになるらしい
過去の訓練例
- 教師あり学習
  - 格付け器を構築するためのラベル付きデータを使用した機械学習
  - 適合性フィードバック
    - どこが機械学習なんだろう
    - 選ばれるタームをパラメータとして見ている
- 適合性フィードバックを使うと10倍近い性能の改善につながる

10.4.4 言語の分類

分類はドキュメントに主眼が、フィルタはカテゴリに主眼がありそう
- 分類
  - ドキュメントdとカテゴリの集合に対して、dが属するカテゴリを識別する。各カテゴリが与えられたドキュメントを含む可能性がどれくらいであるかに応じてカテゴリをランク付けするカテゴリランキングに変換できる
- フィルタ
  - 特定のカテゴリcに対して、cに属するドキュメントを特定する。ドキュメントがカテゴリに属している可能性応じてランク付けするドキュメントランキングに変換できる
言語の分類
- 与えられた言語に対して、学習用のスニペットを関連ドキュメントとし、バイト4グラムの上位m位のタームをクエリとしてBM25を用いた
表10.9について
- どうやってs(d,l)を算出したのか
  - 適合性フィードバックでそれぞれの言語に対応するタームを割り出し、そこから任意のドキュメントをBM25でスコアリングした？
MRR
- https://qiita.com/tmasao/items/73388948af77105e30c8
- 単一のトピックの場合、RR = 1 / r
- MRRはそれの平均値
- AP = P@r = 1 / r
- よって、MAP = MRR
ミクロ平均とマクロ平均
- ミクロ平均
  - 全てのドキュメントの要約指標
- マクロ平均
  - カテゴリ毎に計算された要約指標の平均値
- ミクロ平均とマクロ平均との違いは、分類に固有のものである。MAPおよび他の要約指標は、検索結果に適用した場合、常にマクロ平均となる
  - 検索結果が1000個のドキュメントでも1万個のドキュメントでもマクロ平均は変わらない

10.1.5 オンライン適応スパムフィルタ

このアプリケーションでは、受信トレイを単純な待ち行列、隔離ファイルを優先度付き待ち行列とすることを考えると良い
- 僕のMacだと受信トレイは時系列順、隔離ファイル（迷惑メールフォルダ）も時系列順であった。これは隔離ファイルは優先度付き待ち行列ではなく、単純な待ち行列となっているという解釈で良い？
適合性フィードバックを伴うBM25
- スパムかハムで分類分けされたドキュメントから適合性フィードバックを用いて、タームを選定し、任意のメールに対してBM25でスコアリングした？
P@kやAPなどの有効性指標
- 分類が一番容易なドキュメントを探し出すシステムに報酬を与える
- 分類が難しいドキュメントをフィルタがうまく扱うことができるか（=スパムかハムか分かりづらいドキュメントをうまく判断できるか）、つまりスパムフィルタの有効性の核心についてはほどんど情報をもたらさない
ミクロ平均とフィルタが測定しているスパムの割合（有病率）は変わらない
- ミクロ平均誤差率は14%から8.9%に下落しているって書いてるけど
- スパムの割合もスパムの量が増えたら増えるんじゃないのか
適合率と再現率、そしてそれらに基づく要約指標をフィルタ処理として解釈することは困難である
- ここでの議論においては適合率、再現率、F_1は適切な解釈が難しいため、フィルタ処理のための評価指標としては排除するのが妥当だと考えられる
- なぜ
  - ロジット平均誤差に比べると劣るよねっていう話なんだと思います

10.1.6 二値分類の閾値選択

s(d) > 0の代わりに、 s(d) > tにしてみる
ROC曲線は、適合率-再現率曲線が特定のカットオフとは無関係にランキング検索の有効性を示すのと同様に、特定の閾値設定とは独立にフィルタ効果を幾何学的に特徴付ける
- ある曲線が別の曲線よりも上にある場合は、上にあるフィルタの方が下にあるフィルタよりも有効性が高いことを示している
ROC曲線の下の領域
- AUCと呼ぶ
- 幾何学的解釈は有名
- 確率的解釈
  - AUCはランダムなスパムメッセージがランダムなハムメッセージよりも高いスコアをもつ確率
  - どうすればこうなるか
評価の前に閾値が決定されている場合、ROC曲線は点（x,y）となるためAUCが定義できない
- 事前にスパム誤差率等が定められている状況？
  - ならばy=a(aは定数)との交点が一番ハム誤差率を低くするフィルタにすれば良いと思った、多分違う
  - 本の流れ（t=0で話を進めた場合）がまさにこの状況
- 事前にtの値が決定されている状況だが、こんなのありうるのか
  - ロジックやアルゴリズムによりハイパーパラメータは大きく異なり、それが事前に決められている状況がイメージできない
閾値tの調整
- ユーザーインターフェースによって、ユーザーに閾値の調整をさせることが可能

10.2 格付け

各付けとあるが、classificationだと分類では？と思った
基本的な格付け問題
- 二値格付け
- オブジェクトが何らかの特性Pを持つか否かを判断する処理
格付けの研究
- 初期の統計的取り込み
  - 醸造所でのビールの品質管理のために品質の悪い仕込みを特定するような問題
- 信号検出理論
  - さらに発展
  - 陽性、陰性などの言葉はこの頃の言葉かな
診断テストの結果
- テストの結果は陽性と陰性があり、実際の状態が「なし」と「あり」があるため、組み合わせはtrue positive, false positive, true negative, false negativeの4つがある
prosecutor’s fallacy(漢字読めない)
- fpr = 1%, fnr = 10%となる妊娠検査
- 1 - fpr = 99%となることから、陽性となったら99%の確率で妊娠している
- だが、男ならほぼ妊娠してないし、妊娠っぽい症状をしている女性なら99%より高い確率で妊娠しているので、事前確率を考慮する必要がある

10.2.1 オッズとオッズ比

(10.14)
- tpr + fpr = 100%になるのではないか？
- LR(pregnant, positive) = Pr[pregnant|positive] / Pr[pregnant | negative] = tpr / fnr
- とはならない？
  - 本文は多分誤植
(10.16)はどの式を使っている？
- p(e) + p(e-)=1 を使っている
結局prosecutor’s fallacyは解決されてるのか？
- 分からない

10.2.2 格付け器の構築

ドキュメント集合D、何らかの性質をもつドキュメントの部分集合をPとすると、ここでの課題は「任意のドキュメントdに対して、与えられたdはd∈P？」という問い
ハード格付け器
- (10.20)
- 決定木とかは考え方的にはハード格付け器になりそう
ソフト格付け器
- (10.21)
- ロジスティック回帰はソフト格付け器になりそう
- ロジスティック回帰は基本的には0.5を閾値としている
ハード格付け器はソフト格付け器と閾値があると構築可能
ハード格付け器の評価指標
- accuracy
- false positive rate
- false negative rate
ソフト格付け器の評価指標
- 1 - AUC
  - 0に近づくほど良い
- 間違った組み合わせ（d’の方にスコアを高くしたり、d’に同等のスコアを与える）が少ないと良い
- (10.25)の式がイコールになるのはよくわからない
フィルタの場合、cは学習されたprofileを定める隠れパラメータをもつような固定の式とみなすと良い
- profileはユーザーの好み、みたいなものを指すかと思ったが、もっと一般的なモデルのパラメータと考えた方が良さそう

10.2.3 学習モード

教師あり学習
- 入力はDの部分集合Tと関数label:T → {pos, neg}の(T, label)
- 関数labelをつくるのは人の手作業である
  - アノテーションと呼ばれるタスクで、多くの場合とてもコストフルである
  - ルームクリップに関係しそうな事例
  - 画像認識だとタグとかを使って学習させる事例がある
    - https://arxiv.org/pdf/1805.00932.pdf
  - 推薦問題の場合は「clickした」とか「購入した」がlabelとなる
  - 「clickした」は弱いフィードバックだと見なされていて、implicit feedbackなどと呼ばれる（explicit feedbackが対義語）
  - labelの構築は非常に面倒であり、間違いを起こしやすい。したがって、精度を最適化しても目的に最も適した格付け器は生成できないと考えた方が良い
半教師あり学習
- 入力はDの部分集合Tとその部分集合Sとlabel: S → {pos, neg}の(T, S, label)
- サンプルを取得する方がそれらをアノテーションするよりもはるかに簡単という思想に基づく
- T/Sを使うことで、単に入力を(S, S ,label)とした場合よりもDの分布を学習することができる
transductive learning
- 入力はドキュメント全体Dとその部分集合Sとlabel: S → {pos, neg}の(D, S, label)
- ドキュメント統計量としてコーパス全体を用いると、関連するドキュメントに分類された集合はその部分集合であるので、古典的な情報検索はtransductive learningの一種である
  - Trecシリーズのことを考えれば良い？
  - ドキュメント全体と関連ドキュメントの集合と暗黙的なlabel(関連しているかしてないかなので、明示的には存在しない)が与えられている
    - 「古典的な検索システムを使って、検索タームを最適化している人」のようなことを指しているのではないか
教師なし学習
- 入力は集合T⊆D
- 格付け器の構築に直接使われることはほとんどないが、他の学習手法と組み合わせて使われる
  - KNNとか？
  - kNNを学習方法と言って良いのか？
- ちなみにクラスタリングやったことあります
- 検索ワードのクラスタリングver4(レポート用)
オンライン学習
- ドキュメントd_kが格付けされると、それ以前のすべてのドキュメント{d_j<k}は訓練例として使用できるようになる
- すべてのサンプルは初めは格付け器をテストするために使用され、その後で訓練に使用される
- コンセプトドリフト。訓練例の列に本来備わっている時間的な手がかりを無視するため、時間変化をモデル化することができない
  - サンプルが時間とともに変化する場合、うまく機能することができないということ？
- すべての格付け器を作ると時間がかかる（O(n^2)）
逐次学習
- 逐次学習者はT_kを調べなくてもd_kのために構築された格付け器の根底にある隠されたプロファイルprofile_kから効率的にc_(k+1)を構築する
  - fine tuningはこれを満たしているような気がする
  - 以前のパラメータを初期値としながら、新たなデータで学習を行う。これはfine tuningと呼ばれる
- 逐次学習は、バッチとスライディングウィンドウを使用した非逐次学習者によって近似することができる
  - 定期的なバッチと直近のデータを対象とすることで実現できるということを言ってそう
  - fine tuning的なことをする必要がある（初期値を以前の結果を使う必要がある）
能動学習
- 格付け器は訓練例のラベルを問い合わせることができる
- なんか強化学習では違う文脈になる的な文章を見たことがある気がするが、詳細は覚えてない（本手元になくて確認できてないです）
- 不確実性サンプリング
  - ラベルづけされてない各サンプルにソフト格付け器を適用して、閾値tに最も近いサンプルに対するラベルを求める
この本ではめちゃくちゃ学習モードがあるように見えますが、機械学習の本では機械学習は以下の3タイプに分類されることが多い気がします。それ以外はこれらの亜種だとして見れることが多いと思います。
- 教師あり学習
- 教師なし学習
- 強化学習

10.2.4 特徴工学

格付け器にとって有用となりうる特徴を定義して抽出する処理
- 特徴工学
各メッセージはn次元の特徴空間内の点として表される
スパースバイグラムは特徴空間の次元を増加させるが、フィルタに良い効果があることが認められている
このようなケースではほとんどの場合、連立方程式の組を解くことでTの完全な格付け器を構築することができる
- モデルの表現力がありすぎて、過学習するよということ
- 汎化誤差をプロットすればoverfittingは検出可能
- データ量を増やすか、モデルの表現力を低減させることが必要
次元削減
- 必要としている時間効率や空間効率を達成するため
- 汎化誤差を減少させるため
  - こちらが主要だと思う
次元削減を含む手法と含まない手法が存在している
次元削減の例
- ストップワード
- 語幹抽出
- ハッシュ
  - 初めて知った。バイグラムで言うと、0と1の同じ部分を一つの次元に写すのか？
- 主成分分析
オンラインフィルタと統計量は相性が良くない
- IDFは新たにドキュメントが追加されると変化するので、これまでの値が大きく変わることがある
訓練ドキュメントとテストドキュメントに基づいて特徴選択と次元選択を実行してしまうことである
- テストセットはテストのみに用いる必要がある

10.3 確率的格付け器

ドキュメントdが、ある特性を持つドキュメント集合Pに含まれている確率はソフト、あるいはハード格付け器に使用できる
1. 特徴量中の一つの要素について、P_[i,x] = Pr[d∈P]を推定する
2. 推定値を結合して、Pr[d∈P|x_d]を得る

10.3.1 確率推定

カテゴリ特徴と連続的な特徴が存在していて、確率を推定する手法が異なる
カテゴリ特徴からの確率推定
- オッズを使用した確率推定を行う
- 正例と負例の数が小さすぎる場合があるので、平滑化する
連続特徴からの確率推定
- 二値あるいはn個のビンに分けて、カテゴリ特徴に変換
  - ビンの数を多くすると、任意のkに対してx_d,i = kとなるドキュメントの数が減少し、オッズの推定値の信頼性が低くなる
- オッズをkの関数として表現する
  - p(k|P)とp(k|P-)をパラメトリックな確率分布として表現
  - LRを使ってオッズをkの関数とする

10.3.2 確率推定の統合

(10.45)
- 単純ベイズの仮定
  - オッズ比は足し合わせることができる
  - 「シルデナフィル」と「バイアグラ」が共存しているメッセージでは足し算しなくても確率はほぼ変わらないので、足し算するのはおかしい
(10.46)
- 平均対数オッズ
  - 「シルデナフィル」と「バイアグラ」が共存しているメッセージはどちらかが単独で出現するメッセージとスパムらしさは変わらない
  - よって平均値を取る
βの取り方には他にも様々な方法がある
- 単純ベイズと平均対数オッズのβの平均
- 自信度に応じてβに1/n以外の重みを割り当てる
ロジスティック回帰
- 尤度を最大化するようにβの値を最適化していく
- ロジスティック回帰はβ_iについて解くため、それぞれのl_(d,i)が対数オッズの推定値として校正されている必要はない
  - βがl_dの線型結合の係数となっているが、必ずしもこの形式でなくても良い
- カテゴリ特徴は二値に分解する
- 連続的な特徴は変換する必要もない

10.3.3 実装における考慮事項

特徴表現とその合成方法の選択は特にオンライン用の開発では、得られる格付け器の複雑さと効率に対して大きな影響を与える可能性がある
- feature enginneringのことを言ってそうです
- 良い特徴量の作成が格付け器の性能に大きな影響を与えるということ
オンラインでの設定には個々のメッセージから導出された訓練集合内にある、互いに独立な離散特徴がより適している
- 全体の統計量の正確な値を特徴量としないほうが良い
図10.7
- 分かりづらいのは本文だとβは線型結合のパラメータだったが、疑似コードではβに確率部分logitが押し込まれていること
- 多くの特徴を考慮すればするほど、過大評価しやすくなる
  - x_(i,d)のm個の最大値とm個の最小値だけを使ってx_dを計算する
  - 多分だけど、「連続特徴からの確率推定」の手法を使っている、つまり多く出現するタームに影響されることになる
図10.8
- 勾配降下法を使ったロジスティック回帰
  - 最適化すべき関数（この場合尤度関数）が決まっている時、それを与えるパラメータを決めていく話（最適化数学）
  - 他にはニュートン法とか劣勾配降下法とかがある
- 特徴の数がサンプルの数を超えた場合に過剰適合するが、学習率δを適切な選択することにより、この落とし穴を避けることができる
  - モデルの表現力が高すぎる状況となる
- 正則化
  - overfittingにペナルティを与える
  - L1正則化とかL2正則化とかがある
  - 基本的にはoverfittingはβの値が大きくなるときに起こるので、その状況に対してペナルティを与える項

10.4 線形格付け器

線形分離可能なら、分けることのできる超平面が存在する
どうすれば最良の格付け器を構成できるのか
- 超平面に最も近いサンプルからの距離を最大化して、すべての訓練例を正しく格付けする
- 一つ以上のサンプルが誤まって格付けされても良いとする。それ以外のサンプルについては超平面までの距離を増加させる

10.4.1 パーセプトロンアルゴリズム

分離超平面が存在するのであれば探索可能。逆に言うと、分離超平面が存在しないなら、終了しない
これを発展させたマルチレイヤーパーセプトロンはいわゆるdeep learningと呼ばれる
- パーセプトロンは線形なアルゴリズムで、マルチレイヤーパーセプトロンはそこに非線形性を折り込みまくる。そうすることで、関数の表現力が向上する
マージンパーセプトロン
- 初めて知った
- アルゴリズムがより大きなマージン分離に高い評価を与えるようにマージンパラメータτを追加している
- τ/ |β|のマージンを達成するまで超平面を調整し続ける
  - よくわからない

10.4.2 サポートベクターマシン

誰もが知るようなアルゴリズム
最も近いサンプル点までのマージンを最大化する分離超平面を計算
現代的なSVM
- マージン最大化と訓練誤差の大きさの最小化との間のトレードオフ

10.5 類似性に基づいた格付け器

似たドキュメントは似てないものよりも同じカテゴリに属する可能性が高い
過去のサンプルを利用しないトピック指向のフィルタ
- c(d) = sim(d,q) というソフト格付け器
過去のサンプルを利用できる場合
- 過去のサンプルのいずれか、または全てに対するdの類似度を計算し、dを格付け
- 類似度関数 Sim: D × 2^D → R を定義
  - 2^Dという表記を初めて見た、どういう意味だろう
  - 冪集合のことを指す

10.5.1 ロッキオ法

D’内のすべてのメンバの重心であるような仮想的な代理ドキュメントd’とsim(d, d’)を計算する
word2vecを使ったドキュメントの類似度の計算を思い出した。つまり、word2vecで各単語をベクトル化し、それらの平均をドキュメントのベクトルとする方法。Doc2vecというドキュメントをベクトル化する手法はこのアプローチに負けていたのを見たことがあるので、性能悪いんだなって思った
ロッキオ法はベクトル空間モデルでの適合性フィードバックに広く使用されてきたが、基礎にしているコサイン近似度と同様に、現在では全く使われてない
- BM25適合性フィードバックの方が優れている
10.1節はSimがBM25適合性フィードバックで定義されたロッキオ法の亜種

10.5.2 メモリベース法

最近傍
- 最も簡単なメモリベース法
- 伝統的にはハード格付け器と解釈される
- 訓練例をインデックス化し、検索エンジンを使って最も類似度の高いドキュメントを探索することで、効率的に実装することができる
ソフト最近傍格付け器を計算することでハード格付け器を導出可能
- 検索インデックスを構築すると効率的
kNN
- dに最も類似したk個のドキュメントを返す
- 最も一般的なハード格付け器は、これらk個のドキュメント間の多数決として定義されている
  - k個の近傍を取ってきて、スパムかハムで多数決を取って、スパムが多かったら該当のドキュメントをスパムとみなす

10.6 一般化線形モデル

確率的格付け器（ベイジアンフィルタ、ロジスティック回帰）
- 特徴量にロジット変換を利用
線形格付け器（パーセプトロン、SVM）
- 特徴量の一つにガウス変換を利用
モデル選択
- φとそのパラメータをを推測する全体的なプロセス
- 評価データが参照されないようにする

10.6.1 カーネル法

線形分離可能なデータばかりではないし、低次元よりも高次元の方が当たり前だが、表現力が高い
高次元あるいは無限次元の表現力は使いたいが、計算は楽にしたいというのがカーネル法のやっていること
カーネルトリックを使ったSVMはカーネルSVMと呼ばれ、非線形なデータも分類できるようになる
この本だと
- (10.65)で変換先の特徴量での分離をしようとしている
- ただ、実際の計算は(10.67)ですることにより、変換先でのベクトルの内積などの計算はしてない

10.7 情報理論的モデル

モデル
- 観測可能な証拠から導出された、なんらかの事象に対する確率推定値
Mが他のモデルM’よりも真の確率に近い場合、MはM’より優れていると仮定する
MとM’どちらが優れているかを決定するタスク
- 真の確率は不明なので、ゴールドスタンダードとして比較に使用できない
- 「近い」という概念には、様々な解釈がある
より良いモデルを決定する方法があるなら以下の2つ方法で格付け器を構築できる
- 正負の訓練例ごとに別のデータ圧縮モデルを構築し、それらを使って未知のドキュメントの尤度比を推定する
- 多くの候補モデルの中から、訓練例のラベルを一番よくモデル化しているMを選択し、格付けにMそのものを使用する

10.7.1 モデルの比較

情報量
- https://ja.wikipedia.org/wiki/情報量#:~:text=情報量（じょうほうりょう,を表す尺度である。
- 情報量はそのできごとが本質的にどの程度の情報を持つかの尺度
エントロピー
- 情報量の平均
- https://www.mnc.toho-u.ac.jp/v-lab/yobology/entropy/entropy.htm
- 分布Pを持つ確率変数Xを符号化するために必要なビット数の期待値の情報理論的な下限
データ圧縮方法はこの下限に至ることはできない
- M(x) = P(x)という仮定のもとで、約I_M(x)ビットを使って各xを符号化するため、H(P)ではなく、H(M)が最適化されている
- 一般にI_M(x)は整数ではないため、ビット数の一部を無駄にしている
xを符号化するためにI_M(x)ビットを使用するコードは、下限からどのくらい離れているのだろうか
- 分布Pを持つ確率変数Xに対するコードの長さの期待値はPとMの間のクロスエントロピーで与えれらる
- クロスエントロピーとエントロピーの間の差はKL divergenceである
- (10.82)
  - 結局真の確率P(x)が出てきてしまうが、比較できるのか
  - P(x)が分かってるデータについてはどちらのモデルが良いのかが分かる

10.7.2 逐次圧縮モデル

メッセージを有限文字列のシンボル列として扱う
- モデルは(10.83)として定義して、(10.85)もしくは(10.86)の式でスコアを出す
- 負のサンプルにdを追加したことによって増加する情報量と正のサンプルにdを追加したことによって増加する情報量との差が格付け器となる
(10.85)はなぜ成立？
- 単純にLRと合わない気がしている
- 分からない
DMC
- メッセージ表現は{0,1}のシンボルの列
- 最初は0を表す状態と1を表す状態の2つの状態
- 次によく出てくるパターン（図10.17では0と01と00の3状態）を踏まえた複数の状態
- 最終的にマルコフモデルが定義されるので、確率遷移が計算可能

10.7.3 決定木と決定株

決定木の（よくある）説明
- 純度の高い集合に分割しよう、というもの
- 条件の決め方は集合の純度を純粋なものにするものがより良い条件
- 純度にはよく使われるのはジニ係数というもの
本文での説明
- 各ステップで情報利得を最大化する条件を検索していく
- ジニ係数とエントロピーはscikit-learnでの実装では両方ともあるっぽい
  - https://note.com/mucun_wuxian/n/ne8257c954514#I33rW
- 本論での情報利得の定義は上のノートとは違っている
  - ノートでは、分割により変化する純度（この純度にはエントロピーも使える）だが、本論では分割により得られる情報量、となっている
  - 式はほとんど一緒（log_2の前の係数がそのままの数か、確率か）
訓練データにモデルが過剰適合してしまう傾向がある
- 決定木はoverfittingしやすい、とよく言われる
- よくあるペナルティは木の深さ
  - これは本論でも言及があり、「Dを分割しすぎない」とある
- 式がn個の候補の集合から選択される場合、その情報量はlog_2(n)ビットである。式と訓練ラベルの組み合わせ情報量が負の情報利得を示す場合、分割を細かくしても逆効果になる可能性が高い
  - 直感的に複雑すぎる式を導入してもoverfittingにしかならないので、これは正しそう

10.8 実験による比較

10.8.1 トピック指向オンラインフィルタ

履歴型訓練
- ヘルスケアに関するドキュメントをフィルタする
- 形式は履歴を使ってバッチ的に処理する
適応型訓練
- 形式は格付け後、それをトレーニングデータとする
履歴型訓練
- BM25が特化しているため、性能が良い
- ただし、適応型訓練だと性能が他の手法より劣る
  - 適応型訓練はより多くのデータを使っているということ？
言語分類
- DMC, LR, SVM, BM25は良くて、NBとDTは良くない
タスクによって最適な手法が異なる

10.8.2 オンライン適応スパムフィルタ

DMC, LR, ROSVM(緩和オンラインSVMで最も成功したフィルタの一つらしい)はほとんど同じ効率性で、BM25とNBは大幅に劣っている

10.9 さらに学習を進めるために

情報検索と機械学習はそれぞれが大きく離れた研究コミュニティの中で進化した
IRの主な焦点は検索であったため分類やフィルタリングは副次的なものであった
機械学習分野では、テキスト分類は通常、格付けのための教師付き学習の一つの応用と見なされてきた

12 有効性の評価

評価手法を適用する上では以下が必要
- 対象となるIR手法の目的が明確になっていること
- どの程度目的が満たされているかを定量的するための指標
- 精密かつ正確で、あまりコストのかからない測定方法
- 測定誤差の推定値
12.1
- 伝統的な有効性評価を再検討し、それに対応する検索タスクについての説明
12.2
- TRECが採用する評価手法について説明
12.3
- 得られた結果に対する統計分析
12.4
- 評価の結果の信頼性を維持しながら関連性評価の数を削減する方法
12.5
- 伝統的な評価指標の拡張

12.1 伝統的な有効性指標

以下の2つの仮定がある
- ユーザーの情報要求があり、それが検索クエリで代表され、与えられたドキュメントコレクションのそれぞれのドキュメントは、その情報要求に対して関連、非関連のどちらかである
- ドキュメントdの関連性はその情報要求とドキュメントdだけに依存する。ドキュメントコレクション中に存在する他のドキュメントに対する検索エンジンのランキングとは独立である
  - ドキュメントの関連性は他のドキュメントとは関係なく決まる
  - 後半の文は検索エンジン的にランキングが低くても、それは関連性には関係ないということを言ってる？

12.1.1 再現率と適合率

再現率
- 情報要求に適合するドキュメント集合のうち、検索により取得できたドキュメントの割合
- 検索結果がユーザーの情報要求をどの程度網羅的に満足させることができたかを定量化する
- これは文献調査やリーガルサーチなどのように、関連するドキュメントを全て検索したい場合の検索タスクをモデル化している
- 検索エンジンは、単純にドキュメントコレクションにある全てのドキュメントを検索結果として返すことで、再現率100%を達成できる
適合率
- 検索により得られたドキュメント集合のうち、関連するドキュメントの割合
- 単位労力（一つのドキュメントとも考えられそう）に対する関連ドキュメントの数
- 適合率の逆数はユーザーが検索結果のドキュメント集合の要素ドキュメントを一つ一つ確認して、最初に関連ドキュメントに遭遇するまでのドキュメント数の期待値

12.1.2 検索結果の上位k件の適合率（P@k）

再現率の問題点
- ドキュメントコレクションが大きくなるにつれて、関連ドキュメントの数が多くなってしまい、全てのドキュメントにユーザーが興味を持たないレベルになってしまった
検索結果の上位k件の適合率
- 上位k件にランク付けされたドキュメントを参照した時、ユーザーがどの程度満足するかを表す
- 検索結果の上位k件の適合率には再現率の要素は含まれていないため、薬物乱用やベトナム戦争に関する全てのドキュメントを確認するユーザーはいない、という仮定を受け入れる必要がある

12.1.3 平均適合率

P@kにおいて、kの値を決める明確な基準はない
- 平均適合率はとりうる再現率レベル全てにおける適合率を統合することによって、上記の問題を解決しようとするもの
平均適合率APには結果リストに現れない関連ドキュメントも計算に組み込まれる
- |Rel|の部分を言っている？
  - 多分そう

12.1.4 逆数順位

これまでの評価指標はユーザーがこのうちある程度の数のドキュメントを閲覧したいと考えていると仮定していた
ユーザーがある一つの関連ドキュメントのみを求めている場合もあり、その場合は当該ドキュメントをできるだけ高くランク付けする必要がある
逆数順位
- 関連ドキュメントが1位にランキングされる結果を非常に高く評価する
- 複数の関連するドキュメントの存在を許容し、|Rel| > 1の場合においても、ユーザーのタスクは1件目の関連ドキュメントを確認すればすぐに完了すると仮定している

12.1.5 算術平均と幾何平均

APやRRの複数のトピックにおける平均はMAPやMRRで表され、平均という単語が名称にあるが、いくつかの評価指標（P@k）では、MP@kではなく、単にP@kと呼ばれている
(12.6)と(12.7)の例
- 両者の適合率は0.5
  - P@2のことを言ってるのか？
  - 逆数順位の可能性もある
幾何平均の方が算術平均よりも直感的に平均を正しく表す場合もある

12.1.6 ユーザーの満足度

ユーザーの満足度と様々な有効性指標の間に関係性を見つける研究は近年になってから行われるようになった
平均適合率とユーザーの満足度との関係性は極めて低いことが報告されている
P@10のような初期の適合率指標とユーザーの満足度との関係性は、適度な合理性を持つことが知られている
平均適合率は最も多く用いられている情報検索の評価指標であり、それは変わりそうにない

12.2 テキスト検索会議(TREC)

主催者がトピック集合とドキュメントコレクションを実験に参加するグループに配布する
通常、トピックからクエリを自動作成されなければならない
各トピックに対するクエリをコレクション上で実行すると、各グループは上位k件のランク付けされたリストを返す
- k=1000が典型的な値
- トピック集合全体に対するランキングリストはTRECの専門用語でrunと呼ばれている
参加者から一つ以上のrunを受け取ると、主催者は評価用のドキュメント集合（プール）を作成する
プールは各runの上位ドキュメントの和集合で構成されており、runあたりのプールの深さには100が用いられることが多い
これらの判断は人手で行われ、プール中に存在しないドキュメントは非関連ドキュメントと判断される
そのため多くの評価実験ではマニュアルなrunを奨励している。これは既知の関連ドキュメント数を増やすためである
- 人間がすることでシステムが見つけることのできない関連ドキュメントを見つけることができる
- 一つのrunくらい人間でやっていた方がシステムの性能比較にも使える
- 性能が進化しても、関連ドキュメントかどうかを多く判定してないと、性能の進化を検出できない
- マニュアルでないということは機械的（タームがあったら関連性があるとみなすとか）だと思うが、それでも関連ドキュメント数は変わらない。変わるのは精度だと思うが、、

12.3 統計指標を用いた評価

定量的測定値の精度の推定
- Aという手法はどの程度良いものか
- AはBよりどの程度優れているのか
仮説
- AはBよりも優れている
情報検索分野でも、統計的推定や仮説検定はほとんど使われてない。使われていても、そのほとんどが誤用である

12.3.1 基本的な用語の解説

「真の身長」はいくつか
- 無限回の測定を行い、それらの結果を平均化したもの
ランダム誤差
- 個々の測定値の真の値からのずれ
- 誤差=ランダム誤差+システム誤差
測定精度
- ある測定に含まれるランダム誤差の量（少なさ）
母集団の考え方
- 母集団は無限でなければならない
  - なぜなら有限の母集団から標本を得ると一つのネズミが白であるという事実が他のネズミが白である確率に影響を与えてしまうからである
    - サイコロの話なんかは試行の独立性を仮定していると思うが、仮定しないとこんな話になるのか？
    - 本来確率は無限回試行しないと導き出せないものであり、それとの関連性があるようなことを言ってる？
様々な種類のドキュメント、トピック、関連性評価はそれら自身が仮想的な母集団を代表している
「真の有効性」はとりうる全ての測定値の平均であるとする。身長の場合と同様に、母集団を正確に特定することは不可能であることから、当然「有効性」の概念は正確ではない
仮想敵母集団を列挙する代わりに、容易に準備できるデータと所見を用いることが考えられる
- それらをある仮想敵母集団「現実に得られたデータと同様なデータの全て」から抽出されたもの
- 標的母集団
  - 実際の、しかし入手は不可能な研究対象である母集団
- 仮想敵母集団
  - ソース母集団と呼ばれる
- ソース母集団は仮想敵母集団を近似し、近似が適切であればあるほど、ソース母集団を用いた測定は標的母集団を用いた測定をよく近似する
測定の妥当性
- 測定精度
- ソース母集団によって定義された真の値の測定の妥当性
  - 内的妥当性
  - ソース母集団によって定義された値の妥当性（標的母集団の値から大幅にずれていないということ）という意味？
    - 後ろの説明的にこれが外的妥当性っぽい？
- 標的母集団に対する測定の妥当性
  - 外的妥当性
  - よく分からない、、
統計的推論
- 測定精度と内的妥当性に関係する
- ソース母集団により定義された真の値に対して、測定値がどの程度優れているか
外的妥当性
- 科学的調査の手順を踏むことで評価できる
- 標的母集団とソース母集団との間で差が生じる特性値を見つけ、これらの特性値において異なる新たなソース母集団を得て、新たなソース母集団に対する有効性を測定し、特性値の差の影響を評価する
  - 標的母集団は存在しないから、ソース母集団とソース母集団との間の話になるのではないか
どのような実験手法にも外的妥当性に影響を与えるなんらかの仮定や制約が存在する
- それを明らかにし、その影響を科学的調査の手順により評価すべき
情報検索分野においても、外的妥当性の評価は難しい問題
- 研究室では現実的なテストコレクションが得にくい
- 稼働中のシステム上で実在の人物を対象に実験を行おうとすると様々な理由で実施が困難になる

12.3.2 信頼区間

信頼区間
- 実験によって得られた測定値mの「真の値」が存在すると考えられる数値範囲
- その「確からしさ」は信頼度 1 - α で数値化される。αは有意水準と呼ばれる
- 下側信頼限界lと上側信頼限界uの組[l, u]の区間として現れるか、推定された値との相対的な許容幅として表される
- 信頼度は一般に95%が用いられる
- 信頼区間は、測定に用いた実験手法の精度を示している
  - 信頼区間には真の値が少なくとも信頼度 1 - α の頻度で含まれる
  - 信頼区間のうち、真の値を含まない割合はαを超えないということ
同一の信頼度 1 - α で比較した時、より小さな信頼区間を得る測定の方が測定精度が高い
- 測定精度はサンプルサイズ、推定された測定値、測定手法に依存する
信頼区間の計算方法
- 累積分布関数が必要となる
  - これは分布をどのように規定し、推定するかによって様々な方法がある
- 正規分布について
  - https://ja.wikipedia.org/wiki/正規分布
- 二項分布
  - 独立な実験結果からの陽性結果の分布
  - 試行の回数を無限大とした時、二項分布は正規分布に近づく
- 経験分布
  - 正規分布や二項分布はパラメトリックな分布
  - 観測値の確率を頻度に基づいて素朴に計算する
  - 要素それぞれが等しい出現確率をもつと仮定された値の離散的なマルチセットとして特徴付けられる
  - 平均値と分散が定義でき、多くの場合これらをパラメータとする正規分布で近似可能
分布から信頼区間へ
- 測定値の真の値が分かっている状況を仮定
- 測定値から誤差の式を得る（(12.29)や(12.30)）
- 誤差の式から正規分布なら累積分布関数を用いればa,bの値を求めることができる
分布の推定
- 情報検索における研究結果で多いのはドキュメントと関連性評価を固定し、測定ごとにトピックを変化させたもの
  - ドキュメントや関連性評価においては無作為性がない
- 個々のドキュメント、トピック、関連性評価は仮説的無限母集団から独立かつ無作為に抽出されたものとする
- ある単独のクラス（ドキュメント、トピック、関連性評価）のみが測定ごとに変化し、他のクラスは一定であると仮定
  - ある単独のクラスは3つのうち一つのことを指しているのか、それとも3つのことを指しているのか
  - どれか一つだと思う
- 変化する要素を個体と呼び、個体の集合を標本、個体の母集団を単に母集団Pと呼ぶ
- 測定値mは標本sの関数と考える
伝統的な推定
- 関数fはそれぞれの個体になんらかの初等関数gを適用した結果の平均値であることを仮定
- f’, g’の話
  - GMAPはf=MAPで、g=log(AP)だと思うが
  - 必ずしも(12.32)のような形式でなくても良くて、GMAPでも割と同じ形で扱える
- fは平均なので、測定値の真の値の分散に標本の標準誤差を使うことができる
- この方法は2つの近似誤差が含まれている
  - 標本分散が母分散の最も良い推定値にならないこと
    - サンプルサイズが小さい時に推定値がよくない
  - 信頼区間の誤差
    - σ^2のある特定の値とそれに対応する正規分布を採用すると、関連する信頼区間はσ^2の誤差を反映したものになる
    - N ≦ 30の場合には正規分布を採用した時の誤差が大きくなる
      - この時はt分布を使うべき
ブートストラップ法を用いた推定
- リサンプリングと呼ばれている
- 標本集合をソース母集団として扱うので、データを生成可能
- 分散を計算し、正規分布の累積分布を使うか経験分布の累積分布を使う

12.3.3 各手法の比較

m_A, m_BをシステムA, Bの測定された有効性とする
- m_A > m_B
AがBよりも効果的である証拠と考えて良さそう
- AはBよりもどのくらい有効なのか
  - m_A - m_B は両者の差の指標の一つ
- 両者の差は存在するのか
  - m_A - m_B の差が意図する目的に対して意味のある差があるならyes
- 両者の差が存在するという証拠は、どのくらい確信のあるものなのか
  - 測定された差の信頼区間を考えることで対応可能
  - 信頼区間が実質的な差のみを含んでいる場合、信頼度 1 - α でAがBよりも実質的に優れている
    - 「実質的な差」は「両者の差は存在するのか」という質問に対する「意味のある差」と同じ意味だと思われる
優位性
- 有意な差とは、1 - α の信頼区間が0を含まないこと
p値
- 有意水準αにおいて結果が有意であるときのαの最小値

12.3.4 仮説検定における注意事項

そのような検定は m_A > m_B V m_A < m_Bという複合的検定、すなわち m_A ≠ m_B を行なっているのであり
有意でない事は対立仮説に反する証拠になる
- 12.35の左辺が0.06, α=0.05のケースでも優位でないとなるが、これが94%信頼区間だと優位になってしまう
- 優位でないからといって、対立仮説を否定できない
結局優位ってなんなの？
ボンフェローに補正

12.3.5 ペア化および非ペア化差異手法

(12.41)だと分散が小さくなる

12.3.6 優位性検定

両側p値は片側p値の2倍
t検定
- 通常、非ペア化、ペア化の3つがあり、それぞれでp値が異なってくる
符号検定およびウィルコクソンの符号順位検定
- どちらが大きいのか、ということにフォーカスした検定らしい

13 効率の評価

効率
- システムが作業を行う際に計算資源をどの程度消費するかを示す指標
- 3つの異なる側面
  - 時間的効率性
    - どの程度速く結果を返せるか
  - 空間的効率性
    - どの程度メモリやディスク容量が必要か
  - コスト効率性
    - その検索エンジンを構築し、維持するためにどの程度コストが生じうるか
本章の構成
- 13.1
  - 性能測定法について。スループットとレイテンシ。
- 13.2
  - スループットとレイテンシの関係
- 13.3と13.4
  - クエリのスケジューリングとキャッシング

13.1 効率の基準

80年代はマイクロプロセッサの動作速度を主な効率基準としていた
- 新しい世代のマイクロプロセッサは前世代と同じクロック周波数か遅い周波数であったとしても、処理速度が速いから
  - そうなの？
  - 2000年代はそんな感じがする
SPECというベンチマークを提供してくれる団体があるが、検索エンジンに関する性能ベンチマーク群は提供されてない
- あったとしても、有効性と性能のトレードオフを含めた品質の測定は難しいだろう

13.1.1 スループットとレイテンシ

同じ検索結果を生成するような二つの競合するシステムに出会うことがあり、これらのどちらが良いかの判断に迷うことがある
- このような場合、スループットとレイテンシがよく使われる
スループット
- 与えられた一定時間内に検索エンジンが処理するクエリの数
- サービス時間ってなんのためあるんだろう？
  - そもそも定義あってる？
    - 合ってた
レイテンシ
- 検索エンジンがクエリを受け取りそれをユーザへ返すまでに要した時間の総計
- クエリあたりの秒数
- クライアント側でのレイテンシはend-to-end latencyと呼ばれる
- 性能比較を行う時には、検索レイテンシだけを評価すれば十分である。ネットワークにより付加される遅延は実装と関係ない一定時間だからである
どちらの実装が優れているかの回答
- クエリ集合に対して二つの実装によって処理を行い、クエリごとにレイテンシを記録する
- システム間の差について信頼区間を計算する
- 信頼区間が0を含む場合は、二つの実装の間に実質的な差がない証拠と考えることができる
- そうでなければ一方の実装が他方より実質的に高速であると言える
性能比較は有効性評価と異なり、人間の判断を一切必要としないため、1%以下の違いであっても高い信頼性で検出できる
レイテンシ ≠ サービス時間
- レイテンシは実際のクエリ処理のために費やされている時間に加えて、以下の処理時間も含まれる
- ポスティングの読み込み
- CPUの待ち時間
- 分散型検索エンジンにおいて、i番目のサーバの処理が終わり、残りの n - i 個のサーバの検索結果の待ち時間
- レイテンシはスループットとも頻繁に対立する関係性にある
クエリ処理の負荷を分割することができる方法として以下の二つがある
- インデックスの複製
  - スループットが100%増加するが、レイテンシは変わらず
- インデックスの分割
  - スループットもレイテンシの両方が同程度向上するが、100%は増加しない
    - ディスクの読み込みは変わらない
    - コレクションを半分にしても、スコアリング対象のドキュメント数は変わらない可能性がある（MaxScore heuristic）
- スループットが目的ならば、インデックスの複製は正しい。レイテンシが目的ならば、インデックスの分割が正しい

13.1.2 集合的統計量とユーザの満足度

スループットやレイテンシの平均を求めることは常に意味のある結果をもたらすとは限らない
- 一部のクエリに対してとても遅いシステムは平均値では問題ないように見える
- この問題を避けるためパーセンタイル値がよく用いられる
- 「クエリの99%を1秒未満で処理する」
  - ユーザの視点で、平均レイテンシよりもはるかに有意義
  - レイテンシは自由変数ではない
  - 99%のクエリを1秒未満で処理するという条件で最適なスループットを得るために、システムを微調整することになる

13.2 待ち行列理論

一定のレイテンシ要求を満たしつつ達成可能な最大スループットを推定したい
- 事前定義されたレイテンシの限界に達するまで徐々にクエリがシステムに到達する頻度を増加させ、検索エンジンにクエリを送信する
- この方法は常に実行可能ではない
実験の代わりに数理モデルを使ってスループットを推定する方法がある
- クエリごとの平均サービス時間と平均到着頻度が得られれば、待ち行列理論により平均レイテンシを推定することができる
- 計算順序を逆転させることで、事前定義したレイテンシ要求のもとで最大スループットを計算可能
以下の3つの仮定をおく
- 連続する二つのクエリの到着時間差はある指数分布に従う。このモデルはポアソン過程と呼ばれることがある
  - クエリは互いに強い独立性があり、時間軸上で一様に分布しているという洞察に基づいている。
- クエリごとのサービス時間も指数分布に従う
  - 理論的な根拠があるわけではないが、実際に観測されたサービス時間の分布から得られた
- クエリは先着順に処理される。またシステムは一度に一つのクエリのみを処理する
  - 単純化のため。複雑なスケジューリングアルゴリズムの分析は大きな困難を伴う

13.2.1 ケンドールの記法

上記の待ち行列モデル
- M/M/c/∞/∞/Fモデル
  - クエリの到着がマルコフ過程に従う/サービス時間がマルコフ過程に従う/サーバの数/待ち行列のスロット数/クエリの母集団の大きさ/先着順
  - 最後の3つはほとんどの場合同じなので、省略される

13.2.2 M/M/1待ち行列モデル

リトルの法則
- 単位がよく分からない
- n[q/s], λ[q/s], r[s/q]になるのではないのか？
  - nは多分次元がない
  - f_t * dtを時間tで積分したのがr_total
- だとすると、「一つのクエリに着目して考えると、処理中あるいは処理待ちの状態でシステム上にある時のみ、このクエリはr_totalの計算に組み込まれる→ r_total = n * t」の部分がよく分からない
システム内の任意の時点におけるクエリ数の期待値を計算
- 状態Z_i
  - システム上にi個のクエリがある状態
  - p_i
    - 任意の時間においてシステムの状態がZ_iである確率
- マルコフ性を仮定すると、それらの相対数はシステム内のクエリ数には依存しない
- T_+とT_-は同じ頻度で起こる
  - クエリは到着した後に処理されるT_-はT_+より高頻度ではない
  - T_+ > T_-なら、待ち行列は∞となってしまう
- このことから平均応答時間を含む値が導出される

13.2.3 レイテンシ分位数と平均占有率

上記の例は検索エンジンの理論的スループットと実用上不便にならない範囲で実現可能なスループットとの違いを示している
- 理論的スループットがμ = 10で、実用上のスループットがλ=5.4?
実際には50%以上の平均占有率は非常に高いと考えられており、ほとんどの場合実現できない
このような到着頻度の変化があるため、超規定な占有率は20%以下が一般的である。したがって、レイテンシを考慮しない単純なスループット分析を用いたとき、実際にはその5倍のハードウェア資源を必要とする可能性がある
- どういう意味？
  - 日中は稼働するが、夜は0%となるので、長期的に平均すると20%以下となる
  - あるシステム（スループット10）を用意しても占有率は20%程度しかならないので、現実的なスループットは2となる。スループットが10とするためには最初に用意したハードの5倍を用意しないといけない可能性がある

13.3 クエリスケジューリング

13.2のレイテンシの導出ではクエリは先着順に処理されるという仮定をおいた
- 第一の目標が公平性を保つことではなく、レイテンシを最小化することなのであれば、これは最適な戦略ではない
スケジューリングアルゴリズム
- 検索エンジンが処理するクエリの順序を変更する仕組み
- 先着順(first-come-first-served)
- 最短ジョブ優先(shortest-job-first)
  - 検索エンジンが一つのクエリを処理を終え、次のクエリを待ち行列から選択するときに、最短のサービス時間が予測されるものを選択する
- 処理期限によるスケジューリング(deadline-driven scheduling)
  - システム上のすべてのクエリに対してその処理時間をクエリ到着後1秒以内とする。検索エンジンがクエリを処理するたびに、待ち行列の中で、処理期限に間に合わないクエリ数を最小とするようにソートする。同数の場合、検索エンジンは平均レイテンシが最小になるようにその順序を選択する
あるクエリqのサービス時間を予測することは困難だが、推定値を用いれば十分である。この推定値はポスティングリストの長さとクエリタームの数から得られる
高負荷状態では適切なスケジューリングアルゴリズムを選択することが大きな差を生んでいる
- ρ = 0.7 ではレイテンシ1秒以内のクエリの割合はFCFSでは5%だが、DDSでは1%
レイテンシコスト関数
- スターベイション
  - あるクエリが長いサービス時間を必要とすることが予測されると、そのクエリは処理を長く待たされる
- SJFは1勝以上のレイテンシとなるようなクエリの割合を5%から2.5%に減少させる。しかし、レイテンシ2秒以上のクエリを0.02%から0.06%に増加させる
- 一般に一つの数値だけを用いて検索エンジンの性能とユーザへの満足度への影響を完全に記述することは不可能
- ある種のクエリのレイテンシを減らすことは必然的に他の種類のクエリのレイテンシを増加させる
  - したがって全体の目標を設定すべき
  - 与えられたレイテンシレベルがどれほど不都合なものであるかを示すコスト関数を定義してからクエリごとの平均コストを下げるべき
  - コスト関数
    - 線形
      - 平均レイテンシの最小化
    - 指数
      - 桁外れの長いレイテンシを発生させるクエリがあれば、ユーザは不満を覚えるのでその対策
  - 適切なコスト関数を定義するにはユーザを調査するしかない
  - コスト関数が選択されれば、それを最適化するためのスケジューリングアルゴリズムを決定できる
Elastic Searchはどういうスケジューリングアルゴリズムをアルゴリズムを使用してるのか
OSのスケジューリングとの関連性を感じた

13.4 キャッシング

データのキャッシュによって平均サービス時間を削減する方法
キャッシュ
- 時間と空間の古典的なトレードオフ
- 主記憶メモリを追加し、それを以前のクエリに対する検索結果の記憶に使う
- クエリを受け取るたびに、検索エンジンはまずキャッシュを探索し、そこにすでにクエリに対する結果があるかどうかを確認する。なければ検索処理を開始する
AOLクエリログ
- 平均2.8ターム
- ユニークなクエリは平均3.5ターム
キャッシュ前のサービス速度とキャッシュ後のサービス速度の計測値に大幅な差が出る可能性がある
- キャッシュによってはヒット率の目標値を達成するには幾らかの時間を必要とする
- 検索システムの再起動時には、実効サービス頻度は期待されるより大幅に低い値を示すことがある

13.4.1 3段階キャッシュ

クエリの頻度もおおよそジップの法則に従う
- yahooの1年間のクエリログからクエリの44%はシングルトン
- 全期間を通して、各クエリは平均2回しか要求されていない
- キャッシュが無限の容量を持っていたとしてヒット率は50%を超えない
- 実際には50%を割り込むことも珍しくはない
3段階のキャッシュ階層構造
- 検索結果
  - 長いクエリの多くはシングルトンであるため、キャッシュされるクエリは2,3タームの短いものになる
  - したがってキャッシュの効果はさらに薄まる
    - キャッシュされるクエリはキャッシュされないクエリより短いため、もともと処理コストが小さいため
- リスト交差
  - 多くの検索エンジンは連言検索モデル
    - すべてのクエリタームのポスティングリストの交差を求めなければならない
  - 一般的な組み合わせの効果結果をキャッシュすることにより、クエリごとに実効しなければならない作業を減らすことができる
  - ロングとスーは、この交差のキャッシュはディスク上のインデックス構成において、平均サービス時間を約50%削減することができると見積もっている
  - インデックスが主記憶メモリ上に配置されている場合この改善幅は減少するだろう
- ポスティングリスト
  - アクセス頻度の高いポスティングリストを主記憶メモリ上に保持することによって検索エンジンの処理コストを下げることが可能
  - 検索結果のキャッシュを行なっているが、交差のキャッシュを行ってない場合、平均クエリコストを45%削減
  - 検索結果のキャッシュ+交差のキャッシュの場合、20%の削減
- (タービンら)ドキュメント
  - ドキュメントをキャッシュしても検索処理に影響はない
  - しかし、ユーザに表示するスニペットを生成する速度を向上できる
  - 情報検索分野では無視されがちな側面

13.4.2 キャッシュの方針

どの項目がキャッシュする価値があり、どの項目がその価値がないのかを決定する必要がある
キャッシュアルゴリズム
- 与えられた項目の集合とキャッシュの容量から、どの項目をキャッシュに格納するのかを決定する
- 静的なものと動的なものがある
- 動的キャッシュポリシーは置換アルゴリズムとも呼ばれる
  - 通常キャッシュに項目を追加すれば、その分他の項目を削除することになるから
汎用キャッシュポリシー
- LRU
  - 最後にアクセスされてから一番長い間アクセスのなかった項目を削除する
- LFU
  - キャッシュに加えられてからの使用頻度が最も低い項目をキャッシュから削除する
- LRUとLFUは対象項目集合のサイズがほぼ一定の場合には良好な動作をする
- 前項の例において3段階のキャッシュ全てにLRUを適用した場合、キャッシュの90%以上がポスティングリストによってよって占められることになる
  - 大きな項目が来ると以前のキャッシュが無効化されてしまう
コストを意識したキャッシュポリシー
- キャッシュを3つのバケツに分割し、それぞれを各キャッシュの段階に割り振ることである
  - 各バケツの容量はキャッシュの種類によって、その経験値などから決定される
- コストを考える方法
  - キャッシュする項目xが以下3つの要素で表される
    - キャッシュされるときに生じるコストを c_x とする。このコストはxのサイズに比例する
    - g_x はxをキャッシュから取り出したとき、それを用いなかったときに比べて得られる利得とする。これはキャッシュの種類によって、クエリのサービス時間、リストの交差を求める時間、ポスティングを主記憶メモリに展開する時間のいずれかで測定される
    - p_x は一定の時間内にxが使われる回数の期待値である。確率と考えても良い
    - 全体としてxをキャッシュしたときに期待される利得は
      - ENB(x) = (p_x * g_x) / c_x
    - このポリシーは2つの便利な特性を持つ
      - 3つの項目全てに当てはめることができる
      - パラメータc_x, g_x, p_xは過去のクエリログを使って推定できる
        
        ENBを静的キャッシュポリシーとして使うことができ、初期化中に上位n項目をあらかじめキャッシュに格納しておくことができる
        
        クエリとクエリタームの分布が時間とともにゆっくりとしか変化しない場合、この静的ポリシーは理想に近い性能を発揮する
        
        このキャッシュポリシーは未使用のキャッシュ領域をつくることがあるため、最適解とは言えないことがあるが、現実の運用では内部断片によるメモリ領域の消費も無視できるほど小さい
13.4.3 ログデータからの検索結果のプリフェッチ
- 既存のクエリログを参照できる場合近い将来問い合わせられると予測されるクエリに対する結果をプリフェッチするために使うことができる
  - 結果のプリフェッチは検索エンジン全体の負荷を軽減するわけではない
  - キャッシュヒット率を改善することになるので、平均レイテンシを減少させることができる
  - 日中の検索エンジンの負荷を平均化する作用もある
  - 特定の時間に発行されると予測されるクエリを発行して、その結果をプリフェッチし続けることが考えられる
    - ベイツェルらは商用web検索エンジンの1週間のクエリログを解析し、「個人資産管理」と言うクエリは午前7~10時でより多くなり、一方音楽に関するクエリは減少することを発見した
13.5 さらに学習を進めるために
- ファニらは検索エンジンのキャッシュを静的な部分と動的な部分に分ける方法を論じている
  - ハイブリッドな静的/動的キャッシングは過去のクエリ統計とクエリ分布変動に同時に対応できることから、純粋な静的あるいは動的なキャッシュより高い性能を達成できることが示されている

15 Web検索

今までの仮定
- 情報検索システムはトークん列で表現されたテキストコレクションを保持している
- タイトル、著者、あるいは他の構造的要素がある
Web検索
- ハイパーリンクがもたらす構造がある
- 様々な問題もある
  - 大手国際ニュース配信会社から高校生の個人ページまで
  - ほとんどがspam
  - 規模が巨大
  - クエリの曖昧さ

15.1 Webの構造

aタグの説明をしている
サイトの中にページがある

15.1.1 Webグラフ

Webグラフ
- 数学的なモデルとしてみた場合、各ページはこのグラフ内で各ノードを形成し、各ハイパーリンクはあるノードから別のノードへの有向エッジを形成する

15.1.2 静的ページと動的ページ

静的Webページ
- あらかじめ準備されてディスク上に配置され、ブラウザまたはWebクローラから要求があった場合に送出される
動的Webページ
- 要求があったときにその要求内容に依存した内容を含むページを生成する
- 多くの動的Webページはクロールとインデックス化に向いてない
  - オンラインカレンダーシステムの予定のない日付に対して延々とインデックスを作成し続けるのは好ましい作業とはいえない
  - 小売サイト上のカタログページは製品を検索する消費者のニーズを満たすため、検索エンジンはこれらのページをクロールし、インデックス化する必要がある
すべてのWebページは静的または動的になる可能性があり、静的か動的かを確実に知る方法はない
クロールとインデックス作成にはページが静的か動的かの判断よりも内容の方が重要である

15.1.3 隠れたWeb

隠れたWebとして、多くのページが存在している
- イントラネット内のページなど
- クローラには探し出すことはできない
- イントラネットをインデックス化するエンタープライズ検索エンジンは、一般的なWeb検索エンジンに見られる検索技術の多くを実装しつつ、イントラネットの特徴をうまく活用することを目指して設計されている

15.1.4 Webの規模

Webのサイズの有意義な推定値を計算することは困難
単一のホストを追加・削除することで、アクセス可能なページ数を変更することができる
多くのWebはほとんど検索結果の上部に表示されない。これらのページを検索エンジンから削除しても、影響はほとんどない
インデックス化Web
- 汎用Web検索エンジンに含まれるべきだと考えられるWebのこと
- 検索結果に実質的に影響を与える可能性があるすべてのページが含まれる
主要な検索エンジンのインデックスに含まれるすべてのページがインデックス化Webの要素だとすれば、インデックス化Webのサイズの下界は主要な検索エンジンのインデックスの和集合を取ることで決定できそうである
- この和集合を明示的に計算することは困難
- 主要検索エンジンはインデックスとページ数を公開してない
  - していても、重複があるので、求めたい和集合はこれらのページ数の和よりも小さくなる
主要検索エンジンがインデックス化したページ数の和集合を推定する手法
- 無作為なクエリ列を検索エンジンに送り、結果からURLを一つずつ無作為に抽出してテスト集合とする
- テスト集合が別の検索エンジンに保持されてるかどうかを確認
- あるURLが検索エンジンAに存在していた時に、AとBの積集合に含まれている確率を計算

15.2 クエリとユーザ

Webクエリは短い
- 長めのクエリは推奨されてなかった
- あるページが結果集合に出現するためにはページに直接出現するか、そのページを参照しているリンクのアンカーテキストとして出現しているかのどちらかで、さらにすべてのクエリタームが含まれる必要がある
- その結果、関連タームを追加してクエリが長くなった場合、関連ドキュメントに追加されたタームが含まれなければ、関連ページが除外される可能性が高くなる
- 厳密なフィルタは近年では緩和されているが、効率性の観点からフィルタはクエリ処理に置いて今でも活用されている
- Webクエリの分布はジップの法則に従う
  - ロングテール

15.2.1 ユーザの意図

ブロダーはユーザの見かけ上の目的によってWebクエリを次の3つのカテゴリに分類した
- 案内型クエリ
  - Web上の特定のページやサイトの検索
  - 通常、正確な結果は一つだけ
- 情報型クエリ
  - 特定のトピックについて何かを知ることに関心を持っており、信頼できるものであれば情報源にはさほど注意を払わない
  - ニーズはユーザにより異なることがあり、対象範囲は広いことも狭いこともある
- 取引型クエリ
  - Webサイトを見つけたらそのサイトとやりとりすることを意図している
    - ゲーム、商品購入、旅行予約、ダウンロード、地図、天気
- ローズとレビンソンの拡張
  - 情報型と取引型カテゴリをさらにいくつかのサブカテゴリに分類
    - 有向情報のクエリ
      - 特定の質問への答えを探している
      - さらにオープンクエリとクローズドクエリに分類可能
    - 無向情報のクエリ
      - 単にトピックについて知る
- 案内型クエリと情報型クエリの違い
  - ユーザが特定のサイトを求めているかどうか
- 取引型クエリと他の二つのカテゴリとの違い
  - 両方に当てはまる時があるのではないか
- 様々な研究は3つのカテゴリがWebクエリのかなりの割合を占めていることを示しており、Web検索エンジンはユーザの意図の違いを明確に認識しなければならないことを示している
- 意図はクエリ固有のものではない
  - 「UPS」というクエリには様々な意図がありうる
  - ユーザ以外の者による一つのカテゴリへの振り分けは経験に基づく推測の域を超えることはない

15.2.2 クリックによるユーザ意思の推定

案内型クエリと情報型クエリの違いはユーザの行動に表れる
- ユーザの意図を推測するために使える一つの特徴としてクリックスルーがある
- 上位10件のクリックスルー分布が案内型と情報型では異なる
  - 案内型
    - 単一の順位に集中する
  - 情報型
    - 複数の順位に散らばる結果
  - 案内型クエリに比べると情報型クエリはより線型的であり、低ランクでのクリックはなだらかに減少する

15.3 静的ランキング

Web検索の作業は二つのフェーズに分けられる
- インデックス化
  - 各ページに静的ランキングが割り当てられ、静的ランキングはページの関連性の事前確率に対応し、確率が高いほどそのランクが高くなる
- 動的ランキング
  - ターム近接度や頻度といったクエリ依存の特徴が静的ランキングと組み合わせられる
Web検索エンジンは実際のクエリ処理時に検討できない特徴をあらかじめインデックス作成時に検討し静的ランキングに割り当てておくことで検索に取り入れている
- リンク解析
  - ページランクが有名
- ページの内容やユーザの行動

15.3.1 基本的なページランク

直感的に分かりやすいのはランダムにネットサーフィンをする人
- 現在のページにあるリンクをクリックしてリンク先に移る
- ランダムにページを選択し、アドレスバーにURLを入力してそこにジャンプする
リンクをたどる確率は0.85がよく使用され、減衰係数と呼ばれることがある
ページαについてのページランクの値r(α)はサーファーがそのページを訪問する相対頻度を示す
ランダムジャンプを許して減衰係数を使用すると、ジャンプを伴わない同等のアルゴリズムと比べてページランクの安定性が統計的に改善されることが知られている
ページランクの式(15.8)は3の寄与がある
- ジャンプから
- リンクから
- シンクから
ページランクの式は実際には線形の連立方程式となる
- 不動点反復
  - 適当な初期値を入力して、新しい近似値を計算し、最終的に収束すれば、それが解となる
  - アルゴリズムの計算量はO(N + E)で、実際の計算量はメインループの反復回数による
- リンクでの反復vsノードでの反復
  - リンクの反復だと単純なデータ構造でメモリを節約できるので、大規模なWebグラフに適している
  - リンクをディスク上のファイルに保存でき、メモリ消費量をさらに削減できる

15.3.2 拡張ページランク

現実のユーザはランダムサーファーのようにはWeb上で行動しない
設定をより現実に近づけるにはリンクとジャンプについてサーファーに好みを持たせる必要がある
- 広告へのリンクよりも案内型のリンク
- ページ下部のリンクよりも上部のリンク
ジャンプの優先傾向に対応するために、テレポートベクトルJを定義する
- Jの要素J[i]はランダムサーファーがジャンプを行う際にページiを選ぶ確率
リンクの優先傾向に対応するために、追跡行列Fを定義する
- F[i, j]はページiからページjへのリンクをたどる確率
- 行の総和は1(リンクすると決まれば、リンクがあるページのどこかに移動するため)
Fは疎な行列であることを利用すればFもディスク上に置いたまま反復計算可能
図15.7に追加で必要なメモリはジャンプベクトルJを格納するメモリのみ
実際のWeb検索では外部知識を反映するために多くの調整を追跡行列とジャンプベクトルに施す必要がある
- Webグラフ自体の特性を反映させるような調整を行うべきではない
- Webグラフ自体の特性を考慮するのはページランクの仕事
外部情報の例
- ページのコンテンツと構造
  - ページのレイアウトと見た目に基づいてリンクに確率を割り当てることができる
  - ページ上部の近くやメニュー内のリンクをたどる可能性が高いだろう
  - テキスト量は多いとプラスで、量が少ないとマイナス
  - 文字が小さくて読めないとマイナス
- サイトのコンテンツと構造
  - リンクをいくつも辿らなければ見れないページよりもトップに出てくるページを好む
  - サイトによってはユーザはサイト外のリンクをたどるよりもサイト内を閲覧して回る可能性が高いことがある
  - 教育サイトと商用サイトの間のリンクは商業的な利益関係によるものでないことが多いので、ユーザにとっては強く推薦されているように見えることがある
  - 新しいサイトよりも古くて評価の確率したサイトの方が好まれることがある
- 明示的な判断
  - 高品質なサイトを手動で同定するため、編集者を動員して、これらのサイトに高いジャンプ確率を与えることがある
- 暗黙的なフィードバック
  - 検索結果のクリックスルーはそのページの品質に関する暗黙的な判断として解釈できる
  - メールサービスを介して送信されるリンクは評価が高い
特定のユーザのページランク
- ユーザが個人的な関心を持つページに高いジャンプ確率を割り当てる
トピック指向のページランク
- 特定のトピックに関連していることが知られるページに対して高いジャンプ確率を割り当てる
- 例えばWikipediaコーパスからあるページを選び、そのページのみに焦点を当てたトピック指向のページランクを生成することができる
- 50%のジャンプ確率を選択したページに割り振り、残りを均一に他のページに分配する
- だが、「William Shakespeare」と「Information Retrieval」のトピックに関するページランクに上位に「United States」のような一般的なページランクでも上位に現れるものがある
KL divergenceの利用
- トピック指向のページランクと一般的なページランクはいずれも同じページ集合における確率分布を表す
- 正規化されたトピック指向のページランクをf、一般的なページランクをg
- 各ページαについて、各店ごとのKL情報量に従ってページを再度ランクづけする
- KL情報量はシンボルが正しい分布fではなく、gに従って分布していると仮定した場合に、メッセージを圧縮するのに必要なシンボルあたりの追加ビット数の平均
- つまり、正しい分布（トピック指向）に戻すために必要なビット数が大きいものがトピック特有ということ

15.3.3 ページランクの特性

考慮すべき点
- 不動点反復法の手順は収束するのか
- 特定のWebグラフでは収束しない可能性はあるのか
- 収束する場合、どれほどの速度で収束するのか
- 初期推定値にかかわらず、常に同じページランクベクトルに収束するのか
遷移行列
- (15.8)の式から変形させていくと多分出ると
- (15.16)で遷移行列が定義でき、マルコフ連鎖の遷移行列に対応
- ページランクではサーファーがより長い時間ネットサーフィンすれば各ページでサーファーが費やす相対的な時間はスタートしたページにかかわらず一定値に収束するだろうという考えに基づいている
- ページランクは遷移行列の固有値1を持つ固有ベクトル
収束する場合
- つまり(15.20)が成り立つ
- エルゴード性により保障される
収束速度
- 収束速度はM^Tの2番目の固有値に依存する
- この値が小さいほど、より速く収束する
2番目に大きな固有ベクトルの値は減衰係数δである
- δが1に近くない場合は、実用上十分な速さで収束する
- δが0に近い場合、ランダムジャンプがほぼ全てのステップで起こるため、ページランクではWebグラフに関する有用な情報が得られなくなる
- δ=0.85は安定性と収束性を保ちつつページランクの目的を遂行可能にするための合理的なものだと思われる
ページランクの収束性と安定性を決定するのは減衰係数であり、Webグラフ自体の構造は重要な役割を果たさない
αを非ゼロのジャンプ確率を持ったページからどのようにリンクを辿っても到達できないページとすると、サーファーがαからランダムなジャンプを行なった場合、決してこれに戻ることはない
- 無限にサーフィンし続けるとサーファーが最終的にジャンプする確率は1になる。ジャンプを行なった後にαを訪れる確率は0である。したがって計算を省いてαのページランク値を0に設定できる
- ジャンプ後に到達できるページの集合をΦ’とすると、Φ’の外側のページについてページランクを計算する必要がない
  - Φ’に対応する遷移行列M’は既約（有限ステップで任意のページに到達できる）かつ非周期的（任意のタイミングでジャンプ可能なため）であるため、収束する

15.3.4 その他のリンク解析方法：HITSとSALSA

ページランク以外のリンク解析技術としてHITSアルゴリズムとSALSAアルゴリズムがある
HITSアルゴリズム
- あるページが特定のトピックに対してWebの中で果たす役割について検討したことから生まれた
- オーソリティ
  - トピックについての実質的かつ信頼性の高い情報を含むページとしての役割
- ハブ
  - トピックに関連するページへのリンクを集約したページとしての役割
- 収束に関する性質がページランクには劣る
  - 収束性
    - 初期推定値が主固有ベクトルの方向の成分を持っている場合
  - 一つの解に収束するか
    - 初期推定値に応じて異なる解に収束する可能性あり
SALSA
- ページランクのランダムサーファーをHITSに導入したもの

15.3.5 その他の静的ランキング手法

リンク解析以外に静的ランキングの計算に活用できる要素
- 暗黙的なフィードバック
  - クリック
- ページ自体の内容
  - テキストの量と複雑さ、グラフィック要素の配置とフォーマット、フォントと色の種類
- 機械学習の活用（多分回帰）
  - 基本的なページランクや内容、URLの特徴を組み合わせる

15.6 Webクローラ

クローラは順次ページをダウンロードし、それらのページからリンクを抽出し、さらに新たなリンクリンクでこの作業を繰り返す
webクローラの開発に伴う課題の多くはこのプロセスが行われる規模と速度に関係している
クローラの活動によってサイトの正常な動作を妨げないようにする
訪れたサイトの意向を尊重する
クロールおよび再クロールの順序と頻度を管理するため、クローラは閲覧したURLの優先度付き待ち行列を更新し、維持しなければならない
- 優先度付き待ち行列におけるURLの順序付けには他のページとの相対的な重要性や更新頻度を含む様々な要因を反映させる必要がある

15.6.1 クローラの構成要素

ドメイン名の翻訳
- 基本的にはDNSを私用するが、クローラの要求するスピードを満たせない場合は独自の翻訳キャッシュを用意する
ロボット排除プロトコル
- robots.txtによるアクセス等の制御
ダウンロード
- リダイレクトの解決を求められることがある
- JavaScriptのでリダイレクトを実行している場合、クローラが全てを実行するのは現実的ではない
後処理
- ダウンロード後、クローラはアーカイブにページを保存する
- 検索エンジンはこのアーカイブからインデックスを作成する
- 古いページのコピーをこのアーカイブに保存しておくことで、クローラはページが受ける変更の頻度と内容を推定できる
- リンクがあってもインデックスに含めないようにクローラに指示することが可能
  - ユーザが外部リンクを作成することができるブログやWikiなどのサイトではそのようなリンクのページランク値を不適切に増加させるリンクの作成を阻止するためのものである
優先度付き待ち行列
- 後処理中に抽出されたURLは優先度付き待ち行列に挿入される
- 優先度付き待ち行列の実装は困難である
  - ストレージ要件（簡単な試算で0.5TB必要となる）と毎秒何百万という更新をクロール必要と相まって優先度付き待ち行列の管理戦略を改善する上でネックになる

15.6.2 クロールの順序

初めてWebをクロールし、数十億のページのスナップショットをキャプチャして、それらを維持しようとしていると仮定する
よく知られているURLのシードセットから着手する
- こんなのあるんや
幅優先方法でクロールを進行すればクロールの初期段階で多くの高品質なページに遭遇するはず
クローラは段階的に処理をしながらWebのスナップショットを拡張する
更新ポリシー
- ページ変更の頻度と種類
- これらの変更が検索結果に与える影響と新たなURLをクロールした時に検索結果に与える影響の比較
- 最も単純な更新ポリシー
  - 幅優先で新しいURLをクロールし続けながら一定の頻度で全てのページに再アクセスすること
  - このポリシーは頻繁に変更を受ける影響力の強いページには適してない
  - また、新しいURLの中で検索結果に影響を与える可能性が最も高いものは最優先にクロール必要がある
  - この可能性はユーザの行動から推定可能
  - 既存のページの再訪問率と新しいURLのクロール順序を決定するのは更新ポリシーの役割
- Webは変化し続けている
  - ほとんどのページは削除されるまでに変更されなかった
  - 変化の頻度はポアソン分布でモデル化できた
- 再訪問率はそのページの変化の性質によって決まる
  - 広告や「本日の格言」
  - 変化の種類や影響力によって訪問頻度を変える
- 静的ランキングは影響力と同等ではない

15.6.3 複製ページの処理

基本的にストレージや処理コストの増大、望ましい検索結果への阻害要因になることから望ましくない
ページの厳密な複製の検出
- ハッシュ関数を使う
- 厳密な複製はクロール処理中に検出されるべきである
  - これはミラー化されたページを検出して計算量を減らすため？
準同一ページ
- バイトごとに全く同じではなくも、本質的に同じ内容を含んでいる
- 正規化してハッシュ関数を適用する
- しかし、軽微な変更や追加によりハッシュ関数で検出できないことが多い
- あるページがどの程度別のページの複製であるかは共通する部分文字列を比較することで推定できる
- shingle

15.7 まとめ

Webのスケール、ドキュメントの構造、ユーザの3つが主にフォーカスされている

15.8 さらに学習を進めるために

15.8.1 リンク解析

HITSやSALSAとその性質、Webスパムの検出の話など

15.8.4 Webクローラ

Webクローラ用の優先度付き待ち行列の効率的な実装はほとんど公開されていない