Faktora grafeo

Faktora grafeo estas dukolora grafeo, kiu reprezentas la faktoradon de funkcio. En probabloteorio, faktoran grafeon oni uzas por reprezenti faktoradon de probablodistribua funkcio, ebligante rapidan komputadon, ekzemple de marĝena distribuo tra la sum-produkta algoritmo. Unu el la gravaj sukcesoj de faktora grafeo kaj la sum-produkta algoritmo estis malkodigo de preskaŭ-perfekta eraro-korektada kodo kiel Maldensa Pareca Kodo kaj kodo turbo.

Faktora grafeo estas ĝeneraligo de limiga grafeo. Faktoro, kies valoro estas aŭ 0 aŭ 0, estas limigo. Limiga grafeo estas faktora grafeo kies faktoroj estas limigoj.

Difino

Faktora grafeo estas dukolora grafeo reprezentanta faktoradon de funkcio. Por faktorafo de funkcio $g(X_{1},X_{2},\dots ,X_{n})$,

$g(X_{1},X_{2},\dots ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j}),$

kie $S_{j}\subseteq \{X_{1},X_{2},\dots ,X_{n}\}$ estas la argumentaro de la funkcio. La rilata faktora grafeo $G=(X,F,E)$ havas variablo-verticojn$X=\{X_{1},X_{2},\dots ,X_{n}\}$, faktoro-verticojn $F=\{f_{1},f_{2},\dots ,f_{m}\}$, kaj eĝojn $E$. Ĉiu eĝo ligas variablo-verticon kaj faktoro-verticon, kaj dependas al faktorado jene: ekzistas sendirekta eĝo inter faktoro-vertico $f_{j}$ kaj variablo-vertico $X_{k}$ se kaj nur se $X_{k}\in S_{j}$, alprene ke la funkcio estas reela:  $g(X_{1},X_{2},\dots ,X_{n})\in \mathbb {R}$.

Oni povas uzi faktoran grafeon kun mesaĝada algoritmo por rapide komputi propraĵon de funkcio $g(X_{1},X_{2},\dots ,X_{n})$, ekzemple la marĝenan distribuon.

Ekzemplo

Ekzemplo de faktora grafeo

Konsideru funkcion kiu faktoriĝas jene

$g(X_{1},X_{2},X_{3})=f_{1}(X_{1})f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})f_{4}(X_{2},X_{3})$,

Dekstre montriĝas la rilata faktora grafeo. Vidu ke la faktora grafeo havas ciklon. Se oni kunigus $f_{2}(X_{1},X_{2})f_{3}(X_{1},X_{2})$ al unu faktoro, la rezultanta faktora grafeo iĝus arbo.  Tio ĉi gravas ĉar mesaĝadaj algoritmoj ĝenerale bezonas arbon por ekzakta kalkulado.

Vidu ankaŭ

• Kredo-elsendo
• Inferencio je Bejesa reto
• Kondiĉa probablo
• Markova reto
• Bejesa reto
• Teoremo de Hammersley–Clifford