### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# 272 Class Note for CS 59000 with Professor Qi at Purdue

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Department

This 32 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Purdue University taught by a professor in Fall. Since its upload, it has received 21 views.

## Similar to Course at Purdue

## Reviews for 272 Class Note for CS 59000 with Professor Qi at Purdue

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

CS 59000 Statistical Machine learning Lecture 25 Yuan Aura j PUMME C3 Hum 25 200 Outline 0 Review of Hidden Markvo Models forward backward algorithm EM for learning HMM parameters Viterbi Algorithm Kalman filtering and smoothing Rejection Sampling Importance Sampling Metroplis hasting algorithm Gibbs sampling Hidden Markov Models Many applications eg speech recognition natural language processing handwriting recognition bio sequence analysis From Mixture Models to HMMs By turning a mixture Model into a dynamic model we obtain the HMM Let model the dependence between two consecutive latent variables by a transition probability K K pZnZn71Agt H H Ag1jznlc k1j1 HMMS Prior on initial latent variable K plt21lvrgt ngw ZR wk 2 1 A721 Emission probabilities K pX71Z717 HpXn kZnA 191 Joint distribution N N 19X Zl9 pZ17T pzynlzyn1i M H 10anle lt25 m 1 Samples from HMM l l 05 0 05 I 0 05 a Contours of constant probability density for the emission distributions corresponding to each of the three states of the latent variable b A sample of 50 points drawn from the hidden Markov model with lines connecting the successive observations Inference Forwardbackward Algorithm Goal compute marginals for latent variables Forward backward Algorithm exact inference as special case of sum product algorithm on the HMM Factor graph representation grouping emission density and transition probability in one factor at a time Forwardbackward Algorithm as Message Passing Method 1 O O O 31 3111 3n MZ i PZ1PltX1Z1 fnZn 17Zn 19Z39n Zn 1pxn Zn Forward messages IU39Zni gtfn Zn 1 Mf711 gtZn1Zn 1 Wen gt271 Z71 Z fnzn 1aZnHzn1 gtfnZn 1 znel lufn Znzn Z fnZn17Z39nlujfngjr gtZn1Zn 1 1Zn an Znzn Forwardbackward Algorithm as Message Passing Method 2 ll 71 I A n I m Backward messages Q how to compute it Zn an1 Zn The messages actually involves X pZ717 an I Zn ZnquotLfn1 gtZn Zn azn ltzngt Z plxlzvzpzn 1Z39nl lzn flZ39rlr p an Similarly we can compute the following Q why CYZn 1pxnlZ39rLpZ39rblZn i zn ltZn 1Zn pltZn 1ianX Rescaling to Avoid Overflowing When a sequence is long the forward message will become to small to be represented by the dynamic range of the computer We redefine the forward message 04272 pX1 Zn A 04Zn as alzn plznlxh I i lxnl 19X17 Xn Similarly we redefine the backward message ltzn PXn17 7 XNlZn as pXn19 39 39 7XNlZn pXn 17 39 39 39 7XNlX17 39 39 7X71 Then we can compute VZquot1 aZnBZn Zn 17Zn C Ilaltz 71 1pX77lz71rpznlZ 1 ltzn See detailed derivation in textbook Viterbi Algorithm Viterbi Algorithm 0 Finding the most probable sequence of states Special case of sum product algorithm on HMM What if we want to find the most probable individual states Maximum Likelihood Estimation for HMM Goal maximize pltX6gt meizim From EM for mixture of Gaussians to EM for HMMS EM for HMM E step WI ZI7 ZH pz IX 9 pzl1tz1X 601d Computed from forwardbackwardsumproduct algorithm M step 771 HI JV Z 13IIA39XH ul v Z nlc i Z 739I739XH ILLXn ILAT 1 Linear Dynamical Systems 19ZHIZV1 NZ7Az11quot XH ZH NX1CZZ 1Z1 NZIIM0V0 Equivalently we have Zn Aznil W77 XII CZII VII 21 no 11 where W N N39W0 F v N Nv02 11 Nu0V Kalman Filtering and Smoothing Inference on linear Gaussian systems Kalman filtering sequentially update scaled forward message A Z39n azn Z7X7Xn gt 1 i pltX177X71 Kalman smoothing sequentially update state beliefs based on scaled forward and backward messages f7Z39n ampZrzBZn Sampling Methods Goal compute Elf fZpZdZ Challenges we cannot compute the above equation in analytically Sampling methods draw random samples suchthat Rejection Sampling 1 Goal draw samples from a complicated distribution 1 plz 2 1359 where 152 can readily be evaluated but Zp is unknown In the rejection sampling method samples are drawn from a sim ple distribution 12 and rejected if they fall in the grey area be tween the unnormalized distribu tion 7152 and the scaled distribu tion kqz The resulting samples are distributed according to 122 which is the normalized version of 192 Example Plot showing the gamma distribu tion given by 1115 as the green curve with a scaled Cauchy pro posal distribution shown by the red curve Samples from the gamma distribution can be obtained by sampling from the Cauchy and then applying the rejection sam pling criterion 015 Limitations of Rejection Sampling When the proposal distribution is very different from the un normlized target distribution many samples will be wasted Difficult for high dimensional problems Importance Sampling 1 Em fzpz dz z 2 Zp gtfzn Importance weights n pzlqz gt Discussion what will be an ideal proposal distribution qZ Importance Sampling 2 When Zpin 192 i5zZp is unknown we have Em fltzgtpzdz Z z 25 gt ffltzgt qltzgtdz L 2 g Wu 1 where 73 z EZ Importance Sampling 3 2 g Ziqgzdz E2qzdz 1 L N E 1 1 a 13z iz gt L Em 2 Zum w E 17ZmCIZD 2mm 2 mmzvmnmzmw39 Sampling and EM M step in EM maximizes mam pZX601d111pZX6dZ What if we cannot even evaluate the above integration One idea using sampling method L Old N 1 w l Qlt99 piglnmz XI6gt Known as Monte Carlo EM algorithm Imputation Posterior IP Algorithm Change EM for Bayesian Estimation IP Algorithm Istep We wish to sample from ZX but we cannot do this directly We therefore note the relation ZlX Z0X10Xt16 1130 and hence for l I we rst draw a sample 19 from the current esti mate 1 orp0X and then use this to draw a sample Z from 1Z6 X Pstep Given the relation HIX 70ZX72Z1X1Z 1131 we use the samples 21 obtained from the I step to compute a revised estimate of the posterior distribution over 9 given by L p0X Zp61ZWX 1132 11 By assumption it will be feasible to sample from this approximation in the Istep Markov Chain Monte Carlo Goal use Markov chains to draw samples from a given distribution Idea set up a Markov chain that converges to the target distribution and draw samples from the chain Invariant Distribution and Detailed Balance 1order Markov chain pzquot39 1gtlzlt1WZWpz lz m Transition probabilities Tmzlmaz gtEPltZquot IZ Invariant distribution A distribution is said to be invariant or stationary with respect to a Markov chain if each step in the chain leaves that distribution invariant Detailed balance sufficient condition for invariant distributions IZTZ 2 19Z TZ 2 Ergodicity and Equilibrium Distribution For m gt00 the distribution pzm converges to the required invariant distribution ie the target distribution irrespective of the choice of initial distribution which may be different from the target distribution This property is called ergodicity and the invariant distribution is called the equilibrium distribution Under weak restrictions on invariant and transition distributions a homogeneous Markov chain will be ergodic MetropolisHastings Algorithm Iterative algorithm At step T with state 2 we draw a sample 2 from a proposal qulzm distribution and accept it with probability T 14 Z7 ZT lnin pZTQkZlZTgt Such that the detailed balance requirement is satisfied Choice of Proposal Distributions Local Gaussian distributions centered on the current state if it is symmetric Gaussian HM algorithm reduces to Metroplis algorithm Variance is too small gt high acceptance rate but slow random walks Variance is too large gt low acceptance rate Global Gaussian distribution find Laplace approximation to the posterior amp sample from it Mixture of Gaussians fit a mixture of Gaussians and then sample from it Example A simple illustration using Metropo lis algorithm to sample from a Gaussian distribution whose one standarddeviation contour is shown by the ellipse The proposal distribu tion is an isotropic Gaussian distri bution whose standard deviation is 02 Steps that are accepted are shown as green lines and rejected steps are shown in red A total of 150 candidate samples are gener ated of which 43 are rejected 25 39 Gibbs Sampler 1 Gibbs Sampling 1 Initialize 22 z39 11 2 ForT1T 739 1 739 739 739 Sample p21z hag Z M Sample z TH pzglzr1 25 1 1 1 Sample 237 pzjlz wz T i gt73 Tgtigt 1 71 71 71 739 Gibbs Sampler 2 Special case of Metroplis Hasting Sampler Given the proposal distribution qkzlz 19ZZZIZVJ The acceptance rate is AZ Z pzqkzlz pZl ZltkpltZApzk Zltl ZN Wm 29Zk ZkpltZkpZlzkgt 1 So every sample from the proposal distribution in a Gibbs sampler will be accepted

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.