第2章 コスト関数とは何なのか

第1節 アニーリングマシンとコスト関数の関係

最適化問題を解くためには、事象を数値で表現する必要があります。ゲームの世界でキャラクターの強さを可視化するためにレベルやヒットポイントで数値化するのと同じように、問題が解決する状態を最適解として数値化するために、式を立てていきます。式を立てるために、複雑な問題では模型(モデル)を使って課題をできるだけ数値化しやすく置き換えていきます。アニーリングマシンでは、イジングモデルの総エネルギーを式に表し、「最適解がエネルギーの最低の状態にある」とした上で問題を解く仕組みです。

数学を中学校・高校で学習している時に、はっきりとは先生は言いませんが、勝手に$x$だの$y$だのに世の中を当てはめてしまって、法則の中で法則がどのように変わっていくかを机上で確認していく取り組みを行ってきました。アニーリングマシンではないふつうのコンピュータも、あるルールのもとで計算を繰り返しているのでその点は同じですが、アニーリングマシンの場合は、解きたい問題が「エネルギーを持った何か」であるといったとらえ方をしなければいけない点が、少し頭の切り替えが必要なポイントです。その「何か」が、「イジングモデル」なのだという事実を、読者はなんとなくわかってくれていると思います(アニーリングマシンとイジングモデル参照)。しかし、このモデルがどう動くか、頭の中で動かすことは簡単なことではないと思います。それでも、エネルギーが高い場合や低い場合があるんだな、という場合に、そのエネルギーのグラフならなんとなく想像することならできますね。

例えばこういう形かもしれません。

でも、私たちはこのような適当にぐにゃぐにゃしたグラフを描くことを求められているわけではありません。グラフの形は式によって特定されます。

高校数学で習った知識を思い出してみましょう。

$y=x^2$のグラフ,$y=-x^2$のグラフ

このように、式が決まるとグラフの形が決まるという事実が前提にあります。ですが、正しいグラフの形はたった1つではありません。私たちが求めたいのは、基本的にはたった1つの最適解(あるいはそれに近いもの=近似解)なので、そのような解が導ける式であれば多少、その他の部分が違っていてもかまわないのです。最適解とは、グラフの頂点にあたるエネルギーを与える時の変数の組合せのことです。

たとえば、求めるイジングモデルのエネルギーが$H=3 \times s_1s_2 - 2 \times s_3s_4$だったとします。$s_n$はスピンで$+1$か$-1$がはいります。そのような$H$が最も低くなる時、$s_1,s_2,s_3,s_4$がそれぞれどのような値を取るのか、が解です。答えは順に

$$ (+1,-1,+1,+1) \\ (-1,+1,+1,+1) \\ (+1,-1,-1,-1) \\ (-1,+1,+1,+1) $$

のいずれかです。これらはどれも$H=-6$となる組合せです。

この式で表される問題があったなら、エネルギーが最も小さくなる($-6$を示す)場合のスピンの組合せが、知りたい最適解です。

このように、コスト関数が決まれば、範囲内のどこかが頂点になり、それを与える時の変数の値が最適な組合せとなるという手法です。しかし、1つの事象を最適化問題として解くときに、コスト関数の形はたった1つではなく、式を立てる作業はある程度創造的な作業となります。実際に作ってみて慣れていくことでどういうことかを理解するほかはありませんが、基本的には頂点が真実に正しい値である必要がありますが最適解を与えるエネルギーが「グラフの中で最も低いところ」なのか「最も高いところ」なのかは式を作る人が決めることになっています。それどころか、頂点以外の傾斜の部分の傾きや、山がいくつあるかも、式を作る人の創造する力にかかっているのです。そのため、正しいコスト関数が唯一の絶対的な式で限定されるとは言えないのです。本当のところを言うと、組合せ最適化問題の解は曲線上ならどこでもいいわけではありません。解は、飛び飛びに存在しているため、曲線上の解と解の間の部分は、解になり得ぬ値の集合になっているのです。詳しくは第3章で説明します。

さらに、最適化問題をエネルギー関数で解くというこの手法について、前提として知って頂きたいことがもう1つあります。それは、「最も正しいただ一つの解を得る」ための方法ではないということです。組合せ最適化問題は、とても解くのが難しい問題に分類されており、従来のコンピュータで何年もかけて解く(時間を犠牲にする)か、近似解法と呼ばれる方法で解く(精度を犠牲にする)ことが必要です。

アニーリングマシンで最適解を得るという手法は後者であり、最も正しいたった一つの解を得ることを保証しません。そのため、暗号化技術のような、厳密性を必要とする課題には向いていないのですが、「けっこういい解」であれば十分成果があるというような課題には向いています。