Mining reference tables for automatic text segmentation

ABSTRACT

Automatically segmenting unstructured text strings into structured records is necessary for importing the information contained in legacy sources and text collections into a data warehouse for subsequent querying, analysis, mining and integration. In this paper, we mine tables present in data warehouses and relational databases to develop an automatic segmentation system. Thus, we overcome limitations of existing supervised text segmentation approaches, which require comprehensive manually labeled training data. Our segmentation system is robust, accurate, and efficient, and requires no additional manual effort. Thorough evaluation on real datasets demonstrates the robustness and accuracy of our system, with segmentation accuracy exceeding state of the art supervised approaches.

REFERENCES

• 1: Microsoft SmartTagger.
• 2: Proceedings of the 7th Message Understanding Conference (MUC-7). Morgan Kaufman, 1998.
• 3: Brad Adelberg, NoDoSE—a tool for semi-automatically extracting structured and semistructured data from text documents, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.283-294, June 01-04, 1998, Seattle, Washington, United States
• 4: J. Bilmes. What HMMs can do. Technical report, UWEETR-2002-0003, 2002.
• 5: Vinayak Borkar , Kaustubh Deshmukh , Sunita Sarawagi, Automatic segmentation of text into structured records, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.175-186, May 21-24, 2001, Santa Barbara, California, United States
• 6: Mary Elaine Califf , Raymond J. Mooney, Relational learning of pattern-match rules for information extraction, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.328-334, July 18-22, 1999, Orlando, Florida, United States
• 7: Surajit Chaudhuri , Kris Ganjam , Venkatesh Ganti , Rajeev Motwani, Robust and efficient fuzzy match for online data cleaning, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872796]
• 8: Stanley F. Chen , Joshua Goodman, An empirical study of smoothing techniques for language modeling, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.310-318, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981904]
• 9: William W. Cohen , Sunita Sarawagi, Exploiting dictionaries in named entity extraction: combining semi-Markov extraction processes and data integration methods, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014065]
• 10: Michael Collins, Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.1-8, July 06, 2002 [doi>10.3115/1118693.1118694]
• 11: M. Collins and Y. Singer. Unsupervised models for named entity classification. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 1999.
• 12: Valter Crescenzi , Giansalvatore Mecca , Paolo Merialdo, RoadRunner: Towards Automatic Data Extraction from Large Web Sites, Proceedings of the 27th International Conference on Very Large Data Bases, p.109-118, September 11-14, 2001
• 13: J. Droppo, L. Deng, and A. Acero. Evaluation of the splice algorithm on the aurora2 database. In Proceedings of the Eurospeech Conference, 2001.
• 14: D. W. Embley , Y. Jiang , Y.-K. Ng, Record-boundary discovery in Web documents, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.467-478, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 15: Dayne Freitag , Andrew McCallum, Information Extraction with HMM Structures Learned by Stochastic Optimization, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.584-589, July 30-August 03, 2000
• 16: Dayne Freitag , Andrew McCallum, Information Extraction with HMM Structures Learned by Stochastic Optimization, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.584-589, July 30-August 03, 2000
• 17: Ralph Grishman, Information Extraction: Techniques and Challenges, International Summer School on Information Extraction: A Multidisciplinary Approach to an Emerging Information Technology, p.10-27, January 1997
• 18: Mauricio A. Hernández , Salvatore J. Stolfo, Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem, Data Mining and Knowledge Discovery, v.2 n.1, p.9-37, January 1998 [doi>10.1023/A:1009761603038]
• 19: C. A. Knoblock, K. Lerman, S. Minton, and I. Muslea. Accurately and reliably extracting data from the web: A machine learning approach. IEEE Data Engineering Bulletin, 23(4):33--41, 2000.
• 20: Mirella Lapata, Probabilistic text structuring: experiments with sentence ordering, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.545-552, July 07-12, 2003, Sapporo, Japan [doi>10.3115/1075096.1075165]
• 21: A. Martin and M. Przybocki. NIST 2003 language recognition evaluation. In Proceedings of the Eurospeech Conference, 2003.
• 22: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 23: Andrei Mikheev , Marc Moens , Claire Grover, Named Entity recognition without gazetteers, Proceedings of the ninth conference on European chapter of the Association for Computational Linguistics, June 08-12, 1999, Bergen, Norway [doi>10.3115/977035.977037]
• 24: Ion Muslea , Steve Minton , Craig Knoblock, A hierarchical approach to wrapper induction, Proceedings of the third annual conference on Autonomous Agents, p.190-197, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301191]
• 25: L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 1989.
• 26: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 27: K. Seymore, A. McCallum, and R. Rosenfeld. Learning hidden Markov model structure for information extraction. In AAAI 99 Workshop on Machine Learning for Information Extraction, 1999.
• 28: Charles Sutton , Khashayar Rohanimanesh , Andrew McCallum, Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data, Proceedings of the twenty-first international conference on Machine learning, p.99, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015422]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
data cleaning, information extraction, machine learning, text management, text segmentation