Crash Course na DST

Teoria Dempstera – Shafera (DST) zapewnia metodę łączenia różnych źródeł dowodów w celu uzyskania przekonania. Biorąc pod uwagę listę możliwych stwierdzeń (z których jedno jest prawdziwą odpowiedzią), każdej możliwej kombinacji oświadczeń przypisuje się „masę” wskazującą stopień potwierdzających dowodów. Całkowita masa wszystkich kombinacji jest zawsze równa 1.

Na podstawie tych przypisań masy możemy stworzyć rozsądną dolną granicę (przekonanie) i górną granicę (wiarygodność) na podstawie prawdziwości tej kombinacji. Wiara bel(X)w dowolny zestaw X jest sumą mas wszystkich podzbiorów X (w tym siebie). Prawdopodobieństwo pl(X)dowolnego zbioru X wynosi „1 - suma mas wszystkich zbiorów rozłącznych z X”. Poniższy schemat ilustruje, w jaki sposób wiara i wiarygodność są powiązane z niepewnością.

Załóżmy na przykład, że istnieje sygnalizacja świetlna, która może być jedną z następujących opcji: Green, Yellow lub Red. Lista opcji i możliwe przypisanie masy jest pokazana poniżej:

binary    interpretation    m(X)    bel(X)  pl(x)
000       null              0       0       0
001       R                 0.2     0.2     0.7
010       Y                 0.1     0.1     0.3 
011       Y||R              0.05    0.35    0.8
100       G                 0.2     0.2     0.65
101       G||R              0.3     0.7     0.9
110       G||Y              0       0.3     0.8
111       G||Y||R           0.15    1       1

Masy te można zapisać za pomocą tablicy [0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15].

Teraz pytanie brzmi: w jaki sposób decydujemy, jakie są masy? Powiedzmy, że mieliśmy czujnik, który patrzy na światło, a ten czujnik wskazuje, że światło nie jest zielone ; wiemy jednak, że istnieje 20% szansy, że czujnik wyśle ​​losowy, fałszywy sygnał. Ten dowód można opisać rozkładem masy, w [0, 0, 0, 0.8, 0, 0, 0, 0.2]którym {Y, R} ma masę 0,8, a {G, Y, R} ma masę 0,2.

Podobnie, powiedzmy, że jakiś drugi czujnik wskazuje, że światło nie jest czerwone , ale wiemy również, że istnieje 30% szans, że czujnik jest nieprawidłowy, a światło jest faktycznie czerwone. Ten dowód można opisać, [0, 0.3, 0, 0, 0, 0, 0.7, 0]gdzie {G, Y} ma masę 0,7, a {R} ma masę 0,3.

Aby przyswoić te dwa dowody i utworzyć pojedynczy rozkład masy, możemy zastosować Regułę Dempstera.

Reguła kombinacji Dempstera

Przypisanie dwóch masę m1i m2mogą być łączone w celu wytworzenia m1,2z użyciem następujących wzorów, w których A, Bi Cstanowią możliwe kombinacje (wiersze tabeli powyżej).

gdzie K jest miarą „konfliktu” używaną do renormalizacji i jest obliczane przez:

Można również opisać ten proces geometrycznie, jak na poniższym obrazku. Jeśli A = 011(żółty lub czerwony) i B = 101(zielony lub czerwony), to wartość m1(A) * m2(B) przyczynia się do (jest dodawana) wartości m1,2(001)(czerwonego). Proces ten powtarza się dla wszystkich możliwych kombinacji A i B, gdzie A&B != 0. Na koniec tablica jest znormalizowana, dzięki czemu wartości sumują się do 1.

Oto prosta metoda Java, która łączy dwie tablice zgodnie z regułą Dempstera:

public static double[] combine(double[] a, double[] b) {
  double[] res = new double[a.length];
  for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < b.length; j++) {
      res[i & j] += a[i] * b[j];
    }
  }
  for (int i = 1; i < res.length; i++) {
    res[i] /= 1 - res[0];
  }
  res[0] = 0;
  return res;
}

Aby zobaczyć, jak to działa w praktyce, rozważ powyższe czujniki sygnalizacji świetlnej, które niezależnie dają masy [0, 0, 0, 0.8, 0, 0, 0, 0.2]i [0, 0.3, 0, 0, 0, 0, 0.7, 0]. Po wykonaniu reguły Dempstera wynikowa masa łączna wynosi [0, 0.3, 0.56, 0, 0, 0, 0.14, 0]. Większość masy jest przypisana do „żółtego”, co ma intuicyjny sens, biorąc pod uwagę, że dwa czujniki zwróciły odpowiednio „nie zielony” i „nie czerwony”. Pozostałe dwie masy (0,3 dla „czerwonego” i 0,14 dla „zielonego lub żółtego”) wynikają z niepewności pomiarów.

Wyzwanie

Napisz program, który pobiera dwie listy liczb rzeczywistych i wyprowadza wynik zastosowania reguły Dempstera do dwóch list wejściowych. Długości dwóch list wejściowych będą równe, a ta długość będzie potęgą 2 i będzie wynosić co najmniej 4. Dla każdej listy pierwszą wartością zawsze będzie 0, a pozostałe wartości będą nieujemne i będą dodane do 1.

Dane wyjściowe powinny być listami o tej samej długości co listy danych wejściowych. Możesz założyć, że istnieje rozwiązanie (możliwe, że rozwiązanie nie istnieje, gdy istnieje całkowity konflikt między dowodami, a zatem K = 1). Aby wprowadzić minimalne wymagania dotyczące precyzji, program musi być w stanie generować dokładne wyniki po zaokrągleniu do czterech miejsc po przecinku.

Przykład I / O

in:
[0, 0, 0, 0.8, 0, 0, 0, 0.2]
[0, 0.3, 0, 0, 0, 0, 0.7, 0]
out:
[0.0, 0.3, 0.56, 0.0, 0.0, 0.0, 0.14, 0.0]

in:
[0.0, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.4]
[0.0, 0.2, 0.0, 0.2, 0.0, 0.2, 0.0, 0.4]
out:
[0.0, 0.2889, 0.0889, 0.1556, 0.0889, 0.1556, 0.0444, 0.1778]

in:
[0.0, 0.0, 0.5, 0.5]
[0.0, 0.7, 0.1, 0.2]
out:
[0.0, 0.53846, 0.30769, 0.15385]

in:
[0.0, 0.055, 0.042, 0.098, 0.0, 0.152, 0.0, 0.038, 0.031, 0.13, 0.027, 0.172, 0.016, 0.114, 0.058, 0.067]
[0.0, 0.125, 0.013, 0.001, 0.012, 0.004, 0.161, 0.037, 0.009, 0.15, 0.016, 0.047, 0.096, 0.016, 0.227, 0.086]
out: (doesn't have to be this precise)
[0.0, 0.20448589713416732, 0.11767361551134202, 0.028496524069011694, 0.11809792349331062, 0.0310457664246791, 0.041882026540181416, 0.008093533320057205, 0.12095719354780314, 0.11306959103499466, 0.06412594818690368, 0.02944697394862137, 0.06398564368086611, 0.014369896989336852, 0.03774983253978312, 0.006519633578941643]

in:
[0.0, 0.0, 0.1, 0.1, 0.0, 0.0, 0.0, 0.1, 0.1, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.0, 0.1, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.1, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.0, 0.0, 0.0, 0.1, 0.1, 0.0, 0.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.0, 0.0, 0.1, 0.0, 0.1, 0.0]
out:
[0.0, 0.09090909090909094, 0.23376623376623382, 0.0, 0.07792207792207795, 0.025974025974026, 0.03896103896103895, 0.0, 0.10389610389610393, 0.05194805194805199, 0.02597402597402597, 0.0, 0.012987012987012984, 0.012987012987012993, 0.012987012987012984, 0.0, 0.09090909090909094, 0.038961038961038995, 0.06493506493506492, 0.0, 0.07792207792207796, 0.0, 0.0, 0.0, 0.012987012987012984, 0.012987012987013, 0.012987012987012984, 0.0, 0.0, 0.0, 0.0, 0.0]

Perl, 68 bajtów

Obejmuje +2 za -an

Daj pierwszy zestaw jako wiersz, a drugi jako kolumnę na STDIN

perl -M5.010 dempster.pl
0.0  0.0  0.5  0.5
0.0
0.7
0.1
0.2
^D
^D

dempster.pl:

#!/usr/bin/perl -an
/$/,map$H[$m%@F&$m++/@F]+=$_*$`,@F for<>;say$%++&&$_/(1-"@H")for@H

Całkiem standardowe rozwiązanie do gry w golfa. Nie działa, jeśli zastąpić @Hprzez@;