Linear Regression with Tolerance

Question

I want to do simple 2D linear regression across a set of points, however, the 'y' or second coordinate is not precise and a narrow range of values is acceptable. For example, my points might be |index| value | |:---:|:-------------:| | 1 | [0.8 : 1.2] | | 2 | [3.6 : 4.4] | | 3 | [8.2 : 9.8] | So if I want to model those points using a small polynomial function and linear regression to find the multipliers for each term, I would consider a model producing:

index	value
1	1
2	4
3	9

and another model producing:

index	value
1	0.9
2	3.9
3	8.8

to be equally good for my purposes. Is there a name for such a regression algorithm that does that?

Update: I want to clarify that the range given for the second coordinate or y-value is not due to measurement inaccuracy. I am not trying to model a measurement inaccuracy. In my case, the range is due to the second coordinate literally being an interval rather than a point (this specific application is finance and the interval is the bid/ask spread) and I just want a model for a curve that will pass somewhere through the points. Yes, I could just take the median and use those points for regression, but what I really want is a model for a curve that passes through the points where my error is measured as the distance of the curve from the outside of the closest interval endpoint. If the curve goes though the interval (y-coord) at the given x-coordinate, then the error for that model for that point is 0.

I suspect that there is a modified regression algorithm that can handle this, but that it likely relies on optimization rather than direct solution through matrix multiplication. I'm looking for the name of that algorithm.

Update #2: I found this website helpful:

http://polynomialregression.drque.net/math.html

Still digesting it... Regression usually involves over-constrained situations where solving the system of equations involves more equations or constraints than free variables. Therefore, unless the equations or points are linearly-dependent, it's not possible to find a perfect fit and not possible to directly solve for a solution via solving the system of equations or invert a matrix to find a solution for the coefficients. As the website describes above, this type of regression usually involves taking partial derivatives and computing the gradient of the cost function with respect to each coefficient and then walking towards the global minimum. I think the issue with finding a solution for an interval rather than a point is that the interval necessarily introduces conditionality into the cost function or rather the cost function needs to take into account both end points of the interval with 3 cases: 1. Point outside but closer to one end point, 2. Point outside, but closer to the other end point, 3. point is inside the interval in which case the error for that point is 0. It's simply not possible to take the partial derivative of such a function because that function is discontinuous. However, I am considering the last comment below which might work -- Perform regression using midpoints for interval, but adjust the error function to account for the intervals. That could work. I'll try that approach. Other approach for small number of coefficients and points use regression of midpoints for the first point, then use a genetic algorithm / optimization to directly fine tune the coefficients with custom cost function.

Answer 1

This is what in Econometrics goes under the name of "errors in variables model": see for instance the Wikipedia. The important point to bear in mind is that you may experience inconsistency if the errors in the variables are correlated iwth the regression disturbance. Unless this is the case, I think you can safely take a representative value of your interval and proceed as usual, otherwise you might resort to techniques like instrumental variables.

Answer 2

The re-phrasing of your problem suggests another approach. For each $x_i$ you appear to have $(y_{i,low}, y_{i,high})$. You might consider two sets of points in $R^2$, respectively made of $(x_i, y_{i,low})$ and $(x_i, y_{i,high})$, $i=1,\ldots,n$, and search for a (linear, quadratic, whatever...) separator doing discriminant analysis. If your points can be nearly separated by a low order function, that might work all right. You might want to check linear discriminant analysis and support vector machines (SVM). I have a feeling, though, that what I suggested in a previous answer might work best.