On the Relationship Between Binary Classification, Bipartite Ranking, and Binary Class Probability Estimation
We investigate the relationship between three fundamental problems in machine learning: binary classification, bipartite ranking, and binary class probability estimation (CPE). It is known that a good binary CPE model can be used to obtain a good binary classification model (by thresholding at 0.5), and also to obtain a good bipartite ranking model (by using the CPE model directly as a ranking model); it is also known that a binary classification model does not necessarily yield a CPE model. However, not much is known about other directions. Formally, these relationships involve regret transfer bounds. In this paper, we introduce the notion of weak regret transfer bounds, where the mapping needed to transform a model from one problem to another depends on the underlying probability distribution (and in practice, must be estimated from data). We then show that, in this weaker sense, a good bipartite ranking model can be used to construct a good classification model (by thresholding at a suitable point), and more surprisingly, also to construct a good binary CPE model (by calibrating the scores of the ranking model).
Summary. In more detail, this paper considers 
      BC (binary classification), BBR (binary bipartite ranking -- elements of 
      one class should all be ranked ahead of the other class), and CPE (binary 
      class probability estimation). As discussed in the short review, it is 
      shown that a consistent method for BBR, taken as a black box, can be used 
      to produce a consistent method for CPE and BC. The key technical point is 
      that the rankings must be "calibrated": a sample must be used to either 
      figure out where the positive/negative threshold should lie to solve BC, 
      or, in the more refined case of CPE, isotonic regression is used to find 
      the univariate monotonic map from ranking scores to probability estimates. 
      This paper provides these reductions (first with idealized 
      distributional access, and then via finite sample estimates), and closes 
      with some experiments which show that if one has an existing BBR model and 
      some extra samples, then it is better to train the specified reductions, 
      rather than just using the sample to train a CPE or BC model from scratch. 
      While the experimentation is not extensive, this is exactly the sort of 
      sanity check one would like to see. I will note that the use of 
      extra samples to calibrate a reduction of this type appears to be new 
      (that is, existing reductions which, say, solve BC and BBR via CPE, do not 
      need to use extra samples). Evaulation. While perhaps 
      not the world's most glamorous problem, it is foundational, and I am happy 
      to see progress. The solutions given above are sketched in the body, and 
      it is intuitive that some extra data is needed to adapt the ranking 
      values. I like the paper, but see one weakness. The definition of 
      reduction ("weak regret transfer bound") makes no restrictions on how the 
      new samples are used; in particular, whenever class B of problems is 
      learnable, then it is possible to reduce from B to any class A simply by 
      ignoring A and using the fresh samples to learn B directly. 
      Personally, I would like the authors to add some writing to 
      address the following points. To be clear, no request is being made for 
      new theorems or extensive extra work; simply I think the writing can both 
      clarify the above issue, and also pave the way for future work to deal 
      with it rigorously. 1. It should be stressed that reductions 
      should not be trivial in the sense above (ignoring the provided ranking), 
      and moreover that the two presented in this paper are not trivial in that 
      way. Moreover, the theorem statements in this paper directly provide the 
      reduction, and thus the reader can verify there is no cheating. I note 
      that the simulation section is a comparison to the start-from-scratch 
      approach, and thus the authors are aware of this issue, but I think it 
      deserves significant mention well before that section. 2. It might 
      be nice to explicitly state as an open problem the task of formalizing the 
      notion of "no cheating", for instance some sort of information theoretic 
      approach that asserts these reductions can use fewer samples than what 
      you'd need if provided only fresh examples and no ranking function. 
      3. As a step in this direction, it may be worth stressing that the 
      sample complexity of the binary classification reduction is very nice, 
      only paying for thresholds, and not for the full price of learning within 
      some potentially large class. Unfortunately, on the other hand, the 
      probability estimation reduction pays the full price of isotron, which 
      appears unnecessary since only the link function and not the direction are 
      used. Thus, another open problem may be reducing the sample complexity in 
      the reduction from probability estimation. One more comment, not 
      along the lines of the above "weakness". It would be nice if there were at 
      least a heuristic argument that extra examples are necessary (i.e., 
      "strong reductions" are impossible). For classification, I think it 
      suffices to fix a ranking and show that, without extra samples, one can 
      not decide which of two classifications (via thresholding) are better, and 
      thus samples are necessary. For probability estimation, similarly 
      considering two different links (from a fixed ranking) could work. 
      Detailed/Minor feedback. Introduction. I think the 
      intro can more cleanly identify the core strategy of the paper. For 
      example, by my reading, the basic outline is (1) these binary problems all 
      seem related, but we currently have gaps, then (2) the problem is that BBR 
      scores can be stretched out without tweaking the loss, which is not true 
      for BC and CPE, (3) so we should use a finite sample / distributional 
      access to adapt them, (4) for BC this is just a threshold and for CPE it's 
      just the link part of isotonic regression. If the authors like this 
      approach, I think honoring it could also hint how to break the long 
      paragraph in lines 64-81. Line 25. I think the abstract could be made 
      more accessible either by defining "Regret transfer bound" or by replacing 
      it with an explanation. Line 29. I am not sure this is surprising. 
      Line 43. I suggest also citing Tong Zhang's classification consistency 
      paper, which Bartlett/Jordan/McAuliffe cite heavily, and which appears in 
      for instance the Boucheron-Bousquet-Lugosi survey as the origination of 
      these rigorous convex -> zero/one bounds. Line 72. I think this 
      would be a good place to discuss the necessity of fresh samples (as 
      discussed above). Line 79. Regarding citations for this covering bound 
      (which follows by gridding the domain and range?), there are is probably 
      earlier work (by a number of decades) in the analysis literature...? 
      Line 89. This is nice and I think it could be stressed. Line 125. 
      I guess f should map to \bar R, but isotonic regression doesn't handle 
      this as far as I know, so I recommend switching to R. Line 177. I am 
      not sure the minimizer exists for arbitrary f. In particular, imagine that 
      error decreases as t approaches some t0, but then jumps up at t0. This 
      should be possible when the pushforward measure through f has a point mass 
      at t0. This sort of thing is abusing the fact that "sign" function decides 
      0 is positive. Line 215. Rather than "equal parts", might be good to 
      stress you can get away with using far fewer samples for the reduction 
      step. Line 219. I think this is a nice point. Line 269. Similarly 
      to Line 177, I wonder if this minimizer exists. Also, though I didn't 
      check your details carefully, I suppose your PAV procedure may be working 
      with Lipschitz functions (or at least continuous), in which case this 
      really may not be attained. I realized you have a reference here for the 
      minimum being attained, but that is a 57 page paper and I must admit I did 
      not check for distributional assumptions (ruling out the sorts of 
      non-Lebesgue-continuous measures I mention in Line 177). Line 278. I 
      suggest parentheses or something around OP3 so it's clearly referring to 
      line 269. Line 297. It might be good to mention isotron earlier, for 
      instance in the intro as I dicsussed above. Line 307. As mentioned 
      throughout, I think some discussion of the n^{-1/3} is warranted. If you 
      believe the bound is not tight, maybe state improvements as an open 
      problem. Line 341. Just like Remark 8, remark 19 is very nice (note, I 
      think the last sentence went astray?). Line 504. Missing an [h] to the 
      left of the leftmost equality. Line 602. I guess this 3 is "definition 
      3"; similar issues on Line 615.5.