ir - ~matubara/ChangeLog →移動しました

■ Pattern Matching Pointers (maintained by Stefano Lonardi) [string][ir][net]

<http://www.cs.ucr.edu/~stelo/pattern.html#Resources>
文字列アルゴリズム、情報検索周辺の学会、本、ソフトウェア

■ LETOR -- Benchmark Dataset for Learning to Rank [ir][learning][net]

<http://research.microsoft.com/users/LETOR/>
"learning to rank" タスクのデータセットが公開されている。

■ Fast exact maximum likelihood estimation for mixture of language models [lm][ir]

<http://dx.doi.org/10.1145/1277741.1277948>
情報検索の一部（）で使われている、片方の分布が未知の混合ユニグラムモデルにおいて、
厳密かつ、線形時間な解法が得られた。

p, q を多項分布に従う確率変数、\alpha を実数とするとき、
r = \alpha p + (1-\alpha) q
（rはpとqの混合、または線形補完と呼ばれる）

r の標本値がたくさん
p の分布（パラメタ）
\alpha の値
がわかっているときに、q のパラメタ（多項分布の各項の重み）を求めるのが問題。

証明が面白い。
でも、正当性きちんと検証できるほど読み込めてはいない。

実用的なインパクトはあまりないと思うけれど、
安易な「EMで近似解」ではないアプローチとして、価値があると思う。

■ The Xapian Project [ir][net]

<http://www.xapian.org/>

■ もっとも近い点を探す [algorithm][ir]

離散値（あるいは有限精度の実数値）の高次元空間を考える。
サイト集合と問い合わせ点が与えられたとき、
問い合わせ点にもっともちかく、サイトのひとつである点を出力せよ。

近さはユークリッド距離で定義する。
ただし、他の距離で高速な手法があればその定義をつかってもいい。

サイト数をN個、次元数をDとすると、
素朴な方法では O(ND) 時間になる。

次元数は1万程度、サイト数は千程度を想定している。
サイト数に関してオーダーNより小さい計算時間が望ましい。

1. 二分探索的な手法
2. 計算幾何で有名な方法があった気がする
3. Z-ordering
4. approximate near neighbor search -- nearest neighbor search を誤差つきにして、誤差内にあるかどうかの決定問題

■ 井上真琴, 『図書館に訊け！』 [ir][book]

情報探索入門の本。
どちらかというと文系よりで、文書を対象とした調べ物のやり方がかかれている。

「参考図書」は「貸出し禁止である」ことが必要充分条件だと思っていたけどそうではなかったらしい。
汎用の百科事典、専門の百科事典、書誌(bibliography, annotated bibliography)の本質は、
他の文献や適切なキーワードへのポインタを得るための検索ツール。
図書館（他の図書館ふくむ）にある本を探すための本なので、貸し出す必要がないということ。

人力検索の元祖、レファレンスの実態も、シナリオを挙げて、詳しく紹介されていた。
Web上にも、レファレンス協同データベースに実例がたくさんある。

■ Gilad Mishne [people][ir][net]

<http://staff.science.uva.nl/~gilad/>
ブログ、Webマイニングの人。
International conference on weblogs and social media でチュートリアル

■ 位置情報を数値1つで表す手法「Z-ordering」 [ir][net]

<http://toremoro.tea-nifty.com/tomos_hotline/2007/03/p2p1zordering_d8ba.html>

Z-orderingは文字の通り空間をＺのように埋め尽くし、一次元の数値で表してしまう技法だ。

空間充填曲線で敷き詰めたとき始点からその点まであるいた距離を、
ある点の座標として使う。

有限精度のN次元実数空間を非負整数で表すことができる。
ある種のインデキシング。

ユークリッド距離的に近い点同士はある程度近いインデクス値を持つので、
あらい距離でよければ次元数に依存せず、
整数引き算一発でできるというのがすごい。

■ Inverted Files for Text Search Engines [ir][net]

<http://www.aifb.uni-karlsruhe.de/Lehre/Winter2006-07/AIA/invertedFiles.pdf>
転置インデクスまとめ

■ Advanced Search - Project Gutenberg [lx][ir][net]

<http://www.gutenberg.org/catalog/world/search>
Project Gutenberg が全文検索可能になっていた件について
たとえば Chrismas carol のあのことばも一発で

いつからあった？

全部落とす方法

■ Language Modeling for Information Retrieval Resources [lm][ir]

<http://sifaka.cs.uiuc.edu/lmir/>

■ Probabilistic models for focused web crawling [ir][net]

<http://portal.acm.org/citation.cfm?id=1031458>

■ Finding Frequent Items in Data Streams - Charikar, Chen, Farach-Colton (2002) [ir][algorithm][net]

<http://citeseer.ist.psu.edu/charikar02finding.html>
頻度の近似計算？

■ Clarke -- Shortest-substring retrieval and ranking (2000) [ir][string][net]

<http://scholar.google.com/scholar?hl=en&lr=&cluster=2191706408632576091>
AND,OR,region algebra のクエリに対して、
データベースの部分文字列（位置）のリストを返す。

リスト中の部分文字列は、クエリに適合する極小な部分文字列。
リストは文字列の長さ順にソートされている。

演算子が AND だけのときは、
キーワード密度を測って、高い方から返すことに相当する。

この手法は、
[2006-06-01-1]Spectral-based IR の立場からは、
「解像度が非常に細かく、正確だが時間のかかる検索」
とされている。

■ Generalized Hebbian Algorithm for Incremental Singular Value (2006) [lm][ir][net]

<http://citeseer.ist.psu.edu/746603.html>
yet another SVD algorithm

■ Bayesian Hierarchical Clustering (2004, ICML) [lm][ir][algorithm][net]

<http://citeseer.ist.psu.edu/735303.html>
ボトムアップクラスタリングの距離評価に、
Bayesian なモデルによる確率を使う。

■ Modeling word burstiness using the Dirichlet distribution [ir][lm][stat][net]

<http://portal.acm.org/citation.cfm?id=1102420>
Dirichlet分布を使った文書モデル。
単語頻度の経験的分布において、
多項分布によって表すことができない性質があることを示し、
それを Dirichlet 分布で表すことができることを示す。
（明らかに傾向が違う）

多項分布モデル（単語頻度だけの Vector Space Model）は良くないが、
Vectorの作り方を TFIDF などログスケールにした場合はよくなる。
Dirichletモデルは、そのようなヒューリスティクスを使わなくても、近い性能が出る。
（というか最初から対数線形…）

双方を改善するヒューリスティクス（先行研究）：
Complement modeling (complement training) は、
あるクラスに対象が属する確率を、属しないデータを使って推定する。
属するデータより属しないデータの方が多いから有効？

Dirichlet 分布モデルの論文の中で、一番分かりやすかった。

■ Spectral Based Information Retrieval [math][nlp][ir][net]

<http://www.ee.unimelb.edu.au/multimedia/research/cubin_Laurence_Park_SpectralPhD.pdf>
DCT x IR

基本に使う情報が、単語の頻度ではなく空間周波数。
どっちも Frequency なのはご愛嬌。

slides

質問単語と文書の類似度を、
その単語のその文書における空間周波数スペクトルの大きさと角度を使って決める。
質問の中のすべての単語について、大きさと角度のそれぞれの平均をとる。
その平均スペクトルにおいて、角度を大きさで重み付け和をとった値を、
類似度とする。

これが Fourier Transform Model による IR。
性能は良いが、まだちょっと遅いので、
FFTをDCTで近似する方法を提案し、
速度と性能を両立するWavelet Transform バージョンを提案する。

DCTは高周波領域の情報を落としたスペクトルを使う近似法。

…というのが、スライドの内容でした。

面白いけど、ほんと？

■ An Algebra for Structured Text Search and A Framework for its Implementation - Clarke, Cormack, Burkowski (1995) [math][ir][net]

<http://citeseer.ist.psu.edu/clarke95algebra.html>
GCL(General Concordance List)問い合わせ代数。

■ A comparison of continuous vs. discrete image models for probabilistic image and video retrieval(2004) [lm][ir][vis][net]

<http://ieeexplore.ieee.org/search/wrapper.jsp?arnumber=1421581>
画像検索