Crashkurs zur Sommerzeit

Die Dempster-Shafer-Theorie (DST) bietet eine Methode, um verschiedene Beweisquellen zu einem Glauben zu kombinieren. Bei einer Liste möglicher Aussagen (von denen eine die wahre Antwort ist) wird jeder möglichen Kombination von Aussagen eine "Masse" zugewiesen, die den Grad der unterstützenden Beweise angibt. Die Gesamtmasse aller Kombinationen ist immer gleich 1.

Aus diesen Massenzuordnungen können wir eine vernünftige Untergrenze (Glaube) und Obergrenze (Plausibilität) für die Wahrheit dieser Kombination erstellen. Der Glaube bel(X)einer Menge X ist die Summe der Massen aller Teilmengen von X (einschließlich sich selbst). Die Plausibilität pl(X)einer Menge X ist "1 - die Summe der Massen aller Mengen, die zu X disjunkt sind". Das folgende Diagramm zeigt, wie Glaube und Plausibilität mit Unsicherheit zusammenhängen.

GNehmen Ywir zum Beispiel an, es gibt eine Ampel, die entweder reen, ellow oder Red sein kann. Die Liste der Optionen und eine mögliche Massenzuordnung ist unten dargestellt:

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

Diese Massen können von einem Array notiert werden [0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15].

Die Frage ist nun, wie wir entscheiden, was die Massen sind. Nehmen wir an, wir hatten einen Sensor, der das Licht betrachtete, und dieser Sensor zeigt an, dass das Licht nicht grün ist . Wir wissen jedoch, dass die Wahrscheinlichkeit, dass der Sensor ein zufälliges, falsches Signal sendet, bei 20% liegt. Dieser Beweis kann durch die Massenverteilung beschrieben werden, bei der [0, 0, 0, 0.8, 0, 0, 0, 0.2]{Y, R} eine Masse von 0,8 und {G, Y, R} eine Masse von 0,2 hat.

Nehmen wir an, ein zweiter Sensor zeigt an, dass das Licht nicht rot ist , aber wir wissen auch, dass die Wahrscheinlichkeit, dass der Sensor falsch und das Licht tatsächlich rot ist, bei 30% liegt. Dieses Beweisstück kann beschrieben werden, indem [0, 0.3, 0, 0, 0, 0, 0.7, 0]{G, Y} eine Masse von 0,7 und {R} eine Masse von 0,3 hat.

Um diese beiden Beweisstücke zu einer einzigen Massenverteilung zusammenzufassen, können wir die Dempster-Kombinationsregel verwenden.

Dempsters Kombinationsregel

Zwei Massenzuordnung m1und m2kann kombiniert werden , um zu bilden m1,2unter Verwendung der folgenden Formeln, in denen A, Bund Cstellt mögliche Kombinationen (Zeilen der Tabelle oben).

Dabei ist K ein Maß für "Konflikt", das für die Renormierung verwendet wird, und wird berechnet durch:

Es ist auch möglich, diesen Prozess geometrisch zu beschreiben, wie in der Abbildung unten. Wenn A = 011(Gelb oder Rot) und B = 101(Grün oder Rot), trägt der Wert von m1(A) * m2(B) zum Wert von m1,2(001)(Rot) bei (wird zu diesem addiert ). Dieser Vorgang wird für alle möglichen Kombinationen von A und B wiederholt, wobei A&B != 0. Schließlich wird das Array renormiert, sodass sich die Werte zu insgesamt 1 addieren.

Hier ist eine einfache Java-Methode, die zwei Arrays nach der Dempster-Regel kombiniert:

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;
}

Um zu sehen, wie dies in der Praxis funktioniert, betrachten Sie die obigen Ampelsensoren, die unabhängig voneinander die Massen [0, 0, 0, 0.8, 0, 0, 0, 0.2]und angeben [0, 0.3, 0, 0, 0, 0, 0.7, 0]. Dempsters Regel Nach der Durchführung der resultierende gemeinsame Masse ist [0, 0.3, 0.56, 0, 0, 0, 0.14, 0]. Der Großteil der Masse wird "Gelb" zugeordnet, was intuitiv sinnvoll ist, da die beiden Sensoren "nicht grün" bzw. "nicht rot" zurückgaben. Die anderen beiden Massen (0,3 für "Rot" und 0,14 für "Grün oder Gelb") sind auf die Unsicherheit der Messungen zurückzuführen.

Die Herausforderung

Schreiben Sie ein Programm, das zwei Listen mit reellen Zahlen verwendet und das Ergebnis der Anwendung der Dempster-Regel auf die beiden Eingabelisten ausgibt. Die Längen der beiden Eingabelisten sind gleich, und diese Länge ist eine Potenz von 2 und beträgt mindestens 4. Für jede Liste ist der erste Wert immer 0 und die verbleibenden Werte sind alle nicht negativ und addieren sich bis zu 1.

Die Ausgabe sollte eine Liste mit der gleichen Länge wie die Eingabelisten sein. Sie können davon ausgehen, dass eine Lösung existiert (es ist möglich, dass eine Lösung nicht existiert, wenn ein totaler Konflikt zwischen Beweisen und damit K = 1 besteht). Um eine Mindestanforderung an die Genauigkeit zu stellen, muss Ihr Programm in der Lage sein, Ergebnisse zu liefern, die genau sind, wenn sie auf vier Dezimalstellen gerundet werden.

Beispiel E / A.

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 Bytes

Beinhaltet +2 für -an

Geben Sie den ersten Satz als Zeile und den zweiten als Spalte in STDIN an

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

Eine ziemlich normale Golflösung. Funktioniert nicht, wenn ich ersetzen @Hdurch@;