1〖〗因果推断的可分解性和可传递性问题耿直
北京大学数学科学学院， 北京100871 理性的最高成就是引起了人们对其有效性的怀疑。
(乌纳穆诺 (Miguel de Unamuno), 1864—1936） 自提出替代指标悖论以来，它成了我心中一片飘逝不去的阴云，使我对因果作用的统计结论的可传递性产生了怀疑。我想借此机会，向大家介绍一下这个困扰我的问题。
1引言
基于还原论的方法将一个大规模的系统分解为若干个小规模的系统，再对每个小系统进行局部研究，然后，将局部研究的结论汇总后综合得出大系统的结论。但是，一个大系统的研究问题是否能分解为小系统的研究问题？如果分解的话，需要什么条件？本文针对因果推断问题，探讨因果路径上变量之间的因果作用问题。例如，我们希望研究一个系统中三个变量T,S和Y之间的因果机制。我们是否能将其分解为两个子系统，一个包含T和S，另一个包含S和Y，分别研究各子系统的因果机制，然后组建T,S和Y之间的因果机制？这种分解需要什么条件？ 
采用变量选择的手段将一个高维空间的统计问题降到低维空间解决，需要考虑两个问题： 可压缩性(collapsibility)和可分解性(decomposability)。可压缩性的意思是将高维数据经变量筛选降到低维空间后能保证得到与高维空间相同的统计结论\[1,3,20,23,27\]。我们曾经探讨过关于离散数据、连续数据、混合数据和一般分布情况进行统计推断的可压缩问题\[8,10,11,15\]。可分解性的意思是将一个高维的问题分解到若干变量子集的低维空间分别进行分析，然后将这些低维的结论汇总，最终解决高维的问题\[5,7,13,24\]。可分解性与可压缩性相互联系，高维问题分解为若干低维问题，希望在分解后的每个低维空间能得到无混杂偏倚的推断结论，即可压缩性。然后将所有低维空间得到的无混杂偏倚的结论进行汇总，得到高维空间的结论，即可分解性。本文将探讨因果推断的可分解性。在X1→X2→…→Xp的一条因果路径上，是否可以通过分解，得到各个局部Xi对Xi+1的因果作用，然后综合这些局部因果作用得到X1对Xp的因果作用？ Pearl定义了因果路径的作用\[16\]。VanderWeele和Robins提出了利用带正负号的因果网络判断因果作用正负号的方法\[22\]。他们的方法需要已知一个完整的因果网络。但是在实际应用中，也许很难获得一个完整网络的知识。
机器学习及其应用2011〖〗因果推断的可分解性和可传递性问题在医学临床试验中，称研究的目标变量为结局指标(endpoint)。当这个结局指标在实际研究中难以获得时，常常用一个容易获得的指标替换这个结局指标，称为替代指标(surrogate endpoint)。例如，一个评价预防更年期妇女骨折药物的临床试验，因为观测妇女是否今后会出现骨折需要等待很长时间，因此，将骨密度作为结局指标“骨折”的一个替代指标，通过该药物是否能增加骨密度来评价对于骨折的预防效果。替代指标的方法不仅应用于医学，也广泛应用于自然科学、 经济学和人文社会科学的研究。很多学者提出了确定替代指标的准则\[2,4,13,14,18,25\]。这些准则都有一个共同的特点，就是要求一个替代指标应该是从原因通向结局的因果路径上的变量，并且希望这个替代指标能够在各种意义上切断原因到结局的路径。我们曾指出可能会出现治疗对替代指标有正作用，并且替代指标对结局指标也有正作用，但是治疗对结局指标可能有负作用的替代指标悖论现象\[2\]。这里的正作用是指总体分布意义上的因果作用。替代指标悖论意味着在总体分布意义上统计推断的结论不具有可传递性。本文将进一步指出，即使总体中每一个个体的替代指标对结局都有严格正的个体作用，由治疗对替代指标的统计结论也不能预测治疗对结局的作用。关于如何综合分析因果路径上变量之间的因果作用，文献\[2,12,22\] 提出了利用变量之间有单调性关系的先验知识进行定性的评价方法。但是，即使观测到因果路径上所有变量的联合数据，这些先验知识也是不可检验的。本文的目的不是探讨如何进行因果路径上的统计推断方法，而是试图论述统计结论不具有可传递性。
本文第2节介绍因果网络结构学习的分解方法，在条件独立的情况下，可以将整体的结构学习分解为局部的结构学习。接下来的几节探讨评价因果作用的分解问题。首先，在第3节介绍了目前已经提出的几种直接作用的概念。然后，第4节探讨在任何意义上都没有直接作用的情况下，也很难采用分解方法进行因果作用的评价，由分解后的局部因果作用难以综合得出整体的因果作用。最后，我们提出如何综合统计推断结论是一个具有挑战性的问题，希望这个问题能得到统计学者和各科学领域研究者的关注。
2图模型结构学习的可分解条件
令V表示包含所有变量的集合，将其划分为三个互不相交的子集A，B，C。很多人研究过无向图模型的估计和模型选择的分解算法\[5,6,9\]。如果给定C的条件下A与B相互独立并且 C上是一个完全无向子图（称为强分解条件），那么，我们可以分别计算两个子图模型的最大似然估计，然后，将它们进行整合，就可以得到全图模型的最大似然估计。关于因果网络或有向无环网络的结构学习，我们曾经探讨过结构学习的分解算法\[26,28\]。关于有向无环图的D\|分离\[17\]，如果C可以D\|分离A和B，记为A⊥B|C，那么，判断任意两点x和y是否能被D\|分离，可以在A∪C和B∪C的两个子图上进行: 
(1) 当x∈A 且y∈A∪C时，如果在全图上存在一个子集SV,有 x⊥y|S当且仅当在A∪C的子图上存在一个子集S′A∪C,有x⊥y|S′(2) 当x和y都在C中，即x,y∈C时，如果在全图上存在一个子集SV,有x⊥y|S当且仅当存在A∪C或B∪C的一个子集S′，即S′A∪C或 S′B∪C，有x⊥y|S′根据这个结果，我们可以构造因果网络结构学习的分解算法。对于一个包含所有变量的集合V 的大网络GV的结构学习，在忠实性假定下，如果给定C的条件下A与B相互独立（称为弱分解条件），那么，我们可以分别学习两个子网络 GAC和GBC，然后合并两个子网络可以得到完整的网络GV。注意弱分解条件不要求在条件集合C上有一个完全图。
3直接作用和间接作用
吸烟可以引起高血脂和胆固醇升高等问题，然后导致心血管疾病。其中吸烟通过高血脂导致心血管疾病的比例有多大？ 采用图1中的因果网络表示。在这个因果网络中，吸烟T通过高血脂S导致心血管疾病Y的作用定义为T对Y的间接作用； T指向Y的箭头表示了T对Y的直接作用，图1三个因素的因果网络 这个直接作用可以视为除了通过S的间接作用以外的所有其他路径的综合作用。Pearl举了另一个例子说明直接和间接作用\[16\]。某种治疗疾病Y的药物T，其副作用是头痛，头痛导致服用阿司匹林S,而阿司匹林S对该病也有疗效。那么，我们如何评价除了阿司匹林的作用之外，该药物T对疾病Y的直接作用？多因素之间的直接作用和间接作用的术语被广泛用于很多科学研究中。但是，直接作用和间接作用的概念与定义并不是很清楚。一方面，基于关联度量定义的直接作用和间接作用，有很多传统的统计模型和方法可以用于统计推断，但是，它们不能解释为因果作用。另一方面，基于因果模型，可以清楚地定义直接作用和间接作用，但是，缺乏有效的统计推断方法。
3.1基于关联模型的直接作用与间接作用
一个最简单的描述直接作用和间接作用的模型是采用联立方程组： Y=αS+βT+䦶Euclid Math OnerCpy
S=γT+䦶Euclid Math OnerCps其中䦶Euclid Math OnerCpy和䦶Euclid Math OnerCps是与其他变量独立的误差变量。这个模型可以用图2中的路径分析图表示。将S的方程代入Y的方程，可以得到Y和T的边缘模型： Y=(αγ+β)T+䦶Euclid Math OnerCp′y(αγ+β)解释为T对Y的总作用，β解释为 T对Y的直接作用；αγ解释为T对Y的间接作用。这种解释基于关联度量模型，没有因果作用的意义。如果给定S下T与Y条件独立，记为TY|S,那么β=0，因此，T对Y没有直接作用。但是，我们在后面将说明这个结论不能保证T对Y没有因果意义上的直接作用。
以吸烟与心血管疾病为例，这个条件独立似乎说明在相同的高血脂人群，吸烟和不吸烟对是否患心血管疾病没有直接的影响。实际上，这个条件独立并不能说明吸烟对心血管病没有直接作用。因为在同一高血脂水平人群，不吸烟的人与吸烟的人是不可比的。这些不吸烟的人能达到另一些吸烟人的高血脂水平，说明与吸烟的人相比，这些不吸烟的人有其他导致高血脂的危险因素U，比如，不吸烟的人会吃更多的糖果，而这些危险因素U可能也是心血管疾病的危险因素； 如图3，U同时是高血脂S和心血管疾病Y的危险因素。条件独立意味着在相同高血脂水平的条件下，不吸烟人与吸烟人有相同患心血管疾病的概率，吸烟的人吃糖果少，没有这种危险因素，却达到了吃糖果但不吸烟人的患病概率，这说明吸烟应该有高血脂以外的危害，存在着吸烟对心血管疾病的直接作用。在图3的因果网络中，存在公共危险因素U同时指向S和Y，如果条件独立TY|S成立，说明可能存在T指向Y的直接箭头。
图2路径分析图 
[]图3存在S和Y的公共原因U 
3.2基于因果模型的主分层直接作用
文献\[4,19\]提出用潜在结果模型来刻画直接作用和间接作用。用w表示个体, T(w)表示个体w所接受的处理或治疗，S(w)表示个体w的中间变量，Y(w)为个体w的结果变量。潜在结果定义为： 假若个体w接受处理t的话，将会得到结果Yt(w)和中间变量St(w)。如果个体w实际接受的处理为t′，那么个体w在处理t≠t′的结果 Yt(w)是潜在的、观测不到的。例如，吸烟人当初不吸烟的话，他是否会得心血管疾病是不可观测的潜在结果。进一步，我们用Yts(w)表示个体w在处理t和中间结果s情况下的结果。Yts(w)可能是先验不可观测的。例如，个体w吸烟的话将有高血脂，不吸烟的话将没有高血脂。那么，不可能观测到他吸烟但没有高血脂的情况下心血管疾病的潜在结果;也不可能观测到他不吸烟但有高血脂的情况下心血管疾病的潜在结果。这些潜在结果对这个个体w是先验不可观测的。令Yt(w)表示YtSt(w)为接受处理t的潜在结果。
下面用这些记号给出个体、平均和分布意义上的因果作用： 
· 对于个体w，二值处理T(T=0,1)对中间变量S的个体因果作用: ST=1(w)－ST=0(w)· 对于总体，处理T对中间变量S的平均因果作用 (average causal effect, ACE): ACE(T→S)=E(ST=1－ST=0)E(·)表示对总体中所有个体的期望。
· 对于总体，处理T对中间变量S的分布因果作用 (distributional causal effect, DCE): DCE［T→(S>s)］=P(ST=1>s)－P(ST=0>s)这里s是中间变量的某个水平。
类似地，我们定义处理对结果变量的因果作用： ACE(T→Y)=E(YT=1－YT=0)对于多值中间变量S，定义中间变量S=s相对S=s′对结果变量Y的因果作用: ACE(S→Y|s,s′)=E(Ys－Ys′)为了避免在前一节提到的、达到相同血脂水平的吸烟人与不吸烟人是不同人群，他们不具有可比性的问题，Frangakis 和 Rubin提出了主分层意义上的直接作用的概念\[4\]。不是只用中间变量观测到的水平对人群进行分层，而是用中间变量的所有潜在水平进行分层，称为主分层(principal stratification)：记Q(w)={St(w),t∈䦶Euclid Math OneTAp}其中䦶Euclid Math OneTAp是一个集合，表示所有可能的处理。当仅两种处理时，Q(w)={S1(w),S0(w)}。具有相同Q(w)=q的个体定义为一个主分层，在一个主分层Q=q中处理对结果的因果作用定义为不同处理之间潜在结果的比较。例如，一个主分层内的个体w，两种不同处理t与t*的潜在结果之差：Yt(w)－Yt*(w)。
主分层直接作用定义为：在某个St=s，t∈䦶Euclid Math OneTAp的主分层，存在t≠t*使得Yt≠Yt*，那么称T对Y有主分层直接作用。主分层直接作用刻画了处理T对中间变量S没有因果作用时，处理T仍对结果变量Y有作用。Frangakis 和 Rubin\[4\]给出了数值例子说明，可能会存在有主分层直接作用，但是条件独立YT|S成立；相反地，还可能会没有主分层直接作用，但是条件独立YT|S不成立。这说明3.1节基于关联度量定义的直接作用与主分层直接作用不同，不能刻画出因果意义上的直接作用。特别是，条件独立YT|S成立时可能会有主分层直接作用。
VanderWeele\[21\]定义主分层间接作用为：如果P(Yt－Yt*|Q=q)与q有关，那么称T对Y有主分层间接作用。等价地，如果P(Yt－Yt*|St=s,St*=s*)与s或s*有关，那么称T对Y有主分层间接作用。改变中间状态{St,St*}，结果Yt和Yt*的差别将变化。无主分层间接作用表现为，不管怎么改变中间因素的数值{s,s*}都不影响结果Y。
尽管在概念上，利用主分层能够清楚地刻画因果意义上的直接作用和间接作用，但是，在操作上不能够根据观测数据来确定个体属于哪一个主分层。考虑二值处理的情况。因为通常观测到一个个体的ST=1(w)的话，ST=0(w)是不可观测的。任一个个体w属于哪一个主分层是未知的。因此主分层的直接作用和间接作用的识别需要更多的假定。另一方面，总因果作用不能用主分层直接作用和主分层间接作用表示。例如，平均主分层直接因果作用定义为:E(Yt－Yt*|St=St*)或者对于一个具体的中间变量值s定义平均主分层直接因果作用为: 对于St=St*=s的主分层，E(Yt－Yt*|Q=(s,s))平均主分层间接作用定义为： 对于St≠St*的两个主分层Q=q,q′，E(Yt－Yt*|Q=q)－E(Yt－Yt*|Q=q′)因为Q=q和Q=q′可能是不同的总体，这个主分层间接作用的定义是不同总体之间的比较。
3.3控制的和自然的直接作用
处理T对结果Y的总作用（total effect) 用潜在结果模型定义为 TE(t,t*)=Yt－Yt*描述了同一个体在不同处理t≠t*下潜在结果的差。Pearl\[16\] 定义了控制直接作用 (control direct effect) 为 CDEt,t*(s)=Yts－Yt*s控制直接作用描述了在控制中间变量S=s不变的情况下，两种处理t和t*对结果变量Y的影响作用。因为不能通过控制某些变量来消除直接作用，因此Pearl没有严格地定义控制间接作用 (control indirect effect)。如果硬性地将总作用和控制直接作用的差定义为控制间接作用的话，控制间接作用定义为 CIEst,st*(t)[]=TE(t,t*)－CDEt,t*(st*)
=Ytst－Yt*st*－［Ytst*－Yt*st*］
=Ytst－Ytst*描述了处理T=t不变的情况下，两种中间变量S=st和S=st*对结果Y的影响。
与控制直接作用不同，保持中间变量在自然状态S=st′下，Pearl定义了自然的直接作用 (natural direct effect) 为 NDEt,t*(t′)=Ytst′－Yt*st′通常采用0表示自然的处理状态t′，并用自然处理状态作为对照处理t*，定义自然直接作用为NDEt,0(0)=Yts0－Y0s0描述了在保持中间变量为自然状态s0时，改变处理为t导致的对结果的作用。自然的间接作用 (natural indirect effect) 定义为 NIEt,t*(t′)=Yt′st－Yt′st*描述了保持处理在t′不变的情况下，比较不同处理t≠t*导致的中间状态变化引起的结果变化。处理对结果的总作用可以表示为自然直接作用和自然间接作用之和： Yt－Yt*[]=Ytst－Yt*st*=Ytst－Ytst*+Ytst*－Yt*st*
=NIEt,t*(t)+NDEt,t*(t*)Pearl用了一个例子来解释自然作用和控制作用的差别。设想有一位心脏病病人，如果他接受T=1治疗，就会发烧，因此他就服用阿司匹林S=1。假定对这位病人来说，只有接受治疗T=1并且服用阿司匹林S=1的话，才能治好病YT=1,S=1=1，那么，对于这个病人，就有控制的直接作用。这是因为控制他服用阿司匹林的情况下，治疗是有效的： YT=1,S=1－YT=0,S=1>0但是，对于这个病人没有自然的直接作用。这是因为保持这个病人不接受治疗T=0的自然中间变量状态ST=0=0，他不会服用阿司匹林，那么，治疗T=1对他是无效的YT=1,S0=0－YT=0,S0=0=0VanderWeele\[21\]讨论了各种作用之间的关系： 
· 如果对每个个体都没有自然直接作用NDEt,t*(t*)=0, 那么，处理T=t相对不同处理T=t*没有对Y的主分层直接作用。
· 如果对每个s和每个个体都没有控制直接作用CDEt,t*(s)=0, 那么，处理T=t相对不同处理T=t*没有对Y的主分层直接作用。
· 无主分层直接作用，但可能有控制和自然直接作用。
· 无主分层间接作用，但可能有自然间接作用； 有主分层间接作用，但可能无自然间接作用。
另外，我们还可以得到: 如果对每个个体和每个s（实质上只要对每个个体的st*） 都没有控制直接作用CDEt,t*(s)=0, 那么，对每个个体都没有自然直接作用NDEt,t*(t*)=0。
4因果作用的可传递性问题
所谓传递性，是指如果一个事物A增大使得事物B增大，并且事物B增大使得事物C增大，那么事物A增大使得事物C增大。在这一节中,我们将说明即使在任何意义上都没有直接作用的情况下，因果作用的统计推断的结论也不存在传递性。考虑一个最简单的情况，假定处理对结果的所有作用都是通过一个中间变量产生的，也就是对每个个体来说，处理对结果没有控制直接作用，即每个个体都有Yts=Yt*s=Ys, s。这时可以知道也不存在主分层直接作用和自然直接作用。进一步假定对每个个体来说，中间变量对结果都有正作用，即Ys>Ys*, s>s*，那么，如果对任一个体，处理T=t相对T=t*(t>t*)都对中间变量S有正作用的话，处理一定对结果有正作用，即St>St*蕴含Yt>Yt*，这是因为Yt=Ytst=Yst>Yst*=Yt*st*=Yt*也就是说，在个体水平上，如果处理T=t对中间变量S有增加作用，并且S对结果Y有正作用，那么处理T=t对结果Y一定有正作用，我们称关于个体的推断结论满足传递性。
例如，心脏病病人的寿命作为结果变量Y。心律是否正常为中间变量S，S=1表示心律正常，S=0表示心律不正常。处理是一种药品，T=1表示接受药物治疗，T=0表示服用安慰剂、未接受药物治疗。假定病人的寿命只受心律是否正常的影响，药物仅是通过纠正心律失常对寿命起到延长的作用，即，Yts=Ys，并且YS=1>YS=0。也就是说，这种药物对病人的寿命没有任何意义上的直接作用。在药物临床试验时，为了评价药物对延长寿命的作用，通常不可能长时间观察病人的寿命。假定医学知识告诉我们，任何心脏病病人在心律正常情况下的寿命都会比其在心律失常情况下的寿命长。根据这个医学知识，用心律是否正常作为寿命的替代指标，评价药物对心律失常的疗效。如果这种药物能使每一位病人的心律正常或维持原来的心律的话，即ST=1≥ST=0，那么，这种药物一定能延长或至少不减少每位病人的寿命，YT=1≥YT=0。在临床试验中，随机地将病人分派到药物治疗组和安慰剂对照组，分派到药物治疗组的病人，可以观察到服药一段时间后的心律是否正常ST=1，但是不可能观察到其服用同样一段时间安慰剂后的心律正常与否。因此，不可能根据病人服药后的心律正常与否判断该药物对这个病人的心律是否有反作用，即不能判断不等式ST=1≥ST=0是否成立。当服药病人出现了心律不正常ST=1=0时，因为观测不到该病人在不服药时的心律ST=0，所以，我们不能否定也不能肯定这个不等式。
上面的例子说明，在很多实际研究中得不到个体水平的因果作用。因此，我们不得不借助统计推断方法来评价总体水平的因果作用。这样的话，我们提出一个问题：是否关于总体的统计推断结论具有传递性？ 在总体的统计意义上，如果根据统计推断方法得到药物对心律失常有显著的纠正作用，而且心律正常能延长每一个人的寿命，那么这种药物就一定会显著地延长病人的寿命吗？ 我们的答案是否定的。
为了说明这一点，还是考虑上面最简单的情况，这也是最有利于统计结论可传递的情况，即假定处理对结果在任何意义上都没有直接作用(Yts=Yt*s=Ys), 并且每个个体中间变量对结果都有正作用(Ys>Ys*, s>s*)。我们考虑一个数值的例子。设总体只有100位心脏病病人，表1给出了每个病人完整的潜在数据。100位病人按照主分层(ST=0,ST=1)的取值分为四个主分层。表中给出了每一层的人数，假设每一层中病人都有一样的潜在寿命。例如，第2主分层有40人，他们接受治疗的话，心律就会正常(ST=1=1)，不接受治疗的
表1100位心脏病病人完整的潜在数据，YS=1>YS=0，T对S有总体水平的正作用[][]主分层[]心律正常与否的潜在寿命[]不同处理下的寿命主分层编号
[]人数
[]ST=0[]ST=1[]YS=0[]YS=1[]YT=0[]YT=11[]20[]0[]0[]9[]10[]9[]92[]40[]0[]1[]6[]7[]6[]73[]20[]1[]0[]5[]8[]8[]54[]20[]1[]1[]3[]5[]5[]5话心律就异常(ST=0=0)； 这些病人如果心律正常的话能活7年(YS=1=7)，心律异常的话能活6年(YS=0=6)。表1中最后两列是根据前面四列推算出来的； 例如，第2主分层的40位病人，他们接受治疗的话，那么心律会正常，因此能活7年，即YT=1=7； 不接受治疗的话，那么心律异常，只能活6年，即YT=0=6。由表中第3和4列100人的数据，我们可以得到这100人都接受治疗的话，心律正常的百分比为(40+20)/100，他们都不接受治疗的话，心律正常的百分比为(20+20)/100；这两个百分比之差为治疗对心律失常的平均疗效: ACE(T→S)=40+20〖〗100－20+20〖〗100=20〖〗100>0也就是治疗对心律有纠正作用。这里假定了总体所有个体的数据都得到了，因此该推断结论是确定的。如果数据是从抽样得到的样本，我们可以考虑将表中数据扩大到更大的样本量，已达到任意水平的统计显著结论。类似地，可以从表中最后两列得到治疗延长病人寿命的平均作用: ACE(T→Y)[]=9×20+7×40+5×20+5×20〖〗100－9×20+6×40+8×20+5×20〖〗100
=－0.2<0表明治疗减少了总体的平均寿命。该例子说明治疗对寿命的作用都是通过心律是否正常起作用，心律正常确切地能延长每一个人的寿命，在总体水平上治疗对纠正心律异常有确定的平均作用。我们不能将这两个正作用传递得到治疗能延长总体寿命的平均作用。
在这个例子中，我们看到统计结论不可传递是因为存在主分层 (ST=0,ST=1)=(1,0)。也就是T对S的正作用是统计意义上的，而不是个体作用。下面说明在T经过S到Y的因果路径上，如果T对S有个体水平的正作用，即ST=1≥ST=0，但是S对Y的作用是总体意义上的正作用，那么T对Y的作用也不可预测。
假设一个随机化临床试验证明某种新药比传统药有显著的疗效，那么是否在门诊开这种新药的处方就一定会比开传统药处方得到更好的治疗结果？ 在门诊医生给病人开新药的处方对病人服用新药会有建议的作用，但是可能会出现一些病人由于费用或受传统药的影响等因素不依从医生的处方的情况。用T表示医生所开处方，T=1表示新药处方，T=0表示传统药处方。令St表示当医生开T=t处方时，病人实际服用的药物，St=1表示医生开t处方时，病人实际服用新药；St=0表示服用传统药。假定医生开新药处方对每位病人服用新药都有积极作用，尽管有些病人可能不依从，即ST=1≥ST=0。令Yts表示医生开t处方，病人服用s药物，病人服药后的疾病状态，1表示康复，0表示未康复。假定病人是否康复只与实际服用药物有关，与处方无关，即Yts=Ys。这个假定意思是处方对康复没有直接作用。下面用一个数值例子说明新药在门诊使用后不一定比传统药得到更好的结果。设想一个300位病人的总体，表2给出了每个病人完整的潜在数据。300位病人按照主分层(ST=0,ST=1)的取值分为三个主分层。因为假定新药处方对病人服用新药有积极作用，所以表中不存在(ST=0,ST=1)=(1,0)的主分层，既不存在不开新药服新药、开新药反而不服新药的病人。表中第5和6列给出了病人服传统药和新药的情况下康复的人数。由第2~5列可以得到第6和7列，给病人开传统药处方和新药处方的情况下康复的人数。表中3个主分层可以解释为，主分层1是病情轻的病人，不管服用什么药，他们都有很高的康复率； 主分层2是中度病情的病人，他们愿意依从医生的处方，但是新药对他们不是很有效； 主分层3是重病情的病人，他们知道传统药不会有疗效，不管医生开什么药，他们都会想办法买到新药服用。由第5和6列可以得到300人都服传统药或都服新药的话，康复的百分比分别为 (80+60+0)/300=140/300和(80+50+20)/300=150/300。说明在总体水平上新药比传统药确切地更有疗效。如果是临床试验的话，可以将表中数据扩大，能达到任意水平的统计显著结论。类似地，可以从表中最后两列得到开处方的效果，开传统药处方的效果是(80+60+20)/300=160/300，而开新药处方的效果是(80+50+20)/300=150/300。说明在总体水平上开传统药处方比开新药处方能确切地得到更好的结果。该例子说明总体水平有统计显著意义的药物，即使医生督促每位病人服药都有积极的个体作用，也可能得到相反的效果。这个例子也说明采用临床试验方法评价药物的疗效，也许需要考虑到药物批准后在门诊的依从性，应该保证药品上市后门诊和临床试验阶段有大致相同的依从程度。上市后的新药的价格、服药后的症状等都会影响病人的依从性。表2300位病人完整的潜在数据，ST=1≥ST=0，S对Y有总体水平的正作用[][]主分层[]服药S后康复人数[]开处方T后康复人数主分层编号
[]人数
[]ST=0[]ST=1[]#{YS=0=1}[]#{YS=1=1}[]#{YT=0=1}[]#{YT=1=1}1[]100[]0[]0[]80[]80[]80[]802[]100[]0[]1[]60[]50[]60[]503[]100[]1[]1[]0[]20[]20[]20我们从两个方面: 
(1) T对S有总体水平的正因果作用，而S对Y有个体水平的正因果作用； 
(2) T对S有个体水平的正因果作用，而S对Y有总体水平的正因果作用； 
分别用例子说明T对Y都可能有总体水平的负因果作用。显然，如果T对S且S对Y都只是总体水平的正因果作用，那么更可能会出现T对Y有总体水平的负因果作用。因此，我们回答了上面提出的问题，因果作用的统计结论可能没有可传递性。当统计推断方法应用于一个科学研究的各个阶段中，由于统计结论不具备传递性，使得我们很难根据各个阶段的统计结论进行综合推断。还原论的方法将一个大系统分解为局部，由局部得到的统计结论也许难以得出大系统的正确结论。但是，不排除有些统计推断方法可以进行分解和综合，例如在第2节讨论的图模型的似然估计和网络结构学习的问题是可以分解的，这个分解需要的条件是两个局部在给定公共部分后条件独立。
5讨论
还原论的方法和统计推断的方法是人们从事科学研究的两个重要的工具，被广泛应用于科学研究的各个领域。还原论的方法将整体分解为局部，综合局部得到的结论推断出整体的结论。关于统计结论是否能综合，本文提出了统计推断结论的不可传递性的问题，探讨了将局部统计结论综合得出整体统计结论的问题。
统计学发展了一个多世纪，统计学者已经提出了大量有效的统计推断方法，各个领域的科学工作者已经广泛应用这些统计推断方法。在科学研究中，人们积累了大量利用统计方法得到的结论和知识，如何根据这些结论和知识进行科学推断？ 科学工作者也许会认为，他们只要能够使用统计方法对每个阶段得到的数据集合孤立地进行正确的统计分析，然后就可以根据专业理论知识对各个阶段和各个局部得到的正确的统计结论进行综合推断分析。其实不然，即使在研究的各个阶段都得到了正确的统计结论，我们应该如何综合这些正确统计结论，仍然是一个与统计推断相关的困难问题。这个问题尚没有得到足够的关注，不仅非统计专业的工作者不知道，就连统计学者也不知道应该如何解决这个问题，甚至可能不存在一种方法能从局部统计结论综合得出整体统计结论。也许只有利用一些貌似合理、但不可证伪的假定，才能形而上学地解决这个问题。探索综合局部的统计结论的条件和方法是一个具有挑战性的问题。

致谢感谢会议组织者周志华教授和杨强教授邀请我参加2010年的机器学习会议和本文的约稿。本文得到了我的学生丁鹏、何平和吴镇国的建议与讨论。本研究得到国家基金委项目(NSFC 10721403, 10931002)的资助。
参考文献
\[1\]Asmussen S, Edwards D. Collapsibility and response variables in contingency tables. Biometrika, 1983, 70: 567~578
\[2\]Chen H, Geng Z, Jia J. Criteria for surrogate end points. J Royal Statist Soc B, 2007, 69: 919~932
\[3\]Cox DR, Wermuth N. A general condition for avoiding effect reversal after marginalization. J Roy Statist Soc B, 2003,  65: 937~941
\[4\]Frangakis CE, Rubin DB. Principal stratification in causal inference. Biometrics, 2002, 58: 21~29
\[5\]Frydenberg M, Lauritzen SL. Decomposition of maximum likelihood in mixed interaction models. Biometrika, 1989, 76: 539~555
\[6\]Geng Z. Multidimensional contingency tables with missing data. Communications in Statistics\|Theory and Methods, 1988, 17: 4137~4146
\[7\]Geng Z. Decomposability and collapsibility for log\|linear models. Applied Statistics, 1989, 38: 189~197
\[8\]Geng Z. Collapsibility of relative risks in contingency tables with a response variable. J Royal Statist Soc B, 1992, 54: 585~593
\[9\]Geng Z, Asano C. Recursive procedures for hierarchical loglinear models on high\|dimensional contingency tables. J Jap Soc Comput Statist, 1988, 1: 17~26
\[10\]Geng Z, Asano C. Strong collapsibility of association measures in linear models. J Royal Statist Soc B, 1993, 55: 741~747
\[11\]Guo JH, Geng Z. Collapsibility of logistic regression coefficients. J Royal Statist Soc B, 1995, 57: 263~267
\[12\]Ju C, Geng Z. Criteria for surrogate endpoints based on causal distributions. J Royal Statist Soc B, 2010, 72: 129~142
\[13\]Lauritzen SL.  The EM algorithm for graphical association models with missing data. Comput Statist Data Analy, 1995, 19: 191~201
\[14\]Lauritzen SL. Discussion on causality. Scand J Statist, 2004, 31: 189~192
\[15\]Ma ZM, Xie X, Geng Z. Collapsibility of distribution dependence. J Royal Statist Soc B,2006, 68: 127~133
\[16\]Pearl J. Direct and indirect effects. Proc 7th Conf Uncertain Artifi Intell,2001, 411~420
\[17\]Pearl J. Causality: Models, Reasoning, and Inference. 2nd ed. Cambridge: Cambridge University Press, 2009
\[18\]Prentice RL. Surrogate endpoints in clinical trials: definition and operational criteria. Statistics in Medicine, 1989,8: 431~440
\[19\]Rubin DB. Direct and indirect causal effects via potential outcomes. Scandinavian Journal of Statistics, 2004, 31: 161~170
\[20\]Simpson EH. The interpretation of interaction in contingency tables. J Royal Statist Soc B,1951, 13: 238~241
\[21\]VanderWeele TJ.  Simple relations between principal stratification and direct and indirect effects. Statist Proba Lett,2008, 78: 2957~2962
\[22\]VanderWeele TJ, Robins JM.  Signed directed acyclic graphs for causal inference. J Royal Statist Soc B,2010, 72: 111~127
\[23\]Wermuth N.  Parametric collapsibility and the lack of moderating effects in contingency tables with a dichotomous response variable. J Roy Statist Soc B,1987, 49: 353~364
\[24\]Whittaker J.  Graphical models in applied multivariate statistics. New York: John Wiley & Sons, 1990
\[25\]Wu ZG, He P, Geng Z. Sufficient conditions for concluding surrogacy based on observed data. Statistics in Medicine,2011, 30: 2422~2434
\[26\]Xie X, Geng Z. A recursive method for structural learning of directed acyclic graphs. J Mach Learn Res,2008, 9: 459~483
\[27\]Xie X, Geng Z. Collapsibility for directed acyclic graphs. Scand J Statist,2009, 36: 185~203
\[28\]Xie X, Geng Z, Zhao Q. Decomposition of structural learning about directed acyclic graphs. Artificial Intelligence,2006, 170:422~439
\[29\]耿直. 因果挖掘的若干统计方法. 见:周志华，王珏主编.机器学习及其应用2009. 北京: 清华大学出版社，2009,49~802〖〗机器学习的几何观点何晓飞
浙江大学计算机科学与技术学院， 杭州3100271引言
随着信息技术的迅速发展，数据采集能力的提高导致各领域数据的维度呈指数级增长（curse of dimensionality）\[1\]。如何从大量原始数据中提取有效的信息规律是国际上数据挖掘和信息检索领域最前沿的研究方向之一，也成为了机器学习研究者们面临的一大挑战。近十年兴起的机器学习的一般过程可以被描述为:机器学习过程:数据输入→（目标函数+目标函数优化）→输出其中，数据输入一般是存在于高维欧氏空间的一些数据x1,x2,…,xm，xi∈Rn。每个数据点拥有类别标签yi。我们通过一定的学习方法求得一个函数f，这个函数的作用是将原始的数据点映射到它属于的类别空间。也即f(xi)→yi。传统的机器学习方法中，数据点与数据点之间的距离和映射函数f都是定义在欧氏空间中的。然而在实际情况中，这些数据点可能并不是分布在欧氏空间中的，因此，传统欧氏空间的度量难以直接用于真实世界的非线性数据，从而需要对数据的分布引入新的假设。
流形（manifold）\[2\]是局部具有欧氏空间性质的空间，包括各种维度的曲线曲面，例如球体、弯曲的平面等。流形的局部和欧氏空间是同构的。流形学习假设所处理的数据点分布在嵌入于外维欧氏空间的一个潜在的流形体上，或者说，这些数据点可以构成这样一个潜在的流形体。
以人脸图片为例\[3\]，我们用一架移动的相机对一张固定的人脸进行拍摄，得到m张由n×n像素点构成的不同角度不同光照下的灰度人脸图片。每张图片都是存在于欧氏空间Rn2中的一个数据点。然而实际上，不同图片的差异是由相机的参数自由度（位置、角度和光照）产生的。我们可以把这些图片看成是嵌入在高维欧氏空间Rn2中的低维流形上的点。在该例中，该流形的维度即为相机的参数个数。在新的模型下，我们用测地线（geodesic distance）代替欧氏距离作为流形上距离的度量，而映射函数也被重新定义在流形体上。在这样的假设下，数据点的本征维度即等价于数据所处的流形维度。
为了表示数据点，我们需要引入坐标系，然而流形上本身很难定义坐标系。因此，为了表示流形上的点，需要将流形放入外围空间（ambient space）中，用外围空间的坐标系来表示流形上的点。例如，考虑将一个球面放入R3空间中，球面本身是一个流形，而球面上的点可以由R3中的x,y,z三维坐标来表示。对于球面流形本身来说，分布在流形上的点的本征坐标（intrinsic coordinate）是两维的，因为只要两个自由度（经度和纬度）就可以表示球面上的点。因此流形学习的任务可以概括为：在保持流形的某些几何特性的前提下，找到其对应的本征坐标表示。这个过程也可称为参数化（parameterization）。继续以球面为例，直观地说，可以将这个过程想象成将三维空间中的球面展开摊平在二维平面上。
流形学习利用了数据的几何结构进行学习，相比其他机器学习方法能更好地利用数据本身的结构特点。但是随之面临的问题是，我们只有流形上的离散采样点（输入数据）（如图2），却不知道数据所分布的流形的真实结构（如图1）。因此，我们需要利用流形的几何拓扑特性，根据离散点去猜测整个流形的结构。例如，需要微分几何的知识在流形上定义距离概念，需要利用泛函分析帮助我们重新在流形上定义映射函数。
图1数据分布在潜在的流形上 
[]图2离散的数据采样点的分布 
机器学习及其应用2011〖〗机器学习的几何观点本文的主旨是介绍流形学习中的降维方法以及利用流形理论进行主动学习的方法。在这之前将先在第2节简要介绍这些方法涉及的无监督学习、半监督学习以及监督学习的概念。第3节将主要介绍一种线性流形降维算法——保局投影（locality preserving projection）及其应用。第4节则主要介绍在流形上的主动学习方法。第5节将介绍一些流形学习的开放问题和热点研究方向。
2监督学习、半监督学习与无监督学习
在机器学习的过程中，按照学习所利用的数据种类可将学习方法分成三大类:监督学习、无监督学习和半监督学习。当输入每个数据资料是带有类别标签（label）的，机器将根据数据和对应的标签进行学习，产生模型（model）；之后遇到新的数据，用学习出来的模型对新的数据进行标签分类，这个过程属于监督学习。许多经典的学习算法如支持向量机（SVM）\[4\]，人工神经网络（ANN）\[5\]都属于监督学习的范畴。对于无监督学习来说，输入训练的只有数据，而没有标签信息，机器将学习这些未标记数据的模式（pattern），通过数据内在的一些特性和联系，将数据自动分成几类。之后如果遇到新的数据，根据产生出来的模型，只判断新数据是属于哪种由原来数据所构成的模式。属于这一范畴的算法有谱聚类（spectral clustering）\[6\]、K\|means\[7\]等。半监督学习介于监督学习和无监督学习之间，研究起步相对较晚。由于大量标记数据的获得很费时耗力，在这样的背景下，同时利用有标记的数据和无标记的数据进行学习的半监督学习方法应运而生。在标记数据个数有限的情况下，半监督学习能够利用未标记的数据进行学习。如图3(a)所示，实际数据点只有极少量有标记。在图3(b)中，由于有标记的信息少，监督学习没有其他可利用的信息，难以找到正确的分类面。在图3(c)中，半监督学习利用额外的无标注数据点找出沿数据分布平滑的分类方案。除了半监督学习之外，利用未标记数据进行学习的算法还有直推学习（transductive learning）。
图3(a) 原始数据点分布图，只有两个数据点有标注； (b) 监督学习没有利用其他未标注数据点的信息，难以找到正确的分类面； (c) 半监督学习利用额外的无标注数据点找出沿数据分布平滑的分类方案 
近十年兴起的流形学习经典降维算法如ISOMAP\[8\]、LLE\[9\]、LE\[3\]、LPP\[10\]都属于无监督学习的范畴。流形假设的引入，增加了对数据结构的考量，有效提高了目标任务学习的效果。在下面的章节中，我们将介绍基于流形的降维和主动学习算法。LPP利用数据的流形特征，将高维数据点降到低维空间，并保持了数据局部的几何特性。成功用于人脸识别、数字识别、检索等应用方向。LapRDD\[20\]方法综合了LapRLS\[11\]和主动学习方法，选取了数据中具有代表性的点进行标识。通过对数据几何进行流形假设，利用未标记的数据点估计了数据分布，进行半监督学习，增加了最终的模型预测能力，并在图像压缩和视频压缩领域取得良好的应用效果。
3基于几何拓扑的降维算法
在数据挖掘领域经常会遇到高维度的数据输入，如多媒体数据、股票交易数据、文档词频数据等。而高维的数据输入常常会导致问题的复杂化，甚至会影响后期学习的效果，增加计算的复杂度。因此对高维数据进行降维处理显得尤为重要。基于流形学习的数据降维方法假设观测到的高维数据是分布于嵌入欧氏空间中的低维流形上的点。和一般的降维方法类似，流形学习降维也是将一组在高维空间的数据点映射到低维的空间上重新表示。不同之处在于，在映射中利用了流形的几何特性，可以有效地学习和保持数据集的内在几何结构。因此，流形学习成为了数据挖掘、模式识别、计算机视觉等相关领域的研究热点。
3.1流形降维
流形学习的基本设定是：假设数据点x1,x2,\:,xm∈M是分布于一个低维子流形M上，M嵌入于一个高维欧氏空间Rn。我们需要利用流形的特性找到数据所分布的低维流形在欧氏空间中的表示。即要找到一组对应的y1,y2,\:,ym∈Rk,kn,并能保持原有数据的某些几何特性。这个过程也可以直观地看成是从一堆随机分布的数据点中学习出数据对象（流形）的几何和拓扑结构过程。早期的流形学习工作主要集中在以线性为假设的欧氏空间中。近十年来，涌现出许多研究流形非线性结构的工作。我们将这些工作总结为三大体系：第一组是属于Kernel PCA类\[25\]（PCA的核方法）；第二组是基于算子和距离的流形学习；第三组是流形的切空间学习。
ISOMAP引入测地线距离来表示潜在流形上点与点之间的距离，并在降维过程中保持该距离不变。LLE在降维过程中保持了数据的局部拓扑结构。LE方法在黎曼几何的框架内，用邻接图来描述一个流形，并在映射到低维空间的过程中，保持了图的局部邻接关系。根据文献\[26\]所示，这些非线性算法都可以由Kernel PCA算法通过选择不同的核函数得到。在这些算法的基础上，还衍生出C\|ISOMAP\[27\]、MLLE\[28\]和MVU\[29\]等相关的工作。
传统数据点之间的距离度量是利用欧氏距离作为尺度的，这种直接的距离表达方式忽视了数据本身的非线性结构。因此在近几年，基于算子和距离的学习在机器学习中得到广泛运用。其中代表性的算法有扩散距离（diffusion distance）和扩散映射（diffusion map）\[30\]。
在流行算法中两种最重要的算子为拉普拉斯\|贝尔特拉米算子（Laplace\|Beltrami operator）和海森算子（Hessian operator）。LE算法就是通过最小化拉普拉斯算子的模来实现狄利克雷泛函（Dirichlet functional）的离散化。而这种离散化方法主要归功于谱图理论\[6\]。除了降维之外，拉普拉斯算子在半监督学习、主动学习等问题中得到广泛的应用。在许多实际问题中，外围空间的维度往往非常的高，因此在很多机器学习问题中存在维度灾难。一个自然的解决方法是对学习函数应用光滑性准则。而之前的研究表明，拉普拉斯算子可以很好地度量定义在流形上的函数的光滑性。因此，在许多半监督问题中，拉普拉斯算子都用作正则项。比如Laplacian Regularized Least Squares（LapRLS）利用了流形的本征几何去解决了这样一个病态的学习问题。基于流形观点的主动学习同样得益于拉普拉斯算子。在实际中，标注样本往往非常昂贵，因此这里的挑战是如何确定哪些未标注的样本是最具有信息量的（即最大程度地改善分类器）。X.He\[18\]等人提出的主动学习回归算法，与传统只将损失函数定义在有标注的数据点上的方法不同，该方法利用了拉普拉斯算子，将损失函数同时定义在了所有的数据点上。
海森算子是近几年在流形学习中用到的另一个重要的算子。基于海森算子的流形学习包括Hessian eigenmaps（HLLE)\[31\]和基于Elles energy的方法\[32,33\]。HLLE通过最小化Hessian energy来找到等距映射。在算法\[32,33\]中，Hessian energy被推广到Elles energy，并将其应用到回归和半监督学习问题中。
切空间学习是流形学习的另一个重要方向。LTSA\[34\]通过拼接数据的局部切空间坐标来构造数据的全局坐标。类似的思想也体现在流形绘制（manifold charting)\[35\]算法中。黎曼流形学习（Riemannian manifold learning)\[36\]使用法坐标（normal coordinate）来展开流形，试图保持流形的度量。这些降维映射的质量往往依赖局部切空间的估计。局部平滑流形学习（locally smooth manifold learning)\[37,38\]利用切空间的光滑性正则项来学习出全局光滑的切空间。切空间是用来学习流形几何特性的重要工具，大多数流形上的微分算子是定义在流形的切空间上的，如图4所示，我们可以用切空间来表征流形。目前切空间的工作主要是利用数据点的邻接点去构造流形的切空间。非局部（non\|local）的流形切空间学习方法通过使用加权投影距离来衡量切空间的好坏\[39\]。
图4用切空间表征流形示意图\[43,44\] 
3.2几何和拓扑
流形学习问题的具体数学框架为：给定数据点x1,x2,\:,xm∈MRn,dim M=d并且dn。我们需要学习在流形之间的映射f:M→N。这其中有很多种准则去定义最优的映射，然而基本上每一种准则都可以归结为如下的形式：minE(f)=∫ML(f)其中，L表示某个微分算子。在离散形式的情况下，我们最小化min∑iL(f)xi传统的机器学习往往考虑目标流形是欧氏空间度量的，如，N=Rd。这是最方便的一种方式，因为在欧氏空间中我们可以很简单地计算出两点之间的最短距离。然而，如果M与欧氏空间不等距（isometric）或者流形的拓扑结构并不是平凡的（比如拓扑上有洞），那么这样映射到欧氏空间就会产生问题。因为这样强行映射必然导致信息的丢失甚至破坏原来流形的结构。
因此我们首先需要学习流形的拓扑结构，从而可以帮助判断映射的好坏。然而，仅仅通过随机的数据点去计算整个流形的拓扑结构是很困难的。因为数据点是离散的，而拓扑却是一个连续的概念。基于此，我们必须通过构造一个连续的对象去逼近流形。在这方面有两个主要的研究工作，一个是持续同调方法（persistent homology）\[40\]；另一个是高置信同调计算（computing the homology with high confidence）\[41\]。两种方法都是先通过数据点构造单纯复形（simplicial complex）。构造过程取决于每个数据点为中心球的半径大小。当半径过大时，容易覆盖流形内在的洞（intrinsic hole）；当半径过小时，这些球就不会连起来，从而导致构造出错误的单纯复形。高置信同调计算方法对于采样的要求很高。而持续同调方法利用稳定性来判断球半径的好坏。持续同调方法通过持续变换球的半径值，直到找到一个稳定的区间段来求得同调群。
从几何的角度看问题，能量函数E(f)反映了映射希望保持的原流形的几何特性。我们首先考虑等距准则。令df表示函数f的微分。对于每一个x,dfx，是从切空间TxM到切空间Tf(x)N的线性映射。若df是正交的，则f是等距的。令λj为df的特征值，则有E(f)=∫ML(f)=∫M∑jλj－12众所周知，映射中等距的性质是很难保证的，在大多数情况下甚至不可能达到。退而求其次的方法是放松等距的约束，去寻找一个调和的映射\[42\]，因为等距必导出调和。对于调和映射，函数E(f)重新定义为E(f)=∫Me(f)，其中e(f)即为函数f的能量密度函数，e(f)x=1〖〗2‖dfx‖2H－S其中‖·‖H-S表示的是dfx项的希尔伯特施密特模（Hilbert\|Schmidt norm）。E(f)被称为函数f的全能量。对‖dfx‖2H-S进行x求导可得到：‖dfx‖2=∑ih(dfx(ei),dfx(ei))其中{ei}是TxM的正交基，h是流形N的黎曼度量。上述问题的解是一个调和映射。和Laplacian Eigenmaps类似，利用函数的全能量来描述定义在流形上函数的平滑性，也是一个很好的选择。Ellesenergy\[32\]和Hessianenergy\[33\]是最近提出的利用能量函数约束在流形上求回归函数的方法。这两种方法考虑下述目标函数E(f)=∫M‖䥺SymbolQC@′df‖2采用该目标函数的原因是如果所求映射函数f满足䥺SymbolQC@′df=0，则函数f将具备完全测地线性质，即映射f将M上的测地线映射到N上的测地线。
3.3保局投影
传统的降维方法有主成分分析PCA（principal component analysis）\[12\]、线性判别分析LDA（linear discriminant analysis）\[13\]和独立成分分析ICA（independent component analysis）\[14\]。这些方法能处理具有线性和高斯分布的数据。然而当输入数据呈其他分布结构时，这些方法难以发现隐藏在高维数据中的信息。许多经典的流形算法如Isomap、LLE、LE等都是非线性的，都只能直接得出数据降维之后的结果，得不到具体的“降维映射函数”，因此难以扩展到新的数据。这在实际问题中成为一个应用瓶颈。在此背景下，一种新的流形降维方法，即保局投影（locality preserving projection）\[10\]成功地对LE算法进行了线性化，得到显示的映射函数，并被有效地应用于多种实际问题中。
我们可将LPP算法过程归纳为：给定m个数据点构成的集合X={x1,x2,\:,xm}，每个数据点属于高维空间Rn。需要找到一个转移矩阵A，将这m个数据点映射到另一组点集合y1,y2,\:,ym上，yi∈Rl(ln)。yi=ATxi，每个新点yi代表相应的xi。
LPP算法步骤:
(1) 构造邻接图：将m个数据点构造成邻接图G。定义度量点之间关联性的函数，根据定义，如果xi和xj关联度高（也可以认为是点与点在流形上的相近程度），则在图G上的点i和点j就有边相连。如图5所示为分布在流形上的离散采样原始数据点，图6是根据图5所构造的数据点的邻接图。
一般采用两种函数用来计算点之间的相关性:
a) 䦶Euclid Math OnerCp\|邻接计算法。\[䦶Euclid Math OnerCp∈R\]。如果‖xi-xj‖2<䦶Euclid Math OnerCp,则图G上的点i和点j之间有边相连。
b) k近邻法。\[k∈N\]。如果xi在xj的k个最近邻中或者xj在xi的k个最近邻中，则图G上的i和j之间有边相连。
(2) 赋权重：构造m×m的矩阵W，Wij表示图G上点i和点j之间边的权重值，如果i和j之间没有边相连，则权重为0。Wij的计算方法也有两种。
a) 高斯核。如果点i和点j是相连的，则权重Wij=e-‖xi-xj ‖2[]t(t∈R)。