置信度傳播

置信度傳播（英語：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)，每個頂點v∈V表示一個在集合 X 的隨機變數，每條邊{u,v} ∈E表示隨機變數u和v之間的一種依賴關係。

一個函式集合（也稱為因子或者團因子有時也稱為特徵），每一個的定義域是圖G的團或子團k. 每一個是從可能的特定聯合的指派（到元素k）到非負實數的映射。