Multisource linear regression

Multisource Linear Regression Vctor Blanco Universidad de Granada (joint work with D. Ponce and J. Puerto) VI International Workshop on Locational Analysis and Related Problems Barcelona, November 2015 Multiple Linear Regression Given a set of variables X 1 ;:::; X d multiple regression analyzes the existence of some relationship among them. f ( X 1 ;:::; X d )=0 And the function f is estimated based on a sample of data. A Linear Regression model appears if we assume that f belongs to the set of linear functions, i.e.: f ( X 1 ;:::; X d ) =  0 + d X k =1  k X k for some  0 ; 1 ;:::; d 2 R . Multiple Linear Regression Given a set of variables X 1 ;:::; X d multiple regression analyzes the existence of some relationship among them. f ( X 1 ;:::; X d )=0 And the function f is estimated based on a sample of data. A Linear Regression model appears if we assume that f belongs to the set of linear functions, i.e.: f ( X 1 ;:::; X d ) =  0 + d X k =1  k X k for some  0 ; 1 ;:::; d 2 R . Multiple Linear Regression Given a set of variables X 1 ;:::; X d multiple regression analyzes the existence of some relationship among them. f ( X 1 ;:::; X d )=0 And the function f is estimated based on a sample of data. A Linear Regression model appears if we assume that f belongs to the set of linear functions, i.e.: f ( X 1 ;:::; X d ) =  0 + d X k =1  k X k for some  0 ; 1 ;:::; d 2 R . Residuals Given a sample of data f x 1 ;:::; x n g  R d +1 1 one tries to nd the model that minimizes the deviation of the data with respect to the tting body H (^ β ) = f z 2 R d +1 : d X k =0 ^  k z k = 0 g : For an observation x the residual is the error when adjusting a model compared to the sample data. ✠ Usually: " x =      x d  d  1 X k =0  k x k      , (  d = 1). (Vertical Distance) 1 assume that x i = (1 ; x i 1 ;:::; x id ) Residuals Given a sample of data f x 1 ;:::; x n g  R d +1 1 one tries to nd the model that minimizes the deviation of the data with respect to the tting body H (^ β ) = f z 2 R d +1 : d X k =0 ^  k z k = 0 g : For an observation x the residual is the error when adjusting a model compared to the sample data. ✠ Usually: " x =      x d  d  1 X k =0  k x k      , (  d = 1). (Vertical Distance) 1 assume that x i = (1 ; x i 1 ;:::; x id ) Residuals X 1 X 2 x b x " x Residuals Why not to consider dierent point-to-model error measures? X 1 X 2 x b x " x Residuals Why not to consider dierent point-to-model error measures? X 1 X 2 x b x " x Are the extesions reasonable? \Least squares regression estimators, has been studied intensively for well over 200 years now, primarily due to its convenient closed form." (Giloni & Padberg, 2002). Under Gaussian distribution of the error terms an impressive statistical apparatus has been created to assess the goodness of t, the quality of individual and/or subsets of the regression coecients, as well as other statistical properties of the linear regression model. But: \The ancient solitary reign of the exponential (Gaussian) law of error should come to an end". (Edgeworth, 1920). \We have left out a summary of linear regression models using the more general `  -norms with  62 f 1 ; 2 ; 1g for which the computational requirements are considerably more burdensome than in the linear programming case (as they generally require methods from convex programming where machine computations are far more limited today)." (Giloni & Padberg, 2002). Are the extesions reasonable? \Least squares regression estimators, has been studied intensively for well over 200 years now, primarily due to its convenient closed form." (Giloni & Padberg, 2002). Under Gaussian distribution of the error terms an impressive statistical apparatus has been created to assess the goodness of t, the quality of individual and/or subsets of the regression coecients, as well as other statistical properties of the linear regression model. But: \The ancient solitary reign of the exponential (Gaussian) law of error should come to an end". (Edgeworth, 1920). \We have left out a summary of linear regression models using the more general `  -norms with  62 f 1 ; 2 ; 1g for which the computational requirements are considerably more burdensome than in the linear programming case (as they generally require methods from convex programming where machine computations are far more limited today)." (Giloni & Padberg, 2002). Generalized Linear Regression Given: ✠ A sample of data f x 1 ;:::; x n g 2 R d +1 , ✠ Residuals " x : R d +1 ! R , and ✠ Aggregation of residuals criterion  : R n ! R . Find ^ β 2 arg min β 2 R d +1 ( ε x ( β )) ; (LRP  ; ε ) where ε x ( β ) = ( " x 1 ( β ) ;:::;" x n ( β )) t is the vector of residuals. Generalized Linear Regression Given: ✠ A sample of data f x 1 ;:::; x n g 2 R d +1 , ✠ Residuals " x : R d +1 ! R , and ✠ Aggregation of residuals criterion  : R n ! R . Find ^ β 2 arg min β 2 R d +1 ( ε x ( β )) ; (LRP  ; ε ) where ε x ( β ) = ( " x 1 ( β ) ;:::;" x n ( β )) t is the vector of residuals. Regression and Location Given a set of demand points A = f a 1 ;:::; a n g  R d +1 (assuming that a i 1 = 1 for i = 1 ;:::; n ) endowed with a distance measure between points in R d +1 ,  , the goal of continuous location models is to nd β  β  2 arg min  2 R d (  ( a 1 ; β ) ;:::; ( a n ; β )) : For an error measure " (dened as a norm-based distance kk ) and an aggregation criterion , solving the linear regression problem to t the model β t X = 0 is nothing but a continuous location problem where the residuals " a i are: " a i :=  ( a i ; β ) = D( a i ; H ( β )) = j β t a i j k (  1 ;:::; d ) k  This implies that many results already known in the eld of Location Analysis can be applicable in solving generalized regression problems. Regression and Location Given a set of demand points A = f a 1 ;:::; a n g  R d +1 (assuming that a i 1 = 1 for i = 1 ;:::; n ) endowed with a distance measure between points in R d +1 ,  , the goal of continuous location models is to nd β  β  2 arg min  2 R d (  ( a 1 ; β ) ;:::; ( a n ; β )) : For an error measure " (dened as a norm-based distance kk ) and an aggregation criterion , solving the linear regression problem to t the model β t X = 0 is nothing but a continuous location problem where the residuals " a i are: " a i :=  ( a i ; β ) = D( a i ; H ( β )) = j β t a i j k (  1 ;:::; d ) k  This implies that many results already known in the eld of Location Analysis can be applicable in solving generalized regression problems. Responses and Prediction For norm-based distances (based in Mangasarian, 1999): For a given observation z t = (1 ; z 1 ;:::; z d ) and the linear tting body H ( β ) the response ^ z consistent with the residual ε z = min y 2H ( β ) k z  0  y k is given by ^ z = z  0  β t z k β  0 k  k( β ) ; where k  k  is the dual norm to k  k and k( β ) = arg max k x k =1 β t  0 x . Moreover, ε z = j β t z j k β  0 k  : (1) Marginal variation: @ ^ z d @ z j =   j k β  0 k  k( β ) d . Responses and Prediction Let z = (1 ; z 1 ;:::; z d ) t , then 1If D is the ` 1 - distance, ^ z k = 8 < : z k if j  k j 6 = max fj  j j : j = 1 ;:::; d g , z k  β tz k β  0 k1 v k ; if  k = max fj  j j : j = 1 ;:::; d g , z k + β tz k β  0 k1 v k ; if  k =  max fj  j j : j = 1 ;:::; d g , for k = 1 ;:::; d , and for some v 1 ;:::; v d  0 such that X j v j = 1. 2If D is the ` 1 - distance, ^ z k = ( z k  β tz k β  0 k 1 ; if  k > 0, z k + β tz k β  0 k 1 ; if  k < 0, k = 1 ;: : :; d : 3If D is the `  - distance with 1 <  < + 1 then ^ z k = z k  β tz k β  0 k  k  ( β ) k ; k = 1 ;:::; d and k  ( β ) k = ( sg( β k ) j β k j = ( P d j =1 j β j j  )1 = if β k 6 = 0 0 if β k = 0 ; k = 1 ;:::; d ; 1  + 1  = 1. A General Model: non-negative lambdas   = min n X j =1  j  j (LR  ; kk ) s.t. ε i j β t x i j k β  0 k  ; 8 i = 1 ;: : :; n ; (2) z s i  ε r i ; 8 i = 1 ;: : :; n ; (3) z i   j + M (1  w ij ) ; 8 i ; j = 1 ;: : :; n ; (4)  j   j  1 ; 8 j = 2 ;: : :; n ; (5) n X i =1 w ij = 1 ; 8 j = 1 ;: : :; n ; (6) n X j =1 w ij = 1 ; 8 i = 1 ;: : :; n ; (7) β 2 R d +1 ; w 2 f 0 ; 1 g n  n ; z ; 2 R n + : OWA: (Nickel and Puerto, 2003), (Fernandez, Pozo and Puerto, 2015) A General Model Each constraint z s  ε r can be equivalently written as a set of O ( b log 2 ( r ) c ) second order cone constraints with b log 2 ( r ) c additional nonnegative variables. (B., Puerto, ElHaj; 2014) For 0   1     n :   =min n X j =1 v j + n X i =1 w i s.t. ε i j β t x i j k β  0 k  ; 8 i = 1 ;:::; n ; z s i  ε r i ; 8 i = 1 ;:::; n ; v j + w i   i z j ; 8 i ; j = 1 ;:::; n ; β 2 R d +1 ; z 2 R n + ; v ; w 2 R n (B., Puerto, Salmeron, Arxiv2015): SOCP for block-norm residuals and inner-outer approx. for `  . Lots of Experiments... Multisource Regression Multisource Regression Multisource Regression Multisource regression Multisource regression Multisource regression Multisource regression Multisource Regression Multisource Regression Multisource Regression Multisource regression min ( e 1 ;:::; e n ) s : t : (8) e i  " ij z ij ; representation of residuals ( " ) ; (9) p X j =1 z ij = 1 ; 8 i = 1 ;:::; n ; z ij 2 f 0 ; 1 g ; 8 i = 1 ;:::; n ; j = 1 ;:::; p ; e i 2 R + ; 8 i = 1 ;:::; n ; β jk 2 R ; 8 j = 1 ;:::; p ; k = 0 ;:::; d  1 : where z ij =  1 if the i th observation is assigned to H ( β j ), 0 otherwise, Multisource regression min ( e 1 ;:::; e n ) s : t : (8) e i  " ij  M (1  z ij ) ; 8 i ; j ; representation of residuals ( " ) ; (9) p X j =1 z ij = 1 ; 8 i = 1 ;:::; n ; z ij 2 f 0 ; 1 g ; 8 i = 1 ;:::; n ; j = 1 ;:::; p ; e i 2 R + ; 8 i = 1 ;:::; n ; β jk 2 R ; 8 j = 1 ;:::; p ; k = 0 ;:::; d  1 : where z ij =  1 if the i th observation is assigned to H ( β j ), 0 otherwise, Set partitioning formulation ✠ Let I = f 1 ;:::; n g denote the entire set of observations. ✠ Let S be a cluster of observations S  I . ✠ Let c S denote the cost of cluster S , i.e. the overall aggregation of the residuals of data in S . y S =  1 if cluster S is selected 0 otherwise : The set partition formulation is: min X S c S y S (10) X S y S = p X S 3 i y S = 1 8 i = 1 ;:::; n y S 2 f 0 ; 1 g ; S  f 1 ;:::; n g : (11) Set partitioning formulation ✠ Let I = f 1 ;:::; n g denote the entire set of observations. ✠ Let S be a cluster of observations S  I . ✠ Let c S denote the cost of cluster S , i.e. the overall aggregation of the residuals of data in S . y S =  1 if cluster S is selected 0 otherwise : The set partition formulation is: min X S c S y S (10) X S y S = p X S 3 i y S = 1 8 i = 1 ;:::; n y S 2 f 0 ; 1 g ; S  f 1 ;:::; n g : (11) Pricing problem Let u be the dual variable for constraint ( P S y S = p ) and v i the dual variables for constraints ( P S 3 i y S = 1). The reduced cost for variable y S is  c S = c S  u  P i 2 S v i . For instance, the pricing problem for the vertical distance residual: min S X i 2 S e 2 i  u  X i 2 S v i Clearly, this pricing problem can be formulated as a Mixed Integer Non Linear Programmming Problem similar to the single -source regression models. Pricing problem Let u be the dual variable for constraint ( P S y S = p ) and v i the dual variables for constraints ( P S 3 i y S = 1). The reduced cost for variable y S is  c S = c S  u  P i 2 S v i . For instance, the pricing problem for the vertical distance residual: min S X i 2 S e 2 i  u  X i 2 S v i Clearly, this pricing problem can be formulated as a Mixed Integer Non Linear Programmming Problem similar to the single -source regression models. Pricing as a mixed integer quadratic min n X i =1 t i  n X i =1 v i h i s.t. e i  j y  β t x i j  M (1  h i ) ; 8 i (12) t i  e 2 i ; 8 i = 1 ;:::; n ; (13) h i 2 f 0 ; 1 g ; 8 i = 1 ;:::; n ; e i 2 R + ; 8 i = 1 ;:::; n ; β k 2 R ; k = 0 ;:::; d  1 : where h i = 1 i i 2 S . COLUMN GENERATION... Pricing as a mixed integer quadratic min n X i =1 t i  n X i =1 v i h i s.t. e i  j y  β t x i j  M (1  h i ) ; 8 i (12) t i  e 2 i ; 8 i = 1 ;:::; n ; (13) h i 2 f 0 ; 1 g ; 8 i = 1 ;:::; n ; e i 2 R + ; 8 i = 1 ;:::; n ; β k 2 R ; k = 0 ;:::; d  1 : where h i = 1 i i 2 S . COLUMN GENERATION... To be continued... ✠ Behavior of CG... ✠ Use of norm-based residuals. ✠ Notion of MultiSource GCoD... Computation? ✠ Adapt to study Structural Changes in Time Series. ✠ ... Thank you! [email protected]