Least absolute deviations

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Least absolute deviations (LAD), also known as Least Absolute Errors (LAE), Least Absolute Value (LAV), or Least Absolute Residual (LAR) or the L1 norm problem, is a mathematical optimization technique similar to the popular least squares technique that attempts to find a function which closely approximates a set of data. In the simple case of a set of (x,y) data, the approximation function is a simple "trend line" in two-dimensional Cartesian coordinates. The method minimizes the sum of absolute errors (SAE) (the sum of the absolute values of the vertical "residuals" between points generated by the function and corresponding points in the data). The least absolute deviations estimate also arises as the maximum likelihood estimate if the errors have a Laplace distribution.

Formulation of the problem[edit]

Suppose that the data set consists of the points (xi, yi) with i = 1, 2, ..., n. We want to find a function f such that f(x_i)\approx y_i.

To attain this goal, we suppose that the function f is of a particular form containing some parameters which need to be determined. For instance, the simplest form would be linear: f(x) = bx + c, where b and c are parameters whose values are not known but which we would like to estimate. Less simply, suppose that f(x) is quadratic, meaning that f(x) = ax2 + bx + c, where a, b and c are not yet known. (More generally, there could be not just one explanator x, but rather multiple explanators, all appearing as arguments of the function f.)

We now seek estimated values of the unknown parameters that minimize the sum of the absolute values of the residuals:

 S = \sum_{i=1}^n |y_i - f(x_i)|.

Contrasting Least Squares with Least Absolute Deviations[edit]

The following is a table contrasting some properties of the method of least absolute deviations with those of the method of least squares (for non-singular problems).

Least Squares Regression Least Absolute Deviations Regression
Not very robust Robust
Stable solution Unstable solution
Always one solution Possibly multiple solutions

The method of least absolute deviations finds applications in many areas, due to its robustness compared to the least squares method. Least absolute deviations is robust in that it is resistant to outliers in the data. LAD gives equal emphasis to all observations, in contrast to OLS which, by squaring the residuals, gives more weight to large residuals, that is, outliers in which predicted values are far from actual observations. This may be helpful in studies where outliers do not need to be given greater weight than other observations. If it is important to give greater weight to outliers, the method of least squares is a better choice.

For a set of applets that demonstrate these differences, see the following site: http://www.math.wpi.edu/Course_Materials/SAS/lablets/7.3/73_choices.html

For a discussion of LAD versus OLS, see these academic papers and reports: http://www.econ.uiuc.edu/~roger/research/rq/QRJEP.pdf http://www.leeds.ac.uk/educol/documents/00003759.htm

Other properties[edit]

There exist other unique properties of the least absolute deviations line. In the case of a set of (x,y) data, the least absolute deviations line will always pass through at least two of the data points, unless there are multiple solutions. If multiple solutions exist, then the region of valid least absolute deviations solutions will be bounded by at least two lines, each of which passes through at least two data points. More generally, if there are k regressors (including the constant), then at least one optimal regression surface will pass through k of the data points.[1]:p.936

This "latching" of the line to the data points can help to understand the "instability" property: if the line always latches to at least two points, then the line will jump between different sets of points as the data points are altered. The "latching" also helps to understand the "robustness" property: if there exists an outlier, and a least absolute deviations line must latch onto two data points, the outlier will most likely not be one of those two points because that will not minimize the sum of absolute deviations in most cases.

One known case in which multiple solutions exist is a set of points symmetric about a horizontal line, as shown in Figure A below.

Figure A: A set of data points with reflection symmetry and multiple least absolute deviations solutions. The “solution area” is shown in green. The vertical blue lines represent the absolute errors from the pink line to each data point. The pink line is one of infinitely many solutions within the green area.

To understand why there are multiple solutions in the case shown in Figure A, consider the pink line in the green region. Its sum of absolute errors is some value S. If one were to tilt the line upward slightly, while still keeping it within the green region, the sum of errors would still be S. It would not change because the distance from each point to the line grows on one side of the line, while the distance to each point on the opposite side of the line diminishes by exactly the same amount. Thus the sum of absolute errors remains the same. Also, since one can tilt the line in infinitely small increments, this also shows that if there is more than one solution, there are infinitely many solutions.

Variations, extensions, specializations[edit]

The least absolute deviation problem may be extended to include multiple explanators, constraints and regularization, e.g., a linear model with linear constraints:[2]

minimize S(\mathbf{\beta}, b) = \sum_i | \mathbf{x}'_i \mathbf{\beta} + b - y_i |
subject to, e.g., \mathbf{x}'_1 \mathbf{\beta} + b - y_1 \leq  k

where \mathbf{\beta} is a column vector of coefficients to be estimated, b is an intercept to be estimated, xi is a column vector of the ith observations on the various explanators, yi is the ith observation on the dependent variable, and k is a known constant.

Regularization with LASSO may also be combined with LAD.[3]

Solving methods[edit]

Though the idea of least absolute deviations regression is just as straightforward as that of least squares regression, the least absolute deviations line is not as simple to compute efficiently. Unlike least squares regression, least absolute deviations regression does not have an analytical solving method. Therefore, an iterative approach is required. The following is an enumeration of some least absolute deviations solving methods.

Simplex-based methods are the “preferred” way to solve the least absolute deviations problem.[8] A Simplex method is a method for solving a problem in linear programming. The most popular algorithm is the Barrodale-Roberts modified Simplex algorithm. The algorithms for IRLS, Wesolowsky's Method, and Li's Method can be found in Appendix A of,[8] among other methods. Checking all combinations of lines traversing any two (x,y) data points is another method of finding the least absolute deviations line. Since it is known that at least one least absolute deviations line traverses at least two data points, this method will find a line by comparing the SAE (Smallest Absolute Error over data points) of each line, and choosing the line with the smallest SAE. In addition, if multiple lines have the same, smallest SAE, then the lines outline the region of multiple solutions. Though simple, this final method is inefficient for large sets of data.

Solving using linear programming[edit]

The problem can be solved using any linear programming technique on the following problem specification. We wish to

 \text{Minimize} \sum_{i=1}^n |y_i - a_0 - a_1x_{i1} - a_2x_{i2} - \cdots - a_kx_{ik}|

with respect to the choice of the values of the parameters a_0,..., a_k, where yi is the value of the ith observation of the dependent variable, and xij is the value of the ith observation of the jth independent variable (j = 1,...,k). We rewrite this problem in terms of artificial variables ui as

 \text{Minimize} \sum_{i=1}^n u_i
with respect to a_0,..., a_k and u_1,..., u_n
subject to
 u_i \ge y_i - a_0 - a_1x_{i1} - a_2x_{i2} - \cdots - a_kx_{ik} \,\ \,\ \,\ \,\ \,\ \text{for}  \,\ i=1,...,n
 u_i \ge -[y_i - a_0 - a_1x_{i1} - a_2x_{i2} - \cdots - a_kx_{ik}] \,\ \,\ \text{for} \,\ i=1,...,n.

These constraints have the effect of forcing each u_i to equal |y_i - a_0 - a_1x_{i1} - a_2x_{i2} - \cdots - a_kx_{ik}| upon being minimized, so the objective function is equivalent to the original objective function. Since this version of the problem statement does not contain the absolute value operator, it is in a format that can be solved with any linear programming package.

See also[edit]

References[edit]

  1. ^ Branham, R. L., Jr., "Alternatives to least squares", Astronomical Journal 87, June 1982, 928–937. [1] at SAO/NASA Astrophysics Data System (ADS)
  2. ^ Mingren Shi & Mark A. Lukas (March 2002). "An L1 estimation algorithm with degeneracy and linear constraints". Computational Statistics & Data Analysis 39 (1): 35–55. doi:10.1016/S0167-9473(01)00049-4. 
  3. ^ Li Wang, Michael D. Gordon & Ji Zhu (December 2006). "Proceedings of the Sixth International Conference on Data Mining". pp. 690–700. doi:10.1109/ICDM.2006.134.  |chapter= ignored (help)
  4. ^ I. Barrodale & F. D. K. Roberts (1973). "An improved algorithm for discrete L1 linear approximation". SIAM Journal on Numerical Analysis 10 (5): 839–848. Bibcode:1973SJNA...10..839B. doi:10.1137/0710069. JSTOR 2156318. 
  5. ^ E. J. Schlossmacher (December 1973). "An Iterative Technique for Absolute Deviations Curve Fitting". Journal of the American Statistical Association (Journal of the American Statistical Association, Vol. 68, No. 344) 68 (344): 857–859. doi:10.2307/2284512. JSTOR 2284512. 
  6. ^ G. O. Wesolowsky (1981). "A new descent algorithm for the least absolute value regression problem". Communications in Statistics – Simulation and Computation B10 (5): 479–491. doi:10.1080/03610918108812224. 
  7. ^ Yinbo Li and Gonzalo R. Arce (2004). "A Maximum Likelihood Approach to Least Absolute Deviation Regression". EURASIP Journal on Applied Signal Processing 2004 (12): 1762–1769. doi:10.1155/S1110865704401139. 
  8. ^ a b William A. Pfeil, Statistical Teaching Aids, Bachelor of Science thesis, Worcester Polytechnic Institute, 2006

External links[edit]