世界でもっとも強力な9のアルゴリズム 6章 パターン認識
機械が得意なことを対象としていた今までの章と異なり、この章ではコンピュータが苦手な文字認識や顔認識といった、パターン認識について説明する。
主に3つのアルゴリズムを説明しており:
多次元の数値化を行い、既に分類されているサンプル値を分布させ、判定したい対象との距離によって分類を判断する最近傍法
対象について、定量化された2項の質問を繰り返して、判定時の閾値の精度をあげていく決定木
決定木に似ているが、自分自身が次の接続先に対して信号を出すかどうかを受け取った信号の大きさと閾値を比較して、次々に信号を送っていくニューロンを模したニューラルネットワーク
となっている。
これらパターン認識は、今までコンピュータが苦手としてきたチェスや画像認識といった分野を開拓し、夢とされていた人工知能の発達にも寄与しているだけではなく、AmazonやNetflixなでのサービスでのレコメンド機能などにも応用されている。
世界でもっとも強力な9のアルゴリズム 5章 誤り訂正符号
コンピュータのもっとも基本的な3つの機能、計算、保存と伝送の後者2つに関わるデータの信頼性の向上については、ベル研のシャノンやハフマンに始まり様々な科学者が貢献してきた。
この章では:
・同じデータを複数回送り、平均を取る「反復トリック」
・数字を全て英語(one, two…)にするなどの符号化することによる「冗長性トリック」
・元のデータに代数操作を加える「チェックサムトリック」
・複数のチェックサム(単純総和と階段総和)を組み合わせることによる「複数誤り検出可能なチェックサム」
・二次元に元のデータを並び替えて、魔法陣のように縦横にチェックサムをとり、誤りがあったポイントの検出及び訂正が可能な「ピンポイントチェックサム」
を紹介している。
ベル研に端を発っした、誤り訂正符号の研究は、リードソロモン符号や、CRC-32といったチェックサム、MD5やSHA-1のような暗号学的ハッシュ関数を用いたものなど、今でも研究が進んでいる。
感想:
数学的なトリックとして、代数学を使用するため理解が簡単だった。最後の節に最新の数学とこの技術の関係の目配せがあって良かった。
世界でもっとも強力な9のアルゴリズム 4章 公開鍵暗号
インターネットの様な、経路の安全性が確保できない伝送路で秘密の鍵を交換する方法として、公開鍵暗号というアルゴリズムで、何種類かの変種が、ディフィー=ヘルマン法やRSAといった形で考案されてきた。
これは、秘密通信を行う2人同士が、それぞれが持っている秘密の数値(本の中では絵の具の色)と、公開された数値をそれぞれが掛けあわせて、その数字を公開すると、更に2人が自分の秘密の数値と空いての公開数を掛け合わせることで、共通の秘密の数値を作り出すことが可能になる。
この数字から秘密の数字をは、本来は大素数同士の積の素因数分解の困難性(NP性)によって担保される。
感想:
いくつかの要素を端折ったため、数学としての面白みにかける章になってしまっている。
大素数同士の積には、素因数分解のむずかしさとともに、この積を作成を可能にするのは2つの素数以外には存在しないという点が、
RGBの和がたまたま合えば、混合色は無限につくることができる2色の組み合わせがある。
また翻訳としては、復号化という間違った用語を使用している点が残念だ。
世界でもっとも強力な9のアルゴリズム 3章 ページランク
グーグルがaltavistaの検索エンジンから遅れること3年、サーゲイブリンとラリーペイジが立ち上げたグーグルでは、そのページの持つ価値をハイパーリンクに着目して計量化するという手法を実装した。
あるページがどれだけリンクされているかを判断基準とするページランクトリック、どれだけ価値の高いページからリンクされたかを判断基準とするオーソリティトリックは循環参照に対して誤って高いランクをつけてしまうという欠点を持っていた。
それを、あるページから平均で7リンクほどランダムにアクセスしたあとに、別のページにランダムに移動してまたランダムウォークを始める、というのを繰り返して、各ページを訪れた回数をランクとするという、ランダムサーファートリックによって、解消した。
世界でもっとも強力な9のアルゴリズム 2章 検索エンジンのインデックス
Altavistaが初めて実装した検索エンジンはマッチングという考えを導入して、
単純に世界中のページに対して、有無を調べると膨大な時間がかかる単語の検索を、
予め全ページのインデックスを作成しておくことによって実現した。
また、位置情報(ある単語のページ内での出現順)を合わせて記憶することにより、
2つ以上の語の関連検索について、より検索者が求めているページに近しいかどうかを、
発生順の近接度によって機械的に判定している。
更に、対象であるHTMLのタイトルや本文といったタグについても位置情報を把握することにより、
その検索語がタイトルに現れたのか、本文に現れたのかを判別することができる。
世界でもっとも強力な9のアルゴリズム 1章 イントロダクション
実際の定義は10章に譲るとして、まず本書ではアルゴリズムについては、コンピューターに特定の問題を解決させる上での「非常に正確なレシピ」と定義する。
この本では中でも偉大なアルゴリズムを9つ取り上げようと思うが、まず偉大さの基準として「巧妙なトリックに支えられている」こととし、またインフラやコンピューターの設計自体に関わる(例えばソート処理や最短経路問題などの経路アルゴリズムなど)アルゴリズムよりも、一般庶民が半ば無意識に使用しているサービスなどで用いられているアルゴリズムを取り上げる。
この本を読んで、コンピューターで動いている機能の裏側を理解することで、例えばGoogleを使用して検索する際の調べ方についてより上手になるようになるかもしれないが、それはこの本が期待していることの本の一端であり、それ以上に天文学の僅かな知識だけでも夜空を眺めるのが楽しくなるように、コンピュータという最も普及しながら最も不可思議なブラックボックスに触れる際の楽しみが増すだろう。