{"id":1253,"date":"2010-03-15T16:53:06","date_gmt":"2010-03-15T22:53:06","guid":{"rendered":"http:\/\/hunch.net\/?p=1253"},"modified":"2010-03-15T16:53:06","modified_gmt":"2010-03-15T22:53:06","slug":"the-efficient-robust-conditional-probability-estimation-problem","status":"publish","type":"post","link":"https:\/\/hunch.net\/?p=1253","title":{"rendered":"The Efficient Robust Conditional Probability Estimation Problem"},"content":{"rendered":"

I’m offering a reward of $1000 for a solution to this problem. This joins the cross validation problem<\/a> which I’m offering a $500 reward<\/a> for. I believe both of these problems are hard but plausibly solvable, and plausibly with a solution of substantial practical value. While it’s unlikely these rewards are worth your time on an hourly wage basis, the recognition for solving them definitely should be \ud83d\ude42<\/p>\n

The Problem<\/h2>\n

The problem is finding a general, robust, and efficient mechanism for estimating a conditional probability P(y|x)<\/em> where robustness and efficiency are measured using techniques from learning reductions. <\/p>\n

In particular, suppose we have access to a binary regression oracle B<\/em> which has two interfaces—one for specifying training information and one for testing. Training information is specified as B(x’,y’)<\/em> where x’<\/em> is a feature vector and y’<\/em> is a scalar in [0,1]<\/em> with no value returned. Testing is done according to B(x’)<\/em> with a value in [0,1]<\/em> returned.<\/p>\n

A learning reduction consists of two algorithms R<\/em> and R-1<\/sup><\/em> which transform examples from the original input problem into examples for the oracle and then transform the oracle’s predictions into a prediction for the original problem.<\/p>\n

The algorithm R<\/em> takes as input a single example (x,y)<\/em> where x<\/em> is an feature vector and y<\/em> is a discrete variable taking values in {1,…,k}<\/em>. R<\/em> then specifies a training example (x’,y’)<\/em> for the oracle B<\/em>. R<\/em> can then create another training example for B<\/em> based on all available information. This process repeats some finite number of times before halting without returning information.<\/p>\n

A basic observation is that for any oracle algorithm, a distribution D(x,y)<\/em> over multiclass examples and a reduction R<\/em> induces a distribution over a sequence (x’,y’)*<\/sup><\/em> of oracle examples. We collapse this into a distribution D'(x’,y’)<\/em> over oracle examples by drawing uniformly from the sequence.<\/p>\n

The algorithm R-1<\/sup><\/em> takes as input a single example (x,y)<\/em> and returns a value in [0,1]<\/em> after using (only) the testing interface of B<\/em> zero or more times.<\/p>\n

We measure the power of an oracle and a reduction according to squared-loss regret. In particular we have:
\n


\nreg(D,R-1<\/sup>)=E(x,y)~ D<\/sub>[(R-1<\/sup>(x,y)-D(y|x))2<\/sup>] <\/em><\/center>
\n and similarly letting mx’<\/sub>=E(x’,y’)~ D’<\/sub>[y’]<\/em>.
\n

\nreg(D’,B)=E(x’,y’)~ D’<\/sub>(B(x’) – mx’<\/sub>)2<\/sup><\/em><\/center><\/p>\n

The open problem is to specify R<\/em> and R-1<\/sup><\/em> satisfying the following theorem:
\n
\nFor all multiclass distributions D(x,y)<\/em>, for all binary oracles B<\/em>: The computational complexity of R<\/em> and R-1<\/sup><\/em> are O(log k)<\/em>
\nand


\nreg(D,R-1<\/sup>) < = C<\/em> reg<\/em>(D’,B)<\/em><\/center>
\nwhere C<\/em> is a universal constant.
\n<\/strong>
\nAlternatively, this open problem is satisfied by proving there exists no deterministic algorithms R,R-1<\/sup><\/em> satisfying the above theorem statement.<\/p>\n

Motivation<\/h2>\n

The problem of conditional probability estimation is endemic to machine learning applications. In fact, in some branches of machine learning, this is simply considered “the problem”. Typically conditional probability estimation is done in situations where the conditional probability of only one bit is required, however there are a growing number of applications where a well-estimated conditional probability over a more complex object is required. For example, all known methods for solving general contextual bandit problems require knowledge of or good estimation of P(a | x)<\/em> where a<\/em> is an action.<\/p>\n

There is a second intrinsic motivation which is matching the lower bound. No method faster than O(log k)<\/em> can be imagined because the label y<\/em> requires log2<\/sub> k<\/em> bits to specify and hence read. Similarly it’s easy to prove no learning reduction can provide a regret ratio with C<1<\/em>.<\/p>\n

The motivation for using the learning reduction framework to specify this problem is a combination of generality and the empirical effectiveness in application of learning reductions. Any solution to this will be general because any oracle B<\/em> can be plugged in, even ones which use many strange kinds of prior information, features, and active multitask hierachical (insert your favorite adjective here) structure.<\/p>\n

Related Results<\/h2>\n

The state of the art is summarized here<\/a> which shows it’s possible to have a learning reduction satisfying the above theorem with either:<\/p>\n

    \n
  1. C<\/em> replaced by (<\/em>log2<\/sub> k)2<\/sup><\/em> (using a binary tree structure)<\/li>\n
  2. or the computational time increased to O(k)<\/em> (using an error correcting code structure).<\/li>\n<\/ol>\n

    Hence, answering this open problem in the negative shows that there is an inherent computation vs. robustness tradeoff.<\/p>\n

    There are two other closely related problems, where similar analysis can be done.<\/p>\n

      \n
    1. For multiclass classification, where the goal is predicting the most likely class, a result analogous to the open problem is provable using error correcting tournaments<\/a>.<\/li>\n
    2. For multiclass classification in a partial label setting, no learning reduction can provide a constant regret guarantee<\/a>.<\/li>\n<\/ol>\n

      Silly tricks that don’t work<\/h2>\n

      Because Learning reductions are not familiar to everyone, It’s helpful to note certain tricks which do not work here to prevent false leads and provide some intuition.<\/p>\n

      Ignore B<\/em>‘s predictions and use your favorite learning algorithm instead.<\/strong><\/p>\n

      This doesn’t work, because the quantification is for all D<\/em>. Any specified learning algorithm will have some D<\/em> on which it has nonzero regret. On the other hand, because R<\/em> calls the oracle at least once, there is a defined induced distribution D’<\/em>. Since the theorem must hold for all D<\/em> and B<\/em>, it must hold for a D<\/em> your specified learning algorithm fails on and for a B<\/em> for which reg(D’,B)=0<\/em> implying the theorem is not satisfied.<\/p>\n

      Feed random examples into B<\/em> and vacuously satisfy the theorem by making sure that the right hand side is larger than a constant.<\/strong><\/p>\n

      This doesn’t work because the theorem is stated in terms of squared loss regret rather than squared loss. In particular, if the oracle is given examples of the form (x’,y’)<\/em> where y’<\/em> is uniformly at random either 0<\/em> or 1<\/em>, any oracle specifying B(x’)=0.5<\/em> has zero regret.<\/p>\n

      Feed pseudorandom examples into B<\/em> and vacuously satisfy the theorem by making sure that the right hand side is larger than a constant.<\/strong><\/p>\n

      This doesn’t work, because the quantification is “for all binary oracles B<\/em>”, and there exists one which, knowing the pseudorandom seed, can achieve zero loss (and hence zero regret).<\/p>\n

      Just use Boosting to drive the LHS to zero.<\/strong><\/p>\n

      Boosting theorems require a stronger oracle—one which provides an edge over some constant baseline for each invocation. The oracle here is not limited in this fashion since it could completely err for a small fraction of invocations.<\/p>\n

      Take an existing structure, parameterize it, randomize over the parameterization, and then average over the random elements.<\/strong><\/p>\n

      Employing this approach is not straightforward, because the average in D’<\/em> is over an increased number of oracle examples. Hence, at a fixed expected (over oracle examples) regret, the number of examples allowed to have a large regret is increased.<\/p>\n","protected":false},"excerpt":{"rendered":"

      I’m offering a reward of $1000 for a solution to this problem. This joins the cross validation problem which I’m offering a $500 reward for. I believe both of these problems are hard but plausibly solvable, and plausibly with a solution of substantial practical value. While it’s unlikely these rewards are worth your time on … <\/p>\n

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