Articles

どうやってここまで来たのか? アルゴリズムの話

つい最近まで、アルゴリズムはコンピュータ科学者の領域でした。 しかし、今では私たちの生活に入り込み、浸透しつつあります。 アルゴリズムはもう外国語ではありません。 アルゴリズム取引、アルゴリズムバイアス、Facebookアルゴリズム、さらにはアルゴリズム戦争など、これらの用語はすべて近年、私たちのボキャブラリーの一部になっています。 私たちは新しい時代、つまりアルゴリズムの時代に生きている、とまで主張する人もいる。 しかし、アルゴリズムはそれほど新しいものではありません。 私たちは何百年、何千年にもわたって、知ってか知らずか、アルゴリズムを使ってきたのです。 アルゴリズムとは、ある特定の結果を得るために必要な行動を段階的に具体的に記述したものに過ぎない。

事実上、誰かに何かを教えるプロセスはすべてアルゴリズムを使っています。

しかし、アルゴリズムのいくつかの側面は、過去数十年で変化しました。 特に、コンピュータの導入により、今日の多くのアルゴリズムは、過去に想像もできなかったほど劇的に複雑になっています。 では、どのようにしてアルゴリズムは進化を遂げ、現在では昔とは比べものにならないほど高度なものになっているのでしょうか。 その歴史を簡単に見てみよう。

人間の行動を導くアルゴリズム

アル・クワーリズミの(およそ)1200歳の誕生日を記念し、ソビエト連邦にて、1983年9月6日に発行された切手です。 via Wikimedia Commons

アルゴリズムという言葉は、9世紀のペルシャの数学者、ムハンマド・イブン・ムーサー・アル・クワーリズミーの名前に由来している。 彼のラテン語化した名前Algoritmiは「十進法の数体系」を意味し、何世紀にもわたってこの意味で使われた。 現代のアルゴリズムという概念は、19世紀に英語で生まれ、1950年代以降、初めて商業的に利用可能なコンピュータの出現をきっかけに、より一般的に使われるようになった。 ゲラサのニコマスやユークリッドといった学者たちは、当時、近代数学の構成要素を作り出していた。

ゲラサのニコマスがエラトステネスの篩を紹介した。 ふるい」は、今日でも効率的なコンピュータコードの書き方を学ぶ学生たちに使われている。 このふるいにより、素数を特定するプロセスが簡略化された。 素数とは、1より大きい自然数で、2より小さい自然数の掛け算では成り立たない数である。 例えば、4は2と2を掛け合わせることでできるため、素数ではない。 これに対して、5は、5より小さい自然数をかけても5にはならないので、素数である。 最初の数個の素数(例えば2、3、5、7、11、13、17、19、23、29)を特定するのはそれほど難しくないが、大きな素数を見つけるには多くの時間がかかる。 そして、大きな素数は暗号技術に不可欠である。 エラトステネスの篩(ふるい)は、決められた数の集合(例えば1〜10,000)から、素数以外の数を素早く取り除き、素数だけを残す方法を段階的に示したものである。 現在では、このような数字を識別する作業を簡略化するアルゴリズムが数多く提供されている。 エラトステネスのふるい」は、同じ目標を持つアルゴリズム群全体を開始し、素数の検出においてより良く(より速く、またはより少ないステップで)なってきている。

Sieve of Eratosthenes by SKopp at German Wikipedia

Euclid, 上記以外の学者で最近では Nicomachus よりはるかに有名な人は 2 つの数の最大公約数を識別するアルゴリズムを紹介しました。 これもまた、必ずしも簡単な作業ではありませんが、多くの場面で不可欠なものです。 ユークリッドのアルゴリズムは、この計算を容易にするのに役立ったのである。 なぜユークリッドのアルゴリズムが役に立つのか? 612×2006センチメートルの正確な大きさの部屋があり、新しい床が必要だとします。 ユークリッドのアルゴリズムは、その床をきれいに覆うことができる最大の正方形タイルの大きさを見つけるのに役立つ。 アルゴリズムが出した答えは、34センチ×34センチで、18×59枚のタイルをレイアウトすることになります。 もちろん、タイル職人は皆、この答えは間違っている、アルゴリズムがグラウト幅を考慮せず、スペースを空けているから何をやっているのかわからないと言うでしょう。

機械の動作を導くアルゴリズム

その後、数百年にわたって、さらに多くのアルゴリズムが作成され、紙に書き留められました。 そして、それらは個人によって使用され、一歩一歩進んでいったのです。 6354>

Ada Byron, years 4. まもなく世界初のコンピュータープログラマーとなる。 アーティストによる アルフレッド、オルセー伯爵。 Digital image; Somerville College, Oxford – Somerville College, Oxford, Public Domain, https://commons.wikimedia.org/w/index.php?curid=44246375

エイダは魅力的な人物だった。 彼女は1815年、詩人バイロン卿の唯一の正嫡子として生まれた。 彼女は数学に優れた才能を発揮した。 そして、詩を愛する心が遺伝的に備わっていたため、科学と詩の両方をバランスよく発展させることができた。 エイダは自分の考え方を「詩的な科学」と自称している。 数学が得意だった彼女は、その発明のおかげで「コンピューターの父」とも呼ばれるチャールズ・バベッジと知り合うことになる。 二人は仕事上の付き合いもあり、友情を育んでいった。 6354>

Analytical Engineの設計図。 By ArnoldReinhold – Own work, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=69497631

The Analytical Engineは機械式コンピュータ、つまり計算を自動化する機械であった。 彼女が最初にアルゴリズムを書いたのは、この「分析エンジン」である。 彼女の作品は、ベルヌーイ数と呼ばれる特定の複雑な数列を計算するためにエンジンを設定する方法を示す公式であった。 この式は現在、歴史上最初のコンピューター・アルゴリズムとして広く認識されている

Ada は、純粋な数学計算にとどまりませんでした。 19世紀に生きた彼女は、真の空想家であった。

同時代の多くの人々が、最初の機械式コンピュータを主に数字計算機として見ていたのに対し、彼女は計算を行うことの先に何があるのかを問うていたのだ。 彼女は、共同作業の道具としての機械式コンピュータのより広い可能性に興味を抱いていました。 彼女は、計算を自動化するだけでなく、もっと人間に力を与えてくれるようなコンピュータが登場することを期待していたのです。

エイダ・ラブレスによる最初のコンピュータアルゴリズム「ノートG」の図 – http://www.sophiararebooks.com/pictures/3544a.jpg, Public Domain, https://commons.wikimedia.org/w/index.php?curid=37285970

残念なことに、エイダの生前に「分析エンジン」の建設が完了しなかったため、彼女は自分のアルゴリズムが動いているところを見ることができなかったのである。 悲しいことに、「分析エンジン」は今日まで作られていない。 バベッジが設計したもう一つの「差分エンジン」№2は、1991年にロンドン科学博物館によってのみ製作された。 これは、バベッジが持っていた材料と技術を使って、機能することが実証されたものである。 バベッジは、自分の設計を実現することにかけては不運だったようだ。

19世紀は「機械に組み込まれたアルゴリズム」の時代となり、人間のあらゆる行動を自動化するアルゴリズムがたくさん登場しました。 布地に複雑な模様が必要な場合、フランスの織物商であったジョセフ・マリー・ジャカールは、ジャカード織機という解決策を用意していました。 ジャカード織機は、ミシン目の入ったカードで織機の織り方を指示することで、高度な柄を織ることを可能にしたのだ。 同じように、初期の電話交換機では、洗練された機械装置を使って電話をつないでいました。 この機械は、最終的に2人の人間が会話できるように、段階的な指示に自動的に従います。 これらの機械は、織機であれ交換機であれ、当時としては画期的なものであり、今日に至ってもなお、その素晴らしさは変わりません。 その精巧さには感心するばかりである。 しかし、これらの機械はすべて純粋に機械的なものである。 レバー、スイッチ、シャフトでできている。 音も大きい。 6354>

汎用コンピュータにおけるアルゴリズム

電子(非メカニカル)コンピュータにおけるアルゴリズムについて初めて言及されたのは1930年代になってからである。 アラン・チューリングは、個人がどのように計算を行うかを正式に捉えた最初の科学者の一人です。 チューリングの目標は、素数の同定や最大公約数の計算といった特定のタスクに特化したものではなく、一般的なプロセスを捕捉することであった。 そして、その一般的なプロセスを用いて、特定のタスクを実行することができるようにしたのです。 チューリングの概念的な研究は、現在チューリングマシンとして知られているものを開発することにつながった。 チューリングマシンによって、汎用コンピュータが登場したのである。 ここで、汎用という接頭語が重要である。 それまでの機械とは異なり、この新しいコンピュータは、任意の命令セットを実行することができる。 そのため、開発者が予想もしなかったような用途に使われる可能性がある。 つまり。 チューリングの研究は、私たちがアプリケーションをインストールして実行できるようなコンピュータの開発につながった。 実際、あまりに洗練されているため、それらがどのように機能するかを説明することはしばしば不可能です。 20世紀には、多くの人がコンピュータ アルゴリズムをブラックボックスとして考えることを好みました。 アルゴリズムがどのように機能するかを正確に理解する必要はない。 気になるのは、入力(ブラックボックスに入るもの)と出力(出てくるもの)だけである。 このように単純化したのは、ある意味、選択だった。 21世紀になって、いくつかのアルゴリズムでは、これはもう選択肢ではなくなりました。アルゴリズムがどのようにして特定の出力に到達するのか、人間は正確に説明することができないので、これらのアルゴリズムをブラックボックス、あるいは魔法の箱として考えざるを得なくなったのです。 そのようなアルゴリズムの一群が人工知能のアルゴリズムである。 我々はその原理を説明することができる。 例えば、あるアルゴリズムは人工的なニューラルネットワークを使っていると言うことができます。 また、そのネットワークがどのように作られたか、どのように入力が特定の出力に結びついたか、も説明することができます。 しかし、なぜそのような結果が出るのか、機械的な説明だけでは分からない。 エリック・L・ルーミスは、収監の長さがアルゴリズムに依存していたため、COMPASアルゴリズムが彼を高リスクの犯罪者と評価した理由を理解しようとしました。 しかし、それは不可能であった。 アルゴリズムの精巧さには、しばしば圧倒されます。 紙や心の中だけでなく、機械やコンピューター、ロボットを制御しているのです。

それらは小さく、どこにでもあり、少なくともいくつかのケースでは説明不可能です。

アルゴリズムのより正式な定義は、「問題のクラスをどのように解決するかの曖昧でない仕様」または「実行すべき操作の自己完結したステップバイステップのセット」です

www.oed.com/view/Entry/4959

2018年10月の時点で、既知の最大の素数は 277,232,917- 1、桁数は 23,249,425 であり、この数。 この1つの数字が素数かどうかを調べるだけで、現代の家庭用パソコンで6日間もノンストップで計算したそうです。 (https://www.mersenne.org/primes/press/M77232917.html)