{"id":47,"date":"2005-03-18T20:16:39","date_gmt":"2005-03-19T02:16:39","guid":{"rendered":"\/?p=47"},"modified":"2005-03-18T20:17:51","modified_gmt":"2005-03-19T02:17:51","slug":"binomial-weighting","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=47","title":{"rendered":"Binomial Weighting"},"content":{"rendered":"

Suppose we have a set of classifiers c<\/em> making binary predictions from an input x<\/em> and we see examples in an online fashion. In particular, we repeatedly see an unlabeled example x<\/em>, make a prediction y’<\/em>(possibly based on the classifiers c<\/em>), and then see the correct label y<\/em>. <\/p>\n

When one of these classifiers is perfect, there is a great algorithm available: predict according to the majority vote over every classifier consistent with every previous example. This is called the Halving algorithm. It makes at most log2<\/sub> |c|<\/em> mistakes since on any mistake, at least half of the classifiers are eliminated.<\/p>\n

Obviously, we can’t generally hope that the there exists a classifier which never errs. The Binomial Weighting algorithm<\/a> is an elegant technique allowing a variant Halving algorithm to cope with errors by creating a set of virtual classifiers for every classifier which occasionally disagree with the original classifier. The Halving algorithm on this set of virtual classifiers satisfies a theorem of the form:
\n

errors of binomial weighting algorithm less than minc<\/sub> f(number of errors of c, number of experts)<\/center><\/p>\n

The Binomial weighting algorithm takes as a parameter the maximal minimal number of mistakes of a classifier. By introducing a “prior” over the number of mistakes, it can be made parameter free. Similarly, introducing a “prior” over the set of classifiers is easy and makes the algorithm sufficiently flexible for common use.<\/p>\n

However, there is a problem. The minimal value of f()<\/em> is 2<\/em> times the number of errors of any classifier, regardless of the number of classifiers. This is frustrating because a parameter-free learning algorithm taking an arbitrary “prior” and achieving good performance on an arbitrary (not even IID) set of examples is compelling for implementation and use, if<\/em> we had a good technique for removing the factor of 2<\/em>. How can we do that?<\/p>\n

See the weighted majority algorithm<\/a> for an example of a similar algorithm which can remove a factor of 2 using randomization and at the expense of introducing a parameter. There are known techniques for eliminating this parameter, but they appear not as tight (and therefore practically useful) as introducing a “prior” over the number of errors.<\/p>\n","protected":false},"excerpt":{"rendered":"

Suppose we have a set of classifiers c making binary predictions from an input x and we see examples in an online fashion. In particular, we repeatedly see an unlabeled example x, make a prediction y’(possibly based on the classifiers c), and then see the correct label y. When one of these classifiers is perfect, … <\/p>\n

Continue reading “Binomial Weighting”<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,18,16],"tags":[],"class_list":["post-47","post","type-post","status-publish","format-standard","hentry","category-online","category-papers","category-problems"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/47","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=47"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/47\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=47"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=47"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}