发帖
雷达卡
Discrete Stochastic Processes: Tools for Machine Learning and Data Science
Author(s): Nicolas Privault
Division of Mathematical Sciences Nanyang Technological University Singapore, Singapore
Course description
This course presents selected applications of discrete-time stochastic processes that involve random interactions and algorithms, and revolve around the Markov property. It covers recurrence properties of (excited) random walks, convergence and mixing of Markov chains, distribution modeling using phase-type distributions, applications to search engines and probabilistic automata, and an introduction to the Ising model used in statistical physics. Applications to data science are also considered via hidden Markov models and Markov decision processes. A total of 32 exercises and 17 longer problems are provided with detailed solutions and cover various topics of interest, including statistical learning.
Contents
1 A Summary of Markov Chains
1.1 Markov Property
Transition Matrices
Higher-Order Transition Probabilities
1.2 Hitting Probabilities
Hitting Probabilities
1.3 Mean Hitting and Absorption Times
First Return Times
Hitting Times vs. Return Times
Markov Chains with Rewards
Mean Number of Returns
1.4 Classification of States
Communicating States
Examples: Reducibility and Irreducibility
Recurrent States
Transient States
Examples: Recurrent and Transient States
Positive vs. Null Recurrence
Periodicity and Aperiodicity
Examples: Periodicity and Aperiodicity
1.5 Hitting Times of Random Walks
Mean Hitting Times
Notes
Exercises
2 Phase-Type Distributions
2.1 Negative Binomial Distribution
2.2 Markovian Construction
2.3 Hitting Time Distribution
2.4 Mean Hitting Times
Notes
Exercises
3 Synchronizing Automata
3.1 Pattern Recognition
Markovian Text Generation
First-Order Word Analysis
Second-Order Word Analysis
Independent Samples
Average Recognition Times
Probability Generating Functions
3.2 Winning Streaks
Probability Distribution of T(m)
3.3 Synchronizing Automata
Example
Markovian Text Generator
3.4 Synchronization Times
Mean Synchronization Times
Synchronization Probabilities
Notes
Exercises
4 Random Walks and Recurrence
4.1 Distribution and Hitting Times
One-Dimensional Random Walk
Two-Dimensional Random Walk
Multidimensional Random Walk
Return Times
4.2 Recurrence of Symmetric Random Walks
Recurrence of the One-Dimensional Random Walk
Recurrence of the Two-Dimensional Random Walk
Recurrence of d-Dimensional Random Walks, d3
Recurrence Revisited
4.3 Reflected Random Walk
4.4 Conditioned Random Walk
Conditional Hitting Probabilities
Conditional Mean Hitting Times
Notes
Exercises
5 Cookie-Excited Random Walks
5.1 Hitting Times and Probabilities
Hitting Probabilities
5.2 Recurrence
5.3 Mean Hitting Times
5.4 Count of Cookies Eaten
5.5 Conditional Results
Notes
Exercises
6 Convergence to Equilibrium
6.1 Limiting and Stationary Distributions
Limiting Distributions
Example
Stationary Distributions
Example
6.2 Markov Chain Monte Carlo: MCMC
Generating Random Samples from a Target Distribution
Interpretation
Generating Posterior Samples Using MCMC
Implementation Example
6.3 Transition Bounds and Contractivity
6.4 Distance to Stationarity
6.5 Mixing Times
Coupling
Notes
Exercises
7 The Ising Model
7.1 Construction
Example
7.2 Irreducibility, Aperiodicity and Recurrence
Aperiodicity
Irreducibility
Recurrence
7.3 Limiting and Stationary Distributions
7.4 Simulation Examples
Notes
Exercises
8 Search Engines
8.1 Markovian Modeling of Ranking
8.2 Limiting and Stationary Distributions
8.3 Matrix Perturbation
8.4 State Ranking
Convergence Analysis
Mean Return Times Analysis
8.5 Meta Search Engines
Limiting and Stationary Distributions
Matrix Perturbation
State Ranking
Convergence Analysis
Mean Return Times Analysis
Notes
Exercises
9 Hidden Markov Model
9.1 Graphical Markov Model
Hidden Chain
Observed Process
Example
9.2 Forward–Backward Formulas
9.3 Hidden State Estimation
Maximum Likelihood Estimation
9.4 Forward–Backward Algorithm
Forward Algorithm
Backward Algorithm
Forward–Backward Algorithm
9.5 Baum-Welch Algorithm
Simulation Example
Frequency Analysis
Notes
Exercises
10 Markov Decision Processes
10.1 Construction
Example: Deterministic MDP
10.2 Reinforcement Learning
Policy Optimization
Q-Learning
10.3 Example: Deterministic MDP
Optimal Value Function
Optimal Policy
10.4 Example: Stochastic MDP
Notes
Exercises
Nicolas Privault - Discrete Stochastic Processes_ Tools for Machine Learning and.pdf
(12.34 MB, 需要: RMB 19 元)
京公网安备 11010802022788号
