Beroendenätverk (grafisk modell)

Beroendenätverk (DN) är grafiska modeller , liknande Markov-nätverk , där varje vertex (nod) motsvarar en slumpmässig variabel och varje kant fångar beroenden mellan variabler. Till skillnad från Bayesianska nätverk kan DN innehålla cykler. Varje nod är associerad med en villkorad sannolikhetstabell, som bestämmer realiseringen av den slumpmässiga variabeln givet dess föräldrar.

Markov filt

I ett Bayesian-nätverk är Markov -filten för en nod uppsättningen föräldrar och barn i den noden, tillsammans med barnens föräldrar. Värdena för föräldrarna och barnen i en nod ger uppenbarligen information om den noden. Men dess barns föräldrar måste också inkluderas i Markov-filten, eftersom de kan användas för att bortförklara noden i fråga. I ett Markov slumpmässigt fält är Markov -filten för en nod helt enkelt dess intilliggande (eller angränsande) noder. I ett beroendenätverk Markov-filten för en nod helt enkelt uppsättningen av dess föräldrar.

Beroendenätverk kontra Bayesiska nätverk

Beroendenätverk har fördelar och nackdelar med avseende på Bayesianska nätverk. I synnerhet är de lättare att parametrisera från data, eftersom det finns effektiva algoritmer för att lära sig både strukturen och sannolikheterna för ett beroendenätverk från data. Sådana algoritmer är inte tillgängliga för Bayesianska nätverk, för vilka problemet med att bestämma den optimala strukturen är NP-hårt. Icke desto mindre kan ett beroendenätverk vara svårare att konstruera med hjälp av ett kunskapsbaserat tillvägagångssätt som drivs av expertkunskap.

Beroendenätverk kontra Markovnätverk

Konsekventa beroendenätverk och Markovnätverk har samma representationskraft. Icke desto mindre är det möjligt att konstruera icke-konsistenta beroendenätverk, dvs beroendenätverk för vilka det inte finns någon kompatibel giltig gemensam sannolikhetsfördelning . Markov-nätverk är däremot alltid konsekventa.

Definition

Ett konsekvent beroendenätverk för en uppsättning slumpvariabler ${\textstyle \mathbf {X} =(X_{1},\ldots ,X_{n})}$ med gemensam fördelning $p(\mathbf {x} )$ är ett par $(G,P)$ där $G$ är en cyklisk riktad graf, där var och en av dess noder motsvarar till en variabel i $\mathbf {X}$ , och $P$ är en uppsättning villkorliga sannolikhetsfördelningar. Föräldrarna till nod $X_{i}}$$\mathbf {Pa_{i}} \subseteq (X_{1},\ldots,X_{i-1},X_{i+1},\ldots, X_{n})$ , betecknad $\mathbf {Pa_{i}}$ , motsvarar dessa variabler som uppfyller följande oberoende relationer

$p(x_{i}\mid \mathbf {pa_{i}} )=p(x_{i}\mid x_{1},\ldots ,x_{i-1},x_{i+1} ,\ldots ,x_{n})=p(x_{i}\mid \mathbf {x} -{x_{i}}).$

Beroendenätverket är konsekvent i den meningen att varje lokal distribution kan erhållas från den gemensamma distributionen $p(\mathbf {x} )$ . Beroendenätverk som lärs ut med hjälp av stora datamängder med stora urvalsstorlekar kommer nästan alltid att vara konsekventa. Ett icke-konsekvent nätverk är ett nätverk för vilket det inte finns någon gemensam sannolikhetsfördelning som är kompatibel med paret ( $\displaystyle (G,P)}$ . I så fall finns det ingen gemensam sannolikhetsfördelning som tillfredsställer de oberoende relationerna som ingår i det paret.

Inlärning av struktur och parametrar

Två viktiga uppgifter i ett beroendenätverk är att lära sig dess struktur och sannolikheter från data. I huvudsak består inlärningsalgoritmen av att oberoende utföra en probabilistisk regression eller klassificering för varje variabel i domänen. Det kommer från observation att den lokala fördelningen för variabel $X_{i}$ i ett beroendenätverk är den villkorliga fördelningen $p(x_{i}|\mathbf {x} -{x_{i}})$ , som kan uppskattas genom valfritt antal klassificerings- eller regressionstekniker, såsom metoder som använder ett probabilistiskt beslutsträd, ett neuralt nätverk eller en probabilistisk stödvektormaskin. För varje variabel $X_{i}$ i domän $X$ uppskattar vi därför oberoende dess lokala distribution från data med hjälp av en klassificeringsalgoritm, även om det är en distinkt metod för varje variabel. Här kommer vi kort att visa hur probabilistiska beslutsträd används för att uppskatta de lokala fördelningarna. För varje variabel $X_{i}$ i $\mathbf {X}$ lärs ett probabilistiskt beslutsträd där $X_{i}$ är målvariabeln och $\mathbf {X} -X_{i}$ är indatavariablerna. För att lära sig en beslutsträdstruktur för $X_{i}$ börjar sökalgoritmen med en singelrotnod utan barn. Sedan ersätts varje lövnod i trädet med en binär uppdelning på någon variabel $X_{j}$ i ${\displaystyle \mathbf {X} -X_{i}} ,$ tills inte mer byten ökar trädets poäng.

Probabilistisk slutledning

En probabilistisk slutledning är uppgiften där vi vill besvara probabilistiska frågor av formen ${\displaystyle p(\mathbf {y\mid z} )} ,$ givet en grafisk modell för $\mathbf {X}$ , där $\mathbf {Y}$ ('target'-variablerna) $\mathbf {Z}$ ('input'-variablerna) är disjunkta delmängder av $\mathbf {X}$ . Ett av alternativen för att utföra probabilistisk slutledning är att använda Gibbs sampling . Ett naivt tillvägagångssätt för detta använder en ordnad Gibbs-sampler, en viktig svårighet är att om antingen $p(\mathbf {y\mid z} )$ eller $p (\mathbf {z} )$ är liten, då krävs många iterationer för en korrekt sannolikhetsuppskattning. En annan metod för att uppskatta $p(\mathbf {y\mid z} )$ när $p(\mathbf {z} )$ är liten är att använda modifierade ordnade Gibbs sampler, där $\mathbf {Z=z}$ är fixerad under Gibbs sampling.

Det kan också hända att $\mathbf {y}$ är sällsynt, t.ex. när $\mathbf {Y}$ har många variabler. Så lagen om total sannolikhet tillsammans med de oberoende som är kodade i ett beroendenätverk kan användas för att dekomponera slutledningsuppgiften till en uppsättning slutledningsuppgifter på enskilda variabler. Detta tillvägagångssätt kommer med fördelen att vissa termer kan erhållas genom direkt uppslagning, och därigenom undviker viss Gibbs-sampling.

Nedan kan du se en algoritm som kan användas för att erhålla $p(\mathbf {y|z} )$ för en viss instans av $\mathbf {y} \in \mathbf {Y}$ och $\mathbf {z} \in \mathbf {Z}$ , där $\mathbf {Y}$ och $\mathbf {Z}$ är disjunkta delmängder.

• Algoritm 1:

1. $\mathbf {U:=Y}$ (* de obearbetade variablerna *)
2. $\mathbf {P:=Z}$ (* de bearbetade och konditioneringsvariablerna *)
3. $\mathbf {p:=z}$ (* värdena för ${\displaystyle \mathbf {P} } *$ )
4. Medan $\mathbf {U} \neq \emptyset$ :
   1. Välj $X_{i}\in \mathbf {U}$ så att $X_{i}$ inte har fler föräldrar i $U$ än någon variabel i ${\ displaystil U}$
   2. Om alla föräldrar till $X$ är i $\mathbf {P}$
      1. $p(x_{i} |\mathbf {p} ):=p(x_{i}|\mathbf {pa_{i}} )$
   3. Annars
      1. Använd en modifierad ordnad Gibbs-sampler för att bestämma $p(x_{i}|\mathbf {p} )$
   4. $\mathbf {U:=U} -X_{i}$
   5. $\mathbf {P:=P} +X_{i}$
   6. $\mathbf {p:=p} +x_{i}$
5. Returnerar produkten av villkoren $p(x_{i}|\mathbf {p} )$

Ansökningar

Utöver applikationerna för probabilistisk slutledning är följande applikationer i kategorin Collaborative Filtering (CF), som är uppgiften att förutsäga preferenser. Beroendenätverk är en naturlig modellklass att basera CF-förutsägelser på, när en algoritm för denna uppgift bara behöver uppskattning av $p(x_{i}=1|\ mathbf {x} -{x_{i}}=0)$ för att producera rekommendationer. I synnerhet kan dessa uppskattningar erhållas genom en direkt uppslagning i ett beroendenätverk.

• Förutsäga vilka filmer en person kommer att gilla baserat på hans eller hennes betyg av filmer som har setts;
• Förutsäga vilka webbsidor en person kommer att komma åt baserat på hans eller hennes historik på webbplatsen;
• Förutsäga vilka nyheter en person är intresserad av baserat på andra berättelser han eller hon läser;
• Att förutsäga vilken produkt en person kommer att köpa baserat på produkter som han eller hon redan har köpt och/eller hamnat i hans eller hennes varukorg.

En annan klass av användbara applikationer för beroendenätverk är relaterad till datavisualisering, det vill säga visualisering av prediktiva relationer.

Se även

• Relationsberoende nätverk