{"id":17,"date":"2005-02-07T20:58:31","date_gmt":"2005-02-08T02:58:31","guid":{"rendered":"\/?p=17"},"modified":"2005-02-08T21:46:49","modified_gmt":"2005-02-09T03:46:49","slug":"the-state-of-the-reduction","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=17","title":{"rendered":"The State of the Reduction"},"content":{"rendered":"

What?<\/strong> Reductions are machines which turn solvers for one problem into solvers for another problem.
\nWhy?<\/strong> Reductions are useful for several reasons.<\/p>\n

    \n
  1. Laziness<\/strong>. Reducing a problem to classification make at least 10 learning algorithms available to solve a problem. Inventing 10 learning algorithms is quite a bit of work. Similarly, programming a reduction is often trivial, while programming a learning algorithm is a great deal of work.<\/li>\n
  2. Crystallization<\/strong>. The problems we often want to solve in learning are worst-case-impossible, but average case feasible. By reducing all problems onto one or a few primitives, we can fine tune these primitives to perform well on real-world problems with greater precision due to the greater number of problems to validate on.<\/li>\n
  3. Theoretical Organization<\/strong>. By studying what reductions are easy vs. hard vs. impossible, we can learn which problems are roughly equivalent in difficulty and which are much harder.<\/li>\n<\/ol>\n

    What we know now<\/strong>.<\/p>\n

    Typesafe reductions<\/strong>. In the beginning, there was the observation that every complex object on a computer can be written as a sequence of bits. This observation leads to the notion that a classifier (which predicts a single bit) can be used to predict any complex object. Using this observation, we can make the following statements:<\/p>\n

      \n
    1. Any prediction problem which can be broken into examples can be solved with a classifier.<\/li>\n
    2. In particular, reinforcement learning can be decomposed into examples given a generative model (see Lagoudakis & Parr<\/a> and Fern, Yoon, & Givan<\/a>).<\/li>\n<\/ol>\n

      This observation also often doesn’t work well in practice, because the classifiers are sometimes wrong, so one of many classifiers are often wrong.<\/p>\n

      Error Transform Reductions<\/strong>. Worrying about errors leads to the notion of robust reductions (= ways of using simple predictors such as classifiers to make complex predictions). Error correcting output codes<\/a> were proposed in analogy to coding theory. These were analyzed in terms of error rates on training sets<\/a> and general losses on training sets<\/a>. The robustness can be (more generally) analyzed with respect to arbitrary test distributions<\/a>, and algorithms optimized with respect to this notion are often very simple and yield good performance<\/a>. Solving created classification problems up to error rate e<\/em> implies:<\/p>\n

        \n
      1. Solving importance weighed classifications up to error rate eN<\/em> where N<\/em> is the expected importance. Costing<\/a><\/li>\n
      2. Solving multiclass classification up to error rate 4e<\/em> using ECOC. Error limiting reductions paper<\/a><\/li>\n
      3. Solving Cost sensitive classification up to loss 2eZ<\/em> where Z<\/em> is the sum of costs. Weighted All Pairs algorithm<\/a><\/li>\n
      4. Finding a policy within expected reward (T+1)e\/2<\/em> of the optimal policy for T<\/em> step reinforcement learning with a generative model. RLgen paper<\/a><\/li>\n
      5. The same statement holds much more efficiently when the distribution of states of a near optimal policy is also known. PSDP paper<\/a><\/li>\n<\/ol>\n

        A new problem arises: sometimes the subproblems created are inherently hard, for example when estimating class probability from a classifier<\/a>. In this situation saying “good performance implies good performance” is vacuous.<\/p>\n

        Regret Transform Reductions<\/strong> To cope with this, we can analyze how good performance minus the best possible performance (called “regret”) is transformed under reduction. Solving created binary classification problems to regret r<\/em> implies:<\/p>\n

          \n
        1. Solving importance weighted regret up to r N<\/em> using the same algorithm as for errors. Costing<\/a>\n
        2. Solving class membership probability up to l2<\/sub> regret 2r<\/em>. Probing paper<\/a><\/li>\n
        3. Solving multiclass classification to regret 4 r0.5<\/sup><\/em>. SECOC paper<\/a><\/li>\n
        4. Predicting costs in cost sensitive classification up to l2<\/sub> regret 4r<\/em> SECOC again<\/a><\/li>\n
        5. Solving cost sensitive classification up to regret 4(r Z)0.5<\/sup><\/em> where Z<\/em> is the sum of the costs of each choice. SECOC again<\/a><\/li>\n<\/li>\n<\/ol>\n

          There are several reduction-related problems currently being worked on which I’ll discuss in the future.<\/p>\n","protected":false},"excerpt":{"rendered":"

          What? Reductions are machines which turn solvers for one problem into solvers for another problem. Why? Reductions are useful for several reasons. Laziness. Reducing a problem to classification make at least 10 learning algorithms available to solve a problem. Inventing 10 learning algorithms is quite a bit of work. Similarly, programming a reduction is often … <\/p>\n

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