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

可信度

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

$$\begin{gathered} \mathrm{HB}(H,E)=\{\begin{array}{ll}1,& P(H)=1,\\ \frac{\max \{P(H|E),P(H)\}-P(H)}{1-P(H)},& \text{otherwise}.\end{array} \\ \mathrm{HD}(H,E)=\{\begin{array}{ll}1,& P(H)=0,\\ \frac{\min \{P(H|E),P(H)\}-P(H)}{0-P(H)},& \text{otherwise}.\end{array} \end{gathered}$$

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

$$\begin{array}{rl}\mathrm{CF}(H,E)& =\mathrm{HB}(H,E)-\mathrm{HD}(H,E)\\ & =\{\begin{array}{ll}\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{array}\end{array}$$

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

可信度规则

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

合成算法

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

记$\mathrm{CF}(H,E_1)=f_1$，$\mathrm{CF}(H,E_2)=f_2$，则

$$\mathrm{CF}(H,E_1\cap E_2)=\{\begin{array}{ll}{f}_1+f_2-f_1{f}_2,& f_1>0,f_2>0,\\ f_1+f_2+f_1{f}_2,& f_1<0,f_2<0,\\ \frac{f_1+f_2}{1-\min \{|f_1|,|f_2|\}},& \text{otherwise}.\end{array}$$

合成算法的推导

如果假设$E_1$与$E_2$独立且关于$H$条件独立，那么根据贝叶斯公式，有

$$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)$$

即

$$\frac{P(H|E_1)}{P(H)}\frac{P(H|E_2)}{P(H)}=\frac{P(H|E_1\cap E_2)}{P(H)}$$

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

$$\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)$$

同理，$\mathrm{CF}(H,E_1)>0$时，$\frac{P(\overline{H}|E)}{P(\overline{H})}=\frac{1-P(H|E)}{1-P(H)}=1-\mathrm{CF}(H,E)$，那么若$E_1$与$E_2$独立且关于$\overline{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})}$$

有

$$\begin{gathered} \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) \end{gathered}$$

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

$$\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)\}}$$

合成算法的不完全结合律

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

$$\begin{gathered} \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) \end{gathered}$$

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

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

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

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

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

可信度与贝叶斯方法

引入几率函数：

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

再记

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

那么可信度可表示为

$$\mathrm{CF}(H,E)=\{\begin{array}{ll}1-\frac{1}{\lambda (H,E)},& \lambda (H,E)>1,\\ \lambda (H,E)-1,& \lambda (H,E)<1.\end{array}$$

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

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

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

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

$$\mathrm{CF}(H,E)=\{\begin{array}{ll}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{array}$$

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

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

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

对于合取，假设$H_1$与$H_2$独立，注意到

$$\lambda (H_1\cap H_2,E)=\frac{P(H_1)P(H_2)}{1-P(H_1)P(H_2)}$$

记$f(x)=\ln \left(\frac{1}{x}+1\right)$，那么

$$f(\lambda (H_1\cap H_2,E))=f(\lambda (H_1,E))+f(\lambda (H_2,E))$$