tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 理学 >>

graphical lasso算法


SPARSE INVERSE COVARIANCE ESTIMATION WITH THE GRAPHICAL L ASSO

基于graphical Lasso 法对逆 稀疏协方差矩阵的估计

现代科技的快速发展带动了高维数据的广泛应用。在许多实际问题中,高 维稀疏矩阵的研究处理起到了至关重要的作用。在2011年,Jianqing Fan等对 稀疏矩阵进行了定义,且提出了在金融、稀疏矩阵在金融行业中的处理高维度 数据的普遍性与所遇到的困难。所谓稀疏矩阵,即矩阵中非零元素的个数远远 小于矩阵元素的总数,并且非零元素的分布没有规律。 图论,作为数学的一个分支,以图为研究对象,将若干给定的点及连接 这些点之间的连线来构成的一些图形。这些图形通常用来描述事物之间的某种 特定关系。图论的核心思想即为用点来代表事物,并用连接两点的线来表示相 应的这两个事物间具有的关系。 随着计算机的出现,图论得到了快速的发展。图论的应用范围覆盖面很 广,从自然科学到社会科学等的广阔的领域,包括电信网络计算机程序设计、 人工智能情报检索、社会结构、运筹学、经济学、遗传学等。由于图论丰富的 内容以及广泛的应用,在解决实际问题和理论问题中,图论都是一个有力的工 具。

高斯图模型:假定 1 , 2 , 3 , 4 , … … 是一组p维的随机变量,它服 从p元正态分布(, Σ) ? u ?
? ? 11 ? ? ? U ? ? ?,? ? ? ? ? ?? ? ? p1 ?u ? ? ? p?
1



? w11 ? ? , ? ? ? ? ?w ? pp ? ? ? p1

?1 p ?

w1 p ? ? ? 密度矩阵(concentration matrix) wpp ? ?

′ ′ ′ 如果记1 = 1 , 2 ,2 = 3 , ? , ,Σ = Ω?1 ,如果给定2 = 3 , ? , 的值,那么在此条件下
* * * * ? w11 ? ? w22 ? w12 ? w21 1 ? ? * * * * * ? * ? * * ? w w ? w w w w ? w w 11 22 12 21 ? ? 21 22 ? 12 11 ? ?1

* ?12 ? ? 12|(34

p)

?

? w *12 ( w *11 w *22 )
1 2

称之为相关系数

? 12|(34
T

p)

? 0 ? w *12 ? 0
? 1 2

R (X) ? A ? A, A ? (diag(?))

,

pcor (X) ? R ?1 (X) ? A ?1 ?A?T pcor (X1 , X 2 ) ? w12 ? 11 ? 22

如果

w12 ? 0

称1 , 2 ,关于3 , 4 ……, 条件独立。在图模型中记作 1 || 2 |(3 , 4 ……, )

当P=3时,那么 1 || 2 |3 如果用他们的偏相关系数是否为0来表示边,此时的无向图为, 1 2

高斯图模型

3

LASSO 算法的引入
在大数据的时代下,选择合适的变量建立模型是重中之重,因此多元线性回归算法显 得至关重要,目前,“LASSO( The Least absolute shrinkage and selection operator )” 和逐步回归法 是两种被理论证明很有效的算法,他们都是由一种计算简单的方法所演 变出来的“LARS(Least angle Regression Selection )” 比如在多元回归中常用的逐步回归法。我们只知道向前回归,向后回归还有二者 的结合的一些最基本的想法。比如向前回归,就是先选择和响应最相关的变量,进行 最小二乘回归。然后在这个模型的基础上,再选择和此时残差相关度最高的(也就是 相关度次高)的变量,加入模型重新最小二乘回归。之后再如此法继续,直到在某些 度量模型的最优性准则之下达到最优,从而选取一个最优的变量子集进行回归分析, 得到的模型是相比原模型更加简便,更易于解释的。 这种方法,牺牲了模型准确性(预测有偏),但是提高了模型的精确度(方差变 小)。大多数本科生对逐步回归的理解也就如此了。Efron看待这个问题时,比起常 人更高了一个层次。他首先指出,逐步向前回归,有可能在第二步挑选变量的时候去 掉和X1相关的,但是也很重要的解释变量。这是因为它每次找到变量,前进的步伐都 太大了,侵略性太强。

LARS的算法实际执行步骤如下: 1. 对自变量 进行标准化(去除不同尺度的影响),对Y进行中心化(去除截距项的影 响),初始的所有系数都设为0,此时残差 r 就等于中心化后的Y 2. 找出和残差r相关度最高的变量 3. 将 的系数 从0开始沿着LSE(只有一个变量 的最小二乘估计)的方向变化,直到某 个新的变量 与残差r的相关性大于 时 4. 和 的系数 和 ,一起沿着新的LSE(加入了新变量 的最小二乘估计)的方向移 动,直到有新的变量被选入 5. 重复2,3,4,直到所有变量被选入,最后得到的估计就是普通线性回归的OLS 从上面这个算法可以看出,LARS这个东西明显和OLS, Ridge Regression等给出了Closedform solutions的模型不同,而是给出了一套对计算机来说非常友好的算法。这也说明了 随着计算机能力的强大,现代统计基本上越来越靠近算法,而和模型无关。

因此在这个基础上,Efron提出了LARS(least angle regression selection):

LARS算法,保证了所有入选回归模型的变量在solution path上前进的时候, 与当前残差的相关系数都是一样的。这一点,比起Forward stagewise要捷径 一些,走得更快一些。这种算法是一种自动进行模型构建的方法。它和传统的 Forward selection在本质上是一样的,都是选择一个变量,然后选择一个继 续进行的solution path,在该方向上前进。这两种方法的solution path的选 择方法是一样的,唯一的区别就是前进的步伐不一样,Forward selection的 前进步伐很大,一次到头,而stepwise则是一小步一小步前进。这样比 Forward selection要谨慎一些,会免于漏掉一些重要的变量。

LASSO 算法:
The Least absolute shrinkage and selection operator, Tibshirani(1996) 是一种压缩估计。它通过构造一个罚函数得到一个较为 精炼的模型,使得它压缩一些系数,同时设定一些系数为零。因此保留了子集收缩的优点,是一种处理具有复共线性数据 的有偏估计。 其想法可以用如下的最优化问题来表述: 在
=1

≤ 的条件下,求残差平方和 ?
2

达到最小的回归系数的估值

此处,我们可以写如下等价形式: ? 我们叫做L1型的lasso回归 Lasso 的基本思想是在回归系数的绝对值之和小于一个常数的约束条件下,使残差平方和最小化,从而能够产生某 些严格等于0 的回归系数,得到可以解释的模型。我们熟悉如何求解限制条件为等号时,回归方程的求解。也就是用 lagrange乘子法求解。但是对于这种,限制条件是不等号的情况,该如何求解。比较倾向于的方法,是利用计算机程序, 对 从0 开始,不断慢慢增加它的值,然后对每个t ,求限制条件为等号时候的回归系数的估计,从而可以以t 的值为横轴, 作出一系列的回归系数向量的估计值,这一系列的回归系数的估计值就是lasso estimation。已有学者已经证明,对
2

+

1

LARS的算法进行一定的修改,可以得到相应条件下,LASSO的全部解。

假设P维观测量 1 , 2 , 3 , 4 , … … , = 1,2,3, … … ,服从 (, Σ) 的正态 分布。当N远大于P时,已知样本中心二阶距,我们如何通过较少的计算量 来得到 Σ ?1 。 极大似然法:
L(U , ?) ? ? f ( X i , U , ?) ?
i ?1 n

?

1 (2? ) pn / 2 ?
n/2

? 1 n ? exp ?? ? ( X i ? U ) ' ? ?1 ( X i ? U ) ? ? 2 i ?1 ?

1 n 1 n ?1 ln L(U , ?) ? ? pn ln(2? ) ? ln ? ? ? ( X i ? U ) ' ? ?1 ( X i ? U ) 2 2 2 i ?1 1 n 1 ? ? pn ln(2? ) ? ln ? ?1 ? tr (? ?1 A) 2 2 2 1 n Set S ? ? ( X i ? U )' ( X i ? U ) n i ?1 1 n n ln L(U , ?) ? ? pn ln(2? ) ? ln ? ?1 ? tr (? ?1 S) 2 2 2 n n ? C ? ln ? ?1 ? tr (? ?1 S) 2 2

1 n n ln L(U , ?) ? ? pn ln(2? ) ? ln ? ?1 ? tr (? ?1 S) 2 2 2

n n ? C ? ln ? ?1 ? tr (? ?1 S)...............(1) 2 2

我们借用lasso算法的模式,加入一个惩罚函数,令X=Σ ?1 那么(1)式我们可以写成

其中,X为正定矩阵,tr(x)指的是矩阵X的迹,此处的范数指的是矩阵的1-范数,即矩阵中元 素绝对值之和。 控制罚函数的大小,而罚函数标记着,矩阵中非零元素的个数。 当S为正定矩阵时,且为0的时候,此时(2)式就是经典极大似然估计。然而,当数据的 个数n远小于变量数p时,二阶距矩阵可能会出现不可逆的现象。但是当 > 0的时候 ,我们的 估计式可以使得估计量Σ总是可逆的,无论N/P的比值是多么小。即使有些时候,我们拥有足 够的样本使得S正定,但是Σ ?1 可能不是稀疏的,又有时候,存在很多对变量是条件独立的,通 过尽可能将指数似然函数稀疏性的最大化后,我们希望可以找到一个非常稀疏的解,使得可以 很好的解释数据变量之间的关系。 因为λ 的值越大,会使得解很稀疏,无法很好的解释数据, 反而λ 的值越小,能够解释了数据,却保证不了解的稀疏性。

? ?1 ? arg min{? ln det X ? tr ( SX ) ? ? X 1}...........(2)
X ?0

? ?1 ? arg min{? log det X ? trace( SX ) ? ? X 1}...........(2)
X ?0

针对(2)的问题,Yuan & Lin (2007)通过使用Vandenberghe(1998)的方法,即内点 法解决了问题,但Banerjee et al. (2007)发现了一种新的优化算法,为这个问题带来了新 的解决方式。他在自己的论文里证明了这个问题是收敛的,并且他将W记作Σ,而不是Σ ?1 ,然 后使得W作为Σ的估计量。他对(2)做了如下变化:

目标函数:
arg min{? log det X ? trace( SX ) ? ? X 1}
X ?0

令W= ?1 ,对其进行求梯度得:

? W ? S ? ?? ? 0

其中 Γ是一个矩阵,其中的元素ij 如下表示规则:

? jk

?1 ? sign( ? ) ,if ? jk jk ? 0 ? ?? ?1 [ ? 1,1] ,if ? ? jk ? 0 ?

根据(3)式可以转化为: W ? S ? ?? ? 0..........(3)
W12 ? S12 ? ?? 12 ? 0.............(4) Wii ? Sii ? ?? ii ? 0 ? Wii ? Sii ? ?

? W11 W?? T ? w12
因为 W=Σ,记Σ
?1

w12 ? ?, w22 ?

? S11 S ?? T ? s12

s12 ? ? s22 ?

=

W ?? ? I ? W11 ?W?? T ? w12

? ?11 ?12 ? ??? T ? ? ?12 ? 22 ?

?12? 21 ?1 ?12 ? ? (?11 ? ) ?W11 ? ? 22 ? 22 ? w12 ? ?12 ? ? ? ? w ? ? W ...(5) ? ? 12 11 w22 ? 1 ? 21W11?12 ? ? 22 . ? ? ? 2 ? ? ? 22 22 ?

结合(4),(5)可得:

?12 W11 ? s12 ? ?? 12 ? 0 ? 22
如果令

=

12 ? 22

W11? ? s12 ? ?? 12 ? 0........(6)
? 22 ? 0 ?12 ? ? 12 ? sign(?12 ) ? sign( ) ? ? sign( ? ) ? ??12 ? 22
1 min{ ? T W11 ? ? ? T s12 ? ? ? 1} 2
W11? ? s12 ? ??12 ? 0

如果将下式和(6)进行比较:

令b =

? 2 11 12

1

1 min{ ? T W11 ? ? ? T s12 ? ? ? 1} 2 1 1 1 1 ? ? ? 1 T T T 2 2 2 ? min{ ( ? W11 ? ? 2 ? W11 W11 s12 ? W11 s12s12 W112 ) ? ? ? 1} 2 1 1 2 ? min{ W11 ? ? b ? ? ? 1} 2
2

1 1 ?1 2 ? ? arg min{? ln det X ? trace( SX ) ? ? X 1} ? min{ W11 ? ? b ? ? ? 1} 2 X ?0
此处,可以使用带有1-范数的Lasso回归算法。进行计算求解。

2

? ??
? ? 22

?12 , ? 22

w12 ? W11?

1 ? , w22 ? s22 ? ? w22 ? ? w12

? ?12 ? w22 ? ? w12

算法步骤 :

Graphical LASSO

Step 1.初始化 W (0) = + Step 2.重复按列执行如下步骤,以对角线上元素开始 ,i:p—>1,直至达 到预定精度(收敛) (1)对W的行和列重新排列,使得目标列,处于最后(隐性条件)。

(2)对问题
(4)令

,使用lasso算法进行求解,得到 ' ' w ? W ? , w 11 22 ? s22 ? ? (3)利用(2)中所得结果,更新协方差矩阵中的 12
1 1 2 min{ W11 ? ?b 2

2

? ? ? 1}

()

=W 0 ,i=i-1;返回(1)

Step 3.当i遍历所有列时,检验收敛条件:

? (k) ? W ? (k ?1) W

1

??

( 为预设精度)

如果满足条件,停止迭代,返回W,并求出其逆。否则继续 step 2.迭代直至最大迭代次数k。

模拟试验
?1 1.稠密矩阵Σ?1 生成:令Σii = 2,其他元素为1。 ?1 ?1 2.稀疏矩阵Σ?1 生成:令Σii =1,Σ?1 = Σ =0.5,其余为0. ,?1 i?1 ,i

根据Σ ?1 求出协方差矩阵Σ,定义数据维度为P,样本个数N=10,从而产生符合分布 的随机数,代入算法,设定最大迭代次数为30次,收敛精度为0.01。模拟结果如下

算法评价:
算法时间复杂度:O(KP 3 ),K为迭代次数,一次遍历需要O(P 3 ) 优点: (1)创新之处:将回归的算法用到极大似然估计上,简单易理解便于实现,且逼近速 度快。 (2)迭代法可以利用原始矩阵的稀疏结构,保持逆协方差矩阵的稀疏结构,为分析数 据的相关性提供很好的条件。 (3)在数据量大(数据样本n大于104 )条件下有很好的表现,收敛精度可控,以及迭 代旋转次数可以选择,便于在不同的条件下的使用。 (4)利用LASSO 算法对Σ?1 的估计,好处是解是稀疏的,并且在回归的过程中,不会因 为模型变量选择错误,使得结果缺少精度。

为了证明这种算法在高维度的数据条件下是可行的,Fredman借用了Sachs et al的数据,数据是研究人体主要的免疫系统细胞内11种磷酸蛋白质和磷脂 的数据,总共11个变量,7466个细胞。
根据Graphical Lasso 算法,对数据进行了处理。根据12个不同的值,最后 得到的图模型也不一样。

Figure 4: Cell-signaling data: profile of coefficients as the total L1 norm of the coefficient vector increases, that is, as decreases. Profiles for the largest coefficients are labeled with the corresponding pair of proteins.

美国议员投票数据
从 http://www.senate.gov 可以看到senators每次投票的结果。数据选 取美国第111届议会(2009年、2010年)roll-call vote数据,涉及110位参 议员696个议案的投票结果。利用图模型,结合我们前面提到的罚极大似然法, 我们可以对议员投票行为作图。下图中,每个点代表一个议员,每条边表示两 个议员的投票行为“很相似”——他们常常同时投赞成票或反对票。

图中,两派阵营的状态很明显。绿色的是 Democrat,红色的是Republican,蓝色的是 Independent。一般认为,民主党在政治上偏 左,主张社会自由与进步;而共和党偏右, “reflects American Conservatism”。可以 从图中获得很多信息,下面我们对此图做一点 深究。

While she(Cantwell) scores high on a progressive chart from ProgressivePunch.org. Cantwell has made several controversial votes during her time in the Senate that have created friction between her and members of the Democratic Party. Enzi was ranked by National Journal as the sixth-most conservative U.S. Senator in its March 2007 conservative/liberal rankings.Despite his strong support of the War in Iraq, he was one of 14 U.S. Senators to vote against the Iraq War funding bill in May 2007 because he opposes the clauses of the bill which increase domestic spending.

请各位批评指正!


推荐相关:

graphical lasso算法_图文.pdf

graphical lasso算法 - 对高斯逆协方差矩阵的极大似然估计。包括算法原理... graphical lasso算法_理学_高等教育_教育专区。对高斯逆协方差矩阵的极大似然估计。包括算...


graphical lasso采样及稀疏表示方法及伪代码.pdf

graphical lasso采样及稀疏表示方法及伪代码_数学_自然科学_专业资料。graphical lasso算法信号抽样,相关算法伪代码,人脸识别中常用的特征及其提取方法 ...


Lasso算法简介.doc

Lasso 算法则是一种能够实现指标集合精简的估计方法。 Tibshirani(


从理论到应用浅谈lasso模型.doc

模型的概念谈起, 对其起源、思想、与岭回归的比较、通过 lar 的算法实现等方面...另一个例子是 graphical lasso 拟合的稀疏高斯图, 将其应用于逆协方差矩阵,...


Lasso回归算法.doc

Lasso回归算法 - Lasso 回归算法: 坐标轴下降法与最小角回归法小结... Lasso回归算法_计算机软件及应用_IT/计算机_...graphical lasso算法 29页 2下载券 岭...


Lasso算法与AIC、bic.doc

Lasso算法与AIC、bic_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 Lasso算法与AIC、bic_数学_自然科学_专业资料。筛选变量的三种方法之间的比较...


Lasso算法介绍和R实例.pdf

Lasso算法介绍和R实例_数学_自然科学_专业资料。对于Lasso算法的介绍,有大量R...Journal of Computational and Graphical Statistics 9, 319337. Tibshirani, R...


广义线性模型组LASSO路径算法_马景义.pdf

2 广义线性模型组 LASSO 系数路径估计算法 ?(λ) 的算法, 有两部分内容: 首先, 推广 Park 和 本节将给出计算广义线性模型组 LASSO 路径 β Hastie [9] 的...


lasso算法.doc

2011/04/25 郝智恒在小弟的上一篇文章中,简单的介绍了 LARS 算法是怎么回事。...graphical lasso算法 29页 2下载券 Lasso算法介绍和R实例 44页 1下载券 支持...


基于Lasso特征选择的方法比.pdf

首先定义参数 s=t /Σβ 通过让 s 在[0,1]上取不 同的值来估计预测误差, 选择合适 s 的使得 CV (s)= 这种方法的提出使得 Lasso 算法的计算更加简单, ...


Graphical Lasso.doc

concentration matrix) 用于估计逆协方差矩阵的 graphical Lasso 模型的 Matlab ...eHiTS.LASSO.Manual 13页 免费 基于Lasso的人脸识别算法... 91页 5下载券 ...


坐标下降法求解LASSO问题.pdf

坐标下降法求解LASSO问题_工学_高等教育_教育专区。经典论文:回归问题COORDINATE DESCENT ALGORITHMS FOR LASSO PENALIZED REGRESSIONThe Annals of Applied Statistics 200...


测量误差模型的自适应LASSO变量选择方法研究_图文.pdf

测量误差模型的自适应LASSO变量选择方法研究 - 中 国科 学:数学 201


针对Lasso问题的多维权重求解算法_论文.pdf

针对Lasso问题的多维权重求解算法 - Jounarl of Computer Applications ISSN 1 ...... 针对Lasso问题的多维权重求解算法_电子/电路_工程科技_专业资料。Jounarl of ...


基于序lasso的时间序列分析方法_论文.pdf

基于实际的时序数据上的实验结 果证明了本文的模型和算法。 关键词:时序大数据;序lasso;块坐标下降;保序回归 中图分类号:TP18;TP391 文献标识码:A DOI:10....


Lasso问题的最新算法研究_论文.pdf

本文介绍和分析 了解 决最 小收 缩和选择算 子( Least absolute shrinkage and selection operator,Lasso) 问题 的最新算法: 梯度下降方法 、交替方向乘 子法( ...


lasso.doc

这个近似值也使人想到想到一个算出 Lasso 预测值本身的重复的岭回归算法, 但 是这个算法效率很低。然而,对于选择 Lasso 系数 t 却很有用。 8 ...


稀疏GroupLasso高维统计分析.pdf

有效算法的提出使得 L1 正则化成为机 器学习和稀疏信号处理领域的热点。 但是 ...lasso [ J] . Journal of Computational and Graphical Statistics, 1998 , 7...


高维数据回归分析中基于LASSO的自变量选择.pdf

2002 年出现 LARS ( the least angle regression ) 算法LASSO算法像个...The Bridge Versus the Lasso. Journal of Computational and Graphical Statistics...


稀疏学习优化算法.ppt

NIPS 2012 0 -10 -5 y 0 x 5 10 优化算法多阶段多任务特征学习算法(MSMTFL) 加权Lasso问题 repeat 加权系数 Pinghua Gong, Jieping Ye, Changshui Zhang, ...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com