IFT 6760A - Winter 2019
Matrix and tensor factorization techniques for machine learning
[new] Important dates: Project poster session will be on Tuesday April 23rd from 12:30pm to 3:30pm ||| Deadline for report is on May 3rd .
[new] Notes for lecture 10 on CP and Tucker decomposition and for lecture 13 on learning latent variable models with tensor methods are available.
Description
The goal of this course is to present an overview of linear and multilinear algebra techniques for designing/analyzing ML algorithms and models, and to engage students with new research in the area.
- Fundamental notions of linear and multilinear algebra.
- Old and new ML methods leveraging matrix and tensor decomposition: PCA/CCA,
collaborative filtering, spectral graph clustering, spectral methods for HMM, K-FAC,
spectral normalization,
tensor method of moments, NN/MRF compression, tensor regression/completion, etc.
- Open problems.
Class Info
When:
Tuesdays 12:30-2:30PM and Thursdays 11:30-1:30PM
Where: Mila auditorium, 6650 St-Urbain street
Instructor: Guillaume Rabusseau, Office: 3151.André-Aisenstadt @ UdeM / D.15 @ Mila.
Office hours: Tuesdays after class
Evaluation
Class project (50%) + Paper presentation (30%) + Scribing (10%) + Class participation (10%)
The latex template for scribing can be found in this overleaf project.
Tentative list of topics (to be updated as we go along)
- Linear algebra fundamentals
- Vector spaces, linear maps, matrices, rank, change of basis, Hilbert spaces (orthogonality), etc.
- Matrix decomposition: eigenvalues/eigenvectors, diagonalizability (Jordan canonical form), Gram-Schmidt algorithm, QR decomposition, singular value decomposition.
- Linear algebra and matrix factorization techniques for ML
- Linear algebra is everywhere: PCA, CCA, LLE, ...
- Spectral graph clustering
- Spectral learning of HMMs, PCFGs and related models
- Collaborative filtering, matrix completion and low rank matrix recovery
- Multilinear algebra and tensor factorization techniques for ML: Tensors are the new matrices! (quoting David Steurer)
- Presentation of several tensor decomposition formats: CanDecomp/ParaFac (CP), Tucker, Tensor Train (TT), etc.
- Tensor networks: a unifying tool
- Some tensor decomposition algorithms: alternating least squares, SVD based algorithms (HOSVD, TT-SVD), DMRG like algorithms, etc.
- Tensor method of moments: consistent estimators from observable tensors
- Algorithms for CP decomposition of symmetric tensors: Jenrich's algorithm, tensor power method, sum of squares hierarchy...
- Multilinear extensions: tensor completion, tensor recovery, tensor regression, ...
- Compressing ML models (e.g. NN, MRF) with tensor factorization
Schedule
January 8
Linear algebra refresher.
- Vector space, subspaces, span, linear independence, basis, orthogonality, etc.
- The four fundamental spaces of a matrix, matrix rank, rank nullity theorem
Reading suggestions:
Linear algebra refresher (cont'd).
- Orthogonality, projections
- Singular value decomposition
Reading suggestions:
Linear algebra refresher (cont'd).
- QR decomposition
- Basics about matrix inverse and determinant
- Moore-Penrose pseudo-inverse
- Eigenvalues / eigenvectors definition
Reading suggestions:
Linear algebra refresher (cont'd).
- Diagonalizability, spectral theorem, Schur decomposition, Jordan canonical form
- Proof of the SVD
Reading suggestions:
Linear algebra refresher (cont'd).
- Matrix norms
- Low rank approximation (Eckart-Young-Mirsky theorem)
- Variational characterization of eigenvalues (Rayleigh quotient), Min-max theorem
Reading suggestions:
Dimensionality reduction
- Principal component analysis (PCA)
- Canonical correlation analysis (CCA)
- Locally linear embedding (LLE)
Reading suggestions:
Spectral learning of HMMs and related models
Reading suggestions:
February 5th
Spectral learning of HMMs and related models (cont'd)
Introduction to tensor decomposition
- Basic tensor operations, Kronecker product, ...
- Notions of tensor rank
- CP and Tucker decomposition
- Jennrich's algorithm and Alternating Least Squares (ALS) for CP and Tucker decomposition
Reading suggestions:
Tensor networks and SVD based tensor decomposition algorithms
- Introduction to tensor networks
- Tensor Train (TT), Tensor Ring (TR), Hierarchical Tucker (HT) decomposition
- SVD based decompostion algorithms for Tucker and TT
Reading suggestions:
Guest lecture by
Jacob Miller:
- Tensor Train (TT) decomposition
- Parametrization of ML models with the TT format
- DMRG-like algorithms for optimization in TT format
Reading suggestions:
More on the tensor train decomposition and tensor networks
- SVD-based and DMRG-like algorithms for optimization in TT format
- Beyond TT: PEPS, tensor ring, hierarchical Tucker...
Reading suggestions:
Learning latent variable models via tensor decomposition
- Single topic model and mixture of Gaussians
- Method of moments and tensor decomposition
- Power method for matrix and tensor decomposition
Reading suggestions:
Guest lecture by
Ioannis Mitliagkas:
- Johnson–Lindenstrauss lemma
- Random projections and sketching
Reading suggestions:
March 12th
Student presentations:
- Bogdan, Eirk-Olivier and William:
Tensorizing Neural Networks (Novikov et al, 2015)
- Mohamed and Charles: [slides]
Tensor-Train Recurrent Neural Networks for Video Classification (Yang et al., 2017)
March 14th
[slides]
Low-Rank Regression with Tensor Structured Outputs
March 19th
Student presentations:
- Mostafa, Abdulmonhem and Adrien:
Multilinear Independent Components Analysis (Vasilescu and Terzopoulos, 2005)
- Tayssir, Tapopriya and Aayushi: [slides]
Learning relevant features of data with Multi-scale Tensor networks (Stoudenmire, 2018)
- Nicolas and Adam:
Exact Matrix Completion via Convex Optimization (Candès and Recht, 2008)
March 21st
Student presentations:
- Nicolas, Jimmy and Tobi:
Duality of Graphical Models and Tensor Networks (Robeva and Seigal, 2017)
- Alex and Faruk: [slides]
Spectral Normalization for Generative Adversarial Networks (Miyato et al., 2018)
- Tianyu, Koustuv and Bhairav: [slides]
Generalized Tensor Models for Recurrent Neural Networks (Khrulkov 19)
March 26th
- Thomas George (Mila PhD student autditting the class) will talk about his work on Kronecker Factorization and Natural Gradient Descent
Reading suggestions:
March 28th
Student presentations:
- Timothy and Arthur:
Higher-Order Partial Least Squares (HOPLS): A Generalized Multi-Linear Regression Method (Zhao et al., 2013)
- Yann and Adel: [slides]
Spectral clustering from a geometric viewpoint (Berry and Sauer)
- David, Gavin and Junhao:
Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning (Rabusseau et al., 2018)
April 2nd
Student presentations:
- Parviz and Mamhoud:
Learning to Reason with Third-Order Tensor Product (Schlag and Schmidhuber, 2018)
- Harsh Satija (Mila PhD student auditting the class) will introduce predictive state representations and present the paper:
Efficient Learning and Planning with Compressed Predictive States (Hamilton et al., 2014)
April 4th
- Theoretical Analysis of the Expressive Power of Deep Nets using Tensor Decomposition.
Reading suggestions:
April 9th
No class (instructor is travelling)
April 11th
No class (instructor is travelling)
April 23rd, 12:30pm-3:30pm
Poster Presentations of the Class Projects
Resources
Linear Algebra
Tensor Decomposition
Class Bibliography
PCA / CCA / ICA
Spectral Clustering
Spectral Learning
Tensor Decomposition
Tensor Networks
Model Compression
Latent Variable Models
Neural Network Analysis with Tensors
Tensor Completion
Various Applications of Tensor Methods
Misc.
- Neural Word Embedding as Implicit Matrix Factorization (Levi and Goldberg, 2014)
- Understanding Composition of Word Embeddings via Tensor Decomposition (Frandsen and Ge, 2019)
- Incremental Truncated LSTD (Gehring et al., 2016)
- Boosted Sparse and Low-Rank Tensor Regression (He et. al, 2018)
- Learning from Multiway Data: Simple and Efficient Tensor Regression (Yu and Liu, 2016)
- Multi-Dimensional Causal Discovery (Schaechtle et al., 2013)
- Learning to Reason with Third-Order Tensor Product (Schlag and Schmidhuber, 2018)
- Optimizing Neural Networks with Kronecker-factored Approximate Curvature (Martens and Grosse,2015)
- Fast Approximate Natural Gradient Descent in a Kronecker Factored Eigenbasis (George et al., 2018)
- Spectral Normalization for Generative Adversarial Networks (Miyaot et al., 2018)
- Multilinear PageRank (Gleich et al., 2015)
- Multilinear Dynamical Systems for Tensor Time Series