Androidで走るProcessingアプリケーション

祢次金 佑
エンジニア

2010-12-24 14:44:32

今日は24 Season8 を徹夜で見ます。祢次金です。

前回、CinderでiPadアプリケーションを書きましたが、今回はJavaベースのProcessingを使ってAndroidアプリケーションを書いてみます。


続きを読む »

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年の非常に最近の結果です。
続きを読む »

wat-array : wavelet木を利用した高速配列処理ライブラリ

岡野原 大輔
リサーチャー

2010-12-17 19:10:33

こんにちは岡野原です。もう年末になりましたが、私の今年はこれからです。

wat-arrayというC++ライブラリを公開しました。
google code:wat-array
wat-arrayはフリーソフトウェアであり、修正BSDライセンスに基づいて利用できます.

wat-arrayはwavelet木と呼ばれるデータ構造を利用することにより、配列上の様々な処理を効率的に行うことができるC++ライブラリです。
続きを読む »

劣微分を用いた最適化手法について(4)

preferred

2010-12-15 17:22:45

徳永です。進撃の巨人3巻が発売される頃までにはこのエントリを公開するつもりだったのですが、無理でした。

前回は、劣勾配法を紹介し、前々回で紹介した確率的勾配降下法と劣勾配法を比較した場合、劣勾配法を用いることによって微分不可能な点があっても最適化が可能になるけれど、解の品質には依然として問題がある場合があり、特にL1正則化に付いてはあまり良い結果が得られない、というところまでお話しました。

続きを読む »

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)\).
もう少し数式が見やすくなれば良いのですが。次回からは工夫してみたいと思います。

劣微分を用いた最適化手法について(3)

preferred

2010-12-03 16:41:42

進撃の巨人3巻が11月に発売されるものと勘違いして本屋を探し回っていましたが、発売日は12月9日でした。徳永です。

前回は、確率的勾配降下法(SGD)について説明しました。今回はいよいよ、劣微分を用いた最適化手法に付いての説明をおこないます。

続きを読む »