Curso intensivo en horario de verano

La teoría de Dempster-Shafer (DST) proporciona un método para combinar varias fuentes de evidencia para formar una creencia. Dada una lista de posibles afirmaciones (una de las cuales es la respuesta verdadera), a cada combinación posible de afirmaciones se le asigna una "masa" que indica el grado de evidencia de apoyo. La masa total de todas las combinaciones es siempre igual a 1.

A partir de estas asignaciones masivas, podemos crear un límite inferior razonable (creencia) y un límite superior (plausibilidad) sobre la verdad de esa combinación. La creencia bel(X)de cualquier conjunto X es la suma de las masas de todos los subconjuntos de X (incluido él mismo). La plausibilidad pl(X)de cualquier conjunto X es "1 - la suma de las masas de todos los conjuntos disjuntos a X". El siguiente diagrama ilustra cómo la creencia y la plausibilidad están relacionadas con la incertidumbre.

Por ejemplo, digamos que hay un semáforo que podría ser uno cualquiera de Green, Yellow, o Red. La lista de opciones y una posible asignación en masa se muestra a continuación:

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

Estas masas pueden ser notadas por una matriz [0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15].

Ahora la pregunta es, ¿cómo decidimos cuáles son las masas? Digamos que teníamos un sensor mirando la luz, y este sensor indica que la luz no es verde ; Sin embargo, sabemos que hay un 20% de posibilidades de que el sensor envíe una señal aleatoria y espuria. Esta evidencia se puede describir por la distribución de masa [0, 0, 0, 0.8, 0, 0, 0, 0.2]donde {Y, R} tiene una masa de 0.8 y {G, Y, R} tiene una masa de 0.2.

Del mismo modo, digamos que un segundo sensor indica que la luz no es roja , pero también sabemos que hay un 30% de posibilidades de que el sensor esté equivocado y la luz sea realmente roja. Esta evidencia se puede describir por [0, 0.3, 0, 0, 0, 0, 0.7, 0]donde {G, Y} tiene una masa de 0.7 y {R} tiene una masa de 0.3.

Para asimilar estas dos piezas de evidencia para formar una única distribución de masa, podemos usar la Regla de combinación de Dempster.

La regla de combinación de Dempster

Dos asignaciones en masa m1y m2se pueden combinar para formar m1,2usando las siguientes fórmulas, donde A, By Crepresentan posibles combinaciones (filas de la tabla anterior).

donde K es una medida de "conflicto", utilizada para la renormalización, y se calcula mediante:

También es posible describir este proceso geométricamente, como en la imagen a continuación. Si A = 011(Amarillo o Rojo) y B = 101(Verde o Rojo), entonces el valor de m1(A) * m2(B) contribuye a (se agrega a) el valor de m1,2(001)(Rojo). Este proceso se repite para todas las combinaciones posibles de A y B donde A&B != 0. Finalmente, la matriz se renormaliza para que los valores sumen un total de 1.

Aquí hay un método Java simple que combina dos matrices siguiendo la regla 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;
}

Para ver cómo funciona esto en la práctica, tenga en cuenta los sensores de semáforos anteriores, que proporcionan independientemente las masas [0, 0, 0, 0.8, 0, 0, 0, 0.2]y [0, 0.3, 0, 0, 0, 0, 0.7, 0]. Después de realizar la regla de Dempster, la masa articular resultante es [0, 0.3, 0.56, 0, 0, 0, 0.14, 0]. La mayoría de la masa se asigna a "Amarillo", lo que tiene un sentido intuitivo dado que los dos sensores devolvieron "no verde" y "no rojo" respectivamente. Las otras dos masas (0.3 para "Rojo" y 0.14 para "Verde o Amarillo") se deben a la incertidumbre de las mediciones.

El reto

Escriba un programa que tome dos listas de números reales y genere el resultado de aplicar la regla de Dempster a las dos listas de entrada. Las longitudes de las dos listas de entrada serán iguales, y esa longitud será una potencia de 2, y será al menos 4. Para cada lista, el primer valor siempre será 0 y los valores restantes serán no negativos y sumarán hasta 1.

La salida debe ser una lista con la misma longitud que las listas de entrada. Puede suponer que existe una solución (es posible que no exista una solución cuando existe un conflicto total entre la evidencia y, por lo tanto, K = 1). Para establecer un requisito mínimo de precisión, su programa debe ser capaz de producir resultados precisos cuando se redondea a cuatro decimales.

Ejemplo de 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 bytes

Incluye +2 para -an

Dé el primer conjunto como fila y el segundo como columna en 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

Una solución de golf bastante estándar. No funciona si lo reemplazo @Hpor@;