4色定理とコンピュータ

5. 4色定理とコンピュータ 

4色定理とは平面上に地図が書かれていてその国に色を塗るとき, どんな地図でも4色あれば足りるという定理である(一つの国は飛び地を持たないとする). これを証明するのにコンピュータが用いらた。この事について数学者(+世間の人たち?)の間で, 「コンピュータを用いたを証明と呼べるのか」という議論がなされたという事は聞いたことがあるかもしれない. 

コンピュータが用いられたといっても, 決してありとあらゆる地図に対する塗りわけをコンピュータにやらせた, というものではない. 地図の種類は無限にあるので, そんなことは不可能である. そして, 意味のある数学の定理は事実上全てが, 無限の対象に対する言明(全ての自然数は..., 全ての実数は...)だから, コンピュータによって「難しい」定理の証明の 「本質的な部分」がなされる可能性は今も昔も少ない. 

4色定理の場合まず, 何通りかの「部分地図」の形が定義され,

1. どのような地図も必ずそれらのうちのどれかを一部に含む
2. 一方, それらのどれも, 4色で塗り分けられない最小の地図(最小反例)には含まれ得ない,

という事が証明された. 4色定理が成り立たないとしたらその中で国の数が最小の例がある はずだが, 上の2つの事実により, そのような例は存在しないことになり, 定理の証明が完成する. 

上で何通りかの「部分地図」と述べたその部分地図の数が, 最初の証明(AppelとHaken)では1476種類あり, 前者の証明やプログラムも複雑であったため, その正しさに疑問がつけられたという. 後にThomasらによってより単純なプログラムによる証明が得られ, その際の「分類」の数は633種類だった. 

参考リンク:

• http://people.math.gatech.edu/~thomas/FC/fourcolor.html
• http://people.math.gatech.edu/~thomas/PAP/
  

私自身はコンピュータをやっている人間として, このような証明がなされたことに興味を覚えるし, 今後別の, もっと多くの数学者の関心を引いている問題で, 似たようなことが起きても不思議はないと思う。むしろそれが数学の進歩に役に立つのであれば喜ばしいと思う. そもそも命題自身の真偽がわかっていない状態では手段など選ばず, 「後はこれら有限個の場合をコンピュータでチェックするだけ」というところに持ち込んだら, コンピュータを利用するのは自然なことだ. そして4色問題を「有限個の場合のチェックを行えば良い」ところまで持ち込んだのは紛れもなく人間だ。今後別の問題の場合でもおそらくなるするだろう. 

これに対し, 「これを数学の証明と呼べるのか」という批判が起きるのもまた分からないこともない. 要するに証明は「白黒つける」だけが目的ではなく「分かる」事が目的であり, 要するに何を持って「分かった」とするかという問題だ. コンピュータの手続きがYESと答えたからと言って, それを見た人にとって「分かった」という満足が得られないではないかという感覚は理解できる. しかし, チェックのためのプログラムが十分理解可能で信頼に足るものであれば, 「わかった」と言えるのではないか. そもそも人が書いた証明であればそれが1000ページを越えており, 自分ではとても検証できなくても良しとするというのも不思議な話だ. 要するにプログラムを使うと「分かった」とは言えず, 使わなければ「分かった」というような 2者択一ではないということだ. 

そもそも同じ問題に何通りも証明があるのが普通であり, その問題が重要ならば, たとえ先にコンピュータを用いた証明がなされたとしても, より簡潔な, うまくするとコンピュータに頼らずに正しさが確認できるような別証が出てくるのが普通だろう. それは他の問題でも, 最初に長く複雑な証明が提出された後, より本質をついた, 整理された証明が出てくるのと同じ事だ. たまたま最初になされた証明がコンピュータを使った「人」によってなされたというに過ぎない. それを認めずに「コンピュータに先を越された」とか, 「コンピュータに人間が負けた」という類の感情論はナンセンスだ. そのような人にはぜひ以下の事実を思い起こしてもらいたい. コンピュータによる計算の原理も, その物理的な実現方法も, プログラムによる計算の表現方法も, 元はと言えばすべて人間が考えたものだ.

出典：Motivation to learn computer  (一部変更)

 

機械学習(例からの関数近似または補間)

4. 機械学習(例からの関数近似または補間)

機械学習とは文字通り, 「機械による学習」=「学習する機械」の事であり, 擬人化して言えば使っているうちに勝手に頭がよくなる(正解を出し易くなる) コンピュータプログラムの事である. 人間も, ある日足し算の仕方を習うと 足し算が出きるようになり, 廊下を走って転べば廊下を走らなくなる. 元々できなかった事が出きるようになる事を学習というのだから, コンピュータにこれをやらせることができれば実に色々な事ができそうである.
後からがっかりされぬようもう少し現実的な話をしておくと, 典型的な応用としては手書き文字認識などがある. 例えば郵便番号の自動読み取りなどは実用的で, 色々な形で書かれた各数字 $0, 1, 2, \ldots , 9\,$ を, コンピュータに正解ともに覚えさせておく. 実際に与えられる形はそれらと正確に同じものではないが, コンピュータがそれらしいものを正解として出す.

f(File:One1.png) = '1', f(File:One2.png) = '1', 
f(File:One3.png) = '1', f(File:One4.png) = '1', 

f(File:Two1.png) = '2', f(File:Two2.png) = '2', 
f(File:Two3.png) = '2', f(File:Two4.png) = '2', 

• 謝辞: データは, 杉山「統計的機械学習 生成モデルによるパターン認識」のデータを用いた.
  

画像に写っている物体を当てるという, 物体認識の問題でも, あらかじめこの画像は花です, この画像は象です, などとコンピュータに入力しておくと, これまで見たどの画像とも 同一ではない画像に対して, 花だ, 象だと, 答えるようになる.
少し問題を抽象化して考えると, 要するにここでやらせたいことは, ある「関数」の値を, いくつかの与えられた入力と出力の「例」から求める(推測する) 事であると考えられる. 文字認識の例では, 入力が画像であり, 出力が $0, 1, \ldots , 9\,$ のどれかの数字(記号)である. ありとあらゆる画像が「例」として与えられていれば問題はそももそ存在しないが, それは現実的ではない. 例えば1画素が白か黒かの2値であるとし, 画像が16画素x16画素という控えめな大きさであっても, 可能な画像は $2^{256}\approx 6\cdot 10^{26}$ 通りある. したがって, 例として与えられていない入力に対する出力を, いわば「補間」することが問題である. 統計学で, 「回帰」(観測データによく合う関数の形を求める問題)というのを習うと思うが, 目標はそれと同じと言ってよい. 求める関数として一次関数を仮定して, もっともよく合う一次関数がいわゆる回帰直線であり, それを求める手法として最小2乗法がある. 機械学習はそれをもっと複雑な関数に対して行う様々な方法を研究する分野である.
このための手段は非常に色々な方法が研究されていて, 私も専門家ではないのであまり知った顔で書く事はできないが, 例えば, 入力 $x\,$ に対し, $x\,$ に一番近い「例」を見つけてその出力を, $x\,$ に対する出力とする方法, 各文字に対して, 特定パターン画像が発生する「確率」を定義して, その確率がもっとも高いものを選ぶ方法, などがある.
一旦この様に抽象的に問題が(つまり, 入出力例からの関数を補間する問題として) 定式化されると, これらの方式が非常に広い範囲の問題に応用可能だということが分かるだろう. 例えば, 実用的によく用いられているのは, 迷惑メールの分類である. 事前に多くの迷惑メールと, そうでないメールのサンプルを入手しておき, 例として入力しておく. コンピュータは, 中に書かれている文章を人間並に理解して行っているのではなく (これはやりたくてもできない), 多くの場合は, メール全体を単なる単語の集まりとして見ている(この他にメールの差し出し人や, 送信したマシンのアドレスなども情報に含める). 後は未知のメールに対する答えを 「補完」する. 使える方法は, 原理的には手書き文字認識の場合と共通である.
機械学習はその原理から, 人間が「なぜか」できてしまうような処理を, 計算機に真似させる場面でしばしば力を発揮する. 「なぜか」できてしまう処理だから, そもそもコンピュータに正解を計算させる手順もよく分からない, あるいはそもそも正解を厳密に定義しようと思っても, 最後は曖昧な部分が残っていて, 人間にすらそれができないという場合もある. 手書き文字認識も, 画像認識も, 迷惑メールも全てそのような問題である.
私は, 機械学習という, 一見すると非常に高級に見える処理が, 少し冷静に分析すると, 関数の補間という問題に定式化され, そのおかげで非常に広範囲の応用があり, 特定の応用ごとに似て非なる方法を発明しなくてよく, それが「計算機に知能(に似たもの)を持たせる」というゴールに向けた一方であることに 感銘を受けるのですが, どうでしょうか.


出典：Motivation to learn computer

 

乱数(試行)を用いた計算やシミュレーション

3. 乱数(試行)を用いた計算やシミュレーション

手計算で求めるのは割と厄介なのに,コンピュータにとっては非常に簡単になってしまう問題に,色々な確率の問題がある.例えば打率3割の打者が年間500回打席に立つとして,打席連続ヒットが出ない事が15回以上ある,というのは,どのくらいの確率で起きるのか?
コンピュータにこれを計算させるのは非常に簡単で,要は「実際に0.3の確率で「当たり」となるようなクジを500回引く」 ということを何度も繰り返し,「15打席連続ハズレが1回以上ある」回数を数えれば良い. 100000回繰り返して,31234回そのような事があったら,確率はおよそ0.31くらいと言うことだろう(試しに今やってみると0.51と出た.3割打者もシーズン中15連続無安打と言うことはざらにあるということ).
微分方程式の例と同じく,これは「試行」をコンピュータで行うことさえできれば,およそどんな確率でも計算できるし,期待値なども計算できる.例えば様々な要素で株の値段が上下する時に,自分の持っている株全体の値打ち(明日の株価の期待値)はいくらか,などという計算も簡単にできる.
これを用いて,元々は確率の計算ではなかったものを,乱数(試行)を用いて求める計算方法が存在する.例えば3次元空間内で,
\[x^2 + y^2 + z^2 \leq 1, x + y + z \geq \] で表される領域の体積を求めるという問題を考える(手計算でも求められるが,ここで例題として使う).方法は驚くほど単純で,

       1. 点 $(x, y, z)\,$ をランダムに生成する. ただし,
               $0 \leq x \leq 1$, $0 \leq y \leq 1$, $0 \leq z \leq 1$
           とする.
       2. $x^2 + y^2 + z^2 \leq 1$, $x + y + z \geq 1$ を満たしているかを検査
       3. 1と2を多数回繰り返し, 満たした回数の割合を答えとする.

というものである. 要するに,単位立方体の中に点をたくさん投げ込んで,考えている領域の中に入ったら当たり,入らなかったらハズレとして,当たりの確率を計算していることになる.
詳細は省略するが,この方法の発展として,実際に起きやすい点を重点的に生成するという方法(重み付きサンプリング)が存在する.つまり,上記では単位立方体の中に点を一様に生成したが,そうではなく例えば原点の近くによりたくさんの点が生成されるようにしたりすることが可能である.
この方法を用いると,コンピュータを用いて様々な問題の「解」を効率的に探索する事ができるようになる.例えばある関数 $f(x,y, z)\,$ を最大にする $(x,y, z)\,$ を求めたいが,その答えは解析的には求まらないとする.コンピュータを用いてこれを(運が良ければ)求める安直な方法は,色々な $(x,y, z)\,$ をひたすら生成し,その最大値をとるというものである(もちろん必ず正解が求まるという保証はないが).そうする代わりに, $f(x, y, z)\,$ の値が大きい点の付近だけを「重点的に」生成すると言う方法がある.

出典：Motivation to learn computer