Joint Inference in Information Extraction

Citation

Hoifung Poon & Pedro Domingos, "Joint Inference in Information Extraction", 27th National Conference on Artificial Intelligence (AAAI), 2007

Online version

Click here to download

Introduction

This paper aims at solving the problem of Citation Matching.
The approach makes use of Markov Logic Networks or MLN. This can be thought of as an extension to rule-based approach, where every rule has a weight with it. The nodes in an MLN are ground atoms, and the edges are ground clauses (see the method page for details). Each clause has a weight associated with it. Each state in the MLN has a probability
$P(x)=(1/Z)exp({\Sigma }w{_{i}}f{_{i}}(x))$
where Z is a normalization constant, w${_{i}}$ is the weight of the i-th clause, f${_{i}}$ = 1 if the i-th clause is true, and f${_{i}}$ = 0 otherwise. The weights are learned by iteratively optimizing pseudo-likelihood on a train databse/corpus. One way to think about MLNs as an amalgamation of probabilistic graphical models and first order logic.
The authors decided some rules for segmenting the citation into certain entities (title of the publication, authors and venue) and also identifying those entities, which were represented through an MLN. Three variants of solutions for inference were tried: an isolated inference for segmentation, a joint inference for segmentation, in which one inferred segmentation takes part in inferring another, and a joint inference of segmentation and recognition. The results were compared with existing baselines and were found to outdo baseline, although with a meager margin.

Dataset Used

The dataset used were Standard Citation Datasets Citesteer and Cora. These datasets contain a number of citations, with duplicate citations clustered together.

MLN for Joint Citation Matching

The main predicate used in the MLN is Token(t, i, c), which is true iff token t appears in the ith position of the cth citation. A token can be a word, date, number, etc. Punctuation marks are not treated as separate tokens; rather, the predicate HasPunc(c, i) is true iff a punctuation mark appears immediately after the ith position in the cth citation. Two "query" predicates are used (query predicates are the ones whose truth values are to be inferred):
InField(i, f, c), which is true iff i-th position of c-th citation is a field f, where f $\mathrm {E}$ {Title,Author,Venue}, and
SameCitation(c, c′) which is true iff citations c and c' represent the same publication, and inferring this predicate performs entity resolution.

Isolated Segmented Model

The first model that the authors tried to solve the problem with, was to segment the citations without any kind of joint inference. Their segmentation model is essentially an HMM, where observation matrix and trnasition matrix are defined by certain logical formulas. For this model for identifying a segment, the observation matrix is defined by the logical formula:
Token(+t, i, c) ⇒ InField(i, +f, c)
The “+t, +f” notation signifies that the MLN contains an instance of this rule for each (token, field) pair. If this rule was learned in isolation, the weight of the (t,f)th instance would be log(p${_{t}f}$ /(1−p${_{t}f}$ )), where p${_{t}f}$ is the corresponding entry in the HMM observation matrix. The transition matrix, on the other hand, is defined by the below logical formula:
InField(i, +f, c) ⇒ InField(i + 1, +f',c')
The inclusion of token boundary in the above formulas for finding the token in a filed is as below:
InField(i, +f, c) ∧ ¬HasPunc(c, i) ⇒ InField(i + 1, +f, c)
In addition to the above rules, the following rules were also used: the first two positions of a citation are usually in the author field, and the middle one in the title; initials (e.g., “J.”) tend to appear in either the author or the venue field; positions preceding the last non-venue initial are usually not part of the title or venue; and positions after the first venue keyword (e.g., “Proceedings”, “Journal”) are usually not part of the author or title.

Entity Resolution Model

The Entity Resolution/Recognition model contains rules of the form: if two fields contain many common tokens, they are the same; if the fields of two citations match, the citations also match, and vice-versa; etc. Simply taking the output InField() predicates of the segmentation MLN as evidence to this MLN would constitute a standard pipeline model. Merging the two MLNs produces a joint model for segmentation and entity resolution.
However, the problem with this pipeline is that entity resolution often affects segmentation in a joint model. Since only a small fraction of citation pairs (c, c′) match, in the absence of strong evidence to the contrary the MLN will conclude that SameCitation(c, c′) is false. If SameCitation(c, c′) is the consequent of a rule (or rule chain) with InField() in the antecedent, the MLN may infer that InField() is false, even if segmentation alone would correctly predict it to be true.
Therefore, the authors defined additional rules that would not simply take InField as an antecedent rule.
A rule SimilarTitle(c, i, j, c′, i′, j′) was defined, which is true if citations c and c′ contain similar title like strings at positions i to j and i′ to j′, respectively. A string is title-like if it does not contain punctuation and does not match the “title exclusion” as defined above in isolated segmentation model.

Joint Segmentation Model

Segmenting a citation can help segment similar ones. For example, if in one citation the title is clearly delimited by punctuation, but in a similar one it is not, noticing this similarity can help extract the more difficult title. Incorporating this idea into the MLN described earlier leads to joint segmentation, where citations are segmented collectively, as opposed to in isolation. As before, we proceed by defining a predicate for this purpose. JointInferenceCandidate(c, i, c ′ ) is true if the trigram starting at position i in citation c also appears somewhere in citation c ′ , the trigrams do not match the “title exclusion” rules, and the trigram in c is not preceded by punctuation, while in c ′ it is. This rule thus identifies potential opportunities for one title segmentation to help another. We then incorporate this into the segmentation model simply by adding a precondition to the “field propagation” rules. For example: InField(i, +f, c) ∧ ¬HasPunc(c, i) ∧(¬∃c ′ JointInferenceCandidate(c, i, c ′ )) ⇒ InField(i + 1, +f, c) The effect of this precondition is to potentially introduce a field boundary in c immediately before a substring if a similar title-like substring is preceded by punctuation in another citation. This may be quite effective when citation lists are “sparse” (i.e., strings usually do not occur both at boundaries and inside fields). However, if the citation lists are “dense,” it may produce incorrect field boundaries. Consider the following two citations from the Cora dataset: R. Schapire. On the strength of weak learnability. Proceedings of the 30th I.E.E.E. Symposium on the Foundations of Computer Science, 1989, pp. 28- 33. Robert E. Schapire. 5(2) The strength of weak learnability. Machine Learning, 1990 197-227, In the second citation, “The strength of” is immediately preceded by punctuation, which will cause a title boundary to be incorrectly introduced between “On” and “the” in the first citation. To combat this, we can in addition require that the two citations in fact resolve to the same entity: InField(i, +f, c) ∧ ¬HasPunc(c, i) ∧(¬∃c ′ JointInferenceCandidate(c, i, c ′ ) ∧SameCitation(c, c ′ )) ⇒ InField(i + 1, +f, c)

As the cliques considered are single-node and two-node cliques, the features were also defined for both single nodes and parent-child pairs. There were many syntactic features used; I will not be describing each of them as the reference for them can be found in the paper. The syntactic features or the feature types were made into binary functions $g$ and $h$ by combining (feature type, feature value) pairs with label (for a single node) or label pairs (for two-noded cliques), when such a feature-type, feature-value was seen at least once in the training data.
The different feature types used were:
Basic features: {Head word, head PoS, phrase syntactic category, phrase path, position relative to the predicate, surface distance to the predicate, predicate lemma, predicate token, predicate voice, predicate sub-categorisation, syntactic frame}.
Context features: {Head word of first NP in preposition phrase, left and right sibling head words and syntactic categories, first and last word in phrase yield and their PoS, parent syntactic category and head word}.
Common ancestor of the verb: The syntactic category of the deepest shared ancestor of both the verb and node.
Feature conjunctions: The following features were conjoined: { predicate lemma + syntactic category, predicate lemma + relative position, syntactic category + first word of the phrase}.
Default feature: This feature is always on, which allows the classifier to model the prior probability distribution over the possible argument labels.
Joint features: These features were only defined over pair-wise cliques: {whether the parent and child head words do not match, parent syntactic category + and child syntactic category, parent relative position + child relative position, parent relative position + child relative position + predicate PoS + predicate lemma}.

Experimental Results and Conclusion

The parsed training data sentences yielded 90,388 predicates and 1,971,985 binary features ($g$ and $h$). The experimental results of precision, recall and f-scores are shown in the table below.


Although the modeling of the problem is neat, the results reported were not at par with the best systems that competed in the CoNLL shared task. Marquez et. al. in their paper showed that modeling the SRL problem as a sequential BIO-tagging problem still gives far better results. They made use of a combination of deep and shallow syntactic features and used boosting technique for the BIO-tagging.

Comments

Any ideas why their approach doesn't work as well as BIO tagging? That is an interesting result. --Brendan 18:55, 13 October 2011 (UTC)

---

Response to the Comment (by Manaj)

Well, I guess this might have to do something with the kind of problem and the approach taken. Modeling a sequential labeling problem (such as SRL) with CRF should give good results when modeled over sequential structures. However, here CRF is modeled over syntactic tree structures. The authors thought that it would make sense since the arguments in SRL are always relative to a predicate (verb), and the features generally used are the syntactic features. However, it turned out that the results were not as great as many other techniques applied, including SVM (seethis or this). This brings me to thinking that CRF over tree structures might not be a good representation of the problem itself. Coming to its comparison with the sequential BIO-tagging in Semantic Role Labeling as Sequential Tagging, the most likely reasons why the latter outperformed the former significantly could be because of the use of a combination of features (syntactic features and chunk-features) and the usage of Ada-boost with decision trees. Its worth mentioning how this empirical study proved Decision Trees to be among the better performing models.