Text categorization for multi-page documents: a hybrid naive Bayes HMM approach

ABSTRACT

Text categorization is typically formulated as a concept learning prob lem where each instance is a single isolated document. In this paper we are interested in a more general formulation where documents are organized as page sequences, as naturally occurring in digital libraries of scanned books and magazines. We describe a method for classifying pages of sequential OCR text documents into one of several assigned categories and suggest that taking into account contextual information provided by the whole page sequence can significantly improve classification accuracy. The proposed architecture relies on hidden Markov models whose emissions are bag-of-words according to a multinomial word event model, as in the generative portion of the Naive Bayes classifier. Our results on a collection of scanned journals from the Making of America project confirm the importance of using whole page sequences. Empirical evaluation indicates that the error rate (as obtained by running a plain Naive Bayes classifier on isolated page) can be roughly reduced by half if contextual information is incorporated.

REFERENCES

• 1: The metadata engine project. http://meta-e.uibk.ac.at, 2001.
• 2: Y. Bengio and P. Frasconi. An input output HMM architecture. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems 7, pages 427-434. MIT Press, 1995.
• 3: D. A. Bicknese. Measuring the accuracy of the OCR in the Making of America. Report available at moa.umdl.umich.edu/moaocr.html, 1998.
• 4: W. Cavnar and J. Trenkle. N-Gram based text categorization. In Prof. of the 3rd Annual Symposium on Document Analysis and Information Retrieval, pages 161-175, Las Vegas, NV, 1994.
• 5: Eugene Charniak, Statistical Language Learning, MIT Press, Cambridge, MA, 1994
• 6: W. W. Cohen. Text categorization and relational learning. In Proceedings of the Twelfth International Conference on Machine Learning, Lake Tahoe, California, 1995.
• 7: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum-likelihood from incomplete data via the EM algorithm. Journal of Royal Statistical Society B, 39:1-38, 1977.
• 8: Michelangelo Diligenti , Paolo Frasconi , Marco Gori, Image Document Categorization Using Hidden Tree Markov Models and Structured Representations, Proceedings of the Second International Conference on Advances in Pattern Recognition, p.147-156, March 11-14, 2001
• 9: 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
• 10: David Heckerman, Bayesian Networks for Data Mining, Data Mining and Knowledge Discovery, v.1 n.1, p.79-119, 1997 [doi>10.1023/A:1009730122752]
• 11: Finn V. Jensen , F.V. V. Jensen , F. V. Jensen, Introduction to Bayesian Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 12: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 13: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 14: Markus Junker , Rainer Hoch, Evaluating OCR and Non-OCR Text Representations for Learning Document Classifiers, Proceedings of the 4th International Conference on Document Analysis and Recognition, p.1060-1066, August 18-20, 1997
• 15: T. Kalt, A New Probabilistic Model of Text Classification and Retrieval TITLE2:, University of Massachusetts, Amherst, MA, 1998
• 16: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 17: David D. Lewis , William A. Gale, A sequential algorithm for training text classifiers, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.3-12, July 03-06, 1994, Dublin, Ireland
• 18: D. Lewis and M. Ringuette. Comparison of two learning algorithms for text categorization. In Proc. 3rd Annual Symposium on Document Analysis and Information Retrieval, 1994.
• 19: Helmut Lucke, Bayesian Belief Networks as a tool for stochastic parsing, Speech Communication, v.16 n.1, p.89-118, Jan. 1995 [doi>10.1016/0167-6393(94)00046-D]
• 20: Andrew Kachites McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, Automating the Construction of Internet Portals with Machine Learning, Information Retrieval, v.3 n.2, p.127-163, July 2000 [doi>10.1023/A:1009953814988]
• 21: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 22: Hwee Tou Ng , Wei Boon Goh , Kok Leong Low, Feature selection, perception learning, and a usability case study for text categorization, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.67-73, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 23: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 24: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 25: L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257-286, 1989.
• 26: E. Shaw and S. Blumson. Online searching and page presentation at the University of Michigan. D-Lib Magazine, July/August 1997. url: www.dlib.org/dlib/july97/america/07shaw.html.
• 27: Padhraic Smyth , David Heckerman , Michael I. Jordan, Probabilistic independence networks for hidden Markov probability models, Neural Computation, v.9 n.2, p.227-269, Feb. 15, 1997 [doi>10.1162/neco.1997.9.2.227]
• 28: Andreas Stolcke , Stephen M. Omohundro, Hidden Markov Model} Induction by Bayesian Model Merging, Advances in Neural Information Processing Systems 5, [NIPS Conference], p.11-18, November 30-December 03, 1992
• 29: Yiming Yang , Christopher G. Chute, An example-based mapping method for text categorization and retrieval, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.252-277, July 1994 [doi>10.1145/183422.183424]
• 30: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING

General Terms:
Design, Documentation, Experimentation, Human Factors, Management, Measurement, Performance, Theory

Keywords:
hidden Markov models, multi-page documents, naive Bayes classifier, text categorization