セミナーのテキスト (北大・情報知識ネットワーク研究室)


データマイニング・情報検索・計算機科学関係

うちの研究室の輪講で現在読んでいるテキストや,過去に輪講したテキストを参考までに下記に示します.各テキストには,補助情報として,出版情報と,難易度や輪読の読み方等をコメントしています.ゼミの準備や自主的な勉強の参考にしてください.

勉強が終わって,情報検索やデータマイニング等の研究テーマを決めて, 具体的な研究を始めるときは,自分のテーマの原著論文を読むことになるかと思います.

最近のゼミのテキスト.

期間 ゼミ テキスト 表紙画像
現在(平成17年頃から) ジュエルズ・ゼミ(研究室ゼミ)
  • Jewels of Stringology -- Text Algorithms --
  • Maxime Crochemore and Wojciech Rytter, World Scientific, 2002
  • 文字列アルゴリズムの入門書.行間を埋めながら読もう.
  • このテキストの輪読はなぜか良く続いています. けっこうおおざっぱ(いいかげん?)な所もありますが,それもこの教科書の良いところです(勉強になります).
  • [publisher]
現在
(平成17年頃から)
ゼミ(研究室ゼミ)
  • Introduction to Algorithms
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Second Edition, 1202 pp, MIT Press, 2001
  • 本格的なアルゴリズムへの入門に読む本.DCがチューターの4年生ゼミの教科書ですが,オブザーバの院生諸君も勉強になっているのではと想像します.(教員はB4ゼミには出ない決まり).最近のアルゴリズムの教科書の定番といってよい分厚い本です.内容は意外に読みやすいです.英語の無料 podcastもネット上にあります.
  • [publisher]
現在(平成17年頃から) 研究室ゼミ
  • Elements of the Theory of Computation
  • Harry R. Lewis, Christos H. Papadimitriou, 2nd edition, Prentice Hall, 1997.
  • 第1章で,集合と,関係,関数,証明の基本,離散数学の基礎と計算機科学の文体を身に付けます.本の最初から,行間を埋めつつ,自分の言葉でノートをとりながら,ゆっくり読むこと.他分野からの転入生・やり直したい人は自分で読んでみよう.
  • 離散数学の専門の入門書よりも,アルゴリズムの人にはコンパクトな導入になるのでは? 古典的な計算機科学の教科書なら,最初の部分を同じ目的に使えると思います.最近のものは,どちらかというと不向きかも.
現在
(平成20年頃から)
ゼミ(研究室ゼミ)
  • Flexible Pattern Matching in Strings : Practical On-Line Search Algorithms for Texts and Biological Sequences
  • Navarro, Gonzalo and Raffinot, Mathieu, Cambridge, 2002.
  • Gonzalo Navarro氏による文字列パターン照合アルゴリズムの教科書.索引を使わないいわゆるオンライン系のパターン照合の最右翼.理論にも強いが,とにかく実用性に徹底してこだわっている点が特色.くせはあるが,ビット並列手法と正規表現照合の入門には最適だと思う.
  • ACM学会員ならば,オンラインサービスで読めるようです.
現在 研究室ゼミ
  • データマイニング関係のテキスト
  • データマイニング関係のテキストは,残念ながら,ちょうど良いコンパクトな教科書がないようです.入門には,データマイニングの個々の技術の原著論文を読んでもらっています.次のテキストは,アルゴリズムが比較的きちんと書いてある方ですが,どれも分量が多いのが玉にキズです.
  • "Data Mining: Concepts and Techniques"(Jiawei Han and Micheline Kamber, 2nd ed., Morgan Kaufmann, 2006. [author page]
  • "Principles of Data Mining"(David Hand, Heikki Mannila and Padhraic Smyth, MIT Press, 546 pp, 2001) [publisher]
  • 個々のデータマイニング技術の原著論文.
現在(平成20年頃から) 自主ゼミ(HMMゼミ)
  • Biological Sequence Analysis, Probabilistic Models of Proteins and Nucleic Acids
  • Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison, 368 pp, 1998.
  • 隠れマルコフモデルを中心にした生物情報学の本ですが, アルゴリズムが好きな人にとっては,良い統計学習の入門書だと思います. 生物情報の話は,アルゴリズムとしても,生物の話としても見れて,面白いですよ.
  • この本は,B4の学生さんが来た時に,北大人獣共通感染症センターの伊藤公人先生と一緒に輪読を始めて,現在も読んでいます(2010.10).
  • 日本語訳が,阿久津達也先生, 浅井潔先生, 矢田哲史先生の共訳で,「バイオインフォマティクス - 確率モデルによる遺伝子配列解析」(医学出版, 2001)として出版されています.(私は阿久津先生のお勧めに引かれて,この本を読みました.)
  • [publisher]

以前のゼミのテキスト.

期間 ゼミ テキスト 表紙画像
平成16から18年(後期のみ) 3年生ゼミ(輪読)
  • Managing Gigabytes: Compressing and Indexing Documents and Images
  • Ian H. Witten, Alistair Moffat, and Timothy C. Bell, Second Edition, Morgan Kaufmann, 1999.
  • 情報検索とテキスト圧縮テキスト.キーワード検索システムの実際.
  • Ian H. Witten教授はデータマイニングシステム Wekaの製作者リーダーでもあります.この3先生方は,索引系の情報検索と圧縮の研究では第一人者.
  • [book homepage]
  • 情報検索分野の最近の良いテキストとして, "Modern Information Retrieval"(Baeza-Yates, Rebeiro-Neto, 1999), "Information Retrieval, 2nd eds."(Grossmanら, Springer, 1998/2004), "Introduction to Information Retrieval"(Manning & Raghavanら, Cambridge, 2008)等がある.
  • 圧縮関係のテキストとして, "Text Compression"(Bell, Cleary, and Witten, Prentice-Hall, 1990)や "Compression and Coding Algorithms"(Moffat & Turpin, 2002) もある. "Data Compression: The Complete Reference"(Salomon)は電話帳のように厚い.
平成16年頃(1996年頃から) 研究室ゼミ
  • Data Structures and Algorithms
  • Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft, 400 pp, Addison-Wesley, 1983.
  • データ構造とアルゴリズムの古典. 最近は Cormen, Leiserson, Rivest (& Stein) 等が定番になってきているが,このAho-Ullman-Hopcroft 本は,基本的なことを丁寧に書いてあって,今でも情報科学の入門には良い本だと思う.興味があったら読んでみてください.アルゴリズムと応用をするならば,学部レベルの教科書でも,自力で丁寧に読むと勉強になります.アルゴリズムの語法(と技術英語)になれる効果があります.(今となっては,古い話題も多いので飛ばすと良いです.今では,これを1年間やる訳にもいかないですね.)
  • [publisher]
参考書
(1996年頃から)
研究室ゼミ
  • The Design and Analysis of Computer Algorithms
  • Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, 432 pp, Addison-Wesley, 1974.
  • さきのAUHの"Data structures and Algorithms"の前のバージョン.今では"Data structures ..." に比べるとマイナーだが,こちらの方にしか載っていない部分もあり,けっこう重宝する.あなどり難い.例えば,個人的には,ランダムアクセス機械の定義や,NFAへの変換による正規表現照合のアルゴリズム等は,「どうだったかな」という時にみることが多い.
  • ちなみに著者の,Aho-Hopcroft-Ullmanの3人組は,70年代から80年代の計算機科学における最強の教科書メーカー.コンパイラオートマトン理論の教科書も有名.とくにUllman先生は,他にもデータベースの教科書など,ベストセラー教科書メーカーとして有名.
  • [publisher]
1996年から2004年頃 研究室ゼミ
  • Computational Geometry, An Introduction
  • Franco P. Preparata, Michael I. Shamos, 1st ed., 420 pp, Springer, 1985.
  • 計算幾何学のアルゴリズムの最初の本(ちがってたらすみません). 案外素朴で面白いアルゴリズムが多いので, 計算幾何学分野の研究をしなくても, データマイニングや情報検索のアルゴリズムの発想の訓練に好適. 学生さんにも面白いようだ.
  • 走査型と索引型のアルゴリズムの(アイディアの)宝庫.余裕があれば副読本に.
  • 新しい教科書もあります(例:"Computational Geometry, Algorithms and Applications", Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M, 3rd ed., 2008).ただし,うちの研究室では必要なときに,サブグループや個人で読む程度で良いかも知れません.
2002年頃から最近まで 研究室ゼミ
  • 機械学習関係のテキスト
  • Pattern Recognition and Machine Learning
  • Christopher Bishop, Springer, 304 pp, 2006.
  • [publisher]
  • 過去に,上記などいろいろテキストを読んだりしているが,今一つ定着しない.どちらかというと,興味があるトピックの原著論文を最初から読んでもらうことになる.
  • "The Elements of Statistical Learning: Data Mining, Inference, and Prediction"(Hastie, Trevor, Tibshirani, Robert, Friedman, Jerome) [publisher]
  • "An Introduction to Computational Learning Theory"(Michael J. Kearns and Umesh V. Vazirani)は,良く使った計算学習理論のテキスト.しかし,今となっては必要ないような気がする. [publisher]
  • "Support Vector Machines"(John Shawe-Taylor and Nello Cristianini, Cambridge, 2000)[author page]
2004年から2008年頃まで 研究室ゼミ
  • 系列とグラフのカーネルのテキスト
  • 上記の Shawe-Taylor と Cristianiniの SVMの教科書の姉妹編の"Kernel Methods for Pattern Analysis"(John Shawe-Taylor, Nello Cristianini, Cambridge, 476 pp, 2004)は,カーネル関係の記載が豊富.アルゴリズム好きには面白いテキスト. [publisher]
  • "Kernel Methods in Computational Biology"(Bernhard Scholkopf, Koji Tsuda and Jean-Philippe Vert, eds., 410 pp, 2004) [publisher]も系列とグラフのカーネルの話題が満載.
現在 研究室ゼミ
  • 機械学習関係のテキスト
  • Machine Learning
  • Tom Mitchell, McGraw Hill, 1997
  • 内容的にはけっこう古いテキストだが,初心者への入門に有用.他分野から来た学生さんに,機械学習の全体像をつかんでもらうのに良い本だと思う.ときどき,読んでもらうことがある.ざっと見た後で,専門的な教科書か論文を読むと良い.(無論,好きな概説書があれば何でも良い."Introduction to Information Retrieval"(Manning & Raghavan)等も良いかもしれない.)
  • [author page]
(1996年から2004年頃まで) ゼミ(研究室ゼミ)
  • 最近のアルゴリズムの教科書
  • Randomized Algorithms
  • Rajeev Motwani and Prabhakar Raghavan, Cambridge, 492 pp, 1995.
  • 以前は,研究室ゼミで輪講していました.直接,役立つわけではありませんが,古典的な教科書に含まれていない新しい問題やアルゴリズムを議論すると,いろいろと面白いし,いい訓練になるように思います.そういえば,最近,研究室ではこの本を輪読していませんね.
  • 他に,Christos H. Papadimitriou の"Computational compulexity"(Addison Wesley, 1993)など.[author page]
(1996年から2004年頃まで) ゼミ(研究室ゼミ)
  • 最近のアルゴリズムの教科書
  • Computational compulexity
  • Christos H. Papadimitriou, Addison Wesley, 1993
  • 他に,これも輪読していました.
  • [author page]

ゼミのスケジュール.

[今期の研究室セミナーのスケジュール]
IKN Lab: Information Knowledge Network Laboratory
Last updated: 2010/10/20, Hiroki Arimura
E-mail: webmaster @ www-ikn.ist.hokudai.ac.jp