Unsupervised deduplication using cross-field dependencies

ABSTRACT

Recent work in deduplication has shown that collective deduplication of different attribute types can improve performance. But although these techniques cluster the attributes collectively, they do not model them collectively. For example, in citations in the research literature, canonical venue strings and title strings are dependent -- because venues tend to focus on a few research areas -- but this dependence is not modeled by current unsupervised techniques. We call this dependence between fields in a record a cross-field dependence. In this paper, we present an unsupervised generative model for the deduplication problem that explicitly models cross-field dependence. Our model uses a single set of latent variables to control two disparate clustering models: a Dirichlet-multinomial model over titles, and a non-exchangeable string-edit model over venues. We show that modeling cross-field dependence yields a substantial improvement in performance -- a 58% reduction in error over a standard Dirichlet process mixture.

REFERENCES

• 1: A. Bagga and B. Baldwin. Algorithms for scoring coreference chains. In Proceedings of MUC7, 1998.
• 2: I. Bhattacharya and L. Getoor. A latent dirichlet model for unsupervised entity resolution. In SIAM Conference on Data Mining (SDM), 2006.
• 3: Indrajit Bhattacharya , Lise Getoor, Collective entity resolution in relational data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.5-es, March 2007 [doi>10.1145/1217299.1217304]
• 4: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.993]
• 5: P. Carbonetto, J. Kisynski, N. de Freitas, and D. Poole. Nonparametric Bayesian logic. In Conference on Uncertainty in Artificial Intelligence (UAI), 2005.
• 6: C. Chemudugunta, P. Smyth, and M. Steyvers. Modeling general and specific aspects of documents with a probabilistic topic model. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19, pages 241--248. MIT Press, Cambridge, MA, 2007.
• 7: Aron Culotta , Andrew McCallum, Joint deduplication of multiple record types in relational data, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099615]
• 8: D. B. Dahl. Sequentially-allocated merge-split sampler for conjugate and nonconjugate dirichlet process mixture models. Journal of Computational and Graphical Statistics, 2005.
• 9: A. Haghighi and D. Klein. Unsupervised coreference resolution in a nonparametric Bayesian model. In ACL, 2007.
• 10: A. McCallum and B. Wellner. Conditional models of identity uncertainty with application to noun coreference. In L. K. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems 17, pages 905--912. MIT Press, Cambridge, MA, 2005.
• 11: Brian Christopher Milch , Stuart J. Russell, Probabilistic models with unknown objects, University of California at Berkeley, Berkeley, CA, 2006
• 12: R. M. Neal. Markov chain sampling methods for Dirichlet process mixture models. Journal of Computational and Graphical Statistics, 9:249--265, 2000.
• 13: H. M. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. Identity uncertainty and citation matching. In NIPS, 2003.
• 14: P. Singla and P. Domingos. Multi-relational record linkage. In KDD-2004 Workshop on Multi-Relational Data Mining, pages 31--48, 2004.
• 15: Parag Singla , Pedro Domingos, Entity Resolution with Markov Logic, Proceedings of the Sixth International Conference on Data Mining, p.572-582, December 18-22, 2006 [doi>10.1109/ICDM.2006.65]
• 16: Yee Whye Teh, A hierarchical Bayesian language model based on Pitman-Yor processes, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, p.985-992, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220299]
• 17: Y. W. Teh, M. I. Jordan, M. J. Beal, and D. M. Blei. Hierarchical Dirichlet processes. Journal of the American Statistical Association, 101(476):1566--1581, 2006.
• 18: Ben Wellner , Andrew McCallum , Fuchun Peng , Michael Hay, An integrated, conditional model of information extraction and coreference with application to citation matching, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.593-601, July 07-11, 2004, Banff, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Experimentation

Keywords:
data mining, deduplication, dirichlet process mixture, information extraction