Using NLP based features for machine learning

Alexandre, Thanks for the response !

1] I do understand some classifiers are immune to noise but I want to avoid the Garbage in- Garbage out scenario viz. giving incorrect POS tags and grammatical sequences may lead to incorrect results (though classification may work but results won't be generalizable).

2] W.r.t. to POS tags, I want my input feature to be a POS tag sequence (completely complete) of the document (of any length) and hence don't want to restrict their length/size on n. The length of my documents significantly vary and hence, this is one requirement which I may not be able to relax. Even if I am, I would like to pose a generic question (assuming it's not) as to how to incorporate such sequences as "features" in a ML classifier. The number of permutations/combinations of such a sequence would be very huge and hence the traditional method of counting (and incorporating) such occurrences as features would lead to an exponential increase in feature dimension which would lead me to apply a new feature reduction algorithm on the feature space. I would like to avoid that scenario as after the decision boundary is formed by the classifier I would like to know the best POS tag sequences (I want to avoid doing this manually and encode them as features) ranked by their discriminatory power which led to successful classification. Therefore, I thought string kernels would be a nice way forward.

3] W.r.t. to Grammatical relations, I wouldn't like to limit the subtrees for reasons similar to POS tag sequences. Tree Kernels (as mentioned in the link in my post) provide a good alternative to avoid such tasks. Is there any specific reason not to use them?

4] Obviously, using different kernels for different types of features( POS tags, Grammatical relations aren't the ONLY features for my classifier, other features include standard statistical features like average word length/sentence, number of function words etc.) introduces a whole new ( and probably rather complex) dimension. Something which currently I am not exposed to. Is it possible to have different kernels for different features in the same classification task? OR Should I use three different classifiers depending on the kernels and combine their output to another classifier and make a decision?

PS: Thanks for bearing with me !

(1) To protect against over fitting the best way is to use separate validation and test sets. Doing that you shouldn't have to worry about feature noise

(2) String kernels are completely uninteresting if you want an interpretable model because they are completely black-box. All a string kernel model will tell you is that such and such documents are the more relevant to classification. If you use POS n-grams (or up-to-n-grams), what you get is essentially a finitist approximation to string kernels, but one that lets you treat directly each substring as its own feature. After training a regularized linear classifier you can inspect the weights it assigns to different POS n-grams and see which are more relevant, or you can even use the lasso (l1 regularization) or elastic net (l1 and l2 regularization, which generalizes better than the lasso) to bring down the weights of most features and see only the relevant ones when you actually inspect your feature vector. Then you can trim your feature set to use only features similar to those and train again (with l2 regularization) to get the best classifier you can get. To repeat: the best way of finding which ones are relevant is indeed dealing with them explicitly, since string kernels are completely opaque, and then inspecting the weight vector, possibly using the lasso to do model selection.

(3) Tree kernels are just like string kernels, so the argument I gave in (2) applies: they are opaque (you can't tell from a classifier which subtrees do matter) and can be well approximated by lots of features corresponding to finite subtrees.

(4) Combining different kernels in the same classifier is a much harder problem (called kernel learning or multiple kernel learning). There's been a lot of recent work in this area, trying to reliably tune different kernels for a single prediction task, but the overall complexity of training is a lot higher and the results are not as good. There was a workshop in nips 2009 where you can get more references. Overall, for what you seem to want, I'd say there are two ways you can go: one is to use an unstructured linear model (logistic regression or svms, basically) and use a lot of features (tag up-to-n-grams, subtrees of up-to-n length) and model selection (for interpretability; l2 regularized logistic regression is known to perform well with a ridiculously high number of irrelevant features in nlp problems, against some theoretical work) to find out what matters. The second way is to explicitly use a structured model, like a CRF, and make the POS tags and dependency tree part of the model itself, such as is done in this paper: http://www.blogger.com/aclweb.org/anthology-new/N/N10/N10-1120.pdf (Dependency Tree-based Sentiment Classification using CRFs with Hidden Variables). If your problem is binary classification, however, such a model should be overkill and you're probably better with a featuritis model.

Fundamentally, string and tree kernels are nice if what you're after is performance, but for non trivial tasks specific features are usually better, since with these kernels you're effectively averaging over all possible features, which decreases interpretative power and makes it sure you will need a lot of documents to represent the simpler decision boundaries (since you will effectively need to "average out" most of the infinite features availiable to these models).

Alexandre, Thanks once again !

1] Great!

2] Thanks for clearing the String/Tree Kernel doubt. In order to make this discussion more generic let us consider two scenarios:

2.a] Using String/Tree Kernels as I don't want to find the most discriminatory sequences Since, this is opaque and will require multiple kernel learning for the prediction tax Shogun (http://www.fml.tuebingen.mpg.de/raetsch/suppl/shogun) Machine Learning toolbox seems a good implementation. One point I would like to stress is that though my dataset size is small, the real-world setting may have millions of instances. I could only get so much annotated! Hence, I am worried about the performance of the classifier. I haven't ruled out the possibility of MKL as yet.

2.b] Not using String/Tree Kernels to find the distinguishing sequences Limiting the size of POS tags and Subtrees sounds a good idea. However, I have a question regarding the choice of the classifier. I guess I may have to used LibLinear (http://www.csie.ntu.edu.tw/~cjlin/liblinear/index.html) instead of LibSVM with a linear kernel? Does SVM provide me an option for l1 or l2 regularization? I am yet not clear on how I could use the output provided by a SVM to "interpret" the model. I know one could get the distance of a point from the hyperplane. (http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f4151). I also see some work done by FML-MPI to improve the "interpretability of predictive classifiers like SVMs" . FIRM (http://www.fml.tuebingen.mpg.de/raetsch/members/raetsch/bibliography/ZKSR2009) seems to be one such algorithm. I also read the CRF + dependency tree paper but I can't use the same (in the current task) as I don't have such phrase/word level annotations (in this paper sentiment is annotated or calculated using a lexicon). Unfortunately, in the current setting I guess this may not help.

3] I read the paper link posted by Awais (Sentiment Classification Using Word Sub-sequences and Dependency Sub-trees) and they use the most frequent word sequences and Dependency sub-trees. How does the idea come across to you? My first reaction to it is that it may be missing some important features as my understanding is that frequent doesn't necessarily mean discriminator and vice-versa. If I'm wrong, I was wondering if I can mix-match and use string/tree kernels for classification and use the frequent subsequence/tree mining algorithms from the paper to characterize my class.

:-)

1. a) Just to clarify, you only need MKL if you want to use more than one out of string kernels, tree kernels, and other features. Shogun seems nice. The size (and prediction complexity) of the SVM with kernels depends linearly on the training set size, so if your training set is small this shouldn't be an issue.

2. b) I like to use logistic regression instead of support vector machines precisely because of interpretability. I use a variant of the standard theano implementation (you'll find it in deeplearning.net/tutorial ) that I tuned to support elastic net and optimization by L-BFGS (which gives better results on small data sets than stochastic graident descent). To interprete the weights of any linear classifier (logistic regression and svm included) you need to have access to the classifier itself (and I'm not sure how to do it with either liblinear or libsvm, but with the theano implementation it's trivial). What you're interested in are the features whose weights have the highest modulos. If the weights are positive, the features are generally good indicators of the positive class; same for negative weights. If the weights are negative the features are highly predictive of the negative class. This requires that all features have roughly the same mean and variance, but this is very easy to ensure in an nlp setting, since most of them are binary. My code is really hacky, but it should be easy to extend the theano implementation to do what I did. You can get a good, fast implementation of logistic regression (that does support model selection, although not with the lasso) at http://www.cs.utah.edu/~hal/megam/ , and a faster general linear classifier implementation at http://hunch.net/~vw/ ; both make it relatively easy to tune the hyperparameters and inspect the weights.

3) Yes, this is an issue with looking at only the most frequent X when doing classification, for all values of X. If you can afford it's better to do some model selection during training instead of doing that, since the model selection will take care of the irrelevant features (which might just as well be frequent, i.e. stopwords) by itself.

Thanks Alexandre !

1 a] Yes. I will have to use more than one.

2 b] If needed (and appropriate) I will contact you later for your code. I will also in the mean time delve more into logistic regression. I guess megam should be good even if no lasso. What say? The Yahoo research link looks more like an online learning algorithm. I will currently stay away from it.

3] Thanks for buttressing me on this point. However, by model selection I hope you mean interpretability of the model built with the training data and tested on the test data.