{"id":181,"date":"2006-04-06T17:21:32","date_gmt":"2006-04-06T23:21:32","guid":{"rendered":"http:\/\/hunch.net\/?p=181"},"modified":"2006-04-08T16:57:19","modified_gmt":"2006-04-08T22:57:19","slug":"bounds-greater-than-1","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=181","title":{"rendered":"Bounds greater than 1"},"content":{"rendered":"

Nati Srebro<\/a> and Shai Ben-David<\/a> have a paper<\/a> at COLT<\/a> which, in the appendix, proves something very striking: several previous error bounds are always<\/em> greater than 1.<\/p>\n

Background<\/strong> One branch of learning theory focuses on theorems which<\/p>\n

    \n
  1. Assume samples are drawn IID from an unknown distribution D<\/em>.<\/li>\n
  2. Fix a set of classifiers<\/li>\n
  3. Find a high probability bound on the maximum true error rate (with respect to D<\/em>) as a function of the empirical error rate on the training set.\n<\/li>\n<\/ol>\n

    Many of these bounds become extremely complex and hairy. <\/p>\n

    Current<\/strong> Everyone working on this subject wants “tighter bounds”, however there are different definitions of “tighter”. Some groups focus on “functional tightness” (getting the right functional dependency between the size of the training set and a parameterization of the hypothesis space) while others<\/a> focus on “practical tightness” (finding bounds which work well on practical problems). (I am definitely in the second camp.)<\/p>\n

    One of the dangers of striving for “functional tightness” is that the bound can depend on strangely interrelated parameters. In fact, apparently these strange interrelations can become so complex that they end up always<\/em> larger than 1 (some bounds here<\/a> and here<\/a>). <\/p>\n

    It seems we should ask the question: “Why are we doing the math?” If it is just done to get a paper accepted under review, perhaps this is unsatisfying. The real value of math comes when it guides us in designing learning algorithms. Math from bounds greater than 1 is a dangerously weak motivation for learning algorithm design.<\/p>\n

    There is a significant danger in taking this “oops” too strongly. <\/p>\n

      \n
    1. There exist some reasonable arguments (not made here) for aiming at functional tightness.<\/li>\n
    2. The value of the research a person does is more related to the best they have done than the worst.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

      Nati Srebro and Shai Ben-David have a paper at COLT which, in the appendix, proves something very striking: several previous error bounds are always greater than 1. Background One branch of learning theory focuses on theorems which Assume samples are drawn IID from an unknown distribution D. Fix a set of classifiers Find a high … <\/p>\n

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