『世界でもっとも強力な9のアルゴリズム』（ジョン・マコーミック）

　「この本の著者として私がとても驚いたのは、これら大きなアイデアは、どれもコンピュータプログラミングやコンピュータ科学の予備知識を一切必要とせずに説明できることだ。（中略）どの場合でも、全体を機能させるための鍵を握っているメカニズムは、普通の人の概念だけを使って説明することができた」（Kindle版No.4132）

　ネットで通販するとき、私たちは人類が生み出した最も偉大なアイデアのいくつかを知らないうちに使っている。検索エンジン、データベース、誤り訂正符号、公開鍵暗号、デジタル署名。これら傑出した「アルゴリズム」の仕組みを、コンピュータサイエンスの知識がない読者にも理解できるように解説してくれる一冊。その電子書籍版を、Kindle Paperwhiteで読みました。単行本（日経BP社）出版は2012年7月、Kindle版配信は2013年10月です。

　今日のコンピューティングで用いられている重要なアルゴリズムについて解説した本は数多く出版されていますが、いずれも「理解するためには、ある程度プログラミングの知識と経験を必要とする技術書」であるか、「まったく比喩だけで説明し、表面的に分かったような気にさせる雑学本」であるか、そのいずれかに偏っているように思えます。

　本書の特徴は、この中間、つまり「ごく日常的な概念と算数の知識だけを使ってアルゴリズムの核心を説明し、実際にそのアルゴリズムがどう機能するか手計算で確かめさせる」というところにあります。

　特に後半の特徴は素晴らしく、簡略化されたバージョンとはいえ、読者は実際にデータを圧縮復元してみたり、二つの小さな数字をキーにして暗号復号を試してみたり、シンプルなニューラルネットを書いてみたり、素朴なデータベースを修復してみたり、そんな体験を得ることが出来るのです。それも、プログラミングの知識なしに。

　もちろん面倒なら読みとばしてもいいのですが、自分でやってみることで、アルゴリズムの背後にある驚くほどクールなアイデアを深く理解できるようになります。そして、「気分が乗ってくる」のです。

　「この本で説明するすべてのアルゴリズには、核心の部分の巧妙なトリックによって全体が支えられているという特徴がある。そのトリックを解き明かしたときに「アハ体験」が得られる分、私からすると、この種のアルゴリズムは説明していて気分が乗ってくるアルゴリズムだ。願わくば、読者にとってもそうであってほしい」（Kindle版No.236）

　さて、本書でまず最初に取り上げられるのは、今日のインターネット検索エンジンを支えている重要なアルゴリズムである、インデックスとページランクです。

　インデックスに位置情報を組み込む、ページはハイパーリンクを介して他のページにその「評価」の一部を分け与える、といった中核的なアイデアが、どのようにしてあのグーグルが成し遂げた驚くべき成果を生むのか、詳しく解説されています。

　信頼性の低い（エラーが発生する）通信回線上で、信頼性の高いデータ通信を実現する誤り訂正符号。回線容量やディスク容量を大きく節約するデータ圧縮。

　流れるデータを誰でも見ることが出来るインターネットを介して、一度もオフラインで会ったことのない二人（例えば通販会社と利用者）が秘匿通信を行うという、不可能とも思える難事を解決してのけた公開鍵暗号。

　そして、手書き文字入力から大規模画像解析まで広く用いられているパターン認識のアルゴリズムとして、最近傍法、決定木、ニューラルネットワークが解説されます。

　「最先端の計測方法を備えた最近傍識別器は、手書きの数字では99.5パーセントを超える精度を誇る。（中略）エレガントに感じられるシンプルさとめざましい処理性能を兼ね備えており、コンピュータ科学の驚異と言ってよいだろう」（Kindle版No.1904）

　「重要ポイントは、決定木自体の細部ではなく、決定木全体が、約1万7000のウェブページから得た訓練データをもとに、コンピュータプログラムによって生成されたものだということである」（Kindle版No.1957）

　「自分の脳のなかに入り込んで、ニューロンを結ぶ接続の強さを分析できたら、大多数はでたらめに見えるだろう。しかし、アンサンブルとして働くと、これらのでたらめな強さの寄せ集めが、知的なふるまいを生み出しているのである」（Kindle版No.2161）

　データベースを支えるアルゴリズムとしては、ログ先行書き込み、二段階コミット、リレーショナルデータベースが解説されています。

　「どんな処理の途中でもエラーを起こす可能性のあるハードウェアを使って作られていながら、データベースは効率がよく頑丈で頼りがいがある。オンラインバンキングなどを通じて、私たちはデータベースのそういった性質を当然のものと感じるようにさえなっている」（Kindle版No.3050）

　データベースの驚異的な信頼性と一貫性を支えているアルゴリズムの巧妙さは舌を巻きほど。こういうことを分かりやすく解説してくれる本は少ないので、本当に助かります。

　「初心者向けのデータベース入門書はあふれかえるほどあるが、それらは一般にデータベースがどのような仕組みで動作するのかを説明するのではなく、データベースの使い方を説明するものである。大学レベルの教科書ですら、データベースの使い方に傾斜しがちだ」（Kindle版No.4262）

　そして、デジタル署名の解説を経て、アルゴリズムの「決定不能性」とは何かを読者に自分で確かめさせる、という途方もない難事に挑みます。

　「コンピュータプログラムによって書き出すことが本当にできない単純で正確な英文が存在する」（Kindle版No.3712）

　「ほかのプログラムを分析し、そのなかに含まれていてプログラムをクラッシュさせる原因になるようなバグをすべて見つけ出すプログラムは書けない」（Kindle版No.3956）

　といった直観に反することを順を追って証明してゆきながら、「チャーチ＝チューリングのテーゼ」が何を意味しているのかを解説するのです。

　最後に、これらの革命的なアルゴリズムがすべて前世紀に生まれたことを指摘し、今後このような偉大なアルゴリズムが生まれる余地はあるのか、という問題を論じます。著者の考えはこうです。

　「今後は２つの効果が競合し合うようになる。ときどき新しいテクノロジーが新しいニッチを作り出し、新しいアルゴリズムが生まれる余地を生む一方で、コンピュータ科学という分野が次第に成熟してチャンスが狭まっていく」（Kindle版No.4086）

　「私はバランスを取ってこれら２つの効果が互いに打ち消し合うだろうと考えることが多い。すると、今後、新しい偉大なアルゴリズムはゆっくりしたペースながら、着実に生まれてくるはずだ」（Kindle版No.4088）

　本書では、今後新しく生まれてくる偉大なアルゴリズムの候補として、人工知能、ゼロ知識プロトコル、分散ハッシュテーブル、ビザンチンフォールトトレランス、などを挙げています。

　ところで、「ビットコイン」って、偉大なアルゴリズムなんでしょうか？

　というわけで、プログラミングの知識なしに、アルゴリズムを理解させようという野心的な一冊です。個人的に感心したのは、例えば本書で使われている「絵の具の混合という形で一方向性関数を表現する」といった比喩が、単なる比喩やモデルにとどまらず、アルゴリズムを実現する手段として実際に有効だと自分で確かめられるように書かれていること。アルゴリズムはコンピュータの物理的性質に依存しない、という本質を見事に示してくれます。

　「プログラミング言語の知識はコンピュータ科学者にとって必要不可欠である。しかし、それは単なる前提条件に過ぎない。研究者の主要な課題は、アルゴリズムを発明、修正、理解することである。この本の優れたアルゴリズムを見たあとは、読者もこの区別を今までよりもしっかり理解していただけたことと思う」（Kindle版No.4161）

タグ：その他（サイエンス）