tag:blogger.com,1999:blog-19803222.post8353335392148287640..comments2024-03-18T01:45:45.724-06:00Comments on natural language processing blog: Bootstrappinghalhttp://www.blogger.com/profile/02162908373916390369noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-19803222.post-22486548741975398632009-05-12T10:45:00.000-06:002009-05-12T10:45:00.000-06:00酒店經紀PRETTY GIRL 台北酒店經紀人 ,禮服店 酒店兼差PRETTY GIRL酒店公關 酒...酒店經紀PRETTY GIRL <A HREF="http://www.taipeilady.com/" REL="nofollow" TITLE="台北酒店經紀人">台北酒店經紀人</A> ,<A HREF="http://tw.myblog.yahoo.com/jw!qZ9n..6QEhhc0LkItOBm/" REL="nofollow" TITLE="禮服店">禮服店</A> 酒店兼差PRETTY GIRL<A HREF="http://www.mashow.org/" REL="nofollow" TITLE="酒店公關">酒店公關</A> 酒店小姐 彩色爆米花<A HREF="http://blog.xuite.net/jkl338801/blog/" REL="nofollow" TITLE="酒店兼職">酒店兼職</A>,酒店工作 彩色爆米花<A HREF="http://tw.myblog.yahoo.com/jw!BIBoU5SeBRs21nb_ajFpncbTqXds" REL="nofollow" TITLE="酒店經紀">酒店經紀</A>, <A HREF="http://mypaper.pchome.com.tw/news/thomsan/3/1310065116/20080905040949/" REL="nofollow" TITLE="酒店上班">酒店上班</A>,酒店工作 PRETTY GIRL<A HREF="http://tw.myblog.yahoo.com/jw!rybqykeeER6TH3AKz1HQ5grm/" REL="nofollow" TITLE="酒店喝酒">酒店喝酒</A>酒店上班 彩色爆米花<A HREF="http://mypaper.pchome.com.tw/news/jkl338801/" REL="nofollow" TITLE="台北酒店">台北酒店</A>酒店小姐 PRETTY GIRL<A HREF="http://www.mashow.org/" REL="nofollow" TITLE="酒店上班">酒店上班</A>酒店打工PRETTY GIRL<A HREF="http://www.tpangel.com/" REL="nofollow" TITLE="酒店打工">酒店打工</A>酒店經紀 彩色爆米花Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-19803222.post-87852772245473790482007-10-03T14:40:00.000-06:002007-10-03T14:40:00.000-06:00This is an article on the analysis of semi-superv...<A HREF="http://www.cs.sfu.ca/fas-info/cs/people/GradStudents/ghaffar1/personal/publications/uai_yar.pdf" REL="nofollow"> This </A> is an article on the analysis of semi-supervised learning in the same line as Abney's analysis.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-19803222.post-65542218409079426722007-10-02T08:55:00.000-06:002007-10-02T08:55:00.000-06:00Bootstrapping, self-training, semi-supervising etc...Bootstrapping, self-training, semi-supervising etc. have been tried for at least 4 decades (some OCR research from the 60's already had same idea).<BR/><BR/>The main problem with bootstrapping with a 'single' classifier was that the samples classified with high precision by the classifier are not uniformly distributed in the feature space. I.e., the errors made by a classifier are near the boundary, and if we throw these samples away the remaining samples don't add much to the existing classifier. <BR/><BR/>The novelty of some of the latest approaches (like co-training) is that they assume that there are two classifiers where the errors of each one are 'uniformly distributed' for the other. In NLP we can often find a natural analogue because some intrinsic properties of tokens (like its identity) are usually independent of its context given its label.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-19803222.post-60391521352892530302007-09-28T16:02:00.000-06:002007-09-28T16:02:00.000-06:00"... I hear that they work pretty well". Don't tru..."... I hear that they work pretty well". Don't trust everything you hear. As far as I know, no bootstrapping algorithm has ever been shown to work widely beyond its first reported application. In other words, the bootstrap parameters have been seriously overfitted to the initial application. Bootstrapping is intuitively a very cool idea, but we are missing a sketchy theoretical understanding of under what conditions it would work. Until we do, bootstrapping methods will be one-offs from which we can learn little.Fernando Pereirahttps://www.blogger.com/profile/05849361902113771573noreply@blogger.comtag:blogger.com,1999:blog-19803222.post-23934830179496463262007-09-28T10:33:00.000-06:002007-09-28T10:33:00.000-06:00In regards to the generalization problem, aren't t...In regards to the generalization problem, aren't there enough similarities between bootstrapping and boosting that could help explain the apparent lack of overfitting? In both instances, it appears you've got a weighted combination of classifiers that are specialized on certain areas of the problem space, and (at least in boosting) adding in additional features apparently does not lead immediately to overfitting.Erichttps://www.blogger.com/profile/12667686849634630528noreply@blogger.comtag:blogger.com,1999:blog-19803222.post-41084880951289454392007-09-28T07:57:00.000-06:002007-09-28T07:57:00.000-06:00hrm... the statement "bootstrapping works for the ...hrm... the statement "bootstrapping works for the same reason naive Bayes works" doesn't make sense to me. afaik, there's nothing that says that i couldn't bootstrap, say, with an svm or maxent model. but in these models, there's a huge chance that you'll just memorize the data and not generalize... i can easily construct distributions on which this will happen.<BR/><BR/>i think problem 1 is deeper than not getting off the ground: (to continue the analogy) i think we can actually start digging a hole. why doesn't this happen?<BR/><BR/>i think i'm starting to understand problem 2 and this may be kind of cool. essentially what bob seems to be saying (buried somewhere)---which i agree with---is that while D^0 (the distribution over sentences from the output of our rules) and D (the true distribution over sentences) maybe be different in an "adaptation" sense, by doing this "incrementally add a few more examples" thing, we're essentially constructing a sequence of distributions D^0, D^1, D^2, ..., D^T, where D^T = D.<BR/><BR/>looking at this from the domain adaptation perspective, this is actually quite interesting. i don't think anyone's looked at the problem in this way before. there may be some new D.A. algorithm lurking in there somewhere.<BR/><BR/>mark -- yes, this is weird. i don't have a good answer. one thing that i can suggest based on some work a student of mine is doing right now is that maybe what's going wrong is that when we usually do EM, we do it on a naive bayes model, which is very poorly calibrated for predicting probabilities (as bob points out). by doing this thresholding in bootstrapping, we may be effectively trying to remedy this problem....halhttps://www.blogger.com/profile/02162908373916390369noreply@blogger.comtag:blogger.com,1999:blog-19803222.post-23471032994928610712007-09-27T21:01:00.000-06:002007-09-27T21:01:00.000-06:00I confess I'm puzzled as to why these bootstrappin...I confess I'm puzzled as to why these bootstrapping methods seem to work better than EM. The informal story seems to be that with EM, the unlabeled data overwhelms the labeled data, which seems a reasonable enough explanation of why EM goes wrong. But then the question is: why doesn't this happen with bootstrapping, especially if it is just a kind of approximation to EM as Bob suggests.<BR/><BR/><A HREF="http://www.vinartus.net/spa/publications.html" REL="nofollow">Steven Abney</A> has thought a lot about these things, and has a <A HREF="http://www.vinartus.net/spa/03c-v7.pdf" REL="nofollow">Computational Linguistics article</A> and <A HREF="http://www.crcpress.com/shopping_cart/products/product_detail.asp?sku=C5599" REL="nofollow">new book</A> on this topic (I haven't seen the book yet) which may be worth looking at.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-19803222.post-73319462799841222632007-09-27T16:14:00.000-06:002007-09-27T16:14:00.000-06:00The short answer is that bootstrapping works for t...The short answer is that bootstrapping works for the same reason naive Bayes works -- tokens in docs are highly correlated with topics, and with even a few example docs, we can build a better-than-chance classifier. <BR/><BR/>Problem 1 worries that we might never get off the ground (continuing the "bootstrap" analogy). The reason this doesn't happen is that from a few set of seed words, we'll pick up some documents. From even a small set of docs, we can train a classifier that is not embarassing on 0/1 loss at high confidence. If this doesn't happen, we're grounded, so the annealing param needs to be set right here. If we do pick up more docs, we can build up flight speed by inferring that the words in those docs are associated with the categories. Many of these inferences will be wrong, but the reason it works is the same as for naive Bayes -- we're accumulating lots of little pieces of evidence in a voting scheme and the method's fairly low variance. These new docs are then enough to push some more relevant docs over the threshold, and then we're flying.<BR/><BR/>Problem 2 questions whether we can estimate a good distribution over all words. The answer is that just like for naive Bayes, it doesn't matter much if what we care about is 0/1 loss. The method's surprisingly robust because all the words tend to provide evidence. The lack of modeling correlation is why naive Bayes does so poorly on log (cross-entropy) loss compared to models that model dependency better (make fewer independence assumptions).<BR/><BR/>Unfortunately, like EM, we're left with a residual problem 3: we may get stuck in a local optimum. This indeed seems to happen in practice. Luckily, annealing through high precision examples helps push the initial steps of EM in the right direction. And if it doesn't we can just choose a different seed set.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-19803222.post-51440316608866609732007-09-27T11:29:00.000-06:002007-09-27T11:29:00.000-06:00The EM connection makes sense, but I didn't mentio...The EM connection makes sense, but I didn't mention it because it doesn't really address either of my concerns, or at best partially addresses only the first one :).<BR/><BR/>In a sense bootstrapping is a family of algorithms for solving semi-sup learning. I guess my concern---especially concern #2---is that we know that we can do much better than semi-sup learning when different domains are involved. (Thanks to John Blitzer for teaching us this.)halhttps://www.blogger.com/profile/02162908373916390369noreply@blogger.comtag:blogger.com,1999:blog-19803222.post-44162992920220264972007-09-27T11:17:00.000-06:002007-09-27T11:17:00.000-06:00I find the best way to understand the common appro...I find the best way to understand the common approach to "bootstrapping" in NLP (not to be confused with Efron's statistical <A HREF="http://www-stat.stanford.edu/software/bootstrap/index.html" REL="nofollow">bootstrap</A>) is to think of it as a highly quantized EM with annealing.<BR/><BR/>Specifically, you build an initial model, ideally with high precision. Then you run EM iterations with quantization. By that I mean that you quantize the expectations with a high threshold (e.g. [0.0,0.9] to 0 and (0.9,1.0] to 1). As you go, that threshold presumably gets lowered, making the whole thing a kind of annealing. <BR/><BR/>There are some good refs related to this issue: Nigam, McCallum and Mitchell's <A HREF="http://www.cs.umass.edu/~mccallum/papers/semisup-em.pdf" REL="nofollow">Semi-Supervised Text Classification Using EM</A>, and Neal and Hinton's <A HREF="http://citeseer.ist.psu.edu/neal98view.html" REL="nofollow">A View Of The EM Algorithm That Justifies Incremental, Sparse, And Other Variants</A>. The former discusses annealing and the latter winner-take-all versions of EM, which I'm suggesting modifying to winner-take-all if they won by a large enough margin.<BR/><BR/>Of course, this assumes an underlying classifier that can infer conditional estimates of categories given inputs. I suppose you can do this with Yarowsky-style <A HREF="http://citeseer.ist.psu.edu/yarowsky94decision.html" REL="nofollow">word list classifiers</A> by recasting them as decision trees and estimating probabilities.Anonymousnoreply@blogger.com