PaperlayerView exact revision on arXiv

Source-linked AI summary

Unsupervised Methods for Determining Object and Relation Synonyms on the Web

Alexander Pieter Yates, Oren Etzioni

arXiv:1401.5696v1cs.CL

TL;DR

Web information extraction produces many different strings for the same objects and relations, while schemas and labeled examples are often unavailable at that scale. Resolver uses an unsupervised probabilistic model and scalable clustering to resolve both. It reports results for object and relation synonymy, and extensions address function evidence and polysemous names.

  • Problem

    Web extractions can use different names for the same objects and relations, while domain schemas and hand-labeled examples are unavailable or impractical at Web scale.

    Source: §1 · pp. 1–2

  • Method

    Resolver combines string similarity and similarity among assertions containing the strings in a probabilistic model, then clusters the strings using a scalable algorithm.

    Source: §1 · p. 2, §5 · p. 14

  • Results

    78% precision and 68% recall for objects, and 90% precision and 35% recall for relations; the polysemy extension reports 97% precision and 95% recall on TREC extractions.

    Source: §9 · p. 31

  • Takeaways & Limitations

    Resolver applies unsupervised synonym resolution to both objects and relations, with extensions for function evidence and polysemous names.

    Source: §1 · pp. 2–3

    The ESP model’s hidden parameter is currently set using a small manually assembled development set; sampling-based estimation is proposed as an alternative.

    Source: §9 · p. 31

Abstract

from arXiv · show

The task of identifying synonymous relations and objects, or synonym resolution, is critical for high-quality information extraction. This paper investigates synonym resolution in the context of unsupervised information extraction, where neither hand-tagged training examples nor domain knowledge is available. The paper presents a scalable, fully-implemented system that runs in O(KN log N) time in the number of extractions, N, and the maximum number of synonyms per word, K. The system, called Resolver, introduces a probabilistic relational model for predicting whether two strings are co-referential based on the similarity of the assertions containing them. On a set of two million assertions extracted from the Web, Resolver resolves objects with 78% precision and 68% recall, and resolves relations with 90% precision and 35% recall. Several variations of resolvers probabilistic model are explored, and experiments demonstrate that under appropriate conditions these variations can improve F1 by 5%. An extension to the basic Resolver system allows it to handle polysemous names with 97% precision and 95% recall on a data set from the TREC corpus.

1. Introduction

Resolver addresses synonym resolution for Web extractions, where different strings can name the same objects or relations at a scale that makes schemas and hand-labeled examples impractical. It uses an unsupervised probabilistic model for both objects and relations, with extensions for scalability, function evidence, and polysemy.

1. Introduction

  • Synonymy is common in Web extractions: frequent objects average 2.9 extracted names per entity, while frequent relations average 4.9 synonyms per relation.Some of the top 80 objects had as many as 10 names.Source: §1 · p. 2
  • Resolver combines string similarity with similarity among assertions containing the strings to resolve both objects and relations without domain knowledge or labeled training data.The system is domain-independent and unsupervised.Source: §1 · p. 2
  • Resolver empirically resolves objects with 78% precision and 68% recall, and relations with 90% precision and 35% recall; its function-based extensions improve object-merging precision by 3% without hurting recall.Source: §1 · pp. 2–3
  • O(KN log N) time in N extractions and maximum synonym count K gives Resolver a scalable clustering algorithm, run on assertions from over 100 million Web pages.The paper also reports experiments on two million assertions extracted from a Web crawl.Source: §1 · p. 2
  • Resolver’s mutual-information comparison improves AUC by 193% on object clustering and 121% on relation clustering.The compared metric is based on mutual information.Source: §1 · p. 2
  • 97.3% precision and 94.7% recall on a manually cleaned TREC set show that Resolver’s extension can detect coreference among polysemous named entities.The basic system assumes each name has a single meaning; the extension requires only a large, unannotated corpus as input.Source: §1 · p. 3

2. Previous Work

Previous work addresses object resolution, relation paraphrase discovery, and broader coreference tasks, often with task-specific resources or assumptions. Resolver’s distinguishing contribution is a formal similarity model for both objects and relations that is designed to scale to millions of extractions.

2. Previous Work

  • Resolver’s main contribution to object-resolution work is a formal similarity measure for both objects and relations, with theoretical and empirical evidence of scaling to millions of extractions.Earlier object-resolution approaches include clustering names in Web documents and emails and using databases of nicknames and titles (Li, Morie, & Roth, 2004a, 2004b).Source: §2 · p. 3
  • Many coreference systems use parsers, training data, or local sequence and salience information; they address arbitrary noun phrases, unlike synonym resolution of extracted objects and relations.Coreference systems have information that is lost during extraction and do not address relation synonymy.Source: §2 · p. 4
  • Relation paraphrase work has used aligned corpora and manually labeled examples, while Resolver relies on automatically acquired extractions from a large corpus.Prior approaches include parallel translations and multiple reports of the same story (Barzilay & Lee, 2003; Barzilay & McKeown, 2001; Shinyama & Sekine, 2003; Pang, Knight, & Marcu, 2003).Source: §2 · p. 4
  • Traditional distributional metrics compare words in document contexts, whereas Resolver uses extracted properties that are sparser but provide stronger evidence for synonymy.Resolver’s metric is designed for the relational model produced by Web Information Extraction.Source: §2 · p. 5
  • Database object-resolution methods may rely on fixed schemas or domain-specific evidence, and the described approaches do not address relation resolution.Some supervised entity-resolution methods also depend on labeled examples per relation of interest.Source: §2 · p. 5
  • The paper adds a comparison with a mutual-information similarity metric, a property-weighting extension, proofs for three claims, and a fast ESP calculation to earlier Resolver work.The earlier work is Yates & Etzioni (2007).Source: §2 · p. 6

3. The Formal Synonym Resolution Problem

The formal problem takes extracted assertions and produces clusters that conjecture which strings are synonymous. It separates estimating pairwise synonymy from forming clusters, while noting that ordinary clustering imposes a single-sense assumption.

3. The Formal Synonym Resolution Problem

  • A synonym-resolution system takes extracted assertions and returns clusters of synonymous object or relation strings; the paper assumes binary assertions.Each assertion consists of a relation string and two object strings.Source: §3 · p. 6
  • A clustering partitions the distinct strings in the data into distinct clusters that cover the set.Each cluster represents a system conjecture about which strings are synonyms.Source: §3 · p. 6

3.1 The Single-Sense Assumption

  • The formal clustering assumes every string belongs to exactly one cluster, so it cannot accurately represent polysemous strings with multiple meanings.The paper later presents an extension that removes this single-sense assumption.Source: §3.1 · p. 6
  • “President Roosevelt” illustrates the limitation: it can refer to Franklin D. Roosevelt or Theodore Roosevelt, who are not synonyms of each other.No clustering under the stated definition represents all three synonymy relationships accurately.Source: §3.1 · p. 6
  • Alternative representations include soft clustering, distributions over clusters, and assigning each string instance to a cluster according to its context.The first two encode possible cluster membership or its prior probability, while instance-level clustering represents context-specific membership.Source: §3.1 · pp. 6–7

3.2 Subproblems in Synonym Resolution

  • Synonym resolution has two subproblems: estimating pairwise string similarity or synonymy probability, then clustering strings with high within-cluster and relatively low between-cluster similarity.Resolver estimates P(Rt_i,j|D_si, D_sj) for each pair and then uses those scores to produce a clustering.Source: §3.2 · p. 7

4. Models for String Comparisons

Resolver estimates synonymy from string similarity and the similarity of assertions containing each string, then clusters strings using those pairwise scores. Its models combine evidence at the string level and compare candidate clusters for merging.

4. Models for String Comparisons

  • Resolver’s probabilistic model combines edit-distance string similarity with similarity of the assertions in which strings appear.The latter evidence is distributional similarity.Source: §4 · p. 7

4.1 String Similarity Model

  • The String Similarity Model (SSM) smooths a string-similarity score into a probability of coreference, using Monge-Elkan for objects and Levenshtein edit distance for relations.The experiments use α = 20 and β = 5, with parameters chosen so the probability is neither zero nor one.Source: §4.1 · pp. 7–8

4.2 The Extracted Shared Property Model

  • The Extracted Shared Property (ESP) model estimates coreference probability from the number of shared properties or relation instances in the strings’ extracted assertions.It models synonymy as the strings sharing as many potential properties as the smaller set, although only some are extracted for both.Source: §4.2 · pp. 8–9

4.3 Comparison of ESP with Other Distributional Similarity Metrics

  • ESP’s similarity estimate stays low until roughly 10 shared properties, then rises rapidly, while CSM changes linearly; the threshold depends on extraction counts and potential-property estimates.The figure compares the models’ curve shapes, not directly comparable absolute scales.Source: §4.3 · p. 12, Figure 1 · p. 12

4.4 Combining the Evidence

  • The combined model uses a Naïve Bayes assumption that ESP and string-similarity evidence are conditionally independent given synonymy.Bayes’ Rule is used to combine the two evidence sources into a coreference probability.Source: §4.4 · pp. 12–13

4.5 Comparing Clusters of Strings

  • Resolver scores cluster pairs using probabilities for their constituent string pairs, with experiments finding that mean, geometric mean, or harmonic mean aggregation slightly improves results over an initial transitive-closure approach.The cluster-merge metric is a likelihood ratio comparing the assertions’ probability under merged clusters against the original clustering.Source: §4.5 · p. 13

5. Resolver’s Clustering Algorithm

Resolver makes greedy agglomerative clustering practical for synonym resolution by restricting comparisons in sparse, high-dimensional data. Its analysis and experiments show reduced comparison counts and operation at Web-extraction scale.

5. Resolver’s Clustering Algorithm

  • The algorithm uses greedy agglomerative clustering, comparing pairs that share properties while excluding comparisons involving properties shared by at least Max clusters.It merges the highest-scoring cluster pairs until none exceed the threshold; the shared-property restriction limits comparisons.Source: §5 · p. 14

5.1 Algorithm Analysis

  • 136× fewer object-string comparisons and 486× fewer relation-string comparisons than comparing all pairs, on 2.1 million TextRunner extractions.Resolver clustered the data in approximately 30 minutes and processed over 100 million extractions in approximately 3.5 days on a single machine.Source: §5 · p. 14, Table 1 · p. 16
  • For the data set’s Zipf parameter z < 1, O(|D| log |D|) is equivalent to O(|S| log |S|), where D is extractions and S is distinct strings.The comparison-count analysis bounds one iteration of merges by O(|D| log |D|); the paper notes the bound can be loose because most properties apply to far fewer than Max strings.Source: §5.1 · pp. 15–17

5.2 Relation to Other Speed-Up Techniques

  • Resolver adapts the Canopy method’s indexing to prune comparisons, additionally skipping pairs that share only high-frequency properties; the paper contrasts this with methods whose assumptions do not fit domain-independent extraction.The paper also notes nearest-neighbor methods’ dimensionality dependence: Resolver operates in hundreds of thousands of dimensions and determines exact nearest neighbors under its stated assumptions.Source: §5.2 · pp. 17–18

5.3 Resolver Implementation

  • Resolver is implemented as a Java package with separate modules for shared-property modeling, string similarity, and clustering, and its clusters are integrated into TextRunner’s Web-search index.The system can accept tuples of strings and optionally labeled clusters for precision and recall scoring.Source: §5.3 · p. 18

6. Experiments

The experiments compare Resolver and its components with distributional similarity baselines on Web-extracted objects and relations. They assess clustering performance, sensitivity to ESP’s hidden parameter, and sources of error.

6.1 Experimental Setup

  • Models were evaluated on 2.1 million assertions, comparing strings that appeared at least 25 times; the gold standard included 318 object and 330 relation clusters.The evaluation focused on proper nouns and excluded relation strings with punctuation or capital letters; the gold-standard construction treated polysemous names conservatively.Source: §6.1 · pp. 19–20

6.3 Sensitivity Analysis

  • Across a wide range of ESP parameter settings, ESP outperforms sMI and CSM, while Resolver outperforms SSM in AUC.The maximum possible AUC is below one because some correct pairs share no properties and are not compared by the algorithm.Source: §6.3 · pp. 21–23

6.4 Discussion

  • In all experiments, ESP outperforms CSM and sMI, but each distributional model performs below SSM alone on both objects and relations.The exception is relation clustering, where SSM’s recall is low; combining the models improves precision and recall over SSM alone.Source: §6.4 · p. 23

6.2 Clustering Analysis

  • Resolver’s F1 is 19% higher than SSM’s on objects and 28% higher on relations in the clustering experiments.The comparison covers the clustering results in Table 2.Source: §6.2 · p. 21, Table 2 · p. 21, §6.4 · p. 23

6.4 Discussion

  • Distributional similarity metrics perform worse at ranking string pairs than at clustering, which can improve estimates as clusters grow.The authors note that this difference requires further investigation.Source: §6.4 · p. 23
  • Resolver’s errors include extraction mistakes, merging similar but distinct entities, and names with multiple senses.The paper leaves extraction errors unaddressed and develops techniques for the latter two error types in later sections.Source: §6.4 · p. 23

7. Similar and Identical Pairs

Resolver’s extensions target false merges between similar but nonidentical objects using Web co-occurrence contexts and functional relations. Coordination-phrase and function filtering improve precision, while weighted property modeling yields essentially no improvement on the tested TextRunner data.

7. Similar and Identical Pairs

  • Resolver’s errors often involve similar, nonidentical objects, and distinguishing them can require unavailable amounts of additional data.Virginia and West Virginia share many properties and high string similarity, yet have different governors.Source: §7 · p. 24

7.1 Web Hitcounts for Synonym Discovery

  • The Coordination-Phrase Filter uses Web hitcounts for phrases such as “s1 and s2” to block candidate merges above a development-set threshold.This approach requires objects to occur close together in text, making it especially vulnerable to data sparsity for rare strings.Source: §7.1 · pp. 24–25

7.2 Function Filtering

  • The Function Filter blocks merges when candidate objects have mismatching values for a known function or inverse function.The experiments use a manually selected list of reliably functional relations, drawn from 500 common relations.Source: §7.2 · p. 25

7.3 Function Weighting

  • W-ESP weights shared properties by their degree, or expected number of values for an object, without requiring functional-relation knowledge or Web hitcounts.The explored version sets a property’s degree to its extraction count and reweights shared-property counts.Source: §7.3 · pp. 26–27

7.4 Experiments

  • 28% higher F1 than SSM and 6% higher F1 than unfiltered Resolver on objects with coordination-phrase filtering.Function filtering provides a smaller benefit than coordination-phrase filtering, while W-ESP yields essentially no improvement.Source: Table 6 · p. 27, §7.4 · p. 27
  • Function filtering and coordination-phrase filtering blocked merges among similar countries, continents, planets, and people, but coordination filtering was more consistent.The function filter’s smaller benefit was partly attributed to the limited number of available functions.Source: §7.4 · p. 27
  • Neither W-ESP nor TF-IDF weighting improved results on TextRunner extractions, and W-ESP’s benefits on other data remain untested.The authors identify data sets where TF-IDF helps as a setting for further investigation.Source: §7.4 · pp. 27–28

8. Resolver and Cross-Document Entity Resolution

Resolver’s cross-document extension clusters name occurrences rather than treating each name as a single meaning, using surrounding entities as context. On polysemous people’s names, it achieves significantly higher precision and roughly equal recall to Li et al.’s system.

8. Resolver and Cross-Document Entity Resolution

  • The single-sense assumption treats every token as having exactly one meaning, a limitation that becomes more problematic across multiple domains.Names such as Clinton and Bush can refer to multiple people.Source: §8 · p. 28

8.1 Clustering Polysemous Names with Resolver

  • The extension clusters entity occurrences, representing each occurrence with nearby named entities to distinguish different referents of the same name.For each occurrence, the experiment used the 100 closest named entities as context.Source: §8.1 · pp. 28–29, §8.2 · p. 29

8.2 Experiment with Cross-Document Entity Resolution

  • The evaluation used 300 New York Times documents and manually annotated clusters of approximately 4,000 people-name occurrences.Resolver’s higher absolute performance than on TextRunner partly reflects contextual information and manually labeled named entities rather than noisy extractions.Source: §8.2 · pp. 29–30
  • Resolver achieved significantly higher precision than Li et al.’s system, with roughly equal recall on polysemous people’s names.The precision and recall differences were statistically significant at p < 0.01.Source: Table 8 · p. 30, §8.2 · p. 30

9. Conclusion and Future Work

Resolver clusters coreferential object and relation names from Web extractions, with performance varying across tasks and data settings. The conclusion identifies polysemy handling and parameter setting as continuing challenges.

9. Conclusion and Future Work

  • 78% precision and 68% recall for objects, and 90% precision and 35% recall for relations, were reported for Resolver on extracted relations.Object results used coordination-phrase filtering; Resolver also improved over existing similarity metrics.Source: §9 · pp. 30–31
  • On a much cleaner set of extractions from the TREC corpus, Resolver achieved 97% precision and 95% recall using an extension that clustered different senses of the same name into separate groups.Source: §9 · p. 31
  • Resolver currently sets the ESP model’s single hidden parameter using a manually assembled development set.The authors propose sampling data and measuring the rate at which new properties appear as a possible alternative.Source: §9 · p. 31
  • Mutual recursion did not improve Resolver on TextRunner data, though artificial simulations suggest recall could rise by as much as 16% under suitable conditions.The authors identify finding natural data where this technique is useful as future work.Source: §9 · p. 31

Appendix A. Derivation of the Extracted Shared Property Model

The appendix derives the Extracted Shared Property (ESP) model’s probability of synonymy from the overlap in two strings’ extracted properties. It does so using an urn-based account of shared and unshared potential properties.

Appendix A. Derivation of the Extracted Shared Property Model

  • ESP estimates the probability that two strings are synonymous given their observed shared properties, using their potential-property counts and extraction counts.The derivation frames synonymy as the event that the strings’ potential-property sets share as many properties as possible.Source: Appendix A · p. 32
  • Under the model’s assumptions, synonymy probability depends on the number of shared extracted properties and each string’s extraction and potential-property counts.The derivation uses a uniform prior for the number of shared potential properties, with independent draws across urns and equal likelihood for each property.Source: Appendix A · p. 32
  • The derivation counts ways to select shared and unshared properties from two urns, summing over possible non-shared selections from their shared potential properties.This count supplies the probability of observing k shared extractions under varying overlap between the strings’ potential-property sets.Source: Appendix A · pp. 32, 34

Appendix B. Fast Calculation of the Extracted Shared Property Model

The appendix describes computational shortcuts for ESP and bounds Resolver’s comparison count under Zipf-distributed data. Its simplification makes ESP practical for the reported data size, while larger data may require sampling.

Appendix B. Fast Calculation of the Extracted Shared Property Model

  • Direct evaluation of the ESP formulation involves three sums and binomial-coefficient calculations, making it expensive without the described shortcuts.The appendix also notes using log probabilities and Stirling’s approximation for factorials in the implementation.Source: Appendix B · p. 35
  • Simplifying ESP’s calculation removes two sums and reduces its complexity from O(P2n2n1) to O(n2).This was sufficient for the paper’s data set, though larger data sets might require sampling.Source: Appendix B · p. 36
  • The initial Resolver clustering algorithm makes O(N log N) string comparisons, claimed asymptotically better than Canopies’ O(M2) comparisons for Zipf-distributed data.Here N is the number of extractions and M the number of distinct strings.Source: Appendix B · p. 36
  • For data with Zipf shape z < 1, Resolver’s comparison bound is O(N log N); for z = 1 it is O(M log^2 M), and for z > 1 it is O(M^z log M).Resolver’s experimental data had z < 1; the authors note naturally occurring text is unlikely to have z as high as 2.Source: Appendix B · p. 38
Loading 1401.5696v1…