「Introduction to Information Retrieval」の輪講の第20回です。
この輪講（勉強会）の最終回なのです。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今回も六本木ヒルズの百度 (http://www.baidu.jp/)
の会議室を会場として使わせて頂きました。ありがとうございます。

今回の内容

id:naoya 氏による恒例の復習プレゼン。
第18章「Matrix decompositions and latent semantic indexing」を説明して頂きました。
ref. Introduction to Information Retrieval #18 の復習資料 (naoyaのはてなダイアリー) http://d.hatena.ne.jp/naoya/20090301/1235912009

で、今回の輪講は一気に3章分。
第19章「Web search basics」、
第20章「Web crawling and indexes」、
第21章「Link analysis」をやりました。
すべてウェブ検索がらみの章です。
IIRの19-21章は他の章とはほぼ独立した話題なので、IIRを読むときに最初にこの辺から読み始めるのは良いかも知れません。



以下、メモ： （あとで追記する）

20章：
- Mercator: A scalable, extensible web crawler
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.5342
- common heuristic:

今回の内容に関係する書籍や話題になった書籍

■Introduction to Information Retrieval


■WEB+DB PRESS Vol.49

(ref. [を] レコメンデーションの解説が分かりやすい「WEB+DB PRESS Vol.49」[2009-02-22-2])

（あとで追記する）

打ち上げ

終了記念として打ち上げ（という名の飲み会）を行いました。
場所は「松ちゃん（まっちゃん）」[2009-03-12-1]。

「Introduction to Information Retrieval」の輪講の第19回です。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今回も六本木ヒルズの百度 (http://www.baidu.jp/)
の会議室を会場として使わせて頂きました。ありがとうございます。

今回の内容

まずは、id:naoya 氏による恒例の復習プレゼン。
第17章「Hierarchical clustering」を説明して頂きました。

今回の輪講は第18章「Matrix decompositions and latent semantic indexing」でした。
今までで一番難しい章でした。
というのも線形代数の知識がすっぽり頭から抜けていたから。
そこらへんの復習から始めて、Singular Value Decomposition (SVD) のおおまかな流れを理解し、Latent Semantic Indexing (LSI) の仕組みもなんとなく分かりました。
というか、LSI が初めてちゃんと分かった気になれました。
よかった、よかった。

以下、用語リスト。Wikipedia にあればリンクも。
- 転置行列 (A^T)
- 行列式 (|A|)
- 対角行列 (diagonal matrix)
- 単位行列 (identity matrix)
- 対称行列 (symmetric matrix)
- 特異値分解 (singular value decomposition)
- 低階数近似 (low-rank approximation)

最後に、第15章の残りを少々[2008-11-02-3]。

これで IIR も第19-21章のウェブまわりを残すのみとなりました！
次回、その3章を一気にやって大団円を迎える予定！！！

今回の内容に関係する書籍

■Introduction to Information Retrieval

「Introduction to Information Retrieval」の輪講の第18回です。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今回も前回に引き続き、六本木ヒルズの百度 (http://www.baidu.jp/)
の会議室を会場として使わせて頂きました。ありがとうございます。
百度！BAIDU!百度！

今回の内容

今回の参加者は13名くらいでした。

id:naoya 氏による恒例の復習プレゼンが久しぶりに復活しました。
前回の第16章「Flat clustering」の概要を
まとめて説明して頂きました。


今回の輪講は、第17章「Hierarchical clustering」でした。
樹形図・トーナメント図のように1対1でクラスタを
まとめあげていくという話です。
基本はボトムアップでまとめていく手法についての解説でした。
クラスタ間の類似度の尺度のバリエーションなどが丁寧に
解説されています。

あと、各クラスタの名前（ラベリング）を自動でつけるという
「Cluster labeling」の話もあったのですが、
「キーワード抽出してみよう！」レベルの話だったので、
なんというかちょっと残念でした。

今回の内容に関係する書籍

■Introduction to Information Retrieval

今回のおやつ

今回のおやつは、YRP方面から届いた、
横須賀名物(?)「携帯サブレー」でした。
横須賀は携帯電話発祥の地らしいです。
オーソドックスなサブレで非常においしいです。
ごちそうさまでした。


（形状、パッケージ、「そもそも」論など、
  ツッコミどころがいろいろとありそうです）

「Introduction to Information Retrieval」の輪講の第17回です。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今回の場所は、六本木ヒルズの百度 (http://www.baidu.jp/) の
会議室を使わせて頂きました。ありがとうございます。
BAIDU! BAIDU!


今回の参加者は12名くらいでした。



恒例の復習プレゼンですが、しばらくお休みしていた
id:naoya 氏が輪講に復活したのですが、
いろいろと忙しいようで今回も無しでした。また近々！



今回の輪講は、第16章「Flat clustering」でした。
クラスタリングです。つまり、ドキュメントを
いくつかのクラスター（グループ）に分けちゃいます。
そういう手法の一つとして、
k-means というアルゴリズムを紹介しています。
これは重要！



とはいえ、実際に応用ソフト、ウェブサービスで使う上では、
クラスタに分けるだけではなく、各クラスタの名前（ラベリング）
を自動で適切につけないと使いものにならないのですが、
そこらへんについては次章でやるらしいです。

今回の内容に関係する書籍

■Introduction to Information Retrieval

「Introduction to Information Retrieval」の輪講の第16回です。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今回の場所は、前回に引き続き
初台の DeNA (http://www.dena.jp/) の会議室でした。
いつもありがとうございます！
DeNA!! DeNA!! モバゲー！ モバゲー！


はてブのリニューアルとかで大変っぽい雰囲気な id:naoya 氏
は今回もお休みでしたので恒例の復習プレゼンは無しでした。
また今度！

さて、今回の輪講は、第15章
「Support vector machines &
machine learning on documents」です。
Support vector machines は略して SVM。
「機械学習と言えば俺のこと！泣く子も黙る SVM でい！」
SVM!! SVM!!

またこの章は、SVM の話だけでなく、
どういう分類タスクにどういう機械学習手法を使ったら良いか、
という話題もあり、参考になるかと。

今日は章の三分の二まで終了。
続きは次回。

ref.
- Wikipedia: ラグランジュの未定乗数法

懇親会

今回は、輪講終了後に懇親会を行いました。
前回同様、さくら水産です。新宿西口店。
一番安いコースでしたが、コース中にナベがあったので
非常にあったまりました。おじや最高！

今回の内容に関係する書籍

■Introduction to Information Retrieval


あと、 id:sleepy_yoshi による機械学習入門書籍リストが
はてブで話題になってたので紹介しておきます。
- Amazon.co.jp: "機械学習ことはじめ"
  http://www.amazon.co.jp/lm/R1TFEFE679T5CN

「Introduction to Information Retrieval」の輪講の第15回です。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今回は、
初台の DeNA (http://www.dena.jp/) の会議室で行われました。
会場提供、ありがとうございます。
DeNA! DeNA!

恒例の「前章の復習 by id:naoya」は
id:naoya 氏がお休みだったので無しでした。
また次回。

さて、今回の輪講は、まずは
第13章「Text classification & Naive Bayes」の続きで、
文書分類の評価についての話。
そして第14章「Vector space classification」を最後まで。
線形と非線形の2種類の分類について。
Rocchio と k Nearest Neighbor。
非線形分類器である kNN は普通の検索エンジンを
利用できるので、実装は超ラクラク！

用語メモ

13章。
1. Performance ⇔ Effectiveness
2. Macro average ⇔ Micro average

14章。
1. Contigunity hypothesis
2. Centroid, Prototype
3. Any-of ⇔ One-of classification
4. Confusion matrix

なお、前の方の章でもでてきた「Rocchio」の
読み方／カタカナ表記について議論があったので、
グーグルで出現頻度を調べたら下記の結果に。

キーワード	検索結果数
ロッキオ	250
ロッチオ	15

少ないからあまり参考にはならないかも。

今回の内容に関係する記事

13.6 で出てくる macro + micro average については、
実例入りの解説記事をあとで書く予定です。
とりあえずはこちら：
- [を] マクロ平均とマイクロ平均を混乱しがち[2006-12-12-3]

今回の内容に関係する書籍

■Introduction to Information Retrieval

「Introduction to Information Retrieval」の輪講の第14回です。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

前回に引き続き今回も
六本木ヒルズの百度の会議室を使わせて頂きました。
ありがとうございます。
BAIDU! BAIDU!

最初に恒例の「前章の復習 by id:naoya」
(http://d.hatena.ne.jp/naoya/20080928/1220796559)
前章の言語モデルネタの解説。お疲れさまです。

今回の輪講は第13章「Text classification & Naive Bayes」。
文書分類とは何か？的な話と、それを行う一手法としての
ナイーブベイズ(Naive Bayes)についてです。
この章はページ数が多くてくじけてしまいそうになりがちですが、
扱っている内容は前章、前前章をふまえればそれほど難しくありません。
文書分類技術はスパム判定はじめ、
あらゆる場面で適用できる使い道の多い便利なツールです。
こまった場面でささっと取り出せるようになると良いですね。

なお、今回は章の途中で時間切れ。
次回に続きをやります。

用語メモ

この章の冒頭には今後も使われる重要キーワードが
どんどん出てくるので、メモ。
それぞれが何かぱっと説明できればok。

1. document space
2. labeling
3. class (category, label)
4. training set (training data) [⇔8]
5. learning method (learning algorithm)
6. classifier (classification function)
7. supervised learning [⇔un-]
8. test set (test data) [⇔4]

今回の内容に関係する記事

13.5.1 の Mutual informatin （相互情報量）
については、下記の記事の私の資料が参考になるかも、ならないかも。
- [を] Blog Hackers Conference 2005[2005-05-27-1]

13.5.2 の χ^2 Feature selection （カイ２乗）
については、下記の記事が参考になるかと。
- [を] カイ二乗値で単語間の関連の強さを調べる[2007-09-19-1]

今回の内容に関係する書籍

■北研二 / 確率的言語モデル

今回というか、前回の内容に関係する本。

■Introduction to Information Retrieval

これは欠かせない！

今日のIIR輪講[2008-09-07-2]の内容のフォローも兼ねて、ちょっとしたハックを紹介。

bigram language model に基づく、ランダム文生成を行います。
って、まあ、単純にある単語の次に現れる単語の分布を用いて、文章を生成していくだけですが。

以下、サンプルプログラムと実行例です。

サンプルコード

rss-lm.pl

#!/usr/bin/perl
use strict;
use warnings;
use XML::RSS;
use LWP::Simple;
use XML::Simple;
use URI::Escape;
use utf8;
binmode STDOUT, ":utf8";

my $appid = "YahooDemo";
my $rss_url = shift;
my $rss_cont = get($rss_url) || "";
my $rss = XML::RSS->new;
$rss->parse($rss_cont);

my %next_words;
my $pre = "";
foreach my $i (@{$rss->items}) {
    my $ma_ref = webma($i->{title}."\n".$i->{description});
    foreach my $mo (@{$ma_ref->{ma_result}->{word_list}->{word}}) {
        my $w = $mo->{surface};
        $w = "" if ref($w) eq "HASH";
        next if ($pre eq "" and $w eq "");
        push @{$next_words{$pre}}, $w;
        $pre = $w;
    }
}

my @words;
my $cur = "";
for (my $i = 0; $i < 200; $i++) {
    my $tmp = $next_words{$cur};
    $cur = $tmp->[rand(@$tmp)];
    last if $cur eq "" and $i > 100;
    push @words, $cur;
}

print join("", @words), "\n";

sub webma {
    my ($key) = @_;
    return {} unless $key;
    my $url = "http://api.jlp.yahoo.co.jp/MAService/V1/parse"
        ."?appid=$appid&results=ma&response=surface"
        ."&sentence=".URI::Escape::uri_escape_utf8($key);
    my $response = get($url);
    my $xmlsimple = XML::Simple->new(ForceArray => [ 'word' ]);
    return $xmlsimple->XMLin($response);
}

日本語形態素解析に Yahoo!API を使っています。
$appid は自分で取得したものを使ってくださいね。
(http://e.developer.yahoo.co.jp/webservices/register_application)

実行例

RSS の URL を引数に与えて実行します。
実行結果はカオスです！

http://chalow.net/

./rss-lm.pl http://chalow.net/cl.rdf

【初めての持ちが、ハーゲンダッツの会）ブログで焼いて、その他のひみつ][2008北海道へ行かなくて。場所は、彼のエコアート。ローマ人のスーパーでは一個29,400円は、-04-03-08-基本的な味で売っていた！描画がFX35-KChromeLUMIXでも、デニムの大和路[2008特にhttp://wassr...blog.com/2008受賞作品展」というかとか西麻布でオフィシャルにスイカを置いておいしいです。

「北海道へ行かなくて。場所は、彼のエコアート。」ってのは、ポエムな感じで素敵です。
あと、確かにオフィシャルなスイカ（たぶん国産西瓜のことかと）はおいしいです。

http://d.hatena.ne.jp/naoya/

./rss-lm.pl http://d.hatena.ne.jp/naoya/rss

SKK分だけ、はてなハイクの発表を受けはてなハイクのインターンもbyteArray::Gapでした。金曜日はアルゴリズムの頃、はてなハイクのたつをさんから、あの変換スタイルにやろうと言えばThriftcodesKansai.net/~naoya1977/about-thrift/naoya/naoya1977/インフラを終えて発表資料を試みました。という課題が終わり、計算機科学にアップロードしましたことから何か適当に関する手法第2回募集

ついに「はてなハイクのたつをさん」になってしまいました！
あまり使ってないんだけどな、最近は。
あと、「何か適当に関する手法」を募集しているようです。
しかも第2回。一発ネタでは終わらないのですね。

簡単な解説

RSS（日本語）を読み込んで、テキストを形態素解析し、単語２連続（bigram）をカウントしています（ハッシュ %next_words に格納）。
単語 x の後に y が現れる確率は P(y|x) です。
生成時は、確率 P(y|x) に準じてランダムに y を選びます。
その方法は、

(1) x の次に現れる単語( ...)を重複をゆるすリストに格納する。

例：「今日」→「は」「も」「の」「の」「は」「から」「は」「の」
（x = 「今日」）

(2) そのリストから一つランダムで選ぶ。

という単純なものです。
説明するまでもないと思いますが、こうすることで「は」「も」「の」「から」は、それぞれ P(は|今日)、P(も|今日)、P(の|今日)、P(から|今日)、に準じた確率でランダムに選ばれます。
単語が多い対象では実行性能が悪くなりますが、RSS のテキストくらいの量なら問題ないでしょう。

ランダムで選ばれた単語を出力し、その単語の次に現れる単語をまたランダムで選ぶ、ということをループさせることにより文章を生成していきます。
なお、空文字の単語は「文頭または文末」を意味しています。
ループの最初は空文字からスタートさせます。

関連リンク

JavaScript 版と PHP 版。生成のロジックは同じです。
- マルコフ連鎖で文章生成（JavaScript） - エブログ
  http://ablog.seesaa.net/article/20987336.html
- Yahoo!のAPIを利用してマルコフ連鎖で文章生成(php)
  http://shohoji.net/blog/archives/001723.html

trigram (3gram) によるモデル。
- mizzy.org : perlで人工無脳 #1
  http://blog.mizzy.org/articles/2005/06/19/bot01

確率文章生成を含む、いろんな人工無脳について。
- 人工無脳レビュー
  http://www.ycf.nanet.co.jp/~skato/muno/material/review.html

いくつかの RSS でやってみたサンプル集。
- いろんなブログのRSSで文章生成してみた (ヲハニュース)
  http://d.hatena.ne.jp/yto/20080906/p5

「Introduction to Information Retrieval」の輪講の第13回です。

- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

今回は六本木ヒルズの Baidu の会議室を使わせて頂きました。
ありがとうございました。百度！百度！


最初に恒例の「前章の復習 by id:naoya」
(http://d.hatena.ne.jp/naoya/20080907/1220796559)。
前章の確率ネタの解説。これは結構大変。お疲れさまです。

そして、今回の輪講は第12章
「Language models for information retrieval」。
この章は、前章に続いて確率・統計の話。
言語を確率分布で表現する「言語モデル」についてです。
内容の難易度や分量は前章や次章と比べると控えめ。
今回の内容（言語モデル）を適用したハックもどうぞ→[2008-09-07-3]

次回はナイーブベイズ(Naive Bayes)です。
内部ベイズではありません。

夏休みの宿題

前回から1ヶ月あいていたので「夏休みの宿題」（任意）がありました。
IIR に関係する何かをやる、という課題。
輪講終了後に何人かが発表を行いました。
こんなのがありました。

(1) RSS から言語モデルを得て、ランダムな文を生成するハック / 私
  (see [2008-09-07-3])
(2) ナイーブベイズによるテキスト分類体験アプリ / sleepy_yoshi
  (http://d.hatena.ne.jp/sleepy_yoshi/20080907/p1)
(3) 5章の圧縮を行う Perl Module「Array::Gap」 / id:naoya
  (http://d.hatena.ne.jp/naoya/20080906/1220685978)
(4) II簡単実装環境 / id:naoya
(5) Wikipedia データで Variable Byte Code の評価 / yamada

発表は、次回へと続きます。

今日の関連書籍

■Introduction to Information Retrieval

(ref. [2008-08-05-2])
輪講の本。関連書籍というよりも主役書籍。

■荒木雅弘 / フリーソフトでつくる音声認識システム -
パターン認識・機械学習の初歩から対話システムまで

(ref. [2007-10-09-4])
今日の言語モデルの話の基礎をカバー。

■徳永健伸 / 情報検索と言語処理

(ref. http://d.hatena.ne.jp/naoya/20080906/1220685978)
東工大の徳永先生による定番本。11章の復習・補足に。

ドラフトPDFがネット上にあることで、
輪講に使っている IIR ですが、このたび書籍版もゲットしました。


- Introduction to Information Retrieval
  http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

■Introduction to Information Retrieval


PDFだと印刷したやつがどっか行っちゃう問題があったり、
本全体を俯瞰したいときに不便だったりするので、
結局「本」というまとまった媒体が必要なのです。
あとから何度も参照することになると思うので、
やはり物理的にあった方が良いのです。個人的には。