Markov Chains for Machine Learning

* Motivate the use of methods to capture the structure of problems
* How to?
- assume random walker over structure
- what are the states? web pages, movies, books, authors of articles, ...
* Goals
- clustering
- ranking
- select top k
- given a node, determine which one is more closely related to it
* Tools
- Random walks on graphs
- Markov chains
* Markov chain 
- memoryless property
- but state can store history!
- 1 step, 2 step, 3 step, .... transitions
- steady state
- iterative versus direct solution methods
- ergodicity
* Node clustering: L = I - D^(-1/2) S D^(-1/2)