What is the convex hull in ROC curve?

Question

I'm reading a paper about ROC and PR curves. They mentioned the ROC convex hull but they don't define it or say what it is. Can someone please tell me the meaning of it? What is a convex hull in ROC curve and what does it mean? Is it just the ROC curve?!!

Edit:

from the paper: "In ROC space the convex hull is a crucial idea. Given a set of points in ROC space, the convex hull must meet the following three criteria". So it is a "crucial idea". That's not a definition. It's like saying: a car is important for humans. A car has four wheels and color. But it doesn't say that a car is a vehicle.

Answer 1

The paper gives the following definition, which is pretty much a constructive one:

1. Linear interpolation is used between adjacent points.
2. No point lies above the final curve.
3. For any pair of points used to construct the curve, the line segment connecting them is equal to or below the curve.

The main problem with this one is it's not a particularly intuitive thing.

So let's look at Wikipedia:

Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X.

This is pretty good, and carries some intuition, but (unless you have experience of convex sets) doesn't really give much of an idea of what it's like.

It also gives the commonly used (and intuitive) "rubber band" explanation of a convex hull:

For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X

This intuitive explanation must be slightly modified for ROC curves, because of the way they're defined - the convex hull of an ROC fulfill the conditions for an ROC. So if we take a stretched "rubber band" which is fixed at (0,0) and (1,1) and the middle is pulled up and to the left so that it sits "outside" (0,1), and release it so that it "catches" on the points, then between (0,0) and (1,1) the rubber band will form the convex hull of the ROC:

Hopefully, now, the intent of the definitions should be clearer.

Answer 2

After reading the same paper and digging around, I believe that the importance of the convex hull is that it represents the "optimal" classifier, given a set of ROC points.

What does "optimal" mean in this case?

This paper by Scott et. al. "describes a procedure which will create from two existing classifiers a new one whose performance (in terms of its ROC) lies on a line connecting the performance of its two components. This is done by choosing one or other of the classifiers at random and using its result." [1]

So in essence, given a set of ROC points from multiple classifiers, it is possible to construct the "optimal" classifier that lies on the convex hull of all of these ROC points.

[1]: I haven't actually read the paper, I've only read a summary of it here: http://www0.cs.ucl.ac.uk/staff/ucacbbl/roc/

Answer 3

Taking the convex hull of the ROC curve points is just a way of enforcing a constraint that the estimated ROC curve be convex (concave down in this case). It is equivalent to assuming that the distributions of the marker in the cases and in the controls are unimodal. In situations where this assumption is reasonable then imposing the convexity constraint is warranted.