置信度傳播

置信度傳播(英語:belief propagation),又稱為乘積和信息傳遞(sum-product message passing),是在貝葉斯網路、馬爾可夫隨機場機率圖模型中用於推斷的一種信息傳遞算法

基本介紹

  • 中文名:置信度傳播
  • 外文名:belief propagation
簡介,歷史,置信度傳播基礎,貝葉斯網路,馬爾可夫網路,

簡介

在給定已觀測節點時,可以用該算法高效地計算未觀測節點的邊緣分布。置信度傳播在人工智慧資訊理論中十分常見,已成功套用於低密度奇偶檢查碼Turbo碼自由能估計、可滿足性等不同領域。

歷史

置信度傳播由美國計算機科學家朱迪亞·珀爾於1982年提出。最初該算法的運用範圍僅限於,不久則擴展到多樹。此後,研究者發現在一般的圖中該算法是一種十分有用的近似算法。

置信度傳播基礎

貝葉斯網路

貝葉斯網路(Bayesian network),又稱信念網路(belief network)或是有向無環圖模型(directed acyclic graphical model),是一種機率圖型模型,藉由有向無環圖(directed acyclic graphs, or DAGs)中得知一組隨機變數
及其n條件機率分布(conditional probability distributions, or CPDs)的性質。舉例而言,貝葉斯網路可用來表示疾病和其相關症狀間的機率關係;倘若已知某種症狀下,貝葉斯網路就可用來計算各種可能罹患疾病之發生機率。
一般而言,貝葉斯網路的有向無環圖中的節點表示隨機變數,它們可以是可觀察到的變數,抑或是隱變數、未知參數等。連線兩個節點的箭頭代表此兩個隨機變數是具有因果關係或是非條件獨立的;而兩個節點間若沒有箭頭相互連線一起的情況就稱其隨機變數彼此間為條件獨立。若兩個節點間以一個單箭頭連線在一起,表示其中一個節點是“(parents)”,另一個是“(descendants or children)”,兩節點就會產生一個條件機率值。比方說,我們以
表示第i個節點,而
的“因”以
表示,
的“果”以
表示;圖一就是一種典型的貝葉斯網路結構圖,依照先前的定義,我們就可以輕易的從圖一可以得知:
,以及
大部分的情況下,貝葉斯網路適用在節點的性質是屬於離散型的情況下,且依照
此條件機率寫出條件機率表(conditional probability table, or CPT),此條件機率表的每一行(row)列出所有可能發生的
,每一列(column)列出所有可能發生的
,且任一行的機率總和必為1。寫出條件機率表後就很容易將事情給條理化,且輕易地得知此貝葉斯網路結構圖中各節點間之因果關係;但是條件機率表也有其缺點:若是節點
是由很多的“因”所造成的“果”,如此條件機率表就會變得在計算上既複雜又使用不便。
置信度傳播
圖1

馬爾可夫網路

馬爾可夫網路,(馬爾可夫隨機場無向圖模型)是關於一組有馬爾可夫性質隨機變數{\displaystyle X}的全聯合機率分布模型。
馬爾可夫網路類似貝葉斯網路用於表示依賴關係。但是,一方面它可以表示貝葉斯網路無法表示的一些依賴關係,如循環依賴;另一方面,它不能表示貝葉斯網路能夠表示的某些關係,如推導關係。馬爾可夫網路的原型是易辛模型,最初是用來說明該模型的基本假設。
形式上,一個馬爾可夫網路包括:
一個無向圖G= (V,E),每個頂點vV表示一個在集合 X 的隨機變數,每條邊{u,v} ∈E表示隨機變數uv之間的一種依賴關係。
一個函式集合
(也稱為因子或者團因子有時也稱為特徵),每一個
的定義域是圖G的團或子團k. 每一個
是從可能的特定聯合的指派(到元素k)到非負實數的映射。

相關詞條

熱門詞條

聯絡我們