Stacked Sequential Learning

1 Introduction

In this paper, we will consider the application of sequential probabilistic learners to sequential partitioning tasks. Sequential partitioning tasks are sequential classification tasks characterized by long runs of identical labels: examples of these tasks include document analysis, video segmentation, and gene finding.

Motivated by some anomalous behavior observed for one sequential learning method on a particular partitioning task, we will derive a new learning scheme called stacked sequential learning. Like boosting, stacked sequential learning is a meta-learning method, in which an arbitrary base learner is augmented-in this case, by making the learner aware of the labels of nearby examples. Sequential stacking is simple to implement, can be applied to virtually any base learner, and imposes only a constant overhead in training time: in our implementation, the sequentially stacked version of the base learner A trains about seven times more slowly than A.

In experiments on several partitioning tasks, sequential stacking consistently improves the performance of nonsequential base learners. More surprisingly, sequential stacking also often improves performance of learners specifically designed for sequential tasks, such as conditional random fields and discriminatively trained HMMs. Finally, on our set of benchmark problems, a sequentially stacked maximum-

Vitor R. Carvalho

Language Technologies Institute School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 vitor@cs.cmu.edu

entropy learner generally outperforms conditional random fields.

2 Motivation: AHard Task for MEMMs

To motivate the novel learning method that we will describe below, we will first analyze the behavior of one well-known sequential learner on a particular real-world problem. In a recent paper [Carvalho and Cohen, 2004], we evaluated a number of sequential learning methods on the problem of recognizing the "signature" section of an email message. Each line of an email message was represented with a set of handcrafted features, such as "line contains a possible phone number", "line is blank", etc. Each email message was represented as a vector x of feature-vectors x1, . . . , xn, where xi is the feature-vector representation of the i-th line of the message. A line was labeled as positive if it was part of a signature section, and negative otherwise. The labels for a message were represented as another vector y, where yi is the label for line i.

The dataset contains 33,013 labeled lines from 617 email messages. About 10% of the lines are labeled "positive". Signature sections always fall at the end of a message, usually in the last 10 lines. In the experiments below, the data was split into a training set (of 438 sequences/emails), and a test set with the remaining sequences, and we used the "basic" feature set from Carvalho & Cohen.

The complete dataset is represented as a set S of examples S = {(x1, y1), . . . , (xt, yt), . . . , (xm, ym)}. Sequential learning is the problem of learning, from such a dataset, a sequential classifier-i.e., a function f such that f(x) produces a vector of class labels y. Clearly, any ordinary non-sequential learning algorithm can be used for sequential learning, by ignoring the sequential nature of the data 1 .

In the previous paper [Carvalho and Cohen, 2004], we reported results for several non-sequential and sequential learners on the signature-detection problem, including a nonsequential maximum entropy learner [Berger et al., 1996]

1 Specifically, one could build a dataset of non-sequential examples (xt,i, yt,i) from S, and use it to train a classifier g that maps a single feature-vector x to a label y. One can then use g to classify each instance xi in the vector x = 〈x1, . . . , xn〉 separately, ignoring its sequential position, and append the resulting predictions yi into an output vector y.

(henceforth ME) and conditional random fields [Lafferty et al., 2001] (henceforth CRFs). Another plausible sequential learning method to apply to this task are maximumentropy Markov models (MEMMs) [McCallum et al., 2000], also called maximum-entropy taggers [Ratnaparkhi, 1999], conditional Markov models [Klein and Manning, 2002], and recurrent sliding windows [Dietterich, 2002]. In this model, the conditional probability of a label sequence y given an instance sequence x is defined to be Pr(y|x) = ∏i Pr(yi|yi-1, xi). The local model Pr(yi|yi-1, xi) is learned as follows. First one constructs an extended dataset, which is a collection of non-sequential examples of the form ((xi, yi-1), yi), where (xi, yi-1) denotes an instance in which the original feature vector for xi is augmented by adding a feature for yi-1. We will call (xi, yi-1) an extended instance, and call yi-1 a history feature. Note that yi is the class label for the extended example ((xi, yi-1), yi).

After constructing extended instances, one trains a maximum-entropy conditional model from the extended dataset. Inference is done by using a Viterbi search to find the best label sequence y.

MEMMs have a number of nice properties. Relative to the more recently-proposed CRF model, MEMMs are easy to implement, and (since no inference is done at learning time) relatively quick to train. MEMMs can also be easily generalized by replacing the local model with one that uses a longer "history" of k previous labels-i.e., a model of the form Pr(yi|yi-1, . . . , yi-k, xi)-and replacing the Viterbi search with a beam search. Such a learner scales well with the history size and number of possible classes y.

Unfortunately, as Table 1 shows, MEMMs perform extremely badly on the signature-detection problem, with an error rate many times the error rate of CRFs. In fact, on this problem, MEMMs perform much worse than the nonsequential maximum-entropy learner ME. 2

The MEMM's performance is better if one changes the threshold used to classify examples. Letting ˆ pi be the probability Pr(yi = +|xi, yi-1) as computed by MEMM, we found, for each learner, the threshold θ such the rule [(yi = +) ⇔ (ˆ pi > θ)] gives the lowest test error rate. The column labeled "Min Error" in Table 1 gives this "best possible" result. The "Min Error" for MEMMs is much improved, but still higher than non-sequential ME.

The high error occurs because on many test email messages, the learned MEMM makes a false positive classification somewhere before the signature starts, and then "gets stuck" and marks every subsequent line as part of a signature. This behavior is not consistent with previously-described limitations of MEMMs. It is known that MEMMs can represent only a proper subset of the distributions that can be represented by CRFs [Lafferty et al., 2001]; however, this "label bias problem" does not explain why MEMMs perform worse than non-sequential ME, since MEMMs clearly can represent strictly more distributions that ME.

2 We used the implementations of ME, MEMMs, and CRFs provided by Minorthird [Minorthird, 2004], with a limit of 50 optimization iterations. This limit does not substantially change the results.

Klein and Manning [2002] also describe an "observation bias problem", in which MEMMs give too little weight to the history features. However, in this case, relative to the weights assigned by a CRF, MEMM is seems to give too much weight to the history features. To verify this, we encouraged the MEMM to downweight the history features by adding noise to the training (not test) data: for each training email/sequence x, we consider each feature-vector xi ∈ x in turn, and with probability 0.10, we swap line xi (together with its label yi) with some other xj, yj chosen uniformly from the sequence. Adding this "sequence noise" almost doubles the error rate for CRFs, but reduces the error rate for MEMMs. (Of course, this type of noise does not affect nonsequential ME.) This experiment supports the hypothesis that MEMM is overweighting history features.

3 Stacked Sequential Learning

3.1 Description

The poor results for MEMM described above can be intuitively explained as a mismatch between the data used to train the local models Pr(yi|yi-1, x) of the MEMM, and the data used to test these models. With noise-free training data, it is always the case that a signature line is followed by more signature lines, so the MEMM's local model tends to weight the history feature yi-1 heavily. However, this strong regularity does not hold when the model is applied to test data in the course of executing the Viterbi algorithm, because then the local model is applied to extended examples (xi, ˆ yi-1), where ˆ yi-1 is a prediction made by the local model.

In theory, of course, this training/test mismatch is compensated for by the Viterbi search, which is in turn driven by the confidence estimates produced by the local model. However, if the assumptions of the theory are violated (for instance, if there are high-order interactions not accounted for by the maximum-entropy model), the local model's confidence estimates may be incorrect.

One way to correct the training/test mismatch is to modify the extended dataset that is used to train the local model so that the true previous class yi-1 in an extended instance (xi, yi-1) is replaced by a predicted previous class ˆ yi-1. Below we will outline a way to do this.

Assume that one is given a sample S = {(xt, yt)} of size m, and a sequential learning algorithm A. Previous work on a meta-learning method called stacking [Wolpert, 1992] suggests the following scheme for constructing a sample of (x, ˆy) pairs in which ˆy is a vector of "predicted" class-labels for x. First, partition S into K equal-sized disjoint subsets S1, . . . , SK, and learn K functions f1, . . . , fK, where

Stacked Sequential Learning.

Parameters: a history size Wh, a future size Wf , and a crossvalidation parameter K.

Learning algorithm: Given a sample S = {(xt, yt)}, and a sequential learning algorithmA:

1. Construct a sample of predictions ˆyt for each xt ∈ S as follows:
2. (a) Split S into K equal-sized disjoint subsets S1, . . . , SK

• (c) Let ˆ S = {(xt, ˆyt) : ˆyt = fj(xt) and xt ∈ Sj}
• Construct an extended dataset S′ of instances (x′t, yt) by converting each xt to x′t as follows: xt ′ = 〈x′1, . . . , x′ℓt 〉 where x′i = (xi, ˆ yi-Wh , . . . , ˆ yi+Wf ) and ˆ yi is the i-th component of ˆyt, the label vector paired with xt in ˆ S.
• Return two functions: f = A(S) and f ′ = A(S′ ).

Inference algorithm: given an instance vector x:

1. Let ˆy = f(x)
2. Carry out Step 2 above to produce an extended instance x′ (using ˆy in place of ˆyt).
3. Return f ′ (x′ ).

Table 2: The sequential stacking meta-learning algorithm.

fj = A(S -Sj). Then, construct the set

In other words, ˆ S pairs each xt with the ˆyt associated with performing a K-fold cross-validation on S. The intent of this method is that ˆy is similar to the prediction produced by an f learned by A on a size-m sample that does not include x.

This procedure is the basis of the meta-learning algorithm of Table 2. This method begins with a sample S and a sequential learning method A. In the discussion below we will assume that A is ME, used for sequential data.

Using S, A, and cross-validation techniques, one first pairs with each xt ∈ S the vector ˆyt associated with performing cross-validation with ME. These predictions are then used to create a dataset S′ of extended instances x′ , which in the simplest case, are simply vectors composed of instances of the form (xi, ˆ yi-1), where ˆ yi-1 is the (i -1)-th label in ˆy.

The extended examples S′ are then used to train a model f ′ = A(S′ ). If A is the non-sequential maximum-entropy learner, this step is similar to the process of building a "local model" for an MEMM: the difference is that the history features added to xi are derived not from the true history of xi, but are (approximations of) the off-sample predictions of an ME classifier.

At inference time, f ′ must be run on examples that have been extended by adding prediction features ˆ y. To keep the "test" distribution similar to the "training" distribution, f will not be used as the inner loop of a Viterbi or beam-search process; instead, the predictions ˆ y are produced using a nonsequential maximum-entropy model f that is learned from S. The algorithm of Table 2 simply generalizes this idea from ME to an arbitrary sequential learner, and from a specific history feature to a parameterized set of features.

In our experiments, we introduced one small but important refinement: each "history feature" ˆ y added to an extended example is not simply a predicted class, but a numeric value indicating the log-odds of that class. This makes accessible to f ′ the confidences previously used by the Viterbi search.

3.2 Initial results

We applied stacked sequential learning with ME as the base learner (henceforth s-ME) to the signature-detection dataset. We used K = 5, Wh = 1, and Wf = 0. The s-ME method obtains an error rate of 2.63% on the signature-detection task-less than the baseline ME method (3.20%) but still higher than CRFs (1.17%). However, certain extensions dramatically improve performance.

For s-ME, the only impact of more "history" features is to add new features to the extended instances; hence like MEMMs, s-ME can efficiently handle large histories. On the signature-detection task, increasing the history size to 11 reduces error (slightly) to 2.38%.

For s-ME, the extended instance for xi can include predicted classes not only of previous instances, but also of "future" instances-instances that follow xi in the sequence x. We explored different "window sizes" for s-ME, where a "window size" of W means that Wh = Wf = W, i.e., the W previous and W following predicted labels are added to each extended instance. A value of W = 20 reduces error rates to only 0.71%, a 46% reduction from CRF's error rate of 1.17%. This improvement is statistically significant. 3

Finally, stacked sequential learning can be applied to any learner-in particular, since the extended examples are sequential, it can be applied any sequential learner. We evaluated stacked sequential CRFs (henceforth s-CRFs) with varying window sizes on this problem. A value of W = 20 reduces error rates to 0.68%, a statistically significant improvement over CRFs. However, for moderately large window values, there was little performance difference between s-CRF and s-ME.

3.3 Discussion

A graphical view of a MEMMs is shown in Figure 1(a). We use the usual convention in which nodes for known values are shaded. Each node is associated with a maximum-entropy conditional model which defines a probability distribution given its input values.

Figure 1(b) presents a similar graphical view of the classifier learned by sequential stacking with Wh = 1 and Wf = 0. Inference in this model is done in two stages: first the middle layer is inferred from the bottom later, then the top layer is inferred from the middle layer. The nodes in the middle layer are partly shaded to indicate that their hybrid status-they are considered outputs by the model f, and inputs by the model f ′ .

3 A two-tailed paired t-test rejects with > 95% confidence the null hypothesis that the difference in error rate between s-ME and CRF on a randomly selected sequence x has a mean of zero.

One way to interpret the hybrid layer is as a means of making the inference more robust. If the middle-layer nodes were treated as ordinary unobserved variables, the top-layer conditional model (f ′ ) would rely heavily on the confidence assessments of the lower-layer model (f). Forcing f ′ treat these variables as observed quantities allows f ′ to develop its own model of how the ˆ y predictions made by f correlate with the actual outputs y. This allows f ′ to accept or downweight f's predictions, as appropriate. As suggested by the dotted line in the figure, stacking conceptually creates a "firewall" between f and f ′ , insulating f ′ from possible errors in confidence made by f .

Figure 1(c) shows a sequential stacking model with a window of Wh = Wf = 2. To simplify the figure, only the edges that eventually lead to the node Yi are shown.

To conclude our discussion, we note that as described, sequential stacking increases run-time of the base learning method by approximately a constant factor of K +2. (To see this, note sequential stacking requires training K + 2 classifiers: the classifiers f1, . . . , fK used in cross-validation, and the final classifiers f and f ′ .) When data is plentiful but training time is limited, it is also possible to simply split the original dataset S into two disjoint halves S1 and S2, and train two classifiers f and f ′ from S1 and S′2 respectively (where S′2 is S2, extended with the predictions produced by f). This scheme leaves training time approximately unchanged for a linear-time base learner, and decreases training time for any base learner that requires superlinear time.

4 Further Experimental Results

4.1 Additional segmentation tasks

We also evaluated non-sequential ME, MEMMs, CRFs, sME, and s-CRFs on several other sequential partitioning tasks. For stacking, we used K = 5 and a window size of Wh = Wf = 5 on all problems. These were the only parameter values explored in this section, and no changes were made to the sequential stacking algorithm, which was developed based on observations made from the signature-detection task only.

One set of tasks involved classifying lines from FAQ documents with labels like "header", "question", "answer", and "trailer". We used the features adopted by McCallum et al

[2000] and the three tasks (ai-general, ai-neural-nets, and aix) adopted by Dietterich et al [2004]. The data consists of 57 long sequences, each sequence corresponding to a single FAQ document; in total, each task contains between 8,965 and 12,757 labeled lines. Our current implementation of sequential stacking only supports binary labels, so we considered the two labels "trailer" (T) and "answer" (A) as separate tasks for each FAQ, leading to a total of six new benchmarks.

Another set of tasks were video segmentation tasks, in which the goal is to take a sequence of video "shots" (a sequence of adjacent frames taken from one camera) and classify them into categories such as "anchor", "news" and "weather". This dataset contains 12 sequences, each corresponding to a single video clip. There are a total of 418 shots, and about 700 features, which are produced by applying LDA to a 5x5, 125-bin RGB color histogram of the central frame of the shot. (This data was provided by Yik-Cheung Tam and Ming-yu Chen.) We constructed two separate video partitioning tasks, corresponding to the two most common labels.

All eight of these additional tasks are similar to the signature-detection task in that they contain long runs of identical labels, leading to strong regularities in constructed history features. Error rates for the learning methods on these eight tasks, in addition to the previous signature-detection task, are shown in Table 3. In each case a single train/test split was used to evaluate error rates. The bold-faced entries are the lowest error rate on a row.

We observe that MEMMs suffer extremely high error rates on two of the new tasks (finding "answer" lines for ai-general and ai-neural-nets), suggesting that the "anomalous" behavior shown in signature-detection may not be uncommon, at least in sequential partitioning tasks.

Also, comparing s-ME to ME, we see that s-ME improves the error rate in 8 of 9 tasks, and leaves it unchanged once. Furthermore, s-ME has a lower error rate than CRFs 7 of 9 times, and has the same error rate once. There is only one case in which MEMMs have a lower error rate than s-ME.

Overall, s-ME seems to be preferable to either of three older approaches (ME, MEMMs, and CRFS). This is made somewhat more apparent by the scatter plot of Figure 2. On this plot, each point is placed so the y-axis position is the error of s-ME, and the x-axis position is the error of an earlier learner; thus points below the line y = x are cases where sME outperforms another learner. (For readability, the range of the x axis is truncated-it does not include the highest error rates of MEMM.)

Stacking also improves CRF on some problems, but the effect is not as consistent: s-CRF improves the error rate on 5 of 9 tasks, leaves it unchanged twice, and increases the error rate twice. In the table, one of the two stacked learners has the lowest error rate on 8 of the 9 tasks.

Applying a one-tailed sign test, the improvement of s-ME relative to ME is statistically significant (p > 0.98), but the improvement of s-CRF relative to CRF is statistically not (p > 0.92). The sign test does not consider the amounts by which error rates are changed, however. From the figures and tables, it is clear that error rates are often lowered substantially, and only once raised by more than a very small proportion (for the "A/aix" benchmark with CRFs).

4.2 A sequence classification task

As a final test, we explored one additional non-trivial task: classifying popular songs by emotion. This task was considered after all code development was complete, and hence is a completely prospective test of sequential stacking. A collection of 201 popular songs was annotated by two students on a five-point scale: "very happy"(5), "happy"(4), "neutral"(3), "sad"(2) and "very sad"(1). The Pearson's correlation [Walpole et al., 1998] was used as a measure of interannotator agreement. The Pearson's correlation coefficient ranges from -1 (perfect disagreement) to +1 (perfect agreement),and the inter-annotator agreement between the two students was 0.643.

To learn a song classifier, we represented each song as a sequence of 1-second long "frames", each frame being labeled with the emotion for the song that contains it. We then learned sequence classifiers from these labeled sequences. To classify an unknown song, we used the sequence classifier to label the frames for the song, and finally labeled the song with the most frequent predicted frame label.

The "frames" are produced by extracting certain numerical properties from a waveform representation of the song every 20ms, and then averaging over 1-second intervals. Each 1second frame has as features the mean and standard deviation of each property. The numerical properties were computed using the Marsyas toolkit [Tzanetakis and Cook, 2000], and are based on the short-time Fourier transform, tonality, and Cepstral coefficients.

The music dataset contains 52,188 frames from the 201 songs, with 130 features for each frame. We looked at two versions of the problem: predicting all of the five labels (music5), and predicting only "happy" versus "sad" labels (music2). Preliminary experiments suggested that large windows were effective, thus we used the following parameters in the experiments: K = 2 and a window size of Wh = Wf = 25 on music5 problem, and K = 5 and Wh = Wf = 25 on music2.

The results are summarized in Table 4. Both s-CRF and s-ME outperform their non-stacking counterparts, and s-ME outperforms CRFs. Furthermore, s-CRF improves substantially over unstacked CRFs on the two-class problem, reducing the error rate by more than 27%.

5 Conclusions

Sequential partitioning tasks are sequential classification tasks characterized by long runs of identical labels: examples of these tasks include document analysis, video segmentation, and gene finding. In this paper, we have evaluated the performance of certain well-studied sequential probabilistic learners to sequential partitioning tasks. It was observed that MEMMs sometimes obtain extremely high error rates. Error analysis suggests that this problem is neither due to "label bias" [Lafferty et al., 2001] nor "observation bias" [Klein and Manning, 2002], but to a mismatch between the data used to train the MEMM's local model, and the data on which the MEMM's local model is tested. In particular, since MEMMs are trained on "true" labels and tested on "predicted" labels, the strong correlations between adjacent labels associated sequential partitioning tasks can be misleading to the MEMM's learning method.

Motivated by these issues, we derived a novel method in which cross-validation is used correct this mismatch. The end result is a meta-learning scheme called stacked sequential learning. Sequential stacking is simple to implement, can be applied to virtually any base learner, and imposes an constant overhead in learning time (the constant being the number of cross-validation folds plus two). In experiments on several partitioning tasks, sequential stacking consistently improves the performance of two non-sequential base learners, often dramatically. On our set of benchmark problems, sequential stacking with a maximum-entropy learner as the base learner outperforms CRFs 7 of 9 times, and ties once. Also, on a prospective test conducted on a completely new task, sequential stacking improves the performance of both CRFs and maximum-entropy learners, leading in one case to a 27% reduction in error over conventional CRFs.

One of the more surprising results (for us) is that sequential stacking also often improves performance of conditional random fields, a learner specifically designed for sequential tasks. In a longer version of this paper, we conducted similar with two margin-based base learners: the non-sequential voted perceptron algorithm (VP)[Freund and Schapire, 1998] and a voted-perceptron based training scheme for HMMs proposed by Collins (VPHMMs) [Collins, 2002], with qualitatively similar results.

Some initial experiments on a named entity recognition problem suggest that sequential stacking does not improve performance on non-partitioning problems; however, in future work, we plan to explore this issue with more detailed experimentation.

Acknowledgements

The authors wish to thank many friends and colleagues for input, in particular David McAllister. We are also grateful to Yik-Cheung Tam and Ming-yu Chen for providing the videosegmentation data, and to Chih-yu Chao for the popular music dataset labels. This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA). Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the Defense Advanced Research Projects Agency, or the Department of Interior-National Business Center.