{"id":29,"date":"2005-02-21T10:47:02","date_gmt":"2005-02-21T16:47:02","guid":{"rendered":"\/?p=29"},"modified":"2005-02-21T12:47:54","modified_gmt":"2005-02-21T18:47:54","slug":"problem-cross-validation","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=29","title":{"rendered":"Problem: Cross Validation"},"content":{"rendered":"

The essential problem here is the large gap between experimental observation and theoretical understanding.<\/p>\n

Method <\/strong> K-fold cross validation is a commonly used technique which takes a set of m<\/em> examples and partitions them into K<\/em> sets (“folds”) of size m\/K<\/em>. For each fold, a classifier is trained on the other folds and then test on the fold.<\/p>\n

Problem <\/strong> Assume only independent samples. Derive a classifier from the K classifiers with a small bound on the true error rate.<\/p>\n

Past Work<\/strong> (I’ll add more as I remember\/learn.)<\/p>\n

    \n
  1. Devroye<\/a>, Rogers, and Wagner analyzed cross validation and found algorithm specific bounds. Not all of this is online, but here is one paper<\/a>. <\/li>\n
  2. Michael Kearns<\/a> and Dana Ron<\/a> analyzed cross validation<\/a> and found that under additional stability assumptions the bound for the classifier which learns on all the data is not much worse than for a test set of size m\/K.<\/em><\/em><\/li>\n
  3. Avrim Blum, Adam Kalai<\/a>, and myself<\/a> analyzed cross validation<\/a> and found that you can do at least as well as a test set of size m\/K<\/em> with no additional assumptions using the randomized classifier which draws uniformly from the set of size K<\/em>. <\/a><\/li>\n
  4. Yoshua Bengio and Yves Grandvalet<\/a> analyzed cross validation<\/a> and concluded that there was no unbiased estimator of variance.<\/a><\/li>\n
  5. Matti K\u00c3\u00a4\u00c3\u00a4ri\u00c3\u00a4inen<\/a> noted that you can safely derandomize a stochastic classifier (such as one that randomizes over the K<\/em> folds) using unlabeled data<\/a> without additional assumptions.<\/li>\n<\/ol>\n

    Some Extreme Cases to Sharpen Intuition<\/strong><\/p>\n

      \n
    1. Suppose on every fold the learned classifier is the same. Then, the cross-validation error should behave something like a test set of size m<\/em>. This is radically superior to a test set of size m\/K<\/em>.<\/li>\n
    2. Consider leave-one-out cross validation. Suppose we have a “learning” algorithm that uses the classification rule “always predict the parity of the labels on the training set”. Suppose the learning problem is defined by a distribution which picks y=1<\/em> with probability 0.5<\/em>. Then, with probability 0.5<\/em>, all leave-one-out errors will be 0<\/em> and otherwise 1<\/em> (like a single coin flip).<\/li>\n<\/ol>\n

      (some discussion is here<\/a>)<\/p>\n

      Difficulty<\/strong> I consider this a hard problem. I’ve worked on it without success and it’s an obvious problem (due to the pervasive use of cross validation) that I suspect other people have considered. Analyzing the dependency structure of cross validation is quite difficult.<\/p>\n

      Impact<\/strong> On any individual problem, solving this might have only have a small impact due to slightly improved judgement of success. But, because cross validation is used extensively, the overall impact of a good solution might be very significant.<\/p>\n","protected":false},"excerpt":{"rendered":"

      The essential problem here is the large gap between experimental observation and theoretical understanding. Method K-fold cross validation is a commonly used technique which takes a set of m examples and partitions them into K sets (“folds”) of size m\/K. For each fold, a classifier is trained on the other folds and then test on … <\/p>\n

      Continue reading “Problem: Cross Validation”<\/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":[8,16],"tags":[],"class_list":["post-29","post","type-post","status-publish","format-standard","hentry","category-prediction-theory","category-problems"],"_links":{"self":[{"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/29","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=29"}],"version-history":[{"count":0,"href":"https:\/\/hunch.net\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions"}],"wp:attachment":[{"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/hunch.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}