大師兄的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)筆記（二十三）：貝葉斯網(wǎng)絡(luò)與概率推理（六）

大師兄的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)筆記（二十二）：貝葉斯網(wǎng)絡(luò)與概率推理（五）
大師兄的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)筆記（二十四）：貝葉斯網(wǎng)絡(luò)與概率推理（七）

三、復(fù)雜度分析

1. 復(fù)雜性的度量
  • 在VE算法中，最耗費(fèi)時(shí)間和空間的步驟是對(duì)Elim(F,Z)的調(diào)用。
  • 他的運(yùn)輸段復(fù)雜度遠(yuǎn)遠(yuǎn)超過其他步驟，所以可以把這一步的復(fù)雜度作為整個(gè)算法的復(fù)雜度。
  • Elim(F,Z)從F中挑選出所有涉及Z的函數(shù)\{f_1,...,f_k\}，將它們相乘得到中間函數(shù)g，再講Z從g中消去。
  • 設(shè)X_1,...X_t是g中所有除Z之外的變量。
  • 如果把函數(shù)表示成多為表，則g所需儲(chǔ)存的函數(shù)值的個(gè)數(shù)為|Z|\prod^l_{i=1}|X_i|。
  • 因此|Z|\prod^l_{i=1}|X_i|是函數(shù)g的復(fù)雜性的一個(gè)恰當(dāng)?shù)亩攘?，從而也?img class="math-inline" src="https://math.jianshu.com/math?formula=Elim(F%2CZ)" alt="Elim(F,Z)" mathimg="1">的復(fù)雜性的一個(gè)恰當(dāng)?shù)亩攘俊?/li>
  • 這稱之為Z的消元成本(elimination cost)，記為l(Z)。
  • 在推理過程中，VE算法需要消去多個(gè)變量，設(shè)它們依次為Z_1,Z_2,...,Z_n，用總消元成本l=\sum^n_{i=1}l(Z_i)來度量VE算法的復(fù)雜度。
  • 式\sum^n_{i=1}l(Z_i)中最大的一項(xiàng)對(duì)整個(gè)式子的值的大小起支配作用，因此有時(shí)也用它來度量VE算法的復(fù)雜性。
  • 在上一章的網(wǎng)絡(luò)中，設(shè)所有變量均取二值，校園順序\rho=<C,E,B,D>，消去C時(shí)，需要計(jì)算g=P(C)P(E|B,C)，共設(shè)計(jì)3個(gè)變量：B,C和E。
  • 所以C的消元成本為l(C)=2\times 2\times 2=8。
  • 類似的，其它3個(gè)節(jié)點(diǎn)E,B和D的消元成本分別為8,8和4。
  • 因此，用\rho進(jìn)行變量消元的總成本為28，其中最大的一項(xiàng)為8.
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容