,.,. NP,., ,.,,.,.,,, (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., , tatsukaw

Size: px

Start display at page:

Download ",.,. NP,., ,.,,.,.,,, (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., , tatsukaw"

ゆきじゅふく
5 years ago
Views:

1 ,.,. NP,., ,.,,.,.,,, (PCA)...,,. Tipping and Bishop (1999) PCA. (PPCA)., (Ilin and Raiko, 2010). PPCA EM., , tatsukawa.m.aa@m.titech.ac.jp, , mirai@ism.ac.jp 1

2 1.1.2, itunes, Amazon, Netflix.,,,.,,.,,., : m n, 5. 1,. m n. m = 3, n = 5 : V = a b c d e A 2 5? 4 1 B 1? (1) C? 1 4? 5 V,., A b 5, c.,?. (1), A B., A B., b A 5, B.,,...,, 3 (Su and Khoshgoftaar, 2009).,,,.,..,., Pearson.,,.,,.,,.,.. 1, 2

3 .,, V (R {?}) m n.?,., V ij =? V ij. Candés and Recht (2009) V V. : minimize rank(x) subject to X ij = V ij ((i, j) Ω). (2), X R m n V. Ω, Ω = {(i, j) : V ij R}. (2), l 0, NP., (2). (SDP)., SDP., SDP,. Olsson and Oskarsson (2009); Gillis and Glineur (2011), V, : m n minimize W ij (X ij V ij ) 2 i=1 j=1 subject to rank(x) r. W {0, 1} m n, W ij = 1 V ij R, W ij = 0. Ω = {(i, j) : V ij R} = {(i, j) : W ij = 1}, (3) : minimize (X ij V ij ) 2 (i,j) Ω (4) subject to rank(x) r. Ω. Olsson and Oskarsson (2009) (3). Gillis and Glineur (2011) (3) (4) NP. (3) 3

4 ,., Ω, (4) : minimize X V 2 F subject to rank(x) r., V., r l=1 σ lp l q l (Trefethen and Bau, 1997, Theorem 5.9). σ l, p l, q l V l. V., O(min{m 2 n, mn 2 }),., r, r..,. 1,,, (Sarwar et al., 2000). : 1. V,,. ˆV., (i, j) Ω ˆV ij = (1/ {i : (i, j) Ω} ) i :(i,j) Ω V i j. 2. µ. µ i µ i V i., µ i = (1/ {j : (i, j) Ω} ) j:(i,j) Ω V ij. 3., ˆV µ1 r V r V V r + µ : 2. 3 NP. (4), NP.,,. 4,.,

5 2,., X R m n V (R {?}) m n. V X.. X, L X U. L (R { }) m n, U (R {+ }) m n L U,., L X i, j L ij X ij.,,., Amazon 1 5., L, U.., (i, j) V ij δ, L ij = V ij δ, U ij = V ij + δ.,., Y R m n, Y., X Y 2 Frobenius X Y 2 F., : minimize X Y 2 F + λ subject to rank(x) r, L Y U. (i,j) Ω (Y ij V ij ) 2 λ 2. λ,, V Y. λ,, V, 2 Y. (5) 3 NP (5) NP., : 1. V ([0, 1] {?}) m n r = 1, (5), 2 12 (mn) 7 NP., : 5

6 2 (Gillis and Glineur (2011, Theorem 1.2)). V ([0, 1] {?}) m n r = 1, (4), 2 12 (mn) 7 NP. Proof of Theorem 1. (5), (i, j) Ω L ij = U ij = V ij, (i, j) / Ω L ij = U ij = +., (i, j) Ω Y ij = V ij, 0. (i,j) Ω (X ij V ij ) 2 + (i,j) Ω (X ij Y ij ) 2., (i, j) Ω Y ij X ij, 0., (4)., (4) (5).., (5) NP r (Gillis and Glineur, 2011, Remark 3), 1 r. 4, (5). : f 0 (X, Y ) = X Y 2 F + λ (Y ij V ij ) 2, (i,j) Ω f 1 (X) = ι(rank(x) r), f 2 (Y ) = ι(l Y U), f(x, Y ) = f 0 (X, Y ) + f 1 (X) + f 2 (Y ), ι., rank(x) r f 1 (X) = 0; f 1 (X) = +. f(x, Y ) (5)., f(x, Y ) X Y. f(x, Y ) (5) (X (0), Y (0) ) dom f 1 dom f 2. for k = 0, 1, 2,... ( ): X (k+1) = argmin X f(x, Y (k) ). Y (k+1) = argmin Y f(x (k+1), Y ). X, X (k+1) Y (k) r., X (k+1) 6

7 : minimize X Y (k) 2 F subject to rank(x) r., Y (k). Y. Y : minimize X (k+1) Y 2 F + λ (Y ij V ij ) 2 subject to L Y U. (i,j) Ω., 1 2., (i, j) Ω, (i, j) Ω minimize (1 + λ)yij 2 2(X(k+1) ij + λv ij )Y ij subject to L ij Y ij U ij minimize Yij 2 2X(k+1) ij subject to L ij Y ij U ij. : L ij (A ij L ij ), Y (k+1) ij = A ij (L ij < A ij < U ij ), U ij (U ij A ij ). A ij = X (k+1) ij X (k+1) 1 + λ + λv ij Y ij ((i, j) Ω), ij ((i, j) Ω)., (6), O(mn). 1, f., 2, Tseng (2001) ( X, Ȳ ) f. 2, ( X, Ȳ ) dom f = {(X, Y ) : f(x, Y ) < + } (6) f ( X, Ȳ ; X, Y ) 0 ( ( X, Y )). f ( X, Ȳ ; X, Y ) ( X, Ȳ ), ( X, Y ) f,, f ( X, Ȳ ; X, Y ) = lim inf f( X + X, Ȳ + Y ) f( X, Ȳ ) 7

8 . f.,. 3. {(X (k), Y (k) )} 1, L = {(X, Y ) : f(x, Y ) f(x (0), Y (0) )}., {(X (k), Y (k) )} 1., f.,. 1. dom f. Proof., dom f = dom f 1 dom f 2 dom f 2., dom f 1. X dom f 1., r X σ r (X). E 2 < σ r (X) E. Golub and van Loan (2013, Corollary 8.6.2), X + E dom f 1, l = 1,..., r σ l (X + E) σ l (X) E 2 > 0. dom f Tseng (2001, Sections 3 and 4). 3., {(X (k), Y (k) )} L dom f., {(X (k), Y (k) )}. 1 dom f, {(X (k), Y (k) )} dom f 1. {(X (kj), Y (kj) )}, ( X, Ȳ ) {(X(k), Y (k) )}. ( X, Ȳ ), ( X, Ȳ ) dom f, ( X, Y ) f ( X, Ȳ ; X, Y ) 0., f(x (kj+1), Y (kj+1) ) f(x (kj+1), Y (kj) ) f(x, Y (kj) ) ( X). f dom f, j f( X, Ȳ ) f(x, Ȳ ) ( X) (7)., f(x (k j), Y (k j) ) f(x (k j), Y ) ( Y ) j f( X, Ȳ ) f( X, Y ) ( Y ) (8). f 0, ( X, Y ) : f ( X, Ȳ ; X, Y ) = f 0 ( X, Ȳ ), ( X, Y ) + lim inf ( f1 ( X + X) f 1 ( X) + f 2(Ȳ + Y ) f 2(Ȳ ) ) 8

9 X f 0 ( X, Ȳ ), X + Y f 0 ( X, Ȳ ), Y + lim inf f 1 ( X + X) f 1 ( X) + lim inf f 2 (Ȳ + Y ) f 2(Ȳ ) = X f 0 ( X, Ȳ ), X + Y f 0 ( X, Ȳ ), Y + f 1( X; X) + f 2(Ȳ ; Y ) f( = lim inf X + X, Ȳ ) f( X, Ȳ ) f( X, Ȳ + Y ) f( X, Ȳ ) + lim inf 0., (7) (8). 2. L = {(X, Y ) : f(x, Y ) f(x (0), Y (0) )},, i, j L ij > U ij < +. 3., Y. Y,., Y Y,. 5,. OS MacOS Sierra , CPU Intel Core m3 1.1 GHz, RAM 8 GB. MATLAB (R2017b).., rank(a) = 10 i, j 0.5 A ij 5.5 A R :, 2 B R 20 9, C R , 0.5 A ij 5.5. A Āij {1, 2,..., 5}, 80%. V., r r = 10, λ λ = 1., 4. SKKR V Sarwar et al. (2000),. perturb + SKKR V Sarwar et al. (2000),. low rank rand A. rand ,. 9

10 objective value objective value SKKR perturb + SKKR low rank rand rand iteration number 1: 0.8 perturb + SKKR low rank rand rand 2: SKKR 1, perturb + SKKR, low rank rand, and rand 10,. 1.,. 1, perturb + SKKR low rank rand, SKKR., rand. 2.., , SKKR. 2, perturb + SKKR low rank rand, SKKR. rand, SKKR. 6,..,.,,.,.,,.,, r λ,.. 10

11 REFERENCES Candés, E. J. and Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6): Gillis, N. and Glineur, F. (2011). Low-rank matrix approximation with weights or missing data is NP-hard. SIAM Journal on Matrix Analysis and Applications, 32(4): Golub, G. H. and van Loan, C. F. (2013). Matrix Computations. The Johns Hopkins University Press, fourth edition. Ilin, A. and Raiko, T. (2010). Practical approaches to principal component analysis in the presence of missing values. Journal of Machine Learning Research, 11(Jul): Olsson, C. and Oskarsson, M. (2009). A convex approach to low rank matrix approximation with missing data. In Salberg, A.-B., Hardeberg, J. Y., and Jenssen, R., editors, Proceedings of the 16th Scandinavian Conference on Image Analysis (SCIA 09), pages Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. (2000). Application of dimensionality reduction in recommender system a case study. In Kohavi, R., Masand, B., Spiliopoulou, M., and Srivastava, J., editors, Proceedings of the ACM WEBKDD 2000 Workshop. Su, X. and Khoshgoftaar, T. M. (2009). A survey of collaborative filtering techniques. Advances in Artificial Intelligence, 2009(421425):1 19. Tipping, M. E. and Bishop, C. M. (1999). Probabilistic principal component analysis. Journal of the Royal Statistical Society. Series B, 61(3): Trefethen, L. N. and Bau, D. (1997). Numerical Linear Algebra. SIAM. Tseng, P. (2001). Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of Optimization Theory and Applications, 109(3):

icml10yomikai.key

icml10yomikai.key A Fast Augmented Lagrangian Algorithm for Learning Low- Rank Matrices Ryota Tomioka, Taiji Suzuki, Masashi Sugiyama, Hisashi Kashima 2010/8/18 ICML2010 1 Matrix completion [Srebro et al. 05; Abernethy