Inducing Search Keys for Name Filtering

L. Karl BrantingEMNLP 2007

TL;DR

This paper introduces ETK, a novel algorithm that learns efficient "search keys" to filter name lists for matching. Unlike traditional methods that rely on fixed phonetic rules, ETK adapts to specific similarity metrics and learns from examples, offering improved accuracy and flexibility for tasks like cross-lingual name matching.

What Problem Does This Paper Address?

In many applications, from national security to managing large databases, we need to identify when different strings likely refer to the same entity – a task known as name matching. The challenge arises from the myriad ways names can vary: typos, OCR errors, and especially cross-lingual transliterations (e.g., "Mohamed" vs. "Muhammet").

Performing exact string comparisons on massive datasets is computationally prohibitive. Therefore, a common strategy is a two-stage approach: first, an inexpensive "filter" narrows down the potential matches to a manageable subset, and then a more computationally intensive "similarity metric" is applied to this subset. The crucial problem is designing filters that are both highly effective (high recall and precision) and computationally cheap, while also being adaptable to different ways of defining "similarity." Existing methods like phonetic indexing (e.g., Soundex) or n-gram indexing are fast but often lack adaptability and can miss matches or include too many false positives.

Methods

The core innovation is ETK (Ensemble of Transformation-based Keys). ETK learns to generate "keys" for names by analyzing examples of names that are considered matches under a given similarity metric and a defined "error threshold" (k).

Here's how it works:

  1. Equivalence Classes: The process starts with groups of names that are known to match (equivalence classes).
  2. Centroid and Alignment: For each class, a "centroid" name is chosen. Then, dynamic programming is used to align every other name in the class with the centroid, identifying corresponding characters.
  3. Transformation Rules: Based on these alignments, "transformation rules" are created. These rules describe how to transform a small window of characters in one name to a single character in the centroid. For example, a rule might state that the sequence "LAY" in one name should map to "L" in the centroid.
  4. Key Formation: These rules are then grouped into consistent subsets. Each subset forms an independent "key function." A name is then transformed into a key by applying its key function to different parts of the name.
  5. Ensemble: ETK creates an ensemble of these key functions. A name is indexed by all the keys generated by all its key functions. When searching, a query name is also converted into multiple keys, and any name sharing at least one key with the query is considered a potential match.

The key advantage is that ETK learns these transformations directly from data, making it adaptable to various similarity metrics (phonetic, edit distance, etc.) and specific error thresholds.

Datasets

The paper uses two primary datasets for evaluation:

  • U.S. Surnames: The 5,000 most common last names from the U.S. Census, with pronunciations from the CMU Pronouncing Dictionary.
  • German Surnames: The first 5,963 entries from the HADI-BOMP collection.

These datasets were used to train and test ETK, comparing its performance against other filtering algorithms.

Key Insights and Ideas

  • Learning Similarity: The most significant insight is that search keys don't need to be hand-crafted based on fixed linguistic rules. They can be learned from examples of what constitutes a match, making them far more adaptable.
  • Ensemble Power: Combining multiple, independently learned keys (an ensemble) significantly boosts recall and precision compared to any single key. This is because different keys can capture different aspects of name variation.
  • Adaptability is Key: ETK's ability to adapt to different distance metrics (phonetic vs. edit distance) is crucial. This means it can be applied to a wider range of name-matching problems than static algorithms like Soundex.
  • Implicit Metric Learning: ETK can learn effective filters even if the underlying similarity metric is not explicitly known, as long as representative equivalence classes are available.

Key Results

ETK consistently outperformed other filtering algorithms (Soundex, Phonex, ngrams, partition filtering, and BKT) in terms of F-measure (a balance of precision and recall) across various conditions, particularly when using pronunciation distance.

  • High F-measure: ETK achieved the highest F-measure in most evaluations, demonstrating a strong balance between precision and recall. For instance, on U.S. surnames with pronunciation distance and k=1, ETK achieved an F-measure of 0.3428, significantly higher than Soundex (0.0637) or Phonex (0.0339).
  • Adaptability Demonstrated: ETK showed strong performance with both phonetic (pronunciation distance) and non-phonetic (edit distance) metrics.
  • Recall vs. Precision Trade-off: While ETK generally offered the best F-measure, other algorithms like BKT sometimes achieved higher recall (1.0000) but at a severe cost to precision, leading to many more expensive similarity metric calls.

Limitations and Future Work

  • Training Data Dependency: ETK requires a substantial set of training examples (equivalence classes) to learn effective keys. If such data is scarce, simpler filters might be more practical.
  • Computational Cost of Training: While ETK's filtering is efficient, the process of inducing the keys from training data can be computationally intensive.
  • Future Directions: The authors suggest exploring variations like using finite-state transducers instead of transformation rules, or alternative window-based approaches for deriving mappings. They also note that the choice of training set size is important, with learning curves rising steeply, suggesting that more data generally leads to better performance.

Summary updated

BibTeX
@inproceedings{branting2007inducing,
  author = {L. Karl Branting},
  title = {{Inducing Search Keys for Name Filtering}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}

Loading related content...

Figure