Embedding as a Tool for Algorithm Design

Explore embedding algorithms as a powerful tool for algorithm design in this lecture from the Simons Institute's Computational Challenges in Machine Learning series. Delve into prediction for structured data, combinatorial optimizations over graphs, and dynamic processes over networks. Learn about representing structures as latent variable models, using posterior distributions as features, and applying mean field algorithms for information aggregation. Discover the concept of embedding, its applications in learning, and how to embed belief propagation. Gain insights into new tools for algorithm design, including embedding mean field and directly parameterizing nonlinear mapping. Examine the process of unrolling time-varying dependency structures and building generative models through embedding algorithms. Finally, investigate how greedy algorithms can be viewed as Markov decision processes in combinatorial optimization over graphs.

Intro
Embedding algorithms
Prediction for structured data
Big dataset, explosive feature space
Combinatorial optimizations over graphs
Key observation & fundamental question
Represent structure as latent variable model (LVM)
Posterior distribution as features
Mean field algorithm aggregates information
What's embedding?
Learning via embedding
Embedding mean field
Directly parameterize nonlinear mapping
Embed belief propagation
New tools for algorithm design
Motivation 2: Dynamic processes over networks
Unroll: time-varying dependency structure
Embedding algorithm for building generative model
Scenario 3: Combinatorial optimization over graph
Greedy algorithm as Markov decision process