Sieć zależności (model graficzny)

Sieci zależności (DN) to modele graficzne , podobne do sieci Markowa , w których każdy wierzchołek (węzeł) odpowiada zmiennej losowej, a każda krawędź przechwytuje zależności między zmiennymi. W przeciwieństwie do sieci bayesowskich nazwy wyróżniające mogą zawierać cykle. Każdy węzeł jest powiązany z tablicą prawdopodobieństwa warunkowego, która określa realizację zmiennej losowej przy danych jej rodzicach.

Koc Markowa

W sieci bayesowskiej koc Markowa węzła jest zbiorem rodziców i dzieci tego węzła wraz z rodzicami dzieci. Wartości rodziców i dzieci węzła ewidentnie dostarczają informacji o tym węźle. Jednak rodzice jego dzieci również muszą zostać uwzględnieni w kocu Markowa, ponieważ mogą być wykorzystani do wyjaśnienia danego węzła. W polu losowym Markowa koc Markowa dla węzła to po prostu sąsiednie (lub sąsiednie) węzły. W sieci zależności koc Markowa dla węzła jest po prostu zbiorem jego rodziców.

Sieć zależności a sieci bayesowskie

Sieci zależności mają zalety i wady w porównaniu z sieciami bayesowskimi. W szczególności łatwiej je parametryzować na podstawie danych, ponieważ istnieją wydajne algorytmy do uczenia się zarówno struktury, jak i prawdopodobieństw sieci zależności z danych. Algorytmy takie nie są dostępne dla sieci bayesowskich, dla których problem wyznaczenia optymalnej struktury jest NP-trudny. Niemniej jednak sieć zależności może być trudniejsza do zbudowania przy użyciu podejścia opartego na wiedzy opartego na wiedzy eksperckiej.

Sieci zależności a sieci Markowa

Spójne sieci zależności i sieci Markowa mają taką samą moc reprezentacji. Niemniej jednak możliwe jest konstruowanie niespójnych sieci zależności, tj. sieci zależności, dla których nie ma zgodnego ważnego łącznego rozkładu prawdopodobieństwa . Natomiast sieci Markowa są zawsze spójne.

Definicja

$_$ zestawu _ ${\ Displaystyle p (\ mathbf {x})}$ to para $(G, P)}$$Displaystyle$ jest cyklicznym grafem skierowanym, w którym każdy z jego węzłów odpowiada $zbiorem$ zmiennej w $.$ jest warunkowych rozkładów prawdopodobieństwa Rodzice $oznaczeni$ , $,$${\ Displaystyle \ mathbf {Pa_ {i}} \ subseteq (X_ {1}, \ ldots, X_ {i-1}, X_ {i + 1}, \ ldots, X_{n})}$ tym , które spełniają następujące zależności niezależności

${\ Displaystyle 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}}).}$

Sieć zależności jest spójna w tym sensie, że każdy rozkład lokalny można uzyskać z rozkładu łącznego ${\ displaystyle p (\ mathbf {x})}$ . Sieci zależności wyuczone przy użyciu dużych zestawów danych z dużymi próbami prawie zawsze będą spójne. Sieć niespójna to sieć, dla której nie ma łącznego rozkładu prawdopodobieństwa zgodnego z parą ${\ Displaystyle (G, P)}$ . W takim przypadku nie ma łącznego rozkładu prawdopodobieństwa, który spełniałby relacje niezależności zawarte w tej parze.

Uczenie struktury i parametrów

Dwa ważne zadania w sieci zależności to poznanie jej struktury i prawdopodobieństw na podstawie danych. Zasadniczo algorytm uczenia się polega na niezależnym wykonywaniu regresji probabilistycznej lub klasyfikacji dla każdej zmiennej w dziedzinie. ${x} -{x_{i}})}$ z obserwacji, że lokalny rozkład zmiennej $)$ sieci zależności jest rozkładem warunkowym ${\ Displaystyle p (x_ {i} | \$ , które można oszacować za pomocą dowolnej liczby technik klasyfikacji lub regresji, takich jak metody wykorzystujące probabilistyczne drzewo decyzyjne, sieć neuronową lub probabilistyczną maszynę wektorów nośnych. Dlatego dla każdej zmiennej $w$$.$ niezależnie jej lokalny rozkład na podstawie danych za pomocą algorytmu klasyfikacji, mimo że jest to odrębna metoda dla każdej Tutaj pokrótce pokażemy, w jaki sposób probabilistyczne drzewa decyzyjne są wykorzystywane do oszacowania lokalnych rozkładów. Dla każdej zmiennej $a$ probabilistyczne drzewo decyzyjne jest uczone, gdzie $X_ {i}}$$displaystyle$ zmienną docelową, ${\ Displaystyle \ mathbf {X} -X_ {i}}$ to zmienne wejściowe. Aby $nauczyć$ się struktury drzewa decyzyjnego dla wyszukiwania zaczyna się od pojedynczego węzła głównego bez dzieci. ${\ Displaystyle \ mathbf {X} -X_ {i}} ,$ każdy węzeł liścia w drzewie jest zastępowany podziałem binarnym na jakiejś zmiennej w $X$ więcej zastąpienia zwiększają wynik drzewa.

Wnioskowanie probabilistyczne

Wnioskowanie probabilistyczne to zadanie, w którym chcemy odpowiedzieć na probabilistyczne zapytania w postaci ${\ Displaystyle p (\ mathbf {y \ mid z})}$ , biorąc pod uwagę model graficzny dla $}}$${\ Displaystyle \ mathbf$$)$$( zmienne „wejściowe”$ , gdzie (zmienne „docelowe”) są rozłącznymi podzbiorami ${\ displaystyle \ mathbf {X}}$ . Jedną z alternatywnych metod wnioskowania probabilistycznego jest próbkowanie Gibbsa . Naiwne podejście do tego wykorzystuje uporządkowany próbnik Gibbsa, którego ważną trudnością jest to, że albo ${\ Displaystyle p (\ mathbf {y \ mid z})}$ lub ${\ displaystyle p (\mathbf {z} )}$ jest małe, to do dokładnego oszacowania prawdopodobieństwa potrzeba wielu iteracji. Innym podejściem do szacowania, ${\ Displaystyle p (\ mathbf {y \$ jest małe, jest zmodyfikowanego uporządkowanego Gibbsa $mid z$$ustalany$ , gdzie podczas próbkowania Gibbsa

Może się również zdarzyć, że $to$$ma$ , np. gdy wiele zmiennych. Tak więc prawo całkowitego prawdopodobieństwa wraz z zależnościami zakodowanymi w sieci zależności może być użyte do dekompozycji zadania wnioskowania na zbiór zadań wnioskowania na pojedynczych zmiennych. Takie podejście ma tę zaletę, że niektóre terminy można uzyskać przez bezpośrednie wyszukiwanie, unikając w ten sposób niektórych próbkowania Gibbsa.

$Poniżej$ możesz zobaczyć algorytm, którego można użyć do uzyskania y $\ mathbf {Y}}$$\ Displaystyle \ mathbf {y$ i ${\ Displaystyle \ mathbf {z} \ in \ mathbf {Z}}$ , gdzie są ${\ Displaystyle \ mathbf {Y}}$ i ${\ Displaystyle \ mathbf {Z}}$ rozłączne podzbiory.

• Algorytm 1:

1. ${\ Displaystyle \ mathbf {U: = Y}}$ (* nieprzetworzone zmienne *)
2. ${\ Displaystyle \ mathbf {P: = Z}}$ (* przetworzone i warunkowane zmienne *)
3. ${\ Displaystyle \ mathbf {p: = z}}$ (* wartości dla ${\ Displaystyle \ mathbf {P}}$ *)
4. podczas gdy ${\ Displaystyle \ mathbf {U} \ neq \ pusty zbiór}$ :
   1. Wybierz takie, że ${\ Displaystyle X_ {i}}$$nie$ ma więcej rodziców w $}$ niż jakakolwiek zmienna w $styl wyświetlania U}$$\ displaystyle$
   2. Jeśli wszyscy rodzice są w ${\ Displaystyle \$
      1. ${\ Displaystyle p (x_ {i} |\mathbf {p}):=p(x_{i}|\mathbf {pa_{i}} )}$
      ${P}}$
   3. W przeciwnym razie
      1. użyj zmodyfikowanego uporządkowanego próbnika Gibbsa, aby określić ${\ Displaystyle p (x_ {i} | \ mathbf {p})}$
   4. ${\ Displaystyle \ mathbf {U: = U} -X_ {i}}$
   5. ${\ Displaystyle \ mathbf {P: = P} + X_ {i}}$
   6. ${\ Displaystyle \ mathbf {p: = p} + x_ {i}}$
5. Zwraca iloczyn warunków warunkowych ${\ Displaystyle p (x_ {i} | \ mathbf {p})}$

Aplikacje

Oprócz aplikacji do wnioskowania probabilistycznego, następujące aplikacje należą do kategorii Collaborative Filtering (CF), która jest zadaniem przewidywania preferencji. Sieci zależności są naturalną klasą modeli, na której można oprzeć prognozy CF, gdy algorytm do tego zadania wymaga jedynie oszacowania ${\ displaystyle p (x_ {i} = 1 |\ mathbf {x} -{x_{i}}=0)}$ w celu wygenerowania rekomendacji. W szczególności oszacowania te można uzyskać przez bezpośrednie wyszukiwanie w sieci zależności.

• Przewidywanie, jakie filmy spodoba się danej osobie na podstawie jej ocen obejrzanych filmów;
• Przewidywanie, do jakich stron internetowych dana osoba będzie miała dostęp, na podstawie jej historii w witrynie;
• Przewidywanie, jakimi wiadomościami dana osoba jest zainteresowana, na podstawie innych przeczytanych przez nią wiadomości;
• Przewidywanie, jaki produkt dana osoba kupi na podstawie produktów, które już kupiła i/lub wrzuciła do swojego koszyka.

Inna klasa przydatnych aplikacji dla sieci zależności jest związana z wizualizacją danych, czyli wizualizacją relacji predykcyjnych.

Zobacz też

• Relacyjna sieć zależności