Why does least angle regression work

《Why does least angle regression work》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Whydoesleastangleregressionwork?SvenLaurswen@math.ut.eeHelsinkiUniversityofTechnologyMinimisationgoaloftheLASSOalgorithmGiven:anoutputvectoryandadesignmatrixXwithcolumnsx1,...,xn.Find:acoefficientvectorβthatminimises12Elasso=2·ky−Xβk2+λ·kβk1(1)Equivalentformulation:Findaco

2、efficientvectorβthatminimises2Eols=ky−Xβk2s.t.kβk1≤t(2)Correspondence:Task(1)isLagrangefunctionalofTask(2).T-122.102Regularizationandsparseapproximations,February8,20051ExplicitgradientofthecostfunctionDividethesetoffeasiblesolutionsRnintooctantssign(β)=const.iLetsbethesig

3、nvector,i.e.si=sign(βi).Thenineachoctant12tElasso=·(y−Xβ)+λ·sβ2tt∇βElasso=XXβ−Xy+λ·sIftheminimumisaninternalpoint,thenthesolutionhasaform?t−1tβ=(XX)(Xy−λs)T-122.102Regularizationandsparseapproximations,February8,20052Whathappensintheboundaries?Fortheminimisationoveraboun

4、dary,weexplicitlyrequireβi=0foralli∈Nβi∈Rforalli∈AHence,thecostfunctionsimplifies12tElasso=2·(y−XAβA)+λ·sAβAtt∇βAElasso=XAXAβA−XAy+λ·sAandthus?t−1tβA=(XAXA)(XAy−λsA)?β=0NT-122.102Regularizationandsparseapproximations,February8,20053Geometricalinterpretationofβ?Ifβ?isanint

5、ernalpoint,thenthecorrespondingpredictionvector?t−1tt−1µ=Xβ=X(XX)(Xy−λs)=µols−λ·X(XX)s

6、{z}uwhereuisanequiangulartothevectorss1x1,...,snxnttt−1tXu=XX(XX)s=s=(±1,...,±1)Tosummarise,asmallchangeinλmovesµinthedirectionofu.T-122.102Regularizationandsparseapproximations,Februa

7、ry8,20054Whathappensintheboundaries?Letβ?betheinternalpointofaboundarywithworkingsetA,i.e.βi=0foralli∈Nβi6=0foralli∈AThenthecorrespondingpredictionvector?t−1tt−1µ=XAβA=XA(XAXA)(XAy−λsA)=µA−λ·X

8、A(XA{zXA)sA}uAwhereuAisequiangulartothevectorssixi,i∈Attt−1tXAuA=XXA(XAXA)sA=s

9、A=(±1,...,±1)Tosummarise,asmallchangeinλmovesµinthedirectionofuA.T-122.102Regularizationandsparseapproximations,February8,20055InformaldescriptionofLARSLARSisagreedyoptimisationalgorithm:•Startsfromtheextremeboundary:A=∅,β0=0andµ0=0.•Movesalongthe“optimal”pathinspacevect

10、orspacehxi,i∈Ai.•Occasionally,extendstohigherdimension.•Alwayschoosesthemostprofitablevectorxitoadd.•Fin