PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepER -- Deep Entity Resolution

Muhammad Ebraheem, Saravanan Thirumuruganathan, Shafiq Joty, Mourad Ouzzani, Nan Tang

arXiv:1710.00597v6cs.DB

TL;DR

Entity resolution still demands substantial human effort for labeling, feature and similarity design, parameter tuning, and blocking. DeepER addresses these demands by representing tuples with distributed representations, tuning them for ER, and using LSH-based blocking across all attributes. The paper reports superior performance to existing solutions across multiple datasets, while reducing human effort and avoiding feature engineering.

  • Problem

    Current entity-resolution pipelines require substantial human involvement in labeling, similarity design, parameter tuning, and blocking.

  • Method

    DeepER composes word embeddings into tuple representations, tunes them for ER, and applies locality-sensitive-hashing blocking across all attributes.

  • Results

    DeepER reports superior performance to existing ER solutions and published methods across citation, product, and proteomics datasets.

  • Takeaways & Limitations

    The system targets ER that requires less labeled data, feature engineering, parameter tuning, and manually defined blocking functions.

Abstract

from arXiv · show

Entity resolution (ER) is a key data integration problem. Despite the efforts in 70+ years in all aspects of ER, there is still a high demand for democratizing ER - humans are heavily involved in labeling data, performing feature engineering, tuning parameters, and defining blocking functions. With the recent advances in deep learning, in particular distributed representation of words (a.k.a. word embeddings), we present a novel ER system, called DeepER, that achieves good accuracy, high efficiency, as well as ease-of-use (i.e., much less human efforts). For accuracy, we use sophisticated composition methods, namely uni- and bi-directional recurrent neural networks (RNNs) with long short term memory (LSTM) hidden units, to convert each tuple to a distributed representation (i.e., a vector), which can in turn be used to effectively capture similarities between tuples. We consider both the case where pre-trained word embeddings are available as well the case where they are not; we present ways to learn and tune the distributed representations. For efficiency, we propose a locality sensitive hashing (LSH) based blocking approach that uses distributed representations of tuples; it takes all attributes of a tuple into consideration and produces much smaller blocks, compared with traditional methods that consider only a few attributes. For ease-of-use, DeepER requires much less human labeled data and does not need feature engineering, compared with traditional machine learning based approaches which require handcrafted features, and similarity functions along with their associated thresholds. We evaluate our algorithms on multiple datasets (including benchmarks, biomedical data, as well as multi-lingual data) and the extensive experimental results show that DeepER outperforms existing solutions.

1. INTRODUCTION

DeepER targets the human effort embedded throughout entity resolution by using distributed tuple representations to improve accuracy, efficiency, and ease of use.

  • Challenges: Entity resolution pipelines require labeling, model learning, blocking, and learned-rule application, with blocking reducing pairwise comparisons.Blocking functions usually ensure matched entities co-exist in the same block.
  • Challenges: Current ER solutions rely on human involvement at every step, while labeling is tedious and error-prone and different steps demand different expertise.The paper distinguishes knowing which entities match from explaining why or defining how to block them.
  • Challenges: Traditional similarity modeling requires experts to select domain-specific functions and thresholds, while blocking often uses only a few attributes.Such blocking lacks a holistic view of all attributes and entity semantics.
  • Our Methodology: DeepER uses distributed representations to reduce labeling, capture syntactic and semantic similarity without feature engineering or parameter tuning, and automate customizable blocking across all attributes.The methodology addresses the three observations motivating the system.
  • Our Methodology: DeepER represents tuples with methods based on token averaging or recurrent neural networks with LSTM hidden units.The system uses distributed representations of words as the basis for tuple representations.

1. [Distributed representations of tuples for ER.]

DeepER composes distributed representations of tokens across all attribute values to represent each tuple as a vector for entity resolution.

  • 1. [Distributed representations of tuples for ER.]: DeepER computes tuple representations by composing distributed representations of tokens from all attribute values.It offers simple averaging and uni- or bi-directional RNNs with LSTM hidden units.
  • 1. [Distributed representations of tuples for ER.]: The averaging method is simple, whereas the RNN-LSTM methods provide compositional tuple representations.Both methods convert a tuple into a distributed vector representation.
  • 1. [Distributed representations of tuples for ER.]: These tuple vectors can be used to capture similarities between tuples.The representation is the basis for comparing entity-resolution records.

2. [Learning/tuning distributed representations.]

DeepER extends distributed representations to task-specific tuning and LSH-based blocking, and experiments report superior performance across several datasets.

  • 2. [Learning/tuning distributed representations.]: DeepER tunes distributed representations end to end for a specific entity-resolution task.The paper states that this task customization improves DeepER’s performance.
  • 3. [Blocking for distributed representations.]: Its blocking algorithms use tuple representations and locality sensitive hashing while considering semantic relatedness across all attributes.The approach is described as efficient and effective.
  • 4. [Experiments.]: Experiments compare DeepER with a state-of-the-art ER solution and published methods on citation, product, and proteomics benchmarks.The evaluation is described as extensive.
  • 4. [Experiments.]: DeepER shows superior performance, and its proposed blocking delivers outstanding results under different conditions.These are the paper’s reported experimental conclusions.

2. DISTRIBUTED REPRESENTATIONS OF TUPLES FOR ENTITY RESOLUTION

DeepER represents tuples as vectors built from word embeddings, using either attribute-wise averaging or LSTM-RNN composition to support tuple similarity.

  • Problem definition: Entity resolution determines which distinct tuple pairs refer to the same real-world entities.Tuples may come from one table or multiple tables with aligned attributes.
  • Distributed Representations of Words: Word embeddings map words to high-dimensional vectors whose geometric relationships often encode semantic relationships.The paper uses GloVe, with an example dimension of d = 300.
  • A Simple Approach – Averaging: The simple approach averages token vectors separately for each attribute and concatenates the resulting vectors into a tuple representation.With d dimensions per attribute and m attributes, the tuple vector has d × m dimensions.
  • A Simple Approach – Averaging: Averaging ignores word order but is simple and efficient to train, motivating a compositional neural alternative.The alternative composes word vectors using a neural network motivated by linguistic structures.
  • A Compositional Approach: LSTM-RNNs process token vectors sequentially, combining each input with the previous hidden state to produce a composed representation.Bidirectional RNNs provide left-to-right and right-to-left views of the sequence.
  • A Compositional Approach: The compositional process looks up GloVe vectors and applies a shared LSTM-RNN to each attribute value, producing a tuple vector.The LSTM-RNN parameters must be learned on the ER task before composing vectors for other classifiers.

3. LEARNING AND TUNING DISTRIBUTED REPRESENTATIONS

DeepER adapts distributed word representations to ER datasets with varying vocabulary coverage, using retrofitting, domain-specific learning, and task-level fine-tuning. The approach supports generic, partially covered, and specialized data while reducing reliance on manual representation design.

  • General Data with Full Coverage: Generic ER datasets with common English vocabulary can use pre-trained GloVe representations directly and achieve competitive results.The paper identifies Citations, Products, Restaurants, and Movies as examples of such datasets.
  • General Data with Partial Coverage: Vocabulary retrofitting adapts embeddings using tuple-based word relationships, including co-occurrence and attribute structure.Known embeddings are initialized from the dictionary, while unknown words begin from averages of frequent co-occurring words before probabilistic inference refines them.
  • General Data with Partial Coverage: Retrofitting efficiently learns embeddings for unknown words, tunes them to ER data, and supports multiple definitions of relatedness.The paper gives dataset-specific co-occurrence, same-attribute, and same-tuple relationships as examples.
  • Specific Data with Minimal Coverage: Specialized datasets with minimal dictionary coverage can use embeddings learned from pooled tuples, related corpora, or domain-customized methods.These alternatives address cases where important domain terms are absent from generic dictionaries or their relationships are not captured.
  • Specific Data with Minimal Coverage: Without auxiliary resources for key concepts, specialized databases require handcrafted features or substantially more training examples for representation learning.The paper identifies this as the worst-case scenario for automatic representation learning.
  • Tuning Word Embeddings for an ER Task: DeepER can fine-tune word embeddings through backpropagation so representations acquire task-specific knowledge during supervised ER training.The network is trained with stochastic gradient descent, and classification errors are propagated through hidden layers to update parameters.

4. BLOCKING FOR DISTRIBUTED REPRESENTATIONS

DeepER reframes blocking as approximate nearest-neighbor search over tuple distributed representations, using LSH to reduce comparisons while preserving similar-pair retrieval probabilistically. Its blocking pipeline hashes tuples into multiple blocks, optionally probes nearby buckets, and classifies candidate pairs rather than comparing every possible pair.

  • New Opportunities for Blocking: Blocking groups tuples into blocks to reduce comparisons, but duplicates may be missed when they fall into different blocks.Without blocking, two-table comparison requires considering n×m tuple pairs.
  • LSH Primer: LSH places similar tuple representations in the same block with high probability by hashing them in high-dimensional similarity space.The method uses multiple hash functions and hash tables; random hyperplanes provide the cosine-distance hash family.
  • New Opportunities for Blocking: LSH-based blocking addresses expert-defined rules, few-attribute heuristics, ignored semantic similarity, and difficult recall-size tuning.Tuple distributed representations encode semantic similarity, while LSH considers all tuple attributes and offers theoretical performance guarantees.
  • LSH-based Blocking: The classifier is applied only to distinct tuple pairs found within non-empty LSH buckets across the hash tables.Each hash table represents a different blocking rule, and similar tuples are expected to share a hash code with high probability.
  • LSH-based Blocking: Traditional LSH may invoke the classifier up to O(L × bmax^2 × Bmax) times, motivating methods that reduce the effects of hash-table count and largest-block size.Here, L is the number of hash tables, bmax the largest block size, and Bmax the maximum number of non-empty blocks.
  • LSH-based Blocking: Increasing K reduces collisions among dissimilar tuples, whereas increasing L improves the chance that similar tuples share a block but adds unnecessary comparisons.The paper therefore targets fewer unnecessary comparisons and fewer hash tables without seriously affecting recall.
  • LSH-based Blocking: Approximate-nearest-neighbor blocking retrieves the top-N nearest candidates for each tuple instead of comparing every pair in a large block.Multiprobe-LSH is used to search additional buckets so the number of hash tables can be reduced without seriously harming recall.
  • LSH Primer: LSH blocking supports rigorous theoretical guarantees, unlike traditional blocking rules that are often heuristic.The paper identifies theoretical guarantees as a major advantage of its LSH-based approach.

5. EXPERIMENTAL RESULTS

Across diverse datasets, DeepER remained competitive with limited, noisy, and multilingual training conditions while its composition and blocking choices exposed clear accuracy–efficiency trade-offs.

  • Cross-domain evaluation: 87.4 F1-measure versus 83.9 state-of-the-art was achieved on the automatic curation benchmark, while DeepER beat hand-crafted ML models for 11 of 21 organisms.For the remaining organisms, performance was within an F1-score of ±5.
  • Training-data sensitivity: 10% of training data was enough for DeepER to remain competitive, corresponding to 11 labeled examples for Rest-FZ and 543 for Pub-DS.Performance improved with larger training sets, attributed to transferred semantic similarity and an ER-customized deep-learning architecture.
  • Label noise: 2.6 average F-measure points was the drop at 10% incorrect labels, increasing to 8% at 30%, while 10% noise remained competitive with state-of-the-art approaches.The corresponding standard deviations were 2.6 and 7%, respectively.
  • Embedding updates: Updating word embeddings slightly helped challenging datasets but had small negative or negligible effects on easy datasets.The experiments therefore advise using the end-to-end framework in general.
  • Composition: Word averaging usually outperformed recurrent composition on easy datasets, whereas sophisticated composition performed slightly better on challenging datasets, especially Prod-AG.Complex methods require longer training and additional hyperparameter tuning, while averaging remained competitive with prior approaches on all datasets.
  • LSH blocking: Increasing K reduced pair completeness but dramatically improved reduction ratio, whereas increasing L improved recall while worsening reduction ratio through additional false-positive comparisons.End-to-end experiments showed the same trade-off: higher K mildly increased precision but reduced recall, while higher L increased recall and mildly reduced precision.

6. RELATED WORK

DeepER is positioned as an end-to-end ER system that reduces expert burden while extending prior work with distributed-representation-based classification and blocking. Its experiments report strong performance across several benchmark settings.

  • Entity Resolution: Prior ER systems commonly rely on declarative rules, machine learning, or expert and crowd involvement, often requiring domain expertise.
  • Entity Resolution: DeepER shares Magellan’s goal of minimizing expert burden through an end-to-end EM system, while remaining modular for incorporation into existing systems.
  • Deep Learning for Data Cleaning: Unlike related distributed-representation ER work, DeepER addresses partial or minimal data coverage and proposes efficient, effective blocking solutions.
  • Blocking: DeepER’s LSH blocking differs from key- and rule-based approaches by using tuple representations and considering the semantic relatedness of all attributes.

7. FINAL REMARKS

The paper presents DeepER as a distributed-representation-based approach to entity resolution and reports results that achieve or surpass the state of the art on multiple benchmark datasets. The authors identify architecture selection, hybrid features, and dirty data as directions for improvement.

  • DeepER uses distributed representations as a key building block for ER classifiers, tuple transformation, and LSH-based blocking.
  • Experiments show that DeepER achieves or surpasses state-of-the-art performance on multiple benchmark datasets.
  • Future work includes automatically recommending architectures, combining distributed and manual features, and addressing dirty data.
Loading 1710.00597v6…