IFT 6760A - Winter 2019
Matrix and tensor factorization techniques for machine learning



[new] Notes for lecture 9 on tensors and CP decomposition are available.
[new] Notes for lecture 7-8 on spectral learning of weighted automata are available.
[new] ~15 papers added to the class bibliography (marked with the [new] tag).

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)

Schedule

January 8

Class introduction. [slides] [quiz]

January 10 [lecture 1 notes] [latex sources (overleaf)]

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:

January 15 [lecture 2 notes] [latex sources (overleaf)]

Linear algebra refresher (cont'd).
  • Orthogonality, projections
  • Singular value decomposition
Reading suggestions:

January 17 [lecture 3 notes] [latex sources (overleaf)]

Linear algebra refresher (cont'd).
  • QR decomposition
  • Basics about matrix inverse and determinant
  • Moore-Penrose pseudo-inverse
  • Eigenvalues / eigenvectors definition
Reading suggestions:

January 22 [lecture 4 notes] [latex sources (overleaf)]

Linear algebra refresher (cont'd).
  • Diagonalizability, spectral theorem, Schur decomposition, Jordan canonical form
  • Proof of the SVD
Reading suggestions:

January 24 [lecture 5 notes] [latex sources (overleaf)]

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:

January 29 [lecture 6 notes] [latex sources (overleaf)]

Dimensionality reduction
  • Principal component analysis (PCA)
  • Canonical correlation analysis (CCA)
  • Locally linear embedding (LLE)
Reading suggestions:

January 31 [lecture 7-8 notes] [latex sources (overleaf)]

Spectral learning of HMMs and related models

Reading suggestions:

February 5th

Spectral learning of HMMs and related models (cont'd)

February 7th [lecture notes] [latex sources (overleaf)]

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:

February 12th

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:

February 14th

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:

February 19th

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:

February 21st

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:

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.