Summary of tutorial on Max Margin Methods for NLP The tutorial titled "Max-Margin Methods for NLP: Estimation, Structure, and Applications" was presented by Dan Klein and Ben Taskar from UC Berkeley. Below are some summary notes from my records - to the best of my knowledge and understanding. Please note that the amount of content I have here is not necessarily proportional to the importance of topics on which the tutorial focused.
The presentation is available at http://www.cs.berkeley.edu/~taskar/pubs/max-margin-acl05-tutorial.pdf, and this summary has a couple of references to slide numbers in this presentation. Broadly, the tutorial was divided into two parts. PART 1 ====== The first part presented by Dan Klein covered the concepts related to flat classification, linear classifiers and some details about Support Vector Machines. It advocated for discriminative methods over generative methods with the primary reason that discriminative methods do not make any assumptions about the real distribution of observed data. The independence assumption in generative methods like Naive Bayes classifier for example buy simplicity at the expense of losing information about interaction among features, since we assume features to be independent. This also results in the fact that there are no relative weights associated with the features, like in discriminative methods. While many problems in NLP can be posed as classification problems that can be solved via discriminative methods, one important aspect to consider is that most of the NLP problems are multi-class classification problems and not binary classification. So for example in Word Sense Disambiguation it is common to have more that two senses in the sense inventory and in case of parsing there are several possible parse trees possible for a sentence, among which the best should be chosen by a discriminative method. The basic idea in max-margin methods underlies binary classification of objects. So typically the method to deal with multi-class problems is to construct multiple binary classifiers (either one-against-all, or pairwise one-to-one) and combining their results using a probabilistic method. With this in background, the tutorial presented a method to handle multi-class classification without the construction of multiple binary classifiers. The method essentially involves learning different weights for each target class (for the same set of features) and constructing a wider weight vector out of them. This is better illustrated on slide #[7]. The outcome is that while evaluating any new feature set for assigning a class, a weight vector specific to that class will be used to evaluate the confidence of the assignment. How exactly are the weight vectors decided for each class is not exactly clear to me. It may perhaps involve considering the dependence between features given one specific class, and then coming up with the weights. The tutorial explained the simple max-margin model of a perceptron. The way a perceptron learns weights of various features is by adjusting an initial weight vector (normally all zeroes) to correctly classify every instance in the training set. The weight vector is updated by the amount of error encountered in misclassifying a training example (weighted by a margin, which should ideally be maximal). There are various aspects involved in selecting the weights. One is to minimize the error on training data. Another is to maximize the margin of separation between the classes. Achieving the first condition of minimal error is not necessarily the best solution since that may translate to over-fitting the model to the training data and causing it to be less generalized to better perform on unknown data. The second condition of maximum margin however improves upon the minimal error solution by allowing better generalization. This might result in some error in the training data classification. Specifically for support vector machines, the margin approach also brings in the aspect of the solution being dependent only on the critical training data points known as support vectors, with the other features getting zero weights. I think this perhaps also means that with a lot of features thrown at an SVM learner, it is going to choose the most critical ones automatically for you (the support vectors) and the other features will be getting zero weights. The next important thing to realize is that maximizing margin (just the value of it) might be simply possible by choosing a larger valued weight vector (or equivalently scaling the feature space). So, the solution for this is to keep the margin fixed at a standard value of 1 and finding the minimal weight vector for classifying the training data. This is how the problem of maximizing the margin gets converted into finding the minimal value of the weight vector. One more step forward is to allow for mis-classified examples in training data. Every mis-classified training example adds an error term known as slack variable to the objective function to be minimized - thus making it incur a penalty. The tutorial then covered some details about loss functions which provide a lower bound on the improvement that the confidence score of the predicted correct class should have on other candidates. The specific functions that were covered were the zero-one loss, hinge loss and log loss. The basic formulation that is achieved for a support vector machine by applying the condition of minimal weight vector with a fixed margin of 1, is a quadratic programming problem. It consists of a quadratic expression that is to be minimized subject to a set of linear constraints. This is known as the primal form of the problem. This form is theoretically possible to solve, but very complex because of the way the constraints are formulated in this original form. The solution to this is the use of Lagrange multipliers to convert the constraints into a more manageable form. A nice explanation of Lagrange multipliers is given in http://www.slimy.com/~steuard/tutorials/Lagrange.html. The resultant problem still remains a quadratic programming problem but with a simpler set of constraints. This is known as the dual form of the problem. After getting the problem in dual form, the major bottleneck of SVMs is the training time due to the numerical quadratic optimization step involved. Several ways to optimize this have been proposed - most of them dealing with optimizations of sub-problems of the bigger numerical quadratic programming problem and then combining the solutions in some incremental manner. One of the more widely used such algorithm is the Sequential Minimal Optimization algorithm proposed by John Platt from Microsoft (http://research.microsoft.com/users/jplatt/smo-book.pdf). To state it in an over-simplified manner, this algorithm incrementally finds the optimal solution of two training data points at a time while maintaining the overall constraints for optimization. There in no numerical quadratic programming done - instead a simple analytical step is used to find the optimal co-efficients of constraint equations. PART 2 ====== The second part of the tutorial was conducted by Ben Taskar and this I think was mostly based on his Ph.D. dissertation titled "Learning Structured Prediction Models: A Large Margin Approach" (http://www.cs.berkeley.edu/~taskar/pubs/thesis.pdf). The focus here was on extending the discriminative methods to exploit the structured nature of problems in NLP. An example that quickly made sense to me was that of character recognition (on slide #[57]). The point to understand is that without the global knowledge of what has been recognized so far, identifying the character "c" in "brace" will be very difficult as it is very similar to the earlier character "r". But the knowledge that we have seen the characters "bra" so far combined with other form of knowledge related to English vocabulary will perhaps make the decision easier and more accurate. This is a "sequential" structure of the problem. Similarly in parsing, there is a "recursive" structure - knowing what sub-trees have we already identified to be specific phrase classes and eliminating use of these phrase classes for other sub-trees by knowledge of grammar. In a bilingual word alignment task there is a "combinatorial" structure - i.e. perhaps(?) if we have already paired some words together we need not consider them for further alignment - thus simplifying our decisions. My feel about this part was that it went into very specific details about the adaptation of discriminative methods to such structural problems, and therefore was less accessible to the general audience (including myself) with lesser background in that area. This is not in any way meant to say that the tutorial was not appropriate or adequate. It was a very nice introduction to this field of max margin methods and I enjoyed it very much. The problems handled in the second half by the structured methods are very interesting indeed and I look forward to gain a better understanding about them, primarily with the help of Ph.D. dissertation of Ben Taskar. Finally, I think there will certainly be some loose ends in the summary above and probably some things that are wrong since I may have misunderstood them. I would therefore be happy to answer any questions if possible and to hear corrections, suggestions or feedback. Thanks! Mahesh PS: Kudos to everyone who managed to read through this entire never-ending summary :) __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/nlpatumd/ <*> To unsubscribe from this group, send an email to: [EMAIL PROTECTED] <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/
