A theoretical framework for learning from a pool of disparate data sources

ABSTRACT

Many enterprises incorporate information gathered from a variety of data sources into an integrated input for some learning task. For example, aiming towards the design of an automated diagnostic tool for some disease, one may wish to integrate data gathered in many different hospitals. A major obstacle to such endeavors is that different data sources may vary considerably in the way they choose to represent related data. In practice, the problem is usually solved by a manual construction of semantic mappings and translations between the different sources. Recently there have been attempts to introduce automated algorithms based on machine learning tools for the construction of such translations.In this work we propose a theoretical framework for making classification predictions from a collection of different data sources, without creating explicit translations between them. Our framework allows a precise mathematical analysis of the complexity of such tasks, and it provides a tool for the development and comparison of different learning algorithms. Our main objective, at this stage, is to demonstrate the usefulness of computational learning theory to this practically important area and to stimulate further theoretical and experimental research of questions related to this framework.

REFERENCES

• 1: J. Baxter. A model of inductive bias learning. Journal of Artificial Intelligence Research, 12:149--198, 2000.
• 2: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 3: Rich Caruana, Multitask Learning, Machine Learning, v.28 n.1, p.41-75, July 1997 [doi>10.1023/A:1007379606734]
• 4: Silvana Castano , Valeria de Antonellis, A Schema Analysis and Reconciliation Tool Environment for Heterogeneous Databases, Proceedings of the 1999 International Symposium on Database Engineering & Applications, p.53, August 02-04, 1999
• 5: AnHai Doan , Pedro Domingos , Alon Y. Halevy, Reconciling schemas of disparate data sources: a machine-learning approach, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.509-520, May 21-24, 2001, Santa Barbara, California, United States
• 6: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 7: D. Hall and J. Llinas. An introduction to multisensor data fusion. In Proceedings of the IEEE, volume 85, pages 6--23.
• 8: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 9: D. Saccà L. Palopol , D. Ursino, Semi-Automatic, Semantic Discovery of Properties from Database Schemes, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.244, July 08-10, 1998
• 10: Tova Milo , Sagit Zohar, Using Schema Matching to Simplify Heterogeneous Data Translation, Proceedings of the 24rd International Conference on Very Large Data Bases, p.122-133, August 24-27, 1998
• 11: E. Rahm and P. Bernstein. On matching schemas automatically. Dept. of Computer Science, Univ. of Leipzig, 2001.
• 12: S. Ben-David, J. Gehrke and R. Schuller. Technical report, Computer Science Department, Cornell University, May 2002.
• 13: S. Thrun and J. O'Sullivan. Discovering structure in multiple learning tasks: The TC algorithm. In International Conference on Machine Learning, pages 489--497, 1996.
• 14: Sebastian Thrun , Lorien Pratt, Learning to learn, Kluwer Academic Publishers, Norwell, MA, 1998
• 15: H. Wache, T. Vgele, U. Visser, H. Stuckenschmidt, G. Schuster, H. Neumann, and S. Hbner. Ontology-based integration of information - a survey of existing approaches. In Proceedings of the Workshop Ontologies and Information Sharing, IJCAI, 2001.
• 16: L. Wald. An overview of concepts in fusion of earth data. In P. Gudmandsen, editor, Future trends in Remote Sensing, pages 385--390. Balkema, 1997.
• 17: Qiu Yue Wang , Jeffrey X. Yu , Kam-Fai Wong, Approximate Graph Schema Extraction for Semi-Structured Data, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.302-316, March 27-31, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.12 Interoperability
            Subjects: Data mapping

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Performance