しっきーのブログ

ひろいこころで\(^o^)/

世界でもっとも強力な9のアルゴリズム

 米国の大学教授によるコンピュータ・サイエンスのガイド。大方の人はアルゴリズムと聞くとソートプログラムを思い浮かべるだろうが、本書は普段私達がよく使うようなシステムに関わるアルゴリズムを取り上げる。これはアルゴリズムなのか?というトピックもあるが、重要な考え方を扱っていることに変わりはない。

世界でもっとも強力な9のアルゴリズム

世界でもっとも強力な9のアルゴリズム

 平易な言葉で説明できていて、数学的な手法を抜きにすれば、コンピューターの基本的な考え方がわりとシンプルにできていることがわかる。「この本の著者として私がとても驚いたのは、これら大きなアイデアは、どれもコンピュータープログラミングやコンピューター科学の予備知識を一切必要とせずに説明できることだ」と著者自身が述べている。

 プログラミングなどテクニカルなことではなく、アイデアそのものに焦点を当てているので、何より話がとても面白い。コンピューターがちょっと苦手だという方にもおすすめしたい本です。


検索エンジンのインデックス

f:id:skky17:20150714212946j:plain

 私達が普段使っている「グーグル」や「ヤフー」などの検索エンジンが成り立つためには、「マッチング」と「ランキング」が必要になる。「マッチング」とは検索ワードに対応するページを探し出すことで、「ランキング」とはマッチングされたサイトのどれを最初に表示するか順位づけすることだ。

 インデックス(索引)は、あらゆる検索エンジンを支えるもっとも基礎的な概念だ。これは本の索引と同じで、裏側の索引に「りんご 11p、58p」とあれば、「りんご」という文字が本の11ページと58ページにあるということになる。本においてのページをウェブページと考えれば、ウェブのインデックス(索引)も現実の本におけるものと変わらない。

 しかし文章での検索などに対応する必要のあるウェブでは、ウェブページの一つ一つの単語に数字を割り振る。その数字の並びで、文章の繋がりやワード同士の近接性をアルゴリズムで把握できる。

 例えばユーザーが「malaria cause」と2つの単語を検索したとき、検索ワードに含まれている単語が互いに近接しているページのほうが、そうでないページよりも関連度が高いということがわかっているそうだ。つまり、「malaria」というワードと「cause」というワードの位置が近いほうが、検索のランキングでは高評価を与える。

 これが検索エンジンの基本的な仕組みだが、スパムが容易になるなど問題もあり、さらに優れたランキングシステムを作り上げたグーグルが一躍世界に踊り出ることになった。


ページランク

f:id:skky17:20150714213017p:plain

 グーグルより以前の検索エンジンはグーグルが出した4年前の1994年にすでにあった。しかし、グーグルは「きわめて関連性の高い結果を返す超人的な技」のために、4年間のハンデを克服したのだ。「ページランク」という名前は洒落になっていて、ウェブページにランクを与えるアルゴリズムであると同時に、開発者の一人ラリー・ペイジの名前に掛けてもいる。

 グーグルの検索エンジンは、他のウェブページからリンクされると高くなる「オーソリティスコア」を設定し、「オーソリティスコア」の高いサイトをランキングの上位に表示するというものだ。つまり、多くのサイトからリンクされているほど評価されやすい。また、単純なリンクの数ではなく、高い評価のサイトからのリンクほどオーソリティスコアを高く設定することで、リンクスパムの妨害に対処する。

 一方でウェブページのリンクは循環してしまうことがままあり、そうすればスコアは無限大になってしまう。グーグルは、一定期間だけランダムにウェブページを循環する「ランダムサーファー」に調査させることで、日常的にオーソリティスコアを計測している。

 また、実際にはこの仕組をうまく利用して自分のサイトの順位を上げようとするスパムを多く見られるので、日々何らかの方法で対策が打たれている。


公開鍵暗号

 「公開鍵暗号方式法」は、コンピュータ科学の歴史全体でも最も独創的で影響力の強いアイデアの一つだ。これは、発明者の名前にちなんで「ディフィー=ヘルマン鍵交換プロトコル」と言われている。

 この章には、オープンな場で「共有された秘密」を作る方法が書かれている。シンプルな方法なのだけどとても面白いアイデアだ。もし、あなたとあなたの仲間がいて、自分たちの会話がすべて他者に筒抜けだったとする。すべての会話が聴かれている状態で、それを聴いている人にはわからない二人だけの秘密を共有する方法はあるだろうか。実はそれがある。この章ではそのやり方をわかりやすく説明していて、それはインターネットの公開鍵暗号の基本的な仕組みでもある。  

誤り訂正符号

 コンピュータ上でやり取りするデータは、ほんの些細な誤りが含まれていると何の役にも立たないことがある。0.0001%でも正確でなければデータは十分な品質とは言えない。一方で、無線や電線、ハードディスク、CD、DVDなどの物理メディアは、傷やゴミなどの影響で確実にエラーが生じてしまう。しかしある方法を使えば、信頼性の低い通信チャネルにおいても信じられないほど情報の損傷率を低く抑えてデータを伝送することができる。

 コンピューターは、何度も同じ情報を送って例外を排除する「反復トリック」や、例えば数字の「2」を「24953187」などの長い情報にして、データ量は多くなるが欠損しても元の数値がわかるようにする「冗長性トリック」がを使って誤りをなくしている。さらに高度で便利なものになると、特定のデータの和を計算して欠損の個数や場所を特定できるようにする「チェックサムトリック」がある。


パターン認識

f:id:skky17:20150714213055g:plain

 パターン認識は人工知能(AI)という分野の下位領域の一つであり、オーディオ、写真、ビデオなど様々な入力を扱う。コンピュータに人の顔を識別させる研究などに注目が集まっているが、「パターン認識」の基本的な方法は、大量の「分類ラベル付きデータ」をコンピュータに読み込ませることだ。

 例えば手書きで書かれた数値をコンピュータに認識させようとするとき、ある数字とある数字が同じものかどうかは、割合(パーセンテージ)で示すことができる。手書きには様々な癖があるが、それでも数字の「3」と「3」同士と、「3」と「7」の場合だと、前者のほうが違う割合が少なくなり、後者は違う割合が大きくなる。このようにしてコンピュータはイメージの違いを計測する。

 人の顔など高度な認識をしようとする際には、コンピュータの処理を人の脳に近づけようとしている。人間の脳機能であるニューロンに着目し、それをシミュレートした数学モデルである「ニューラルネットワーク」が有効な手段とされている。ただ割合を出すだけではなく、その結果に正負の重み付けをして計算し、最終的な判断を出力するという人間の脳に近いモデルになっている。


データ圧縮

 コンピューターは「ロスあり」と「ロスなし」の異なるタイプの圧縮を使っている。「ロスあり」の圧縮はわかりやすい。画像や動画などの容量を減らすと荒くなってドットが見えるようになる。一方で、「ロスなし」の圧縮は見えないところで頻繁に行われている。

 ほとんどの情報には、たくさん登場するものに長いデータが割り当てられていたり、省略した形で表すことのできる繰り返しが見つかる。それらにルールを決めて圧縮することでデータの受け渡しを快適にし、受け取った側はそれを解読して元のデータに解凍すればいいのだ。


データベース

 データベースには、銀行を例に出せば容易に納得できるように、決して間違いがあってはならない。送金したはずのデータが何かの間違いで消えてしまったら大惨事だ。処理の途中に何らかの原因でクラッシュしても、どこまで処理が実行されたかわかる仕組みが不可欠になる。

 その仕組は、私達が使う「to-doリスト」に似ている。指示された通りの処理をそのまま行うのではなく、何かを実行する前には「to-doリスト」を必ず参考にし、トランザクションという確認のためのデータ処理を行うことで、重要なデータベースの一貫性が確保されている。


デジタル署名

 ネットにおいて、そのソフトをインストールしても大丈夫かなど、信頼性は非常に重要になってくるが、数学的な処理によってデジタルの世界でも個人の「署名」を作り出すことができる。

 署名のセキュリティーは、掛け算をするのは簡単でも、その因数分解の解を導き出すのは難しいというところに拠っている。計算する方法はあるのだが、現在のコンピューターの処理能力ではそれを導き出すのに何億年もかかってしまう。しかし、そのような署名の仕組みが本当にセキュアなのかはコンピューター科学者が頭を悩ませるところだ。もし誰かが何らかの形で大きな数を因数分解する方法を編み出せば、現在のデジタル署名システムの多くが危機に晒されてしまう。


決定不可能性

 アルゴリズムとは少し違うが、コンピューターの重要な考え方だ。「コンピューターには決して解決できない問題があ」り、これは数学の証明と同じレベルの厳密さで証明し得る。実際の証明は簡単な背理法なのだが、本書で丁寧に解説されているのでぜひ手にとって読んでみて欲しい。

 しかしここで重要なのは、人間の脳がもしコンピューターによってシミュレートできるものだとすれば、コンピューターの限界は人間の限界でもあるということだ。この証明はアラン・チューリングが1937年に書いた決定不可能性の論文でされたのだが、当時チューリングがコンピューターと呼んでいたのは紙と鉛筆で何らかの計算をする人間のことだった。当時の研究の先駆的な意味が、人間の思考プロセスとコンピューターが近づいた現在において、実感を持って感じられるようになってきた。コンピューターの限界はすなわち私達の限界ではないかという恐怖が説得力のあるものになったのだ。



関連項目