Chapter Content
えーっと、 Chapter 4、始めますね。今回のテーマは「難問の本質」について。まず、問題解決に関わる4つの重要な言葉として、問題、プロセス、解答、そして解決策っていうのがありますよね。問題っていうのは、まあ、取り組むべき課題、解決したい状況のことです。で、プロセスは、解決策を見つける方法、つまり外部的なプロセスと、見つかった解決策が出力を計算する方法、内部的なプロセス、この2つがあるわけです。で、解答は、問題が解決されたことを確認する最終的な状態。で、解決策は、問題解決のために使われる内部プロセスを実装する物理的なオブジェクト、みたいな感じです。
例えば、橋で考えてみましょう。問題は、車両や歩行者が安全かつ効率的に川や谷、道路を渡れるようにすること。外部プロセスは、最終的な構造を発見するための試行錯誤ですよね。で、内部プロセスは、橋の各部品が正しく機能するための因果関係です。解答は、車両や歩行者が川の向こう側に見えること。解決策は、橋そのもの、つまり橋と呼ばれる最終的な構造物です。
ディープラーニングのモデルだと、問題は、例えば顔認識。外部プロセスは、良いモデルにたどり着くための学習フェーズ。内部プロセスは、モデルとして具体化されたものが収束後に実行する計算処理。解答は、認識された顔の正しい名前、で、解決策は、学習済みのパラメータ、重みとかバイアスとかを持った、デプロイされたモデルですね。
もう一つ例を挙げると、ルービックキューブ。問題は、6面すべてを単色で揃えること。外部プロセスは、キューブを解くための手順を見つける試行錯誤、または系統的なアプローチです。内部プロセスは、発見された手順、つまり「アルゴリズム」に従ってキューブを解くときに起こります。解答は、最終的な解決状態、つまり各面が単色で構成されている状態。解決策は、他の人がキューブを解くために使用する、発見された手順、例えば紙に書かれた手順ですね。
まとめると、問題は解決する必要がある状況。外部プロセスは、解決策を見つける方法。例えば演繹とか試行錯誤とか。内部プロセスは、見つかった解決策がどのように実行されるか。段階的とか、あるいは何か他の方法とか。解答は、解決を確認する最終状態。そして、解決策は、問題を解決するために展開される物理的なオブジェクト。例えば、紙に書かれたルールとか、ソフトウェアにデプロイされたモデルとか。これで問題解決について議論するための言葉が揃ったので、次は、何が難問を難しくしているのかについて考えてみましょう。
で、何が問題を難しくするのか？人々は、簡単に解決できない問題を「難しい」って言いますよね。すぐに解決策が見つからない状況は、通常、困難な状況と見なされます。でも、計算機科学的には、「難しい」っていう言葉は、もっと具体的な意味を持ちます。つまり、計算量的に難しい問題っていうのは、コンピュータで効率的に解決することが非常に困難、または事実上不可能な問題のことなんです。このような問題は、計算に膨大なリソース、つまり時間やメモリを必要とします。
計算量的に難しい問題は、入力サイズが大きくなるにつれて、難易度が急速に増加します。これは通常、指数関数的な性質を持ち、問題のサイズが少し大きくなるだけで、解決に必要な時間が爆発的に増加します。指数関数的な増加は、紙を何度も折りたたむことで理解できます。折りたたむたびに、層が数枚増えるだけでなく、倍々に増えていきますよね。具体的に言うと、紙を42回折りたたむと、地球と月の距離を超えるんです。
計算における紙の折りたたみは、アルゴリズムが解決策を見つけるために辿る可能性のある経路の爆発的な増加にあたります。難しい問題には、注意すべき要素がたくさんあることを思い出してください。より長い橋は、それが解決する課題に関わる追加の要素を考慮する必要があるため、より多くの部品を必要とします。顔認識が計算量的に難しいのは、顔を顔たらしめる要素の数が膨大だからです。
問題が計算量的に難しくなる根本的な概念は、可能性空間です。可能性空間は、問題に関連する可能性のあるすべての組み合わせ、配置、または状態の集合です。これは、システムが取り得るすべての構成の集合です。チェス盤について言えば、それは駒を配置できるすべての方法です。問題に関連する可能性空間が大きいほど、それを解決しようとするアルゴリズムが探索しなければならない空間も大きくなります。この探索レベルの増加こそが、問題が本質的に難しい理由です。
可能なすべての構成の宇宙で作業するのは非現実的なので、モデルやアルゴリズムは可能性空間で動作するわけではありません。代わりに、難しい問題に対して、可能な特徴の縮小された集合を定義し、その縮小された空間内で動作しようとします。この縮小された空間は、特徴空間と呼ばれ、私たちが問題にとって重要だと考える特徴で構成されています。
冬に手を暖かく保つ問題を考えてみましょう。ランダムなオブジェクトを組み合わせて手に巻き付けるのではなく、考慮に値する属性を考えます。これらは、厚さ、ロフト、吸水性、強度のようなものです。これらの特徴をプロットすると、4つの軸ができます。問題の解決策は、これらの4つの軸によって切り開かれた空間のどこかに存在します。これは、手袋が適切に機能するための適切な材料の組み合わせが、適切な厚さ、ロフト、吸水性、強度の組み合わせを持っているためです。各特徴は、特徴空間に次元を追加し、すべての特徴の組み合わせは、解決策が存在する高次元空間を作り出します。問題が「高次元」であると言うとき、これは、その特徴空間が多くの次元を含み、その解決策がその空間のどこかに存在することを意味します。
問題が本質的に難しいのは、問題の特徴空間のどこに解決策が存在するかを見つけるのが難しいからです。難しい問題の特徴空間は、広大な領域であり、曲がりくねった道と障害物が絡み合ったパッチワークで構成されています。難しい問題では、解決策を見つけられる場所を示す明らかなマーカーはありません。
難しい問題の特徴空間を探索するのが非常に困難で、解決策を見つけるのが非常に難しい理由となる3つの主な難しさの源があります。これらは、1) 特徴空間自体の固有の複雑さ、2) 異なる特徴間の目に見える因果関係の欠如、そして3) 作成可能なすべての組み合わせと比較して、実行可能な特徴の組み合わせ (実行可能な解決策) の数が少ないことです。
特徴空間の固有の複雑さは、その特徴間の相互作用と依存関係から生じます。手を暖かく保つ問題では、厚い素材はより多くの断熱性を提供するかもしれませんが、器用さを低下させる可能性もあります。吸水性の高い素材は、湿気を逃がすのに適しているかもしれませんが、濡れると冷たくなる可能性もあります。特徴空間の複雑さは、必ずしも特徴空間を大きくするわけではありませんが、解決策につながる道を見つけるのを難しくします。複雑な特徴空間では、間違った方向に進むのが非常に簡単です。固有のトレードオフ、つまり、ある特徴の値を大きくすると、ある側面ではパフォーマンスが向上するかもしれませんが、別の側面ではパフォーマンスが低下する可能性があることを考えてみてください。答えを探して複雑な特徴空間を移動することは、何度も何度もピーターから奪ってポールに支払うようなものです。
一般に、特徴の数が増えるほど、それらの特徴が独立している可能性は低くなります。これが、高次元空間が本当に複雑なシステムの特徴であり、それらに関連する難しい問題の特徴である理由です。これも、複雑さが単に多数の部品の問題ではなく、重要なのは、それらの部品間の相互作用である理由です。
問題の難しさの2番目の源は、特徴空間の特徴間の目に見える因果関係の喪失です。手を暖かく保つ問題に戻りましょう。ここでは、厚さ、ロフト、吸水性、強度がどのように連携して問題を解決するかを簡単に想像できます。演繹を使用して特徴空間を移動し、機能する構成にたどり着くことができます。最初に寒さを自然に遮断する動物の皮を取り、それを動物の腱に接続して材料を固定し、目的の形状を保持するかもしれません。動物の皮の2つの層を動物繊維で満たすと、動物の皮だけよりも断熱性が向上することを簡単に推測できます。
手を暖かく保つ問題は、その特徴空間に固有の複雑さがあるにもかかわらず、比較的単純な問題です。これは、特徴の数が少なく (低次元)、特徴間のトレードオフが最小限であれば、人間は単なる演繹によって解決策を見つけることができる可能性が高いことを示しています。最初の解決策は必ずしも最良のものではありませんが、機能します。ここでは、解決策の各部分間の因果関係が明らかであるため、演繹が機能します。
しかし、もっと難しい問題を考えてみましょう。雪だるまを作っている間、手を暖かく保つという問題の解決策を見つけなければならないと想像してください。問題には、さらに多くの制約があります。手を暖かく保つだけでなく、乾いた状態に保ち、雪を扱うのに十分な器用さが必要です。問題に対するこれらの追加の制約は、考慮に値する特徴の数を増やすかもしれませんが、追加のトレードオフをもたらす可能性があります。これにより、特徴間の因果関係が明確ではなくなるため、解決策を演繹する能力が低下し始めます。
特徴空間の固有の複雑さと目に見える因果関係の喪失の間には、密接な関係があります。特徴が相互作用を通じて「対話」するほど、トレードオフが増え、解決策を見つけるのがますます難しくなります。暖かく保ち、器用さの良い素材を選択した場合、濡れやすいことがわかります。耐水性のある素材を見つけた途端、器用さを失います。より多くの制約が矛盾、ジレンマ、パラドックス、そして、実行可能な解決策への道を見つけるのを困難にする泥沼を悪化させます。
難しさの最後の源は、解決空間と呼ばれる別の空間に関連しています。解決空間は、特徴空間 (それ自体が可能性空間の中に存在します) の中に、問題の基準または制約を満たす可能な構成のサブセットとして存在します。簡単に言うと、解決空間は、問題に対する実行可能な解決策を生み出す可能性のあるすべての構成の空間です。
大きな解決空間は、問題を解決できる可能な解決策が多いことを意味し、小さな解決空間は、解決策が少ないことを意味します。可能性空間に比べて解決空間が大きい問題は、探索する時間が少なくなります。なぜなら、抽象的には、解決策に出会う前に、操作する空間が少ないからです。手を暖かく保つことに関連する問題は、問題を解決できる材料の組み合わせが多いため、大きな解決空間を持っています。私たちの祖先は、初期の頃にまともなミトンに偶然出会った可能性が高いことを考えてみてください。
これをルービックキューブのようなものと比較してください。この特徴空間内の点は、26個の「キュービー」の固有の構成であり、各キュービーは位置と向きに関連する一連の値を持っています。この値の組み合わせは、手を暖かく保つ問題の厚さ、ロフト、吸水性、強度の組み合わせのルービックキューブ版です。ルービックキューブの解決空間は、同じ最終的な答えを生み出す可能性のあるすべての可能なアルゴリズムの集合です。
ルービックキューブの解決策を見つけるには、特徴空間の複雑さのために長い時間がかかります。解決策を見つけると言うとき、キューバーがするように、すでに発見されているアルゴリズムに従うことを意味するのではないことに注意してください。一連の手順を初めて発見することについて話しています。ルービックキューブは、その特徴にトレードオフがあるため、特徴空間に固有の複雑さを持っています。あるキュービーを特定の位置に配置すると、以前に配置された1つ以上のキュービーを簡単に台無しにする可能性があります。
それでも、ルービックキューブは本質的に難しい問題ではありません。ルービックキューブは、ある程度の難しさの兆候を示し始める一方で、妥当な時間で解決できる問題として考えるのが最善です。チェスは、さらに大きく、より複雑な可能性空間を持っています。チェスは、本当に難しい問題に近づきます。もちろん、ルービックキューブもチェスも、自然に難しい問題ではありません。冒頭で述べたように、自然に難しい問題は、私たちが作り出したゲームではなく、自然環境の中で提示されるものです。自然に難しい問題は、コンピュータサイエンスの複雑さのクラスにきちんと収まりません。自然に難しい問題の可能性空間は、事実上無限のサイズと複雑さを持っています。しかし、ルービックキューブとチェスの両方は、より単純な問題 (手を暖かく保つなど) から、真の難しさに近づく問題への移行を見るのに適した方法です。
要約すると、問題を定義するために使用する抽象空間の3つの主な側面が、難しさにつながります。1) 空間自体の複雑さ (相互依存の特徴)、2) 空間内の特徴間の因果関係の劣化、そして3) 全体的な空間と比較して、解決空間のサイズの小ささです。本質的に難しい問題は、これらの3つの側面が高度に組み合わさっています。
難しい問題でどれだけの空間を探索しなければならないかを見ると、答えを見つけることができるとは思えません。ルービックキューブには、4300京を超える可能な構成があります。チェスはさらに多いです。それでも、これらは単なるゲームであり、現実世界の場合と比較して次元が縮小されています。人間の発明によって制限されていない自然環境における可能な構成の数は、ほとんど理解できないレベルの複雑さを持っています。したがって、この空間の問題は、ゲームで見られるものとは異なります。
それでも、人間は自然に難しい問題の解決策を常に発見しています。そのような巨大な可能性の空間をどのように制御し、扱いやすくすることができるのでしょうか？
問題が難しいほど、検索はソフトになる
ルービックキューブで発生する組み合わせ爆発のために、考えられるすべての構成を試みる (正しい構成が見つかるまで) 総当たり検索法は、最速のコンピュータを使用しても不可能であることに注意することが重要です。解決策を探して可能なすべての構成を計算するには、数十億、数兆年かかるでしょう。
これが、ルービックキューブを解くコンピュータが、可能性空間をより効果的に検索するために、ヒューリスティックとパターン認識を使用する必要がある理由です。ヒューリスティックは、人々や機械が、明示的な分析を必要とせずに、困難な問題を解決できるようにする一般的な経験則またはショートカットです。チェスのグランドマスターが、一般的なオープニングなどの認識可能なパターンを使用して、最高のレベルでプレイする方法を考えてみてください。これはチェスの駒の明示的な集計ではありません。これは、プレイヤーを良い動きに導くパターンの迅速な認識です。
繰り返しますが、ルービックキューブは本当に難しい問題ではありませんが、問題の難易度が上がるにつれて、問題解決のアプローチがよりソフトになる必要があることを示しています。ここで、ソフトとは、問題構成要素の詳細な分析よりも、ヒューリスティックやパターン認識のようなものに依存することを意味します。問題が難しいほど、可能性空間は大きく、より複雑になり、その空間を検索する必要があります。これは、問題が難しいほど、検索方法について分析的ではなくなる必要があることを意味します。手を暖かく保つ問題では、少しの試行錯誤と演繹を組み合わせることで、簡単に検索できました。雪だるまの問題では、因果関係が劣化しているため、演繹が役に立たなくなり、より多くの試行錯誤が必要になりました。ルービックキューブでは、新しい解決策を見つけるには、さらに多くの試行錯誤が必要になります。系統的に行われたとしても、ヒューリスティックの使用が必要です。繰り返しますが、解決策が見つかるまで可能なすべての構成を試みる総当たりアプローチは実現可能ではありません。
自然に難しい問題、つまり現実生活で見られる問題は、最もソフトなアプローチでのみ解決できると考えるのが妥当です。そしてもちろん、これこそ私たちが目にしているものです。人間は、詳細な分析ではなく、ヒューリスティックとパターン認識を使用して、最も難しい問題を解決するように進化しました。人間が使用する感情的な手がかりと直感は、ヒューリスティックの進化したバージョンです。したがって、難しい問題の元の定義に従うと、計算するのは人間が作ったコンピュータだけではありません。自然も計算します。そして、自然は、最も難しい問題を解決するために何が必要かを示してくれます。システムの外に出て、慎重な分析の領域から離れ、試行錯誤、ヒューリスティック、パターン認識を使用して、広大な可能性空間を探索する必要があります。
だからこそ、ディープラーニングが存在するのです。分析的なアプローチとルールベースのコンピューティングは、本当に難しい問題を解決できません。ディープラーニングは、分析やルールについてではなく、試行錯誤、ヒューリスティック、パターン認識の計算バージョンを取り入れています。ディープラーニングは、潜在的に新しい解決策を見つけるために、ルービックキューブの問題に適用できます。これは、そのようなアプリケーションが、一般的な問題解決に関連する貴重な洞察、戦略、またはイノベーションを明らかにするかもしれないという期待から動機付けられて行われてきました。ディープラーニングは、人間が行うように、ソフトに、外部的に、可能性空間を検索します。
しかし、ディープラーニングで使用される検索プロセスは、人間が使用するものと概念的に似ていますが、見つかった解決策については同じことは言えません。人間と従来のコンピューティングは、他の人が従うことができる理解可能な一連の指示として提示できる解決策を見つけます (つまり、キューバーのアルゴリズム)。しかし、ディープラーニングは、非常に異なるものを生み出します。目に見える一連の手順ではなく、ディープラーニングの解決策は、このように見ることはできません。ディープラーニングによって生成された解決策は、因果的に不透明で、ほとんど解釈できません。つまり、展開された解決策がキューブを解決するときに、ディープラーニングが何をしているのかわかりません。ここで明らかな疑問は、2つの異なるシステム、人間とAIの間で同じ全体的なアプローチが、なぜこれほど異なる解決策を生み出すのかということです？