Why inverse document frequency?

ABSTRACT

Inverse Document Frequency (IDF) is a popular measure of a word's importance. The IDF invariably appears in a host of heuristic measures used in information retrieval. However, so far the IDF has itself been a heuristic. In this paper, we show IDF to be optimal in a principled sense. We show that IDF is the optimal weight of a word with respect to minimization of a Kullback-Leibler distance suitably generalized to nonnegative functions which need not be probability distributions. This optimization problem is closely related to maximum entropy problem. We show that the IDF is the optimal weight associated with a word-feature in an information retrieval setting where we treat each document as the query that retrieves itself. That is, IDF is optimal for document self-retrieval.

REFERENCES

• 1: Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.158-169, June 28-July 01, 2000
• 2: I. Csiszar. 1991. Why least squares and maximum entropy? an axiomatic approach to inference for linear inverse problems. Annals of Statistics, 19:2032--2066.
• 3: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 4: John Lafferty, Stephen Della Pietra, and Vincent Della Pietra. 1997. Statistical learning algorithms based on Bregman distances. Canadian Workshop on Information Theory, pages 77--80.
• 5: Raymond Lau , Ronald Rosenfeld , Salim Roukos, Adaptive language modeling using the maximum entropy principle, Proceedings of the workshop on Human Language Technology, March 21-24, 1993, Princeton, New Jersey [doi>10.3115/1075671.1075695]
• 6: Kishore Papineni. 2000. A generalized Kullback Leibler distance and its minimization. IBM Research Report RC21815, August. Also available at www.research.ibm.com/resources/paper_search.html.
• 7: S. E. Robertson and K. Sparck Jones. 1976. Relevance weighting of search terms. Journal of the American Society for Information Science, pages 129--146, May-June.
• 8: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 9: K. Sparck Jones. 1973. Index term weighting. Information Storage and Retrieval, 9:619--633.
• 10: S. K. M. Wong and Y. Y. Yao. 1992. An information-theoretic measure of term specificity. Journal of the American Society for Information Science, 43:54--61.