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



This is the webpage of the 2019 edition of the course, webpage for 2020 course is here.

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 9 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 [lecture 10 notes] [latex sources (overleaf)]

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 [lecture 11 notes] [latex sources (overleaf)]

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 [lecture 12 notes] [latex sources (overleaf)]

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 [lecture 13 notes] [latex sources (overleaf)]

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:

February 26th, 28th [lecture 14-15 notes] [latex sources (overleaf)]

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.