Thanks Mahesh, This is an impressive and useful summary. I will have misc comments as I get back on schedule, although my forthcoming trip to Romania and Eurolan may delay me even further.
One point I wanted to mention was that Michael Jordan (also of UC - Berkeley) gave an invited talk at ACL, and he made a rather nice point that summed up the differences between generative and discriminitive models. He said that statisticians referred to generative models sometimes as "frequentist" (because they are based on counting) and discriminitive models as "Bayesian" (because they incorporate prior probabilities that are not based on the observed data). This is familiar terminology to me, and there has been a long discususion in the statistics world about the relative merits of both - I think the conclusion of that argument, if there really has been a conclusion, is that Bayesian methods are great, if you have prior probabilities that are meaningful in some way. Otherwise, there isn't much difference between the two camps. I hope that we reach a point in discussing discriminative versus generative models where the conclusion is likewise expressable in similarly simple terms - right now there is a lot of jargon being associated with generative versus discriminitive, but I suspect it comes down to the same simple sorts of distinctions. BTW, Michael Jordan's talk was interesting to me as well since he talked about one of my favorite issues of late, that is how to determine how many clusters are "optimal" in an unsupervised clustering process. Interestingly enough I heard a talk at AAAI that included some discussion of the Jordan method (called Latent Dirchelet Association or something like that) so it all fits together in some way. I'll see if I can summarize any/all of this as well. More soon. Thanks! Ted On Tue, 12 Jul 2005, Mahesh Joshi wrote: > > 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 :) Thanks! I made it! -- Ted Pedersen http://www.d.umn.edu/~tpederse 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/
