5. The EM Algorithm (14 points) Suppose you have two bags, each of which contains a number of balls. Each ball belongs to one of n colors. The probability of drawing a ball of color c, from bag 1 is pi (c), and the probability of drawing a ball of color c, from bag 2 is p2(ci). Now, suppose we want to draw a sequence of balls from the two bags using the following procedure. Your dear TA, Isaac, first flips a biased coin, where the probability of getting a head is . If the outcome of the coin flip is head, then he lets you draw a ball from bag 1. Otherwise, he lets you draw a ball from bag 2. After you note the color of the ball, you put it back into the bag. If we repeat this procedure m times, we can produce a color sequence Sr( x1 , 22, . . . ,xm }. It should be easy to see that the probability of drawing a ball of color c; is: Note that you know neither the outcome of each coin flip nor the identity of the bag from which you drew each ball, because Isaac decided not to disclose this information to you. Specifically, after each coin flip, Isaac will take one of the two bags (whichever bag he takes will of course be based on the outcome of the coin flip) and ask you to draw a ball from it. Hence, the identity of the bag from which you drew a ball is hidden information. Our goal here is to use the EM algorithm to find the maximum likelihood estimate of . Let Mi be the number of times bag 1 was chosen behind the generation of the sequence S (a) Expectation step: Compute the expected value of Mi. You should express this value in terms of . (Hint: convince yourself that (1) the expected value of Mi is the sum of the probabilities that bag 1 was chosen to draw each of the m balls, and (2) the probability that bag I was chosen to draw a ball can be expressed in terms of .) (b) Maximization step: Compute . You should express in terms of 11. 5. The EM Algorithm (14 points) Suppose you have two bags, each of which contains a number of balls. Each ball belongs to one of n colors. The probability of drawing a ball of color c, from bag 1 is pi (c), and the probability of drawing a ball of color c, from bag 2 is p2(ci). Now, suppose we want to draw a sequence of balls from the two bags using the following procedure. Your dear TA, Isaac, first flips a biased coin, where the probability of getting a head is . If the outcome of the coin flip is head, then he lets you draw a ball from bag 1. Otherwise, he lets you draw a ball from bag 2. After you note the color of the ball, you put it back into the bag. If we repeat this procedure m times, we can produce a color sequence Sr( x1 , 22, . . . ,xm }. It should be easy to see that the probability of drawing a ball of color c; is: Note that you know neither the outcome of each coin flip nor the identity of the bag from which you drew each ball, because Isaac decided not to disclose this information to you. Specifically, after each coin flip, Isaac will take one of the two bags (whichever bag he takes will of course be based on the outcome of the coin flip) and ask you to draw a ball from it. Hence, the identity of the bag from which you drew a ball is hidden information. Our goal here is to use the EM algorithm to find the maximum likelihood estimate of . Let Mi be the number of times bag 1 was chosen behind the generation of the sequence S (a) Expectation step: Compute the expected value of Mi. You should express this value in terms of . (Hint: convince yourself that (1) the expected value of Mi is the sum of the probabilities that bag 1 was chosen to draw each of the m balls, and (2) the probability that bag I was chosen to draw a ball can be expressed in terms of .) (b) Maximization step: Compute . You should express in terms of 11