基于混合条件独立性测试的因果发现算法.pdf
《基于混合条件独立性测试的因果发现算法.pdf》由会员分享,可在线阅读,更多相关《基于混合条件独立性测试的因果发现算法.pdf(11页珍藏版)》请在咨信网上搜索。
1、 年月南宁师范大学学报(自然科学版)J u n 第 卷 第期J o u r n a l o fN a n n i n gN o r m a lU n i v e r s i t y(N a t u r a l S c i e n c eE d i t i o n)V o l N o D O I:/j c n k i i s s n 文章编号:()基于混合条件独立性测试的因果发现算法陈少凡,韦程东,何国源,彭昱忠,徐辉(南宁师范大学 广西人机交互与智能决策重点实验室,广西 南宁 ;广东石油化工学院 计算机学院,广东 茂名 )摘要:在因果发现领域中,条件独立性(C o n d i t i o n
2、a l i n d e p e n d e n c e;C I)测试方法决定了基于约束的算法的效率和准确度P e t e r C l a r k(P C)算法是应用最为广泛的一个基于约束的算法由于C I测试方法的局限性,该算法在处理高维数据时存在耗时过长和准确度不高的问题该文提出一种混合C I测试方法(M i x e dC IT e s t;MC I T),它是一种基于核函数的C I测试方法(K e r n e l b a s e dC o n d i t i o n a l I n d e p e n d e n c eT e s t;K C I T),并结合偏相关性测试 MC I T能与P
3、 C算法结合(称为P CMC I T)进行因果发现 MC I T通过偏相关性测试减少了K C I T中存在的大量有关核矩阵的运算,从而提高了因果发现的效率;同时又保留了K C I T能够处理非线性数据的优点,因而保证了因果发现的准确度在各数据集上的实验结果表明,P CMC I T的精确率比基于K C I T的P C算法(称为P CK C I T)有显著提高,与基于非线性回归的P CR C I T算法不相上下;而P CMC I T的平均运行时间比后两者大为缩短关键词:因果发现;贝叶斯网络;条件独立性测试;偏相关性测试;时间复杂度中图分类号:T P 文献标志码:A因果发现是指利用可观测数据发现变量
4、之间的因果关系,因果网络则是用于表示可观测数据因果关系的重要工具因果发现的过程一般是先对因果网络构建无向图,然后确定因果边的方向并进行方向传播,最终得到表示因果网络的有向无环图因为P C算法在高维数据下进行因果发现时效率和准确率都不够理想,所以探究如何对该算法进行改进是当前因果发现研究领域的一个热点目前适用于较高维数据的因果发现算法主要有基于约束(c o n s t r a i n t b a s e d)的因果发现算法和基于分数(s c o r e b a s e d)的因果结构搜索算法两种基于约束的因果发现算法利用条件独立性(C o n d i t i o n a lI n d e p e
5、 n d e n c e;C I)测试进行因果发现,从而得到表示因果关系的图基于约束的经典因果发现算法有P C算法(P e t e r C l a r k)、I C算法(I n d u c t i v eC a u s a t i o n)、F C I算法(F a s tC a u s a l I n f e r e n c e)等基于分数的因果结构搜索算法则通过优化恰当的得分函数来搜索具有最佳得分的因果结构,常见的得分函数有后验概率、贝叶斯信息准则(B a y e s i a nI n f o r m a t i o nC r i t e r i o n;B I C)和赤池信息量准则(A k
6、 a i k eI n f o r m a t i o nC r i t e r i o n;A I C)等基于分数的因果结构搜索算法有贪婪等价类搜索算法(G r e e d yE q u i v a l e n c eS e a r c h;G E S)、G E S与F C I算法的结合 G F C I算法以及C l a a s s e n等提出的G r e e d yP AGr e s e a r c h算法等随着神经网络技术的发展,一大批使用神经网络的因果发现算法被提出:X i a等 基于梯度下降原理提出了神经因果模型(N e u r a lC a u s a lM o d e l;N
7、CM)以及一个可以同时识别和估计因果效应的梯度下降算法 P a w l o w s k i等 基于深度学习技术提出了深度神经因果网络(D e e pN CM)Z e e v i M等 提出了一个更加精准的N CM,并为图神经网络(G r a p hN e u r a lN e t w o r k;GNN)定义了干预措施这些基于神经网络的因果发现算法通过神经网络对因果网络进行搜索,它们本质上是收稿日期:基金项目:国家自然科学基金(,);广东省教育厅青年创新人才项目(KQN C X );广东省基础与应用基础研究项目(A );广西人机交互与智能决策重点实验室开放基金项目(G XH I I D )第一
8、作者简介:陈少凡(),男,安徽合肥人,硕士研究生,研究方向:因果推断通信作者简介:韦程东(),男,广西上林人,教授,博士,博士生导师,研究方向:贝叶斯统计第期陈少凡,等:基于混合条件独立性测试的因果发现算法 基于分数的算法P C算法是由P e t e rS p i r t e s和C l a r kG l y m o u r提出的一种基于约束的因果发现算法原始的P C算法在稳定性、潜在混杂因子处理、非线性因果关系发现及混合变量处理等方面有诸多局限,所以研究人员不断对P C算法进行改进比如S t a b l eP C算法 通过修改因果骨架学习及因果定向的规则,使P C算法在高维数据上仍可以进行稳
9、定的因果学习;通过添加针对未观测变量的C I测试,基于P C算法的邻接搜索思想的F C I/R F C I算法及其变体,可以在未观测混杂变量和样本选择偏差存在的场景下进行因果发现;C o p u l aP C 将P C算法中基于相关矩阵的C I测试优化成基于G a u s s耦合函数相关矩阵的C I测试,从而使得C o p u l aP C算法能够支持混合变量下的因果发现基于约束的算法通过C I测试来探究数据间的因果关系,因此C I测试方法在很大程度上决定了这类算法的效率Z h a n gK等 提出的基于核函数的C I测试方法(K e r n e l b a s e dC IT e s t;K
10、 C I T)可以很好地解决非线性场景下的C I测试问题;D o r a n 提出了基于随机排序的核函数C I测试方法;Z h a n gH等 提出了基于非线性回归的C I测试方法(R e g r e s s i o n b a s e dC IT e s t;R C I T)以及基于残差相似性的C I测试方法;S t r o b l等 利用随机傅里叶特征去逼近K C I T中的核函数,提出了一种近似核函数的C I测试方法使用以上C I测试方法处理高维数据时存在着不够高效和准确的问题,对此,我们将K C I T与偏相关性测试结合,得到一个混合C I测试方法(M i x e dC IT e s
11、t;MC I T)我们的想法如下:首先偏相关性测试的时间复杂度为O(l o g(n),远低于以上提到的C I测试方法,从理论上是可以提高C I测试的效率的其次,当变量服从联合高斯分布时,若变量之间的偏相关性不成立,则变量之间的C I成立,说明在理论上可以利用偏相关性测试进行C I测试再者,偏相关性测试只能验证变量间的线性偏相关性,因此仍然需要K C I T对变量之间的非线性的C I进行测试预备知识因果网络表示变量之间的因果关系的有向无环图(D i r e c t e dA e y c l i cG r a p h;D AG)称为因果网络图,它可表为三元组G(V,E,P)其中,顶点集Vv,v,v
12、n 表示网络中的所有节点;有向边集E表示网络节点之间的因果关系;PP r(vi|P a r e n t(vi)|in 是一组条件概率的集合,这里P r(vi|P a r e n t(vi)表示vi的父节点集P a r e n t(vi)对vi的因果效应因果网络实际上是联合概率分布P r(v,v,vn)中所有C I的图形化表示在不提前说明的情况下,因果网络中的vi同时表示变量与节点准则和假设d 分离准则是描述因果网络节点间关系的一个重要的图性质定义(d 分离准则)设X,Y,Z为图G中互不相交的节点集,X,Y为目标变量,Z为条件变量集称X与Y在G中被Zd 分离,如果从 任意xjX到任意ykY的任一
13、路径均被Z的某个子集Zl阻断,即该路径上的点vi满足下列任一条件:()vi与xj,yk成对撞结构,即为xjviyk,且vi及其子孙节点均不属于Z;()vi与xj,yk构成链式结构或分叉结构,即xjviyk或xjviyk,且viZ假设(忠实性假设,F a i t h f u l n e s sA s s u m p t i o n)给定一个因果网络图G,令P r(X,Y,Z)为三个变量(集)X,Y和Z的联合概率分布,如果由XY|Z可以推出X,Y被Zd 分离,则称P r(X,Y,Z)满足关于G的忠实性假设在满足忠实性假设的情况下,因果发现算法可以通过C I测试得到一个代表因果网络的部分有向无 南
14、宁 师 范 大 学 学 报(自 然 科 学 版)第 卷环图(P a r t i a lD i r e c t e dA c y c l i cG r a p h;P D AG)假设(马尔可夫假设,M a r k o vA s s u m p t i o n)给定一个因果网络G,令P(X Y Z)为三个变量(集)X,Y和Z的联合概率分布,如果X,Y被Z集d分离XYZ,则称P(X Y Z)满足关于G的马尔可夫假设假设(因果充分性假设,C a u s a lS u f f i c i e n c y)给定一个因果网络G,假设G中所有的变量没有未观测的混杂因子干扰K C I T方法近年来,研究人员提出
15、了一系列基于核函数的C I测试方法:将观测变量映射到再生核H i l b e r t空间(R e p r o d u c i n gK e r n e lH i l b e r tS p a c e;R KH S)上,从而可以用R KH S上的映射去构造用于检验C I的统计量文献 基于R KH S上的归一化互协方差算子,提出了一种关于随机变量C I的度量,从而得以判定X,Y之间的在条件Z下的C I 基于以上工作,Z h a n gK等 提出了K C I T方法,并证明了XYZ成立当且仅当对任意fLX Z,gLY(LY和LX Z分别表示Y和(X,Z)的平方可积函数空间)使得E(fg)成立,其中f
16、(x,Z)f(x,Z)rf(Z),g(y,Z)g(y)rg(Z),其中rf,rg为LZ中的回归函数 K C I T将函数f,g,rf,rg的空间松弛到R KH S中,并利用核函数构造检验统计量与K C I T相结合的P C算法(称为P CK C I T)能够更好地在非线性假设下进行因果发现但由于K C I T涉及核矩阵的特征值分解与求逆,故P CK C I T速度过慢成了一个亟须解决的问题偏相关性与C I的关系文献 基于偏相关性给出了XYZ在平方可积函数空间上的充要条件,即引理条件独立性特性(C h a r a c t e r i z a t i o no fC o n d i t i o n
17、 a l I n d e p e n d e n c e;C C I):令X,X为两个实值随机变量,Z(z,z,zn)为n维随机向量,X,X在条件Z下的C I定义为等式E(f g|Z)E(f|Z)E(g|Z)对fLXZ,gLXZ几乎处处成立,其中LXZ为(X,Z)的平方可积函数空间,LXZ同理XX|Z成立,当且仅当E(f g)文献 给出了高斯和非高斯情况下偏相关性与C I的关系引理给定随机变量X,Y以及Z(z,z,zk),三者均是独立随机变量i(i,q)的线性组合如果所有的i服从联合高斯分布,那么XYZ成立当且仅当偏相关系数X YZ引理表明,在非高斯场景下,若变量之间的偏相关性成立,则C I不
18、成立MC I T方法现有的基于核函数的C I测试方法在处理高维数据时存在效率和准确度都不够理想的问题受到R C I T方法和节中偏相关性与C I关系的启发,本节提出一种结合偏相关性测试与K C I T的MC I T方法对C I测试方法来说,最重要的是检验统计量的构造,下面给出偏相关性测试以及K C I T中的检验统计量的定义定义(MC I T中偏相关性测试的检验统计量)设X和Y为实随机变量,Z为N维随机向量,zi表示Z的第i个分量 MC I T方法中的偏相关性测试所使用的检验统计量为z(X YZ)l nX YZX YZ,()其中第期陈少凡,等:基于混合条件独立性测试的因果发现算法 X YZNN
19、ieX,ieY,iNNieX,iNNieY,i,()N为观测变量数,eX,ixiwX,zi,eY,iyiwY,zi为线性回归问题wXa r gm i nwNi(xiw,zi),wYa r gm i nwNi(yiw,zi)中的残差,其中 w,zi为向量w和zi的数量积考虑假设检验问题H:X YZH:X YZ当不等式N|Z|z(X YZ)|()()成立时,以显著性水平拒绝原假设H,其中()为标准正态分布的分布函数定义(MC I T中K C I T的检验统计量)考虑假设检验问题H:X与Y在条件Z下C I成立H:X与Y在条件Z下C I不成立当不等式TC I nt r(KX|Z KY|Z)()成立时,
20、以显著性水平拒绝原假设其中,n为X中的变量数,KXHKXH,这里KX为X的高斯核矩阵,HInJ JT,J为全方阵MC I T的主要步骤为:先对变量进行偏相关性测试,再对偏相关性测试无法判定的C I使用K C I T进行C I测试,从而确定变量之间的因果关系MC I T的总体框架如下算法MC I T输入:目标变量X,Y,条件变量Z,显著性水平,输出:X与Y在条件Z下的C I:计算z(X YZ):II ff()成立,tt hh ee nn:根据()计算TC I:II ffTC I,tt hh ee nn:RR ee tt uu rr nnX与Y在条件Z下的C I成立:EE ll ss eeRR e
21、e tt uu rr nnX与Y在条件Z下的C I不成立:EE nn ddII ff:EE ll ss eeRR ee tt uu rr nnX与Y在条件Z下偏相关,即X与Y在条件Z下的C I不成立:EE nn dd ii ff基于MC I T的因果发现算法(P CMC I T)将MC I T与P C算法结合,就可将MC I T应用至因果发现中P CMC I T算法首先,P CMC I T根据原始数据集V中的所有变量建立全连接无向图接着,P CMC I T使用混合C I测试判定变量之间的C I 然后,P CMC I T寻找条件相关变量之间的V 结构,并进行方向传播,从而确定变量之间的因果方向最
22、终,P CMC I T得到结果因果网络GP CMC I T的总体框架如下 南 宁 师 范 大 学 学 报(自 然 科 学 版)第 卷算法P CMC I T输入:原始数据集Vv,v,vn输出:因果网络图G:建立V的全连接图G:FF oo rr在G中相邻的节点vi,vjVdd oo:II ff存在ZVvi,vj使得vivjZ(用混合C I测试进行C I测试)tt hh ee nn:删除G中的e(vi,vj)和e(vj,vi),且保存混合C I测试的结果:EE nn ddII ff:EE nn ddFF oo rr:根据混合C I测试保存的关于vivjZ是否成立的结果,在G中寻找V 结构,并进行方向
23、传播:得到结果因果网络图G我们给出P CMC I T的一个实例,如图所示图P CMC I T算法的一个实例P CMC I T的时间复杂度从定义和不难看出,偏相关性测试在构建检验统计量时只需要进行回归的计算,其时间复杂度为O(l o g(n);而K C I T构建检验统计量的过程中涉及复杂的高斯核矩阵的特征核计算,其时间复杂度为O(n)MC I T通过偏相关性测试大大减少了K C I T的相关计算,从而极大地提高了C I测试的效率考虑P CMC I T的时间复杂度P C算法的时间复杂度C为CnkiniT,()其中n为因果网络中的节点个数,k为任意节点的最大入度,T为C I测试方法的时间复杂度由(
24、)可以看出,C I测试的时间复杂度决定了P C算法的效率 P CMC I T在对观测变量进行K C I T之前先进行偏相关性测试,可以避免许多冗余的K C I T,从而提高因果发现的效率数值实验本文的数值实验是在MAT L A BR b上完成的本文分别在A s i a、I n s u r a n c e、A l a r m、B a r l e y、H a i l f i n d e r和W i n p t s这六个真实因果网络(h t t p s:/wwwb n l e a r n c o m/b n r e p o s i t o r y/)上对P CMC I T算法进行数值实验以上真实因果
25、网络的统计信息见表本文选用召回率、精确率和F得分 来对算法性能进行评估,它们分别定义如下:召回率算法发现的真实因果关系真实的因果关系,()第期陈少凡,等:基于混合条件独立性测试的因果发现算法 精确率算法发现的真实因果关系算法发现的因果关系,()F召回率精确率召回率精确率()这三个指标可以用来评价因果学习算法的准确度,各项得分越高,则算法准确度越高表六个因果网络结构的统计信息数据集节点数平均度最大度数A s i a I n s u r a n c e A l a r m B a r l e y H a i l f i n d e r W i n p t s 基于表中的因果网络结构,分别生成大小为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 混合 条件 独立性 测试 因果 发现 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。