Ctrl+K

バイナリエンコーディング

6. バイナリエンコーディング#

6.1. 導入#

連続変数をバイナリ変数によって離散近似する手法の一つに， バイナリエンコーディング （二進符号化）がある．

数理最適化モデルを QUBO などのバイナリ最適化問題へ変換する際には， もともと連続値をとる変数を，有限個の候補値のいずれかとして表現する必要がある． 最も素朴な方法は，値の候補を等間隔に並べ， その中からちょうど一つを選ぶ形で表す方法である． しかし，この方法では高い精度を得ようとすると候補数が急増し， それに伴ってバイナリ変数の数も大きくなってしまう．

そこで有力な選択肢となるのが，二進数展開を用いたバイナリエンコーディングである． バイナリエンコーディングでは，必要な精度に対して少ない変数数で表現できることが多く， QUBO 定式化における変数削減の観点から重要な手法である．

まず比較対象として，等間隔の刻み幅に基づく単純な離散化を考える． 定数 \(r_j\) は \(0\) 以上 \(1\) 以下の値をとり， 最小ステップ幅を \(\Delta r\) とすると，次のように書ける．

(1)#\[r_j = j \Delta r \quad \left( j \in J = \{0,1,\ldots,K\},\; K = \frac{1}{\Delta r} \right)\]

このとき，連続変数 \(w_i\) を離散変数 \(x_{i,j}\) によって次で表す．

(2)#\[w_i = \sum_{j \in J} r_j x_{i,j}\]

ここで \(x_{i,j}\) は， 「変数 \(w_i\) が候補値 \(r_j\) を選ぶかどうか」を表すバイナリ変数である． 従って，各 \(i\) に対してちょうど一つの候補値を選ぶように， 次の制約を課す．

(3)#\[\sum_{j \in J} x_{i,j} = 1, \quad \forall i \in I\]

これは one-hot エンコーディングに対応する表現であり， 分かりやすい反面，刻み幅を細かくすると必要な変数数が増えやすい．

6.2. バイナリエンコーディングの定義#

上の one-hot 型の離散化に対して， よりコンパクトな表現として二進数展開を用いる方法を考える． ビット数を \(B \in \mathbb{Z}_{\geq 1}\) とすると， 各桁の重みを次で定める．

(4)#\[r_j = 2^{-(j+1)} \quad (j \in \{0,1,\ldots,B-1\})\]

このとき，連続変数 \(w_i\) は次のように近似される．

(5)#\[w_i = \sum_{j=0}^{B-1} 2^{-(j+1)} x_{i,j}\]

ここで \(x_{i,j} \in \{0,1\}\) は， 二進数表現における \(j\) 番目のビットに対応する． one-hot 型の離散化とは異なり，各ビットは独立に 0 または 1 をとればよいため， 「ちょうど一つを選ぶ」という次の制約は不要である．

(6)#\[\sum_j x_{i,j} = 1\]

この表現では， \(B\) 個のバイナリ変数によって \(2^B\) 通りの値を表現できる． 従って，one-hot 型のように候補値の数だけ変数を用意する方法と比べると， 必要な変数数を大幅に削減できる可能性がある．

6.3. 平坦化の必要性#

QUBO 形式へ変換する際には， 添字を複数もつ変数を一次元に並べ直す，いわゆる 平坦化 が必要になることが多い．

例えば，変数 \(x_{i,j}\) が添字 \(i\) と \(j\) をもつとすると， QUBO 行列の行・列番号に対応させるために，これを単一添字 \(k\) へ写像する．

one-hot 型の離散化で \(j \in \{0,\dots,K\}\) とすると， 例えば，次のように定義できる．

(7)#\[k = k(i,j) = (i-1)(K+1) + j\]

添字の開始を 0 にするか 1 にするかは実装依存であるが， 重要なのは \((i,j)\) を一意に \(k\) に対応づけることである． このとき，変数の総数は次で見積もれる．

(8)#\[|I \times J| = |I|\,|J| = N(K+1)\]

この添字を用いて \(x_{i,j}\) を \(x_k\) と書き換えると， 目的関数は一般に次の形に整理でき，QUBO 行列 \(Q\) を構成しやすくなる．

(9)#\[\sum_{k_1,k_2} Q_{k_1,k_2} x_{k_1} x_{k_2}\]

また，必要に応じて単一添字 \(k\) から元の添字 \(i, j\) を復元することもできる． 例えば，次のように表せる．

(10)#\[\begin{split}i &= \left\lfloor \frac{k}{K+1} \right\rfloor + 1, \\ j &\equiv k \pmod{K+1}\end{split}\]

この意味で，\(i = i(k)\)，\(j = j(k)\) とみなすことができる．

なお，バイナリエンコーディングの場合も考え方は同様であり， \(j \in \{0,\dots,B-1\}\) として \((i,j)\) を単一添字に平坦化すればよい．

6.4. 十進数刻みの場合と比較したバイナリエンコーディングの利点#

バイナリエンコーディングの最大の利点は， 必要な表現精度に対して変数数を抑えやすいこと である．

one-hot 型の等間隔離散化では，刻み幅を \(\Delta r\) とすると， 各変数あたりに必要な候補数は次の個数だけある．

(11)#\[K+1 = \frac{1}{\Delta r} + 1\]

よって，それに対応してバイナリ変数も \(K+1\) 個必要になる．

一方，バイナリエンコーディングでは， \(B\) ビットで表現できる値の総数は次の個数だけある．

(12)#\[2^B\]

このとき，最小分解能はおおよそ次で与えられる．

(13)#\[2^{-B}\]

従って，同程度の分解能を得るために必要な変数数は， one-hot 型では候補数に比例して増加するのに対し， バイナリエンコーディングではビット数に比例してしか増えない． これは，必要変数数が対数オーダーで済むことを意味する．

例えば，\(0.01\) 程度の精度が必要であれば，次式のとおり，\(7\) ビット程度で足りる．

(14)#\[2^{-7} \approx 0.0078\]

また，\(0.001\) 程度の精度が必要であれば，次式のとおり，\(10\) ビット程度で表現できる．

(15)#\[2^{-10} \approx 0.00098\]

これに対して，one-hot 型で \(0.01\) 刻みを採用すると およそ 101 個の候補が必要になり， \(0.001\) 刻みではおよそ \(1001\) 個の候補が必要になる． この差は非常に大きく，大規模問題ではモデルサイズや計算コストに直接影響する．

従って，精度を保ちつつ変数数を削減したい場合には， バイナリエンコーディングは非常に有力な選択肢となる．

注意

バイナリエンコーディングとすることで生じうる問題として，次の注意点を挙げる．

第一に，各ビットの重みが異なるため， QUBO の係数スケールにばらつきが生じやすい． 特に高位ビットと低位ビットでは寄与の大きさが大きく異なるため， ペナルティ係数の調整が難しくなることがある． これは，数値的安定性やソルバ上での解きやすさに影響を与える可能性がある．

第二に，二進数表現では値の近さとハミング距離の近さが一致しない場合がある． 例えば，隣接する数値であっても複数ビットが同時に反転することがあり， 局所探索やヒューリスティックな探索において不利に働く可能性がある．

第三に，表現できる値が二進数の構造に依存するため， 問題によっては期待した離散点の配置にならないことがある． 特に，端点を含むかどうか，ちょうど \(1\) を表現できるかどうか， あるいは刻み幅が一様でないことをどう扱うかは， 実際の定式化では慎重に検討する必要がある．

以上，バイナリエンコーディングでは，各ビットの重みが大きく異なるため，係数スケールや数値安定性に注意が必要である．また，離散化の仕方によっては探索性能に影響が出る場合もある．これらは問題やソルバに依存するため，一律の指針は存在しないが，必要に応じて重みの設計を調整することがある．

関連

目次