情報システムに関するメモ4（最後）

これ以上情報システムに関するメモはないです、各言葉に関する簡単な説明ですが、詳しい内容は参考文献を見てください。

検索システムの動作と評価について

情報検索の尺度

　再現率：全体の正解のなかで見つけられた正解の割合
　適合率：正解として見つけたもののうちの正しい正解の含まれる割合
これらの尺度はトレードオフだが検索の結果は上位しか参照されないため再現率は実際には尺度としては適合率ほどには重要ではない。そのため他の尺度を考える必要がある。
　F-score：再現率と適合率の調和平均をとる、これはたとえば再現率と適合率の値に大きな差があるときに通常の算術平均を尺度としては問題があるため。
　ランキングありの再現、適合率：上位k個の検索結果の再現率と適合率を尺度とする、これは実際にはランキングの下位はほとんど参照されないことによる。
　MAP：上位k個のランキングの適合率、再現率を求めてkをかえて再現率、適合率を求めることを繰り返す。これらの再現、適合率の平均値。
　nDCG：文書の検索に対する適合度に関する関数の値にその文書の検索に対するランキングに関する関数の値を掛け合わせる。これらの値の総和をとった指標。*1 つまり、適合度とその文書が上位に表示される妥当性を評価する。

質問緩和法

　最も簡単な例でいくつかのタームからなる検索をしたとき、これまではANDで検索していたものをいくつかの部分集合のセットに分けて検索する。画像のファイル名から検索するのではなく、それらの部分集合でわけた検索クエリでテキストを検索してそれを画像の検索結果を求める際に利用する。
*2

WEB検索の目的と分類

主に「ナビゲーション（特定サイトを探し当てる）」「インフォメーション（知らないものを調べる）」「トランザクション（商品購入などのトランザクションを目的とするページを求める）」タイプに分類。そしてこれらの検索の結果の上位のみが参照されることから上位には多様な検索結果を表示する必要が生まれてくる。そしてそれを行うためにMMRが開発された。MMRは既にランキングに表示されたページと類似するページは評価を下げて、残った結果の内で評価の高いものから表示。

情報フィルタリングシステムについて*3

　情報フィルタリングはその対象、フィルタリングの方法、そして情報の推薦をする方法によって分類できる。
　はじめに対象としてメッセージ（メールのスパム分類など）、プッシュされる情報の分類（ニュースの配信をクライアントごとに違う結果表示など）、そして推薦情報に分類される。その方法は協調フィルタリングとコンテンツ中心フィルタリングがある。つまり前者がサーバ側であるクライアントと類似したクライアントのデータをもとに次に推薦すべきデータを予測する、後者はあるクライアントの過去に好んだ情報に類似する情報を推薦する。
　協調フィルタリングのためには、ユーザー間の類似度を求める必要がありそれは統計の相関係数に基づいた計算で求まる。そしてその相関係数から次にすすめるべき情報を求めるために評価予測を行う。その計算のためにはつぎの推薦情報を求めたいクライアントとの相関が存在すると判断したユーザ集合の各データに対する評価の平均値を用いる。

検索システムのデータ構造について

おもな転置ファイル*4やグリッドファイルの構造と動作

　ようはインデックス型のデータ構造を保持するためのデータ構造の説明。
Btree：B木は各ノードの分岐の最大数をm、木の最大の高さをnとして ${O(\frac{m}{2} n)}$ の時間で探索できるから各タームの文書内の位置をインデックスとしてB木で探索するB木副次探索が考えられる。そしてB木の挿入と削除については参考文献*5参照。

グリッドファイル：kこの属性を持つファイルの特徴をk次元空間の点と表現してその空間を探索するための木を用いて検索をする。k次元空間の検索には二分木をk次元空間に拡張したk-Dtreeを用いる。これ以外のk次元空間の探索をするための構造は後述。
シグニチャファイル：解に含まれないとわかる集合を素早く検索対象から除外する、解になる集合は必ずすべて含んでいるような動作を実現するためのデータ。たとえば出現する単語のはじめの数文字のみ保持、など。

k次元空間探索のためのデータ構造

k-Dtree*6：k次元のユークリッド空間にある点を分類する空間分割データ構造で、要するに各軸に垂直な面（三次元の場合が一番イメージしやすい）で検索範囲を限定していく。
z-ordering*7：空間充填曲線のひとつ、参考文献参照。平面の軸を二進数で表現してshuffle関数からそのZ値を特定することができる。つまり位置情報を一つの数値で表現することができて高速に空間の探索が可能。
Rtree：B木をn次元空間のオブジェクトへと拡張したもの。つまり、B木では数値の大小（一次元での大小関係）で木を分岐していたものがあるオブジェクトがある長方形空間領域（MBR）内部に存在するかで分岐するようになる。MBR内部の要素数が制限を超えたときはそのMBRを分割する、その分割の方法は一通りではなく分割の基準が必要で分割後のMBRの領域のサイズ（面積など）が最小になる、といった基準が定義される。R+木はRtreeを改良したものであり各MBRは重なりを持たない、つまり複数のノードに出現するMBRが存在するためRtreeよりもサイズが大きくなるが長方形に重なりがないため点質問の結果を求める探索は一通りに決まることになる、その他の利点や不利は参考文献*8参照。

マルチメディアを対象にした検索（GEMINI）

　マルチメディアオブジェクトを保持するデータベースを仮定して問い合わせ（問い合わせ自体もマルチメディア）にもっともあったマルチメディアのデータベース上の位置を探す。（ここでのマルチメディアオブジェクトとは一次元の時間系列やデジタルでの音声や音楽メディア、映像などをさす）
　はじめに、マルチメディアのデータを特徴空間fに写像、検索のためにそのデータをk次元空間探索のデータ構造で保持する（Rtreeなど）。なぜならば、マルチメディアの情報を直接関数で計算したり（もっとも単純には”二つの系列を比較”など）をするとものすごい時間がかかる可能性がある。そのためマルチメディアの情報を"k次元"という低い次元の空間に落とし込むことで計算を高速化している、ただしもちろん情報はもとのマルチメディアよりも削られる。つぎにその特徴空間での二つのマルチメディア間の距離の尺度となる距離関数dを与える必要があり、仮にそれが定義できたとしてd(A,B)と記述する。ここで、もとのマルチメディアの情報をk次元空間に落とし込んだのだから「k次元空間で十分近い距離にある二つの点が十分近いならば、その二つ野天に対応するマルチメディアも十分”近い”マルチメディアである」必要がある（ここでの”近い”とは距離関数の定義によるけど、例えば同じ系列を探すのが目的なら”近い”->”同じ”としていいと思う）。
　結局のところ、k次元空間での十分近い点を探すことで「探す必要の無いマルチメディアの大部分を候補からなくす（quick and dirty test）」とともに「Rtreeなどの空間探索構造を用いて素早くそのような箇所を探し当てる」。これを実現するためには元のデータ間の違いを表す距離関数dとk次元特徴空間での距離関数dfの大小関係が保存されていることが望ましいとわかる。だから次の言が言えることはすぐに理解できる。

もとのマルチメディアを特徴空間に写像する関数を,元の空間と特徴空間上の距離関数をそれぞれ ${d,d_f}$ と書くとき、
${ 　d_f (f(A),f(B)) \leq f(A,B) }$
ならば誤って正解となる点を候補からなくしてしまうことはない。そこでユークリッド距離を保存することがPerseval's inequerityより示されている離散フーリエ変換を考える。以下は一次元系列での例。離散フーリエ変換については参考文献*9参照。つまり不等式を利用してフーリエ級数の係数の２乗和を距離関数として定義すれば

${ d_f( f(A),f(B) ) \\ \leq \sum_{i=1}^k |X_i - Y_i|^2 \\ \leq \sum_{i=1}^{n-1} |X_i - Y_i|^2 \\ \leq \sum_{i=1}^{n-1} |x_f - x_f|^2 \\ = d(A,B) }$

が言える。

ST index(subtrail index)*10

　※大学の講義資料はこの本のp309ページ”12.5　Subpattern　Matching”の章の図を使っていた。
　サブパターンマッチに先述の”解で無い大部分のオブジェクトを素早く候補から取り除く”考えを応用するためには先ほどの「マルチメディアオブジェクトひとつ」を「k次元特徴空間の点」に対応させた部分に変更を加える必要がある。以下話を簡単にするために一次元系列の場合に限定して問題を

a.長さ可変の時系列データ ${(s_1,\dots,s_N)}$ がマルチメディアオブジェクト
b.問い合わせは「系列内部に長さQの部分系列があるか？」
c.部分系列の長さと問い合わせの差が ${\epsilon}$ 以下なら許容として解とする
　※以下一般性を失わずに問い合わせQの長さの最小値を {w} とする

　サイズwの窓を用意してスライドさせていく、解になりうる点すべてにその窓を用意。その窓の内部の部分系列ごとに定義された特徴を計算する(たとえば部分系列の離散フーリエ変換によるフーリエ係数の初めのk個の２乗和、など)。だから長さLの系列はこの窓の並びを用いて特徴空間に写像されて素の長さは「(元の系列の長さ)-(問い合わせの最小の値w)+1」となる。なので次にこの特徴空間の系列のインデックスを考えると特徴空間はk次元空間と仮定してk次元空間のデータ構造を探索するために先述したRtreeなどを用いることができると思いつく（はず）。
　しかしこれだけでは効率が悪い、原因は一つの系列に対応して（窓をスライドさせて特徴を計算しているから）データが大きくなること、Rtreeは高くなるほど計算速度が遅くなること、など。なので「窓をスライドさせてどんどん特徴を計算する」点をどうにかしたい。

　そこでST-index法。連続する系列は似たような構造を持っているから、そのような類似した連続する系列をminimum bounding (hyper)rectangle (MBR)で囲い、このMBRをRtreeで保存することを考える。問い合わせQの ${\epsilon}$ に基づいた近傍が含まれる（もしくは部分的に重なる）MBRを探索することで解を得るようにする。質問Qが長ければQの系列を分割してそれらの特徴空間での ${\epsilon}$ に基づいた近傍にふくまれるMBRの和集合の内部を探索する。「和集合」としているのはもっとも大切な「解であるのに誤って候補から外してしまう」ことがないようにするため。

(終わり)

このほかのメモ

<a href="http://misos.hatenablog.com/entry/2015/01/28/114943">情報システムに関するメモ4（最後） - 雑なメモ</a>
情報システムに関するメモ4（最後） - 雑なメモ
<a href="http://misos.hatenablog.com/entry/2015/01/28/115018">情報システムに関するメモ3 - 雑なメモ</a>
情報システムに関するメモ3 - 雑なメモ
<a href="http://misos.hatenablog.com/entry/2015/01/28/115049">情報システムに関するメモ2 - 雑なメモ</a>
情報システムに関するメモ2 - 雑なメモ
<a href="http://misos.hatenablog.com/entry/2015/01/06/193508">情報システムに関するメモ1 - 雑なメモ</a>
情報システムに関するメモ1 - 雑なメモ

*1:参考文献：nDCG (normalized Discounted Cumulated Gain) | クラソル | CrowdSolving

*2:参考文献：http://www.ieice.org/iss/de/DEWS/proc/2004/paper/I-1/I-1-03.pdf

*3:参考文献：Information Filtering | Recommender Systems

*4:参考文献：転置インデックス - Wikipedia

*5:参考文献：B木 - Wikipedia

*6:参考文献：kd木 - Wikipedia

*7:参考文献：http://www.cs.cmu.edu/~christos/courses/721.S03/LECTURES-PDF/0230-z-ordering.PDF

*8:参考文献：R+ tree - Wikipedia, the free encyclopedia

*9:参考文献：6. 離散フーリエ変換 (やる夫で学ぶディジタル信号処理)

*10:参考文献：Advanced Database Systems (The Morgan Kaufmann Series in Data Management Systems) ,Carlo Zaniolo ,1997