差分マップアルゴリズム
フーリエ変換係数からのグレースケール画像の差分マップ再構成における反復0、100、200、300、400

差分写像アルゴリズムは、一般的な制約充足問題のための探索アルゴリズムです。制約集合への射影を実行するより基本的なアルゴリズムから構築されているという意味で、メタアルゴリズムです。数学的な観点から見ると、差分写像アルゴリズムはユークリッド空間への写像に基づく力学系です。解は写像の 不動点として符号化されます。

差分マップアルゴリズムは、もともと位相問題を解くための一般的な手法として考案されましたが、ブール充足可能性問題、タンパク質構造予測、ラムゼー数、ディオファントス方程式、数独[1]、さらには球面パッキング問題や円板パッキング問題[2]にも用いられてきました。これらの応用にはNP完全問題が含まれるため、差分マップの適用範囲は不完全アルゴリズムの範囲となります。不完全アルゴリズムは（候補が見つかれば）解を効率的に検証できますが、解が存在しないことを証明することはできません。

差分マップアルゴリズムは、2つの反復法、すなわち位相回復のためのFienupのハイブリッド入力出力（HIO）アルゴリズム[3]と凸最適化のためのDouglas-Rachfordアルゴリズム[4]を一般化したものです。反復法は一般的に、位相回復と凸最適化において長い歴史を持っています。このタイプのアルゴリズムを困難な非凸問題に適用するようになったのは、比較的最近のことです。

アルゴリズム

解くべき問題は、まずユークリッド空間における集合交差問題として定式化されなければならない。すなわち、集合との交差においてを求める問題である。もう一つの前提条件は、任意の入力点 が与えられたときに、制約集合またはにおいて に最も近い点を返す射影との実装である。アルゴリズムの1回の反復は、次の写像によって与えられる。 × {\displaystyle x} あ {\displaystyle A} B {\displaystyle B} P あ {\displaystyle P_{A}} P B {\displaystyle P_{B}} × {\displaystyle x} あ {\displaystyle A} B {\displaystyle B} × {\displaystyle x}

× ↦ D （ × ） ＝ × + β [ P あ （ f B （ × ） ） − P B （ f あ （ × ） ） ] 、 f あ （ × ） ＝ P あ （ × ） − 1 β （ P あ （ × ） − × ） 、 f B （ × ） ＝ P B （ × ） + 1 β （ P B （ × ） − × ） {\displaystyle {\begin{aligned}x\mapsto D(x)&=x+\beta \left[P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right],\\f_{A}(x)&=P_{A}(x)-{\frac {1}{\beta }}\left(P_{A}(x)-x\right),\\f_{B}(x)&=P_{B}(x)+{\frac {1}{\beta }}\left(P_{B}(x)-x\right)\end{aligned}}}

実パラメータは0であってはならず、どちらの符号でも構いません。最適な値はアプリケーションに依存し、実験によって決定されます。最初の推測としては、反復ごとの射影計算回数を削減するため、 (または)を選択することをお勧めします。 β {\displaystyle \beta} β ＝ 1 {\displaystyle \beta =1} β ＝ − 1 {\displaystyle \beta =-1}

D （ × ） ＝ × + P あ （ 2 P B （ × ） − × ） − P B （ × ） {\displaystyle D(x)=x+P_{A}\left(2P_{B}(x)-x\right)-P_{B}(x)}

点 が写像の不動点となるのは、まさに のときです。左辺は の元であり、右辺は の元であるため、この等式は、2つの制約集合に共通の元が見つかったことを意味します。不動点自体はまたは のどちらにも属する必要はないことに注意してください。不動点の集合は、通常、解の集合よりもはるかに高い次元を持ちます。 × {\displaystyle x} × ↦ D （ × ） {\displaystyle x\mapsto D(x)} P あ （ f B （ × ） ） ＝ P B （ f あ （ × ） ） {\displaystyle P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)} あ {\displaystyle A} B {\displaystyle B} × {\displaystyle x} あ {\displaystyle A} B {\displaystyle B}

アルゴリズムの進行状況は、2 つの投影の差のノルムを調べることによって監視できます。

Δ ＝ | P あ （ f B （ × ） ） − P B （ f あ （ × ） ） | {\displaystyle \Delta =\left|P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right|} 。

これが消えると、両方の制約セットに共通する点が見つかったことになり、アルゴリズムを終了できます。

例: 論理的充足可能性

確率的局所探索などの不完全アルゴリズムは、ブール式に対する満足すべき真理値割り当てを見つけるために広く用いられています。差分マップアルゴリズムを用いて 2-SAT （2-SAT）を解く例として、次の式を考えてみましょう（~はNOTを表します）。

( q 1またはq 2 ) かつ (~ q 1またはq 3 ) かつ (~ q 2または ~ q 3 ) かつ ( q 1または ~ q 2 )

この式中の8つのリテラルそれぞれに、8次元ユークリッド空間における実変数を1つ割り当てます。これらの変数を表に並べると、2-SAT式の構造を復元できます。

× 11 × 12
（× 21） × 22
（× 31） （× 32）
× 41 （× 42）

行は2-SAT式の節であり、同じブール変数に対応するリテラルは列に配置され、否定は括弧で示されます。例えば、実変数x 11、x 21、x 41は同じブール変数 ( q 1 ) またはその否定に対応し、レプリカと呼ばれます。値 1 と -1 を、従来の 1 と 0 ではなく、 TRUEとFALSEに関連付けると便利です。この規則により、レプリカ間の互換性は次の線形方程式の形になります。

× 11 = - × 21 = × 41
× 12 = - × 31 = - × 42
× 22 = - × 32

これらの方程式が満たされる線形部分空間は、差分写像で使用される制約空間の1つ（例えばA）です。この制約に射影するために、各レプリカを符号付きレプリカ平均、またはその負の数で置き換えます。

a 1 = ( x 11 - x 21 + x 41 ) / 3
x 11 → 1 x   21 → - 1 x 41 → 1​​  

2番目の差分マップ制約は、表の行、つまり節に適用されます。条件を満たす割り当てでは、各行の2つの変数に値(1, 1)、(1, -1)、または(-1, 1)が割り当てられる必要があります。したがって、対応する制約セットBは、3 4 = 81点の集合となります。この制約に投影する際に、各行に次の操作が適用されます。まず、2つの実数値が1または-1に丸められます。次に、結果が(-1, -1)の場合、元の2つの値のうち大きい方の値が1に置き換えられます。例：

(-.2, 1.2) → (-1, 1)
(-.2, -.8) → (1, -1)

説明した両方の射影演算が、入力値と出力値間のユークリッド距離を最小化することを確認するのは簡単な作業です。さらに、アルゴリズムが両方の制約集合に含まれる点x を見つけることに成功した場合、(i) xに関連付けられた節がすべてTRUE であること、および (ii) レプリカへの割り当てが元のブール変数への真理値割り当てと一致することがわかります。

アルゴリズムを実行するには、まず初期点x 0を生成する。例えば、

-0.5 -0.8
（-0.4） -0.6
（0.3） （-0.8）
0.5 （0.1）

β = 1 の場合、次のステップはP B ( x 0 ) を計算することです。

1 -1
（1） -1
（1） （-1）
1 （1）

これに続いて2 P B ( x 0 ) - x 0、

2.5 -1.2
（2.4） -1.4
（1.7） （-1.2）
1.5 （1.9）

そして、他の制約P A (2 P B ( x 0 ) - x 0 )に投影されます。

0.53333 -1.6
（-0.53333） -0.1
（1.6） （0.1）
0.53333 （1.6）

2つの投影の差だけx 0を増やすと、差分マップの最初の反復、 D ( x 0 ) = x 1が得られます 。

-0.96666 -1.4
(-1.93333) 0.3
（0.9） （0.3）
0.03333 （0.7）

2回目の反復D ( x 1 ) = x 2は次のようになります 。

-0.3 -1.4
（-2.6） -0.7
（0.9） （-0.7）
0.7 （0.7）

これは不動点である：D ( x 2 ) = x 2 。2つの射影が一致するため、反復は変化しない。P B ( x 2 ) より、

1 -1
（-1） 1
（1） （-1）
1 （1）

満足のいく真理値の割り当てを読み取ることができます: q 1 = TRUE、q 2 = FALSE、q 3 = TRUE。

カオスダイナミクス

1000 個の変数と 4200 個の節を持つランダム 3-SAT インスタンスを解く過程での差分マップ増分Δのノルムの時系列。

上記の単純な2-SATの例では、差分マップの増分Δのノルムは3回の反復で単調に0まで減少しました。これは、差分マップに3-SATの厳密な例が与えられた場合のΔの挙動とは対照的です。3-SATでは、不動点の発見前に Δ が大きく変動します。力学系として、差分マップはカオス的であり、探索対象の空間はストレンジアトラクターであると考えられています。

位相回復

ページ上部に再構成されたグレースケール画像のフーリエ変換係数 (回折パターン)。

位相回復では、信号または画像は、離散フーリエ変換の絶対値（絶対値、大きさ）から再構成されます。例えば、物体がコヒーレント光で照らされたときに形成されるフラウンホーファー回折パターンが、この絶対値データのソースとなる場合があります。

フーリエ係数制約（例えばP A ）への射影は、まず信号または画像の離散フーリエ変換を計算し、係数をデータと一致するように再スケーリングし、次にその結果を逆変換することによって実現されます。これは、制約へのユークリッド距離が最小化されるという意味で射影です。なぜなら、(i) 離散フーリエ変換はユニタリ変換であるため距離が保存され、(ii) 係数の再スケーリング（位相を変更せずに）は係数制約を実現する最小の変化だからです。

フーリエ変換の未知の位相を復元するために、差分マップは別の制約P Bへの投影に依存します。再構成されるオブジェクトが正であること、境界付きサポートを持つことなどが分かっている場合など、この投影はいくつかの形式をとる可能性があります。例えば、表面画像の再構成において、投影P Bの効果は、長方形のサポートの外側にあるすべての値をゼロにし、サポート内の負の値もすべてゼロにすることでした。

  • 数独ソルバー - 差分マップ アルゴリズムに基づいた数独ソルバー。

注記

  1. ^ Elser, V.; Rankenburg, I.; Thibault, P. (2007年1月9日). 「反復マップを用いた探索」. Proceedings of the National Academy of Sciences . 104 (2): 418– 423. doi : 10.1073/pnas.0606359104 . PMC  1766399 . PMID  17202267.
  2. ^ Gravel, Simon; Elser, Veit (2008年9月22日). 「分割と合意：制約充足への一般的なアプローチ」. Physical Review E. 78 ( 3) 036706. arXiv : 0801.0222 . Bibcode :2008PhRvE..78c6706G. doi :10.1103/PhysRevE.78.036706. PMID :  18851188. S2CID  : 27814394.
  3. ^ Fienup, JR (1982年8月1日). 「位相回復アルゴリズム：比較」.応用光学. 21 (15): 2758– 2769. Bibcode :1982ApOpt..21.2758F. doi :10.1364/AO.21.002758. PMID  20396114. S2CID 10777701 . 
  4. ^ Bauschke, Heinz H.; Combettes, Patrick L.; Luke, D. Russell (2002年7月1日). 「位相回復、誤差低減アルゴリズム、そしてFienupバリアント：凸最適化の観点から」. Journal of the Optical Society of America A . 19 (7): 1334– 1345. Bibcode :2002JOSAA..19.1334B. CiteSeerX 10.1.1.75.1070 . doi :10.1364/JOSAA.19.001334. PMID  12095200. 
「https://en.wikipedia.org/w/index.php?title=Difference-map_algorithm&oldid=1317310502」より取得