Tag Archives: linear programming

OPL code for quantile regression with B-splines

Posted on by

I found it to be an interesting exercises to write an optimization model using the Optimization Programming Language (OPL) provided by IBM ILOG CPLEX.

The quantile regression OPL code is provided in the sub-directory OPL in MathematicaForPrediction project at GitHub. The code can use only first order B-splines. The number of knots and the quantile are parameters to be specified. The reason to have only first order splines is because OPL provides only one type of piecewise functions — linear piecewise functions. OPL piecewise functions are somewhat awkward to interpret, but relatively easy to specify. (I will update this post with Mathematica code to parse and interpret them.) Since, of course, OPL’s piecewise{...} can be used to specify step functions I could have programmed zero order splines, but that would be only useful for educational purposes.

The code is short:

tuple Point {
float x;
float y;
};

// Data points provided by an external file
{Point} data = ...;

// Number of knots parameter
int k = 7;

// Quantile parameter
float q = 0.75;

float dataMin = min(d in data) d.x;
float dataMax = max(d in data) d.x;
float cLen = ( dataMax - dataMin ) / (k-1);

dvar float+ u[data];
dvar float+ v[data];
dvar float+ bs[1..k];

minimize sum(d in data) q*u[d] + sum(d in data) (1-q)*v[d];

subject to {

forall ( d in data ) {
(sum ( i in 1..k ) bs[i] * (piecewise{ 0-> dataMin + (i-2)*cLen; 1/cLen -> dataMin + (i-1)*cLen; -1/cLen -> dataMin + i*cLen; 0}( dataMin + (i-2)*cLen, 0) d.x) ) + u[d] - v[d] == d.y;
}
}

The code mentioned earlier provides print-outs of the piecewise, B-spline basis functions and the weights found for them. (The weighted sum of the B-spline basis functions gives the regression quantile.)

Quantile regression with B-splines

Posted on by

Last weekend I made two implementations of Quantile Regression (QR) calculation with B-spline bases. The first implementation is based on the Linear Programming (LP) formulation of the quantile minimization problem. The second implementation is a direct translation of the non-LP minimization formulation. (Mathematica’s functions LinearProgramming and Minimize are used respectively.)

The implementations are in the package QuantileRegression.m provided by the project MathematicaForPrediction at GitHub.

Because of the signature required by the QR implementation with B-splines and the returned results, I had to rename the previous QR implementation to QuantileRegressionFit and I named the new one (with the B-splines) QuantileRegression. I think the new names reflect better what the functions are doing.

Right now, to me the most interesting application of QR is detection of outliers in time series and reconstruction of conditional density functions. Below is a demonstration of using QR for outlier detection.

Consider this data:
Atlanta temperature 2006-2013 changed with y = y+Sqrt[x]

which was generated with the code:

tempData = WeatherData["Atlanta", "Temperature", {{2006, 1, 1}, {2013, 12, 31}, "Day"}];
tempPData = tempData;
tempPData[[All, 1]] = DateDifference[tempData[[1, 1]], #, "Day"] & /@ tempData[[All, 1]];
tempPData[[All, 1]] = tempPData[[All, 1, 1]];
tempPData[[All, 2]] = Sqrt[tempPData[[All, 1]]] + tempPData[[All, 2]];

(I took the temperature in Atlanta, GA, USA for the last 7 years and modified the data with the formula Yi = sqrt(Xi) + Yi .)

Here is a plot with five regression quantiles calculated using B-splines for the quantiles {0.02, 0.2, 0.4, 0.6, 0.8, 0.98}:
Regression quantiles for Atlanta temperature 2006-2013 changed with y = y+Sqrt[x]

Here is another plot with the 0.02 and 0.98 regression quantiles outlining the data:
Outline with regression quantiles for Atlanta temperature 2006-2013 changed with y = y+Sqrt[x]

The regression quantiles were computed with the command:

qFuncs = QuantileRegression[tempPData, 44, {0.02, 0.2, 0.4, 0.6, 0.8, 0.98}]

Note that in order to get satisfactory results, the only tuning value I had to choose is for the second parameter, which in this case specifies the number of B-spline basis knots. The second parameter can also be a list of knots. The option InterpolationOrder specifies the splines order. (By default InterpolationOrder->3.)

Update, 2015.07.04

This blog post was written with an older version of Mathematica, version 9. (The current is 10.1.)  Mathematica 10 uses different format for the WeatherData results — TimeSeries object are returned, which use QuantityArray and/or Quantity around the numerical values like temperature, wind speed, etc. 

Below is given code that runs with Mathematica 10.1. (The only change is the second line of the data loading part.)

1. Data load:

tempData = WeatherData["Atlanta", "Temperature", {{2006, 1, 1}, {2013, 12, 31}, "Day"}];
tempData = Transpose[{Normal[tempData["Dates"]], Normal[tempData["Values"]] /. Quantity[q_, _] :> q}];
tempPData = tempData;
tempPData[[All, 1]] = DateDifference[tempData[[1, 1]], #, "Day"] & /@ tempData[[All, 1]];
tempPData[[All, 1]] = tempPData[[All, 1, 1]];
tempPData[[All, 2]] = Sqrt[tempPData[[All, 1]]] + tempPData[[All, 2]];

2. Regression quantiles computation:

qFuncs = QuantileRegression[tempPData, 44, {0.02, 0.2, 0.4, 0.6, 0.8, 0.98}];

3. Plots:

gr1 = ListPlot[tempPData];
gr2 = Plot[
Evaluate[Through[qFuncs[x]]], {x, Min[tempPData[[All, 1]]],
Max[tempPData[[All, 1]]]}, PlotPoints -> 1200,
PerformanceGoal -> "Speed"];
jan1Pos = Position[DateList /@ tempData[[All, 1]], {_, 1, 1, ___}][[All, 1]];
Show[{gr1, gr2}, PlotRange -> All, Axes -> False, Frame -> True
, GridLines -> {jan1Pos, FindDivisions[{##}, 10] &},
GridLinesStyle -> Directive[GrayLevel[0.8], Dashed],
AspectRatio -> 1/3]