Share
Matrix and Tensor Factorization for Machineย Learning
You can donwload the slide here.
Matrices and tensors, or multidimensional arrays, are highly versatile data structures. They can store a variety of formats: image, video, table, and sensing data. By decomposing such matrices and tensors, we can extract insight from the data: patterns, features, etc. In this lecture, I introduce singular value decomposition (SVD) for matrices, non-negative matrix factorization (NMF) for non-negative matrices, and CP and Tucker decomposition for tensors. The objective is not only to understand the various decomposition methods in a piecemeal manner but also to acquire the know-how to select the appropriate decomposition method according to the situation and various constraints in real-world scenarios while focusing on the properties of each decomposition. For downstream applications of the methods, the lecture will cover subspace methods (CLAFIC) for classification tasks and EM-based methods for determining missing values in given input data. In the last segment of the lecture, I will cover some of the difficulties of tensor decomposition (TD). TD suffers from difficulties that do not occur in SVD, such as ill-posedness and NP-hardness in optimization, and will discuss recent research trends for avoiding these difficulties.
Kazu Ghalamkari
Transcript
132 slides
-
Matrix and Tensor Factorization for Machine Learning Special Topics in
Mechano-Informatics โ ก@ Tokyo University, 2024 Kazu Ghalamkari RIKEN AIP @KazuGhalamkari -
3 3 Announcements Please click the raise hand button if
you can see the slides and hear me clearly. Please refrain from redistributing slides. Feel free to ask any questions using the chat window during the lecture. ๐ The assignment is available on the final section. Some parts of the slide will be skipped due to time limitation. -
4 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
Diverse real-world data โช Purchase history โช Tabular data Sepal
Length [cm] Sepal Width [cm] Petal Length [cm] Petal Width [cm] Species 5.1 3.5 1.4 0.2 setosa 7 3.2 4.7 1.4 versicolor 6.4 3.2 4.5 1.5 versicolor 4.7 3.2 1.3 0.2 setosa 4.6 3.1 1.5 0.2 setosa 6.5 2.8 4.6 1.5 versicolor 6.6 2.9 4.6 1.3 versicolor 4.9 3 1.4 0.2 setosa 5.2 2.7 3.9 1.4 versicolor โช Grayscale image Decomposing the data as a matrix is beneficial โช Spectrum information Image from https://www.mathworks.com/help/images/image-types-in-the-toolbox_ja_JP.html Image from https://sigview.com/help/Time-FFTSpectrogram.html Image from Mithy, S. A., et al. "Classification of Iris Flower Dataset using Different Algorithms." Int. J. Sci. Res. In (2022). -
What is a good decomposition? ใปIs the decomposed representation interpretable?
ใปIs the decomposition scalable to large data? ใปIs the decomposed representation unique? ใปCan the decomposition be done even with missing values? Many Choose appropriate decomposition method by considering real-world constraints Many -
11 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
Rank in linear algebra Each column is a constant multiple
of vector . We call such a matrix a rank-1 matrix. 6-dimensional vector space 12 -
Rank in linear algebra Each row is a constant multiple
of vector . We call such a matrix a rank-1 matrix. 6-dimensional vector space 13 -
Rank in linear algebra Each column of this matrix is
written by a linear combination of the base . The rank-2 matrix is the matrix that is a linear combination of two linearly independent vectors. Each column vector is in a 2-dimensional plane in the 6-dimensional vector space. Plane spanned by 6-dimensional vector space 15 -
Rank in linear algebra When the column vector of A
can be written by linear combination of , is the rank of matrix . Linear independent ๐ vectors (Basis) the rank of matrix A is the minimum integer number of ๐. A matrix whose rank is ๐ is called a rank ๐ matrix. Def. 16 -
Properties of the matrix rank Basis A is full rank
when . A is rank deficient if . Rank Property 18 -
21 Summary: matrix rank Basis Rank Properties When the column
vector of A can be written by linear combination of , the rank of matrix A is the minimum integer number of ๐. Def. -
22 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
the base could be any linearly independent vectors. Singular value
decomposition, SVD So far, we assumed that Imposes orthonormality on 23 -
Singular value decomposition, SVD Most significant rank-1 factor Least significant
rank-1 factor Important term Unimportant term Imposes orthonormality on : weight (importance) of the following rank-1 matrix Singular value -
Singular value decomposition, SVD Imposes orthonormality on : weight (importance)
of the following rank-1 matrix Singular value 25 -
Singular value decomposition, SVD โช Any matrix A can be
decomposed into the product of U, V, and a diagonal matrix ฮฃ It can be a complex, non-singular, or rectangular matrix 26 -
Singular value decomposition, SVD โช Any matrix A can be
decomposed into the product of U, V, and a diagonal matrix ฮฃ 27 It can be a complex, non-singular, or rectangular matrix -
Singular value decomposition, SVD โช A is a rank- matrix
Unnecessary 0 28 -
Singular value decomposition, SVD Rank and Singular Value 0 Unnecessary
The rank of matrix A is the number of non-zero singular values of A โช A is a rank- matrix 29 -
Low-rank approximation by SVD They are not as important, so
let's set them to 0 and ignore them. Important term Unimportant term โ 0 โช Decomposing rank-๐ matrix ๐ into orthogonal ๐ and ๐ and diagonal matrix โ. Singular value : weight of the following rank-1 matrix 30 -
Low-rank approximation by SVD โ 0 โช Decomposing rank-๐ matrix
๐ into orthogonal ๐ and ๐ and diagonal matrix โ. Approximating a matrix by a smaller rank matrix Low-rank approximation They are not as important, so let's set them to 0 and ignore them. Singular value : weight of the following rank-1 matrix 31 -
The BEST Low-rank approximation by SVD โช SVD provides the
best low-rank approximation minimizing Frobenius norm. is the best rank-k approximation for ๐, which minimizes Frobenius norm. Evaluate how close they are via the Frobenius norm. Frobenius norm Eckart-Young Theorem (1936) 32 -
The BEST Low-rank approximation by SVD โช SVD is the
best low-rank approximation minimizing unitary invariant norm. is the best rank-r matrix for ๐, which minimizes any unitary invariant norm. Evaluate how similar they are via unitary invariant norm. Eckart-Young-Mirsky Theorem (1960) * Unitary invariant norm โ โ satisfies that ๐ โ = ๐๐๐ โ for any matrix P and any unitary matrices X and Y. 33 -
Low-rank approximation of matrices saves memory. Required memory before the
approximation Required memory sizes after approximation Low-rank approximation reduces required memory storage Example: Assuming is sufficiently smaller than . 34 -
Singular values and eigenvalues Put into The ๐-th singular value
๐๐ of matrix ๐ is the square root of the ๐-th eigenvalue ฮป๐ of matrix ๐๐โค 35 -
Singular values and eigenvalues Each column vector is orthonormal Put
into The ๐-th singular value ๐๐ of matrix ๐ is the square root of the ๐-th eigenvalue ฮป๐ of matrix ๐๐โค 36 -
Singular values and eigenvalues Each column vector is orthonormal Put
into The ๐-th singular value ๐๐ of matrix ๐ is the square root of the ๐-th eigenvalue ฮป๐ of matrix ๐๐โค 37 -
Singular values and eigenvalues Each column vector is orthonormal Put
into The ๐-th singular value ๐๐ of matrix ๐ is the square root of the ๐-th eigenvalue ฮป๐ of matrix ๐๐โค 38 -
The ๐-th singular value ๐๐ of matrix ๐ is the
square root of the ๐-th eigenvalue ฮป๐ of matrix ๐๐โค Eigenvalue of Eigenvector of Singular values and eigenvalues Each column vector is orthonormal Put into ๐ -th column of U ๐ -th column of V (๐, ๐)-entry of โ -
Singular values and eigenvalues Eigenvector of Put into Eigenvalue of
Eigenvector of The ๐-th singular value ๐๐ of matrix ๐ is the square root of the ๐-th eigenvalue ฮป๐ of matrix ๐๐โค Put into ๐ -th column of U ๐ -th column of V (๐, ๐)-entry of โ -
Singular values and eigenvalues (Left singular vector) The ๐-th singular
value ๐๐ of matrix ๐ is the square root of the ๐-th eigenvalue ฮป๐ of matrix ๐๐โค SVD of A is an eigenvalue decomposition of ๐๐โค and ๐โค๐ The rank of matrix ๐ equals the number of non-zero singular values of ๐. Each column vector of ๐ is an eigenvector of ๐โค๐. Each column vector of ๐ is an eigenvector of ๐๐โค. (Right singular vector) -
Example of low-rank approximation by SVD in Python Smaller rank
๐ worsens the approximation performance. 46 -
Image reconstruction by SVD How many ranks are needed for
reconstruction? 2000ร1500 (2000+1500)ร5 (2000+1500)ร20 (2000+1500)ร100 ๐=100, 11.67% storage ๐=20, 2.33% storage ๐=5, 0.57% storage ใใญในใใๅซใพใใฆใใ็ปๅ ่ชๅ็ใซ็ๆใ ใใ่ชฌๆ Image from Steven L. Brunton, J. Nathan Kutz, โData-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Controlโ Image from Steven L. Brunton, J. Nathan Kutz, โData-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Controlโ 47 -
Hyperparameter tuning in SVD Accurate Rough Increased memory Slow Memory
saving High speed (2000+1500)ร5 (2000+1500)ร20 (2000+1500)ร100 Selecting the appropriate rank is a trade-off problem. It requires repeated trial and error. A typical hyper-parameter tuning problem ๐=100, 11.67% storage ๐=20, 2.33% storage ๐=5, 0.57% storage ใใญในใใๅซใพใใฆใใ็ปๅ ่ชๅ็ใซ็ๆใ ใใ่ชฌๆ Image from Steven L. Brunton, J. Nathan Kutz, โData-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Controlโ Image from Steven L. Brunton, J. Nathan Kutz, โData-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Controlโ 48 -
Data are represented by a low-rank structure plus noise. Most
of the data in this world has a low-rank structure. Real data Low-rank matrix Noise Low-rank approximation is good enough for many datasets. โช Low-rank approximation can approximate real-world data well. 49 -
50 Singular values Summary: Low-rank approximation and SVD โช SVD
can be applied to any matrix. โช SVD finds the best low-rank matrix minimizing the Frobenius norm. are orthonormal. SVD provides the best rank-k approximation that minimizes the Frobenius norm. Eckart โ Young Theorem โช Low-rank approximation reduces data memory requirements. -
52 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
Classification of Iris Data Sepal Petal Sepal Petal โช Iris
Dataset[1] [1] Fisher, Ronald A. "The use of multiple measurements in taxonomic problems." Annals of eugenics 7.2 (1936): 179-188. We estimate the species of iris data-points based on their sepal and petal lengths. Sepal Length [cm] Sepal Width [cm] Petal Length [cm] Petal Width [cm] Species 5.1 3.5 1.4 0.2 setosa 7 3.2 4.7 1.4 versicolor 6.4 3.2 4.5 1.5 versicolor 4.7 3.2 1.3 0.2 setosa 4.6 3.1 1.5 0.2 setosa 6.5 2.8 4.6 1.5 versicolor 6.3 3.3 4.7 1.6 versicolor 6.6 2.9 4.6 1.3 versicolor 4.9 3 1.4 0.2 setosa 5.2 2.7 3.9 1.4 versicolor 5.9 3 4.2 1.5 ??? 5.6 3 4.5 1.5 ??? 4.7 3.2 1.6 0.2 ??? โฆ โฆ Image from Mithy, S. A., et al. "Classification of Iris Flower Dataset using Different Algorithms." Int. J. Sci. Res. In (2022). 53 -
Classification by the CLAFIC method Samples of class A Samples
of class B Estimate class of each sample Classification Training data setosa versicolor Sepal Length [cm] Sepal Width [cm] Petal Length [cm] Petal Width [cm] Species 5.1 3.5 1.4 0.2 setosa 7 3.2 4.7 1.4 versicolor 6.4 3.2 4.5 1.5 versicolor 4.7 3.2 1.3 0.2 setosa 4.6 3.1 1.5 0.2 setosa 6.5 2.8 4.6 1.5 versicolor 6.3 3.3 4.7 1.6 versicolor 6.6 2.9 4.6 1.3 versicolor 4.9 3 1.4 0.2 setosa 5.2 2.7 3.9 1.4 versicolor 5.9 3 4.2 1.5 ??? 5.6 3 4.5 1.5 ??? 4.7 3.2 1.6 0.2 ??? โฆ โฆ 54 -
Classification by the CLAFIC method Sepal Length [cm] Petal Width
[cm] Sepal Width [cm] Samples of class A Samples of class B Estimate class of each sample Classification Training data setosa versicolor 55 -
Classification by the CLAFIC method Samples of class A Samples
of class B Estimate class of each sample Classification Training data setosa versicolor Sepal Length [cm] Petal Width [cm] Sepal Width [cm] 56 -
Classification by the CLAFIC method Samples of class A Samples
of class B Estimate class of each sample Classification Training data setosa versicolor 57 -
Classification by the CLAFIC method Samples of class A Samples
of class B Estimate class of each sample Classification Training data setosa versicolor 58 -
Classification by the CLAFIC method Samples of class A Samples
of class B Estimate class of each sample Classification Training data setosa versicolor 59 -
Classification by the CLAFIC method Samples of class A Samples
of class B Estimate class of each sample Classification Training data setosa versicolor 60 -
Classification by the CLAFIC method ๏ผWe need normalize the data
so that both subspaces pass through the origin๏ผ Samples of class A Samples of class B Estimate class of each sample Classification Training data setosa versicolor -
Classification by the CLAFIC method Orthogonal basis Orthogonal basis ๏ผhyper-parameter
Samples of class A Samples of class B Estimate class of each sample Classification Training data setosa versicolor ๏ผWe need normalize the data so that both subspaces pass through the origin๏ผ -
Classification by the CLAFIC method โช Inference Find the closest
subspace. โช Learning SVD for each class samples. Samples of class A Samples of class B Estimate class of each sample Classification Training data setosa versicolor ๏ผWe need normalize the data so that both subspaces pass through the origin๏ผ If ๐๐ < ๐๐ , ๐ belongs to class A. If ๐๐ > ๐๐ , ๐ belongs to class B. -
1-Neighborhood and CLAFIC 1-NN Classification by the nearest training data
Classification by the nearest subspace CLAFIC If ๐๐ < ๐๐ , ๐ belongs to class A. If ๐๐ > ๐๐ , ๐ belongs to class B. 64 -
65 Summary: Classification by subspace method โช Learning SVD for
each class. โช Inference Find the closest subspace. ๏ผWe need normalize the data so that both subspaces pass through the origin๏ผ If ๐๐ < ๐๐ , ๐ belongs to class A. If ๐๐ > ๐๐ , ๐ belongs to class B. -
Datasets that cannot be linearly separated โช There is no
plane (straight line) that reduces the dimension properly. โช CLAFIC is ineffective for such a dataset. Two-dimensional data space Project the data to a higher dimensional space, making the data linearly separable. 66 -
Kernel CLAFIC, Learning Projection onto the higher dimensional space makes
the data linearly separable. ๐ฟ-dimensional data space ๐(โซ ๐ฟ)-dimensional space 69 -
Kernel CLAFIC, Learning Perform SVD for each class in high-dimensional
space . ๐ฟ-dimensional data space ๐(โซ ๐ฟ)-dimensional space 70 -
Kernel CLAFIC, Inference Project the test data ๐ to the
high-dimensional space and predict the class by the closest subspace. 77 ๐ฟ-dimensional data space ๐(โซ ๐ฟ)-dimensional space If ๐๐ < ๐๐ , ๐ belongs to class A. If ๐๐ > ๐๐ , ๐ belongs to class B. -
No need to seek explicitly. Kernel trick 78 Large The
distance can be written by the eigenvalues and eigenvectors of the Kernel matrix: ๐(โซ ๐ฟ)-dimensional space -
No need to seek explicitly. Kernel trick 79 Large The
distance can be written by the eigenvalues and eigenvectors of the Kernel matrix: Typical example of a inner product (RBF Kernel) We need the similarity between the samples. ๏ผInner product๏ผ ๐(โซ ๐ฟ)-dimensional space -
Denoising by Kernel PCA[1] [1] Mika, Sebastian, et al. "Kernel
PCA and de-noising in feature spaces." Advances in neural information processing systems 11 (1998). โช Denoising : Remove noise from noisy data โฆ 28 28 โฆ 28ร28=784 -
Denoising by Kernel PCA[1] [1] Mika, Sebastian, et al. "Kernel
PCA and de-noising in feature spaces." Advances in neural information processing systems 11 (1998). (784) ๐ฟ-dimensional data space -
Denoising by Kernel PCA[1] Project the noisy data into a
low-dimensional space in . ๐ฟ-dimensional data space ๐(โซ ๐ฟ)-dimensional space -
The denoised image is obtained by the inverse mapping .
Denoising by Kernel PCA[1] ๐ฟ-dimensional data space ๐(โซ ๐ฟ)-dimensional space -
Anomaly detection by Kernel PCA [2] โช Detect anomalous samples
automatically. Normal Normal Anomaly Normal Normal Normal Normal [2] Hoffmann, Heiko. "Kernel PCA for novelty detection." Pattern recognition 40.3 (2007): 863-874. Anomaly 89 -
Anomaly detection by Kernel PCA [2] [2] Hoffmann, Heiko. "Kernel
PCA for novelty detection." Pattern recognition 40.3 (2007): 863-874. โช Normal samples ๏ผTraining data๏ผ โช Normal and anomalous samples๏ผTest data๏ผ ็ฐๅธธ ๆญฃๅธธ Normal Normal Normal Normal Normal ็ฐๅธธ Determine whether it is normal or anomalous . 90 -
Anomaly detection by Kernel PCA [2] (784) Perform the Kernel
PCA with normal samples only. 93 ๐ฟ-dimensional data space ๐(โซ ๐ฟ)-dimensional space -
Anomaly detection by Kernel PCA [2] Next, we project the
test data to . 94 (784) ๐ฟ-dimensional data space ๐(โซ ๐ฟ)-dimensional space -
Anomaly detection by Kernel PCA [2] 95 (784) ๐ฟ-dimensional data
space Next, we project the test data to . ๐(โซ ๐ฟ)-dimensional space -
Anomaly detection by Kernel PCA [2] ๏ผHyper parameter (784) ๐ฟ-dimensional
data space ๐(โซ ๐ฟ)-dimensional space If , is predicted to be an anomalous sample. -
97 Summary: Kernel CLAFIC and its various applications Kernel CLAFIC
The data is linearly separated after projection to a higher dimensional space. Application 2 : Anomaly detection Back to data space with the inverse mapping . Anomaly detection by the distance to subspace. Application 1 : Denoising Data Space Feature space -
Grassmannian Learning span ๐1 ๐ด, โฆ , ๐๐ ๐ด span
๐1 ๐ต, โฆ , ๐๐ ๐ต span ๐1 ๐ถ, โฆ , ๐๐ ๐ถ span ๐1 , โฆ , ๐๐ Classify subspaces by distance between subspaces Face images from Yale Face Database http://cvc.cs.yale.edu/cvc/projects/yalefaces/yalefaces.html ๐๐ด ๐๐ต ๐๐ถ ๐ ๐๐ด , ๐๐ต = 1 2 ||๐๐ด ๐๐ด โค โ ๐๐ต ๐๐ต โค||๐น Grassmannian Kernel method Useful when the number of data used for inference is not static e.g., Classification to estimate labels for each multiple facial image ๐ ๐๐ด , ๐๐ต = 1 โ ฯ ๐ cos2๐๐ Projection Metric Binet-Cauchy Metric = ฯ ๐ sin2๐๐ [17] Hamm, Jihun, and Daniel D. Lee. "Grassmann discriminant analysis: a unifying view on subspace-based learning." ICML. 2008. ๐ ๐๐ด , ๐๐ต = det ๐๐ด โค๐๐ต 2 ๐ ๐๐ด , ๐๐ต = ||๐๐ด ๐๐ต โค||๐น Projection kernel Binet-Cauchy kernel ๐๐ด , ๐๐ต , ๐๐ถ โถ Training data Each point is a linear subspace of โ๐ where N is the size of each image Principal angles obtained by SVD on ๐๐ด โค ๐๐ต -
99 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
Matrix factorization with non-negative constraints โช SVD includes negative values
in the representation โช Non-negativity improves interpretability are orthogonal. SVD imposes that are non-negative. NMF imposes that 100 -
Example of non-negative matrix factorization [3] Lee, Daniel D., and
H. Sebastian Seung. "Learning the parts of objects by non-negative matrix factorization." Nature 401.6755 (1999): 788-791. โฆ ๏ผ hyperparameter 101 1 2 3 2429 19 19 in this experiment, ๐ = 49. -
Example of non-negative matrix factorization [3] Lee, Daniel D., and
H. Sebastian Seung. "Learning the parts of objects by non-negative matrix factorization." Nature 401.6755 (1999): 788-791. โฆ ๏ผ hyperparameter 102 1 2 3 2429 19 19 in this experiment, ๐ = 49. ๐ = 19 โ 19, ๐ = 2429 -
The base is the facial parts such as eyes, mouth,
and nose. The face is reconstructed by the addition of the parts. PCA and NMF [3] Lee, Daniel D., and H. Sebastian Seung. "Learning the parts of objects by non-negative matrix factorization." Nature 401.6755 (1999): 788-791. (Positive values are drawn in black, negative values in red) Each basis is face-like. The face is reconstructed by adding up the faces. 103 Representation by NMF Representation by SVD(PCA) -
The base is the facial parts such as eyes, mouth,
and nose. The face is reconstructed by the addition of the parts. PCA and NMF [3] Lee, Daniel D., and H. Sebastian Seung. "Learning the parts of objects by non-negative matrix factorization." Nature 401.6755 (1999): 788-791. (Positive values are drawn in black, negative values in red) Each basis is face-like. The face is reconstructed by adding up the faces. 104 Representation by NMF Representation by SVD(PCA) -
Challenges of NMF Finding the best is NP-hard problem. โป
in terms of minimizing Frobenius error. Gradient based optimization of nonconvex functions. (Approximated solution depends on initial values) Hyperparameter needs to be tuned Convex Function Non-Convex Function NMF for matrix is non-convex. The error ๏ผHyper-parameter 105 -
Nonnegative multiple matrix factorization[6] 111 โช Extract patterns from playback
history for a music recommendation system User Singer User Tag ๏ผ Who listened to which singer? ๏ผ Tags for artists (Pop, rock, Jazz...) ๏ผ Friendship between users. [6] Takeuchi, Koh, et al. "Non-negative multiple matrix factorization." Twenty-third international joint conference on artificial intelligence. 2013. If user i and user j are friends, then ๏ผ KL divergence ใปPrevents over-training, ใปRobust to outliers, Weights of auxiliary information -
Nonnegative multiple matrix factorization[6] 112 โช Extract patterns from playback
history for a music recommendation system [6] Takeuchi, Koh, et al. "Non-negative multiple matrix factorization." Twenty-third international joint conference on artificial intelligence. 2013. Patterns - between users and singers - between users and genres are simultaneously extracted. -
113 Summary: Non-negative matrix factorization โช Non-negativity improves interpretability โช
Many task-specific NMFs have been developed. โช The best solution cannot be obtained. The best decomposition is NP-hard problem โป in terms of minimizing Frobenius error. Gradient based optimization of nonconvex functions (Approximated solution depends on initial values) PCA NMF Group NMF[5] NMMF[6] [5] Lee, Hyekyoung, and Seungjin Choi. "Group nonnegative matrix factorization for EEG classification." Artificial Intelligence and Statistics. PMLR, 2009. [6] Takeuchi, Koh, et al. "Non-negative multiple matrix factorization." Twenty-third international joint conference on artificial intelligence. 2013. -
114 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
NMF with missing values โช Data often includes missing values
The approach of simply replacing missing values with averages or zeros doesn't work well. Estimates missing values using the assumption that the data have a low-rank structure. ๏ผMissing value Only one value is missing for simplicity. In practice, many missing values are possible. 118 -
๏ผMissing value NMF with missing values The space where each
point is a matrix ใปThe dimension of the subspace is the number of missing value. ใปAssuming A is low rank structure + noise Low-rank matrix completion, EM-WNMF[4] Only one value is missing for simplicity. In practice, many missing values are possible. [4] Zhang, Sheng, et al. "Learning from incomplete ratings using non-negative matrix factorization." Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. -
NMF with missing values Low-rank matrix completion, EM-WNMF[4] [4] Zhang,
Sheng, et al. "Learning from incomplete ratings using non-negative matrix factorization." Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. ๏ผHyper-parameter Rank- matrices The space where each point is a matrix Only one value is missing for simplicity. In practice, many missing values are possible. ๏ผMissing value -
NMF with missing values Low-rank matrix completion, EM-WNMF[4] Initialize missing
values and obtain . [4] Zhang, Sheng, et al. "Learning from incomplete ratings using non-negative matrix factorization." Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. ๏ผHyper-parameter Rank- matrices The space where each point is a matrix Only one value is missing for simplicity. In practice, many missing values are possible. ๏ผMissing value -
NMF with missing values Low-rank matrix completion, EM-WNMF[4] M step
[4] Zhang, Sheng, et al. "Learning from incomplete ratings using non-negative matrix factorization." Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. ๏ผHyper-parameter Rank- matrices The space where each point is a matrix Only one value is missing for simplicity. In practice, many missing values are possible. ๏ผMissing value Do NMF on to obtain rank- matrix . Initialize missing values and obtain . -
NMF with missing values Low-rank matrix completion, EM-WNMF[4] M step
E step Overwrite observations to obtain . ๏ผObserved indices [4] Zhang, Sheng, et al. "Learning from incomplete ratings using non-negative matrix factorization." Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. ๏ผHyper-parameter Rank- matrices The space where each point is a matrix Only one value is missing for simplicity. In practice, many missing values are possible. ๏ผMissing value Do NMF on to obtain rank- matrix . Initialize missing values and obtain . -
NMF with missing values [4] Zhang, Sheng, et al. "Learning
from incomplete ratings using non-negative matrix factorization." Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. Low-rank matrix completion, EM-WNMF[4] M step E step Repeat ๏ผHyper-parameter Rank- matrices The space where each point is a matrix Only one value is missing for simplicity. In practice, many missing values are possible. ๏ผObserved indices ๏ผMissing value Overwrite observations to obtain . Do NMF on to obtain rank- matrix . Initialize missing values and obtain . -
Issues in EM-WNMF Rank needs to be chosen appropriately. Algorithm
has initial value dependence๏ผ Slow convergence. [4] Zhang, Sheng, et al. "Learning from incomplete ratings using non-negative matrix factorization." Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. The space where each point is a matrix ๏ผHyper-parameter Rank- matrices Low-rank matrix completion, EM-WNMF[4] -
Further topics of matrix factorization ใป Probabilistic Principal Component Analysis
128 1ร1 = 1 1๏ผ1 = 1 Decomposition under the algebra with [18] Hashemi, Soheil, Hokchhay Tann, and Sherief Reda. "BLASYS: Approximate logic synthesis using Boolean matrix factorization." Proceedings of the 55th Annual Design Automation Conference. 2018. Confidence intervals can be obtained. Each element of the matrix is sampled from a probability distribution. We assume a prior distribution. Input Output ใป Binary Matrix Factorization ๏ผBoolean matrix factorization ใปAutoencoder and Principal Component Analysis The error function of a linear autoencoder with parameter sharing is equivalent to PCA. The activation is given as f(x) = x. The width of the middle layer corresponds to the rank. Matrix rank ๐ ๐โค often used in recommendation engine -
Further topics of matrix factorization ใปDeep matrix factorization [19] Fan,
Jicong. "Multi-mode deep matrix and tensor factorization." ICLR, 2021. Activation function ใป Double-descent phenomena in NMF 129 โ ๐ โ โ๐ร๐ ๐ โ โ๐ร๐ ๐ โ โ๐ร๐ [20] Kawakami, Y., et.al.,โInvestigating Overparameterization for Non-Negative Matrix Factorization in Collaborative Filteringโ RecSys 2021, Late-Breaking Results track, 2021. โ Larger rank ๐ Over fitting -
130 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
Various data are stored in computers as tensors. 131 NASA,
https://sdo.gsfc.nasa.gov/data/ Microarray data RGB Image Hyperspectral Image EEG Data = [14] M.Mรธrup, Data Mining and Knowledge Discovery 2011 [16] A.Cichocki, et al. Nonnegative Matrix and Tensor Factorizations 2009 [16] A.Cichocki, et al. Nonnegative Matrix and Tensor Factorizations 2009 Video Time series data, Signals [16] A.Cichocki, et al. Nonnegative Matrix and Tensor Factorizations 2009 [15] Kosmas Dimitropoulos, et al. Transactions on circuits and systems for video technology 2018 -
Tensors in modern machine learning 132 Relational Learning A B
C E D F G ๏ผ [7] e.g., Graph link prediction by RESCAL Model Express by tensors [8] Deep Learning e.g., Lightweighting Neural Networks with Tensor Decomposition [9] [7] Nickel, Maximilian, Volker Tresp, and Hans-Peter Kriegel. โA three-way model for collective learning on multi-relational data.โ ICML2011 [8] T. Bezdan, N. Baฤanin Dลพakula, International Scientific Conference on Information Technology and Data Related Research, 2019 [9] Y. Liu et al., Tensor Computation for data analysis, 2022 -
Tensor Hierarchy: Vectors of a Tensor are also Tensors Numbers
Vectors [First-order tensors] Matrices [Second-order tensors] ๐ ๐ = ๐1 ๐2 โฎ ๐๐ ๐ = ๐11 โฏ ๐1๐ โฎ โฑ โฎ ๐๐1 โฏ ๐๐๐ Third-order tensors โฏ ๐ฏ= Fourth-order tensors ๐= โฏ โฏ ๐ฏ 1 ๐ฏ 2 ๐ฏ ๐ 133 -
Density estimation, pattern extraction, data mining, denoising, data compression, anomaly
detectionโฆ Extracting features from tensors. 134 Who Shop โ = เดค ๐ซ minmize ๐ซ โ เดค ๐ซ ๐น + โฏ + ๐ซ We want to extract pattern or feature in tensor formatted data โช Tensor decomposition extracts features from data. mode-๏ผ mode-๏ผ -
Difficulties in tensor factorization โช We need to decide both
of a structure and a rank. CP decomp. โ = ๐ซ เดค ๐ซ โ Tucker decomp. Decomp. with tensor networks + โฏ + minmize ๐ซ โ เดค ๐ซ ๐น Tensor Train decomposion Tensor ring decomposion ๐ซ Tensor networks Each node is a tensor, Each edge is a mode [11] Wang, Wenqi, et al. CVPR. 2018. [12] Zheng, Yu-Bang, et al. AAAI 2021. https://tensornetwork.org [13] A. Cichocki, et al., Tensor Networks for Dimensionality Reduction and Large-scale Optimization, 2016 -
Difficulties in tensor factorization 136 โช We need to decide
both of a structure and a rank. CP decomp. โ = ๐ซ เดค ๐ซ โช Optimization is difficult. Tensor decomposition is often ill-posed or NP-hard. ใป The best rank-1 CP-decomp. for minimizing Frobenius norm is NP-hard. โ Tucker decomp. Decomp. with tensor networks + โฏ + A convex, stable and intuitive designable tensor decomposition is desired. minmize ๐ซ โ เดค ๐ซ ๐น Non-convex ๐ซ โ เดค ๐ซ ๐น Solution often might be indeterminate. The objective function is typically non-convex. ใปInitial values dependency No guarantee to be the best solution. Tensor Train decomposion Tensor ring decomposion ๐ซ -
Many-body approximation for non-negative tensors[10] 137 Natural parameter of exponential
distribution family. Energy function -
Many-body approximation for non-negative tensors[10] 138 Natural parameter of exponential
distribution family. Energy function -
Many-body approximation for non-negative tensors[10] 139 Control relation between mode-k
and mode-l. Control relation among mode-j, -k and -l. Natural parameter of exponential distribution family. Energy function -
Many-body approximation for non-negative tensors[10] 140 One-body approx. Rank-1 approximation
๏ผmean-field approximation๏ผ -
Many-body approximation for non-negative tensors[10] 141 One-body approx. Rank-1 approximation
๏ผmean-field approximation๏ผ Two-body approx. Control relation between mode-k and mode-l. Larger Capability Two-body Interaction -
Many-body approximation for non-negative tensors[10] 142 One-body approx. Rank-1 approximation
๏ผmean-field approximation๏ผ Two-body approx. Two-body Interaction Three-body approx. Larger Capability The global optimal solution minimizing KL divergence from can be obtained by a convex optimization. Intuitive modeling focusing on interactions between modes Control relation among mode-j, -k and -l. Control relation between mode-k and mode-l. Three-body Interaction -
We regard a normalized tensor as a discrete joint probability
distribution whose sample space is an index set Coordinates transformation Theoretical idea behind many-body approx. 143 Index is discrete random variable ๐ฝ- Representation Representation with natural parameters of exponential family Geometry of ๐ฝ-space Low-rank space ๏ผNot flat๏ผ Flat subspace Difficult to optimize We construct flat subspace by focusing interaction among tensor modes Describing tensor factorization in ๐ฝ-coordinate system makes it convex problem We use information geometry to formulate factorization as convex problem -
Example tensor reconstruction by many-body approx. Larger capability Reconstruction for
40ร40ร3ร10 tensor. (width, height, colors, # images) Color depends on image index Shape of each image Color is uniform within each image. Intuitive model designable that captures the relationship between modes Color depends on pixel Three-body Approx. 152 -
Color image is decomposed into shape ร color ร โ
= Shape of each image Color of each image -
Data completion by many-body approx. and the em-algorithm m-step ๐
โ low_rank_approx(๐) e-step ๐๐ โ ๐๐ ๐ : observed indices Low-rank Tensor Completion ๐-projection ๐-projection Not flat. It causes non-uniquness of projection. Which structure is better for decomposition? How to chose rank? Low-rank space 155 -
Data completion by many-body approx. and the em-algorithm m-step ๐
โ low_rank_approx(๐) e-step ๐๐ โ ๐๐ ๐ : observed indices Low-rank Tensor Completion ๐-projection Low-body many_body_approx Low-body space is flat. It ensures uniquness of the projection Intuitive modeling is possible! ๐-projection 156 -
Data completion by many-body approx. and the em-algorithm Missing area
GT Prediction Interaction above correlated modes Reconstructing traffic speed data of 28ร24ร12ร4 tensor with missing values. (days, hours, min, lanes) 157 -
Data completion by many-body approx. and the em-algorithm Missing area
GT Prediction Interaction above correlated modes Interaction above non-correlated modes Fit score: 0.82 Reconstructing traffic speed data of 28ร24ร12ร4 tensor with missing values. (days, hours, min, lanes) 158 -
159 Summary: Many-body approximation for tensors https://arxiv.org/abs/2209.15338 ใปMore intuitive design
than rank tuning One-body Approx. Three-body Approx. Two-body Approx. Many-body Approximation Bias (magnetic field) Weight (electron-electron interaction) ใปConvex optimization always provide unique solution -
160 Report assignments 1. Prove the Eckart-Young or Eckart-Young-Mirsky Theorem.
2. There are many algorithms for Non-negative Matrix Factorization, e.g., HALS-NMF, MU-NMF, etc. Choose one of them and derive the algorithm. You do not have to show the convergence guarantee. There are four assignments below. Choose one of them and write your report. Please indicate which assignment you have chosen. The format is flexible but should be less than 2 sheets of A4 size paper. Handwriting is also acceptable. Note: There are many variation of NMF, such as: - NMF optimizing Frobenius norm - NMF optimizing KL divergence - NMF optimizing Frobenius norm with regularization term. Please indicate which kind of NMF you are discussing. -
161 Report assignments 3. Visit Google Scholar (https://scholar.google.com/) and search
for a paper related to SVD, NMF, or tensor factorization. Summarize the motivation, method, and novelty of the paper. Note: Please clearly indicate the paper title you chose. Example papers: - Lee, Daniel D., and H. Sebastian Seung. "Learning the parts of objects by non-negative matrix factorization." nature 401.6755 (1999): 788-791. - Takeuchi, Koh, et al. "Non-negative multiple matrix factorization." Twenty-third international joint conference on artificial intelligence. 2013. - Lee, Hyekyoung, and Seungjin Choi. "Group nonnegative matrix factorization for EEG classification." Artificial Intelligence and Statistics. PMLR, 2009. - Ding, Chris, Xiaofeng He, and Horst D. Simon. "On the equivalence of nonnegative matrix factorization and spectral clustering." Proceedings of the 2005 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2005. - Lee, Daniel, and H. Sebastian Seung. "Algorithms for non-negative matrix factorization." Advances in neural information processing systems 13 (2000). - Zhang, Jun, Yong Yan, and Martin Lades. "Face recognition: eigenface, elastic matching, and neural nets." Proceedings of the IEEE 85.9 (1997): 1423-1435. Recommended keywords: - Non-negative matrix factorization, SVD, Tensor decomposition, Eigen face, weighted NMF, low-rank completion -
162 Report assignments 4. Follow the steps below using Python,
Matlab, R, C/C++, Fortran, or Julia: (1) Convert a grayscale image into a two-dimensional array (matrix). (2) Perform the rank-r approximation on it using SVD. (3) Plot a figure with rank on the horizontal axis and reconstruction error on the vertical axis. Observe how the reconstructed image changes as the rank is varied. (4) Plot a figure of the singular value distribution obtained by SVD for the image. The vertical axis of the plot is the nth largest singular value, and the horizontal axis is n. Rank Reconstruction Error n n-th singular value Note: Please paste a part of the source code you have written into the report. You do not have to paste all source code. -
163 Overview โช Introduction: Why do we decompose data? โช
A quick review of matrix rank โช Singular value decomposition (SVD) and low-rank approximation โช Kernel subspace method and its applications (denoising, anomaly detection) โช Non-negative matrix factorization โช Tensor low-rank decomposition and many-body approximation -
For further study ใฐใฉ ใ ใฃ ใซ ใซใฆใผใถใผใคใณใฟ ใผใ ใง
ใคใน ่ชๅ็ใซ็ๆใ ใใ่ชฌๆ ใใญในใใๅซใพใใฆใใ็ปๅ ่ชๅ็ใซ็ๆใ ใใ่ชฌๆ โช Textbooks for Matrix and Tensor Decomposition A series lecture by Dr. Steve Brunton ใปSpeeding up SVD ใปSVD for linear regression ใปSVD for face recognition ใปHow to chose ranks โช Tensor libraries ๆ่จ , ใก ใผใฟ ใผ , ใใผใซ , ่จๅท ใๅซใพใใฆใใ็ปๅ ่ชๅ็ใซ็ๆใ ใใ่ชฌๆ ใญใด ่ชๅ็ใซ็ๆใ ใใ่ชฌๆ ็ฎฑใฒใๅณ ใๅซใพใใฆใใ็ปๅ ่ชๅ็ใซ็ๆใ ใใ่ชฌๆ [iTensor] ใซ ใฌใณใใผ ไธญ็จๅบฆใฎ็ฒพๅบฆใง่ชๅ็ใซ็ๆใ ใใ่ชฌๆ โฆ 166 -
167 References [1] Mika, Sebastian, et al. "Kernel PCA and
de-noising in feature spaces." Advances in neural information processing systems 11 (1998). [2] Hoffmann, Heiko. "Kernel PCA for novelty detection." Pattern recognition 40.3 (2007): 863-874. [3] Lee, Daniel D., and H. Sebastian Seung. "Learning the parts of objects by non-negative matrix factorization." Nature 401.6755 (1999): 788-791. [4] Zhang, Sheng, et al. "Learning from incomplete ratings using non-negative matrix factorization.โ Proceedings of the 2006 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2006. [5] Lee, Hyekyoung, and Seungjin Choi. "Group nonnegative matrix factorization for EEG classification.โ Artificial Intelligence and Statistics. PMLR, 2009. [6] Takeuchi Koh, et al. "Non-negative multiple matrix factorization." Twenty-third international joint conference on artificial intelligence. 2013. [7] Nickel, Maximilian, Volker Tresp, and Hans-Peter Kriegel. โA three-way model for collective learning on multi-relational data.โ ICML2011 [8] T. Bezdan, N. Baฤanin Dลพakula, International Scientific Conference on Information Technology and Data Related Research, 2019 [9] Y. Liu et al., "Tensor Computation for data analysis", 2022 [10] Ghalamkari Kazu, Mahito Sugiyama, and Yoshinobu Kawahara. "Many-body approximation for non-negative tensors.โ Advances in Neural Information Processing Systems 36 (2024). [11] Wang, Wenqi, et al. "Wide compression: Tensor ring nets." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018. [12] Zheng, Yu-Bang, et al. "Fully-connected tensor network decomposition and its application to higher-order tensor completion." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 12. 2021. [13] Cichocki, Andrzej, et al. "Tensor networks for dimensionality reduction and large-scale optimization: Part 1 low-rank tensor decompositions." Foundations and Trendsยฎ in Machine Learning 9.4-5 (2016): 249-429. -
168 References [14] Mรธrup, Morten. "Applications of tensor (multiway array)
factorizations and decompositions in data mining." Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 1.1 (2011): 24-40. [15] Dimitropoulos, Kosmas, et al. "Classification of multidimensional time-evolving data using histograms of grassmannian points." IEEE Transactions on Circuits and Systems for Video Technology 28.4 (2016): 892-905. [16] Andrzej Cichocki, Rafal Zdunek, Anh Huy Phan, and Shun-ichi Amari. Non-negative matrix and tensor factorizations: applications to exploratory multi-way data analysis and blind source separation. John Wiley & Sons, 2009. [17] Hamm, Jihun, and Daniel D. Lee. "Grassmann discriminant analysis: a unifying view on subspace-based learning." ICML. 2008. [18] Hashemi, Soheil, Hokchhay Tann, and Sherief Reda. โBLASYS: Approximate logic synthesis using Boolean matrix factorization.โ Proceedings of the 55th Annual Design Automation Conference. 2018. [19] Fan, Jicong. "Multi-mode deep matrix and tensor factorization." ICLR, 2021. [20] Kawakami, Y., et.al.,โInvestigating Overparameterization for Non-Negative Matrix Factorization in Collaborative Filteringโ RecSys 2021, Late-Breaking Results track, 2021. Acknowledgements I would like to express my gratitude to Dr. Profir-Petru Pรขrศachi from the National Institute of Informatics for his valuable comments on the structure and content of this lecture slides. Used datasets MNIST https://yann.lecun.com/exdb/mnist/ COIL100 https://www1.cs.columbia.edu/CAVE/software/softlib/coil-100.php IRIS https://archive.ics.uci.edu/dataset/53/iris Yale Face Database http://cvc.cs.yale.edu/cvc/projects/yalefaces/yalefaces.html