2015 : x 1 + x 2 = 1 (1) x 2 = 2x x 1 x 2 (x 1, x 2 ) N x y = Ax (2) M y A M N x 1 3

Size: px

Start display at page:

Download "2015 : x 1 + x 2 = 1 (1) x 2 = 2x x 1 x 2 (x 1, x 2 ) N x y = Ax (2) M y A M N x 1 3"

えりかあいきょう
5 years ago
Views:

1 05 : x + x = x = x + x x x, x N x y = Ax M y A M N x mohzei@i.yoto-u.ac.jp 3

2 M = N M N M < N. N x 0 0 K M K M < N M > K N x M y M N A y = Ax 3 M < N x K M > K K N K y = Ax N K N K K y = Ax.3 L L0 x 0 x L 0 x min x x 0 s.t. y = Ax 4 0 L 0 L L x = x + x + + x N 5 4

3 L L 0 L L L 0 min x x s.t. y = Ax 6 x x L x L L x = x + x + + x N 7 L? L 0? min x x s.t. y = Ax 8 x x L x L L CS-I:L L min x + x } s.t. y = Ax 9 x,x } min x x,x + x s.t. y = Ax 0 A A = y = y = Ax = x + x x, x x A y y x y x x = x + 3 5

4 L x + x + 4 3x / x x + x + = x + 0 x < / 3x x < 0 5 x, x x, x = /, 0 L x + x + = 5 x x, x x, x = /5, /5 L 6.4 x, x CS-I x = x + L x + x = r r L x x L L p x p = p x p + x p + + x N p 7 p p 0 L 0 L 0 fax = a fx L 0 0 p L 3 6

5 : L : L.5 N x 0 A M y y = Ax 0 8 7

6 3: L p x 0 L x x = x 0 N = 000 K = 0 M = 00 4 L : N = 000 K = 0 M = 00 L 5 L Basis Pursuit Basis Pursuit M y x 0 8

7 : L L CS-II: min x x s.t. y = Ax 9 x T 0 = /, 0 A =, y = Ax 0 = CS-I x T = /, 0 x T 0 = 0, A =, y = Ax 0 = x T = /, 0 [, ] [3, 4] A 0 L π α = + te t Qt} 0 ρ e t = ρ t π Qt α = M/N ρ = K/N 6 Qt = t e x π dx MRI [5] 9

8 : L.6 y = Ax + σ 0 w 3 w M σ 0 y = Ax y Ax L x } min y Ax x s.t. x a 4 Tibshirani LASSO Least Absolute Shrinage and Selection Operators [6] a } min x λ y Ax + x λ > 0 λ 0 y Ax y = Ax λ y λ y λ 5 5 LASSO 5 0

9 .7 LASSO y A x x A y P y A, x P A, B = P A BP B = P B AP A 6 P A, B A B P A B B A P B A A B 3 P A, B, C = P A B, CP B, C = P A, B CP C 7 P A B = P B AP A P B P B AP A = = P A, B A P B = A P A, B P B AP A A P B AP A 8 A B y A P A, x, y = P x A, yp AP y = P y A, xp AP x 9 P x A, y = P y A, xp x P y x P y A, x y A, x A x y P x x x P x A, y y A x x x x Maximum A Posteriori 30

10 x MAP = arg max log P x A, y} 3 x P y A, x A x y 3 P n = exp π nt n 3 A x y n 3 n = σ 0 y Ax 33 P y A, x = P n = exp π σ0 y Ax 34 x λ P x = π exp κ x x MAP = arg max x σ0 y Ax κ } x 36 LASSO L L L 35 P x exp κ x 37 x MAP = arg max x } σ0 y Ax κ x 38 λ = κσ0 LASSO 5 3 L LASSO

11 3. 95% 0 7 x 7: 95% 0 B min x λ y Ax + Bx } 39 B z = Bx min y AB z } z λ + z 40 LASSO 3. A MRI MRI M = N M < N NHK ZERO 3

12 [7] [9] LASSO 3.3 L 0 min x fx} 4 fx x[0] x[t + ] = x[t] δ fx 4 δ L CS-III: min x x + } y x λ 43 λ, y 4

13 x > 0 min x>0 x + } y x λ 44 λ x y λ} + y λ x = y λ x > 0 y λ > 0 y λ 0 x x = 0 8 x 0 45 [ ] 8: x > 0 x = S λ y 46 y λ y > λ S λ y = 0 λ y λ y λ y < λ S λ y Soft thresholding function 9 CS-II:L 47 min x x + } λ y x 48 λ, y L L L x = x + x + + x N 49 5

14 9: L x = x + x + + x N 50 x i = S λ y i 5 x = S λ y. 5 Fast Iterative Shrinage Thresholding Algorithm FISTA L Iterative Shrinage Thresholding Algorithm ISTA FISTA [8] Majorizer Minimization L gx q L x, y = gy + gy T x y + L x y 53 gx q L x, y q L x, y gx gx fx L fx fy L x y 54 6

15 gx L gx gy L x y 55 q L x, y q L x, y gy q L x, y = gy L gy + L x y L gy gy gy 0 L L t x[t] 56 x[t + ] = arg min x q L x, x[t] 57 gx[t + ] q L x[t + ], x[t] gx[t] 58 gx q L x, x[t] 0 0: gx 5 gx = y Ax /λ gx = AT y Ax/λ L = A T A /λ 7

16 [ ] L gx+ x q L x, x[t]+ x x[t + ] = arg min x q L x, x[t] + x } 59 L L x[t + ] = arg min x x[t] + } } x Lλ AT y Ax[t] + x = S λ/l x[t] + Lλ AT y Ax[t] Iterative Shrinage Soft-thresholding Algorithm ISTA t = 0 x[0] x[0] = A T y. gx v[t] = x[t] + Lλ AT y Ax[t] 6 3. x[t + ] = S /L v[t] FISTA Fast Iterative Shrinage Soft-thresholding Algorithm FISTA. t = x[0] β[] = 0 w[] = x[0]. gx v[t] = w[t] + Lλ AT y Aw[t] x[t + ] = S /L v[t] [ ]β[t] β[t] = β[t ] [ ]w[t] w[t + ] = x[t + ] + β[t] x[t + ] x[t] 67 β[t + ] 8

17 FISTA L FISTA FISTA L x x[t] / x[t] gx gx gx[t] + gx T x x[t] 68 Bregman Bregman iterative method LASSO λ LASSO y = Ax y = Ax LASSO BP x = 0 LASSO Bregman Bregman divergence BD fx D p f x, y = fx fy pt x y 69 p fx fx := p fu fx + p T u x u } 70 u u Bregman [ BD ] BD L BD y < 0 BD D 0 x < 0 f x, y = x y + x y = x + x = x x y > 0 Df x x < 0 x, y = x y x y = x x = 0 x 0 7 9

18 : : BD y < 0 y = 0 D p f x, y = x y px y = x px = + px x < 0 px x 0 3 BD y L BD BD y < 0 x = 0 BD 73 min x fx + gx} 74 gx y Ax /λ fx x Bregman 0

19 3: BD y = 0 min x D p[t] f } x, x[t] + gx x[0] = 0 p[0] = 0 LASSO x[t] x[t + ] = argmin x D p[t] f p[t] } x, x[t] + gx p[t] = p[t ] gx[t] fx[t] p p[t] + gx[t] p fx p 0 x = x[t + ] p[t + ] = p[t] gx[t + ] fx[t + ] 78 gx gx[t + ] gx[t + ] + D p[t] f x[t + ], x[t] 79 gx[t] + D p[t] f x[t], x[t] 80 gx[t] 8 BD 3 BD y Ax LASSO p[t + ] = p[t] + λ AT y Ax[t] [, ] 8 y = Ax[t] L [0] 76 LASSO x[t + ] = argmin x D p[t] f x, x[t] + gx[t] T x x[t] + L } x x[t] 83

20 L p[t + ] = p[t] gx[t] Lx x[t] fx[t + ] 84 Bregman [0] Bregman. t = 0 x[0] = 0 p[0] = 0. p[t] } T x[t + ] = argmin x x λ AT y Ax[t] + p[t] x x[t] + L x x[t] v[t] = x[t] + L λ AT y Ax[t] + p[t] x[t + ] = S /L v[t] p[t + ] = p[t] + λ AT y Ax[t] Lx[t + ] x[t] [, ] FISTA LASSO FISTA } T x[t + ] = argmin x x λ AT y Ax[t] x x[t] + L x x[t] FISTA x[t] p[t] T x x[t] x x[t] < ɛ Bregman 89 Lagrangian Augmented Lagrangian method Lagrangian min x fx s.t. c i x = 0 i =,,, m 90 m Lx; λ = fx + h i c i x 9 i=

21 AL-I: min x x + x } s.t. ax + bx c = 0 9 a, b, c x, x Lx, x ; h = x + x + hax + bx c 93 0 x x h Lx, x ; λ x = x + λa = 0 94 Lx, x ; λ x = x + λb = 0 95 h Lx, x ; h = ax + bx c = 0 96 x = ha x = hb h = c/a + b x = ac/a + b x = bc/a + b h c i x = 0 0 ax + bx c = 0 h δ h i [t] = h i [t ] δc i x 99 h[t] = h[t ] δ a + b h t / + δc 00 h[t] = h[t ] = h c h c = c/a +b δa + b / < δ h 3

22 Penalty method L pen. x = fx + µ[t] m c i x 0 µ[t] 0 i= L pen. x, x ; µ[t] x = x + µ[t]aax + bx c = 0 0 L pen. x, x ; µ[t] x = x + µ[t]bax + bx c = x = x = µ[t]ac + µ[t]a + b µ[t]bc + µ[t]a + b µ[t] µ[t] L aug. x; h = fx + m i= h i [t]c i x + µ[t] m c i x 06 i= h i [t + ] = h i [t] + µc i x 07 0 L aug. x, x ; h[t], µ[t] x = x + h[t]a + µ[t]aax + bx c = 0 08 L aug. x, x ; h[t], µ[t] x = x + h[t]b + µ[t]bax + bx c = x = x = µ[t]ac h[t]a + µ[t]a + b µ[t]bc h[t]b + µ[t]a + b 0 4

23 h[t + ] = µ[t]c + h[t] + µ[t]a + b µ[t] h[t] fx = x cx = y Ax L arg. x; h[t], µ[t] = x + h[t] T y Ax + µ[t] y Ax 3 h[t + ] = h[t] + µ[t]y Ax 4 M h[t] = h [t], h [t],, h M [t] A T A T h[t] = p[t] p[t + ] = p[t] + µ[t]a T y Ax 5 µ[t] = /λ gx = A T y Ax/λ Bregman 8 Bregman Alternating Direction Method of MultipliersADMM ADMM [] min x fx + gx} 6 LASSO min x,z fz + gx} s.t. x z = 0 7 L aug. x, z; h[t], µ[t] = fz + gx + h[t] T x z + µ[t] x z 8 ADMM z x x[t + ] = argmin x L aug. x, z[t]; h[t], µ 9 z[t + ] = argmin z L aug. x[t], z; h[t], µ 0 5

24 h[t + ] = h[t] + µx z ADMM LASSO fx = x gx = y Ax /λ x[t + ] = argmin x λ y Ax + h[t]t x z[t] + µ } x z[t] z[t + ] = argmin z z + h[t] T x[t + ] z + µ } x[t + ] z 3 x 0 z L L LASSO ADMM for LASSO. t = 0 x[0] = A T x z[0] = x[0] h[0] = 0. x[t] x[t + ] = µ + λ AT A A T y + µz[t] h[t] 4 3. z[t] z[t + ] = S /µ x[t + ] h[t] µ 5 4. h[t] h[t + ] = h[t] + µx[t] z[t] µ LASSO ON 3 ADMM ADMM ADMM LASSO FISTA L Bx ADMM LASSO min x,z z + λ y Ax } s.t. z Bx = 0 7 L aug. x, z; h, µ[t] = z + λ y Ax + h[t]t z Bx + µ[t] z Bx 8 6

25 x[t + ] = argmin x λ y Ax + h[t]t Bx z[t] + µ[t] z[t + ] = argmin z z + h[t] T Bx[t] z + µ[t] Bx[t] z Bx z[t] } } 9 30 L B FISTA Total Variation L Fast Gradient Projection FGP [] L FISTA Fast Composit Splitting Algorithm FCSA [3] ADMM ADMM-II: ADMM min x x x + } λ y ax bx 3 x x ADMM min x,z z + } λ y ax bx s.t. z x x = 0 3 L aug. x, z; h, µ[t] = z + λ y ax bx + h[t] z x x } + µ[t] z x x } 33 x x z [ ] x [t + ] = x [t + ] = µ[t] + a ay λ λ µ[t] + b ay λ λ z[t + ] = S /µ[t] z[t] + h[t] µ[t] + h[t] + µ[t]z + µ[t] ab λ + h[t] µ[t]z + µ[t] ab λ x } x } L 7

26 4. Ex = J x i x j 37 N x i x i = ± J J > 0 P x = Ex Z exp 38 T Z Z = exp J x i x j 39 NT x N x i x j = N x i N N N i<j i= i<j i= i<j N x i + O N N x i i= 40 Z = NJ exp T x N N i= x i 4 N i= x i/n m = N N x i 4 m x m Z = dmδ m NJ x i exp N T m 43 x = dmδ m x i N i= i= i= 44 m x NKm / m T em = J T m 45 sm = N log δ m x i 46 N x 8 i=

27 Z = dm exp N em } + sm T 47 N m } Z = exp N em + sm T m = arg max em } + sm m T m N f = T log Z = max em + T sm} 50 N m δ m N } N x i = d m exp N m m x i N i= sm = N log d m exp Nm m x i= N i= i= x i exp mx i } 5 5 N N fx i = fx i 53 x i x i sm = } N log d m exp Nm m + N log cosh m i= N m 54 sm = m m + log cosh m 55 m = arg max m m m + log cosh m } 56 m m f = min Jm + T m m + T log cosh m } 57 m, m m = tanh m m J m = tanh T m 58 J m[t + ] = tanh T m[t] [ :K = J/T K ] 59 9

28 4. LASSO λ 0 P x A, x 0 δ y Ax 0 exp κ x 60 β β x A,y = dx P β x A, y 6 MSE = β N x x 0 x A,y 6 β = β β A 0 /N x 0 ρ = K/N P 0 x = ρδx i + ρ exp π x i 63 y = Ax 0 ZA, x 0 = lim λ dx exp λ y Ax β x δy Ax = lim exp λ +0 λ y Ax A x 0 N A x 0 f = [ ] N log ZA, x 0 66 A,x 0 A x 0 30

29 [log ZA, x 0 ] A,x0 = lim n 0 [Z n A, x 0 ] A,x0 n 67 n n [ [Z n A, x 0 ] A,x0 = lim dx a exp n n y Ax a λ +0 λ β x a 68 ]A,x0 n A A t a = Ax 0 Ax a M A t a A 0 t T a t b = x T N 0 x 0 x T 0 x a x T 0 x b + x T a x b a= a= 69 q ab = N xt a x b 70 m = N i= x i/n = dq ab δ q ab N xta x b a,b 7 x a x 0 sq ab } = N log [ZA, y] A,n,x0 = lim λ +0 n a=0 dq dx a exp dm dq [ β exp n a= x a a,b λ δ q ab N xta x b x 0 7 ] n t a exp Nsq ab } 73 t a t a P t a detq Q = π N exp t t aq ab t b 74 Q Q a b = q ab eq ab } = N log [exp 3 λ a= a,b ] n t a 75 t a a=

30 [ZA, y] A,n,x0 = lim λ +0 dq ab exp Neq ab } + Nsq ab } 76 dt a detq π N exp a,b t T a λ δ ab + Q ab t b 77 N a dx π exp a b x + bx = exp a N deta dx exp π xt Ax + b T x = exp bt A b Dx = dx π 80 t a eq ab } = α log det I + λ Q 8 α = M/N t a M log deta = Tr log Λ Λ A Q 0 a q 0a = m a > 0 8 q aa = Q a > 0 83 q ab = q a b 84 q 0 0 = ρ ρ m + Q ρ m + q ρ m + q ρ m + q ρ m + Q ρ m + q Q =..... ρ m + q ρ m + q ρ m + Q = Q qi n + ρ m + q n 85 3

31 I n n n n n n I + Q/λ + Q q/λ + nρ m + q/λ n + Q q/λ [ : ] eρ, Q, m, q = n α ρ m + q λ + Q q n log + λ Q q 86 3 δ Q N Q xta x a = d Q } exp NQ x T a x a 87 δ q N xta x b = d q exp q } Nq x T a x b 88 δ m N xt0 x a = d m exp m Nm x T } 0 x a 89 δ q ab N xta x b = exp N n QQ nn N qq Nn mm a,b n exp Qx T a x a + mx T 0 x a exp qxt a x b a b a= n exp qxt a x b = exp q n x a x T a x a 9 a b a= a= 90 n n Dz exp qz T x a q xt a x a a= a= 9 Dz exp az T x a = exp xt x 93 x δ q ab N xta x b = exp N n QQ nn N qq Nn mm a,b n Dz exp T Q + q x T a x a + qz + mx0 xa β x a a= 94 33

32 x a n n x a N N n a= dx a a,b δ q ab N xta x b = exp N n QQ N nn qq Nn mm } exp Nn log φx 0, z; Q}, Q} 95 φx 0, z; Q, q, m = dx exp Q + q x + qz + mx0 x β x 96 N Q, q, m Q, q, m sρ, Q, m, q = max Q n QQ [ nn qq n mm + n ] } Dz log φx 0, z; Q, q, m x 0 97 n n φx 0, z; Q, q, m L β β β β Q q O/β Q q Q + q Oβ m Oβ q Oβ βq q χ Q + q β Q q β χ m β m λ +0 sρ, Q, m, q = nβ max Q eρ, Q, m, q = n αβ QQ χχ mm ρ m + Q χ [ Dz min x + O 98 }] Q x χz + mx0 + x x 0 χz + mx 0 = χ + mt sρ, Q, m, q = nβ max Q QQ } χχ mm ρ DzΦz; Q, q, 0 ρ DtΦt; Q, q, m x 0 } 99 Φz; Q, q, m = min x Q x χ } + m zx + x 00 Φz; Q, q, m = χ + Q m z Θ χ + m z 0 34

33 Θx = x > 0 0 x 0 0 [ : ] Φz; Q, q, m z βf = N [log Z] A,x 0 α f = max Q, Q χ ρ m + Q + Q Q χ χ m m + ρ Q G χ + m + ρ QG χ } 03 Ha = Dz 04 Ga = a a a + H a π exp a 05 Q Q Q = α χ 06 χ = α ρ m + Q 07 χ m = α χ 08 ρ Q = G χ + m Q + ρ G χ 09 Q ρ χ = Q H + χ ρ Q H 0 + m χ m = ρ mh χ + m α ρ MSE [ ] β MSE = N x x 0 = ρ m + Q x A,x 0 A,x 0 4 LASSO

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0. 0. 0 0 0. 0. 0.3 0.4 0.5 0.6 0.7 0.8 0.9 4: MSE 0.

34 : MSE 0.00 MSE MSE 6 ISTA µ µ µ µ µ P x = N = f x µ f µ x µ 3 P x = f x µ P µ x µ = f a x µ µ M µ x 4 M µ x 5 M µ M µ M [t] µ x M [t] µ x f x dx / f µ x µ ν µ l µ M [t] l µ x l 6 M [t ] ν x 7 36

35 A y N M P β x A, y exp β x δ y µ a T µ x 8 = µ= µ a µ β L N M P β x A, y exp β x f a T µ x y µ = µ= 9 N Approximate Message Passing:AMP N 6 = d uµ δ u µ a T µ x 0 6 M [t] µ x du µ dx / fu µ y µ δ u µ a T µ x l µ M [t] l µ x l M [t] µ x du µ dũ µ dx / fu µ y µ exp iũ µ uµ a T µ x } M [t] l µ x l l µ x l M [t] µ x du µ dũ µ fu µ y µ exp iũ µ u µ a µ x } l µ dx l exp iũ µ a µl x l M [t] l µ x l 3 0 /M a µl /M x l m [t] µ V [t] µ dx x M [t] µ x 4 dx x M [t] µ x m µ [t] 5 x l a µ M [t] µ x du µ dũ µ fu µ y µ exp iũ µ u µ a µ x } l µ exp iũ µ a µl m [t] l µ ũ µ a µlv [t] l µ 6 37

36 ũ µ M [t] µ x du µ fu µ y µ exp } u µ m [t] µ + a µ x m [t] µ V µ m [t] µ V [t] µ a µ m [t] µ 7 a µv [t] µ 8 l m l µ = m [t] µ m [t] µ l V l µ = V [t] µ V [t] µ a µ M [t] µ x } du µ fu µ y µ exp u V µ [t] µ m [t] µ + a µx m [t] µ u µ m [t] µ V [t] µ a µ x m [t] µ u µ c µ = du µ fu µ y µ exp V [t] µ u µ m [t] µ V [t] µ µ u µ m [t] V [t] µ 9 } u µ m [t] µ 30 M [t] µ x c 0 µ exp m [t] µ x } V [t] µ x x g r m µ V µ m [t] µ = a µ g 0 m [t] µ V [t] µ a µg m [t] µ V [t] µ m [t] µ 3 V [t] µ = a µg m [t] µ V [t] µ 3 g r m µ V µ = r m r µ V [t] µ log c 0 µ 33 fu µ y µ 30 6 m µ V µ 7 d r µ = dx x r M [t ] µ x 34 r = m [t ] [t ] µ r = V µ 7 d r µ = dx x r exp β x + ν µ m [t ] ν x V [t ] ν x 35 38

37 β m [t ] ν βm[t ] [t ] [t ] ν V ν βv ν m [t ] = µ V [t ] = µ m [t ] µ 36 V [t ] µ 37 Ia b = log dx exp β x + βax } βbx d r µ = / βar Ia b m [t] µ = S /V [t ] βv [t] µ = V [t ] V [t ] µ V [t ] µ β b a Θ a 38 m [t ] V [t ] m [t ] µ V [t ] µ Θ m [t ] m [t ] µ S /V [t ] V [t ] m [t ] m[t ] µ V [t ] V [t ] Θ m [t ] Θ m [t ] fu µ y µ m [t] = M a µ g 0 m µ [t] V µ [t] M a β β µg m [t] µ V µ [t] m [t ] S [t ] /V µ= µ= V [t ] 4 V [t] = M a β µg m [t] µ V µ [t] 4 m [t] µ = βv [t] µ = µ= a µ S /V [t ] a µ V [t ] LASSO m [t ] V [t ] Θ m [t ] fu µ y µ fu µ y µ = exp βλ } y µ u µ V [t] µ g 0 m [t ] µ V [t ] µ LASSO c 0 µ g 0 m µ V µ = β y µ mµ λ + βv µ 46 g m µ V µ = β λ + βv µ 47 39

38 βv µ V µ m [t] = V [t] = M µ= M µ= m [t] µ = V [t] µ = a µ λ + V [t] µ a µ λ + V [t] µ a µ S /V [t ] a µ V [t ] y µ m µ [t] + V [t] m [t ] V [t ] Θ m [t ] S /V [t ] m [t ] V [t ] V [t] µ g 0 m [t ] µ V [t ] µ 50 5 relaxed Belief Propagation µ a µ = a [t] µ = /M V µ = V [t] V [t] = W [t] M m [t] a µ = λ + V y [t] µ m µ [t] + W [t] m [t ] S /W [t ] 5 W [t ] µ= W [t] = 53 λ + V [t] m [t] µ = m [t ] V [t] a µ S /W [t ] W [t ] λ + V y [t ] µ m [t ] µ 54 V [t] = M N = W Θ m [t ] [t ] 55 x [t] = S Λ [t] m [t] W [t] M x [t] = S Λ[t] x [t ] + a µ z µ [t] z µ [t] = y µ a T µ x[t] M Λ[t] = λ + Λ[t ] M = µ= N = Θ x [t ] Λ [t ] z µ [t ] 58 N Θ x [t ] Λ [t ] 59 W [t] = /Λ[t] AMP 3 59 N K K < M Λ[t ] Λ[t] K > M z µ [t] y µ a T µ x[t] ISTA AMP λ 0 LASSO ISTA 40

39 ISTA AMP ISTA 5 5. N x d d =,,, D P x u = exp Ex u}. 60 Zu Zu u Ex u N N N Ex u = J ij x i x j + h i x i 6 i= j i x i = ± u = J, h j i J ij 0 i j N i= Ex u = xt Jx + h T x 6 x i u = J, h P D x = D D δx x d 63 d=?? u 4

40 5: 5. KL P x D KL P Q = dxp x log Qx KL u 64 Qx P x u P x P D x KL D KL P D P u = PD x dxp D x log P x u u 65 u = arg max Lu. 66 u Lu Lu = D D log P x = x d u. 67 d= Lu = D D Ex = x d u log Zu. 68 d= u[t + ] = u[t] + η Lu u 69 η u 4

41 Lu u = D D d= Ex = x d u u Ex u u u u = x P x u u[0] 6 6: Ex u = x i x j u 7 J ij Ex u h i u u = x i u 7 Mean Field Approximation P x u N P i x i u 73 i= KL P i x i u N N } Pi MF i= x i u = arg min dx P i x i u log P ix i u P i x i u P x u i= 74 43

42 dx i P i x i u = N N } Pi MF i= x i u = arg min dx P i x i u log P ix i u N + λ i P i x i u P i x i u P x u N i= dx i P i x i u log P i x i u + i= i= i= 75 N N dx P i x i ue i x i x /i, u + log Zu + λ i P i x i u 76 E i x i x /i, u /i i Ex u = i= N E i x i x /i, u 77 i= E i x i x /i, u = j i J ij x i x j + h i x i 78 P i x i u 0 = log P i x i u + + E i x i m /i, u + λ i 79 m i = dx i x i P i x i u P i x i u P i x i u = Z MF i u exp E i x i m /i, u 80 Zi MF u P i x i u exp j i J ijx i m j + h i x i P i x i u = 8 cosh j i J ijm j + h i m i m i = tanh J ij m j + h i 8 j i h j x i u = x i x j u x i u x j u 83 [4] : tanh tanh m j = J j m + h j 84 j 44

43 h j = tanh m j j J j m 85 dm i dhj δ ij = = dh j dm i m j J ij 86 J ji = J ij x i u x i x j u [6, 7] P i x i u, x /i Belief Propagation Pseudo Lielihood Estimation D [8] Ex u = N i= E ix i x /i, u Zu N } exp E i x i x /i = x d /i, u. 87 i= Zu N x i N i= cosh j i J ij x d j + h i. 88 x i u tanh x i x j u x d i j i J ij x d j tanh j i J ij x d j + h i 89 + h i + x d tanh j i j J ji x d i + h i 90 J ij = J ji m i x d i MCMC [9] P [t+] y = x W u y xp [t] x 9 W u y x x y P [t] x 45

44 P ss x W u y xp ss x u = P ss y u 9 x W u y x W u x y = P ssy u P ss x u 93 [0,, ] i x i x i x W u x x = min, P ss x u P ss x u = min, exp J ij x i x j h i x i 94 j i P ss x W u x x = P ss x u + P ss x u = tanh J ij x i x j + h i x i j i [ ] 95. x[0]. i 3. Ex[s] u Ex[s] u = J ij x i [s]x j [s] h i x i [s] 96 j i 46

45 4. r r exp Ex[s] u T 97 t w fx u T T +t w s=t w + fx[s] 98 t w T Contrastive divergence CD CD [3]. s = 0 x[0] = x d. i 3. Ex[s] u Ex[s] u = J ij x i [s]x j [s] h i x i [s] 99 j i 4. r r exp Ex[s] u T 300 u[t] x d [] D fx u D D fx d [] 30 Lu u D d= D Ex = x d [] d= u Ex = } xd [0] u 30 47

46 Minimum Probability Flow Minimum Probability Flow MPF [4] dp t y dt = x CD P 0 x = D W u y xp t x. 303 D δx x d 304 d= u KL W u x x = exp } E x u E jx u. 305 x x KL D KL P 0 P t D KL P 0 x P 0 x + dt d dt D KLP 0 x P t x t= [ : ] D KL P 0 x P t x dt D D exp d= y x d Ey u Ex u } d. 307 y x d x d CD 307 L MPF u D D exp d= y x d u L MPF u u = D D d= y x d Ey u u Ey u Ex u } d. 308 Exd u exp Ey u Ex u } d 309 u 48

47 CD P x u Ky, x = log. 30 P y u CD Ky, x u CD = D D d= x[t]} fx[], x[0] W u x[t + ] x[t]δ x[0] x d 3 Ky, x u MPF = D d= y,x t=0 D fy, xw u y xδ x x d 3 Ky, x u MCMC = D D fy, xp y uδ x x d 33 d= y,x i y i = x d i Ey u Ex d u = x d i h i + J ij x d 34 j i j i L MPF u = D N exp D h i + J ij x d j x d i. 35 j i d= i= L MPF u J ij = D L MPF u h i = D D d= D d= x d i x d i exp h i + J ij x d j x d i j i exp h i + J ij x d j x d i j i x d j J ij L [5] 49

48 L min u Lu + λ J ij i<j 38 J ij = J ji min u L MPFu + λ J ij i<j 39 λ > 0 λ L gu = Lu gu = L MPF u fu = u u[t + ] = arg min u fu + gu T u u[t] + L } u u[t] 30 LASSO gu q L u, u[t ]. L[0] α >. L[t] u[t] u[t] = arg min u fu + q L u, u[t ]} 3 3. gu[t] gu[t] q L u[t], u[t ] 3 i L[t] = α i L[t ] LASSO FISTA N = 5 NN / = J ij 0 h i 5000 L 7 50

5 0.8 0 0.6 5 0.4 0 0. 5 0 5 0 5 0 5 5 0 5 0 5 5 0 5 0 5 0.8 0.7 0.6 0.5 0.4 0.3 0. 0. 5 0 5 0 5 5 0 5 0 5 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0. 0. 7: L L [] D. L. Donoho: Discrete & Comput. Geom.

Montanari: Proc. Nat. Acad. Sci., 06, 009 894. [5] M. Lustig, D. L. Donoho and J. M. Pauly: Magn. Reson. Med., 58, 007 8. [6] R. Tibshirani: J. R. Statist. Soc. B, 58, 996 67. [7] M. Honma, K.

49 : L L [] D. L. Donoho: Discrete & Comput. Geom., 35, [] D. L. Donoho and J. Tanner: Proc. Nat. Acad. Sci., 0, [3] Y. Kabashima, T. Wadayama and T. Tanaa: J. Stat. Mech.: Theory Exp., 006 L [4] D. L. Donoho, A. Malei and A. Montanari: Proc. Nat. Acad. Sci., 06, [5] M. Lustig, D. L. Donoho and J. M. Pauly: Magn. Reson. Med., 58, [6] R. Tibshirani: J. R. Statist. Soc. B, 58, [7] M. Honma, K. Aiyama, M. Uemura and S. Ieda: Publ. Astron. Soc. Jpn. 66, [8] A. Bec and M. Teboulle: SIAM J. Imaging Sci., [9] M. F. Duarte, M. A. Davenport, D. Tahar, J. N. Lasa, T. Sun, K. F. Kelly and R. G. Baraniu: IEEE Signal Process. Mag. 5, [0] W. Yin, S. Osher, D. Goldfarb and J. Darbon: SIAM J. Imag. Science, [] S. Boyd, N. Parih, E. Chu, B. Peleato and J. Ecstein: Foundations and Trends in Machine Learning, [] A. Bec and M. Teboulle: IEEE Trans. Image Processing 8, [3] J. Huang, S. Zhang, abd D. Metaxas: Lecture Note in Computer Science [4] H. J. Kappen and F. B. Rodrguez: J. Neural Comp [5] J. S. Yedidia, W. T. Freeman and Y. Weiss: Mitsubishi Electric Research Laboratories, Tech. Rep. TR00-35, 00. [6] Mu. Yasuda and K. Tanaa: Phys. Rev. E, 87, [7] J. Raymond and F. Ricci-Tersenghi: Phys. Rev. E, 87, [8] J. Besag: Journal of the Royal Statistical Society. Series D The Statistician,

50 [9] N.Metropolis, A.W.Rosenbluth, M.N.Rosenbluth, A.H.Teller and E. Teller: J.Chem. Phys., [0] H. Suwa and S. Todo: Phys. Rev. Lett. 05, [] K. S. Turitsyn, M. Chertov, and M. Vucelja: Phys. D Amsterdam, Neth. 40, [] A. Ichii and M. Ohzei: Phys. Rev. E 88, [3] M. Welling, and G. Hinton: Artificial Neural Networs, 44, [4] J. Sohl-Dicstein, and P. B. Battaglino and M. R. DeWeese: Phys. Rev. Lett., 07, [5] M. Ohzei: J. Phys. Soc. Jpn

M = N M N M < N. N x 0 0 K M K M < N M > K N x M y M N A y = Ax 3) M < N x K M > K K N K y = Ax N K N K K y = Ax.3 L L0 x 0 x L 0 x min x x 0 s.t. y =

:06.07.. x + x = ) x = x + x x x, x ) N x y = Ax ) M y A M N x E-mail: mohzeki@i.kyoto-u.ac.jp 3 M = N M N M < N. N x 0 0 K M K M < N M > K N x M y M N A y = Ax 3) M < N x K M > K K N K y = Ax N K N K