2009年9月21日月曜日

ぜひ押さえておきたいコンピューターサイエンスの教科書

僕はバイオインフォマティクスという生物と情報の融合分野で研究を行っています。東大の理学部情報科学科にいた頃は同僚のマニアックな知識に驚かされたものですが、そのような計算機専門の世界から一歩外に出ると、それが非常に希有な環境だったことに気が付きました。外の世界では、メモリとディスクの違いから、オートマトン、計算量の概念など、コンピューターサイエンスの基礎知識はあまり知られていませんでした。コンピューターサイエンスを学び始めたばかりの生物系の人と話をしているうちに、僕が学部時代に受けた教育のうち、彼らに欠けている知識についても具体的にわかるようになってきました。

バイオインフォマティクスに限らず、今後コンピュータを専門としていない人がコンピューターサイエンスについて学ぶ機会はますます多くなると思われます。そこで、これからコンピューターサイエンスを学ぼうとする人の手助けとなるように、基礎となる参考書をまとめることにしました。

ここで紹介する本は主に英語のものですが、初学者でも読みやすいように配慮されているもの選びました。ただし、ここに挙げた書籍を合わせると、生物学系の定番教科書「Molecular Biology of the Cell」(1392ページ!)よりも分量がはるかに多く、ただ情報を吸収するだけではなく、自ら頭や手を動かして能動的に考えないと理解できないため壁も高めです。挫折しないためには、一度きちんと勉強した研究者のガイドを受けながら読むか、大学の情報系の講義に参加して科目の全体像、重要なポイントを知った上で読むことを「強く」お勧めします。もちろん、自力で読みこなせればそれに越したことはありませんのでぜひ頑張ってみてください。

この分野にこれから入ってこようとしている人をdiscourageさせないようにあらかじめ断っておくと、実はここに紹介してある本の内容を完全に理解していなくても実用上はさほど困らないかと思われます。東大の理学部情報科学科でも、教科書を全部読むような教え方ではなく、本の中の重要なエッセンスを取り出したレジュメをもとに講義が行われています。このように分野の雰囲気、全体像を知ることは大切です。というのも、本当に困るのは、必要なときにどこに必要な知識があるかわからなかったり、目の前の問題を解決するためにどのような考え方をすべきかを知らない場合だからです。僕自身の経験でも、大学の講義を受けているときにはちっとも身が入らずほとんど理解していなかったことが、数年後、キーワードを知っていたおかげで、本を通して読まずとも読むべき場所がわかり、内容がすいすい頭に入ってくることが多々ありました。授業のありがたみはこんなときに実感できます。

まずはOSから コンピューターサイエンスは、理論的なものから実用に近いものまでとても応用範囲の幅広い分野です。その基礎として、まず第一にデータ構造やアルゴリズムの知識をまず学ぶべきだと思っていたのですが、それよりも先に、コンピュータを動かしているOSそのものの知識が必要だったのです。情報屋さんは日頃OSに慣れ親しんでいるので、ここが情報系以外の人に理解されていないのが盲点でした。例えば、コンピューター上でプログラムがどう実行されるのか?1つしかないCPUで、複数のアプリケーションがどうして同時に動いているように見えるのか?(プロセス、スレッド、CPUスケジューリング)、データがメモリやファイルにどのように保存されているか。システムコールとは何か。オペレーティングシステムについて学ぶには、Silberschatz先生による「 Operating System Concepts」が定番で俗に恐竜本とも呼ばれています。アルゴリズムを学ぶ前に、それを動かす大前提となるシステムがどのように動き、どのような性質をもっているのか。情報科学科では、実際にプロセスやスレッドを生成してシェルを実装してみたり、ファイルの読み書きなどを演習しながら、これらの知識を身につけていきます。

計算の理論
計算の数学的な性質について学ぶことは、計算できるものと、できないものの違いを知るために必要です。また、どのくらいの速さ、メモリ量で計算できるか? それらがどのような計算の仕方で計算できる問題なのか?について学びます。具体的にはオートマトン、正規表現、文脈自由文法、チューリングマシン、計算の複雑さ(computational complexity, NP完全問題など)、判定可能性(アルゴリズムの限界、アルゴリズムで解けない問題というのがある)などが含まれます。MITの屈指の名講義と呼ばれるSipser先生の講義を教科書にした「Introduction to the Theory of Computation」がとても読みやすいのでお勧めです。この本に限っては、日本語訳版も対応の英語付きで丁寧に訳されているので日英での用語の違いに戸惑うこともないでしょう。(注:上記のリンクは初版の日本語訳に張ってありますが、第二版の日本語訳も内容を3冊に分けて出版されています。)計算のクラスを考える必要がある例を挙げると、例えば、正規表現の限界(参考:Leo's Chronicle 「正規表現に見切りをつけるとき」)を考える理由がよくわからなかった場合は、この本の内容が参考になります。



計算理論に関しては、Garey and Johnson本「Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)」も定番中の定番です。読みやすく(易しいという意味ではなく、簡潔という意味です)、NP完全であることの証明パターンや、そのための巻末のNP完全問題のリストが役に立ちます。この本の「Coping with NP-Complete Problems(難しい問題といかに付き合っていくか)」という章のタイトルは非常に有名で、コンピューターサイエンスという学問を如実に表している表現です。




データ構造とアルゴリズム 離散数学とも呼ばれるこの分野。日本語で平易に書かれた教科書もあるのですが(例えば、データ構造とアルゴリズム (新・情報 通信システム工学)や、計算とアルゴリズム (新コンピュータサイエンス講座)など)、やはり、list、hash、red-black tree, ネットワークフロー、グラフ、木構造など主要なデータ構造をカバーしつつ、NP完全性や集合論などの数学的な基礎知識も巻末に儲けられている「Introduction to Algorithms, Third Edition」が便利です。今月には第3版も出るようです。ただし、内容が豊富で記述も多いため、初学者が通して読む目的には向かない本だとは思います。上に挙げたデータ構造について学んだあと、一通りの手法(Greedy(貪欲)アルゴリズム、分割統治法、Dynamic Programming(DP)、近似、Randomizedアルゴリズムなど)を身につけたい場合は、「Algorithm Design」の方が講義用に構成されている分読みやすいかと思います。

連続系アルゴリズム 工学的には、離散値だけではなく、実数データを扱ったり、固有値問題や、偏微分方程式をCG法(共役勾配法)で解く、波形データの解析のために高速フーリエ変換(FFT)を使う、統計量の計算、検定など、計算機が活躍する場面が多々存在します。これらの計算は並列化して高速に計算する需要も大きく、そのような連続系の計算を理解するのに役立つのが「Numerical Recipes 3rd Edition: The Art of Scientific Computing」です。計算を手法とソースコードの双方向から学習できるので、演習向けです。大学の線形代数の内容も、ここにあるような実際の計算までやってみるともっと楽しくなるように思います。最新版ではSVM(Support Vector Machine)やHMM(Hidden Marcov Model)まで言及されているとか。



ハードウェア レジスタとは何か知っていますか? マシン語は? 計算機の中で整数や小数点以下の数はどう表現されているの?などなど、JavaやRubyなど現代の便利なプログラミング言語しか使っていないと見えなくなってしまうハードウェアの世界を学ぶためには「コンピュータの構成と設計~ハードウエアとソフトウエアのインタフェース 第3版 (上), (下)」が良いでしょう。(注:通称パタヘネ本です。ヘネパタはまた別の本のことです)計算機科学はハードウェアとともに進化してきました。最新のCPUの内部構成を理解するには、レジスタ、計算のパイプライン化、割り込み、キャッシュなどの知識が不可欠ですし、これらを学べる本も、他には見当たらなくなってきました。同じメモリアクセスでもキャッシュに載っている場合とそうでない場合(localityの有無)で相当の性能差があるので、CPUの中身でどのように演算が行われているかを知らないと、CPUの性能を最大限引き出したプログラムは決して書けません。一度は目を通しておくべき本だと思います。

情報論理 アルゴリズムを設計したとき、それが正しい結果を出すこと(soundness)、そしてそのアルゴリズムがすべての答えを見つけ出すこと(completeness)を検証します。このようなsoundness/completenessの概念や、述語論理でロジックの等価性を証明したり、逆に背理法などで矛盾を導きだす技術もどこかで学ぶべきだと思います。萩谷先生の情報論理の講義資料が手軽に学べて良いと思っていますが、まとまった英語の教科書があればぜひ教えてください(識者の方)


プログラミング言語 といってもC++やJavaなどの言語の仕様のことではなく、λ計算、型情報などを用いてプログラムやその意味を数学的に表記する(操作的意味論を用いる)ことで、言語の仕様を正確に定義するのに使えたり、プログラムの意味を変えずに最適化(等価変換)する、また、プログラムが安全に実行されるかどうかを検証できるようにもなります。Pierce先生の書いたTypes and Programming Languages(TAPL)が非常にわかりやすく必要な知識がまとめられた本だと思います。

蛇足ですが、近年日本のインターネット界隈でSICPがプログラミング言語を理論的に学ぶ本として話題になっているのですが、コメント欄で住井先生が指摘されているように、SICPとTAPLではカバーしている世界が違います。僕自身も、この本をベースにした演習をしたり、最後の章にあるようなSchemeでSchemeコンパイラまで作った経験から、SICPだけで関数型言語の勉強をした気になってしまうと視野が狭くなるように思います。関数型言語に慣れたり内部の仕組みを知るにはSICP、操作意味論や型について学ぶにはTAPLが良いでしょう。

(注:このプログラミング言語に関する部分は僕の説明や用語の使い方が悪い書き方になっていたため、住井先生の指摘を受けて書き直しました。そのため、下の方にある住井先生のコメントが指していた内容がわからなくなってしまいました。すみません。)



コンパイラ テキストデータを解析するには書かせない技術です。字句解析、構文解析に始まり、構文木から実行したいコードを作成。コード内で変数の生存範囲を見て最適化を施すなどなど。プログラミング言語を作る以外にも、独自データを表現しやすくするためのデータフォーマットを作ったり、ミニ言語を作って日頃の作業を効率化するなり、身につけると非常に強力な武器になります。Compilers: Principles, Techniques, and Tools (2nd Edition)、通称Dragon Bookが一応教科書的なポジションを占めているのですが、最初から読むと構文解析すらできないうちに挫折する可能性が高いので注意。おすすめの読み方は、実際に使うツールに合わせて読むこと。例えば、ANTLRを使うならLL(1)文法を、Lex/Yacc(Flex/Bison)を使うならLALR(1)文法を知らないとデバッグすらままならないので、必要に迫られて本の該当箇所を読む使い方が良いように思います。てっとり早く内容を把握するには、萩谷先生のコンパイラの講義資料を参考に。簡潔にまとまっていて、本を読み解くのに役立ちます。



データベースシステム Webやユーザーからデータを集めて管理、表示するWebアプリケーションでは、データベースの存在が必要不可欠になってきました。バイオインフォマティクスでは、毎日テラバイト規模のデータを扱う技術が必要になってきています。データベースに関する教科書は、以前 Leo's Chronicle:ぜひ押さえておきたいデータベースの教科書で紹介しました。Raghu本 Database Management Systemsがお勧め。ストレージ管理、データベースの同時更新をさばくためのトランザクション管理、これらの技術は年々重要度を増してきていますし、Google File Systemに代表される分散ストレージや、SSDの登場による時代の変化などに対応していくためにも、データベースシステムの仕組みはぜひ押さえておきたい知識です。


ここに紹介した他にも、コンピューターグラフィックス、自然言語処理、機械学習、データマイニング、ウェブ情報処理、ゲノム配列用の文字列検索、索引、圧縮データ構造、Information Retrieval (IR)など、ここでは紹介しきれないほど、コンピューターサイエンスの応用は多岐に渡っています。そして、教科書にある知識を身につけることも大切ですが、より大事なのは、それらを活用して、コンピューターの力を応用できる分野を切り開いていくことだと思います。

(このエントリを書いているうちに、自分の知識の浅さや分野の広さにくらくらしてきました。他にもコンピューターサイエンスの基礎として勉強すべき分野、良い教科書があるよ、という情報を教えていただけると幸いです)

関連

2009年9月17日木曜日

OMakeで快適に論文執筆:TeX編

Windows上でTeXの論文を快適に書くためのTipsを紹介。インストールが必要なものは以下の通り:
  • OMake: ファイルの更新をモニターして自動再ビルドしてくれる優れもの
  • TeX一式: 僕は英語論文しか書かないのでMikTeXを使っています。インストールが簡単
  • pdfopen, pdfclose: Acrobat Reader でPDFファイルを開け閉しめするのに使います(MikTexにも同梱されていますが、back機能が使えるこちらの方が便利。参考:http://magic.aladdin.cs.cmu.edu/2005/07/15/pdfopen-and-pdfclose/)
omakeと、pdflatex, pdfopen, pdfcloseがコマンドライン(コマンドプロンプトやCygwinシェル)から使えるように、環境変数PATHを設定します。

以下は僕の使っているCygwin用の.bash_profileや.zprofileの設定例です:
export MIKTEX_BIN="/cygdrive/c/Program Files/MiKTeX 2.8/miktex/bin"
export OMAKE_BIN="/cygdrive/c/Program Files/OMake/bin"
export PATH=$OMAKE_BIN:$MIKTEX_BIN:$PATH
論文のファイルが以下のように配置されていると仮定します:
project/paper.tex
project/paper.bib
準備として、omake --installで、OMakefile、OMakerootファイルを作成します。
project> omake --install
次に、OMakefileの内容を以下のように編集します。通常はtex -> dvi -> pdf という流れを辿るのですが、より快適に作業するために、pdflatexを使ってtexファイルから直接PDFを生成するように設定しています。
.PHONY: all install clean preview

USEPDFLATEX=true
PREFIX=paper

PREVIEW_PDF=$(PREFIX)-preview.pdf

LaTeXDocument($(PREFIX), $(PREFIX))

$(PREFIX).pdf: $(PREFIX).bib

preview: $(PREFIX).pdf
pdfclose --file $(PREVIEW_PDF) || true
cp $(PREFIX).pdf $(PREVIEW_PDF)
pdfopen --file $(PREVIEW_PDF) --back

.DEFAULT: preview
(注: cygwinを使わない場合は、上記のcpコマンドを、copyに置き換えるとよいです)

omakeを起動します。
project> omake -P
-Pオプションは、texやbibファイルをモニターして、更新があれば即座に再ビルドしてくれるという機能。AcrobatはPDFファイルを開くとロックしてしまいPDFファイルの上書き更新ができなくなってしまうのですが、pdfclose, pdfopenを使うことで、その問題も解決しています。快適。

関連

2009年9月11日金曜日

世界のトップ研究者がデータベースの未来を語る - Claremont Report on Database Research

5年に一度、データベースのトップ研究者が一か所に集まって、データベースの未来について語るThe Clearemont Report on Database Research 2008の記事がCACMに紹介されていました。

The Claremont Report on Database Research
(各研究者のプレゼンテーションスライドはこちらから)

大規模データ処理、RDBMSエンジンの見直しの必要性、クラウド、MapReduce、開発者にとってのデータベースの使いやすさ、新しい言語は?、Uncertain data, プライバシーの管理などなど、DBの将来を見据えた意見が盛りだくさんです。

どの研究者がどの方向性を打ち出しているのかを記事から読み取れれば、もう立派なデータベース通。そして、錚々たるメンバーのなかになぜかTim O'Reillyが混じっている。。。

とにもかくにも、彼らがこうだというと、間違いなくデータベース研究の世界はこの方向に動いていくので要注目です。

2009年9月10日木曜日

研究者の仕事術 - 「いかに働き、いかに生きるか」

「いかに働き、いかに生きるか」

やるべきことが見えてくる研究者の仕事術―プロフェッショナル根性論

最初は「研究者」のための本かと思って購入したのですが、そんなことはありませんでした。会社や組織に縛られて不自由な思いをしていたとしても、自分の人生にとって大切なことはしっかりものにするためのエッセンスが見事に凝縮されています。
研究者として仕事をすべき10の原則
「興味を持てる得意分野を発見する」
「最初は自分で学ぶ」
「師匠を持つ」
「現場で恥をかく」
「失敗を恐れつつも、果敢に挑戦する」
「自分の世界で一番になり成功体験を得る」
「研究者としての自信をつける」
「井の中の蛙であったことに気付き、打ちのめされる」
「すべてを知ることはできないことを理解する」
「それでも、自分の新しい見識を常に世に問うていく」
一見当たり前のようでも、自らが紆余曲折を経てこの原則に辿りつくことの大切さは、研究者として共感できるところが多いです。この本のタイトルが、「研究者のための仕事術」ではなく「研究者の仕事術」となっているように、研究者の仕事の仕方を垣間見ることで、研究者以外の人にもぜひ知ってほしい考え方が詰まっています。

ネットでアメリカの有名大学の講義が視聴できるようになった今、なぜ大学や、PhDが必要なのか?こんな素朴な疑問への答えもここにあります。スキルを身につけるための設備を提供するインフラという意味もありますが、もっと大切なことは「人間的成長」の機会を与える場としての大学の役割です。サーチエンジンの力で目的の知識に辿りつくためのパスは短くなったとしても、この本にあるような、自身の「人間的成長」は、段階を踏んでひとつひとつ登っていかなければなりません。

山積みになるタスク、環境の変化に対する恐れをどう克服するか。自己表現のためのプレゼンテーション力や英語力とは何か。このエントリも、本書のブログをいかに書くかという意見に触発されて書いています。

恐らく島岡先生自身の、Cell, Nature, ScienceにPI(Principal Investigator:主任研究者)としてFirst Authorの論文を一本、指導者としてLast Authorで一本という「成功体験」があるからこそ書ける本ですが、その業績に奢ることなく、不安と闘いながらも「一番」を目指して常に勝負し続けている姿がうかがえます。僕自身も、勝負に出ようとしていたり、壁にぶちあたったり、といろいろあるのですが、この本のメッセージがとても励みになっていて、良いタイミングで読めたことに感謝しています。

最初178ページで2,940円という設定に驚きましたが、内容をみると至極納得。このテーマの自己啓発本としては、本当に大事なことが集約されている一冊です。

関連

License

Creative Commons LicenseLeo's Chronicle by Taro L. Saito is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 2.1 Japan License.