院試：情報システム用語まとめ
京都大学の社会情報学専攻の院試のために、情報システムの用語をまとめてみました。
この授業は受講してないので、間違いが含まれるかもしれません。
過去に同様のことをしているかたがいらっしゃったのでそちらも参考に。
http://d.hatena.ne.jp/yuku_t/20090705/info_sys
情報検索
再現率（recall）
発見したドキュメント数／全正解ドキュメント数。緩めると再現率は高まる
適合率（精度）
発見したドキュメント数／検索したドキュメント数。引き締めると適合率は高まる
テストコレクション
ドキュメント集合、多数の質問、各質問に対する適合ドキュメントの集合 を組にしたデータベース。情報検索システムの性能評価に重要
ベクトル空間モデル
各文書をV次元ベクトルで表現したもの。二値重み法、tf法、tf/idf法などで検索できる
tf/idf法
１文書におけるタームの出現頻度をtfとおく（対数で正規化する場合もある）。全検索対象ドキュメント中、タームが出現する文書数をdfとおき、全検索対象ドキュメントをNとおいて、idf=log(N/df)とする。タームの重みw=ft×idfと重みを計算する手法。多くのドキュメントに登場する、ありふれたタームの重みを引き下げる。
類似度
複数のタームを次元にしたドキュメントの特徴ベクトルDjと、質問Qの特徴ベクトルの類似度を求めて検索を行う。類似度は、ベクトルの内積やコサイン相関値とする。タームが３つなら、３次元空間で図式できる。内積だとドキュメントの分量の差で類似度が変化するが、コサイン相関値だと、分量の差は重要でなくなる。
パッセージ検索
文書DのかわりにパッセージPの各特徴ベクトルと質問ベクトルとの類似度を計算する。
適合フィードバック
検索結果を改良する手法。元の質問Qの検索結果集合のうち、ユーザーが適合と判断したものの重みを加算し、不適合と判断したものを減算する。
内容に基づくフィルタリング
ユーザ・プロファイルを作成し、コンテンツとの類似度を計算してフィルタリングを行う。ユーザ・フィルタリングはユーザの好み・選好・嗜好の情報を記述したもの。ユーザの好みを十分反映しにくく、過去に選択したものばかり出てくる可能性も高い。遺伝アルゴリズムなどの適用で弱点は補える。
協調フィルタリング
各ユーザが持つ問題解決のための情報を自動的に収集し、おなじ問題を持つユーザに提供してフィルタリングを行う。ユーザ間の類似度を計算する。アマゾンのおすすめなど。両者のフィルタリングをハイブリッドで行う事例が多い。
転置ファイル
データを構造化し、検索しやすくしたもの。データベースの属性値による条件検索や、文書のフルテキスト検索の高速化が図れる。
グリッドファイル
k個の属性を持つレコードをk次元空間の点として表現したもの。k次元空間をグリッドに分割して、各グリッドに点を均等配分する。
k-D木
アドレス空間を重なりのない領域に分割して、２分木として表現したもの。完全一致、範囲、近傍質問の処理に使える。
シグニチャファイル
明らかに解でない文書群のほとんどをすばやく排除する、"Quick and dirty"フィルタの発想にもとづいている。例えば各文書の単語の先頭の2文字を記憶して、適合しない文書をまず排除する。フィルタリングの結果、答えになる文書はすべて含み、false dropもすこし含む。シグニチャファイルを使えば、検索計算を短縮できる。
z-ordering
空間充填曲線のひとつ。空間を小正方形に分割し、Zの形にみえる順番で、k次元データを１次元情報に変換する。範囲質問、近傍質問にも対応可能、。空間結合を使って、複雑な質問にも答えられる。
R木
B木をn次元オブジェクトに拡張したもの。平衡木の一種。空間オブジェクトを、それを含む最小の長方形（MBR, Minimum Bounding Rectangle）で表現する。節点がディスクページをあらわす。オブジェクトが追加され節点を分割するときは、各節点に対応するMBRの面積の総和が最小になるよう、節点の分割を行う。図形的な解説はハンドアウトを参照。
R+木
R木を改良したもの。各非葉節点に対応するMBRの重なりを許さないのがR木との違い。葉節点は重なることもある。点質問の場合、根節点から１つの葉節点までの探索で終了できる。各レベルにおいて、節点のMBRに重なりを持つMBRはすべてその節点に含まれる。あるレコードは複数の葉節点に重複して記憶される。R木よりサイズが大きくなるのが短所。
GEMINI
Generic Multimedia Object Indexing。画像や動画の検索のため、マルチメディアデータを構造化する手法。テキストドキュメント検索と同様、特徴ベクトルを計算して類似度計算を行い、問い合わせマルチメディアオブジェクトQとの距離やパターンを調べる。
全体一致質問のためのGEMINI
全体一致質問を行う場合、まず最初にquick and dirty testを行い、明らかに誤ったオブジェクトを排除する。false dismissals（正しいの誤りと判定してしまい、棄却すること）はゼロ。false alarms（誤報）は許容する。その後、厳密な空間アクセス法を用いる。詳細にいうと、全体一致質問ではF-index（Feature Index）を用いる。F-indexはk次元空間の点集合の空間索引で、R木やR*木を使っている。質問オブジェクトQを特徴空間の点F(Q)に変換し、空間アクセス法を用いてF(Q)から距離ε内にある点を検索。本当の距離を計算して、false alarmを排除する。GEMINIが全体一致質問に対してfalse dismissalsを起こさないためには、特徴関数FはD(F(O1), F(O2)) <= D(O1, O2)の式を満たす。つまり「OがQの答えなら、特徴空間ではOはQの答えとなる」。流れをまとめると、
- オブジェクト間の距離関数D()を決定
- １つ（以上の）特徴抽出関数F()を見つける
- 特徴関数での距離がD(F(O1), F(O2)) <= D(O1, O2)であることを照明する
- 空間アクセス法によってk次元特徴ベクトルを使う
PageRank
ウェブページのランクづけシステムのひとつ。「多くの有用なページからリンクされているページは有用なページ」という仮説に基づいている。Googleのラリー・ペイジがスタンフォード大学で開発したもの。ランダムウォークの結果、辿りつきやすいページが高ランクとなる。HITSに比べてスパムページへとリンクを張る行為（たとえば、Twitterを活用するなどして）に弱いが、アルゴリズムの工夫で対応可能。
HITS(Hypertext Induced Topic Search)
ハブとオーソリティによるランクづけシステム。有用な情報を持つページをオーソリティ、有用なリンクを持つページをハブとする。各ページにハブ度とオーソリティ度を割り当てて計算する。多くの良いハブからリンクされているページは良いオーソリティ。多くの良いオーソリティにリンクしているページは良いハブ。というように相互再帰的に定義されている。スパムページへリンクを張るページに対しては万全の備えを持つが、PageRankに比べ、たいていの人の感覚とは少しずれた検索結果になる。
Region Algebra
XMLをはじめとする構造化文書のための代数
ハイパーテキスト
HTML
見出し、改行などの表現を記述するタグを持ったマークアップ言語。多くのウェブページで使用されている。スタイルシートはCSSが一般的。人間が読むことが前提で、タグを新しく設定したり、意味づけなどはできない。
XLIMK
XMLなどのためのリンクづけ規格。URLを仕様して、任意個のリソース間の、任意の方向のリンクを定義可能。HTMLのリンクは一方向で、ページ中の位置指定（ブログの真ん中など）はできない。
Ajax
JavaScriptとXMLでのサービス。ページ遷移を行わず、JavaScriptが裏で非同期でサーバと通信し、XMLをやりとりしてページの一部を更新する。
