The maximum entropy method for analyzing retrieval measures

ABSTRACT

We present a model, based on the maximum entropy method, for analyzing various measures of retrieval performance such as average precision, R-precision, and precision-at-cutoffs. Our methodology treats the value of such a measure as a constraint on the distribution of relevant documents in an unknown list, and the maximum entropy distribution can be determined subject to these constraints. For good measures of overall performance (such as average precision), the resulting maximum entropy distributions are highly correlated with actual distributions of relevant documents in lists as demonstrated through TREC data; for poor measures of overall performance, the correlation is weaker. As such, the maximum entropy method can be used to quantify the overall quality of a retrieval measure. Furthermore, for good measures of overall performance (such as average precision), we show that the corresponding maximum entropy distributions can be used to accurately infer precision-recall curves and the values of other measures of performance, and we demonstrate that the quality of these inferences far exceeds that predicted by simple retrieval measure correlation, as demonstrated through TREC data.

REFERENCES

• 1: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 2: Chris Buckley , Ellen M. Voorhees, Evaluating evaluation measure stability, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.33-40, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345543]
• 3: William S. Cooper, On selecting a measure of retrieval effectiveness. Part I., Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: B. Dervin and M. S. Nilan. Information needs and use. In Annual Review of Information Science and Technology, volume~21, pages 3--33, 1986.
• 6: Warren R. Greiff , Jay M. Ponte, The maximum entropy approach and probabilistic IR models, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.246-287, July 2000 [doi>10.1145/352595.352597]
• 7: E. Jaynes. On the rationale of maximum entropy methods. In Proc.IEEE, volume 70, pages 939--952, 1982.
• 8: E. T. Jaynes. Information theory and statistical mechanics: Part i. Physical Review 106, pages 620--630, 1957a.
• 9: E. T. Jaynes. Information theory and statistical mechanics: Part ii. Physical Review 108, page 171, 1957b.
• 10: Yuri Kagolovsky , Jochen R. Moehr, Current Status of the Evaluation of Information Retrieval, Journal of Medical Systems, v.27 n.5, p.409-424, October 2003 [doi>10.1023/A:1025603704680]
• 11: Paul B. Kantor , Jung Jin Lee, The maximum entropy principle in information retrieval, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.269-274, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253225]
• 12: David D. Lewis, Evaluating and optimizing autonomous text classification systems, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.246-254, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215366]
• 13: Robert M. Losee, When information retrieval measures agree about the relative quality of document rankings, Journal of the American Society for Information Science, v.51 n.9, p.834-840, July 2000 [doi>10.1002/(SICI)1097-4571(2000)51:9<834::AID-ASI60>3.3.CO;2-T]
• 14: K. Nigam, J. Lafferty, and A. McCallum. Using maximum entropy for text classification. In IJCAI-99 Workshop on Machine Learning for Information Filtering, pages 61--67, 1999.
• 15: D. Pavlov, A. Popescul, D. M. Pennock, and L. H. Ungar. Mixtures of conditional maximum entropy models. In T. Fawcett and N. Mishra, editors, ICML, pages 584--591. AAAI Press, 2003.
• 16: Steven J. Phillips , Miroslav Dudík , Robert E. Schapire, A maximum entropy approach to species distribution modeling, Proceedings of the twenty-first international conference on Machine learning, p.83, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015412]
• 17: Vijay Raghavan , Peter Bollmann , Gwang S. Jung, A critical investigation of recall and precision as measures of retrieval system performance, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.205-229, July 1989 [doi>10.1145/65943.65945]
• 18: A. Ratnaparkhi and M. P. Marcus. Maximum entropy models for natural language ambiguity resolution, 1998.
• 19: Tefko Saracevic, Evaluation of evaluation in information retrieval, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.138-146, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215351]
• 20: C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal 27, pages 379--423 & 623--656, 1948.
• 21: N. Wu. The Maximum Entropy Method. Springer, New York, 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Experimentation, Measurement, Theory

Keywords:
average precision, evaluation, maximum entropy, modeling, precision-recall curve