博士公聴会:定数時間アルゴリズムについて

oxy
エンジニア

2012-01-26 18:10:34

吉田です.

先日,博士論文の公聴会が終わりました. タイトルは「次数を制限したグラフと制約充足問題に対する定数時間アルゴリズムの研究」というものでした. また,博士課程での研究の成果が認められて,日本学術振興会から育志賞という賞を頂くことになりました. こちらは他の受賞者の研究内容が分からなさ過ぎて凄いですね. 今後もPreferred Infrastructureにはアドバイザーの様な形で勤めることになると思いますので宜しくお願い致します.

ということで博士課程の終わりも近く,良い区切りですので, これまで専門に研究してきた定数時間アルゴリズムについて簡単に話をすることにします.

続きを読む »

China Theory Week

oxy
エンジニア

2011-10-29 11:46:30

吉田です.
先日デンマークのオーフスという街で開催されたChina Theory Week 2011というイベントに参加してきましたので,その報告をします.China Theory Weekは中国の清華大学とデンマークのオーフス大学が主催するイベントで,理論計算機科学の世界で成果を上げている学生を集め,講演をしてもらい,互いの交流を深めあおうという趣旨のイベントです.僭越ながら僕も招待されたので参加してきました.下の写真は会場に置かれていた看板なのですが,誰か”仙オ”の意味を教えてください…
続きを読む »

乱択アルゴリズム紹介(Color-Coding)

oxy
エンジニア

2011-07-26 20:13:08

吉田です。今まで数解に渡って乱択アルゴリズムを紹介してきました。そろそろ解析やアイデアがシンプルかつ結果が綺麗な乱択アルゴリズムは尽きてきたかと思っていましたが、もう一つとても素敵な手法が有るのを思い出しましたので解説します。Color Codingと呼ばれる手法です。
続きを読む »

乱択アルゴリズム紹介(最小カット)

oxy
エンジニア

2011-05-14 18:13:20

吉田です。今日も引き続き有名な乱択アルゴリズムということで最小カット問題に対する乱択アルゴリズムを紹介したいと思います。ネタが無くなるということは無いのですが、有名かつ簡単なものとなると、そろそろ終わりが近くなってきているかもしれません。
続きを読む »

乱択アルゴリズム紹介(Bloom Filter)

oxy
エンジニア

2011-03-20 13:56:58

吉田です。相変わらず乱択アルゴリズム紹介ということで、今日はBloom Filterの話をしたいと思います。今までと違うのはBloom Filterはある問題を解くアルゴリズムではなくデータ構造であるということです。データ構造に乱数を導入するとどういうことが出来るようになるか見てみましょう。
続きを読む »

STOC 2011 論文紹介

oxy
エンジニア

2011-02-13 13:15:00

吉田です。最近ACM Symposium on Theory of Computing (STOC)という学会に投稿していた論文が受理されました。論文はECCCにアップロードしています。STOCは次回が43回目の開催となる理論計算機科学(要するにアルゴリズムと計算量を扱う分野)の中では最高峰の学会です。例えばCookが初めてNP完全性という概念を提唱したのもSTOCです。
今年は4年に一度のFederated Computing Research Conference (FCRC)というイベントがあり、STOCの他にもEC (ゲーム理論、オークションなど), CCC (計算量)、PODC, SPAA (共に分散/並列アルゴリズム)など18個の学会が同時開催されます。逆に言うと18個のうちのどれかに論文が受理されれば全体に参加出来るお得なイベントで(勿論お金さえ出せば参加は可能ですが)、僕もどれかに当たれば良いなぐらいの気分でした。
折角ですので、今回はSTOCに通った論文の内容を簡単に紹介したいと思います。流石に細部まで話をするのは技術的になりすぎてしまうので、雰囲気だけ感じ取ってもらえれば十分です。もう少し詳しい所まで踏み込んだスライドを最後に添付しておきますので、興味のある方は読んでみてください。’
続きを読む »

乱択アルゴリズム紹介(3SATのO(1.334^n)時間アルゴリズム)

oxy
エンジニア

2011-01-29 11:32:20

吉田です。今日は3SATの話をしましょう。
3SATは恐らくNP完全問題の中で一番有名な問題です。入力インスタンス\(I\)はBoolean変数の集合\(V\)と節の集合\(\mathcal{C}\)からなるCNF論理式で、各節はリテラルの個数が丁度三つからなっています。目的は全ての節を充足するような変数への割り当て\(\alpha : V \to \{\mathrm{true}, \mathrm{false}\}\)を見つけることです。ともかく例を見てみましょう。
\(V = \{x,y,z,w\}\)
\(\mathcal{C} = (x \vee y \vee z) \wedge (\neg x \vee y \vee z) \wedge (y \vee \neg z \vee w)\).
上の例だと、例えば\(\alpha(x) = \mathrm{true}, \alpha(y) = \mathrm{true}, \alpha(z) = \mathrm{false}, \alpha(w) = \mathrm{false}\)とすれば全ての節を充足することが出来ます。
3SATはNP完全なので全てのNPに属す問題は3SATとして解けるのですが、そうでなくても多くの問題から”自然”に3SATが導出されます。なので3SATを解くアルゴリズムを考えましょう。一番自明なアルゴリズムは次のようになると思います。変数の数を\(n\)、節の数を\(m\)としましょう。
(1) \(2^n\)通りの全ての割り当て\(\alpha\)に対して以下を行う。
(1.1) \(\alpha\)が全ての節を満たしていれば、\(\alpha\)を出力。
(2) 充足不能と出力。
明らかに計算時間は\(O(m2^n)\)、つまり(入力サイズに対して)指数時間になります。
それではこれを高速化することは出来るのでしょうか?残念なことにNP完全な問題は多項式時間では解けないと信じられています。なので大幅に計算時間を縮めることは出来そうにありません。なので実用的には枝刈りを用いて解かれています。ただ枝刈りという解析出来ないものは理論屋さんは好きではないので、理論屋さんは主に次の三つの方法で3SATにアプローチしているようです。
・厳密アルゴリズム: \(c^n\)時間で解くアルゴリズムで、出来るだけ\(c\)が小さいものを作る。
・近似アルゴリズム: 出来るだけ多くの節を充足する多項式時間アルゴリズムを作る。
・ランダム3SAT: 入力がランダムに分布しているとして、高い確率で充足解を出力する多項式時間アルゴリズムを作る。
今回は厳密アルゴリズムに注目しましょう。3SATに対する厳密アルゴリズムとしては、既に乱択アルゴリズムの代表例となっている、Schoeningのアルゴリズム[1]が知られています。Schoeningのアルゴリズムを3SATを\(O((\frac{4}{3})^n)=O(1.334^n)\)解くモンテカルロアルゴリズムです。正確には充足可能であれば高い確率(例えば\(\frac{99}{100}\))で充足解を出力し、充足不能であれば必ず充足不能と出力します。
\(O(2^n)\)が\(O(1.334^n)\)になったって大した違いは無いと思うかもしれませんが、例えば\(n=100\)とすると、
\(2^n \approx 10^{30} = 1000000000000000000000000000000\)、
\(1.334^n \approx 3\cdot 10^{12} = 3000000000000\)
となり、その性能向上は圧倒的です(どちらも現在のコンピュータの性能では解けないのですが)。
Schoeningのアルゴリズムは非常に簡単です。\(K\)を後で決めるパラメータとしましょう。
入力: 3SATのインスタンス\(I=(V; C), |V|=n\).
出力: 充足解\(\alpha\)、又は充足不能。
(1) 以下を\(K\)回繰り返す
(1.1) 割り当て\(\alpha\)をランダムに選ぶ
(1.2) 以下を\(3n\)回繰り返す
(1.2.1) \(\alpha\)が全ての節を充足しているなら\(\alpha\)を出力
(1.2.2) \(\alpha\)が充足しない節\(C\)を選ぶ
(1.2.3) 節\(C\)中の変数\(x\)をランダムに選び、\(\alpha(x)\)をフリップ(trueならfalseに、falseならtrueにする)。
(2) \(I\)は充足不能と出力
簡単に以下が分かります。
[命題] インスタンス\(I\)が充足不能ならば、Schoeningのアルゴリズムは充足不能と出力する。
次にインスタンス\(I\)が充足可能だった時の挙動を考えましょう。何か一つ充足解\(\alpha^*\)を固定し、\(d(\alpha)\)を\(\alpha\)と\(\alpha^*\)のハミング距離とします。ここでハミング距離とは二つの割り当ての不一致の個数です。正確には\(d(\alpha) = |\{x \in V \mid \alpha(x) \neq \alpha^*(x)\}|\)となります。以下の補題が成り立ちます。
[補題] (1.1)で選んだ\(\alpha\)が\(d(\alpha)=j\)を満たすとする。この時(1.2)で充足解を見つける確率は\(\frac{1}{2^jO(\sqrt{n})}\)以上.
この補題を元にSchoeningのアルゴリズムが充足解を出力する確率を求めましょう。(1.1)で選んだ\(\alpha\)が\(d(\alpha)=j\)になる確率は\(2^{-n}{n \choose j} \)です。なので充足解を見つける確率は
\(2^{-n}\sum {n \choose j} \frac{1}{2^jO(\sqrt{n})} = \frac{1}{O(\sqrt{n})}(\frac{3}{4})^n\)
となります。\(K\)をその逆数より少し大きい値、例えば\(K = O(\sqrt{n}(\frac{4}{3})^n)\)と選ぶと、定数確率で充足解を見つけることが示せます。最終的な計算時間も\(O((\frac{4}{3})^n)\)となります。
それでは[補題]の証明をしましょう。最初割り当て\(\alpha\)から始めて、変数を一つずつ変えていくのですが、これは数直線状のランダムウォークとみなすことが出来ます。原点に充足解\(\alpha^*\)が存在し、\(\alpha\)は原点から\(d(\alpha)=j\)の所に存在します。
(1.2.3)では現在の\(\alpha\)が充足していない節\(C\)に現れる変数をフリップしています。ところが\(\alpha^*\)はこの節\(C\)を充足しているので、\(C\)中のある変数\(x\)が存在して、\(\alpha(x) \neq \alpha^*(x)\)のはずです。どれが\(x\)かは分かりませんが、少なくとも確率\(\frac{1}{3}\)で\(x\)を当てることができ、より\(\alpha^*\)に近い割り当てを得ることが出来ます。
つまり各ステップごとに少なくとも確率\(\frac{1}{3}\)で原点に近づき、多くとも確率\(\frac{2}{3}\)で原点から離れます。原点に到達すれば解\(\alpha^*\)を出力出来ます。ここではこれらの確率を正確に\(\frac{1}{3}\), \(\frac{2}{3}\)であるとします。計算量の下限を求めるにはこう仮定しても構いません。さて上の議論から結局次のような問題を解けば良いことが分かります。
[問題] 今原点から\(j\)の距離にいる。各ステップで確率\(\frac{1}{3}\)で原点に近づき、確率\(\frac{2}{3}\)で原点から遠ざかる。この時、\(3n\)ステップ以内に原点に到達する確率は何か。
後は簡単な計算問題です。\(m\)ステップ後に始めて原点に到達したとします。原点から遠ざかった回数を\(i\)と置くと、\(m=j+2i\)と表せます。\(m\)ステップ中に\(i\)回原点から遠ざかり、\(i+j\)回原点に近づくような組み合わせは\({m \choose i}\)通りあります。少し計算をすると、\(m\)ステップ後に”初めて”原点に到達する組み合わせは\(\frac{j}{m}{m \choose i}\)通り有ることが分かります。なので、\(p(j,i)\)を座標\(j\)からスタートして\(m\)ステップ後に初めて原点に到達する確率とすると、
\(p(j,i) = \frac{j}{j+2i}{j+2i \choose i}(\frac{1}{3})^{j+i}(\frac{2}{3})^{i}\)
と書けます。
\(p(j)\)を座標\(j\)からスタートして\(3j\)ステップ以内に原点に到達する確率としましょう。\(p(j) = \sum_{i=0}^jp(j,i)\)ですが、ここでは\(p(j) \geq p(j,j)\)という(かなり粗い)関係から\(p(j)\)を下から抑えることにしましょう。以下は計算だけなので、流れだけ見てもらえれば十分です。まず\(p(j,j) = \frac{1}{3}{3i \choose i}(\frac{1}{3})^{2i}(\frac{2}{3})^i\)です。スターリングの公式\(n! = \sqrt{2\pi }(\frac{n}{e})^n(1+o(1))\)を用いると、\({3i \choose i} \geq (3i)^{3i} / (i^i (2i)^{2i} O(\sqrt{2i}))\)と書けるので、更に計算を進めると\(p(j,j) = \frac{1}{2^jO(\sqrt{j})}\)となります。
解析は(研究者からすると)驚くほど簡単で、実装も(プログラマからすると)驚くほど簡単です。このようなインパクトのある結果が少し乱数を導入しただけで得られるのは面白いです。
[1] Schoening, T., A probabilistic algorithm for k-SAT and constraint satisfaction problems, Proc. of FOCS 1999, pp. 410-414, 1999.

乱択アルゴリズム紹介(行列乗算の検査&多項式等価性の検査)

oxy
エンジニア

2011-01-15 14:55:30

吉田です。今回は乱数を用いたアルゴリズム(Randomized Algorithms、乱択アルゴリズム)を紹介したいと思います。
理論の世界では乱数を使ったアルゴリズムは既に当たり前のものになっているのですが、実際の応用で使われている所は残念ながら余り見たことが無いです。多分それは宣伝が足りないのだろうと思ったので、今回少し書いてみることにしました。実は他の場所で話すことになっていることの下準備も兼ねているのですが。これから書くことがそのまま実用に耐えるとは思っていませんが、それで乱択アルゴリズムに関する感覚を蓄えれば他の形で応用出来るんじゃないかと考えています。
最初に参考文献を挙げておくと、
Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal
がお薦めです。
続きを読む »

László Lovász 教授 京都賞 受賞記念 東京サテライトワークショップ (3)

oxy
エンジニア

2010-12-20 23:36:55

吉田です。もうしばらくLovasz Local Lemma (LLL)にお付き合い下さい。
LLLとは確率事象\(A_1,\ldots,A_m\)が存在したときに、ある条件下でそのどれもが起こらないことが有ることを示す定理でした。その応用例として、\(k\)-CNFのインスタンス\(X\)がどの節も他の高々\(2^k/e\)個の節としか変数を共有しない時、\(X\)の全ての節を充足する解が存在することを見ました。前回のLLLでは解が存在することを保証するのみでしたが、今回はその解を実際に求める話をしたいと思います。2009年の非常に最近の結果です。
続きを読む »

László Lovász 教授 京都賞 受賞記念 東京サテライトワークショップ (2)

oxy
エンジニア

2010-12-07 23:19:18

こんにちは。吉田です。前回は京都賞受賞記念のサテライトワークショップの話をしました。そこでは様々な講演がなされたので今回はその内容に触れたいと思います。ただ殆どは非常に専門的かつ狭い話だったので、その中で(比較的)分かりやすく(理論的な)応用も広いLovasz Local Lemmaについて紹介します。
Lovasz Local Lemmaは、その名の通りロヴァース氏によって証明された定理です。\(A_1,\ldots,A_n\)をある確率空間における確率事象とします。Lovasz Local Lemmaはある条件下のもとで\(\Pr[\bigwedge_i \bar{A_i}] > 0\)、つまりどの事象\(A_i\)も起こらない確率が正ということを示す定理です。
どういう時に\(\Pr[\bigwedge_i \bar{A_i}] >0\)が示せるかを考えてみましょう。もし\(\Pr[A_i] > 0 (1\leq i \leq n)\)かつ全ての\(A_i,A_j (i\neq j)\)が互いに独立であれば非常に簡単です。実際、\(\Pr[\bigwedge_i \bar{A_i}] = \prod_i (1-\Pr[A_i]) > 0\)となります。
逆に独立性を全く仮定しないとUnion Boundを使うことになるでしょう。もし\(\sum_i \Pr[A_i] < 1\)であれば、\(\Pr[\bigwedge_i \bar{A_i}]\geq 1-\sum_i\Pr[A_i] > 0\)となります。
Lovasz Local Lemmaはこれとは全く条件から\(\Pr[\bigwedge_i \bar{A_i}] >0 \)を示すことが出来ます。
(Lovasz Local Lemma) \(A_1,\ldots,A_n\)を任意の確率空間上の確率事象とする。集合\(E=\{(i,j) \mid i \neq j, A_i\)と\(A_j\)は従属\(\}\)と定める。また\(\Pr[A_i] \leq x_i \prod_{(i,j)\in E}(1-x_j)\)を満たす実数\(x_1,\ldots,x_n \in [0,1)\)が存在するとする。この時、\(\Pr[\bigwedge_i \bar{A_i}] \geq \prod_i (1 – x_i)\)が成り立つ。
また下の特殊ケースも有名です
(Lovasz Local Lemma, Symmetric case) \(A_1,\ldots,A_n\)を任意の確率空間上の確率事象とする。各事象\(A_i\)は高々\(d\)個を除く全ての\(A_j (j\neq i)\)と互いに独立とする。また\(Pr[A_i]\leq p (1 \leq i \leq n)\)とする。もし\(ep(d+1)\leq 1\)であれば、\(\Pr[\bigwedge_i\bar{A_i}]>0\)が成り立つ。
[証明] \(d=0\)の時は自明である。そうでなければ、各\(i\)について\(|\{j \mid j \neq i, A_i\)と\(A_j\)は従属\(\}|\leq d\)である。Lovasz Local Lemmaにおいて\(x_i=1/(d+1)(<1)\)とおけば、\(d\geq 1\)の時\((1-\frac{1}{d+1})^d>1/e\)であることから定理が成り立つ。
Lovasz Local Lemmaの証明をする前に、簡単な応用を見てみましょう。CNFとはリテラルの論理和からなる節を論理積で繋げたものです。例えば
\((x \vee y) \wedge (\bar{x} \vee z)\)
は\(x,y,z\)を変数、\(x,y,\bar{x},z\)をリテラル、\((x \vee y),(\bar{x} \vee z)\)を節に持つCNFです。\(\bar{x}\)は\(x\)の否定を意味しています。目的は変数にtrue/falseを割り当てて、CNFが全体としてtrueになるようにすることです。
さて、各節が\(k\)個のリテラルの論理和からなり(\(k\)-CNFとも呼ばれる)、全体として\(m\)個の節の論理積からなるCNFを考えます。
さらにどの節に対しても、その節と変数を共有する節の個数は\(d\)以下であるとします。Lovasz Local Lemmaを用いると\(k,d\)の関係だけからこのCNFが充足可能であることが証明できます。つまり節の個数\(m\)には関係ありません。
Lovasz Local Lemmaを用いるには確率空間を導入する必要があるので、各変数にtrue/falseを\(1/2\)の確率で付与するということを考えましょう。
\(A_i\)を節\(i\)が充足されない事象とします。明らかに\(\Pr[A_i]=1/2^k\)です。 仮定から\(A_i\)と従属な\(A_j (j\neq i)\)の数は高々\(d\)個です。よってLovasz Local Lemmaから\(e2^{-k}(d+1)\leq 1\)であればこのCNFは充足可能であることがわかります。
この議論では単に充足可能であることが示されただけであることに注意してください。充足可能であることが分かっても変数割り当てを得ることは全く自明ではありません。
Lovasz Local Lemmaを構成的にする、つまり変数割り当ても得られるようにするという話題だけで多くの論文が書かれています。
それでは最後にLovasz Local Lemmaを証明しましょう。
[証明] 整数\(s\)の帰納法で、任意の\(S\subseteq \{1,\ldots,n\}, |S|=s<n\)と\(i\not \in S\)について、\(\Pr[A_i \mid \bigwedge_{j\in S}\bar{A_j}] \leq x_i\)を示す。\(s=0\)の時は自明なので、\(s'<s\)の時はこれが成り立っていると仮定して、集合\(S\)に対して証明する。
\(S_1 = \{j \in S \mid (i,j) \in E\}, S_2 = S \setminus S_1\)とする。すると、
\(\Pr[A_i \mid\bigwedge_{j\in S} \bar{A_j}]=\frac{\Pr[A_i\wedge (\bigwedge_{j\in S_1}\bar{A}_j)\mid\bigwedge_{\ell\in S_2}\bar{A}_{\ell}]}{\Pr[\bigwedge_{ j\in S_1}\bar{A}_j\mid\bigwedge_{\ell \in S_2}\bar{A}_{\ell}]}\)
が成り立つ。
\(A_i\)が\(\{A_\ell \mid \ell \in S_2\}\)と独立であることに注意すると、分子は
\(\Pr[A_i\wedge (\bigwedge_{j\in S_1}\bar{A}_j)\mid\bigwedge_{\ell\in S_2}\bar{A}_{\ell}]\leq\Pr[A_i\mid\bigwedge_{\ell\in S_2}\bar{A}_{\ell}]=\Pr[A_i]\leq x_i\prod_{(i,j)\in E}(1-x_j)\)
となる。
分母は帰納法の仮定から次のように抑えることが出来る。\(S_1=\{j_{1},j_{2},\ldots,j_{r}\}\)と置く。もし\(r=0\)であれば、分母は\(1\)になり、題意が示される。もしそうでなければ、次が成り立つ。
\(\Pr[\bar{A}_{j_1}\wedge \ldots \bar{A}_{j_r} \mid \bigwedge_{\ell \in S_2}\bar{A}_{\ell} ]= (1-\Pr[A_{j_1} \mid\bigwedge_{\ell \in S_2}\bar{A}_{\ell} ]) \cdot \cdots \cdot (1-\Pr[A_{j_r} \mid \bar{A}_{j_1} \wedge \ldots \wedge \bar{A}_{j_{r-1}} \wedge \bigwedge_{\ell\in S_2}\bar{A}_{\ell} ]) \geq (1-x_{j_1})\cdots (1-x_{j_r}) \geq \prod_{(i,j\in E)}(1-x_j)\)
ここから\(\Pr[A_i \mid \bigwedge_{j\in S}\bar{A_j}] \leq x_i\)が得られる。
よって、
\(\Pr[\bigwedge_i A_i] = (1-\Pr[A_1])\cdot \cdots (1-\Pr[A_n \mid \bigwedge_{i=1}^{n-1}\bar{A}_i]) \geq \prod_i(1-x_i)\).
もう少し数式が見やすくなれば良いのですが。次回からは工夫してみたいと思います。
12