当前位置：文档之家 › Learning conditional independence relations from a probabilistic model

Learning conditional independence relations from a probabilistic model

  • 格式：pdf
  • 大小：280.20 KB
  • 文档页数：15

Abstract
1
1 Introduction
In designing many traditional information systems and AI systems, a central task is to express our knowledge about the underlying domain in some form of dependency relations. In communication and pattern-recognition systems, it is more desirable that the relations be speci ed using a joint probability distribution (jpd) 2, 8], either in its entirety or in a factorized form. In machine learning 14, 11, 12, 21], to construct classi cation rules or decision trees is the primary objective. For probabilistic reasoning in AI, algorithms were developed to learn a Bayesian network from data samples 6, 3, 15, 13]. In this paper we consider the representation of our knowledge by a Markov network (MN) which is an undirected graph associated with a factorized probability distribution. We have developed an e cient algorithm to learn a MN of a probabilistic model (PM) from data samples produced by the model. Such a representation has a number of advantages as will be discussed in the paper. A description of our algorithm and the preliminary results were presented in 16]. Though the experimental results are promising, two important issues were not addressed. The algorithm employs a greedy search. It was not fully understood why such a myopic search worked so well globally. Secondly, whether a correct MN can be found for any PM was not formally established. In this paper, we formulate the problem as learning an independence map (I-map) and its associated distribution expressed as a MN of a given PM. We will prove that, for any given PM, the proposed algorithm returns a correct MN. The proof of this assertion also o ers deeper insight into the algorithm's working mechanism. As the problem of learning a minimal I-map of a given PM is NP-hard in general 1], any polynomial time algorithm would not guarantee minimality in every case. We show that, however, for a subclass of PMs, the proposed algorithm will indeed return a MN whose structure is a minimal I-map. Section 2 provides the background and terminologies. Section 3 introduces the algorithm. Section 4 shows that our method produces a Markov network as a correct dependency model. Section 5 presents a su cient condition under which the algorithm learns a MN whose structure is a minimal I-map. Section 6 compares this work with related work in traditional estimation of jpds 2, 8], learning of classi cation rules 14, 11, 12, 21] and learning of Bayesian networks 6, 3, 15, 13].
between them. In general, G may not be connected. A junction forest (JF) F of G is a set of JTs each of which is a JT of one component of G. Without confusion, we sometimes refer to a node C in F as a clique when the nodes of G contained in C are of our concern. The intersection of two adjacent cliques in F is called the sepset of the two cliques. Let X , Y and Z be three subsets of nodes in a graph. We use < X jZ jY > to mean that nodes in Z intercept all paths between nodes of X and nodes of Y . In a JF, we use < X jZ jY > to mean that either Z is a clique on the unique path between the clique that contains X and the clique that contains Y or Z is a sepset on that path. Let N be a set of discrete variables and X N . A con guration x of X is an assignment of values to every variable x 2 X . A probabilistic model (PM) over N is an encoding of probabilistic information that determines the probability of every con guration of X for every X N . A PM over N can be speci ed by a joint probability distribution (jpd) over N . However, in practice, we often do not have the jpd, but can only obtain marginal distributions over subsets of N . Our algorithm does not require the jpd as long as there are some independencies among variables. Hence we treat the PM as a means to obtain the necessary marginals without using the jpd as an intermediate step. We only use the jpd as a conceptual entity. The entropy of N de ned by a jpd P is H (N ) = ? Px P (x) log(P (x)): Let X , Y and Z be three subsets of N . X and Y are conditionally independent given Z , denoted Ind(X; Z; Y ), i P (xjyz ) = P (xjz ) whenever P (yz ) > 0. Since we use graphs to represent independency relations among variables, we will use nodes and variables interchangeably. An undirected graph G is an independency map (I-map) of a PM M over N if there is an one-to-one correspondence between nodes of G and variables in N such that for all disjoint subsets X , Y and Z of N we have < X jZ jY > ) Ind(X; Z; Y ). An I-map guarantees that variables graphically separated are independent. However, it does not guarantee that variables graphically connected are necessarily dependent. Conversely, G is a D-map of M , if Ind(X; Z; Y ) ) < X jZ jY >. We call G a perfect map of M if it is both a I-map and a D-map. For a formal treatment of graphical representation of dependency models, see Pearl 13]. Among possible I-maps of a given PM, we only consider those that are chordal due to many desirable properties of chordal graphs 5, 13, 10, 7]. To quantify the strength of dependencies, we associate a chordal I-map with a probability distribution de ned as follows: Let M be a PM over a set N of variables, G = (N; E ) be a chordal graph and F be a JF of G. Let Ci be a clique of F and Sj be a sepset of F . Let P (Ci) and P (Sj ) be the marginal distributions over Ci and Sj , respectively, de ned by M . The jpd P = (Qi P (Ci))=(Qj P (Sj )) is called the projected distribution of M on G (or on F ). The entropy of N de ned by P can be obtained by H (N ) = Pi H (Ci ) ? Pj H (Sj ) 16]. Whenever < X jZ jY > holds in G (or F ), Ind(X; Z; Y ) must hold in P of M on G (or F ). Therefore, we shall say that Ind(X; Z; Y ) is implied by G (or F ). Given a PM M over N and a chordal graph G = (N; E ), we shall call the 3

合集下载

Conditional independence

Conditional independence

Conditional independenceThese are two examples illustrating conditional independence. Each cell represents a possible outcome. The events R, B and Y are represented by the areas shaded red, blue and yellow respectively. And the probabilities of these events are shaded areas with respect to the total area. In both examples R and B are conditionally independent given Y because: \Pr(R \cap B \mid Y) = \Pr(R \mid Y)\Pr(B \mid Y)\,To see that this is the case,one needs to realise that Pr(R ∩ B | Y) is the probability of an overlap of R and B in the Y area. Since, in the picture on the left, there are two squares where R and B overlap within the Y area, and the Y area has twelve squares, Pr(R ∩ B | Y) = \tfrac{2}{12} =\tfrac{1}{6}. Similarly, Pr(R | Y) = \tfrac{4}{12} = \tfrac{1}{3} and Pr(B | Y) =\tfrac{6}{12} = \tfrac{1}{2}.but not conditionally independent given not Ybecause:\Pr(R \cap B \mid \text{not } Y) \not= \Pr(R \mid \mbox{not } Y)\Pr(B \mid\text{not } Y).\,In probability theory, two events R andB are conditionally independentgiven a third event Y precisely if theoccurrence or non-occurrence of R andthe occurrence or non-occurrence of Bare independent events in theirconditional probability distributiongiven Y . In other words, R and B areconditionally independent if and onlyif, given knowledge of whether Yoccurs, knowledge of whether R occursprovides no information on thelikelihood of B occurring, andknowledge of whether B occursprovides no information on thelikehood of R occurring.In the standard notation of probabilitytheory, R and B are conditionallyindependent given Yif and only ifor equivalently,Two random variables X and Y are conditionally independent given a third random variable Z if and only if they are independent in their conditional probability distribution given Z . That is, X and Y are conditionally independent given Z if and only if, given any value of Z , the probability distribution of X is the same for all values of Y and the probability distribution of Y is the same for all values of X .Two events R and B are conditionally independentgiven a σ-algebra Σ ifwhere denotes the conditional expectation of the indicator function of the event , , given the sigma algebra. That is,Two random variables X and Y are conditionally independent given a σ-algebra Σ if the above equation holds for all R in σ(X ) and B in σ(Y ).Two random variables X and Y are conditionally independent given a random variable W if they are independent given σ(W ): the σ-algebra generated by W. This is commonly written:This is read "X is independent of Y, given W"; the conditioning applies to the whole statement: "(X is independentof Y) given W".If W assumes a countable set of values, this is equivalent to the conditional independence of X and Y for the events of the form [W = w]. Conditional independence of more than two events, or of more than two random variables, is defined analogously.The following two examples show that X⊥Y neither implies nor is implied by X⊥Y | W. First, suppose W is 0 with probability 0.5 and 1 otherwise. When W = 0 take X and Y to be independent, each having the value 0 with probability 0.99, the value 1 otherwise. When W = 1, X and Y are again independent, but this time they take the value 1 with probability 0.99. Then X⊥Y | W. But X and Y are dependent, because Pr(X = 0) < Pr(X = 0|Y = 0). This is because Pr(X = 0) = 0.5, but if Y = 0 then it's very likely that W = 0 and thus that X = 0 as well, so Pr(X = 0|Y = 0) > 0.5. For the second example, suppose X⊥Y, each taking the values 0 and 1 with probability 0.5. Let W be the product X×Y. Then when W = 0, Pr(X = 0) = 2/3, but Pr(X = 0|Y = 0) = 1/2, so X ⊥ Y | W is false. This also an example of Explaining Away. See Kevin Murphy's tutorial [2] where X and Y take the values "brainy" and "sporty".Uses in Bayesian statisticsLet p be the proportion of voters who will vote "yes" in an upcoming referendum. In taking an opinion poll, one chooses n voters randomly from the population. For i = 1, ..., n, let Xi= 1 or 0 according as the i th chosen voter will or will not vote "yes".In a frequentist approach to statistical inference one would not attribute any probability distribution to p (unless the probabilities could be somehow interpreted as relative frequencies of occurrence of some event or as proportions ofsome population) and one would say that X1, ..., Xnare independent random variables.By contrast, in a Bayesian approach to statistical inference, one would assign a probability distribution to p regardless of the non-existence of any such "frequency" interpretation, and one would construe the probabilities as degrees of belief that p is in any interval to which a probability is assigned. In that model, the random variablesX 1, ..., Xnare not independent, but they are conditionally independent given the value of p. In particular, if a largenumber of the X s are observed to be equal to 1, that would imply a high conditional probability, given that observation, that p is near 1, and thus a high conditional probability, given that observation, that the next X to be observed will be equal to 1.Rules of conditional independenceA set of rules governing statements of conditional independence have been derived from the basic definition.[3][4] Note: since these implications hold for any probability space, they will still hold if considers a sub-universe by conditioning everything on another variable, say K. For example, would also mean that.Note: below, the comma can be read as , and thus can be visualized as a Venn Diagram.SymmetryDecompositionProof:•(meaning of )•(ignore variable by integrating it out)•repeat proof to show independence of X and B .Weak unionContractionContraction-weak-union-decomposition Putting the above three together, we have:IntersectionIf the probabilities of X, A, B are all positive, then the following also holds:References [1]To see that this is the case, one needs to realise that Pr(R ∩ B | Y ) is the probability of an overlap of R and B in the Y area. Since, in the pictureon the left, there are two squares where R and B overlap within the Y area, and the Y area has twelve squares, Pr(R ∩ B | Y ) == .Similarly, Pr(R | Y ) = = and Pr(B | Y ) = = .[2]http://people.cs.ubc.ca/~murphyk/Bayes/bnintro.html[3]Dawid, A. P. (1979). "Conditional Independence in Statistical Theory". Journal of the Royal Statistical Society Series B 41 (1): 1–31.MR0535541. JSTOR 2984718.[4]J Pearl, Causality: Models, Reasoning, and Inference, 2000, Cambridge University PressArticle Sources and Contributors4Article Sources and ContributorsConditional independence Source: /w/index.php?oldid=418113252 Contributors: 3mta3, Alansohn, AzaToth, Brighterorange, Btyner, Cesarth, Charles Matthews,Circeus, Citrus Lover, DGJM, Ddxc, Dominus, Duoduoduo, Epachamo, Fresheneesz, Gareth Owen, Giftlite, Jeff G., Mackseem, Melcombe, Michael Hardy, Ms2ger, Mtcv, Nasz, Neilc,Ninjagecko, Ogai, Oleg Alexandrov, Pr.elvis, Qwfp, Redrocket, Rkashuba, Splat2010, Tsirel, 31 anonymous editsImage Sources, Licenses and ContributorsImage:Conditional independence.svg Source: /w/index.php?title=File:Conditional_independence.svg License: Creative Commons Attribution-Sharealike 3.0,2.5,2.0,1.0 Contributors: Original uploader was AzaToth at en.wikipedia Later version(s) were uploaded by Ddxc at en.wikipedia.LicenseCreative Commons Attribution-Share Alike 3.0 Unported/licenses/by-sa/3.0/。

练习伴随低估效应的产生机制

练习伴随低估效应的产生机制

练习伴随低估效应的产生机制贾宁;张欣【摘要】学习判断是元认知监测的一种重要形式,指个体对已经学过的项目在以后回忆测验中成绩的预见性判断.练习伴随低估效应(underconfidence with practice,UWP effect)是学习判断中的一个重要现象,指学习判断随着练习次数的增加出现的低估倾向.本研究利用重复学习范式,通过两个实验考察UWP效应的产生机制,检验提取流畅性假说和记忆去偏差假说.实验一证实了UWP效应的稳定性,但实验结果并不支持提取流畅性假说.实验二通过选取正向词对和反向词对作为实验材料,证实编码流畅性与提取流畅性的共同作用导致了UWP效应,并支持记忆去偏差假说对UWP效应的产生机制的解释.【期刊名称】《应用心理学》【年(卷),期】2014(020)002【总页数】8页(P138-145)【关键词】学习判断;练习伴随低估效应;提取流畅性【作者】贾宁;张欣【作者单位】河北师范大学教育学院,石家庄050024;保定监狱,河北保定071028【正文语种】中文【中图分类】B841 引言学习判断(judgment of learning)是个体对随后的记忆成绩的预测，是元认知监测的一种重要形式(贾宁，白学军，2007)。

Koriat(1997)在研究重复学习时发现了练习伴随低估效应(underconfidence with practice,UWP)，它指的是在材料重复呈现的情况下，对回忆成绩的预测常常表现出低估倾向的现象。

因为JOL经常出现高估，所以UWP效应出现的操作性定义是第一次学习—测验中JOL等级与回忆成绩的差值大于第二次学习—测验中JOL等级与回忆成绩的差值。

具体表现有两种：第一种是第一次JOL判断出现高估，JOL等级大于回忆成绩，差值为正，而第二次JOL判断出现低估，JOL等级小于回忆成绩，差值为负；第二种是两次JOL判断都出现了高估，但是第二次JOL等级与回忆成绩的差值变小。

两种独立性定义的等价性

两种独立性定义的等价性

第23卷第1期2020年1月高等数学研究STUDIES IN COLLEGE MATHEMATICSVol23,No.1Jan.,2020doi：10.3969/j.issn.1008-1399.2020.01029两种独立性定义的等价性朱德刚，李文辉，花永健(南京林业大学理学院，南京210037)摘要随机变量独立性的定义，一般由随机变量的分布函数来刻画.但在实际应用中，却通常使用其等价条件来判断随机变量是否独立•本文分别针对连续型和离散型两类随机变量，论证了这两种独立性概念之间的等价性•关键词随机变量；分布函数；独立性；等价性中图分类号O211,G42文献标识码A文章编号1008-1399(2020)01-0120-02Equivalence of Two Definitions of IndependenceZHU Degang,LI Wenhui,and HUA Yongjian(Co l ege of Science!Nanjing Forestry University!Nanjing210037!China)Abstract The independence of random variables is genera l y characterized by the cumulative distribution function of the random variables.However,in practice,an equivalent condition is usually used to judge whether the random variables are independent.This paper considers both continuous and discrete random variables,and demonstrates the equivalence between these two concepts of independence.Keywords random variable,cumulative distribution function,independence,equivalence大多数教材中，随机变量的独立性是用分布函数来定义的.但是在实际应用中，却很少直接用分布函数来判断独立性，而是基于一个等价的独立性定义来判断随机变量是否独立.这是由于通行教材中有结论性的语言指出“这两种独立性定义是等价的”.但是，这两种独立性概念的等价性，却未见正式详细的数学证明.此外，这种等价性看似显然，但严格证明起来，并非易事，还需要一番功夫，需要对相收稿日期：2019-03-07修改日期-019-04-16基金项目：南京林业大学"水杉名师”培养计划；南京林业大学2018年高等教育研究课题;南京林业大学大学生创新训练计划项目(2018NFUSPITP590).作者简介：朱德刚(1980—),男，安徽来安人，博士，副教授，主要从事应用概率统计与大学数学的教学与研究&李文辉(1997—)，男，安徽安庆人，本科在读,Email:1798493505@；花永健(1998—),男,江苏淮安人,本科在读,Email：1261514732@qq.om.关概念有深刻的理解并进行严密的数学推导.本文分别就连续型和离散型两类随机变量,严格论证了这两种独立性定义之间的等价性,解决了一个概率统计教学过程中经常被忽略的问题.1一些定义定义1.1设(X,X)是二维随机变量,对任意X,A,F(x,a)=P{X"x,X"a}称为二维随机变量(X,X)的分布函数.定义1.2Fx(x)="(x,8)和"x(A)="(8,a)分别称为二维随机变量(X,X)关于X和X的边缘分布函数.定义1.3设"Q,A)及Fx(x),F x(A)分别是二维随机变量(X,X)的分布函数及边缘分布函数,对于所有X,A有F(x,a)=F x Q)•F Y(y),(1)则称随机变量X和X 是相互独立的.第23卷第1期朱德刚，李文辉，花永健：两种独立性定义的等价性1212等价性证明结论2.1(离散型随机变量情形)设(x,y)是离散型随机变量，x和y相互独立的条件(1)与下列条件等价:对(x,y)所有可能取的值(x,，A j)有P{X=x i y=y J}=P{X=x1}・P{y=y}}.(2)证不失一般性，设X取值由小到大排列为x1,x2,，-,y取值由小到大A1,A2,，-,故P{X=x,}=P{X"x,}—P{X"x—1}—F x(x,)—F x(x1—1).同理可得p{y—y3}—F y(a u)—F y A j—1),从而P{X=xi}P{y=y}—(F x(x,)—F x(x1—1))(F y(A u)—F y A j—1))—F x(,x,)FY(.yj)—F x(x2—1)F y(y；)—F x(x,)F y(y—)9F x(x i—1)F y(y—)•若(1)式成立，则F x(x,')F y(y；)—F(x,,j'),F x(x2—1)F y(y；)—F(x i—,；),F x(x,)F y(y3—1)—F(x,,3—1),F x(x2—1)F y(y j—1)—F(x i—,y—),从而P{X—x,}P{Y—y；}—F(x,,y j)一F x—,y j)—(F(x,,y j—1)—F(x i—1,y—))—P{X"x,,Y"y j—P{X"x2—1Y"y；}—(P{x"x,,y"y—}—P{X"x—1,y"y—})—P{X—x,,Y"y,}—P{X—x,,Y"y,—1}=P{X=x i y=y i}即(2)式成立.反之,若(2)式成立,则对任意x,y,有F(x,y)—..P{X-x,,Y—y；}x,"xy}"y—.P{X—x,}.P{y—y；}x!"x A；"a—P{X"x}P{Y"y}—Fx(.x)F y(.y),即(1)式成立,从而结论1得证.结论2.2(连续型随机变量情形)设(X,Y)是连续型随机变量,f(x,y),f x(x), f y(y)分布为(X,Y)的概率密度和边缘概率密度,则X和y相互独立的条件(1)与下列条件等价：在平面上几乎处处有f(x,y)—f x(x)・fy(y).证定义(3)F x(x)—f X(x)dz,Fy(.y)—j fy(.y)dy,若(1)式成立,则F(x,y)—F x(x)・F Y(y)fx(x)dx[fy(y)dyI f X(x)f Y(y)dyd x又由定义得F(x,y)—f(.x,y)dydx.故fCx,y)—f x(x)・f y(y)在平面上几乎处处成立,即(3)式成立.反之,若(3)式成立,则有f(.x,y)dydx[fx(x)fY(y)dydzf X(x)dx j f Y(y)dy—F x(x)・F Y(.y),即(1)式成立,从而结论2得证.3结语两随机变的独性定义的等价性,做出了严格的理论证明.对这一看似简单显然的结论,只借助随机变量联合分布和边缘分布的定义做出了简单但严谨的证明,解决了概率统计教学过程中一个经常被忽略的问题.本文仅就二维随机变量的情况做出了证明，结论还可以推广到多维随机变量的情形，可以类似地证明.参考文献[1]盛骤,谢式千,潘承毅.概率论与数理统计.[M].4版.北京：高等教育出版社，200&[2]张宏礼,王苫社，周晓晶,赵艳楠.随机变量独立性的一个注记[J].高等数学研究，2010,13(01):114-115. ']朱焕然.随机变量独立性判别方法注记[J].大学数学, 2003,(04)：107-110.M朱德刚，何念念,陈仕荣.关于独立性的若干反例']•高等数学研究，2019,22(01):79-80+114.']郑发美.离散型随机变量的几种独立性及相互关系[J].大学数学，2010,26(05):191-193.。

第一课-英语让我的世界如此精彩

第一课-英语让我的世界如此精彩

当背到第10 课（silicon vallay)的是时候我的嗓子已经受不 了了，只要我一背就咳嗽，而且咳的很厉害， 背诵被迫终止的5天。后来我只能不出声音的背 （就是默背），结果奇迹出现了，我不在咳嗽 了，而且我的效率提高了一倍。（也许"默背" 是很多人的背诵习惯，可是多我来说就意味着 要改变从"儿时"养成的背诵习惯，还是挺不容 易的。）事情到此，可能也就没有什么可讲的 了。但是，在我快要把第四册背完的时候（背 到第39课what every writer wants)，我遇到了 一个大困难，那就是"噪 音"。因为我家是住在 （天津人叫做）"大杂院"。时直夏日，人门都 出来乘凉，这种生活噪音成了我的最大的敌人。 背诵的速度被迫降了下来。就这样原定第四册 最迟在6.10拿下，结果直到6.21日才全部搞定。
新东方英语牛人学习方法
新东方有个学员现在在Duke大学，他从 高一开始背《新概念英语》第三册，背到高三 就背完了。
高考考进了北大，进北大后，他本来不想 再背了。但当他背给同学听的时候，其他同学 都露出了羡慕的眼光，于是，为了这种虚荣心 ，他就坚持背第四册，把第三、四册都背得滚 瓜烂熟，他熟到什么地步呢，有人把其中任何 一句说出来，把能把上一句和下一句连接下 去，而且语音非常标准，因为他是模仿着磁带 来背的。
1、从小我背课文就拿者一本书在我自己的 小屋里低着头边走边背（出声背）。在一开始 背《新概念》的时候我也是这样，结果一天下 来弄得我简直是精疲力劲，而且效率不高， 这种方法很快就被淘汰。
2、我发现做在自己的床上背诵（出声音背） 效率大大的提高，这样一天下来，感觉除了 嗓子有点累还是蛮轻松的。就这样我在4.30 日把第三册背完了。想想第三册有60课我紧 用了一个多月（哦，我的背诵是从2019年 3.20日开始）就搞定，那么第四册才48课估 计一个月搞定应该没什么问题。但是事实超 出了我的预料。