advertisement

Sequences II Prof. Noah Snavely CS1114 http://cs1114.cs.cornell.edu Administrivia Assignments: – A5P2 due on Friday Quiz Tuesday, 4/24 Final project proposals due on CMS by this Thursday 2 Google’s PageRank Start at a random page, take a random walk. Where do we end up? H A I D E B C F J G 3 Google’s PageRank Add 15% probability of moving to a random page. Now where do we end up? H A I D E B C F J G 4 Google’s PageRank PageRank(P) = Probability that a long random walk ends at node P H A I D E B C F J G 5 Example (The ranks are an eigenvector of the transition matrix) 6 Modeling Texture What is texture? – An image obeying some statistical properties – Similar structures repeated over and over again – Often has some degree of randomness Markov Random Field • A Markov random field (MRF) • generalization of Markov chains to two or more dimensions. • First-order MRF: • probability that pixel X takes a certain value given the values of neighbors A, B, C, and D: A D X C • Higher order MRF’s have larger neighborhoods * * * * * X * * * * * * * * * X * * * * * * B Texture Synthesis [Efros & Leung, ICCV 99] Can apply 2D version of text synthesis More Synthesis Results •Increasing window size More Results •reptile skin •aluminum wire Image-Based Text Synthesis Author recognition Simple problem: Given two Markov chains, say Austen (A) and Dickens (D), and a string s (with n words), how do we decide whether A or D wrote s? Idea: For both A and D, compute the probability that a random walk of length n generates s 13 Probability of a sequence What is the probability of a given n-length sequence s? s = s1 s2 s3 … sn Probability of generating s = the product of transition probabilities: Probability that a sequence starts with s1 Transition probabilities 14 Likelihood Compute this probability for A and D “likelihood” of A Jane Austen wrote s Charles Dickens wrote s “likelihood” of D ??? 15 Problems with likelihood 1. Most strings of text (of significant length) have probability zero – Why? 2. Even if it’s not zero, it’s probably extremely small – What’s 0.01 * 0.01 * 0.01 * … (x200) … * 0.01? – According to Matlab, zero How can we fix these problems? 16