講演のパワーポイント

近似アルゴリズムと距離空間の
埋め込み
スパースカット、SDP近似、整数
ギャップ、距離埋め込み
有限距離空間とその埋め込み
•
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埋め込み可能
– より良い歪みを満たすための十分条件を探そう！
有限距離空間とその埋め込み
• 行列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)
問題の動機
• データの分割 (クラスタリング）
–
データ集合を関連性の高いものたちに分割する
•
–
Assaf Naor (Microsoft) はこのテーマの専門家
テキストアナリシス、文書検索(サーチエンジン設計など）、
WEB分析、データベース構築、回路設計など、全ての情報
処理分野で必要な手法
– データの関連構造をグラフとして表現すると、グラフのカット
(切断）問題として定式化できる
– スパースカット：クラスタリングに適した一つのカット手法
– スパースカットの最適化条件が、Negative metric 条件と一
致し、これがL1に定数近似で埋めこめれば、スパースカットの
良い近似解が得られる（Linial-London-Rabinovich 1994）
グラフのカット問題
• 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| を最小にする
•
ランダムウォークやマルコフ過程の収束解析、エクスパンダなどのネット
ワーク設計で広く使われる
カット問題の計算量
カットに関する最適化問題の計算困難性
– 最小カット：多項式時間
– 最小s-t カット：多項式時間
– 最大カット： NP完全、1.13の近似比の解は多
項式時間で求まる。
– スパースカット： NP完全、O(log n)近似可能
– 一様スパースカット： NP完全、 O(log n)近似可能。
• 大きな問題：スパースカット問題の構造を解析し、
良いアルゴリズムを発見せよ
カットとフロー
• 最小ｓ－ｔカットと最大s-tフローは互いに双対の関係にある
–
最大フローが計算できれば最小カットが計算できる
• 整数計画法として定式化したときの、線形計画法の双対の関係
• スパースカットと（スループット最大）多品種フローが双対の関係にある
–
G=(V,E) 上のフローで、各々の(si, ti) 間に f ・dem(i) 以上のフローを流す。
係数ｆを最大化せよ
• アルゴリズム：
–
–
–
–
カット問題を整数計画法で定式化する。
線形計画法(ただし、変数の数が指数個）に緩和する
双対問題であるフロー問題を解くことで線形計画問題を解く
得られた線形計画法の解からカットを導く
• 困難性の違いはどこにあるか？
– 最大フローも多品種フローも線形計画法で解くことができる。
– 最大フローは最小カット辺上で必ず整数フローになる(フロー整数性)
– 多品種フローではフロー整数性が不成立。整数解がないと、双対がカットとし
て表現できない。（整数性ギャップ）
• 線形計画法の解から整数計画法の解を導く方法：
–
「ランダム丸め」や「主双対法」
カットとフロー
• スループット最大多品種フロー
– 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)の最小値と等しい。
• 演習問題：頂点対が複数だと上記の定理は不成立
メトリックとカット（その１）
• 定理: f* を最適スループットとすると、
f *  Min metric d


eE ( G )
i 1, 2 ,.., k
c ( e) d ( e)
dem(i )d ( si , t i )
– d は V上のメトリック
–以下、まずこの証明を手短に紹介する
–注意：後で、このメトリックのL1埋め込みとカットの関係を
論ずる
線形計画法での定式化
• (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
• この双対を考えよう
線形計画法の双対
主問題
Maximize f
Subject to
– ∑j fji ≧ f ・ dem(i)
(i=1,2,..,k)
– ∑e ∈q(i,j) fji ≦ c(e)
– f , fji ≧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
双対の作り方
主問題
Maximize f
Subject to
– ∑j fji ≧ f ・ dem(i)
(i=1,2,..,k)
– ∑e ∈q(i,j) fji ≦ c(e)
– f , fji ≧0
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
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
双対の作り方
主問題でｚを固定
Maximize ∑i z (i)∑j fji
Subject to
– ∑e ∈q(i,j) fji ≦ c(e)
– fji ≧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
双対問題 (z 固定）
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
1. ∑e ∈q(i,j) x(e) ≧z(i)
(i=1,2,..,k)
2. ∑i z(i) dem(i) ≧1
3. x(e)≧0
4. z(i) ≧0
観察：
• １式は、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
1. ∑e ∈q(i,j) x(e) ≧z(i)
(i=1,2,..,k)
2. ∑i z(i) dem(i) ≧1
3. x(e)≧0
4. z(i) ≧0
Minimize ∑c(e)d(e)
Subject to
1. ∑i d(si,ti) dem(i) ＝1
2. dはメトリック
メトリックのカットパッキング
• (V, d): V上のメトリック
• 辺e がS∈2Vのカット辺 ⇔SとV-Sの間の辺（δ（S))
• y : 2V  R+ が全ての辺eで下記を満たすとき、dのβカット
パッキングという。（β＝１のとき厳密カットパッキング）
 d (e)  S :e ( S ) y ( S )  d (e)
補題：双対計画法から得られたメトリックｄに対して、ｙをβカッ
トパッキングとする。すると、ｙ（S)が正（つまり非ゼロ）である
カットで、スパース度がもっとも小さいもののスパース度は
βf* 以下である。
系：小さくないβを持つカットパッキングで、ｙ（S)が非ゼロであるものが少ないも
のが得られれば、スパースカット問題のよい近似解が得られえる。
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)個以下
カットパッキングと埋め込み
定理：メトリック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埋め込みが存在する
埋め込みの存在
定理：メトリックdに対して歪みO(log n) のL1埋め込
みが存在する
頂点集合 S を取り、Vの各頂点ｖに対し
 S (v)min sS d (v, s)
とすると、一次元への埋め込みが出来る。ここでSとして、サイズ１，２，４、… 2ｋの
k＜ｌog n 個の部分集合をランダムに取る。上記座標値をｋで割ってベクトルにする
• 距離は拡大しない (三角不等式から）
• 全体で(高い確率で）距離がO(log n)倍より縮小しない
SDP緩和とNegative Metric
• 線形計画法を用いて整数計画法を緩和した場合は、
一般のメトリックｄについての理論しか展開できない。
–
β歪みL1埋め込みを持てばスパースカットのβ近似解が
出来る
• 半正定値計画法を用いて問題を緩和した場合、メト
リックｄにNegativeであるという条件が加わる。
– 同様にｄがβ’歪みL1埋め込みを持てば、スパースカットの
β’近似解が出来る
• 大きな問題 β’は本質的にβより小さくできるか？
• Goemans-Linalは小さいと予想。
半正定値計画問題
• 線形計画法：凸多面体の内部での線形関
数の最適値を求める
• 半正定値計画問題：半正定値行列がなす
(実対称行列の空間での）cone の内部での
線形関数の最適値を求める
– 両方とも『内点法』と呼ばれる手法で、多項式時
間で解ける(ただし、実際の計算時間はかなり違
う）
例題(最大カット）
• カット辺の容量和を最大にするカットを求めよ
• 2次整数計画法への定式化
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のベクトルに丸める
例題(最大カット）
• 最大カットの定式化
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にする
•このアルゴリズムの近似比は0.87856 になる（（１－cos Θ）/2 とΘ/πの比の最小）
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) フロベニウス積
SDPとしてのスパースカット
Minimize ∑c(e)d(e) Subject to
1. ∑i d(si,ti) dem(i) ＝1
2.
dはメトリック
Minimize ∑c(e)d(e) Subject to
1. ∑i d(si,ti) dem(i) ＝1
2.
dはメトリック
3.
L1埋め込み可能
Minimize ∑c(e)d(e) Subject to
1. ∑i d(si,ti) dem(i) ＝1
2.
dはメトリック
3.
Negative Type
LP緩和
最適解
中間
注意：L1埋め
込み可能なら
Negativ Type
SDPとしてのスパースカット
Minimize ∑c(e)d(e) Subject to
1. ∑i d(si,ti) dem(i) ＝1
2.
dはメトリック
3.
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 なメトリックで最適なものは見つかる。
これがよいβ歪みで埋め込めれば万歳：だけどもよくわからない。
オマケ(私は計算してません）
• （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 になる。
• 古くから知られていて、ネットワークや回路のデザイン
やマルコフ課程の収束速度解析でよく使われる事。
参考文献
• 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で
見つけてください）

Download Report