Lecture

Spectral Clustering and Laplacian Eigenmaps

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

MICRO-455: Machine learning I

Real-world engineering applications must cope with a large dataset of dynamic variables, which cannot be well approximated by classical or deterministic models. This course gives an overview of methods from Machine Learning for the analysis of non-linear, highly noisy and multi dimensional data

Description

This lecture covers advanced machine learning techniques focusing on spectral clustering and Laplacian eigenmaps. Spectral methods decompose the Graph Laplacian matrix to identify non-linear manifolds in data. By constructing a similarity graph and measuring distances, spectral clustering can determine the number of clusters in a dataset. The eigenvalue decomposition of the Laplacian matrix plays a crucial role in identifying connected components and clustering. Laplacian eigenmaps and Isomap are discussed as non-linear embedding methods, highlighting the importance of geodesic distances in capturing data relationships. The lecture concludes with a summary of spectral methods, emphasizing the power of spectral clustering and Laplacian embeddings when the kernel is well chosen.

Instructor

Aude Billard

Expertise RoboticsMachine LearningArtificial IntelligenceHuman-Robot InteractionMechatronicsDynamical Systems ControlComputational Neuroscience Aude Billard is full professor and head of the LASA laboratory at the School of Engineering at the Swiss Institute of Technology Lausanne (EPFL), and the Director of the Swiss Innovation Booster on Robotics. Dr. Billard acts as the President of the IEEE Robotics and Automation Society (RAS), after serving in several roles in the administrative and executive committe

Official source

Ontological neighbourhood

Mathematics

Algebra: Linear algebra

Related concepts (32)

Nonlinear dimensionality reduction

Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping (either from the high-dimensional space to the low-dimensional embedding or vice versa) itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.

Dimensionality reduction

Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meaningful properties of the original data, ideally close to its intrinsic dimension. Working in high-dimensional spaces can be undesirable for many reasons; raw data are often sparse as a consequence of the curse of dimensionality, and analyzing the data is usually computationally intractable (hard to control or deal with).

Kernel principal component analysis

In the field of multivariate statistics, kernel principal component analysis (kernel PCA) is an extension of principal component analysis (PCA) using techniques of kernel methods. Using a kernel, the originally linear operations of PCA are performed in a reproducing kernel Hilbert space. Recall that conventional PCA operates on zero-centered data; that is, where is one of the multivariate observations.

Eigendecomposition of a matrix

In linear algebra, eigendecomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way. When the matrix being factorized is a normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the spectral theorem. Eigenvalue, eigenvector and eigenspace A (nonzero) vector v of dimension N is an eigenvector of a square N × N matrix A if it satisfies a linear equation of the form for some scalar λ.

Singular value decomposition

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any matrix. It is related to the polar decomposition. Specifically, the singular value decomposition of an complex matrix M is a factorization of the form where U is an complex unitary matrix, is an rectangular diagonal matrix with non-negative real numbers on the diagonal, V is an complex unitary matrix, and is the conjugate transpose of V.

Related lectures (64)

Spectral Clustering: Theory and Applications

Explores spectral clustering theory, eigenvalue decomposition, Laplacian matrix, and practical applications in identifying clusters.

Clustering: K-means & LDA

Covers clustering using K-means and LDA, PCA, K-means properties, Fisher LDA, and spectral clustering.

Clustering: Unsupervised Learning

Explores dimensionality reduction, clustering algorithms, and the state of machine learning.

Unsupervised Learning: Clustering & Dimensionality Reduction

Introduces unsupervised learning through clustering with K-means and dimensionality reduction using PCA, along with practical examples.

Dimensionality Reduction: PCA & LDA