A Tutorial on the Spectral Theory of Markov Chains
- URL: http://arxiv.org/abs/2207.02296v1
- Date: Tue, 5 Jul 2022 20:43:40 GMT
- Title: A Tutorial on the Spectral Theory of Markov Chains
- Authors: Eddie Seabrook and Laurenz Wiskott
- Abstract summary: This tutorial provides an in-depth introduction to Markov chains.
We utilize tools from linear algebra and graph theory to describe the transition matrices of different types of Markov chains.
The results presented are relevant to a number of methods in machine learning and data mining.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Markov chains are a class of probabilistic models that have achieved
widespread application in the quantitative sciences. This is in part due to
their versatility, but is compounded by the ease with which they can be probed
analytically. This tutorial provides an in-depth introduction to Markov chains,
and explores their connection to graphs and random walks. We utilize tools from
linear algebra and graph theory to describe the transition matrices of
different types of Markov chains, with a particular focus on exploring
properties of the eigenvalues and eigenvectors corresponding to these matrices.
The results presented are relevant to a number of methods in machine learning
and data mining, which we describe at various stages. Rather than being a novel
academic study in its own right, this text presents a collection of known
results, together with some new concepts. Moreover, the tutorial focuses on
offering intuition to readers rather than formal understanding, and only
assumes basic exposure to concepts from linear algebra and probability theory.
It is therefore accessible to students and researchers from a wide variety of
disciplines.
Related papers
- Introduction to Machine Learning [0.0]
This book introduces the mathematical foundations and techniques that lead to the development and analysis of many of the algorithms that are used in machine learning.
The subject then switches to generative methods, starting with a chapter that presents sampling methods.
The next chapters focus on unsupervised learning methods, for clustering, factor analysis and manifold learning.
arXiv Detail & Related papers (2024-09-04T12:51:41Z) - Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning [49.0767291348921]
Randomized Numerical Linear Algebra (RandNLA) is an area which uses randomness to develop improved algorithms for ubiquitous matrix problems.
This article provides a self-contained overview of RandNLA, in light of these developments.
arXiv Detail & Related papers (2024-06-17T02:30:55Z) - Curvature-informed multi-task learning for graph networks [56.155331323304]
State-of-the-art graph neural networks attempt to predict multiple properties simultaneously.
We investigate a potential explanation for this phenomenon: the curvature of each property's loss surface significantly varies, leading to inefficient learning.
arXiv Detail & Related papers (2022-08-02T18:18:41Z) - Sign and Basis Invariant Networks for Spectral Graph Representation
Learning [75.18802152811539]
We introduce SignNet and BasisNet -- new neural architectures that are invariant to all requisite symmetries and hence process collections of eigenspaces in a principled manner.
Our networks are theoretically strong for graph representation learning -- they can approximate any spectral graph convolution.
Experiments show the strength of our networks for learning spectral graph filters and learning graph positional encodings.
arXiv Detail & Related papers (2022-02-25T23:11:59Z) - Masked prediction tasks: a parameter identifiability view [49.533046139235466]
We focus on the widely used self-supervised learning method of predicting masked tokens.
We show that there is a rich landscape of possibilities, out of which some prediction tasks yield identifiability, while others do not.
arXiv Detail & Related papers (2022-02-18T17:09:32Z) - Stochastic and Quantum Dynamics of Repulsive Particles: from Random
Matrix Theory to Trapped Fermions [0.0]
This thesis focuses on the study of three kinds of systems which display repulsive interactions: eigenvalues of random matrices, non-crossing random walks and trapped fermions.
We present a combined analysis of these systems, employing tools of random matrix theory and calculus as well as tools of quantum mechanics.
arXiv Detail & Related papers (2021-11-10T15:23:06Z) - Neo: Generalizing Confusion Matrix Visualization to Hierarchical and
Multi-Output Labels [25.336125962529692]
The confusion matrix is a ubiquitous visualization for helping people evaluate machine learning models.
We find that conventional confusion matrices do not support more complex data-structures, such as hierarchical and multi-output labels.
We develop Neo, a visual analytics system that enables practitioners to flexibly author and interact with hierarchical and multi-output confusion matrices.
arXiv Detail & Related papers (2021-10-24T21:55:20Z) - Learning with Density Matrices and Random Features [44.98964870180375]
A density matrix describes the statistical state of a quantum system.
It is a powerful formalism to represent both the quantum and classical uncertainty of quantum systems.
This paper explores how density matrices can be used as a building block for machine learning models.
arXiv Detail & Related papers (2021-02-08T17:54:59Z) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
We consider the general problem of learning about a matrix through vector-matrix-vector queries.
These queries provide the value of $boldsymbolumathrmTboldsymbolMboldsymbolv$ over a fixed field.
We provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs.
arXiv Detail & Related papers (2020-06-24T19:33:49Z) - Spectral Learning on Matrices and Tensors [74.88243719463053]
We show that tensor decomposition can pick up latent effects that are missed by matrix methods.
We also outline computational techniques to design efficient tensor decomposition methods.
arXiv Detail & Related papers (2020-04-16T22:53:00Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.