乱択アルゴリズム紹介(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.

「Hadoop徹底入門」が出ます

preferred

2011-01-20 22:16:17

MacBook Air 11インチ欲しい!、太田です。

1/27に、執筆に関わらせて頂いた「Hadoop徹底入門」という本が、翔泳社さんから出版されます。

Hadoop徹底入門

OSS分散フレームワーク「Hadoop」の、日本語では初めてとなる書き下ろし本になります。執筆はNTTデータでHadoopのお仕事をされている、下垣さん、猿田さん、藤井さん、濱野さん、そして私になります。また、翔泳社の石川さんには非常にお世話になりました。

目次はこのブログの最後に掲載させて頂きました(詳細はこちら)。Hadoopとは何か?といった説明に始まり、Hadoopの周辺プロダクト(Hive, Pig, HBase, Thrift)も詳しくカバーされています。

Hadoopに関して現在日本語で読める大きな情報源として有名なのは、オライリーさんから出版されている「Hadoop」本になります。

本書はこの本と補完関係に有ると思っています。オライリーさんのHadoop本は、どちらかと言えばHadoop上でMapReduceアプリケーションを開発する為の内容になっていますが、本書はどちらかというとシステムの環境構築、運用、監視、可用性の確保等といった内容がメインになっています。

「Hadoop」という単語が気になっていらっしゃる方、実際に使い始めようとしているがつまづいている方、「Hadoop」を既に使いこなしている方、等、全ての方に手に取って頂ければと思います!

続きを読む »

NLP2011で2人ほど発表します

preferred

2011-01-20 12:28:17

新年あけましておめでとうございます。研究開発チームの徳永です。2011年もよろしくお願いします。

3月に言語処理学会年次大会という大きな学会が豊橋技科大で開催されます。PFIからは今年は2人が投稿しました。

1月24日の予稿集締切りに向けて、現在鋭意執筆中です。

という訳で、内容についてはまだ執筆中なわけですが、概要をちょっと語りますと、全部分文字列(ある文書に含まれるすべての部分文字列)を素性としてクラスタリングする、という話と、識別的な手法を使ってかな漢字変換を実験してみました、という話です。詳しく聞きたい方はぜひ言語処理学会年次大会でC1:テキスト・データマイニング  3月8日(火) 09:30-12:10 (A1-201教室)とC4:テーマセッション3: 日本語入力における言語処理(1)  3月10日(木) 13:00-15:30 (A1-201教室)にご参加下さい。

豊橋技科大で岡野原大輔と握手!!

※残念ながら握手会はございませんので、握手される方は会場内を動きまわる岡野原をお探しください。その際、twitterなどから得られる情報が役に立つかもしれません。

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

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
がお薦めです。
続きを読む »