Machine learning for sequential data: A review <s> Hidden Markov Models and Related Methods <s> Vibratory power unit for vibrating conveyers and screens comprising an asynchronous polyphase motor, at least one pair of associated unbalanced masses disposed on the shaft of said motor, with the first mass of a pair of said unbalanced masses being rigidly fastened to said shaft and with said second mass of said pair being movably arranged relative to said first mass, means for controlling and regulating the conveying rate during conveyer operation by varying the rotational speed of said motor between predetermined minimum and maximum values, said second mass being movably outwardly by centrifugal force against the pressure of spring means, said spring means being prestressed in such a manner that said second mass is, at rotational motor speeds lower than said minimum speed, held in its initial position, and at motor speeds between said lower and upper values in positions which are radially offset with respect to the axis of said motor to an extent depending on the value of said rotational motor speed. <s> BIB001 </s> Machine learning for sequential data: A review <s> Hidden Markov Models and Related Methods <s> Hidden Markov models (HMMs) are a powerful probabilistic tool for modeling sequential data, and have been applied with success to many text-related tasks, such as part-of-speech tagging, text segmentation and information extraction. In these cases, the observations are usually modeled as multinomial distributions over a discrete vocabulary, and the HMM parameters are set to maximize the likelihood of the observations. This paper presents a new Markovian sequence model, closely related to HMMs, that allows observations to be represented as arbitrary overlapping features (such as word, capitalization, formatting, part-of-speech), and defines the conditional probability of state sequences given observation sequences. It does this by using the maximum entropy framework to fit a set of exponential models that represent the probability of a state given an observation and the previous state. We present positive experimental results on the segmentation of FAQ’s. <s> BIB002
The hidden Markov Model (HMM; see Figure 2(a) ) is a probabilistic model of the way in which the x i and y i strings are generated-that is, it is a representation of the joint distribution P (x, y). It is defined by two probability distributions: the transition distribution P (y t |y t−1 ), which tells how adjacent y values are related, and the observation distribution P (x|y), which tells how the observed x values are related to the hidden y values. These distributions are assumed to be stationary (i.e., the same for all times t). In most problems, x is a vector of features (x 1 , . . . , x n ), which makes the observation distribution difficult to handle without further assumptions. A common assumption is that each feature is generated independently (conditioned on y). This means that P (x|y) can be replaced by the product of n separate distributions P (x j |y), j = 1, . . . , n. The HMM generates x i and y i as follows. Suppose there are K possible labels 1, . . . , K. Augment this set of labels with a start label 0 and a terminal label K + 1. Let y i,0 = 0. Then, generate the sequence of y values according to P (y i,t |y i,t−1 ) until y i,t = K + 1. At this point, set T i := t. Finally, for each t = 1, . . . , T i , generate x i,t according to the observation probabilities P (x i,t |y i,t ). In a sequential supervised learning problem, it is straightforward to determine the transition and observation distributions. P (y i,t |y i,t−1 ) can be computed by looking at all pairs of adjacent y labels (after prepending 0 at the start and appending K + 1 to the end of each y i ). Similarly, P (x j |y) can be computed by looking at all pairs of x j and y. The most complex computation is to predict a value y given an observed sequence x. This computation depends on the nature of the loss function. Because the HMM is a representation of the joint probability distribution P (x, y), it can be applied to compute the probability of any particular y given any particular x: P (y|x). Hence, for an arbitrary loss function L(y, y), the optimal prediction is y = argmin However, if the sequences are of length L and there are K labels, then direct evaluation of this equation requires O(K L ) probability evaluations, which is usually impractical. There are two notable cases where this computation can be performed in The first is where the loss function depends on the entire sequence. In this case, the goal is usually to find the y with the highest probability: y = argmax y P (y|x). This can be computed via the Viterbi algorithm, which is a dynamic programming algorithm that computes, for each class label u and each time step t, the probability of the most likely path starting at time 0 end ending at time t with class u. When the algorithm reaches the end of the sequence, it has computed the most likely path from time 0 to time T i and its probability. The second interesting case is where the loss function decomposes into separate decisions for each y t . In this case, the so-called Forward-Backward algorithm can be applied. It performs a left-to-right pass, which fills a table of α t (y t ) values which represent P (y 1 , . . . , y t |x 1 , . . . , x t ) , and a right-to-left pass, which fills a table of β t (y t ) values which represent P (y t , . . . , y Ti |x t+1 , . . . , x Ti ). Once these two passes are complete, the quantity gives the desired probability: P (y t = u|x). This probability can be applied to choose the predicted value y t that minimizes the loss function. Although HMMs provide an elegant and sound methodology, they suffer from one principal drawback: The structure of the HMM is often a poor model of the true process producing the data. Part of the problem stems from the Markov property. Any relationship between two separated y values (e.g., y 1 and y 4 ) must be communicated via the intervening y's. A first-order Markov model (i.e., where P (y t ) only depends on y t−1 ) cannot in general capture these kinds of relationships. Sliding window methods avoid this difficulty by using a window of x t values to predict a single y t . However, the second problem with the HMM model is that it generates each x t only from the corresponding y t . This makes it difficult to use an input window. In theory, one could replace the output distribution P (x t |y t ) by a more complex distribution P (x t |y t−1 , y t , y t+1 ) which would then allow an observed value x t to influence the three y values. But it is not clear how to represent such a complex distribution compactly. Several directions have been explored to try to overcome the limitations of the HMM: Maximum Entropy Markov models (MEMMs), Input-Output HMMs (IOHMMs), and conditional random fields (CRFs); see Figure 2 . All of these are conditional models that represent P (y|x) rather than P (x, y). They do not try to explain how the x's are generated. Instead, they just try to predict the y values given the x's. This permits them to use arbitrary features of the x's including global features, features describing non-local interactions, and sliding windows. The Maximum Entropy Markov Model learns P (y t |y t−1 , x t ). It is trained via a maximum entropy method that attempts to maximize the conditional likelihood of the data: The maximum entropy approach represents P (y t |y t−1 , x t ) as a log-linear model: where Z(y t−1 , x) is a normalizing factor to ensure that the probabilities sum to 1. Each f α is a boolean feature that can depend on y t and on any properties of the input sequence x. For example, in their experiments with MEMMs, McCallum, et al. BIB002 employed features such as "x begins with a number", "x ends with a question mark", etc. Hence, MEMMs support long-distance interactions. The IOHMM is similar to the MEMM except that it introduces hidden state variables s t in addition to the output labels y t . Sequential interactions are modeled by the s t variables. To handle these hidden variables during training, the Expectation-Maximization (EM; BIB001 ) algorithm is applied. Bengio and Frasconi  report promising results on various artificial sequential supervised learning and sequence classification problems. Unfortunately, the MEMM and IOHMM models suffer from a problem known as the label bias problem. To understand the origins of the problem, consider the MEMM and note that yt P (y t |y t−1 , x 1 , . . . , This says that the total probability mass "received" by y t−1 (based on x 1 , . . . , x t−1 ) must be "transmitted" to labels y t at time t regardless of the value of x t . The only role of x t is to influence which of the labels receive more of the probability at time t. In particular, all of the probability mass must be passed on to some y t even if x t is completely incompatible with y t . For example, suppose that there are two labels {1, 2} and that the input string x ="rob" is supposed to get the label string "111" and x ="rib" is supposed to get the label string "222". Consider what happens with the input string x ="rib". After observing the x 1 = r, the probability of y 1 is evenly split between labels "1" and "2": P (y 1 = 1|x 1 = r) = P (y 1 = 2|x 1 = r) = 0.5. After observing x 2 = i, the probability remains equally split, because the 0.5 probability for P (y 1 = 1|x 1 = r) must be passed on to P (y 2 = 1|x 1 = r, x 2 = i), since the y 1 = 1 → y 2 = 2 transition has probability 0. After observing x 3 = b, the probability of y 3 = 1 and y 3 = 2 remains equally split. So the MEMM has completely ignored the "i"! The same problem occurs with the hidden states s t of the IOHMM.