Markova reto

En fiziko kaj probabloteorio, Markova reto aŭ neorientita grafemodelo estas modelo por priskribi hazardajn variablojn kun la Markoveco per neorientita grafeo.

Markova reto similas al Bejesa reto je la reprezentado de dependecoj; sed malsamas ĉar Bejesaj retoj uzas orientitan kaj senciklan grafeon. Tial, Markova reto povas reprezenti iajn dependecojn, kiujn ne povas reprezenti Bejesa modelo (ekzemple cikla dependeco). La kontraŭo estas ankaŭ vera (ekzemple por induktita dependeco).

Kiam la kuna probablodenseco de la hazardaj variabloj estas severe pozitiva, la reto nomiĝas Gibbsa reto ĉar laŭ la Teoremo de Hammersley–Clifford, oni povas reprezenti ĝin per Gibbsa mezuro por iu taŭga (loke difinita) energiofunkcio. La origino de Markova reto estis la Modelo de Ising; fakte la Markova reto estis enkondukita kiel ĝeneraligo de la modelo de Ising. Studante artefaritan intelekton, oni uzas Markovan reton por modeli diversajn malaltajn ĝis meznivelajn taskojn en bildotraktado kaj komputa vido

Difino

Kune kun neorientita grafeo $G=(V,E)$, aro da hazarda variabloj $X=(X_v{)}_{v\in V}$ indeksita per $V$ faras Markova reto laŭ $G$ se ili havas iun Markovecon:

Para Markoveco: Ĉiu paro da nenajbaraj variabloj estu kondiĉe sendependaj sciante ĉiujn aliajn variablojn:

$X_u\perp \perp X_v\mid X_{V\setminus \{u,v\}}\text{if }\{u,v\}\notin E$

Loka Markoveco: Ĉiu variablo estu kondiĉe sendependa de ĉiuj aliaj variabloj sciante ĝiajn najbarojn:

$X_v\perp \perp X_{V\setminus \mathrm{N}[v]}\mid X_{\mathrm{N}(v)}$

ĉi tie $\mathrm{N}(v)$ estas aro da najbaroj de $v$, kaj $\mathrm{N}[v]=v\cup \mathrm{N}(v)$ estas la fermita najbaraĵo de $v$.

Malloka Markoveco: Ĉiu du subaroj da variabloj estu kondiĉe sendependaj sciante la disigan subaron:

$X_A\perp \perp X_B\mid X_S$

ke ĉiu ĉeno de vertico en $A$ al vertico en $B$ trairu tra $S$.

La tri Markovecoj ne ekvivalentas.: La malloka estas pli forta ol la loka, kaj la loka pli forta ol la para Markoveco.

En Markova reto, dependecojn oni priskribas per faktoroj, signite kiel $\varphi (x_c)$. Ĉi tie $x_c$ signas la aron da variabloj partoprenantaj en la dependeco. Ĉiun faktoron reprezentas la modelo per kliko de partoprenataj verticoj. La probablo $P$ de iu valorizo do estas

$P(x_1,\dots ,x_n)=\frac{1}{Z}\prod _{c\in C}{\varphi }_c(x_c)$

kies

$Z=\sum _{x_1,\dots ,x_n}\prod _{c\in C}{\varphi }_c(x_c)$

estas ununormiganta konstanto tia, ke la probablo tutas al unu.

Kondiĉa Markova reto

Grava speco de Markova reto estas kondiĉa Markova reto, kies variabloj estas eble kondiĉaj al aro da mallokaj observitoj $o$. En la modelo, ĉiu funkcio ${\varphi }_k$ ĵetas de ĉiu valorizado de kliko k kaj la observito $o$ al iu nenegativa realnombro. La formoj de Markova reto eble pli taŭgas por fari diskriminacia klasilo, kiu ne modelas la distribuon de la observito. Kondiĉan Markovan reton proponis John D. Lafferty, Andrew McCallum kaj Fernando C.N. Pereira en 2001.

Vidu ankaŭ

• Grafemodelo
• Teoremo de Hammersley–Clifford
• Ising modelo
• Markova ĉeno