A New Approach to Characterising Optimisation Problems Using Programmatic Representation and Complexity Measures

ロボットに迷路を解く方法を教えようとしていると想像してみてください。時には、迷路は単純な一本道の廊下であることもあれば、行き止まりや罠のある、ねじれ、曲がりくねった迷宮であることもあります。コンピュータサイエンスの世界では、これを**最適化（optimisation）**と呼びます。つまり、問題に対する最善の解決策を見つけ出すことです。しかし、ここが厄介なところです。すべての迷路が同じ性質を持っているわけではありません。ロボットにとって解きやすい迷路もあれば、最も賢いアルゴリズムでさえ迷ってしまうような迷路もあります。

ロボットが適切な戦略を選べるように、科学者たちはロボットが走り始める前に、これらの迷路を「特性評価（characterise）」、つまり記述しようと試みます。彼らは、地面がどれくらいデコボコしているか、あるいは行き止まりがいくつあるかといった手がかりを探します。通常、これらの手がかりを見つけるためには、ロボットは数歩進み、周囲を見渡し、地形を測定しなければなりません。これは、洞窟を地図に描き出すために、暗闇の中に偵察兵を送り込むようなものです。しかし、もしロボットが迷路の中に一歩も足を踏み入れることなく、ただその「設計図」を見て、それが解くのがどれほど難しいかを推測できるとしたらどうでしょう？ それこそが、この論文が問いかけている大きな疑問です。論文は、コンピュータコードの中に書かれた「書き方」こそが、その問題がどれほど難しいかという秘密を握っているのではないかと示唆しています。まるで、レシピの複雑さが料理の難易度を暗示するのと同様に。

---

クリスタルボールとしてのコード

この論文の中で、マーカス・ギャラガーとキャサリン・マランは、これらの困難な問題に対する、新しく、少し魔法のような視点を提案しています。地形を測定するために偵察兵を送る代わりに、彼らはコンピュータが問題を作成するために使用する「レシピ」をただ読み解くことを提案しています。

最適化問題をビデオゲームのレベル（ステージ）だと考えてみてください。レベルを作るために、プログラマーはコードを書きます。単純なレベルはこうです。「前進し、穴を飛び越え、コインを拾う」。このためのコードは短く、基本的なコマンドを使用しています。一方で、混沌としたレベルはこうです。「もし空が青ければ、スピードに星の数を掛け、そこから体力の平方根を引く。ただし、帽子を被っている場合のみ」。このコードは長く、乱雑で、非常に多様なコマンドを使用しています。

著者たちの大きなアイデアはこうです。コードが乱雑で複雑であればあるほど、その問題はアルゴリズムにとって解くのが難しくなる。

彼らは、この「乱雑さ」を測定するために、ソフトウェア工学の世界から2つのツールを借りています。

1. ヘイステッド・ボリューム（Halstead Volume）: 段落の中にあるすべての単語や記号を数える場面を想像してください。もし短い物語で単純な単語を使っていれば、カウントは低くなります。もし複雑な語彙や長い文章を持つ小説であれば、カウントは高くなります。この指標は、コード内の「演算子（operators）」（数学記号など）と「オペランド（operands）」（数値や変数など）をカウントします。
2. シャノン・エントロピー（Shannon Entropy）: これは「驚きの要素」を測定することに似ています。もしある段落が同じ5つの単語を何度も繰り返し使っていれば、それは予測可能です（エントロピーが低い）。もし膨大な種類のユニークな単語がランダムな順序で使われていれば、それは予測不可能です（エントロピーが高い）。

実験：単純な円から混沌としたピークへ

この理論をテストするために、著者たちは世界中の科学者が使用している有名な24個のテスト問題のセット（BBOBスイートとして知られる）を取り上げました。これらは、「スフィア（Sphere）関数」（転がり落ちるのが簡単な、完璧に滑らかで丸い丘）から、「ルナセック・ビ・ラストリギン（Lunacek bi-Rastrigin）関数」（何千もの小さな頂点や谷がある、ギザギザで岩だらけの風景）まで多岐にわたります。

彼らはこれら24個の問題のコンピュータコードを書き出し、独自の「乱雑さ」計算機を実行しました。結果は、彼らが期待した通りでした。

• 単純で滑らかなスフィア関数は、最も低い複雑性スコアを示しました。
• ギザギザで困難なルナセック関数は、最も高い複雑性スコアを示しました。
• 実際、ルナセック関数は、そのコード構造においてスフィア関数よりも約9.3倍複雑でした。

彼らはこれを別の種類の問題、つまりニューラルネットワーク（一種のAIの脳）の訓練にも適用しました。その結果、「Tanh」活性化関数を使用するネットワークのコードは、「ReLU」を使用するものよりもわずかに複雑であり、これはTanhバージョンの方が解くのが少し難しいパズルであるという考えと一致していることがわかりました。

魔法のつながり：コードの複雑さがパフォーマンスを予測する

本当の魔法は、これらのコードスコアと、異なるアルゴリズムが実際にどのように機能したかを比較するときに起こります。彼らは、これら24個の問題を解こうとする5つの異なる「ロボット」アルゴリズムのデータを調査しました。

明確なパターンが見つかりました。コードが複雑になればなるほど、ロボットのパフォーマンスは低下する。

それは負の関係です。コードが単純（低いヘイステッド・ボリューム）であれば、ロボットは問題を素早く簡単に解きました。コードが複雑（高いヘイステッド・ボリューム）であれば、ロボットは苦戦したり、時間がかかったり、あるいは行き詰まったりしました。例えば、5次元の問題において、コードの複雑さとパフォーマンスの低下との間には、かなり強い相関関係がありました。

しかし、著者たちはこれが完璧なクリスタルボールではないことにも注意を払っています。コードは非常に複雑だが、ロボットのパフォーマンスはコードが示唆するほど悪くなかったという「外れ値」となる問題がいくつか存在しました。これは、コードの複雑さが優れたヒントにはなるものの、それだけがすべてではないことを示唆しています。

なぜこれが重要なのか

このアプローチの素晴らしさは、非常に高速であり、追加の作業を必要としないことです。問題を理解するための従来の方法は、地形がどのようなものかを見るために、アルゴリズムを何千回も実行して様子を見る必要があります。これは、地図を描くために偵察兵を迷路全体に歩かせるようなものです。

対照的に、著者たちの方法は、迷路の設計図を見ることに似ています。問題を一度も実行することなく、一瞬でコードの複雑さを計算できます。問題のサイズや次元数には関与せず、指示の構造だけを見ます。

著者たちは、この新しい「コードの複雑性」の尺度が、アルゴリズムを設計する科学者たちの道具箱への有用な追加要素になり得ると示唆しています。それは問題を眺める従来の方法に取って代わるものではなく、問題を解き始める前に、その問題がどれほど難しいかを推測するための、新しい超高速な方法を加えるものです。それは、単に指示書を読み取るだけで、コンピュータがその仕事に最適な道具を選べるようにするための、有望な一歩なのです。