graphical-lasso算法

SPARSEINVERSECOVARIANCEESTIMATIONWITHTHEGRAPHICALLASSO基于graphicalLasso法对逆稀疏协方差矩阵的估计现代科技的快速发展带动了高维数据的广泛应用。在许多实际问题中，高维稀疏矩阵的研究处理起到了至关重要的作用。在2011年，JianqingFan等对稀疏矩阵进行了定义，且提出了在金融、稀疏矩阵在金融行业中的处理高维度数据的普遍性与所遇到的困难。所谓稀疏矩阵，即矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律。图论，作为数学的一个分支，以图为研究对象，将若干给定的点及连接这些点之间的连线来构成的一些图形。这些图形通常用来描述事物之间的某种特定关系。图论的核心思想即为用点来代表事物，并用连接两点的线来表示相应的这两个事物间具有的关系。随着计算机的出现，图论得到了快速的发展。图论的应用范围覆盖面很广，从自然科学到社会科学等的广阔的领域，包括电信网络计算机程序设计、人工智能情报检索、社会结构、运筹学、经济学、遗传学等。由于图论丰富的内容以及广泛的应用，在解决实际问题和理论问题中，图论都是一个有力的工具。高斯图模型：假定𝑋𝑖𝑥1,𝑥2,𝑥3,𝑥4,……𝑥𝑝′是一组p维的随机变量，它服从p元正态分布(𝑈,Σ)111111111,,pppppppppuwwUwwu如果记𝑋1′=𝑋1,𝑋2，𝑋2′=𝑋3,⋯,𝑋𝑝,Σ=Ω−1,如果给定𝑋2′=𝑋3,⋯,𝑋𝑝的值，那么在此条件下1****11122221********11221221212212111*12|(34)1212121122*(**)p称之为相关系数12|(34)120*0pw121112121122(X)A,A(diag()),(X)R(X)A(X,X)TTRApcorApcorw密度矩阵（concentrationmatrix）如果120w称𝑋1,𝑋2，关于𝑋3,𝑋4……,𝑋𝑝条件独立。在图模型中记作𝑋1||𝑋2|(𝑋3,𝑋4……,𝑋𝑝)当P=3时，那么𝑋1||𝑋2|𝑋3如果用他们的偏相关系数是否为0来表示边，此时的无向图为，𝑋1𝑋3𝑋2高斯图模型LASSO算法的引入在大数据的时代下，选择合适的变量建立模型是重中之重，因此多元线性回归算法显得至关重要，目前，“LASSO（TheLeastabsoluteshrinkageandselectionoperator）”和逐步回归法是两种被理论证明很有效的算法，他们都是由一种计算简单的方法所演变出来的“LARS（LeastangleRegressionSelection）”比如在多元回归中常用的逐步回归法。我们只知道向前回归，向后回归还有二者的结合的一些最基本的想法。比如向前回归，就是先选择和响应最相关的变量，进行最小二乘回归。然后在这个模型的基础上，再选择和此时残差相关度最高的（也就是相关度次高）的变量，加入模型重新最小二乘回归。之后再如此法继续，直到在某些度量模型的最优性准则之下达到最优，从而选取一个最优的变量子集进行回归分析，得到的模型是相比原模型更加简便，更易于解释的。这种方法，牺牲了模型准确性（预测有偏），但是提高了模型的精确度（方差变小）。大多数本科生对逐步回归的理解也就如此了。Efron看待这个问题时，比起常人更高了一个层次。他首先指出，逐步向前回归，有可能在第二步挑选变量的时候去掉和X1相关的，但是也很重要的解释变量。这是因为它每次找到变量，前进的步伐都太大了，侵略性太强。LARS的算法实际执行步骤如下：1.对自变量𝑋𝑖进行标准化（去除不同尺度的影响），对Y进行中心化（去除截距项的影响），初始的所有系数都设为0，此时残差r就等于中心化后的Y2.找出和残差r相关度最高的变量𝑋𝑗3.将𝑋𝑗的系数𝛽𝑗从0开始沿着LSE（只有一个变量𝑋𝑗的最小二乘估计）的方向变化，直到某个新的变量𝑋𝑘与残差r的相关性大于𝑋𝑗时4.𝑋𝑗和𝑋𝑘的系数𝛽𝑗和𝛽𝑘，一起沿着新的LSE（加入了新变量𝑋𝑘的最小二乘估计）的方向移动，直到有新的变量被选入5.重复2，3，4，直到所有变量被选入，最后得到的估计就是普通线性回归的OLS从上面这个算法可以看出，LARS这个东西明显和OLS,RidgeRegression等给出了Closed-formsolutions的模型不同，而是给出了一套对计算机来说非常友好的算法。这也说明了随着计算机能力的强大，现代统计基本上越来越靠近算法，而和模型无关。因此在这个基础上，Efron提出了LARS(leastangleregressionselection)：LARS算法，保证了所有入选回归模型的变量在solutionpath上前进的时候，与当前残差的相关系数都是一样的。这一点，比起Forwardstagewise要捷径一些，走得更快一些。这种算法是一种自动进行模型构建的方法。它和传统的Forwardselection在本质上是一样的，都是选择一个变量，然后选择一个继续进行的solutionpath，在该方向上前进。这两种方法的solutionpath的选择方法是一样的，唯一的区别就是前进的步伐不一样，Forwardselection的前进步伐很大，一次到头，而stepwise则是一小步一小步前进。这样比Forwardselection要谨慎一些，会免于漏掉一些重要的变量。LASSO算法：TheLeastabsoluteshrinkageandselectionoperator,Tibshirani(1996)是一种压缩估计。它通过构造一个罚函数得到一个较为精炼的模型，使得它压缩一些系数，同时设定一些系数为零。因此保留了子集收缩的优点，是一种处理具有复共线性数据的有偏估计。其想法可以用如下的最优化问题来表述：在𝑗=1𝑛𝛽𝑗≤𝑡的条件下，求残差平方和𝑦−𝑋𝛽2达到最小的回归系数的估值此处，我们可以写如下等价形式：𝑚𝑖𝑛𝑦−𝑋𝛽2+𝜆𝛽1我们叫做L1型的lasso回归Lasso的基本思想是在回归系数的绝对值之和小于一个常数的约束条件下，使残差平方和最小化，从而能够产生某些严格等于0的回归系数，得到可以解释的模型。我们熟悉如何求解限制条件为等号时，回归方程的求解。也就是用lagrange乘子法求解。但是对于这种，限制条件是不等号的情况，该如何求解。比较倾向于的方法，是利用计算机程序，对从0开始，不断慢慢增加它的值，然后对每个t，求限制条件为等号时候的回归系数的估计，从而可以以t的值为横轴，作出一系列的回归系数向量的估计值，这一系列的回归系数的估计值就是lassoestimation。已有学者已经证明，对LARS的算法进行一定的修改，可以得到相应条件下，LASSO的全部解。假设Ｐ维观测量𝑋𝑖𝑥1,𝑥2,𝑥3,𝑥4,……𝑥𝑝,𝑖=1,2,3,……𝑛，服从(𝑈,Σ)的正态分布。当Ｎ远大于Ｐ时，已知样本中心二阶距，我们如何通过较少的计算量来得到Σ−１。极大似然法：1'1/2/211'1111'1(,)(,,)11exp()()2(2)11ln(,)ln(2)ln()()22211ln(2)ln()2221()()1ln(,)ln(2)22niiniinpniniiiniiiLUfXUXUXUnLUpnXUXUnpntrASetSXUXUnnLUpn1111ln(S)2ln(S)22ntrnnCtr11111ln(,)ln(2)ln(S)ln(S)...............(1)22222nnnnLUpntrCtr我们借用lasso算法的模式，加入一个惩罚函数，令X=Σ−1那么（1）式我们可以写成110argmin{lndet()}...........(2)XXtrSXX其中，X为正定矩阵，tr（x）指的是矩阵X的迹，此处的范数指的是矩阵的1-范数，即矩阵中元素绝对值之和。𝜆控制罚函数的大小，而罚函数标记着，矩阵中非零元素的个数。当S为正定矩阵时，且𝜆为0的时候，此时（2）式就是经典极大似然估计。然而，当数据的个数n远小于变量数p时，二阶距矩阵可能会出现不可逆的现象。但是当𝜆0的时候，我们的估计式可以使得估计量Σ总是可逆的，无论N/P的比值是多么小。即使有些时候，我们拥有足够的样本使得S正定，但是Σ−1可能不是稀疏的，又有时候，存在很多对变量是条件独立的，通过尽可能将指数似然函数稀疏性的最大化后，我们希望可以找到一个非常稀疏的解，使得可以很好的解释数据变量之间的关系。因为λ的值越大，会使得解很稀疏，无法很好的解释数据，反而λ的值越小，能够解释了数据，却保证不了解的稀疏性。针对（2）的问题，Yuan&Lin(2007)通过使用Vandenberghe(1998)的方法，即内点法解决了问题，但Banerjeeetal.(2007)发现了一种新的优化算法，为这个问题带来了新的解决方式。他在自己的论文里证明了这个问题是收敛的，并且他将W记作Σ,而不是Σ−1,然后使得W作为Σ的估计量。他对（2）做了如下变化：目标函数：10argmin{logdet()}0XXtraceSXXWS令W=𝑋−1,对其进行求梯度得：其中Γ是一个矩阵，其中的元素𝛾ij如下表示规则：1jkjkjk1jksign(),if0[1,1],if0110argmin{logdet()}...........(2)XXtraceSXX根据（3）式可以转化为：0..........(3)WS1112111212221222W,TTWwSsSwwss1212120.............(4)0iiiiiiiiiiWSWSWS因为W=Σ,记Σ−1=11121222T112211211112222111212121112222111122222222()W...(5)1.TWI结合（4），（5）可得：1211121222W0s如果令𝛽=−𝜃12𝜃22111212W0........(6)s2212121212220()()sign()signsign如果将下式和（6）进行比较：111211min{Ws}2TT111212W0s令b=𝑊11−12𝑠121112111112222111111121112121112121111min{Ws}21min{(W2WWsWssW)}21min{W}2TTTTTb此处，可以使用带有1-范数的Lasso回归算法。进行计算求解。121211222222222212122212,1,2112111101argmin{lndet()}min{W}2XXtraceSXXb算法步骤：Step1.初始化W(0)=𝑆+𝜆𝐼Step2.重复按列执行如下步骤，以对角线上元素开始𝑤𝑖𝑖,i：p—1，直至达到预定精度（收敛）（1）对W的行和列重新排列，使得目标列，处于最后（隐性条件）。（2）对问题，使用lasso算法进