Crash Course on DST

A teoria Dempster-Shafer (DST) fornece um método para combinar várias fontes de evidência para formar uma crença. Dada uma lista de possíveis afirmações (uma das quais é a resposta verdadeira), a cada combinação possível de afirmações é atribuída uma "massa" indicando o grau de evidência de apoio. A massa total de todas as combinações é sempre igual a 1.

A partir dessas designações em massa, podemos criar um limite inferior razoável (crença) e um limite superior (plausibilidade) sobre a verdade dessa combinação. A crença bel(X)em qualquer conjunto X é a soma das massas de todos os subconjuntos de X (incluindo ele próprio). A plausibilidade pl(X)de qualquer conjunto X é "1 - a soma das massas de todos os conjuntos é disjunta para X". O diagrama abaixo ilustra como crença e plausibilidade estão relacionadas à incerteza.

Por exemplo, digamos que haja um semáforo que possa ser um dos Green, Yellow ou Red. A lista de opções e uma possível atribuição em massa é mostrada abaixo:

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

Essas massas podem ser anotadas por uma matriz [0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15].

Agora, a pergunta é: como decidimos quais são as massas? Digamos que tínhamos um sensor olhando para a luz, e esse sensor indica que a luz não é verde ; no entanto, sabemos que há uma chance de 20% de o sensor enviar um sinal aleatório e falso. Essa evidência pode ser descrita pela distribuição de massa em [0, 0, 0, 0.8, 0, 0, 0, 0.2]que {Y, R} possui uma massa de 0,8 e {G, Y, R} tem uma massa de 0,2.

Da mesma forma, digamos que algum segundo sensor indique que a luz não está vermelha , mas também sabemos que há uma chance de 30% de que o sensor esteja errado e que a luz esteja realmente vermelha. Essa evidência pode ser descrita por [0, 0.3, 0, 0, 0, 0, 0.7, 0]onde {G, Y} possui uma massa de 0,7 e {R} tem uma massa de 0,3.

Para assimilar essas duas evidências para formar uma única distribuição em massa, podemos usar a Regra de Combinação de Dempster.

Regra de Combinação de Dempster

Dois atribuição em massa m1e m2podem ser combinados para formar m1,2usando as seguintes fórmulas, onde A, Be Crepresentam possíveis combinações (linhas da tabela acima).

onde K é uma medida de "conflito", usada para renormalização e é calculada por:

Também é possível descrever esse processo geometricamente, como na imagem abaixo. Se A = 011(Amarelo ou Vermelho) e B = 101(Verde ou Vermelho), o valor de m1(A) * m2(B) contribui para (é adicionado a) o valor de m1,2(001)(Vermelho). Este processo é repetido para todas as combinações possíveis de A e B em que A&B != 0. Finalmente, a matriz é renormalizada para que os valores totalizem 1.

Aqui está um método Java simples que combina duas matrizes seguindo a regra 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 como isso funciona na prática, considere os sensores de semáforo acima, que fornecem independentemente as massas [0, 0, 0, 0.8, 0, 0, 0, 0.2]e [0, 0.3, 0, 0, 0, 0, 0.7, 0]. Após executar a regra de Dempster, a massa articular resultante é [0, 0.3, 0.56, 0, 0, 0, 0.14, 0]. A maioria da massa é atribuída a "Amarelo", o que faz sentido intuitivo, pois os dois sensores retornaram "não verde" e "não vermelho", respectivamente. As outras duas massas (0,3 para "Vermelho" e 0,14 para "Verde ou Amarelo") são devidas à incerteza das medições.

O desafio

Escreva um programa que pegue duas listas de números reais e produz o resultado da aplicação da regra de Dempster às duas listas de entrada. Os comprimentos das duas listas de entrada serão iguais, e esse comprimento será uma potência de 2 e será pelo menos 4. Para cada lista, o primeiro valor será sempre 0 e os valores restantes serão todos não negativos e incluirão até 1.

A saída deve ser uma lista com o mesmo comprimento que as listas de entrada. Você pode assumir que existe uma solução (é possível que uma solução não exista quando houver conflito total entre evidências e, portanto, K = 1). Para colocar um requisito mínimo em precisão, seu programa deve ser capaz de produzir resultados precisos quando arredondados para quatro casas decimais.

Exemplo 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

Inclui +2 para -an

Dê o primeiro conjunto como linha e o segundo como uma coluna em 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

Uma solução bastante padrão de golfe. Não funciona se eu substituir @Hpor@;