A Comparison of Criteria for Maximum Entropy/ Minimum Divergence Feature Selection

A Comparison of Criteria for Maximum Entropy / Minimum Divergence Feature Selection Adam Berger Carnegie Mellon University School of Computer Science Pittsburgh, PA 15232 aberger0cs.cmu.edu Abstract In this paper we study the gain, a naturally-arising statistic from the theory of MEMD modeling [2], as a figure of merit for selecting features for an MEMD language model. We compare the gain with two popular alternatives-empirical activation and mutual information-and argue that the gain is the preferred statistic, on the grounds that it directly measures a fea- ture's contribution to improving upon the base modeL Introduction Maximum entropy / minimum divergence (MEMD) modeling is a powerful technique for building statisti- cal models of linguistic phenomena. It has been applied to problems as diverse as machine translation [2], pars- ing [10], word morphology [5] and language modeling [6, 11, 3, 9]. The heart of the method is to ~ljoose a collection of informative features, each encodi'llg some linguistically significant event, and then to incorporate these features into a family of conditional models. A fundamental issue in applying this technique is the criterion used to select features. The work described in (3], for instance, incorporates every feature which either appears with above-threshold count in a training cor- pus, or which exhibits high mutual information. In [11] and [1], the authors select features based on a mutual information statistic. As we argue below, both these methods have drawbacks. In this paper, we examine a statistic for selecting MEMD model features, called the gain. The gain was introduced in [4], and studied in greater detail in [5] and [2]. We present intuition, theory and experimen- tal results for this statistic, as a criterion for selecting features for an MEMD language model. We believe our work marks the first time it has been used in MEMD language modeling, and the first side-by-side compar- ison with other selection criteria. Though our experi- mental results concern language models exclusively, we note that the gain can be used to select features for any MEMD model on a discrete space. The language model we present is based on depen- dency grammars. It is similar to, but extends upon, the work reported in [3]. Two important differences between that work and ours are that ours is a true 97 Harry Printz IBM Watson Research Center Yorktown Heights, NY 10598 printz@watson.ibm.com minimum-divergence model, and ours incorporates both link and trigger features. The paper is organized as follows. In Section Struc- ture of the Model we give a briefreview of MEMD models in general, and of our dependency grammar model in particular. In Section Linguistic Features we describe and motivate the types of features we chose to inves- tigate. In Section Expe1'imental Setup we describe our experimental procedure. In Section Selection of Fea- tU?·es we discuss feature selection; it is here that we develop the notion of gain. In Section Additivity of the Gain we discuss the additivity of gain, which measures the extent to which features contribute independently tO a modeL In Section …

Content truncated to 500 words