6.867 Machine Learning, Lecture 19 Notes

1 Lecture topics: • Markov chains (cont’d) • Hidden Markov Models Markov chains (cont’d) In the context of spectral clustering (last lecture) we discussed a random walk over the nodes induced by a weighted graph. Let Wij ≥ 0 be symmetric weights associated with the edges in the graph; Wij = 0 whenever edge doesn’t exist. We also assumed that Wii = 0 for all i. The graph defines a random walk where the probability of transitioning from node (state) i to node j is given by Wij P (X(t + 1) = j|X(t) = i) = Pij = � j � Wij � (1) Note that self-transitions (going from i to i) are disallowed because Wii = 0 for all i. We can understand the random work as a homogeneous Markov chain: the probability of transitioning from i to j only depends on i, not the path that took the process to i. In other words, the current state summarizes the past as far as the future transitions are concerned. This is a Markov (conditional independence) property: P (X(t + 1) = j|X(t) = i, X(t − 1) = it−1 , . . . , X(1) = i1 ) = P (X(t + 1) = j|X(t) = i) (2) The term “homogeneous” specifies that the transition probabilities are independent of time (the same probabilities are used whenever the random walk returns to i). We also defined ergodicity as follows: Markov chain is ergodic if there exist a finite m such that P (X(t + m) = j|X(t) = i) > 0 for all i and j (3) Simple weighted graphs need not define ergodic chains. Consider, for example, a weighted graph between two nodes 1 − 2 where W12 > 0. The resulting random walk is necessarily periodic, i.e., 121212 . . .. A Markov chain is ergodic only when all the states are communi­ cating and the chain is aperiodic which is clearly not the case here. Similarly, even a graph 1 − 2 − 3 with positive weights on the edges would not define an ergodic Markov chain. Every other state would necessarily be 2, thus the chain is periodic. The reason here is 2 that Wii = 0. By adding a positive self-transition, we can remove periodicity (random walk would stay in the same state a variable number of steps). Any connected weighted graph with positive weights and positive self-transitions gives rise to an ergodic Markov chain. Our definition of the random walk so far is a bit incomplete. We did not specify how the process started, i.e., we didn’t specify the initial state distribution. Let q(i) be the probability that the random walk is started from state i. We will use q as a vector of probabilities across k states (reserving n for the number training examples as usual). There are two ways of describing Markov chains: through state transition diagrams or as simple graphical models. The descriptions are complementary. A transition diagram is a directed graph over the possible states where the arcs between states specify all allowed transitions (those occuring with non-zero probability). See Figure 1 for examples. We could also add the initial state distribution as transitions from a dedicated initial (null) state (not shown in the figure). 1 1 2 2 3 Figure 1: Examples of transition diagrams defining non-ergodic Markov chains. In graphical models, on the other hand, we focus on explicating variables and their de­ pendencies. At each time point the random walk is in a particular state X(t). This is a random variable. It’s value is only affected by the random variable X(t − 1) specifying the state of the random walk at the previous time point. Graphically, we can therefore write a sequence of random variables where arcs specify how the values of the variables are influenced by others (dependent on others). More precisely, X(t − 1) → X(t) means that the value of X(t) depends on X(t − 1). Put another way, in simulating the random walk, we would have to know the value of X(t − 1) in order to sample a value for X(t). The graphical model is shown in Figure 2. State prediction We will cast the problem of calculating the predictive probabilities over states in a form 3 X(t − 1) X(t) X(t + 1) . . . . . . Figure 2: Markov chain as a graphical model. that will be useful for Hidden Markov Models later on. Since P (X(t + m) = j|X(t) = i) = [P m ]ij (4) we can also write for any n P (X(n) = j) = k � q(i)P (X(n) = j|X(1) = i) = i=1 k � q(i)[P n−1 ]ij (5) i=1 In a vector form q T P n−1 is a row vector whose j th component is P (X(n) = j). Note that the matrix products involve summing over all the intermediate states until X(n) = j. More explicitly, let’s evaluate the sum over all the states x1 , . . . , xn in the matrix form as � P (X(1) = x1 ) x1 ,...,xn n−1 � n − 1 times � �� � P (X(t + 1) = xt+1 |X(t) = xt ) = q P P · · · P P 1 = 1 T (6) t=1 This is a sum over k n possible state configurations (settings of x1 , . . . , xn ) but can be easily performed in terms of matrix products. We can understand this in terms of recursive eval­ uation of t step probabilities αt (i) = P (X(t) = i). We will write αt for the corresponding column vector so that t − 1 times � �� � q P P · · · P P = αtT T (7) Clearly, q T = α1T αtT−1 P = αtT , t > 1 k � i=1 Estimation αt−1 (i)Pij = αt (j) (8) (9) (10) 4 Markov models can be estimated easily from observed sequences of states. Given x1 , . . . , xn (e.g., 1212221), the log-likelihood of the observed sequence is given by � � n−1 � log P (x1 , . . . , xn ) = log P (X(1) = x1 ) P (X(t + 1) = xt+1 |X(t) = xt ) (11) t=1 = log q(x1 ) + n−1 � log Pxt ,xt+1 (12) n̂(i, j) log Pij (13) t=1 = log q(x1 ) + � i,j where n̂(i, j) is the number of observed transitions from i to j in the sequence x1 , . . . , xn . The resulting maximum likelihood setting of Pij is obtained as an empirical fraction n̂(i, j) P̂ij = � � j � n̂(i, j ) (14) Note that q(i) can only be reliably estimated from multiple observed sequences. For ex­ ample, based on x1 , . . . , xn , we would simply set q̂(i) = δ(i, x1 ) which is hardly accurate (sample size one). Regularization is useful here, as before. Hidden Markov Models Hidden Markov Models (HMMs) extend Markov models by assuming that the states of the Markov chain are not observed directly, i.e., the Markov chain itself remains hidden. We therefore also model how the states relate to the actual observations. This assumption of a simple Markov model underlying a sequence of observations is very useful in many practical contexts and has made HMMs very popular models of sequence data, from speech recogni­ tion to bio-sequences. For example, to a first approximation, we may view words in speech as Markov sequences of phonemes. Phonemes are not observed directly, however, but have to be related to acoustic observations. Similarly, in modeling protein sequences (sequences of amino acid residues), we may, again approximately, describe a protein molecule as a Markov sequence of structural characteristics. The structural features are typically not observable, only the actual residues. We can understand HMMs by combining mixture models and Markov models. Consider the simple example in Figure 3 over four discrete time points t = 1, 2, 3, 4. The figure summarizes multiple sequences of observations y1 , . . . , y4 , where each observation sequence 5 corresponds to a single value yt per time point. Let’s begin by ignoring the time information and instead collapse the observations across the time points. The observations form two clusters are now well modeled by a two component mixture: P (y) = 2 � P (j)P (y|j) (15) j=1 where, e.g., P (y|j) could be a Gaussian N (y; µj , σj2 ). By collapsing the observations we are effectively modeling the data at each time point with the same mixture model. If we generate data form the resulting mixture model we would select a mixture component at random at each time step and generate the observation from the corresponding component (cluster). There’s nothing that ties the selection of mixture components in time so that samples from the mixture yield “phantom” clusters at successive time points (we select the wrong component/cluster with equal probability). By omitting the time information, we therefore place half of the probability mass in locations with no data. Figure 4 illustrates the mixture model as a graphical model. y y x x x x x x x x x x a) t=1 t=2 x x x x t=3 x x x x x x t=4 x x x x time b) t=1 t=2 x x x x t=3 t=4 time Figure 3: a) Example data over four time points, b) actual data and ranges of samples generated from a mixture model (red ovals) estimated without time information. The solution is to model the selection of the mixture components as a Markov model, i.e., the component at t = 2 is selected on the basis of the component used at t = 1. Put another way, each state in the Markov model now uses one of the components in the mixture model to generate the corresponding observation. As a graphical model, the mixture model is a combination of the two as shown in Figure 5. Probability model One advantage of representing the HMM as a graphical model is that we can easily write down the joint probability distribution over all the variables. The graph explicates how the 6 X(1) X(2) X(3) X(4) Y (1) Y (2) Y (3) Y (4) Figure 4: A graphical model view of the mixture model over the four time points. The variables are indexed by time (different samples would be drawn at each time point) but the parameters are shared across the four time points. X(t) refers to the selection of the mixture component while Y (t) refers to the observations. variables depend on each other (who influences who) and thus highlights which conditional probabilities we need to write down: P (x1 , . . . , xn , y1 , . . . , yn ) = P (x1 )P (y1 |x1 )P (x2 |x1 )P (y2 |x2 ) . . . n−1 � = P (x1 )P (y1 |x1 ) [P (xt+1 |xt )P (yt+1 |xt+1 )] = q(x1 )P (y1 |x1 ) t=1 n−1 � � � Pxt ,xt+1 P (yt+1 |xt+1 ) (16) (17) (18) t=1 where we have used the same notation as before for the Markov chains. X(1) X(2) X(3) X(4) Y (1) Y (2) Y (3) Y (4) Figure 5: HMM as a graphical model. It is a Markov model where each state is associated with a distribution over observations. Alternatively, we can view it as a mixture model where the mixture components are selected in a time dependent manner. Three problems to solve We typically have to be able to solve the following three problems in order to use these models effectively: 7 1. Evaluate the probability of observed data or � P (y1 , . . . , yn ) = P (x1 , . . . , xn , y1 , . . . , yn ) (19) x1 ,...,xn 2. Find the most likely hidden state sequence x∗1 , . . . , x∗n given observations y1 , . . . , yn , i.e., {x∗1 , . . . , x∗n } = arg max P (x1 , . . . , xn , y1 , . . . , yn ) (20) x1 ,...,xn (l) (l) 3. Estimate the parameters of the model from multiple sequences of y1 , . . . , ynl , l = 1, . . . , L. Problem 1 As in the context of Markov chains we can efficiently sum over the possible hidden state sequences. Here the summation means evaluating P (y1 , . . . , yn ). We will perform this in two ways depending on whether the recursion moves forward in time, computing αt (j), or backward in time, evaluating βt (i). The only change from before is the fact that whatever state we happen to visit at time t, we will also have to generate the observation yt from that state. This additional requirement of generating the observations can be included via diagonal matrices ⎡ ⎤ P (y|1) 0 ⎦ ··· (21) Dy = ⎣ 0 P (y|k) So, for example, T q Dy1 1 = k � q(i)P (y1 |i) = P (y1 ) (22) i=1 Similarly, q T Dy1 P Dy2 1 = k � i=1 q(i)P (y1 |i) k � Pij P (y2 |j) = P (y1 , y2 ) (23) j=1 We can therefore write the forward and backward algorithms as methods that perform the matrix multiplications in q T Dy1 P Dy2 P · · · P Dyn 1 = P (y1 , . . . , yn ) (24) 8 either in the forward or backward direction. In terms of the forward pass algorithm: � k � q T Dy1 = α1T T αt−1 P Dyt = αtT , or equivalently � αt−1 (i)Pij P (yt |j) = αt (j) (25) (26) (27) i=1 These values hold exactly αt (j) = P (y1 , . . . , yt , X(t) = j) since we have generated all the observations up to and including yt and have summed over all the states except for the last one X(t). The backward pass algorithm is similarly defined as: βn = 1 βt = P Dyt+1 βt+1 , or equivalently βt (i) = k � Pij P (yt+1 |j)βt+1 (j) (28) (29) (30) j=1 In this case βt (i) = P (yt+1 , . . . , yn |X(t) = i) since we have summed over all the possible values of the state variables X(t + 1), . . . , X(n), starting from a fixed X(t) = i, and the first observation we have generated in the recursion is yt+1 . By combining the two recursions we can finally evaluate P (y1 , . . . , yn ) = αtT βt = k � αt (i)βt (i) (31) i=1 which holds for any t = 1, . . . , n. You can understand this result in two ways: either in terms of performing the remaining matrix multiplication corresponding to the two parts αT βt � ��t �� �� � P (y1 , . . . , yn ) = (q T Dy1 P · · · P Dyt ) (P Dyt+1 · · · P Dyn 1) (32) or as an illustration of the Markov property: αt (i) βt (i) k � �� �� �� � � P (y1 , . . . , yn ) = P (y1 , . . . , yt , X(t) = i) P (yt+1 , . . . , yn |X(t) = i) i=1 (33) 9 Also, since βn (i) = 1 for all i, clearly P (y1 , . . . , yn ) = k � i=1 αn (i) = k � i=1 P (y1 , . . . , yt , X(t) = i) (34)