第5.6节证据理论(DS理论)

《第5.6节证据理论(DS理论)》由会员分享，可在线阅读，更多相关《第5.6节证据理论(DS理论)（29页珍藏版）》请在装配图网上搜索。

1、王庆江王庆江计算机科学与技术系计算机科学与技术系课件下载：课件下载：http:/222.195.158.214/教务处教务处“网络教学网络教学”22008-2009学年第1学期第5.6节 证据理论n样本空间样本空间qa1,a2,a3,ann所有可能的随机事件所有可能的随机事件qqa1,a2,a3,anqa1,a2,a1,a3,a1,an,a2,a3,a2,a4,a2,an,an-1,anqa1,a2,a3,a1,a2,a4,a1,a2,an,a2,a3,a4,qq)()(,2,BPAPBABA 则则且且随机试验的结果空间随机试验的结果空间组成组成的的幂集幂集232008-2009学年第1学期第

2、5.6节 证据理论n若若代表疾病类型空间，那么代表疾病类型空间，那么2中的每个元素都中的每个元素都是可能的是可能的诊断结果诊断结果；n若若n（n|2|）个诊断结果缺乏依据，）个诊断结果缺乏依据，按按无差别原无差别原理理确定这确定这n个结果的发生概率。个结果的发生概率。n已分配概率已分配概率-1感冒感冒感冒感冒,发烧发烧发烧发烧0.20.40.4 AAP21)(42008-2009学年第1学期第5.6节 证据理论n若对若对2中中各元素都不了解，则各元素的发生概率各元素都不了解，则各元素的发生概率为为n例：例：2 家里有贼家里有贼,家里没贼家里没贼，在，在无任何无任何知识知识情况下，有贼没贼的概率

3、各情况下，有贼没贼的概率各0.5。|2|1 恐怖恐怖52008-2009学年第1学期第5.6节 证据理论n对对2中那些一点儿不了解（知道）的元素，能不中那些一点儿不了解（知道）的元素，能不能不指定概率？能不指定概率？q不知为不知，是知也。不知为不知，是知也。孔子孔子论语论语n剩余概率该怎么分配呢？剩余概率该怎么分配呢？q分给分给，让整个论域承受剩余概率；，让整个论域承受剩余概率；q这就是证据理论（这就是证据理论（Evidence theory）。）。62008-2009学年第1学期第5.6节 证据理论nArthur P.Dempster提出证据理论，用提出证据理论，用概率范围概率范围而不是而不

4、是单一概率值单一概率值表示不确定度；表示不确定度；n其学生其学生Glenn Shafer进一步研究，进一步研究，1976年出版年出版证据的数学理论证据的数学理论1。q这套方法称作证据理论（也称这套方法称作证据理论（也称D-S理论）。理论）。1 Shafer,Glenn.A Mathematical Theory of Evidence.Princeton University Press,1976,ISBN 0-608-02508-9 72008-2009学年第1学期第5.6节 证据理论n考虑两两考虑两两互斥互斥的元素集的元素集U U A1,A2,A3,Ann例：例：U 三轮车，汽车，火车三轮

5、车，汽车，火车 U 赤，橙，黄，绿，青，蓝，紫赤，橙，黄，绿，青，蓝，紫 U 马，牛，羊，鸡，狗，兔马，牛，羊，鸡，狗，兔 U 气管炎，肺炎，胃炎，肝炎气管炎，肺炎，胃炎，肝炎A1A2A3An互斥元素82008-2009学年第1学期第5.6节 证据理论n2U是是U的幂集（的幂集（power set），），|2U|2|U|；q例：例：U 三轮车三轮车,汽车汽车,火车火车 则则2U,三轮车三轮车,汽车汽车,火车火车,三轮车三轮车,汽车汽车,三轮车三轮车,火车火车,汽车汽车,火车火车,U n幂集的任一元素都幂集的任一元素都可能可能是是U上问题的正确答案，上问题的正确答案，而只有一个元素才是正确答案。

6、而只有一个元素才是正确答案。qU上哪些是能源动力车？上哪些是能源动力车？汽车、火车汽车、火车qU上哪些是人力车？上哪些是人力车？三轮车三轮车qU上哪些是有轨车？上哪些是有轨车？火车火车92008-2009学年第1学期第5.6节 证据理论n幂集的每个元素可看成命题，真命题就是答案。幂集的每个元素可看成命题，真命题就是答案。永假命题永假命题；三轮车是能源动力车；三轮车是能源动力车；汽车是能源动力车；汽车是能源动力车；火车是能源动力车；火车是能源动力车；三轮车和汽车是能源动力车；三轮车和汽车是能源动力车；三轮车和火车是能源动力车；三轮车和火车是能源动力车；汽车和火车是能源动力车；汽车和火车是能源动力

7、车；三轮车、汽车和火车是能源动力车。三轮车、汽车和火车是能源动力车。FFFFFFFTQ：哪些是能源动力车？：哪些是能源动力车？A：汽车和火车是能源动力车。：汽车和火车是能源动力车。102008-2009学年第1学期第5.6节 证据理论n2U是是U的幂集，基本概率分配函数的幂集，基本概率分配函数m:2U0,1qm()=0；q qA属于属于U且且AU，则，则m(A)表示表示A的的精确精确信任度；信任度；q若若A=U，则，则m(A)表示这个概率值表示这个概率值不知不知该如何分配。该如何分配。qU=a,b,c，为，为a和和a,b指定了信任度指定了信任度0.1和和0.2，剩，剩下的下的0.7不知该怎样分

8、配给其他子集，则不知该怎样分配给其他子集，则m(U)=0.7。m代表代表mass U2A1m(A)112008-2009学年第1学期第5.6节 证据理论nBel：2U0,1nBel(A)是是A及其子集的信任总和。及其子集的信任总和。nBel()=0；Bel(U)=1 nBel类似类似概率密度函数概率密度函数，比基本概率分配函数，比基本概率分配函数m更具全局性。更具全局性。ABBmABel)()(证据幂集证据幂集B1AB2122008-2009学年第1学期第5.6节 证据理论nPl：2U0,1nPl(A)是与是与A的的“交交”不是不是的所有集合的信任总的所有集合的信任总和。和。n满足满足BA=的

9、的B是是完全不支持完全不支持A的的命题命题；n0 Bel(A)PL(A)1)(1)(1)(-1)()(ABelBmBmBmAPlABABAB 132008-2009学年第1学期第5.6节 证据理论 ABBmAPl)()(证据幂集证据幂集B1AB2)(1)(1)(ABelBmAPlAB 证据幂集证据幂集B1B2AA142008-2009学年第1学期第5.6节 证据理论nf(Bel(A),Pl(A)q表示表示A的不确定性度量；的不确定性度量；qBel(A)称为称为A的支持度，即最低信任度；的支持度，即最低信任度；qPl(A)称为称为A的合情度，即最高信任度。的合情度，即最高信任度。nf(1,1)表

10、示表示A为真；为真；nf(0,0)表示表示A为假；为假；nf(0,1)表示对表示对A一无所知；一无所知；qBel(A)=1Pl(A)=0，Pl(A)=1Bel(A)=1，即对，即对A也一无所知。也一无所知。nf(1,0)是不可能成立的。是不可能成立的。Pl(A)Bel(A)表示对表示对A不知道的程度不知道的程度152008-2009学年第1学期第5.6节 证据理论n例：拳王和散打冠军打一架，你只了解武术而不懂拳击，例：拳王和散打冠军打一架，你只了解武术而不懂拳击，用证据理论怎样表示各种比赛结果的不确定性呢？用证据理论怎样表示各种比赛结果的不确定性呢？qU拳王胜拳王胜,散打冠军胜散打冠军胜q2U

11、=,拳王胜拳王胜,散打冠军胜散打冠军胜,拳王胜拳王胜,散打冠军胜散打冠军胜假设（命题）假设（命题）mBelPl既不是既不是拳王胜，也不是散打冠军胜拳王胜，也不是散打冠军胜000拳王胜拳王胜001.0散打冠军胜散打冠军胜0.40.41.0拳王胜或散打冠军胜拳王胜或散打冠军胜0.61.01.0问题来自：问题来自：http:/en.wikipedia.org/wiki/Dempster-Shafer_theoryhttp:/en.wikipedia.org/wiki/Dempster-Shafer_theory162008-2009学年第1学期第5.6节 证据理论n例：盒子里的猫是活的吗？例：盒子里

12、的猫是活的吗？假设（命题）假设（命题）mBelPlNull（不是活的，也不是死的）（不是活的，也不是死的）000活的活的0.200.200.50死的死的0.500.500.80Either（活的或死的）（活的或死的）0.301.001.00摘自：摘自：http:/en.wikipedia.org/wiki/Dempster-Shafer_theoryhttp:/en.wikipedia.org/wiki/Dempster-Shafer_theory172008-2009学年第1学期第5.6节 证据理论n例：若食堂提供例：若食堂提供“主食主食”、“菜菜”和和“汤汤”，你吃了什么？，你吃了什么？U

13、的子集的子集mBelPl 000主食主食0.100.100.85菜菜0.00.00.90汤汤0.00.00.50主食，主食，菜菜0.400.501.00主食，主食，汤汤0.00.101.00菜菜，汤汤0.150.150.90主食，主食，菜菜，汤汤0.351.001.00182008-2009学年第1学期第5.6节 证据理论nf1(A)Bel(A)+|A|/|U|(Pl(A)Bel(A)nf1()0nf1(U)1n0 f1(A)1n可证明：可证明：Bel(A)f1(A)Pl(A)0Bel(A)Pl(A)f1(A)1192008-2009学年第1学期第5.6节 证据理论n规则是两个集合之间因果关系

14、的表达；规则是两个集合之间因果关系的表达；n规则规则AB，A=a1,a2,ak，B=b1,b2,bkn用向量用向量(c1,c2,ck)表示表示AB的不确定度，这里的不确定度，这里 ci 0，0 i k，且，且ci1。202008-2009学年第1学期第5.6节 证据理论n“与与”的计算的计算f1(A1A2)=minf1(A1),f1(A2)n“或或”的计算的计算 f1(A1A2)=maxf1(A1),f1(A2)n“非非”的计算的计算f1(A)=1f1(A)勘误：勘误：P200页，页，“f1(A)=f1(A)”应为应为“f1(A)=1f1(A)”212008-2009学年第1学期第5.6节 证

15、据理论n可信度的传播（结论的可信度计算）可信度的传播（结论的可信度计算）q有规则有规则AB，知道，知道f1(A)和向量和向量(c1,c2,ck)，怎样计，怎样计算算f1(B)?m(b1,b2,bk)=(f1(A)c1,f1(A)c2,f1(A)ck)求出求出Bel(B)和和Pl(B)，即可求出，即可求出f1(B)。k1ii1(A)cf1m(U)222008-2009学年第1学期第5.6节 证据理论n有两个概率分配函数有两个概率分配函数m1(A)和和m2(A)，nm(A)=(m1 m2)(A)AYXYmXmKAm)()()(21 YXYXYmXmYmXmK)()()()(121211勘误：勘误：

16、P200页，此页，此处多了一个处多了一个m(A)B1B2A232008-2009学年第1学期第5.6节 证据理论n已知已知f1(A1)=0.40，f1(A2)=0.50，|U|=20nA1B=b1,b2,b3，(c1,c2,c3)=(0.1,0.2,0.3)nA2B=b1,b2,b3，(c1,c2,c3)=(0.5,0.2,0.1)n求求f1(B)b1b2b3b4b5b20空间空间U242008-2009学年第1学期第5.6节 证据理论m1(b1,b2,b3)=(f1(A1)c1,f1(A1)c2,f1(A1)c3)=(0.40.1,0.40.2,0.40.3)=(0.04,0.08,0.12

17、)m1(U)=0.76m2(b1,b2,b3)=(f1(A2)c1,f1(A2)c2,f1(A2)c3)=(0.50.5,0.50.2,0.50.1)=(0.25,0.10,0.05)m2(U)=0.60勘误：勘误：P201页，原为页，原为0.70，应改为，应改为0.60确定单元素子集的确定单元素子集的m值值计算剩余概率计算剩余概率得到了两个概率得到了两个概率分配函数分配函数m1和和m2252008-2009学年第1学期第5.6节 证据理论1/K=m1(b1)m2(b1)+m1(b1)m2(U)+m1(b2)m2(b2)+m1(b2)m2(U)+m1(b3)m2(b3)+m1(b3)m2(U)

18、+m1(U)m2(b1)+m1(U)m2(b2)+m1(U)m2(b3)+m1(U)m2(U)=1.082 K=0.9242得到组合系数得到组合系数b1b2b3b4b5b20b1 b2 b3U262008-2009学年第1学期第5.6节 证据理论m(b1)=Km1(b1)m2(b1)+m1(b1)m2(U)+m1(U)m2(b1)=0.211m(b2)=Km1(b2)m2(b2)+m1(b2)m2(U)+m1(U)m2(b2)=0.129m(b3)=Km1(b3)m2(b3)+m1(b3)m2(U)+m1(U)m2(b3)=0.168m(U)=1 m(b1)+m(b2)+m(b3)=0.492

19、计算组合后的概率分配函数计算组合后的概率分配函数m272008-2009学年第1学期第5.6节 证据理论n目前只对目前只对U上上b1、b2和和b3分配了分配了m值，即值，即m(b1)、m(b2)和和m(b3)；nBel(B)=m(b1)+m(b2)+m(b3)=0.508n令令U=b4、b5、b20，则按证据理论有，对于任意，则按证据理论有，对于任意A 2U，m(A)=0;n而而B=b4,b5,b20，Bel(B)=0nPl(B)=1 Bel(B)=1 0=1nf1(B)=Bel(B)+(Pl(B)Bel(B)|B|U|=0.582282008-2009学年第1学期第5.6节 证据理论n5.13292008-2009学年第1学期第5.6节 证据理论n什么是不确定性推理？什么是不确定性推理？n贝叶斯网络贝叶斯网络n主观贝叶斯方法主观贝叶斯方法n确定性方法确定性方法n证据理论证据理论