そのためには
偉くなって・・・
偉くなって・・・
偉くなって・・・
2010年2月22日月曜日
2010年2月19日金曜日
2010年2月16日火曜日
2010年2月15日月曜日
2010年2月12日金曜日
SK言語で decもしくはeqが作れない
自然数とは何だろうか
それは"1を足す"という操作の回数とみなすことが出来る。
"1を足す"という操作を関数fで表した時 7 という数は
f(f(f(f(f(f(f(0))))))) と表される
自然数nを意味する項<n>を再帰的に定義する
xは任意の項である
・<0> f x ≡ x
・<n> f x ≡ f (<n-1> f x)
これにより
<7> f x ―*→ f(f(f(f(f(f(f(x))))))) となる
<0> f x = x ← K x (K x) ← SKK x ← K (SKK) f x
∴<0> = K(SKK)
<n> f x = f(<n-1> f x) ← K f x (<n-1> f x) ← S(Kf)(<n-1>f)x
← (KSf)(Kf)(<n-1>f)x ← S(KS)K f (<n-1>f) x
← S(S(KS)K))<n-1> f x
∴<n> = S(S(KS)K))<n-1>
また <succ> <n> = <n+1> となる <succ>は
<succ> = S(S(KS)K) により定義出来る
では 次のように定義される <dec> はどうやって定義出来るのだろうか?
・<dec> <0> = <0>
・<dec> <n+1> = <n>
次のように定義される <eq> はどうやって定義出来るのだろうか?
・<eq> <0> <0> = <true>
・<eq> <n+1> <0> = <false>
・<eq> <0> <m+1> = <false>
・<eq> <n+1> <m+1> = <eq> <n> <m>
それは"1を足す"という操作の回数とみなすことが出来る。
"1を足す"という操作を関数fで表した時 7 という数は
f(f(f(f(f(f(f(0))))))) と表される
自然数nを意味する項<n>を再帰的に定義する
xは任意の項である
・<0> f x ≡ x
・<n> f x ≡ f (<n-1> f x)
これにより
<7> f x ―*→ f(f(f(f(f(f(f(x))))))) となる
<0> f x = x ← K x (K x) ← SKK x ← K (SKK) f x
∴<0> = K(SKK)
<n> f x = f(<n-1> f x) ← K f x (<n-1> f x) ← S(Kf)(<n-1>f)x
← (KSf)(Kf)(<n-1>f)x ← S(KS)K f (<n-1>f) x
← S(S(KS)K))<n-1> f x
∴<n> = S(S(KS)K))<n-1>
また <succ> <n> = <n+1> となる <succ>は
<succ> = S(S(KS)K) により定義出来る
では 次のように定義される <dec> はどうやって定義出来るのだろうか?
・<dec> <0> = <0>
・<dec> <n+1> = <n>
次のように定義される <eq> はどうやって定義出来るのだろうか?
・<eq> <0> <0> = <true>
・<eq> <n+1> <0> = <false>
・<eq> <0> <m+1> = <false>
・<eq> <n+1> <m+1> = <eq> <n> <m>
SK言語でdecもしくはeqってどうやって作るの?
SK言語の説明
・SとKは項である
・項Xと項Yを括弧でくくったもの(XY)も項である
・XYはXという関数にYを入力する事を意味する
・項X,Y,Zに対して ((XY)Z)という形は括弧を省略しXYZと書くことが出来る
・XYZはXという関数は2変数関数で入力としてYZを与えることを意味する。
・(X(YZ))という形の項はXYZと書いてはいけない
・項は簡約される。
・KXYという形の項はXに書き換えることが出来る。(Kによる簡約、射影)
・SXYZという形の項はXZ(YZ)に書き換えることが出来る。(Sによる簡約、分配)
・Mを簡約してNになる事を M→N で書く
・Mを0回以上簡約してNになることを M―*→N で書く
・Xを簡約してY1とY2にできるとき、Y1とY2はさらに共通のZに簡約出来る(合流性)
・M1―*→N, M2―*→N の時 M1=M2 と書く。 = は同値関係になっている。
・S,K言語はチューリング完全
・S,K言語はどんな計算もエミュレート出来る
・次のような遊びが出来る
「BXYZを簡約していくと X(YZ)の形になる。BをSとKで表せ」
BXYZ → X(YZ) ← X(YZ) ← KXZ(YZ) ← S(KX)YZ ← (KSX)(KX)YZ ← S(KS)KXYZ
したがって
BXYZ = S(KS)KXYZ
任意の XYZに対してこれは成り立つので
B = S(KS)K
電車の中で暇がつぶせる
・SとKは項である
・項Xと項Yを括弧でくくったもの(XY)も項である
・XYはXという関数にYを入力する事を意味する
・項X,Y,Zに対して ((XY)Z)という形は括弧を省略しXYZと書くことが出来る
・XYZはXという関数は2変数関数で入力としてYZを与えることを意味する。
・(X(YZ))という形の項はXYZと書いてはいけない
・項は簡約される。
・KXYという形の項はXに書き換えることが出来る。(Kによる簡約、射影)
・SXYZという形の項はXZ(YZ)に書き換えることが出来る。(Sによる簡約、分配)
・Mを簡約してNになる事を M→N で書く
・Mを0回以上簡約してNになることを M―*→N で書く
・Xを簡約してY1とY2にできるとき、Y1とY2はさらに共通のZに簡約出来る(合流性)
・M1―*→N, M2―*→N の時 M1=M2 と書く。 = は同値関係になっている。
・S,K言語はチューリング完全
・S,K言語はどんな計算もエミュレート出来る
・次のような遊びが出来る
「BXYZを簡約していくと X(YZ)の形になる。BをSとKで表せ」
BXYZ → X(YZ) ← X(YZ) ← KXZ(YZ) ← S(KX)YZ ← (KSX)(KX)YZ ← S(KS)KXYZ
したがって
BXYZ = S(KS)KXYZ
任意の XYZに対してこれは成り立つので
B = S(KS)K
電車の中で暇がつぶせる
2010年2月11日木曜日
SK言語
Theorem1.
全てのTree(xn)に対して
Tree(xn) = G(S,K)Tree' xn...xn
となる,Tree'が存在する
proof.
書き換え(0) X = (K X xn) … ※Tree(xn)がxnを含まない場合
書き換え(1) (xn Y) = (R Y xn)
書き換え(2) F (G xn) = B F G xn
を使う
Theorem2.
全てのTree(xn)に対して
Tree(xn) = G(S,K)Tree' xn
となるG,Tree'が存在する
proof.
Theorem1.を使うと F xn...xn の形になっている。
F xn xn = SFI xn を繰り返し使えばよい。
Theorem3.
Tree(x1,...,xn)= Tree' x1,...,xnとなるTree'が存在する
xn,x[n-1],...x1の変数にに対してTheorem2を使う。
Theorem4.
F x1 x2 x3...xn = Tree(x1,...,xn,F) に対して
F x1 x2 x3...xn = Tree' x1 x2...xn となる Tree'が存在する
Therem5.から
F x1 x2 x3...xn = Tree'' F x1 x2...xn となる Tree''が存在する
F = Tree'' F なので不動点コンビネータYを使い
F = Y Tree'' とすればよい。
全てのTree(xn)に対して
Tree(xn) = G(S,K)Tree' xn...xn
となる,Tree'が存在する
proof.
書き換え(0) X = (K X xn) … ※Tree(xn)がxnを含まない場合
書き換え(1) (xn Y) = (R Y xn)
書き換え(2) F (G xn) = B F G xn
を使う
Theorem2.
全てのTree(xn)に対して
Tree(xn) = G(S,K)Tree' xn
となるG,Tree'が存在する
proof.
Theorem1.を使うと F xn...xn の形になっている。
F xn xn = SFI xn を繰り返し使えばよい。
Theorem3.
Tree(x1,...,xn)= Tree' x1,...,xnとなるTree'が存在する
xn,x[n-1],...x1の変数にに対してTheorem2を使う。
Theorem4.
F x1 x2 x3...xn = Tree(x1,...,xn,F) に対して
F x1 x2 x3...xn = Tree' x1 x2...xn となる Tree'が存在する
Therem5.から
F x1 x2 x3...xn = Tree'' F x1 x2...xn となる Tree''が存在する
F = Tree'' F なので不動点コンビネータYを使い
F = Y Tree'' とすればよい。
SK言語で現実逃避
Kxy≡x
Sxyz≡xz(yz)
I x ≡ x = SKKx = Kx(Kx)=x
∴I = SKK
K2 x y ≡ y = Iy = K I x y
∴K2 = KI
Bxyz ≡ x(yz) = (Kxz)(yz) = S(Kx)yz = (KSx)(Kx)yz = S(KS)Kxyz
∴B = S(KS)K
Rxy ≡ yx = K2xy(Kxy) = S K2x Kx y = S(SK2)K xy
∴B = S(SK2)K
Y f ≡ f(Yf)
Y = λf.(λx.(fxx)λx.(fxx))
Yf = λx.(fxx) λx.(fxx)
λx.(fxx) x = fxx = BfIx
Yf = BfIx(BfIx) = S(BfI)(BfI)x = S(RI(Bf))(RI(Bf))
= S(RI(Bf))(RI(Bf)) = S(B(RI)Bf)(B(RI)Bf) = BS(B(RI)B)f(B(RI)Bf)
= S(BS(B(RI)B))(B(RI)B) f
∴Y = S(BS(B(RI)B))(B(RI)B)
<true>≡K
<false>≡K2
<not>x ≡ x<false><true>
= R<false>x<true>
= R<true>(R<false>x)
= B(R<true>)(R<false>)x
∴<not> = B(R<true>)(R<false>)
<or>xy ≡ x<true>(y<true><false>)
= x<true>(R<true>y<false>)
= x<true>(R<false>(R<true>y))
= x<true>(B(R<false>)(R<true>)y)
= B(x<true>)(B(R<false>)(R<true>)) y
= R(B(R<false>)(R<true>)) (B(x<true>)) y
= R(B(R<false>)(R<true>)) (B(B<true>x)) y
= R(B(R<false>)(R<true>)) ( BB(B<true>) x ) y
= B (R(B(R<false>)(R<true>))) (BB(B<true>)) xy
∴<or>= B (R(B(R<false>)(R<true>))) (BB(B<true>))
<and>xy ≡ x (y <true> <false> )<false>
= B x (y<true>) <false><false>
= B(Bx)y<true><false><false>
= B B B x y <true><false><false>
= R<true>(B B B x y)<false><false>
= B(R<true>) (B B B x) y <false><false>
= B(B(R<true>)) (B B B) x y <false><false>
= R<false> ( B(B(R<true>)) (B B B) x y ) <false><false>
= B (R<false>) ( B(B(R<true>))(B B B) x ) y <false><false>
= B(B(R<false>))(B(B(R<true>))(B B B)) x y <false><false>
= R<false> (B(B(R<false>))(B(B(R<true>))(B B B)) x y) <false>
= B(R<false>) (B(B(R<false>))(B(B(R<true>))(B B B)) x) y <false>
= B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)) x y <false>
= R<false>(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)) x y)
= B(R<false>)(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)) x) y
= B(B(R<false>)(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)))) x y
∴<and> = B(B(R<false>)(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B))))
<if>≡I
<while> p f e ≡ p e e (<while> (Bpf) (fe) )
= SpI e (S (K(<while>(Bpf))) f e)
= S(SpI)( S(K(<while>(Bpf)))f) e
= S(SpI)( S(K(B<while>(Bp)f))f) e
= S(SpI)( S(BK(B<while>(Bp)) f)f) e
= S(SpI)( BS(BK(B<while>(Bp))) f ( If ) ) e
= S(SpI)( S (BS(BK(B<while>(Bp))))I f ) e
= B (S(SpI)) (S(BS(BK(B<while>(Bp))))I) f e
= B (S(RI(Sp))) (RI ( BS(B(BS)(BK(BB(B<while>)B))) p)) f e
= B (S(B(RI)Sp)) (B(RI)(BS(B(BS)(BK(BB(B<while>)B)))) p) f e
= B (BS(B(RI)S)p) (B(RI)(BS(B(BS)(BK(BB(B<while>)B)))) p) f e
= BB(BS(B(RI)S))p (B(RI)(BS(B(BS)(BK(BB(B<while>)B)))) p) f e
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK(BB(B<while>)B))))) p f e
<while>
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK(BB(B<while>)B)))))
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK( RB(B(BB)(B)<while>))))))
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK( RB ( B(BB)(B) <while>))))))
= S(BB(BS(B(RI)S)))(B(RI)(BS( B(BS) ( B(BK)(B(RB)(B(BB)(B))) <while>))))
= S(BB(BS(B(RI)S)))(B(RI)(BS( B(B(BS))(B(BK)(B(RB)(B(BB)(B)))) <while>)))
= S(BB(BS(B(RI)S)))(B(RI)( B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B))))) <while>))
= S(BB(BS(B(RI)S)))( B(B(RI))(B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B)))))) <while>)
= B(S(BB(BS(B(RI)S))))(B(B(RI))(B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B))))))) <while>
= Y(B(S(BB(BS(B(RI)S))))(B(B(RI))(B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B))))))))
***********************************************************************
<0>sx≡x
<n+1>sx≡s(<n>sx)
<0> = K2
<n+1>sx = s(<n>sx) = Ksx(<n>sx)
= S(Ks)(<n>s)x = BSKs(<n>s)x
= S(BSK)<n>sx
∴<n+1> = S(BSK)<n>
<inc> ≡ S(BSK)
<isZero> <0> ≡ <true>
<isZero> <n+1> ≡ <false>
<isZero> <n> = <n> (K<false>) <true>
= R(K<false>)<n><true>
= R<true>(R(K<false>)<n>)
= B(R<true>)(R(K<false>)) <n>
∴<isZero> = B(R<true>)(R(K<false>))
Sxyz≡xz(yz)
I x ≡ x = SKKx = Kx(Kx)=x
∴I = SKK
K2 x y ≡ y = Iy = K I x y
∴K2 = KI
Bxyz ≡ x(yz) = (Kxz)(yz) = S(Kx)yz = (KSx)(Kx)yz = S(KS)Kxyz
∴B = S(KS)K
Rxy ≡ yx = K2xy(Kxy) = S K2x Kx y = S(SK2)K xy
∴B = S(SK2)K
Y f ≡ f(Yf)
Y = λf.(λx.(fxx)λx.(fxx))
Yf = λx.(fxx) λx.(fxx)
λx.(fxx) x = fxx = BfIx
Yf = BfIx(BfIx) = S(BfI)(BfI)x = S(RI(Bf))(RI(Bf))
= S(RI(Bf))(RI(Bf)) = S(B(RI)Bf)(B(RI)Bf) = BS(B(RI)B)f(B(RI)Bf)
= S(BS(B(RI)B))(B(RI)B) f
∴Y = S(BS(B(RI)B))(B(RI)B)
<true>≡K
<false>≡K2
<not>x ≡ x<false><true>
= R<false>x<true>
= R<true>(R<false>x)
= B(R<true>)(R<false>)x
∴<not> = B(R<true>)(R<false>)
<or>xy ≡ x<true>(y<true><false>)
= x<true>(R<true>y<false>)
= x<true>(R<false>(R<true>y))
= x<true>(B(R<false>)(R<true>)y)
= B(x<true>)(B(R<false>)(R<true>)) y
= R(B(R<false>)(R<true>)) (B(x<true>)) y
= R(B(R<false>)(R<true>)) (B(B<true>x)) y
= R(B(R<false>)(R<true>)) ( BB(B<true>) x ) y
= B (R(B(R<false>)(R<true>))) (BB(B<true>)) xy
∴<or>= B (R(B(R<false>)(R<true>))) (BB(B<true>))
<and>xy ≡ x (y <true> <false> )<false>
= B x (y<true>) <false><false>
= B(Bx)y<true><false><false>
= B B B x y <true><false><false>
= R<true>(B B B x y)<false><false>
= B(R<true>) (B B B x) y <false><false>
= B(B(R<true>)) (B B B) x y <false><false>
= R<false> ( B(B(R<true>)) (B B B) x y ) <false><false>
= B (R<false>) ( B(B(R<true>))(B B B) x ) y <false><false>
= B(B(R<false>))(B(B(R<true>))(B B B)) x y <false><false>
= R<false> (B(B(R<false>))(B(B(R<true>))(B B B)) x y) <false>
= B(R<false>) (B(B(R<false>))(B(B(R<true>))(B B B)) x) y <false>
= B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)) x y <false>
= R<false>(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)) x y)
= B(R<false>)(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)) x) y
= B(B(R<false>)(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B)))) x y
∴<and> = B(B(R<false>)(B(B(R<false>))B(B(R<false>))(B(B(R<true>))(B B B))))
<if>≡I
<while> p f e ≡ p e e (<while> (Bpf) (fe) )
= SpI e (S (K(<while>(Bpf))) f e)
= S(SpI)( S(K(<while>(Bpf)))f) e
= S(SpI)( S(K(B<while>(Bp)f))f) e
= S(SpI)( S(BK(B<while>(Bp)) f)f) e
= S(SpI)( BS(BK(B<while>(Bp))) f ( If ) ) e
= S(SpI)( S (BS(BK(B<while>(Bp))))I f ) e
= B (S(SpI)) (S(BS(BK(B<while>(Bp))))I) f e
= B (S(RI(Sp))) (RI ( BS(B(BS)(BK(BB(B<while>)B))) p)) f e
= B (S(B(RI)Sp)) (B(RI)(BS(B(BS)(BK(BB(B<while>)B)))) p) f e
= B (BS(B(RI)S)p) (B(RI)(BS(B(BS)(BK(BB(B<while>)B)))) p) f e
= BB(BS(B(RI)S))p (B(RI)(BS(B(BS)(BK(BB(B<while>)B)))) p) f e
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK(BB(B<while>)B))))) p f e
<while>
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK(BB(B<while>)B)))))
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK( RB(B(BB)(B)<while>))))))
= S(BB(BS(B(RI)S)))(B(RI)(BS(B(BS)(BK( RB ( B(BB)(B) <while>))))))
= S(BB(BS(B(RI)S)))(B(RI)(BS( B(BS) ( B(BK)(B(RB)(B(BB)(B))) <while>))))
= S(BB(BS(B(RI)S)))(B(RI)(BS( B(B(BS))(B(BK)(B(RB)(B(BB)(B)))) <while>)))
= S(BB(BS(B(RI)S)))(B(RI)( B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B))))) <while>))
= S(BB(BS(B(RI)S)))( B(B(RI))(B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B)))))) <while>)
= B(S(BB(BS(B(RI)S))))(B(B(RI))(B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B))))))) <while>
= Y(B(S(BB(BS(B(RI)S))))(B(B(RI))(B(BS)(B(B(BS))(B(BK)(B(RB)(B(BB)(B))))))))
***********************************************************************
<0>sx≡x
<n+1>sx≡s(<n>sx)
<0> = K2
<n+1>sx = s(<n>sx) = Ksx(<n>sx)
= S(Ks)(<n>s)x = BSKs(<n>s)x
= S(BSK)<n>sx
∴<n+1> = S(BSK)<n>
<inc> ≡ S(BSK)
<isZero> <0> ≡ <true>
<isZero> <n+1> ≡ <false>
<isZero> <n> = <n> (K<false>) <true>
= R(K<false>)<n><true>
= R<true>(R(K<false>)<n>)
= B(R<true>)(R(K<false>)) <n>
∴<isZero> = B(R<true>)(R(K<false>))
2010年2月8日月曜日
2010年2月5日金曜日
・DPの復習
関数 f(x1,x2,...,xN) の最大値を求めたいとする。
もし f(x1,x2,...,xN) = Σ[i=1,N-1] fi(xi,x[i+1]) の形になっていれば
全てのx1,x2,...,xN の組み合わせを探索しなくてもよい。
説明を簡単化するため N=3の場合を考える。
目的関数は f(x1,x2,x3) = f1(x1,x2)+f2(x2,x3) の3変数関数である。
もしもx1,x2,x3各々の取りうる値が100パターンであれば
これらの全組み合わせのパターン数は100^3=1000000である。
しかし、この全てを探索する必要はない
第1項目 f1(x1,x2)に対して x2をある値に固定し、x1を探索して最大化したものを V1(x2)とする。(ここまでで探索回数 100)
つまり V1(x2) = max[x1] f1(x1,x2)
これを全ての x2 に対して計算する。(ここまでで探索回数 10000)
次に V1(x2)+f2(x2,x3) に対して x3をある値に固定し,x2を探索して最大化したものを V2(x3)とする。(ここまでで探索回数10000+100)
つまり V2(x3) = max[x2] V1(x2)+f2(x2,x3)
これを全ての x3 に対して計算する。(ここまでで探索回数 20000)
最後に V2(x3)が最大となる x3を求めるとこれが f1(x1,x2)+f2(x2,x3)の最大値になっている。 (ここまでで探索回数 20100)
全ての組み合わせを求める方法が 1000000回
後者の方法では 20100回
この比は約 50倍
3変数の場合を考えたが、探索回数の差は変数の個数が多いほど急激に大きくなる。
N変数の場合、全ての組み合わせパターンは 100^N 回
後者の方法では(たぶん) 10000(N-1)+100 回
N=1000 程度の問題は珍しくなく
効率のよい後者の方法では 9990100 回だが
この場合前者の方法では 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 回になる。
ばかあほとろまぬけ。
後者で使った V1(x2),V2(x3) は途中の項までの最大値を
x2やx3の取りうる全て可能性に対して求めている。
これらは部分問題の解を保存している。
計算機に、このような変数を持たせるためには記憶領域が必要である。
一方、前者の方法ではこのような記憶領域を必要としない。
部分問題の解を保存しておく必要がないからである。
後者の方法は記憶領域を犠牲にして計算時間の速さを稼いでいる。
一般に使用する記憶領域と計算時間はトレードオフの関係になると考えられる。
・ここから妄想
DP計算をグラフとして図示することを試みる。(トレリスではない。)
各fiをノードとする。
変数を共有しているノードを結ぶ。
例えば、f2(x2,x3)とf3(x3,x4)はx3を共有しているため、節f2とf3は結ばれる。
するとDP計算の概念図を描く事が出来る。
赤い点線枠が、部分問題の解を求めていくイメージ。

もっと一般的なグラフ構造をもつ数式に対しても
下図のイメージでDP計算が出来るコトが期待出来る。萌える。
関数 f(x1,x2,...,xN) の最大値を求めたいとする。
もし f(x1,x2,...,xN) = Σ[i=1,N-1] fi(xi,x[i+1]) の形になっていれば
全てのx1,x2,...,xN の組み合わせを探索しなくてもよい。
説明を簡単化するため N=3の場合を考える。
目的関数は f(x1,x2,x3) = f1(x1,x2)+f2(x2,x3) の3変数関数である。
もしもx1,x2,x3各々の取りうる値が100パターンであれば
これらの全組み合わせのパターン数は100^3=1000000である。
しかし、この全てを探索する必要はない
第1項目 f1(x1,x2)に対して x2をある値に固定し、x1を探索して最大化したものを V1(x2)とする。(ここまでで探索回数 100)
つまり V1(x2) = max[x1] f1(x1,x2)
これを全ての x2 に対して計算する。(ここまでで探索回数 10000)
次に V1(x2)+f2(x2,x3) に対して x3をある値に固定し,x2を探索して最大化したものを V2(x3)とする。(ここまでで探索回数10000+100)
つまり V2(x3) = max[x2] V1(x2)+f2(x2,x3)
これを全ての x3 に対して計算する。(ここまでで探索回数 20000)
最後に V2(x3)が最大となる x3を求めるとこれが f1(x1,x2)+f2(x2,x3)の最大値になっている。 (ここまでで探索回数 20100)
全ての組み合わせを求める方法が 1000000回
後者の方法では 20100回
この比は約 50倍
3変数の場合を考えたが、探索回数の差は変数の個数が多いほど急激に大きくなる。
N変数の場合、全ての組み合わせパターンは 100^N 回
後者の方法では(たぶん) 10000(N-1)+100 回
N=1000 程度の問題は珍しくなく
効率のよい後者の方法では 9990100 回だが
この場合前者の方法では 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 回になる。
ばかあほとろまぬけ。
後者で使った V1(x2),V2(x3) は途中の項までの最大値を
x2やx3の取りうる全て可能性に対して求めている。
これらは部分問題の解を保存している。
計算機に、このような変数を持たせるためには記憶領域が必要である。
一方、前者の方法ではこのような記憶領域を必要としない。
部分問題の解を保存しておく必要がないからである。
後者の方法は記憶領域を犠牲にして計算時間の速さを稼いでいる。
一般に使用する記憶領域と計算時間はトレードオフの関係になると考えられる。
・ここから妄想
DP計算をグラフとして図示することを試みる。(トレリスではない。)
各fiをノードとする。
変数を共有しているノードを結ぶ。
例えば、f2(x2,x3)とf3(x3,x4)はx3を共有しているため、節f2とf3は結ばれる。
するとDP計算の概念図を描く事が出来る。
赤い点線枠が、部分問題の解を求めていくイメージ。

もっと一般的なグラフ構造をもつ数式に対しても
下図のイメージでDP計算が出来るコトが期待出来る。萌える。

2010年2月4日木曜日
2010年2月3日水曜日
君の言っている理論的な所はよく分からないが
工学の役にはたたないねと一蹴された
正しいけど腑に落ちない。
でも正しい。
死ねばいいのに。
私はいわれたとおりに計算をするだけの計算機。
言われた論文をただただ書き続けるマシン。
がっかいではっぴょうをすればしゅうしょくでゆうりだよ。じさつ。
考えるだけ無駄なんだ。
駄目だ工学は向いてない。
社会のためなど知ったことか。
記号と戯れて、集中できる、あの時間が好きなだけなんだ。
誰もいない、あの部屋が好きなだけなんだ。
牢屋、精神病院、天国、死後の世界、どこ?
飯を食べるために仕事。
生きるために仕事。
生きてつらさを味わうために仕事。
長く生きるために仕事。
長く生きて長く辛さを味わうために仕事。
牢屋、精神病院、天国、死後の世界、どこ?
ドアの前に血しぶき
地面にプレスされる人体
離れる世界
遠い人声
ピアノ
*********************************************************************************
パラメータの最尤推定はどういうときに上手くいかない?
学習データをXとする。
P{θ|X} が得られる。
P{θ|X} を最大化する θを求めるのが最尤推定。(単峰、綺麗な山の形を期待)
P{θ|X} の平均値を求めるのもよいかも。(単峰、山の形がいびつなときに有効?)
P{θ|X}P{θ} 事前知識 P{θ}を使いのはどういうときに有効?
モデルθの使用用途は?
・モデルパラメータ自体に興味がある時 (正規分布)
・隠れ情報の推定 (HMM)
・クラスタリング (GMM)
工学の役にはたたないねと一蹴された
正しいけど腑に落ちない。
でも正しい。
死ねばいいのに。
私はいわれたとおりに計算をするだけの計算機。
言われた論文をただただ書き続けるマシン。
がっかいではっぴょうをすればしゅうしょくでゆうりだよ。じさつ。
考えるだけ無駄なんだ。
駄目だ工学は向いてない。
社会のためなど知ったことか。
記号と戯れて、集中できる、あの時間が好きなだけなんだ。
誰もいない、あの部屋が好きなだけなんだ。
牢屋、精神病院、天国、死後の世界、どこ?
飯を食べるために仕事。
生きるために仕事。
生きてつらさを味わうために仕事。
長く生きるために仕事。
長く生きて長く辛さを味わうために仕事。
牢屋、精神病院、天国、死後の世界、どこ?
ドアの前に血しぶき
地面にプレスされる人体
離れる世界
遠い人声
ピアノ
*********************************************************************************
パラメータの最尤推定はどういうときに上手くいかない?
学習データをXとする。
P{θ|X} が得られる。
P{θ|X} を最大化する θを求めるのが最尤推定。(単峰、綺麗な山の形を期待)
P{θ|X} の平均値を求めるのもよいかも。(単峰、山の形がいびつなときに有効?)
P{θ|X}P{θ} 事前知識 P{θ}を使いのはどういうときに有効?
モデルθの使用用途は?
・モデルパラメータ自体に興味がある時 (正規分布)
・隠れ情報の推定 (HMM)
・クラスタリング (GMM)
rect(x;a,b) = 1/(b-a) if(x∈[a,b])
= 0 else
一様分布の共役事前分布g(a,b)は?
g(a,b) = 1/(b-a)^n / Z if( a≦xm,xM≦b )
= 0 else
観測 X={x1,x2,x3,...,xn}
a,bを最尤推定すると a=xm, b=xM になる。(xm,xMは最小元と最大元。)
しかしg(a,b)からa,bの平均値を求めると nの値を考慮した値に多分なる。
(nが小さな時はデータが信用出来ないので、aはxmより小さく,bはxMより大きくなる。
nが大きな時はデータが信用できるので、aはxm、bはxMに近くなる)
f(x,a) = 1/√(a^2-x^2) if(x∈[-a,a])
= 0 else
の場合は?
g(a;X) = Π[i] 1/√(a^2-xi^2) /Z if(a≧max{|x1|,|x2|,...,|xn|})
= 0 else
aを最尤推定すると a=max{ |x1|,|x2|,...,|xn| }≡am
aをg(a;X)から平均値計算すると…?
E[a] = ∫[am,∞] a (Π[i] 1/√(a^2-xi^2) ) /Z da
計算の仕方がわからない
でもx1,x2,...,xnの値が影響している?
= 0 else
一様分布の共役事前分布g(a,b)は?
g(a,b) = 1/(b-a)^n / Z if( a≦xm,xM≦b )
= 0 else
観測 X={x1,x2,x3,...,xn}
a,bを最尤推定すると a=xm, b=xM になる。(xm,xMは最小元と最大元。)
しかしg(a,b)からa,bの平均値を求めると nの値を考慮した値に多分なる。
(nが小さな時はデータが信用出来ないので、aはxmより小さく,bはxMより大きくなる。
nが大きな時はデータが信用できるので、aはxm、bはxMに近くなる)
f(x,a) = 1/√(a^2-x^2) if(x∈[-a,a])
= 0 else
の場合は?
g(a;X) = Π[i] 1/√(a^2-xi^2) /Z if(a≧max{|x1|,|x2|,...,|xn|})
= 0 else
aを最尤推定すると a=max{ |x1|,|x2|,...,|xn| }≡am
aをg(a;X)から平均値計算すると…?
E[a] = ∫[am,∞] a (Π[i] 1/√(a^2-xi^2) ) /Z da
計算の仕方がわからない
でもx1,x2,...,xnの値が影響している?
2010年2月2日火曜日
Dynamic Programing
部品からなる製品を作りたい
・部品と部品を組み合わせるとより大きな新たな部品になり、最終的には製品になる。
・部品がたくさん与えられているので
できるだけ良い組み合わせを見つけて、よい製品を作りたい。
・部品には種類がある。(エンジン、ディスプレイ、HDD、等)
・ある種類の部品を作るためには、それが必要とする種類の部品を組み合わせなければならない。(部品の種類には有限順序関係が定義される。X<Y ⇔ YはXを使って作られる。最大元は製品、極小元は最も細かい部品)
(部品の種類には二項演算子"+"が定義される。 X+Y=Z ⇔ XとYを組み合わせてZが作られる。)
・全ての部品(製品)からは、その評価値が計算できる。最終的に最も高い評価値の製品を作りたい。
・大きな部品を構成するある小さな部品をより評価値の高いものに取り替えたとき、大きな部品の評価値も上がる。
・効率良く、最も評価値の高い製品を構成する方法は?
・部品と部品を組み合わせるとより大きな新たな部品になり、最終的には製品になる。
・部品がたくさん与えられているので
できるだけ良い組み合わせを見つけて、よい製品を作りたい。
・部品には種類がある。(エンジン、ディスプレイ、HDD、等)
・ある種類の部品を作るためには、それが必要とする種類の部品を組み合わせなければならない。(部品の種類には有限順序関係が定義される。X<Y ⇔ YはXを使って作られる。最大元は製品、極小元は最も細かい部品)
(部品の種類には二項演算子"+"が定義される。 X+Y=Z ⇔ XとYを組み合わせてZが作られる。)
・全ての部品(製品)からは、その評価値が計算できる。最終的に最も高い評価値の製品を作りたい。
・大きな部品を構成するある小さな部品をより評価値の高いものに取り替えたとき、大きな部品の評価値も上がる。
・効率良く、最も評価値の高い製品を構成する方法は?
登録:
投稿 (Atom)