{"id":84,"date":"2005-06-06T09:43:18","date_gmt":"2005-06-06T15:43:18","guid":{"rendered":"\/?p=84"},"modified":"2005-06-06T09:43:24","modified_gmt":"2005-06-06T15:43:24","slug":"exact-online-learning-for-classification","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=84","title":{"rendered":"Exact Online Learning for Classification"},"content":{"rendered":"<p>Jacob Abernethy and I have found a computationally tractable method for computing an optimal (or near optimal depending on setting) master algorithm combining expert predictions addressing <a href=\"https:\/\/hunch.net\/index.php?p=47\">this open problem<\/a>.  A draft is <a href=\"https:\/\/hunch.net\/~jl\/projects\/binning\/OnlineLearning.ps\">here<\/a>.  <\/p>\n<p>The effect of this improvement seems to be about a factor of <em>2<\/em> decrease in the regret (= error rate minus best possible error rate) for the low error rate situation.  (At large error rates, there may be no significant difference.)  <\/p>\n<p>There are some unfinished details still to consider:<\/p>\n<ol>\n<li>When we remove all of the approximation slack from online learning, is the result a satisfying learning algorithm, in practice?  I consider online learning is one of the more compelling methods of analyzing and deriving algorithms, but that expectation must be either met or not by this algorithm<\/li>\n<li>Some extra details: The algorithm is optimal given a small amount of side information (<em>k<\/em> in the draft).  What is the best way to remove this side information?  The removal is necessary for a practical algorithm.  One mechanism may be the <em>k->infinity<\/em> limit.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Jacob Abernethy and I have found a computationally tractable method for computing an optimal (or near optimal depending on setting) master algorithm combining expert predictions addressing this open problem. A draft is here. The effect of this improvement seems to be about a factor of 2 decrease in the regret (= error rate minus best &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/hunch.net\/?p=84\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Exact Online Learning for Classification&#8221;<\/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":[19],"tags":[],"class_list":["post-84","post","type-post","status-publish","format-standard","hentry","category-solutions"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/84","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=84"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/84\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=84"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=84"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=84"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}