Constrained monotone regression of ROC curves and histograms using splines and polynomials

Receiver operating characteristics (ROC) curves have the property that they start at (0,1) and end at (1,0) and are monotonically decreasing. Furthermore, a parametric representation for the curves is more natural, since ROCs need not be single valued functions: they can start with infinite slope. We show how to fit parametric splines and polynomials to ROC data with the end-point and monotonicity constraints. Spline and polynomial representations provide us a way of computing derivatives at various locations of the ROC curve, which are necessary in order to find the optimal operating points. Density functions are not monotonic but the cumulative density functions are. Thus in order to fit a spline to a density function, we fit a monotonic spline to the cumulative density function and then take the derivative of the fitted spline function. Just as ROCs have end-point constraints, the density functions have end-point constraints. Furthermore, derivatives of splines are spline functions and can be computed in closed form. Thus smoothing of histograms can also be treated as a constrained monotone regression problem. The algorithms were implementation in a mathematical programming language called AMPL and results on sample data sets are given