スパースカット、SDP近似、整数ギャップ、距離埋め込み

Presentation on theme: "スパースカット、SDP近似、整数ギャップ、距離埋め込み"— Presentation transcript:

1 スパースカット、SDP近似、整数ギャップ、距離埋め込み
近似アルゴリズムと距離空間の埋め込み スパースカット、SDP近似、整数ギャップ、距離埋め込み

2 有限距離空間とその埋め込み d : V x V  R が有限(semi)metric （Vは有限集合）
d(i, i)= 0, d( i,j)= d(j,i), d(i,j)+d(j,k) ≧d(i,k) 例：辺に重みがついたグラフG＝（V,E) 　d(i,j) を頂点間の最短距離とする ｄがLp埋め込み可能とは、xi ∈Rk　で　　　　　　　　　　d(i,j)=|xi-xj|p となる点集合が存在すること ｄが歪み c でLp埋め込み可能とは、xi ∈Rk　でd(i,j)≦|xi-xj|p ≦c・d(i,j)となる点集合が存在すること 演習問題：　任意の有限メトリックはL∞埋め込み可能である 演習問題：　行列P：　p(i,j)=d(1,i)2+d(1,j)2-d(i,j)2 が正定値であることがL2埋め込み可能であることと同値 よって、L2埋め込み可能性は簡単に判定できる これはいろいろ応用される：　WEB検索やVLSI設計 ところが、L1埋め込み可能かどうかの判定はNP困難問題 L2 埋め込み可能ならL1埋め込み可能 O(log n)　の歪みでは必ずL1埋め込み可能 より良い歪みを満たすための十分条件を探そう！

3 有限距離空間とその埋め込み 行列P：　p(i,j)=d(1,i)2+d(1,j)2-d(i,j)2 が正定値であることがL2埋め込み可能であることと同値 K = {X = (xi,j) 対称行列、対角成分0、x1i+x1j-xij が正定値｝　とする。　(d(i,j)2)がKに属することがL2埋め込み可能の必要十分条件 d がnegative type ⇔(d(i,j))がKに属する dがL1埋め込み可能ならnegative type 予想（Goemans-Linial)：　Negative typeなら定数歪みでL1埋め込み可能 反例：　Knot-Vishnoi(2005) Lee-Naor(2006)

4 問題の動機 データの分割 (クラスタリング） データ集合を関連性の高いものたちに分割する
データの分割　(クラスタリング） 　データ集合を関連性の高いものたちに分割する 　Assaf Naor (Microsoft) はこのテーマの専門家 　テキストアナリシス、文書検索(サーチエンジン設計など）、WEB分析、データベース構築、回路設計など、全ての情報処理分野で必要な手法 　データの関連構造をグラフとして表現すると、グラフのカット(切断）問題として定式化できる 　スパースカット：　クラスタリングに適した一つのカット手法　 スパースカットの最適化条件が、Negative metric 条件と一致し、これがL1に定数近似で埋めこめれば、スパースカットの良い近似解が得られる（Linial-London-Rabinovich　1994）

5 グラフのカット問題 G=(V, E) グラフ c: E  R+ 辺の容量(太さ） カット： S と V-Sへの頂点集合の分割
　カット容量：　SとV-Sの間の辺の容量の和 c(S) カットに関する最適化問題 　最小カット：　c(S)を最小にするカットを求める 　最小s-t カット：　頂点対(s,t)を分離する最小カットを求める 　最大カット：　c(S)を最大にするカットを求める 　スパースカット：　頂点対(si, ti) を考え、要求量　dem(i) を考える。カットが分離する要求量の和をDem(S)とし、 c(S)/Dem(S) を最小化する。 クラスタリングだと、Vが頂点集合、辺は類似したデータ間に引く 辺の容量：　データの類似度。　 要求量が高い対：　ユーザ(あるいはシステム）が分離したい対　 遺伝子データベースなら、類似度は塩基列としての類似度、要求量は、機能的に異なると実験的(医学的）に判っている遺伝子の対に与える。 　一様スパースカット：　c(S)/|S||V-S| を最小にする 　ランダムウォークやマルコフ過程の収束解析、エクスパンダなどのネットワーク設計で広く使われる

6 カット問題の計算量 カットに関する最適化問題の計算困難性 大きな問題：スパースカット問題の構造を解析し、良いアルゴリズムを発見せよ
　最小カット：　多項式時間 　最小s-t カット：　多項式時間 　最大カット：　　NP完全、1.13の近似比の解は多項式時間で求まる。　 スパースカット：　NP完全、O(log n)近似可能 一様スパースカット：　NP完全、　O(log n)近似可能。　 大きな問題：スパースカット問題の構造を解析し、良いアルゴリズムを発見せよ

7 カットとフロー 最小ｓ－ｔカットと最大s-tフローは互いに双対の関係にある 整数計画法として定式化したときの、線形計画法の双対の関係
　最大フローが計算できれば最小カットが計算できる 整数計画法として定式化したときの、線形計画法の双対の関係 スパースカットと（スループット最大）多品種フローが双対の関係にある　 　G=(V,E)　上のフローで、各々の(si, ti) 間に 　f ・dem(i) 以上のフローを流す。 係数ｆを最大化せよ アルゴリズム： 　カット問題を整数計画法で定式化する。 　線形計画法(ただし、変数の数が指数個）に緩和する 　双対問題であるフロー問題を解くことで線形計画問題を解く 　得られた線形計画法の解からカットを導く 困難性の違いはどこにあるか？ 最大フローも多品種フローも線形計画法で解くことができる。 最大フローは最小カット辺上で必ず整数フローになる(フロー整数性) 多品種フローではフロー整数性が不成立。　整数解がないと、双対がカットとして表現できない。　（整数性ギャップ） 線形計画法の解から整数計画法の解を導く方法： 　「ランダム丸め」や「主双対法」

8 カットとフロー スループット最大多品種フロー
G=(V,E)、各辺の容量c(e)　 頂点対(si, ti) 間に異なる品種の流通需要 dem(i) フロー：　G上の流れ　＝頂点対間の(流量をつけた）パスの集合 スループット　f: 頂点対間にf・dem(i)以上流れる 演習問題：　最適なスループとをf*とすると、f*は、任意のSに対してc(S)/Dem(S)以下である。 演習問題：最小カット最大フロー定理：　頂点対が1組なら、f* はc(S)/Dem(S)の最小値と等しい。 演習問題：　頂点対が複数だと上記の定理は不成立

9 メトリックとカット（その１） 定理: f* を最適スループットとすると、 d は V上のメトリック 以下、まずこの証明を手短に紹介する
注意：後で、このメトリックのL1埋め込みとカットの関係を論ずる

10 線形計画法での定式化 (si, ti) 間の全てのパスの集合をPi = (q(i,j))とし、q(i,j)上でのフロー量をfji とする。
多品種フロー問題の計画法での定式化 Maximize f Subject to 　 ∑j 　fji ≧　f ・ dem(i) (i=1,2,..,k) ∑e ∈q(i,j) fji ≦　c(e) f , fji ≧0 この双対を考えよう

11 線形計画法の双対 Minimize ∑c(e)x(e) Maximize f Subject to Subject to
主問題 双対問題 Minimize ∑c(e)x(e) Subject to 　 ∑e ∈q(i,j) x(e) ≧z(i) (i=1,2,..,k) ∑z(i) dem(i) ≧1 x(e)≧0 z(i) ≧0 Maximize f Subject to 　 ∑j 　fji ≧　f ・ dem(i) (i=1,2,..,k) ∑e ∈q(i,j) fji ≦　c(e) f , fji ≧0

12 双対の作り方 Maximize Maximize f Min s ∑（s (i)∑j fji /dem(i)) Subject to
主問題 Maximize Min s ∑（s (i)∑j fji /dem(i)) Subject to 　 ∑is(i)≧1 ∑e ∈q(i,j) fji ≦　c(e) s(i), fji ≧0 Maximize f Subject to 　 ∑j 　fji ≧　f ・ dem(i) (i=1,2,..,k) ∑e ∈q(i,j) fji ≦　c(e) f , fji ≧0 Maximize Mini ∑j 　fji /dem(i) Subject to 　 ∑e ∈q(i,j) fji ≦　c(e) fji ≧0 Maximize Min z ∑i（ z (i)∑j fji ) Subject to 　 ∑iz(i)dem(i)≧1 ∑e ∈q(i,j) fji ≦　c(e) z(i), fji ≧0

13 双対の作り方 Maximize ∑i z (i)∑j fji Subject to ∑e ∈q(i,j) fji ≦ c(e) fji ≧0
主問題 でｚを固定 双対問題 (z 固定） Maximize ∑i　z (i)∑j fji Subject to 　 ∑e ∈q(i,j) fji ≦　c(e) fji ≧0 Minimize ∑e 　x(e)c(e) Subject to 　 ∑e ∈q(i,j) x(e) ≧z(i) X(e) ≧0 双対問題 Minimize ∑c(e)x(e) Subject to 　 ∑e ∈q(i,j) x(e) ≧z(i) (i=1,2,..,k) ∑z(i) dem(i) ≧1 x(e)≧0 z(i) ≧0

14 定理の証明 Minimize ∑c(e)x(e) Subject to ∑e ∈q(i,j) x(e) ≧z(i) (i=1,2,..,k)
観察： 　１式は、si, ti 間の最短路に対して成立すればよい。 　z(i)は最短路の重みとしてよい。 　x(e)を、ｘを重みとするGでのeの両端点の最短路の重みに入れ替えても、目的関数が増えない 　すなわち、x(e)=d(e)となるメトリックｄが存在する。 このときz(i) = d(si, ti) 2式は等号で成り立つとしてよい 　式が一つなので、全ての変数をスケールできる 　よって、目的関数は ∑c(e)d(e)/ ∑ d(si,ti) dem(i) 制約式は距離条件から成立 双対問題 Minimize ∑c(e)x(e) Subject to 　 ∑e ∈q(i,j) x(e) ≧z(i) (i=1,2,..,k) ∑i z(i) dem(i) ≧1 x(e)≧0 z(i) ≧0

15 メトリックとして見ると Minimize ∑c(e)x(e) Subject to Minimize ∑c(e)d(e)
∑e ∈q(i,j) x(e) ≧z(i) (i=1,2,..,k) ∑i z(i) dem(i) ≧1 x(e)≧0 z(i) ≧0 Minimize ∑c(e)d(e) Subject to 　 ∑i d(si,ti) dem(i) ＝1 　dはメトリック

16 メトリックのカットパッキング (V, d): V上のメトリック 辺e がS∈2Vのカット辺 ⇔SとV-Sの間の辺 （δ（S))
y : 2V  R+ が全ての辺eで下記を満たすとき、dのβカットパッキングという。（β＝１のとき厳密カットパッキング） 補題：　双対計画法から得られたメトリックｄに対して、ｙをβカットパッキングとする。すると、ｙ（S)が正（つまり非ゼロ）であるカットで、スパース度がもっとも小さいもののスパース度は　βf* 　以下である。 系：　小さくないβを持つカットパッキングで、ｙ（S)が非ゼロであるものが少ないものが得られれば、スパースカット問題のよい近似解が得られえる。

17 L1埋め込みとカットパッキング 定理： d がm次元にL1等長埋め込み距離であれば、厳密カットパッキングが存在する。更に非ゼロのy(S)は、m(n-1)個以下 σ：　V　　Rm　が存在し、d(i、j）＝|σ(i)-σ(j)|1 　m＝1　なら、頂点がv(1),v(2),..,v(n)　が数直線上にｘ(1)<ｘ(2)<..<ｘ(n)と埋め込まれているとすると、　S = {V(1), V(2),.., V(j)} の形のカットをj=1,2,..n-1で考える。 Y(S) = ｘ（j+1)-x(j) とすると、カットパッキングになる。 各次元でおなじことをする。ただし、頂点の並べ方が違うので、m(n-1)個のカットが出来る。　距離の加法性からカットパッキングになることが判る。 定理： d がm次元に歪みβでL1埋め込み距離であれば、βカットパッキングが存在する。更に非ゼロのy(S)は、m(n-1)個以下

18 カットパッキングと埋め込み 定理： メトリックdに対して厳密カットパッキング yが存在すれば、L1埋め込みが存在する
S1, S2, …, Sm をy(S)が非ゼロであるカットとしよう。頂点ｖに対して、座標　（v1, v2,…vm) を 　vj＝y(Sj)　if v ∈ Sj, otherwise vj = 0 とすると、e = (u, v) に対して、　　 d(e)　= ∑j ;e ∈　δ（Sj)　ｙ（Sj)　＝ ∑|ui – vi | 定理： メトリックdに対してβカットパッキング　yが存在すれば、β歪みL1埋め込みが存在する

19 埋め込みの存在 定理： メトリックdに対して歪みO(log n) のL1埋め込みが存在する 頂点集合 S を取り、Vの各頂点ｖに対し
とすると、一次元への埋め込みが出来る。　ここでSとして、サイズ１，２，４、… 2ｋ のk＜ｌog n 個の部分集合をランダムに取る。　上記座標値をｋで割ってベクトルにする 　距離は拡大しない　(三角不等式から） 　全体で(高い確率で）距離がO(log n)倍より縮小しない

20 SDP緩和とNegative Metric
線形計画法を用いて整数計画法を緩和した場合は、一般のメトリックｄについての理論しか展開できない。 　β歪みL1埋め込みを持てばスパースカットのβ近似解が出来る 半正定値計画法を用いて問題を緩和した場合、メトリックｄにNegativeであるという条件が加わる。　 同様にｄがβ’歪みL1埋め込みを持てば、スパースカットのβ’近似解が出来る 大きな問題　β’は本質的にβより小さくできるか？ 　Goemans-Linalは小さいと予想。

21 半正定値計画問題 線形計画法： 凸多面体の内部での線形関数の最適値を求める
線形計画法：　凸多面体の内部での線形関数の最適値を求める 半正定値計画問題：　半正定値行列がなす(実対称行列の空間での）cone の内部での線形関数の最適値を求める 両方とも『内点法』と呼ばれる手法で、多項式時間で解ける(ただし、実際の計算時間はかなり違う）

22 例題(最大カット） カット辺の容量和を最大にするカットを求めよ 2次整数計画法への定式化
　Maximize ∑1≦i<j≦n　c(i,j) (1- y(i)y(j)) Subject to y(i) = 1 or -1 緩和 Subject to |y(i)|=1, y(i) ∈　R n 線形計画法では、　整数を実数に ここでは、ノルム１の整数をノルム1のベクトルに丸める

23 例題(最大カット） 最大カットの定式化 Maximize ∑1≦i<j≦n c(i,j) (1- y(i)y(j))
Subject to y(i) = 1 or -1 緩和 　Maximize ∑1≦i<j≦n　c(i,j) (1- y(i)・y(j)) Subject to |y(i)|=1, y(i) ∈　R n　 緩和問題が解けたとする。　解の点集合が単位球面上に得られる。 ランダムな(原点を通る）超平面を考え、その右側のベクトルを１、　左側をー1にする このアルゴリズムの近似比は になる（（１－cos Θ）/2 とΘ/πの比の最小）

24 SDPとしての見方 最大カットの緩和 Maximize ∑1≦i<j≦n c(i,j) (1- Y(i,j))
Subject to Y(i,i)=1, Y:　正定値nxn行列 一般に 　Maximize　　C ・　Y (minimize でもOK) Subject to 　D(i)　・　Y　　（複数の線形制約式） 　　　　　　　　　Y:　正定値nxn行列 A・B　= tr (AT B) フロベニウス積

25 SDPとしてのスパースカット Minimize ∑c(e)d(e) Subject to ∑i d(si,ti) dem(i) ＝1
LP緩和 Minimize ∑c(e)d(e)　　Subject to 　 ∑i d(si,ti) dem(i) ＝1 　dはメトリック 　L1埋め込み可能 最適解 Minimize ∑c(e)d(e)　　Subject to 　 ∑i d(si,ti) dem(i) ＝1 　dはメトリック 　Negative Type 中間 注意：L1埋め込み可能ならNegativ Type

26 SDPとしてのスパースカット Minimize ∑c(e)d(e) Subject to ∑i d(si,ti) dem(i) ＝1
　Negative Type　　 ｄがNegative Type ⇔ D’ =　（d（1,i)+ d(1,j) –d(i,j)) が半正定値 d’(i,i)= 2d(1,i) なので、D をDiag(D’) – D’ (ラプラシアン）で書け、SDPとして定式化できる。 SDPは解けるので、Negative Type なメトリックで最適なものは見つかる。 これがよいβ歪みで埋め込めれば万歳：　だけどもよくわからない。

27 オマケ(私は計算してません） （d（1,i)+ d(I,j) –d(I,j)) が半正定値であるdの集合 → Cone Kになる
K　のDual Cone｛a| a・b　≧0 for all b ∈K} を考えると、グラフGのラプラシアンで書ける。 特にデマンドが一様な場合は、SDPの最適値はラプラシアンの第二固有値の1/n になる。 古くから知られていて、ネットワークや回路のデザインやマルコフ課程の収束速度解析でよく使われる事。

28 参考文献 V. Vazirani Approximation Algorithms
(浅野孝夫訳、近似アルゴリズム、Springer, 2001) James R. Lee, Assaf Naor, Lp metrics on the Heisenberg group and the Goemans- Linial conjecture, Proc. FOCS 2006 (James R. Lee のＷＥＢから見つかります。） ｔｃｓmath (James Lee のフォーラム、googleで見つけてください）