{'fraction_non_alphanumeric': 0.03358940830336711, 'fraction_numerical': 0.008826413860738803, 'mean_word_length': 4.966357874207704, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Constraint-Driven Rank-Based Learning for Information Extraction

Most learning algorithms for undirected graphical models require complete inference over at least one instance before parameter updates can be made. SampleRank is a rank-based learning framework that alleviates this problem by updating the parameters during inference. Most semi-supervised learning algorithms also perform full inference on at least one instance before each parameter update. We extend SampleRank to semi-supervised learning in order to circumvent this computational bottleneck. Different approaches to incorporate unlabeled data and prior knowledge into this framework are explored. When evaluated on a standard information extraction dataset, our method significantly outperforms the supervised method, and matches results of a competing state-of-the-art semi-supervised learning approach.


Introduction
Most supervised learning algorithms for undirected graphical models require full inference over the dataset (e.g., gradient descent), small subsets of the dataset (e.g., stochastic gradient descent), or at least a single instance (e.g., perceptron, Collins (2002)) before parameter updates are made. Often this is the main computational bottleneck during training.
SampleRank (Wick et al., 2009) is a rank-based learning framework that alleviates this problem by performing parameter updates within inference. Every pair of samples generated during inference is ranked according to the model and the ground truth, and the parameters are updated when the rankings disagree. SampleRank has enabled efficient learn-ing for massive information extraction tasks (Culotta et al., 2007;. The problem of requiring a complete inference iteration before parameters are updated also exists in the semi-supervised learning scenario. Here the situation is often considerably worse since inference has to be applied to potentially very large unlabeled datasets. Most semi-supervised learning algorithms rely on marginals (GE, Mann and McCallum, 2008) or MAP assignments (CODL, Chang et al., 2007). Calculating these is computationally inexpensive for many simple tasks (such as classification and regression). However, marginal and MAP inference tends to be expensive for complex structured prediction models (such as the joint information extraction models of ), making semisupervised learning intractable.
In this work we employ a fast rank-based learning algorithm for semi-supervised learning to circumvent the inference bottleneck. The ranking function is extended to capture both the preference expressed by the labeled data, and the preference of the domain expert when the labels are not available. This allows us to perform SampleRank as is, without sacrificing its scalability, which is crucial for future large scale applications of semi-supervised learning.
We applied our method to a standard information extraction dataset used for semi-supervised learning. Empirically we demonstrate improvements over the supervised model, and closely match the results of a competing state-of-the-art semi-supervised learner.

Background
Conditional random fields (Lafferty et al., 2001) are undirected graphical models represented as factor graphs. A factor graph G = {Ψ i } defines a probability distribution over assignments y to a set of output variables, conditioned on an observation x. A factor Ψ i computes the inner product between the vector of sufficient statistics f (x i , y i ) and parameters Θ. Let Z(x) be the data-dependent partition function used for normalization. The probability distribution defined by the graph is:

Rank-Based Learning
SampleRank (Wick et al., 2009) is a rank-based learning framework for that performs parameter updates within MCMC inference. Every pair of consecutive samples in the MCMC chain is ranked according to the model and the ground truth, and the parameters are updated when the rankings disagree. This allows the learner to acquire more supervision per sample, and has led to efficient training of models for which inference is very expensive .
SampleRank considers two ranking functions: (1) the unnormalized conditional probability (model ranking), and (2) a truth function F(y) (objective ranking) which is defined as −L(y, y L ), the negative loss between the possible assignment y and the true assignment y L . The truth function can take different forms, such as tokenwise accuracy or F1measure with respect to some labeled data.
In order to learn the parameters for which model rankings are consistent with objective rankings, SampleRank performs the following update for each consecutive pair of samples y a and y b of the MCMC chain. Let α be the learning rate, and , then Θ is updated as follows: This update is usually fast: in order to calculate the required model ratio, only factors that touch changed variables have to be taken into account. SampleRank has been incorporated into the FAC-TORIE toolkit for probabilistic programming with imperatively-defined factor graphs ).

Semi-Supervised Rank-Based Learning
To apply SampleRank to the semi-supervised setting, we need to specify the truth function F over both labeled and unlabeled data. For labeled data Y L , we can use the true labels. These are not available for unlabeled data Y U , and we present alternative ways of defining a truth function F U : Y U → for this case.

Self-Training
Self-training, which uses predictions as truth, fits directly into our SampleRank framework. After performing SampleRank on training data (using F L ), MAP inference is performed on the unlabeled data. The predictionŷ U is used as the ground truth for the unlabeled data. Thus the self-training objective function F s over the unlabeled data can be defined as F s (y) = −L(y,ŷ U ).

Encoding Constraints
Constraint-driven semi-supervised learning uses constraints to incorporate external domain knowledge when labels are missing (Chang et al., 2007;Mann and McCallum, 2008;Bellare et al., 2009). Constraints prefer certain label configurations over others. For example, one constraint may be that occurrences of the word "California" are preferred to have the label "location".
We can encode constraints directly into the objective function F U . Let a constraint i be specified as p i , c i , where c i (y) denotes whether assignment y satisfies the constraint i (+1), violates it (−1), or the constraint does not apply (0), and p i is the constraint strength. Then the objective function is:

Incorporating Model Predictions
When the objective function F c is used, every prediction on unlabeled data is ranked only according to the constraints, and thus the model is trained to satisfy all the constraints. This is a problem when the constraints prefer a wrong solution while the model favors the correct solution, resulting in SampleRank updating the model away from the true solution. To avoid this, the ranking function needs to balance preferences of the constraints and the current model.
One option is to incorporate the self-training objective function F s . A new objective function that combines self-training with constraints can be defined as: This objective function has at least two limitations. First, self-training involves a complete inference step to obtainŷ U . Second, the model might have low confidence in its prediction (this is the case when the underlying marginals are almost uniform), but the self-training objective des not take this into account. Hence, we also propose an objective function that incorporates the model score directly, i.e.
This objective does not require inference, and also takes into account model confidence.
In both objective functions F sc and F mc , λ controls the relative contribution of the constraint preferences to the objective function. With higher λ, SampleRank will make updates that never try to violate constraints, while with low λ, SampleRank trusts the model more. λ corresponds to constraint satisfaction weights ρ used in (Chang et al., 2007).

Related Work
Chang et al.
propose constraint-driven learning (CODL, Chang et al., 2007) which can be interpreted as a variation of self-training: Instances are selected for supervision based not only on the model's prediction, but also on their consistency with a set of user-defined constraints. By directly incorporating the model score and the constraints (as in F mc in Section 3.3) we follow the same approach, but avoid the expensive "Top-K" inference step.
Generalized expectation criterion (GE, Mann and McCallum, 2008) and Alternating Projections (AP, Bellare et al., 2009) encode preferences by specifying constraints on feature expectations, which require expensive inference. Although AP can use online training, it still involves full inference over each instance. Furthermore, these methods only support constraints that factorize according to the model. Li (2009) incorporates prior knowledge into conditional random fields as variables. They require full inference during learning, restricting the application to simple models. Furthermore, higher-order constraints are specified using large cliques in the graph, which slow down inference. Our approach directly incorporates these constraints into the ranking function, with no impact on inference time.

Experiments
We carried out experiments on the Cora citation dataset. The task is to segment each citation into different fields, such as "author" and "title". We use 300 instances as training data, 100 instances as development data, and 100 instances as test data. Some instances from the training data are selected as labeled instances, and the remaining data (including development) as unlabeled. We use the same tokenlabel constraints as Chang et al. (2007).
We use the objective functions defined in Section 3, specifically self-training (Self:F s ), direct constraints (Cons:F c ), the combination of the two (Self+Cons:F sc ), and combination of the model score and the constraints (Model+Cons:F mc ). We set p i = 1.0, α = 1.0, λ s = 10, and λ m = 0.0001.
Average token accuracy for 5 runs is reported and compared with CODL 1 in Table 1. We also report supervised results from (Chang et al., 2007) and SampleRank. All of our methods show vast improvement over the supervised method for smaller training sizes, but this difference decreases as the training size increases. When the complete training data is used, additional unlabeled data hurts our performance. This is not observed in CODL since they use more unlabeled data, which may also explain their slightly higher accuracy. Note that Self+Cons performs better than Self or Cons individually.
Model+Cons also performs competitively, and may potentially outperform other methods if a better λ m is chosen. Note, however, that λ m is much harder to tune than λ s since λ m weighs the contribution of the unnormalized model score, the range  Table 1: Tokenwise Accuracy: for different methods as we vary the size of the labeled data of which depends on many different factors such as properties of the data, the learning rate, number of samples, proposal function, etc. For self+cons (λ s ), the ranges of the predictions and constraint penalties are fixed and known, making the task simpler.
Self training takes 90 minutes to run on average, while Self+Cons and Model+Cons need 100 minutes. Since the Cons method skips the inference step over unlabeled data, it takes only 30 minutes to run. As the size of the model and unlabeled data set grows, this saving will become more significant. Running time of CODL was not reported.

Conclusion
This work extends the rank-based learning framework to semi-supervised learning. By integrating the two paradigms, we retain the computational efficiency provided by parameter updates within inference, while utilizing unlabeled data and prior knowledge. We demonstrate accuracy improvements on a real-word information extraction dataset.
We believe that the method will be of greater benefit to learning in complex factor graphs such as joint models over multiple extraction tasks. In future work we will investigate our approach in such settings. Additionally, various sensitivity, convergence, and robustness properties of the method need to be analyzed.