Cours intensif sur DST

La théorie de Dempster – Shafer (DST) fournit une méthode pour combiner diverses sources de preuves pour former une croyance. Étant donné une liste de déclarations possibles (dont l'une est la vraie réponse), chaque combinaison possible de déclarations se voit attribuer une "masse" indiquant le degré de preuve à l'appui. La masse totale de toutes les combinaisons est toujours égale à 1.

À partir de ces affectations de masse, nous pouvons créer une limite inférieure raisonnable (croyance) et une limite supérieure (plausibilité) sur la vérité de cette combinaison. La croyance bel(X)de tout ensemble X est la somme des masses de tous les sous-ensembles de X (y compris lui-même). La plausibilité pl(X)de tout ensemble X est "1 - la somme des masses de tous les ensembles disjoints à X". Le diagramme ci-dessous montre comment la croyance et la plausibilité sont liées à l'incertitude.

Par exemple, disons qu'il y a un feu de circulation qui peut être soit de type Green, Yellow ou Red. La liste des options et une éventuelle affectation en masse est présentée ci-dessous:

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

Ces masses peuvent être notées par un tableau [0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15].

Maintenant, la question est de savoir comment décider ce que sont les masses? Disons que nous avions un capteur qui regarde la lumière, et ce capteur indique que la lumière n'est pas verte ; cependant, nous savons qu'il y a 20% de chances que le capteur envoie un signal parasite aléatoire. Cet élément de preuve peut être décrit par la distribution de masse [0, 0, 0, 0.8, 0, 0, 0, 0.2]où {Y, R} a une masse de 0,8 et {G, Y, R} a une masse de 0,2.

De même, disons qu'un deuxième capteur indique que la lumière n'est pas rouge , mais nous savons également qu'il y a 30% de chances que le capteur soit incorrect et que la lumière soit réellement rouge. Cet élément de preuve peut être décrit par [0, 0.3, 0, 0, 0, 0, 0.7, 0]où {G, Y} a une masse de 0,7 et {R} a une masse de 0,3.

Pour assimiler ces deux éléments de preuve pour former une distribution de masse unique, nous pouvons utiliser la règle de combinaison de Dempster.

Règle de combinaison de Dempster

Deux affectations en masse m1et m2peuvent être combinées pour former en m1,2utilisant les formules suivantes, où A, Bet Creprésentent des combinaisons possibles (lignes du tableau ci-dessus).

où K est une mesure de «conflit», utilisé pour la renormalisation, et est calculé par:

Il est également possible de décrire ce processus géométriquement, comme dans l'image ci-dessous. Si A = 011(Jaune ou Rouge) et B = 101(Vert ou Rouge), alors la valeur de m1(A) * m2(B) contribue à (est ajoutée à) la valeur de m1,2(001)(Rouge). Ce processus est répété pour toutes les combinaisons possibles de A et B où A&B != 0. Enfin, le tableau est renormalisé afin que les valeurs totalisent 1.

Voici une méthode Java simple qui combine deux tableaux suivant la règle de Dempster:

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

Pour voir comment cela fonctionne dans la pratique, considérez les capteurs de feux de circulation ci-dessus, qui donnent indépendamment les masses [0, 0, 0, 0.8, 0, 0, 0, 0.2]et [0, 0.3, 0, 0, 0, 0, 0.7, 0]. Après avoir exécuté la règle de Dempster, la masse articulaire résultante est [0, 0.3, 0.56, 0, 0, 0, 0.14, 0]. La majorité de la masse est attribuée à "Jaune", ce qui est intuitif étant donné que les deux capteurs sont retournés respectivement "pas vert" et "pas rouge". Les deux autres masses (0,3 pour "Rouge" et 0,14 pour "Vert ou Jaune") sont dues à l'incertitude des mesures.

Le défi

Écrivez un programme qui prend deux listes de nombres réels et génère le résultat de l'application de la règle de Dempster aux deux listes d'entrée. Les longueurs des deux listes d'entrée seront égales, et cette longueur sera une puissance de 2, et sera au moins 4. Pour chaque liste, la première valeur sera toujours 0 et les valeurs restantes seront toutes non négatives et s'ajouteront jusqu'à 1.

La sortie doit être une liste de la même longueur que les listes d'entrée. Vous pouvez supposer qu'une solution existe (il est possible qu'une solution n'existe pas lorsqu'il y a un conflit total entre les preuves et donc K = 1). Pour placer une exigence minimale sur la précision, votre programme doit être capable de produire des résultats qui sont précis lorsqu'il est arrondi à quatre décimales.

Exemple d'E / S

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 octets

Comprend +2 pour -an

Donnez le premier ensemble sous forme de ligne et le second sous forme de colonne sur 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

Une solution de golf assez standard. Ne fonctionne pas si je remplace @Hpar@;