{'fraction_non_alphanumeric': 0.03797731045932485, 'fraction_numerical': 0.012935805201992253, 'mean_word_length': 4.734629115430384, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, '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}}
Combining Generative and Discriminative Model Scores for Distant Supervision

Distant supervision is a scheme to generate noisy training data for relation extraction by aligning entities of a knowledge base with text. In this work we combine the output of a discriminative at-least-one learner with that of a generative hierarchical topic model to reduce the noise in distant supervision data. The combination significantly increases the ranking quality of extracted facts and achieves state-of-the-art extraction performance in an end-to-end setting. A simple linear interpolation of the model scores performs better than a parameter-free scheme based on nondominated sorting.


Introduction
Relation extraction is the task of finding relational facts in unstructured text and putting them into a structured (tabularized) knowledge base. Training machine learning algorithms for relation extraction requires training data. If the set of relations is prespecified, the training data needs to be labeled with those relations.
Manual annotation of training data is laborious and costly, however, the knowledge base may already partially be filled with instances from the relations. This is utilized by a scheme known as distant supervision (DS) (Mintz et al., 2009): text is automatically labeled by aligning (matching) pairs of entities that are contained in a knowledge base with their textual occurrences. Whenever such a match is encountered, the surrounding context (sentence) is assumed to express the relation.
This assumption, however, can fail. Consider the example given in (Takamatsu et al., 2012): If the tuple place_of_birth (Michael Jackson, Gary) is contained in the knowledge base, one matching context could be: Michael Jackson was born in Gary ... And another possible context: Michael Jackson moved from Gary ... Clearly, only the first context indeed expresses the relation and should be labeled accordingly.
Three basic approaches have been proposed to deal with noisy distant supervision instances: The discriminative at-least-one approach , that requires that at least one of the matches for a relation-entity tuple indeed expresses the relation; The generative approach (Alfonseca et al., 2012) that separates relation-specific distributions from noise distributions by using hierarchical topic models; And the pattern correlation approach (Takamatsu et al., 2012) that assumes that contexts which match argument pairs have a high overlap in argument pairs with other patterns expressing the relation.
In this work we combine 1) a discriminative atleast-one learner, that requires high scores for both a dedicated noise label and the matched relation, and 2) a generative topic model that uses a feature-based representation to separate relation-specific patterns from background or pair-specific noise. We score surface patterns and show that combining the two approaches results in a better ranking quality of relational facts. In an end-to-end evaluation we set a threshold on the pattern scores and apply the pat- terns in a TAC KBP-style evaluation. Although the surface patterns are very simple (only strings of tokens), they achieve state-of-the-art extraction results.

At-Least-One Models
The original form of distant supervision (Mintz et al., 2009) assumes all sentences containing an entity pair to be potential patterns for the relation holding between the entities. A variety of models relax this assumption and only presume that at least one of the entity pair occurrences is a textual manifestation of the relation. The first proposed model with an atleast-one learner is that of  and . It consists of a factor graph that includes binary variables for contexts, and groups contexts together for each entity pair. MultiR (Hoffmann et al., 2011) can be viewed as a multi-label extension of . A further extension is MIMLRE (Surdeanu et al., 2012), a jointly trained two-stage classification model.

Hierarchical Topic Model
The hierarchical topic model (HierTopics) by Alfonseca et al. (2012) models the distant supervision data by a generative model. For each corpus match of an entity pair in the knowledge base, the corresponding surface pattern is assumed to be typical for either the entity pair, the relation, or neither. This principle is then used to infer distributions over patterns of one of the following types: 1. For every entity pair, a pair-specific distribution.
2. For every relation, a relation-specific distribution.

A general background distribution.
The generative process assumes that for each argument pair in the knowledge base, all patterns are generated by first choosing a hidden variable z which can take on three values, B for background, R for relation and P for pair. Corresponding vocabulary distributions (φ bg , φ rel , φ pair ) for generating the context patterns are chosen according to the value of z. The Dirichlet-smoothed vocabulary distributions are shared on the respective levels. Figure 1 shows the plate diagram of the HierTopics model.

Generative Model
We use a feature-based extension (Roth and Klakow, 2013) of Alfonseca et al. (2012) to include bigrams for a more fine-grained representation of the patterns. For including features in the model, the model is extended with a second layer of hidden variables.
A variable x represents a choice of B, R or P for every pattern, i.e. there is one variable x for every pattern. Each feature is generated conditioned on a second variable z ∈ {B, R, P }, i.e. there are as many variables z for a pattern as there are features for it. First, the hidden variable x is generated, then all z variables are generated for the corresponding features (see Figure 1). The values B, R or P of z depend on the corresponding x by a transition distribution: where features at indices i are mapped to the corresponding pattern indices by a function j(i); p same is set to .99 to enforce the correspondence between pattern and feature topics. 1

Discriminative Model
As a second feature-based model, we employ a perceptron model that enforces constraints on the labels for patterns (Roth and Klakow, 2013). The model consists of log-linear factors for the set of relations Algorithm 1 At-Least-One Perceptron Training R as well as a factor for the NIL label (no relation). Probabilities for a relation r given a sentence pattern s are calculated by normalizing over log-linear factors defined as f r (s) = exp ( i φ i (s, r)θ i ), with φ(s, r) the feature vector for sentence s and label assignment r, and θ r the feature weight vector. The learner is directed by the following semantics: First, for a sentence s that has a distant supervision match for relation r, relation r should have a higher probability than any other relation r ∈ R \ r. As extractions are expected to be noisy, high probabilities for N IL are enforced by a second constraint: N IL must have a higher probability than any relation r ∈ R \ r. Third, at least one DS sentence for an argument pair is expected to express the corresponding relation r. For sentences s for an entity pair belonging to relation r, this can be written as the following constraints: ∀ s,r : P (r|s) > P (r |s) ∧ P (N IL|s) > P (r |s) ∃ s : P (r|s) > P (N IL|s) The violation of any of the above constraints triggers a perceptron update. The basic algorithm is sketched in Algorithm 1. 2

Model Combination
The per-pattern probabilities P (r|pat) are calculated as in Alfonseca et al. (2012) and aggregated over all pattern occurrences: For the topic model, the number of times the relation-specific topic has been sampled for a pattern is divided by n(pat), the number of times the same pattern has been observed. Analogously for the perceptron, the number of times a pattern co-occurs with entity pairs for r is multiplied by the perceptron score and divided by n(pat).  • Topic Model: n(pat,topic(r)) n(pat) • Perceptron: n(pat,r) n(pat) · P (r|s,θ) P (r|s,θ)+P (N IL|s,θ) • Interpolation: 0.5·n(pat,topic(r)) n(pat) + 0.5·n(pat,r)·P (r|s,θ) n(pat)·(P (r|s,θ)+P (N IL|s,θ)) The topic model and perceptron approaches are based on plausible yet fundamentally different principles of modeling noise without direct supervision. It is therefore an interesting question how complementary the models are and how much can be gained from a combination. As the two models do not use direct supervision, we also avoid tuning parameters for their combination.
We use two schemes to obtain a combined ranking from the two model scores: The first is a ranking based on non-dominated sorting by successively computing the Pareto-frontier of the 2-dimensional score vectors (Borzsony et al., 2001;Godfrey et al., 2007). The underlying principle is that all data points (patterns in our case) that are not dominated by another point 3 build the frontier and are ranked highest (see Figure 2), with ties broken by linear combination. Sorting by computing the Paretofrontier has been applied to training machine translation systems (Duh et al., 2012) to combine the translation quality metrics BLEU, RIBES and NTER, each of which is based on different principles. In the context of machine translation it has been found to outperform a linear interpolation of the metrics and to be more stable to non-smooth metrics and noncomparable scalings. We compare non-dominated sorting with a simple linear interpolation with uniform weights.

Ranking-Based Evaluation
Evaluation is done on the ranking quality according to TAC KBP gold annotations (Ji et al., 2010) of extracted facts from all TAC KBP queries from 2009-2011 and the TAC KBP 2009-2011 corpora. First, candidate sentences are retrieved in which the query entity and a second entity with the appropriate type are contained. Candidate sentences are then used to provide answer candidates if one of the extracted patterns matches. The answer candidates are ranked according to the score of the matching pattern.
The basis for pattern extraction is the noisy DS training data of a top-3 ranked system in TAC KBP 2012 (Roth et al., 2012). The retrieval component of this system is used to obtain sentence and answer candidates (ranked according to their respective pattern scores). Evaluation results are reported as averages over per-relation results of the standard ranking metrics mean average precision (map), geometric map (gmap), precision at 5 and at 10 (p@5, p@10).
The maximum-likelihood estimator (MLE) baseline scores patterns by the relative frequency they occur with a certain relation. The hierarchical topic (hier orig) as described in Alfonseca et al. (2012) increases the scores under most metrics, however the increase is only significant for p@5 and p@10. The feature-based extension of the topic model (hier feat) has significantly better ranking quality. Slightly better scores are obtained by the at-leastone perceptron learner. It is interesting to see that the model combinations both by non-dominated sorting perc+hier (pareto) as well as uniform interpolation perc+hier (itpl) give a further increase in ranking .344 †* .220 †* .426 †* .353 †*  quality. The simpler interpolation scheme generally works best. Figure 3 shows the Precision/Recall curves of the basic models and the linear interpolation. On the P/R curve, the linear interpolation is equal or better than the single methods on all recall levels.

End-To-End Evaluation
We evaluate the extraction quality of the induced perc+hier (itpl) patterns in an end-to-end setting. We use the evaluation setting of (Surdeanu et al., 2012) and the results obtained with their pipeline for MIMLRE and their re-implementation of MultiR as a point of reference.
In Surdeanu et al. (2012) evaluation is done using a subset of queries from the TAC KBP 2010 and 2011 evaluation. The source corpus is the TAC KBP source corpus and a 2010 Wikipedia dump. Only those answers are considered in scoring that are contained in a list of possible answers from their candidates (reducing the number of gold answers from 1601 to 576 and thereby considerably increasing the value of reported recall).
For evaluating our patterns, we take the same queries for testing as Surdeanu et al. (2012). As the document collection, we use the TAC KBP source collection and a Wikipedia dump from 07/2009 that was available to us. From this document collection, we use our retrieval pipeline of Roth et al. (2012) and take those sentences that contain query entities and slot filler candidates according to NEtags. We filter out all candidates that are not contained in the list of candidates considered in (Surdeanu et al., 2012), and use the same reduced set of 576 gold answers as the key. We tune a single threshold parameter t = .3 on held-out development data and take all patterns with higher scores. Table 2 shows that results obtained with the induced patterns compare well with state-of-the-art relation extraction systems.   Figure 4 shows top-ranked patterns for per:title and org:top members employees, the two relations with most answers in the gold annotations. For maximum likelihood estimation the score is 1.0 if the patterns occurs only with the relation in question -this includes all cases where the pattern is only found once in the corpus. While this could be circumvented by frequency thresholding, we leave the long tail of the data as it is and let the algorithm deal with both frequent and infrequent patterns.

Illustration: Top-Ranked Patterns
One can see that while the maximum likelihood patterns contain some reasonable relational contexts, they are less prototypical and more prone to distant supervision errors. The patterns scored high by the proposed combination generalize better, variation at the top is achieved by re-combining elements that carry relational meaning ("is an", "vice president", "president director") or are closely correlated to the particular relation.

Conclusion
We have combined two models based on distinct principles for noise reduction in distant supervision: a feature-based extension of a hierarchical topic model, and an at-least-one perceptron. Interpolation increases the quality of extractions and achieves state-of-the-art extraction performance. A combination scheme based on non-dominated sorting, that was inspired by work on combining machine translation metrics, was not as good as a simple linear combination of scores. We think that the good results motivate research into more integrated combinations of noise reduction approaches.