Realizar la regla de combinación de Dempster

9

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.

ingrese la descripción de la imagen aquí

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).

ingrese la descripción de la imagen aquí

ingrese la descripción de la imagen aquí

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

ingrese la descripción de la imagen aquí

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.

https://www.researchgate.net/profile/Fabio_Cuzzolin/publication/8337705/figure/fig1/AS:349313566822412@1460294252311/Fig-1-Dempster's-rule-of-combination-On-the-yx-axes-are- representó-los-elementos-focales_big.pbm

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]
PhiNotPi
fuente
2
Algunas cosas que quería publicar en el sandbox, pero no tuve la oportunidad: creo que la mayoría de las preguntas deben escribirse para que cualquier profeta en álgebra pueda entenderlas ... aquí hay algunas cosas que creo que deberían aclararse: ¿Qué? es m (x)? ¿Qué es un conjunto disjunto? ¿Cómo se pasa del 20% a un conjunto de masas? ¿Por qué necesitas convertir masas a otro conjunto de masas? ¿Qué representa el theta en tu primera ecuación? ¿Qué representan AB y C? ¿Por qué incluir DST si el desafío se basa únicamente en DRC? No es necesario confundir a las personas.
@trichoplax Agregué un requisito de precisión mínimo (exacto cuando se redondea a 4 decimales).
PhiNotPi

Respuestas:

2

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

Ton Hospel
fuente
Buena esa. Sobre el "no funciona con @;": consulte stackoverflow.com/questions/39521060/…
Dada
@Dada Esa respuesta de desbordamiento de pila fue muy útil. Sabía vagamente que estas variables no se interpolan, pero nunca entendí la razón. Y me ahorra un byte en Praming Puzles & Colf: Condense a String
Ton Hospel
Antes de su edición, escribió "de alguna manera", por lo que en caso de que no supiera por qué, bueno, es una opción indocumentada en la implementación ... El "no funciona con @;" es por el "@ H" ¿verdad? (Si no, entonces mi mal, no importa mi comentario)
Dada
Sí, debido a que @Hdespués de hacer la publicación, experimenté un poco más y vi que el problema era la interpolación de cadenas, así que eliminé el "de alguna manera" porque al menos la razón directa estaba clara. Pero hasta que me referiste a ese artículo todavía no sabía POR QUÉ ese tipo de interpolación no funciona. Ahora me doy cuenta de que es una elección consciente por parte de los desarrolladores, por lo que los usuarios se sorprenderán con menos frecuencia por la interpolación inesperada de la matriz, ya que la mayoría de los usuarios no conocen las variables de puntuación.
Ton Hospel
Oh, lo siento, leí mal tu comentario anterior: leí "no fue muy útil" en lugar de "fue muy útil". Bueno, entonces estamos de acuerdo!
Dada