LARS Library Least Angle Regression Stagewise Library.pdf

LARS Library: Least Angle Regression Stagewise Library Frank Vanden Berghen IRIDIA, Universite? Libre de Bruxelles fvandenb@iridia.ulb.ac.be November 22, 2005 Let’s assume that we want to perform a simple identification task. Let’s assume that you have a set of n + 1 measures (x(1), x(2), . . . , x(n), y). We want to find a function (or a model) that predicts the measure y in function of the measures x(j), j = 1, . . . , n. The vector x ∈ n = (x(1), . . . , x(n)) t has several names: ? x is the regressor vector. ? x is the input. ? x is the vector of independent variables. y has several names: ? y is the target. ? y is the output. ? (y is the dependant variable). The pair (x, y) has several names: ? (x, y) is an input?output pair. ? (x, y) is a sample. We want to find f such that y = f(x). Let’s also assume that you know that f(x) belongs to the family of linear models. I.e. f(x) = ∑n j=1 x(j)βj + p = x, β +p where ·, · is the dot product of two vectors and p is the constant term. You can also write f(x) = xtβ + p where β ∈ n and p are describing f(x). We will now assume, without loss of generality, that p = 0. We will see later how to compte p if this is not the case. β is the model that we want to find. Let’s now assume that we have many input?output pairs. i.e. we have (x(1), . . . , x(n))(1) = X(1) ? y1 (1) X(2) ? y2 ... ... X(m) ? ym We want to compute β such that ?i X t(i)β = yi. Using matrix notation, β is the solution of: Xβ = y (2) 1 2where X ∈ m×n is a matrix containing on each line a different regressor and y ∈ m contains all the targets. The columns of X contain the independent variables or, in short, the variables. If m ≤ n, we can compute β using a simple Gauss-Jordan elimination. That’s not very interesting. We are usually more interested in the case where m n: when the linear system Xβ = y is over-determined. We want to find β? such that the Total Prediction Error (TPError) is minimum: TPError(β?) = min β (TPError(β)) (3) If we define the total