Mistake-Driven Learning in Text Categorization Export

@inproceedings{citeulike:3736016, abstract = {Learning problems in the text processing domain often map the text to a space whose dimensions are the measured features of the text, e.g., its words. Three characteristic properties of this domain are (a) very high dimensionality, (b) both the learned concepts and the instances reside very sparsely in the feature space, and (c) a high variation in the number of active features in an instance. In this work we study three mistake-driven learning algorithms for a typical task of this nature -- text categorization. We argue that these algorithms -- which categorize documents by learning a linear separator in the feature space -- have a few properties that make them ideal for this domain. We then show that a quantum leap in performance is achieved when we further modify the algorithms to better address some of the specific characteristics of the domain. In particular, we demonstrate (1) how variation in document length can be tolerated by either normalizing feature weights or by using negative weights, (2) the positive effect of applying a threshold range in training, (3) alternatives in considering feature frequency, and (4) the benefits of discarding features while training. Overall, we present an algorithm, a variation of Littlestone's Winnow, which performs significantly better than any other algorithm tested on this task using a similar feature set.}, author = {Dagan, I. and Karov, Y. and Roth, D.}, booktitle = {eprint arXiv:cmp-lg/9706006}, citeulike-article-id = {3736016}, citeulike-linkout-0 = {http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=1997cmp.lg....6006D}, citeulike-linkout-1 = {http://acl.ldc.upenn.edu/W/W97/W97-0306.pdf}, comment = {=== Representation of Text === Every (possible) word is an attribute and the occurrence of the word is the attributevalue (boolean). This implies: * very high dimensionality * instances are sparse * possibly many irrelevant attributes (intuition: very common words such as 'a', 'and', ... can not determine the class of a document) === Parametersettings === ==== Positive Winnow ==== each weight is initialized with theta / d (where theta is the threshold and d is the avg number of active features per instance) in this way initial scores are close to theta ==== Balanced Winnow ==== weights w+ are initialized with 2*theta / d weight w- are initialized with theta / d === Balanced Winnow Modifications === ==== Wide Margin ==== The separation is learned so that the mergin between the two classes is maximized. The proposed solution does not search the optimum (like in SVMs) and is a heuristic. The concept is implemented using two thresholds: theta+ and theta- * A sample belongs to class 0 if the linear comb. of weights and inputs is below theta- * A sample belongs to class 1 if the linear comb. of weights and inputs exceeds theta+ * if the line. comb is inside [theta-, theta+] then it is considered as a mistake Parametersettings: * theta- = 0.9 * theta+ = 1.1 ==== Irrelevant Features ==== Defined here as the features which have not contributed to many mistakes - those that were promoted or demoted at most once (possibly, with additional promotions and demotions which canceled each other, though). ==== Feature Selection (heuristic) ==== After some iterations (using a threshold) irrelevant features are discarded (the ones which have a value close to the init value). }, keywords = {balanced-winnow, feature-selection, text-categorization, wide-margin, winnow}, month = {June}, pages = {6006+}, posted-at = {2008-12-02 16:07:19}, priority = {0}, title = {Mistake-Driven Learning in Text Categorization}, url = {http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=1997cmp.lg....6006D}, year = {1997} }

TY - CONF ID - citeulike:3736016 L3 - citeulike-article-id:3736016 N2 - Learning problems in the text processing domain often map the text to a space whose dimensions are the measured features of the text, e.g., its words. Three characteristic properties of this domain are (a) very high dimensionality, (b) both the learned concepts and the instances reside very sparsely in the feature space, and (c) a high variation in the number of active features in an instance. In this work we study three mistake-driven learning algorithms for a typical task of this nature -- text categorization. We argue that these algorithms -- which categorize documents by learning a linear separator in the feature space -- have a few properties that make them ideal for this domain. We then show that a quantum leap in performance is achieved when we further modify the algorithms to better address some of the specific characteristics of the domain. In particular, we demonstrate (1) how variation in document length can be tolerated by either normalizing feature weights or by using negative weights, (2) the positive effect of applying a threshold range in training, (3) alternatives in considering feature frequency, and (4) the benefits of discarding features while training. Overall, we present an algorithm, a variation of Littlestone's Winnow, which performs significantly better than any other algorithm tested on this task using a similar feature set. TI - Mistake-Driven Learning in Text Categorization T2 - eprint arXiv:cmp-lg/9706006 SP - 6006 KW - balanced-winnow KW - feature-selection KW - text-categorization KW - wide-margin KW - winnow N1 - === Representation of Text === Every (possible) word is an attribute and the occurrence of the word is the attributevalue (boolean). This implies: * very high dimensionality * instances are sparse * possibly many irrelevant attributes (intuition: very common words such as 'a', 'and', ... can not determine the class of a document) === Parametersettings === ==== Positive Winnow ==== each weight is initialized with theta / d (where theta is the threshold and d is the avg number of active features per instance) in this way initial scores are close to theta ==== Balanced Winnow ==== weights w+ are initialized with 2*theta / d weight w- are initialized with theta / d === Balanced Winnow Modifications === ==== Wide Margin ==== The separation is learned so that the mergin between the two classes is maximized. The proposed solution does not search the optimum (like in SVMs) and is a heuristic. The concept is implemented using two thresholds: theta+ and theta- * A sample belongs to class 0 if the linear comb. of weights and inputs is below theta- * A sample belongs to class 1 if the linear comb. of weights and inputs exceeds theta+ * if the line. comb is inside [theta-, theta+] then it is considered as a mistake Parametersettings: * theta- = 0.9 * theta+ = 1.1 ==== Irrelevant Features ==== Defined here as the features which have not contributed to many mistakes - those that were promoted or demoted at most once (possibly, with additional promotions and demotions which canceled each other, though). ==== Feature Selection (heuristic) ==== After some iterations (using a threshold) irrelevant features are discarded (the ones which have a value close to the init value). AU - Dagan, I AU - Karov, Y AU - Roth, D PY - 1997/June// UR - http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=1997cmp.lg....6006D ER -