Latent Variable Perceptron Algorithm for Structured Classification

1 Introduction

Real-world problems may contain latent dependencies (i.e., hidden sub-structures) that are difficult to be captured by conventional models for structured classification, such as conditional random fields (CRFs). In such cases, models that exploit latent variables are advantageous in learning [Petrov and Klein, 2008]. As a result, recently discriminative probabilistic latent variable models (DPLVMs) have become popular for performing a variety of tasks with latent dependencies, e.g., vision recognition [Morency et al., 2007], syntactic parsing [Petrov and Klein, 2008], and syntactic chunking [Sun et al., 2008].

Morency et al. [2007] demonstrated that DPLVMmodels can learn latent dependencies of natural problems efficiently, and outperform several widely-used conventional models, such as support vector machines (SVMs), conditional random fields and hidden Markov models (HMMs). Petrov and Klein [2008] reported on a syntactic parsing task that DPLVM models can learn more compact and accurate grammars than that of the conventional techniques without latent variables.

However, experimental results in Petrov et al. [2008] have highlighted both time and memory cost problems on training. They used 8 CPUs in parallel for 3 days to train the weighted grammars with latent variables. And because of the memory limitations, their solution fails to learn more complex grammars. Furthermore, our experiments on the named entity recognition (NER) task confirmed that the training of DPLVMs with a low Markov order is already computationally expensive on large scale problems. On a corpus of 10K sentences, the training took more than a week for a linear chain model with latent variables.

On the other hand, the perceptron algorithms (including voted or averaged version) [Rosenblatt, 1958; LeCun et al., 2006] have been shown to be competitive to the modern learning algorithms on structured classification tasks, while their computational costs are much lower [Freund and Schapire, 1999; Collins, 2002]. However, it is still not clear how to apply the perceptron algorithms for the learning task with latent dependencies.

In this paper we propose a novel latent variable perceptron algorithm (latent perceptron below) as an alternative to the DPLVMs. We will show that the latent perceptron gives comparable or even superior performance than the DPLVMs, while it is significantly faster, making it amenable to large scale problems.

2 ProblemDefinition and Background

In practice, given a limited training data, the relationship between specific observations and their contexts may be best modeled at a level finer than explicit class labels but coarser than direct token observations.

For example, in the noun phrase (NP) chunking task, suppose that there are two lexical sequences, "He is her -" and "He gave her -". They would both be conventionally labeled as 'BOB', where B signifies the 'beginning NP', and O 'outside NP'. However, this labeling is too general to encapsulate their respective syntactic dependencies, which is crucial for labeling the next word. For "He is her -", the NP started by 'her' is still incomplete, so the label for '-' is likely to be I, which signifies the continuation of the phrase, e.g., "[He] is [her brother]". In contrast, for "He gave her -", the phrase started by 'her' is normally self-complete and makes the next label more likely to be B, e.g., "[He] gave [her] [flowers]". We expect better performance if the model is able to represent the 'latent' fact, that in the first case, 'her' is most likely the possesive pronoun, while in the second case, it is probably the indirect object pronoun.

Following this example, we give a more formal definition of the problem. The task is to learn a mapping between a sequence of observations x = x1, x2, . . . , xm and a sequence of labels y = y1, y2, . . . , ym. Each yj is a class label for the j'th token of a observation sequence and is a member of a label set, Y . For each sequence, we also assume a vector of latent variables h = h1, h2, . . . , hm, which is not observable. To keep the training efficient, we restrict the model to have a disjointed set of latent variables associated with each class label; Each hj is a member of a set, Hyj , which represents the possible latent variables for the class label yj.

Following the problem definition described above, DPLVMs are defined as [Morency et al., 2007; Petrov and Klein, 2008]:

where Θ represents the parameters of the model. Since sequences with hj /∈ Hyj will have P(y|x,Θ) = 0 by the restriction of disjointed association, the model can be further defined as [Morency et al., 2007; Petrov and Klein, 2008]:

where P(h|x,Θ) is defined using the usual conditional random field formulation:

in which f(h, x) is the global feature vector. Given training sequences (xi, y∗ i ) for i = 1 . . . d, training is performed by optimizing the likelihood of the training data, usually with a regularization of R(Θ):

3 Latent Variable Perceptron

Based on the above problem definition, now we present an alternative model for DPLVMs. We define the score of a label sequence F(y|x,Θ) as the maximum score among its latent sequence:

where Proj(h) is the projection from a latent sequence h to a label sequence y:

and F(h|x,Θ) is the score of a latent sequence:

where the k'th value of the global feature vector, fk(h, x), can be represented as a sum of the local edge features, t(hj-1, hj , x′ ), or local state features, s(hj, x′ ), in which x′ reprents the context, i.e., the local observations. It is common (e.g., see [Collins, 2002]) for each feature to be an indicator function. For example, one such feature might be Input: example xi with gold standard label sequence y∗ i , weight vector Θ, and feature vector f(y, x)

Initialization: set parameters Θ1 = 0

Output: parameter vectors Θi+1 for i = 1 . . . d

Input: xi with y∗ i , weight vector Θ, and feature vector f (y, x)

Initialization: randomly initialize parameters under the condition ||Θ1 || ≈ 0

for i = 1 . . . d do hi = argmaxhF(h|xi,Θi ) yi = Proj(hi) if yi ̸= y∗ i then h∗i = argmaxhF(h|y∗ i , xi,Θi ) Θi+1 = Θi + f (h∗i , xi) - f (hi , xi) elseΘi+1 = Θi Output: parameter vectors Θi+1 for i = 1 . . . d

"s(hj , x′ ) = 1 (if current context x′ is the word the) or 0 (otherwise)". In this paper, we also use indicator features.

The latent perceptron attempts to minimize the difference between the score of the goal feature vector for a training instance (xi, y∗ i ) and the score of current feature vector of the best latent sequence, with the following update formula:

where argmaxh F (h|y∗ i , xi,Θi ) is the Viterbi path of the latent sequences under the constraint of gold standard label sequence, and argmaxh F(h|xi,Θi ) is the current best latent sequence.

3.1 LearningModel Parameters

First, to make a comparison, we review the training of DPLVMs. Fitting the DPLVMs involves the normalizer, ∑∀h expΘ · f(h|x), and the marginalization over latent sequences for corresponding label sequence, ∑h∈Hy1 ×...×Hym P(h|x,Θ). Both of them are computationally expensive. In addition, if to adopt a Quasi-Newton optimizer as most DPLVMs did, it requires computing the derivatives ∂L(Θ)/∂Θ, which is also computationally expensive.

Compared to DPLVMs, training the latent perceptron is much more efficient. It avoids computing the normalizer, the marginalization operation and the derivatives during optimization. The major cost of the latent perceptron is from the computation of the best latent path by using the Viterbi algorithm.

The latent perceptron training algorithm is shown in Figure 1, with a comparison to the training of the perceptron. The parameters are initialized randomly. Each sentence in turn is decoded using the current parameter settings. If the latent path with the highest score under the current model is incorrect, then the parameter vector Θ is updated in a simple additive fashion.

A Modified Estimation Method for Latent Perceptron

There is a refinement to the algorithm in Figure 1 , called the 'averaged parameters' method. Define Θq, i as the values of parameters after the i'th training example has been processed in pass q over the training data. The averaged parameters are then defined as γQ,d = ∑q=1...Q, i=1...d Θq, i/dQ [Freund and Schapire, 1999].

However, we found this refinement is not adequate for the latent perceptron. Naturally, one possible way to further control the overfitting is to 'decay' the new parameters by using the averaged parameters. Following this idea, we propose a modified averaged parameters algorithm for training the latent perceptron: instead of using Θq, start = Θq-1, end , we re-initiate the parameters of the new iteration with the averaged parameters in each k iteration, i.e., Θq, start = γ q-1, end when q%k = 0. Here, % represents the mod operation. Selecting a proper value of k is important for the performance, and this can be done by using a development data set. We normally choose the value of k within the range of [2,8], depending on the specific task.

Although this modification does not improve the performance of the perceptron, it reduces the overfitting of the latent perceptron and improves its performance. Therefore, we use this modified estimation method for training the latent perceptron.

3.2 Convergence Analysis

We now give theorems regarding the convergence of the latent perceptron. We will prove that a separable data will remain separable with a bound. Moreover, after a finite number of updates, the latent perceptron is guaranteed to converge to the parameter values with zero training error. Furthermore, as for the data which is not separable, we will derive a bound on the number of updates in the latent perceptron.

To facilitate the discussion, we will refer to a problem as separable with the following definition:

Definition 1. Let G(xi) signify all possible label sequences for an example xi; Let G(xi) = G(xi) - {y∗ i }. We will say that a training sequence (xi, y∗ i ) for i = 1 . . . d is separable with margin δ > 0 if there exists some vector U with ||U|| = 1 such that 1

Also, a latently separable problem is defined as following:

Definition 2. Let GH(xi) signify all possible candidates of latent sequence for an example xi, we then define GH∗ (xi) = {h|Proj(h) = y∗ i }, and GH(xi) = GH(xi)- GH∗ (xi). In other words, GH∗ (xi) represents the correct latent candidates for xi, and GH(xi) represents the incorrect ones. Then a training sequence (xi, y∗ i ) for i = 1 . . . d is latently separable with margin δ > 0 if there exists some vector U with ||U|| = 1 such that

1 ||U|| is the 2-norm of U, i.e., ||U|| = pPk U2k .

By using latent variables, a local state feature in the perceptron, s(y, x′ ), will be mapped into a new feature set, {s(hi, x′ )} for all possible hi ∈ Hy, with the dimension mk = |Hy|. 2 Similar mapping can be also extended to local edge features. 3 Since a global feature vector consists of local features, we use mk to denote the 'dimension augmentation' of the k'th feature of the original feature vector, fk(y, x), then we get a vector m = (m1, . . . ,mn) so that a global feature vector, f(y, xi) = (β1, . . . , βn), will be mapped into a new feature vector with latent variables, f (h, xi) = (β1 1 , . . . , βm1 1 , . . . , β1n, . . . , βmn n ).

Based on the mapping, it is straightforward to prove that βk = ∑mk i=1 βik for k = 1 . . . n. Since mk is only related to |Hy| for all possible y from fk(y, x) and Hy is fixed before the training, mk will be an integral constant. We then define the latent feature mapping as the vector m = (m1, . . . , mn), and we can state the following theorems:

Theorem 1. Given the latent feature mapping m = (m1, . . . ,mn), for any sequence of training examples (xi , y∗ i ) which is separable with margin δ by a vector U represented by (α1, . . . , αn) with ∑ni=1 αi 2 = 1, the examples then will also be latently separable with margin δ, and δ is bounded below by

The proof is sketched in Appendix.

Theorem 2. For any sequence of training examples (xi, y∗ i ) which is separable with margin δ, the number of mistakes of the latent perceptron algorithm in Figure 1 is bounded above by

where T is as before, and M is the maximum 2-norm of an original feature vector, i.e., M = maxi ||f(y, xi)||.

The proof is sketched in Appendix.

In the case of inseparable data, we need the following definition:

Definition 3. Given a sequence (xi, y∗ i ), for a U, δ pair, define gi = minh∈GH∗ (xi) U · f (h, xi) - maxz∈GH(xi) U · f(z, xi). Then, define DU,δ as the least obtainable error:

2 See Section 2 for Hy; |set| means the number of elements of the set.

3 The only difference for the mapping is that an edge feature consists of more than one labels.

Hence we can further have the following theorem:

Theorem 3. For any training sequence (xi, y∗ i ), the number of mistakes made by the latent perceptron training algorithm is bounded above by

where M is as before.

The proof can be adapted from Freund and Shapire [1999] and Collins [2002].

4 Experiments on Synthetic Data

In this section we use synthetic data to demonstrate that the latent perceptron is able to address problems containing latent dependencies, which cannot be solved by conventional models.

The synthetic datasets are generated by the HMM model. The labels are {y1, y2}; the latent variables are {h1, h2, h3, h4}, with the association Hy1 = {h1, h2} and Hy2 = {h3, h4}; the observable tokens are {x1, x2}. We vary the significance of the latent dependencies to make comparisons. The latent dependencies are illustrated in Figure 2. P represents the transition probability P(hj|hi). A large value of P indicates a strong dependency (the remaining prob. mass '1-P' is uniformly distributed to the remaining transitions). x1 and x2 are generated with P(x1|hi) and P(x2|hi), but since this is not the focus, we set them to be very weakly dependent. Therefore, one artificial label sequence could be like 'y1, y1, y2, y2, y1, . . .', while the observable tokens will appear like a random sequence. The artificial label sequences are observable as gold standards during training but not observable during test. The latent variable sequences are unobservable in both training and test.

We varied the probability P and therefore generated a variety of synthetic data with latent dependencies. All the models employ similar feature templates: node features {xi} × {yi} with edge features {yi-1yi} for conventional models, and node features {xi}×{hi} with edge features {hi-1hi} for latent models; therefore only the 1st order dependencies among labels or latent variables are considered. We use the label accuracy to measure the performance.

As can be seen in Figure 3, the latent perceptron and DPLVMs 4 outperform conventional models like CRFs, and the gap increases rapidly when the latent dependencies are significant. When P is 0.9, the accuracy of the latent perceptron and DPLVMs are both 84.9%, in contrast to CRFs'

4 Since the batch-training performs better than stochastic-training for DPLVMs (see next section), we adopts the batch-training here.

63.4% and the perceptron's 57.3%. In most cases, latent perceptron performs as well as DPLVMs, as can be seen from their almost identical curves. We also found that, by using more latent variables than necessary (e.g., 4 latent variables for each label), both the latent perceptron and DPLVMs kept roughly the same accuracies.

Note that, in the previous section, we have proved the convergence in the worst case, by using a very strict definition of latent separability. Clearly there are many 'separable' cases under the latent perceptron that do not satisfy this strict definition.

Here, we relax the 'separation' under the latent perceptron as follows: maxh∈GH∗ (xi) Θ′ · f (h, xi ) > maxz∈GH(xi) Θ′ · f(z, xi) for i = 1 . . . d. Then, there are many cases that an originally inseparable instance (under the perceptron) become 'separable' by involving latent variables. For example, with P = 0.9, among the 3,000 training instances of this data, we found that less than 10% instances were separable when use the perceptron (trained with enough iterations), i.e., Θ · f (y∗ i , xi) > Θ · maxz∈G(xi) f(z, xi), while the separable instances increased to more than 40% when use the latent perceptron, i.e., maxh∈GH∗ (xi) Θ′ · f (h, xi) > maxz∈GH(xi) Θ′ · f (z, xi ).

5 Experiments on Real-World Tasks

In this section we perform experiments on two real-world tasks, biomedical named entity recognition and noun phrase chunking. As the baseline systems, we implemented DPLVMs and CRFs by extending the HCRF library developed by Morency et al. [2007]. We added a popular batchtraining optimizer, the Limited-Memory BFGS algorithm (LBFGS) [Nocedal and Wright, 1999]. For higher efficiency, we also implemented the stochastic gradient descent algorithm (SGD) [Bottou, 1998]. To reduce overfitting, we employed a Gaussian prior. We varied the the variance of the Gaussian prior (with values 10k , k from -3 to 3), and we found that σ2 = 1.0 was optimal for both DPLVMs and CRFs on the development data and used it throughout the experi-

Word Features: {wi-2, wi-1, wi, wi+1, wi+2, wi-1wi, wiwi+1} ×{hi, hi-1hi, hi-2hi-1hi} POS Features: {ti-2, ti-1, ti, ti+1, ti+2, ti-2ti-1, ti-1ti, titi+1, ti+1ti+2, ti-2ti-1ti, ti-1titi+1, titi+1ti+2} ×{hi, hi-1hi, hi-2hi-1hi} Orth. Features: {oi-2, oi-1, oi, oi+1, oi+2, oi-2oi-1, oi-1oi, oioi+1, oi+1oi+2} ×{hi, hi-1hi, hi-2hi-1hi}

ments in this section.

5.1 BioNLP/NLPBA-2004 Shared Task (Bio-NER)

A large amount of training data is available for the Bio-NER task, which are appropriate to be used for testing the scalability of the models. Named entity recognition aims to identify and classify technical terms in a given domain. The bio-NER task is for recognizing 5 kinds of biomedical named-entities on the GENIA corpus [Kim et al., 2004]. The typical approach to this problem recast it as a sequential labeling task with the BIO encoding. The data consists of 1,800 abstracts (fromMEDLINE) for training, 200 abstracts for the development data, and 404 abstracts for testing. The standard evaluation metrics [Kim et al., 2004] are precision p, recall r, and the F-measure given by F = 2pr/(p + r).

We use word features, POS features and orthography features (prefix, uppercase/lowercase, etc.), as listed in Table 1. For both the latent perceptron and DPLVMs, we varied the number of latent variables per label from 2 to 8 on our preliminary experiments, and we finally use 4. The latent perceptron adopts the modified averaged parameter training (see comparisons in next subsection), and the perceptron adopts the original one.

As can be seen in Table 2, we performed 4 sets of experiments by scaling the models from simple to complex 5 . Cc=n means only features occurring n times or more are included. When cc=15, the training speed 6 of the latent perceptron is 130 times faster than that of the DPLVMs with batch-training (L-BFGS). The latent perceptron performs almost as well as DPLVM-BFGS, and outperforms DPLVM-SGD and other models. When more features were added by setting cc=5, DPLVMs with batch-training became intractable, while the latent perceptron still worked efficiently and achieved much better performance than the DPLVM-SGD, by reducing over 7.0% errors. It also outperformed the CRFs and the perceptron with statistically significant differences (McNemar's significance test).

When cc=2, CRFs also became intractable. When the 2nd order dependencies were further added, even the stochastictraining became intractable for DPLVMs. On the other hand, the latent perceptron worked efficiently, with further error reductions.

Overall, with the same feature set, the latent perceptron demonstrates consistent superiority over the DPLVM-SGD model and the perceptron. Compared to a straightforward high order perceptron, one advantage of the latent perceptron comes from its use of latent variables to adaptively learn long range dependencies. With the F-measure of 70.51%, the latent perceptron achieved a comparable performance to the state-of-the-art systems, and it would be further improved when enhanced with external features or resources, as is done in other systems. The state-of-the-art systems is Okanohara et al. [2006] (71.4%), who used a semi-Markov CRF model with specifically designed global features. Whereas in our latent perceptron model, we did not use such global features. Finkel et al. [2004] (70.0%) used a maximum entropy Markov model with external resources like web-querying. Settles [2004] (69.8%) used a CRF model with additional semantic knowledge.

5.2 Noun Phrase Chunking Task (NP-Chunking)

We choose the NP-chunking task [Sang and Buchholz, 2000] because it is a popular benchmark for testing a structured classification model. In this task, the non-recursive cores of noun phrases called base NPs are identified. The training set consists of 8,936 sentences, and the test set consists of 2,012 sentences. We use features that depend on words and POS tags (see Table 3), and our preliminary experiments in this task suggested the use of 5 latent variables for each label.

In this experiment, our main purpose is to compare the traditional parameter averaging technique with our modified version. However, we also showed the performance of other models for reference.

5 The major feature templates are similar.

6 On Intel Dual-Core Xeon 5160/3GHz CPU, excluding time for feature generation and data input/output.

Word Features: {wi-2, wi-1, wi, wi+1, wi+2, wi-1wi, wiwi+1} ×{hi, hi-1hi, hi-2hi-1hi} POS Features: {ti-1, ti, ti+1, ti-2ti-1, ti-1ti, titi+1, ti+1ti+2, ti-2ti-1ti, ti-1titi+1, titi+1ti+2} ×{hi, hi-1hi, hi-2hi-1hi}

As can be seen in Table 4, the latent perceptron with modified averaged parameter training (mavg) achieves the best performance, which is significantly better than the same model trained by the traditional parameter averaging (avg). Compared with the avg, we also observed that the mavg training (on the latent perceptron) reached an empirically more stable convergent plateau. For example, further training with the mavg for 200 iterations following the beginning of the plateau, the fluctuation of its F-measure was bounded by ±0.1%, while for the avg training, it reached ±0.8%. The latent perceptron with mavg training also outperformed the DPLVM model with stochastic training. As for the perceptron, we did not observe significant difference between the training of mavg and avg. In this simple task, based on a 2ndorder dependency and a rich feature set, we observed that the superiority of the latent perceptron over other models is not very significant.

Finally, with the F-measure of 94.37%, the performance of the latent perceptron is one of the best reports on this data. The state-of-the-art systems include Sha & Pereira [2003] (94.38% by a 2nd order CRF model) and Kudo & Matsumoto [2001] (94.22% by the combination of multiple SVM models).

6 Conclusions

We proposed the latent variable perceptron algorithm to learn latent dependencies, and analyzed its convergence properties. We showed that simply using averaged parameter training on latent perceptron is not good enough. To address this problem, we proposed the modified averaged parameter training. Compared to existing probabilistic models of latent variables, our method lowers the training cost significantly yet with comparable or even superior classification accuracy. Although we only focused on the sequential labeling tasks in this paper, the theoretical framework and algorithm should also be applicable to a wide variety of models beyond linearchain structure.

Acknowledgments

We thank Xia Zhou and Galen Andrew for good suggestions on improving the paper-writing. We also thank the anonymous reviewers who gave very helpful comments.

Appendix: Proof of Convergence 7

Proof of theorem 1. Given the latent feature mapping m = (m1, . . . ,mn) and U ∈ Rn represented by (α1, . . . , αn), there exist a U ∈ RN with N = ∑ni=1 mi represented as follows: ( m1 ︷ ︸︸ ︷ α1, . . . , α1, m2 ︷ ︸︸ ︷ α2, . . . , α2, . . . , mn ︷ ︸︸ ︷ αn, . . . , αn). Then ∀i, ∀h ∈ GH∗ (xi), ∀z ∈ GH(xi),

where βk∗ j ∈ f(h, xi) is the k'th feature value mapped from β∗ j ∈ f(y∗ i , xi) by using latent variables; similarly, βk j ∈ f(z, xi) is mapped from βj ∈ f(yz , xi); yz is the label sequence projected from the latent sequence z.

Let T = ||U|| = (∑ni=1 miαi 2 )1/2 , then it can be seen that the vector U/||U|| latently separates the data with margin δ/T .

Proof of theorem 2. Let Θk be the parameters before the k'th mistake is made, and suppose it is made at the i'th example. Let z be the output proposed at this example, z = argmaxh∈GH(xi) f(h, xi) · Θk . Also, let h∗i = argmaxh∈GH∗ (xi)f (h, xi ) · Θk . Then, by using theorem 1 and adapting Collins [2002] for the lower bound of ||Θk+1 ||, we can derive that

We also derive an upper bound for ||Θk+1 ||2 . First, we have

7 For a more detailed version of the proof, see Sun [2009].

Since Θk · [f(h∗i , xi) - f(z, xi)] < 0 (because of the update rule) and f(h∗i , xi) · f(z, xi) ≥ 0 (because of indicator features), it follows that

Then, it follows that ||Θk+1 ||2 ≤ 2kM 2 .

Combining the upper bound and lower bound completes the proof.