https://www.amazon.co.jp/dp/4794220588
とりとめのない読書メモ。
- 1. 思考の基本部品
- 2. 部品としての論理回路
- 3. プログラミング
- 4. チューリングの万能機械
- 5. アルゴリズムと発見的手法(ヒューリスティック)
- 6. メモリ
- 8. 学習できるコンピュータ
- 9. 工学的アプローチの次にくるもの
- 最後に感想
1. 思考の基本部品
ビットとは「違いを表す単位」である。我々はビットを使うことであらゆる信号を2つの種類にわける。ビットでは1と0を用いてその違いを表すが、これも抽象化されたものである。ビットは電圧の高低、光の有無、磁場の向きなど、さまざまなもので表現することができる。便宜的に1と0で表現しているだけで、アリスとボブでもいいし、赤と青でもいい。
機能の抽象化はコンピュータデザインの基本である。抽象化することで、その中身を知らなくても、ブラックボックスやビルディングブロックとして扱うことができる。そして抽象化された機能を幾重にもわたって階層的に積み重ねていくことでコンピュータは作られている。ブール代数においてはAND, OR, INVERTを抽象化して考えることができれば、それを実現する材料が電気なのか棒と糸なのか液体なのかは考える必要がない。
2. 部品としての論理回路
コンピュータデザインは抽象化を基本としているため、配線やスイッチといった具体ではなく論理ブロックの組み合わせとして考えることができる。そして論理ブロックを基本部品として用いることでほとんどあらゆる種類の関数が実現できる。入力に対してどのような出力がほしいのかを定め、それを記述することができれば、AND, OR, INVERT関数を用いて実現することができる。
例:じゃんけん
入力A | 入力B | 出力 |
---|---|---|
グー | グー | 引き分け |
グー | チョキ | 勝ち |
グー | パー | 負け |
チョキ | グー | 負け |
チョキ | チョキ | 引き分け |
チョキ | パー | 勝ち |
パー | グー | 勝ち |
パー | チョキ | 負け |
パー | パー | 引き分け |
バイナリで表現すると下記のようになる。
入力A | 入力B | 出力 |
---|---|---|
11 | 11 | 00 |
11 | 01 | 10 |
11 | 10 | 01 |
01 | 11 | 01 |
01 | 01 | 00 |
01 | 10 | 10 |
10 | 11 | 10 |
10 | 01 | 01 |
10 | 10 | 00 |
さらにこの論理処理が、状態の変化によって変わるのが有限状態機械(有限オートマトン)である。有限オートマトンの例は挙げればきりがないが、以下のようなものがある。
- ダイヤル錠(最後に回されたいくつかの番号は回された順番も含めて記憶している)
- ノック式ボールペン(ペン先が出ている or 引っ込んでいる/ノック回数が奇数回 or 偶数回)
- 入場者数をカウントするカウンター
- 車の走行距離計
- 交差点の信号機
- エレベーターの操作パネル
- 契約書
有限オートマトンの基本は「内部状態が入力によって次の内部状態に移行する」であり、これらはそれぞれの状態遷移図を描くことができる。ということは逆に状態遷移図で表せるものは有限オートマトンである。
有限状態機械はブール論理で表現されたルックアップテーブルとメモリで構成される。メモリはこれまでの履歴(いまどの状態にあるか)を記憶しておく。
コンピュータにおいては、内部状態はレジスタにビット列として格納される。有限状態機械を作るときは、まず組合せ表を作成し、次にビット列を使ってN個ある内部状態をN通りに表現できるようにする。これはつまり、状態遷移図をプログラムで表現する際にはビット演算が有用であるとも言えそう。 例えば信号機のシステムではタイマーがレジスタへの書き込み(による次の状態への遷移)を制御している。デジタル機器においては、このように一定の間隔(コンピューターなので、時間の流れには切れ目が存在する)で状態を遷移させるメカニズムを持つものがほとんどである。 この一定の間隔をクロックレートと言い、理論的にはクロックレートが高ければコンピュータは速く動作することになるが、実際にはレジスタへの書き込みや論理処理にも時間を要するので、上限は存在する。
有限状態機械が有用なのは、シーケンス(連続した処理の手順)を認識できるからである。例えばダイヤル錠では右回しで2→左回しで5→右回しで9の順序でしか開かない鍵などを作成することができる。ただし有限状態機械にも限界はあり、実質上長さに制限のない記憶が必要なものに適用することは出来ない。例えば、回文は文字列の最初と最後が一致する必要があるので回文のすべてを記憶する必要がある。英語の文章の文法においては、that節を用いれば文章の中に再帰的に文章を入れることが文法上無限にできるので文法の正しさをチェックするのは難しい。
3. プログラミング
プログラミング言語とは、コンピュータの中でもっとも抽象化されたレベルである。 コンピュータはブール演算と有限状態機械から出来上がる。人はプログラミング言語を通じてコンピュータに指示を出すので、プログラミング言語とはインターフェースである。
ではコンピュータはプログラミング言語をどのように理解し、実行するのだろうか?
プログラムと、コンピュータを構成する有限状態機械は3つのレベルで結びついている。
- メモリをもった有限状態機械として捉えるレベル(もっとも物理的なレベル)
- メモリに接続された有限状態機械が機械語の命令を実行するレベル
- 高級言語で書かれたプログラムを機械語にインタープリートしながら、CPUが実行するレベル(もっとも抽象なレベル)
大事なことは抽象化された機能を幾重にも積み重ねることでコンピュータが成り立っているということ。
コンピュータのCPUは
という動作を繰り返し実行する有限状態機械である。もう少し詳しく分解すると、
ステップ | 説明 |
---|---|
命令フェッチ(Instruction Fetch) | メモリから次の命令を取得 |
命令デコード(Instruction Decode) | 取得した命令を解析し、何をするべきかを決定 |
実行(Execute) | 命令を実行(算術演算、比較、データの移動など、さまざまな操作を含む) |
メモリアクセス(Memory Access) | データをメモリから読み取ったり、メモリに書き込んだり |
書き込みバック(Write Back) | 結果をレジスタに書き戻し |
というステージになるらしい。
これまで述べてきたように、有限状態機械と記憶領域はレジスタとブール回路を組み合わせて構築できる。コンピュータを制御する有限状態機械は複雑だが、原理的には信号機を制御する有限状態機械と変わらない。それらがそしてまたレジスタと論理回路で構築できるということは、コンピュータは電子工学でも流体技術でも左右に移動可能な棒でも作れるということである。2値を表現できる媒体に過ぎないからである。
プログラミング言語をビット列の表現である命令に翻訳するプロセスは、私達が辞書を引きながら外国語を翻訳するプロセスとにている。実行するたびに逐次辞書を検索して翻訳するのがインタープリタ方式であり、事前にすべて翻訳を済ませておくのがコンパイル方式である。
4. チューリングの万能機械
コンピュータにできることとはなにか?できないこととはなにか?
チューリングマシンとは仮想機械であり、その原理上チューリングマシン以上の計算能力を持ち得るものはこの世に存在しない。どんなコンピューティングデバイスによる計算も、時間とメモリさえ与えられればチューリングマシンによって計算ができる、そんな機械である。それがこの世に1つしか存在しないということは、人間の脳機能もシミュレーションができることを示唆している。
しかし、そもそも世の中には計算が不可能なものが存在する。その代表例がチューリングの停止性問題である。これはコンピュータに限界があることを示しているが、けれども人間とコンピュータを区別するものではない。コンピュータに計算不能で人間に計算可能なものが存在しない限りにおいては。
自然界には計算可能だが膨大な計算時間を要するものが存在する。しかしこれも量子コンピュータが実現することで解決するかもしれない。量子コンピュータがこれまでのコンピュータと異なる点は逐次的な実行では膨大な時間がかかる計算を同時に実行することである。これによって、計算可能だがその実行時間から実用性がなかったものが実用性を帯びてくるようになる。もしかしたら人間の脳のシミュレーションの現実性も出てくるかもしれない。
5. アルゴリズムと発見的手法(ヒューリスティック)
アルゴリズムとは、真なる知識から成り立つ問題解決の手法である。一般的にコンピュータのアルゴリズムはプログラムの形で表現される。
巡回セールスマン問題は最適なアルゴリズムを導き出すことが難しいと言われている問題であり、数千の都市を訪れるような問題は世界最速のコンピュータを10億年稼働させても計算し尽くすことが出来ない。この問題はNP完全問題の代表的なものとして知られている。もしこの問題をより高速に解くアルゴリズムが見つかった場合のインパクトは非常に大きい。なぜなら、巡回セールスマン問題が素早く解ければ、コンピュータが苦手とする他の問題、例えば暗号システムも簡単に解読できるかもしれないからである。
アルゴリズムは常に成り立つことが保証されているが、それが膨大な計算を必要とする場合に、必ずしも問題解決のための最良な手段とは限らない。常に成立するとは限らなくても、多くの場合において正しい働きをすれば十分なケースもある。このような、経験的知識に基づく方法はヒューリスティックという。巡回セールスマン問題についても、ほとんど瞬時に効率的に算出できる発見的手法がいくつか存在する。この発見的手法を応用した代表例がチェスのプログラムである。強いチェスのプログラムにおいては現在の盤面から大まかな形成を判断し、数手先にもっとも形成が有利になるように駒を動かす。また相手も同じ戦略を採用しているという前提に立つ。これらの発見的知識を用いることで必要な処理を絞り込み、現実的なものとしている。
経験的知識と圧倒的な計算量を誇るコンピュータを組み合わせることで、多くの完璧な正解を必要としない問題において有効な解を探し出すことができる。これはびっくりするような良い結果を生み出すこともあれば、とんでもない間違いを犯すこともある。このような形で問題解決を図るコンピュータは、機械というよりも人間に近づいているといえる。
6. メモリ
(具体的なメモリ・データ圧縮・暗号・誤り検知の話題はスキップ)
私達は思い通りにコンピュータを高信頼化することは出来ない。コンピュータは人間が設計したシステムの中でも抜群に複雑なシステムである。わたしたちは抽象化を通じてコンピュータの構成要素を組み合わせ、相互作用を制御することができるが、それらがすべて予想通りに作用し合うことを前提に組み合わせる。設計段階で予期できる範囲での誤りや故障は冗長化などによって回避できるが、すべてを予期するのは現実的ではないからである。
8. 学習できるコンピュータ
人間vsコンピュータの論争においては「コンピュータはプログラマに命令されたことしかできない」という指摘がしばしばある。コンピュータの動作が予測可能であることをもとに人間の優位性を主張しているのだが、実際には場数を踏むごとに改善をするような柔軟なプログラムを作成することは可能である。このフィードバック方式のシステムは
- 到達すべき目標
- 現状と目標との違い(誤り)
- 現状と目標との違いを訂正するために必要な反応
の3つの情報を必要とする。例えば家庭にあるエアコンは室内温度と設定された温度(到達すべき目標)を比較して暖房(冷房)のオンオフを制御している。飛行機の自動操縦装置は所定の飛行コースとのズレを検知して修正する。
一般的な学習モデルを求めて、人間の脳のような構造を持つ計算モデルが作られた。これは人工ニューラルネットワークと呼ばれている。ニューラルネットワークは神経細胞と似た振る舞いをするユニットで構成される。人工ニューロンは同時に何百、何千の入力を受けつけ、総合して1つの出力を出す。また他の人工ニューロンと結びついているため、1つの人工ニューロンの出力が他の人工ニューロンの入力になる。ニューロンとニューロンを結びつける部分には結合荷重が設定されており、結合荷重によって入力信号の影響度の強さ決まる。入力信号の総合的な値が閾値を超えると興奮状態になる。人工ニューロンはこの仕組みによってAND, OR, INVERT関数と等価の機能を持つことができる。
ニューラルネットワークは各ニューロンの結合荷重を変化させることで学習できる。この典型例がパーセプトロンである。パーセプトロンの「到達すべき目標」は正しい結合荷重の設定であり、入力に対して期待する出力信号を出せるように調節を繰り返す。
肯定的な事例と否定的な事例を組み合わせてフィードバックを提示し学習させることは「教師あり」学習と呼ばれる。そして「教師なし」で学習できるニューラルネットワークも存在する。これはつまり自身で教師信号を生成できる自己組織化されたニューラルネットワークである。自己組織化できるシステムとしてよく知られているのは視覚系のニューラルネットワークである。網膜においては外界の光をニューロンで受容し、それを変換して視神経を通じて脳の視覚中枢に送るが、視神経の結合が不完全だと変換されるものが少しずれて視覚中枢に伝えられてしまう。しかし自己組織化できるニューラルネットワーク(アンスクランブラー)においては、入力される乱れた画像情報を処理して、修正済みの画像情報を出力できる。これは画像が相関性を持つ連続領域によって構成されることが多いことを利用し、隣接したピクセルの情報を踏まえて調節する機構である。
9. 工学的アプローチの次にくるもの
脳の構造は工学的手法で設計された計算機とははっきり異なる。これは脳と同じ機能を持つマシンが設計できないことを示すわけではない。しかし、階層的に設計されたマシンを分解するのと同じ方法で脳を理解することは出来ない。
現在のコンピュータやソフトウェアは大きな問題をいくつもの小さな要素(モジュール)に分解しながら、それぞれの働きを注意深く設計し、再帰的に適用して組み立てて成功してきた。しかし人間の脳のように生物学的進化の結果として形成されたものは必ずしも階層構造を持っていないのである。
現代の工学的手法以外で人工知能を創造しようと試みる場合、コンピュータ上で生物学的な進化をシミュレーションするのも1つの方法である。例えば降順ソートを実行するプログラムを作成する場合、工学的アプローチではソートアルゴリズムに基づいて設計する。進化論的シミュレーションで作成する場合、まず母集団となる適当なプログラムを大量(例えば、1万本ほど)に発生させ、それぞれのプログラムのソーティングの結果をもとに成績をつける。次に、他のプログラムよりも成績の良いプログラムから次世代の集団を発生させる。このような世代交代を数千回繰り返していると、完璧にソートできるプログラムが見られるようになるのである。なお次世代を発生させる際には、他のプログラムと組み合わせて有性生殖のような形で交配させることもできる。実際、著者は進化論的シミュレーションによってソーティングのできるプログラムを誕生させた。このプログラムの興味深い点は、誕生したプログラムを著者が理解できなかったことである。その理由はプログラムの命令の実行手順が分解可能な階層構造になっていなかったからかもしれない。
進化シミュレーションだけを用いて「思考するコンピュータ」の問題を解決することは出来ないが、一つの指針にはなる。脳のような複雑な構造を階層的な設計だけで解決するのではなく、組み合わせ的な能力で解決を図ろうとするのは発見的手法(ヒューリスティック)の一種であり、これはうまく機能する。
進化は新しい構造を誕生させるには良い方法だが、誕生したものが「なぜ」そうなるのかには感知しないため、フィードバックによる学習には適していない。一方で人間の脳は進化の産物でもあり、学習の産物でもある。進化と学習は独立したものではなく、共同作用的にからみあっている。ボールドウィン則によれば、進化の欠陥が学習によって正されるとき、生物学的進化はより速く進行する。ある1つの能力が複数の突然変異を必要とする場合、それらは完全なる偶発でおきるだけではなく、もともとある程度の条件を持ち合わせている個体が学習を通じて能力を獲得することがあるということである。
我々は、人間の脳細胞網に見られる結合パターンを模すかたちで、淘汰的に「思考するコンピュータ」を誕生させうる母集団を発生させることができる。また生物の進化と学習の仕組みを完全に把握しているわけではないが、その知識は持ち合わせている。そしてボールドウィン則は、学習を通じて「思考するコンピュータ」を進化させることを可能にする。
最後に感想
コンピュータの基礎としてのAND, OR, INVERTからはじまり、最後には学習する機械(機械学習)、そして工学的設計手法と人間の脳の違いにまで発展する内容で、コンピューターサイエンスの概観を一気に知ることができる本でした。書籍の中で「ちなみに〜〜は可能である」というような記載がでてきますが、正直自分には実現できるイメージが湧かないこともあり、まだコンピュータのちからを引き出せていないということを実感しました。
「機能を抽象化し幾重にも積み重ねて実現する」というのはソフトウェア開発における基礎でもあり、オブジェクト指向やクリーンアーキテクチャなどの設計手法を読みながら想起することもありました。
自分はどちらかと言うとフロントエンド開発のほうが好きで、それは目に見えるものが作れるからなのですが、本来的に「作りたいもの」にフロントエンドとバックエンドの区別はなく、コンピュータの理解をより深めることで、その力を引き出せるようになりたいなと思いました。