Big Data Analytics Big Data Analytics D. Distributed Machine Learning Algorithms / D.2 Distributed Matrix Factorization Lars Schmidt-Thieme Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim, Germany Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 24
Big Data Analytics Syllabus Tue. 4.4. (1) 0. Introduction A. Parallel Computing Tue. 11.4. (2) A.1 Threads Tue. 18.4. (3) A.2 Message Passing Interface (MPI) B. Distributed Storage Tue. 25.4. (4) B.1 Distributed File Systems Tue. 2.5. (5) B.2 Partioning of Relational Databases Tue. 9.5. (6) B.3 NoSQL Databases Tue. 16.5. (7) A.3 Graphical Processing Units (GPUs) C. Distributed Computing Environments Tue. 23.5. (8) C.1 Map-Reduce Tue. 30.5. (9) C.2 Resilient Distributed Datasets (Spark) Tue. 6.6. — — Pentecoste Break — D. Distributed Machine Learning Algorithms Tue. 13.6. (10) D.1 Distributed Stochastic Gradient Descent Tue. 20.6. (11) D.2 Distributed Matrix Factorization Tue. 27.6. (12) D.3 Alternating Direction Method of Multipliers (ADMM) Tue. 4.7. (13) Questions and Answers Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 24
Big Data Analytics Outline 1. Introduction 2. Matrix Factorization via Distributed SGD 3. NOMAD Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 24
Big Data Analytics 1. Introduction Outline 1. Introduction 2. Matrix Factorization via Distributed SGD 3. NOMAD Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 24
Big Data Analytics 1. Introduction The Matrix Completion Problem Given I the values D ⊆ [N] × [M] × R of some cells of an unknown matrix Y ∈ RN×M (called data) and I a function ` : R × R → R (called loss), predict the values of the missing cells, i.e. find a completion Yˆ ∈ RN×M with minimal error ∑N ∑M err( ˆY,Y) := `(Y ,Yˆ ) n,m n,m n=1 m=1 Note: [N] := {1, . . . ,N}. Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 1 / 24
Big Data Analytics 1. Introduction The Matrix Factorization Model I the basic model: Yˆ :=WH, W ∈ RN×K ,H ∈ RK×M i.e., Yˆ :=W H n,m n,. .,m I K is called latent dimension Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 2 / 24
Big Data Analytics 1. Introduction The Matrix Factorization Model I the basic model: Yˆ :=WH, W ∈ RN×K ,H ∈ RK×M i.e., Yˆ :=W H n,m n,. .,m I K is called latent dimension I parameters are regularized, i.e., minimize 1 ∑ f (W,H) := `(y,W H ) + λ(||W||2 + ||H||2) |D| n,. .,m 2 2 (n,m,y)∈D Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 2 / 24
Big Data Analytics 1. Introduction The Matrix Factorization Model I the basic model: Yˆ :=WH, W ∈ RN×K ,H ∈ RK×M i.e., Yˆ :=W H n,m n,. .,m I K is called latent dimension I parameters are regularized, i.e., minimize 1 ∑ f (W,H) := `(y,W H ) + λ(||W||2 + ||H||2) |D| n,. .,m 2 2 (n,m,y)∈D I usually a global offset a and bias terms are used, i.e., fix Wn,1 :=1, H2,m := 1 yielding Yˆ =a + W + H + W H n,m n,2 1,m n,3:K 3:K,m =a + b + c + wT h Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germanyn m n m 2 / 24
Big Data Analytics 1. Introduction Problem Equivalence I The matrix completion problem really is a prediction problem with X := {0,1}N × {0,1}M, Y := R Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 3 / 24
Big Data Analytics 1. Introduction Stochastic Gradient Descent for Matrix Factorization 1 ∑ f (W,H) := `(y,W H ) + λ(||W||2 + ||H||2) |D| n,. .,m 2 2 (n,m,y)∈D ∑ ( ) ∝ `(y,W H ) + λ(||W||2 + ||H||2) n,. .,m 2 2 (n,m,y)∈D Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 4 / 24
Big Data Analytics 1. Introduction Stochastic Gradient Descent for Matrix Factorization 1 ∑ f (W,H) := `(y,W H ) + λ(||W||2 + ||H||2) |D| n,. .,m 2 2 (n,m,y)∈D ∑ ( ) ∝ `(y,W H ) + λ(||W||2 + ||H||2) n,. .,m 2 2 (n,m,y)∈D ∑ |D| = (`(y,W H ) + λ( ||W ||2 n,. .,m freq1(D,n) n,. 2 (n,m,y)∈D |D| 2 + ||H.,m||2)) freq2(D,m) with freq1(D,n) := |{(n′,m′,y) ∈ D | n′ = n}|, freq2(D,m) := |{(n′,m′,y) ∈ D | m′ = m}| Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 4 / 24
Big Data Analytics 1. Introduction Stochastic Gradient Descent for Matrix Factorization 1 ∑ f (W,H) := `(y,W H ) + λ(||W||2 + ||H||2) |D| n,. .,m 2 2 (n,m,y)∈D ∑ ( ) ∝ `(y,W H ) + λ(||W||2 + ||H||2) n,. .,m 2 2 (n,m,y)∈D ∑ |D| = (`(y,W H ) + λ( ||W ||2 n,. .,m freq1(D,n) n,. 2 (n,m,y)∈D |D| 2 + ||H.,m||2)) freq2(D,m) ∑ = (`(y,wT h ) + λ1||w ||2 + λ2 ||h ||2)) n m n n 2 m m 2 (n,m,y)∈D with freq1(D,n) := |{(n′,m′,y) ∈ D | n′ = n}|, λ1 := λ|D|/freq1(D,n) n freq2(D,m) := |{(n′,m′,y) ∈ D | m′ = m}| λ2 := λ|D|/freq2(D,m) m Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 4 / 24
Big Data Analytics 1. Introduction Stochastic Gradient Descent for Matrix Factorization ∑ f (W,H) = (`(y,wT h ) + λ1||w ||2 + λ2 ||h ||2)) n m n n 2 m m 2 (n,m,y)∈D ∑ =: fn,m,y(wn,hm) (n,m,y)∈D ∂ f (w ,h ) = ∂ `(y,wT h )h + 2λ1w wn n,m,y n m yˆ n m m n n Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 5 / 24
Big Data Analytics 1. Introduction Stochastic Gradient Descent for Matrix Factorization ∑ f (W,H) = (`(y,wT h ) + λ1||w ||2 + λ2 ||h ||2)) n m n n 2 m m 2 (n,m,y)∈D ∑ =: fn,m,y(wn,hm) (n,m,y)∈D ∂ f (w ,h ) = ∂ `(y,wT h )h + 2λ1w wn n,m,y n m yˆ n m m n n ∂ f (w ,h ) = ∂ `(y,wT h )w + 2λ2 h hm n,m,y n m yˆ n m n m m Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 5 / 24
Big Data Analytics 1. Introduction Stochastic Gradient Descent for Matrix Factorization ∑ f (W,H) = (`(y,wT h ) + λ1||w ||2 + λ2 ||h ||2)) n m n n 2 m m 2 (n,m,y)∈D ∑ =: fn,m,y(wn,hm) (n,m,y)∈D ∂ f (w ,h ) = ∂ `(y,wT h )h + 2λ1w wn n,m,y n m yˆ n m m n n ∂ f (w ,h ) = ∂ `(y,wT h )w + 2λ2 h hm n,m,y n m yˆ n m n m m The derivative of the loss needs to be computed once, e.g., for `(y,yˆ) := (ˆy − y)2 ∂yˆ`(y,yˆ) = 2(ˆy − y) Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 5 / 24
Big Data Analytics 1. Introduction Stochastic Gradient Descent for Matrix Factorization 1 sgd−mf(∂yˆ`,∑N,M,D,K, λ,T, η): a := 1 y 2 |D| (n,m,y)∈D randomly initialize W ∈ RN×K and H ∈ RM×K 3 4 Wn,1 := 1 for all n := 1, . . . ,N 5 Hm,2 := 1 for all m := 1, . . . ,M λ1 := 2λ |D| for all n := 1, . . . ,N 6 n |{(n′,m′,y)∈D|n′=n}| λ2 := 2λ |D| for all m := 1, . . . ,M 7 m |{(n′,m′,y)∈D|m′=m}| 8 9 for t = 1, . . . ,T: 10 for (n,m,y) ∈ D (in random order): e := ∂ `(y,a + wT h ) 11 yˆ n m w := w − η(eh + λ1w ) 12 n n m n n h := h − η(ew + λ2 h ) 13 m m n m m 14 wn,1 := 1,hm,2 := 1 15 16 return (a,W,H) Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 6 / 24
Big Data Analytics 2. Matrix Factorization via Distributed SGD Outline 1. Introduction 2. Matrix Factorization via Distributed SGD 3. NOMAD Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 7 / 24
Big Data Analytics 2. Matrix Factorization via Distributed SGD Idea I partition the data into row subsets R1, . . . ,RP, i.e., Dp := D := {(n,m,y) ∈ D | n ∈ R } |Rp p across P workers I avoid conflicting distributed SGD updates by I also partitioning the columns into P subsets C1, . . . ,CP I for each epoch, make P passes over the data (at each worker), in every pass working on each worker on a different column subset, making sure every column subset finally is worked on every worker W|R := (Wr,k)r∈R ,k∈{1,...,K} p p H|C := (Hc,k)c∈C ,k∈{1,...,K} q q Dp := {(n,m,y) ∈ Dp | m ∈ C } |C q q Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 7 / 24
Big Data Analytics 2. Matrix Factorization via Distributed SGD Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 8 / 24
Big Data Analytics 2. Matrix Factorization via Distributed SGD Distributed SGD for Matrix Factorization 1 sgd-dsgd(∂yˆ `, N, M, D, K, λ, T, η, R, C): 2 for p ∈ {1, . . . , P} (in parallel): 3 randomly initialize Wp ∈ RRp×K 4 Wp := 1 for all n ∈ R n,1 ∑ p 5 ap := y (n,m,y)∈Dp 6 push ap to server 7 1 ∑P p 8 a := p=1 a |D| 9 randomly initialize H ∈ RM×K 10 Hm,2 := 1 for all m := 1, . . . , M 11 12 for t = 1, . . . , T: 13 for q = 1, . . . , P: 14 for p := 1, . . . , P in parallel: 15 qp := 1 + (q + p − 2 mod P) 16 pop Cp := C p , Hp := H from server q |Cqp 17 sgd-mf-update(∂ `, R , Cp, Dp , K, λ, T = 1, η, a; Wp, Hp) yˆ p |C p 18 push H := Hp to server |Cqp 19 20 for p := 1, . . . , P in parallel: 21 push W := Wp to server |Rp 22 23 return (a, W, H) Lars Schmidt-Thieme, Information Systems and Machine Learning Lab (ISMLL), University of Hildesheim, Germany 9 / 24
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!