Evaluation and Extension of Maximum Entropy Models with Inequality Constraints

Evaluation and Extension of Maximum Entropy Models with Inequality Constraints Jun’ichi Kazama† kazama@is.s.u-tokyo.ac.jp †Department of Computer Science University of Tokyo Hongo 7-3-1, Bunkyo-ku, Tokyo 113-0033, Japan Jun’ichi Tsujii†‡ tsujii@is.s.u-tokyo.ac.jp ‡CREST, JST (Japan Science and Technology Corporation) Honcho 4-1-8, Kawaguchi-shi, Saitama 332-0012, Japan Abstract A maximum entropy (ME) model is usu- ally estimated so that it conforms to equal- ity constraints on feature expectations. However, the equality constraint is inap- propriate for sparse and therefore unre- liable features. This study explores an ME model with box-type inequality con- straints, where the equality can be vio- lated to reflect this unreliability. We eval- uate the inequality ME model using text categorization datasets. We also propose an extension of the inequality ME model, which results in a natural integration with the Gaussian MAP estimation. Experi- mental results demonstrate the advantage of the inequality models and the proposed extension. 1 Introduction The maximum entropy model (Berger et al., 1996; Pietra et al., 1997) has attained great popularity in the NLP field due to its power, robustness, and suc- cessful performance in various NLP tasks (Ratna- parkhi, 1996; Nigam et al., 1999; Borthwick, 1999). In the ME estimation, an event is decomposed into features, which indicate the strength of certain aspects in the event, and the most uniform model among the models that satisfy: E˜p[fi] = Ep[fi], (1) for each feature. E˜p[fi] represents the expectation of feature fi in the training data (empirical expec- tation), and Ep[fi] is the expectation with respect to the model being estimated. A powerful and ro- bust estimation is possible since the features can be as specific or general as required and does not need to be independent of each other, and since the most uniform model avoids overfitting the training data. In spite of these advantages, the ME model still suffers from a lack of data as long as it imposes the equality constraint (1), since the empirical expecta- tion calculated from the training data of limited size is inevitably unreliable. A careful treatment is re- quired especially in NLP applications since the fea- tures are usually very sparse. In this study, text cat- egorization is used as an example of such tasks with sparse features. Previous work on NLP proposed several solutions for this unreliability such as the cut-off, which sim- ply omits rare features, the MAP estimation with the Gaussian prior (Chen and Rosenfeld, 2000), the fuzzy maximum entropy model (Lau, 1994), and fat constraints (Khudanpur, 1995; Newman, 1977). Currently, the Gaussian MAP estimation (com- bined with the cut-off) seems to be the most promis- ing method from the empirical results. It succeeded in language modeling (Chen and Rosenfeld, 2000) and text categorization (Nigam et al., 1999). As described later, it relaxes constraints like E˜p[fi] − Ep[fi] = λi σ2 , where λi is the model’s parameter. This study follows this line, but explores the fol- lowing box-type inequality constraints: Ai ≥ E˜p[fi] − Ep[fi] ≥ −Bi, Ai, Bi > 0. (2) Here, the equality can be …

Content truncated to 500 words