跳到主要内容

文章 | 人工智能笔记：可信度方法

提示

本文首发于知乎。

可信度​

对于事件HH和条件EE，定义两个函数HB(H,E)\mathrm{HB}(H,E)和HD(H,E)\mathrm{HD}(H,E)，分别表示当条件EE存在时，HH的可能性上升和下降的程度：

HB(H,E)={1,P(H)=1,max⁡{P(H∣E),P(H)}−P(H)1−P(H),otherwise.HD(H,E)={1,P(H)=0,min⁡{P(H∣E),P(H)}−P(H)0−P(H),otherwise.\mathrm{HB}(H,E)=\begin{cases} 1,& P(H)=1,\\ \frac{\max\{P(H|E),P(H)\}-P(H)}{1-P(H)}, &\textrm{otherwise}. \end{cases}\\ \mathrm{HD}(H,E)=\begin{cases} 1,& P(H)=0,\\ \frac{\min\{P(H|E),P(H)\}-P(H)}{0-P(H)}, &\textrm{otherwise}. \end{cases}\\

于是可信度CF(H,E)\mathrm{CF}(H,E)可定义为：

CF(H,E)=HB(H,E)−HD(H,E)={P(H∣E)−P(H)1−P(H),P(H∣E)>P(H),P(H∣E)−P(H)P(H),P(H∣E)<P(H).\begin{align} \mathrm{CF}(H,E)&=\mathrm{HB}(H,E)-\mathrm{HD}(H,E)\\ &=\begin{cases} \frac{P(H|E)-P(H)}{1-P(H)}, & P(H|E)>P(H),\\ \frac{P(H|E)-P(H)}{P(H)}, & P(H|E)<P(H). \end{cases} \end{align}\\

可信度大于 0，表示EE的存在使得HH的可能性增大；可信度小于 0，表示EE的存在使得HH的可能性减小；可信度等于 0，表示EE的存在对HH的可能性无影响。

可信度规则​

可信度规则是一系列形如 If E then H,CF=f\textrm{If}\ E\ \textrm{then}\ H, \mathrm{CF}=f 的句子，这句话表示CF(H,E)=f\mathrm{CF}(H, E)=f。

合成算法​

已知多条可信度规则时，可以采用合成算法将可信度规则结合起来。

记CF(H,E1)=f1\mathrm{CF}(H, E_1)=f_1，CF(H,E2)=f2\mathrm{CF}(H,E_2)=f_2，则

CF(H,E1∩E2)={f1+f2−f1f2,f1>0,f2>0,f1+f2+f1f2,f1<0,f2<0,f1+f21−min⁡{∣f1∣,∣f2∣},otherwise.\mathrm{CF}(H, E_1\cap E_2)=\begin{cases} f_1+f_2-f_1f_2,&f_1>0,f_2>0,\\ f_1+f_2+f_1f_2,&f_1<0,f_2<0,\\ \frac{f_1+f_2}{1-\min\{|f_1|,|f_2|\}},&\textrm{otherwise}. \end{cases}\\

合成算法的推导​

如果假设E1E_1与E2E_2独立且关于HH条件独立，那么根据贝叶斯公式，有

P(H)P(H∣E1∩E2)=P(H)P(E1∣H)P(E2∣H)P(H)P(E1)P(E2)=P(H∣E1)P(H∣E2)P(H)P(H|E_1\cap E_2)=P(H)\frac{P(E_1|H)P(E_2|H)P(H)}{P(E_1)P(E_2)}=P(H|E_1)P(H|E_2)\\

即

P(H∣E1)P(H)P(H∣E2)P(H)=P(H∣E1∩E2)P(H)\frac{P(H|E_1)}{P(H)}\frac{P(H|E_2)}{P(H)}=\frac{P(H|E_1\cap E_2)}{P(H)}\\

注意到当CF(H,E1)<0\mathrm{CF}(H,E_1)<0时，P(H∣E)P(H)=1+CF(H,E)\frac{P(H|E)}{P(H)}=1+\mathrm{CF}(H, E)，那么

(1+CF(H,E1))(1+CF(H,E2))=1+CF(H,E1∩E2)\left(1+\mathrm{CF}(H,E_1)\right)\left(1+\mathrm{CF}(H,E_2)\right)=1+\mathrm{CF}(H,E_1\cap E_2)\\

整理得

CF(H,E1∩E2)=CF(H,E1)+CF(H,E2)+CF(H,E1)CF(H,E2)\mathrm{CF}(H,E_1\cap E_2)=\mathrm{CF}(H,E_1)+\mathrm{CF}(H,E_2)+\mathrm{CF}(H,E_1)\mathrm{CF}(H,E_2)\\

同理，CF(H,E1)>0\mathrm{CF}(H,E_1)>0时，P(H‾∣E)P(H‾)=1−P(H∣E)1−P(H)=1−CF(H,E)\frac{P(\overline{H}|E)}{P(\overline{H})}=\frac{1-P(H|E)}{1-P(H)}=1-\mathrm{CF}(H, E)，那么若E1E_1与E2E_2独立且关于H‾\overline{H}条件独立，根据

P(H‾∣E1)P(H‾)P(H‾∣E2)P(H‾)=P(H‾∣E1∩E2)P(H‾)\frac{P(\overline{H}|E_1)}{P(\overline{H})}\frac{P(\overline{H}|E_2)}{P(\overline{H})}=\frac{P(\overline{H}|E_1\cap E_2)}{P(\overline{H})}\\

有

(1−CF(H,E1))(1−CF(H,E2))=1−CF(H,E1∩E2)CF(H,E1∩E2)=CF(H,E1)+CF(H,E2)−CF(H,E1)CF(H,E2)\left(1-\mathrm{CF}(H,E_1)\right)\left(1-\mathrm{CF}(H,E_2)\right)=1-\mathrm{CF}(H,E_1\cap E_2)\\ \mathrm{CF}(H,E_1\cap E_2)=\mathrm{CF}(H,E_1)+\mathrm{CF}(H,E_2)-\mathrm{CF}(H,E_1)\mathrm{CF}(H,E_2)\\

而当CF(H,E1)\mathrm{CF}(H,E_1)与CF(H,E2)\mathrm{CF}(H,E_2)异号时，无法仅用这两个值表示合成结果，此时的合成公式实际上是估计值：

CF(H,E1∩E2)=CF(H,E1)+CF(H,E2)1−min⁡{CF(H,E1),CF(H,E2)}\mathrm{CF}(H,E_1\cap E_2)=\frac{\mathrm{CF}(H,E_1)+\mathrm{CF}(H,E_2)}{1-\min\{\mathrm{CF}(H,E_1),\mathrm{CF}(H,E_2)\}}\\

合成算法的不完全结合律​

对于全正数或全负数的合成，根据推导中得出的以下形式：

(1+CF(H,E1))(1+CF(H,E2))=1+CF(H,E1∩E2)(1−CF(H,E1))(1−CF(H,E2))=1−CF(H,E1∩E2)\left(1+\mathrm{CF}(H,E_1)\right)\left(1+\mathrm{CF}(H,E_2)\right)=1+\mathrm{CF}(H,E_1\cap E_2)\\ \left(1-\mathrm{CF}(H,E_1)\right)\left(1-\mathrm{CF}(H,E_2)\right)=1-\mathrm{CF}(H,E_1\cap E_2)\\

可知此时的合成算法是满足结合律的，也就是说，如果记CF(H,E1∩E2)=Comp(CF(H,E1),CF(H,E2))\mathrm{CF}(H,E_1\cap E_2)=\mathrm{Comp}\left(\mathrm{CF}(H,E_1),\mathrm{CF}(H,E_2)\right)，那么

Comp(a,Comp(b,c))=Comp(Comp(a,b),c)\mathrm{Comp}(a,\mathrm{Comp}(b,c))=\mathrm{Comp}(\mathrm{Comp}(a, b), c)\\

但是合成算法对于符号不同的可信度的合成并不满足结合律。

同时，合成算法也是无法并行的，即

Comp(Comp(a,b),Comp(c,d))≠Comp(a,Comp(b,Comp(c,d)))\mathrm{Comp}(\mathrm{Comp}(a,b),\mathrm{Comp}(c,d))\ne \mathrm{Comp}(a,\mathrm{Comp}(b,\mathrm{Comp}(c,d)))\\

可信度与贝叶斯方法​

引入几率函数：

O(H)=P(H)P(H‾)O(H)=\frac{P(H)}{P(\overline{H})}\\

再记

λ(H,E)=O(H∣E)O(H)\lambda(H,E)=\frac{O(H|E)}{O(H)}\\

那么可信度可表示为

CF(H,E)={1−1λ(H,E),λ(H,E)>1,λ(H,E)−1,λ(H,E)<1.\mathrm{CF}(H,E)=\begin{cases} 1-\frac{1}{\lambda(H,E)}, & \lambda(H,E)>1,\\ \lambda(H,E)-1, & \lambda(H,E)<1. \end{cases}\\

根据贝叶斯定理，几率函数满足

O(H∣E)=P(E∣H)P(E∣H‾)O(H)O(H|E)=\frac{P(E|H)}{P(E|\overline{H})}O(H)\\

因此λ(H,E)\lambda(H,E)实际上就是充分必然性函数LS(H,E)=P(E∣H)P(E∣H‾)\mathrm{LS}(H, E)=\frac{P(E|H)}{P(E|\overline{H})}。

因此可信度与贝叶斯方法联系了起来：

CF(H,E)={1−1LS(H,E),P(E∣H)>P(E∣H‾),LS(H,E)−1,P(E∣H)<P(E∣H‾).\mathrm{CF}(H,E)=\begin{cases} 1-\frac{1}{\mathrm{LS}(H,E)}, & P(E|H)>P(E|\overline{H}),\\ \mathrm{LS}(H,E)-1, &P(E|H)<P(E|\overline{H}). \end{cases}\\

合取、析取和否定的可信度​

几率函数满足O(H)⋅O(H‾)=1O(H)\cdot O(\overline{H})=1，因此λ(H,E)⋅λ(H‾,E)=1\lambda(H,E)\cdot \lambda(\overline{H},E)=1，故可信度满足

CF(H,E)=−CF(H‾,E)\mathrm{CF}(H,E)=-\mathrm{CF}(\overline{H},E)\\

对于合取，假设H1H_1与H2H_2独立，注意到

λ(H1∩H2,E)=P(H1)P(H2)1−P(H1)P(H2)\lambda(H_1\cap H_2,E)=\frac{P(H_1)P(H_2)}{1-P(H_1)P(H_2)}\\

记f(x)=ln⁡(1x+1)f(x)=\ln\left(\frac1x+1\right)，那么

f(λ(H1∩H2,E))=f(λ(H1,E))+f(λ(H2,E))f(\lambda(H_1\cap H_2,E))=f(\lambda(H_1,E))+f(\lambda(H_2,E))\\
Loading...