9
\$\begingroup\$

Crash Course on DST

Dempster–Shafer theory (DST) provides a method to combine various sources of evidence to form a belief. Given a list of possible statement (one of which is the true answer), each possible combination of statements is assigned a "mass" indicating the degree of supporting evidence. The total mass of all combinations is always equal to 1.

From these mass assignments, we can create a reasonable lower bound (belief) and upper bound (plausibility) on the truth of that combination. The belief bel(X) of any set X is the sum of the masses of all of X's subsets (including itself). The plausibility pl(X) of any set X is "1 - the sum of the masses of all sets disjoint to X". The diagram below illustrates how belief and plausibility are related to uncertainty.

enter image description here

For example, let's say that there is a traffic light that could be one of either Green, Yellow, or Red. The list of options and a possible mass assignment is shown below:

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

These masses can be notated by an array [0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15].

Now the question is, how do we decide what the masses are? Let's say that we had a sensor looking at the light, and this sensor indicates that the light not green; however, we know that there's a 20% chance that the sensor sent a random, spurious signal. This piece of evidence can be described by the mass distribution [0, 0, 0, 0.8, 0, 0, 0, 0.2] where {Y,R} has a mass of 0.8 and {G,Y,R} has a mass of 0.2.

Similarly, let's say that some second sensor indicates that the light is not red, but we also know that there's a 30% chance the sensor is wrong and the light is actually red. This piece of evidence can be describe by [0, 0.3, 0, 0, 0, 0, 0.7, 0] where {G,Y} has a mass of 0.7 and {R} has a mass of 0.3.

To assimilate these two pieces of evidence to form a single mass distribution, we can use Dempster's Rule of Combination.

Dempster's Rule of Combination

Two mass assignment m1 and m2 can be combined to form m1,2 using the following formulas, where A, B and C represent possible combinations (rows of the table above).

enter image description here

enter image description here

where K is a measure of "conflict," used for renormalization, and is calculated by:

enter image description here

It is also possible to describe this process geometrically, as in the image below. If A = 011 (Yellow or Red) and B = 101 (Green or Red), then the value of m1(A) * m2(B) contributes to (is added to) the value of m1,2(001) (Red). This process is repeated for all possible combinations of A and B where A&B != 0. Finally, the array is renormalized so that the values add up to a total of 1.

https://www.researchgate.net/profile/Fabio_Cuzzolin/publication/8337705/figure/fig1/AS:349313566822412@1460294252311/Fig-1-Dempster's-rule-of-combination-On-the-y-x-axes-are-depicted-the-focal-elements_big.pbm

Here is a simple Java method that combines two arrays following Dempster's rule:

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

To see how this works in practice, consider the traffic light sensors above, which independently give the masses [0, 0, 0, 0.8, 0, 0, 0, 0.2] and [0, 0.3, 0, 0, 0, 0, 0.7, 0]. After performing Dempster's rule, the resulting joint mass is [0, 0.3, 0.56, 0, 0, 0, 0.14, 0]. The majority of mass is assigned to "Yellow", which makes intuitive sense given that the two sensors returned "not green" and "not red" respectively. The other two masses (0.3 for "Red" and 0.14 for "Green or Yellow") are due to the uncertainty of the measurements.

The Challenge

Write a program that takes two lists of real numbers and outputs the result of applying Dempster's rule to the two input lists. The lengths of the two input lists will equal, and that length will be a power of 2, and will be at least 4. For each list, the first value will always be 0 and the remaining values will all be non-negative and add up to 1.

Output should be a list with the same length as the input lists. You can assume that a solution exists (it is possible for a solution to not exist when there is total conflict between evidence and thus K=1). To place a minimum requirement on precision, your program must be able to produce results that are accurate when rounded to four decimal places.

Example I/O

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]
\$\endgroup\$
  • 2
    \$\begingroup\$ Some things I wanted to post in the sandbox, but didn't get the chance: I think that most questions should be written so that anyone profecient in algebra could understand them.. here are a few things that I think should be clarified: What is m(x)? what is a disjoint set? how do you get from 20% to a set of masses? why do you need to convert masses to another set of masses? what does the theta represent in your first equation? what do A B and C represent? Why include DST if the challenge is solely based on DRC? no need to confuse people. \$\endgroup\$ – user56309 Sep 27 '16 at 16:27
  • \$\begingroup\$ @trichoplax I added a minimum precision requirement (accurate when rounded to 4 decimal places). \$\endgroup\$ – PhiNotPi Sep 27 '16 at 16:57
2
\$\begingroup\$

Perl, 68 bytes

Includes +2 for -an

Give the first set as row and the second as a column on 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

A pretty standard golf solution. Doesn't work if I replace @H by @;

\$\endgroup\$
  • \$\begingroup\$ Nice one. About the "doesn't work with @;" : see stackoverflow.com/questions/39521060/… \$\endgroup\$ – Dada Sep 29 '16 at 8:04
  • \$\begingroup\$ @Dada That stack overflow answer was very useful. I vaguely knew these variables don't interpolate but never understood the reason. And it saves me a byte in Praming Puzles & Colf: Condense a String \$\endgroup\$ – Ton Hospel Sep 29 '16 at 9:45
  • \$\begingroup\$ Before your edit, you wrote "somehow", so in case you didn't know why, well it's kind of an undocumented choice in the implementation... The "doesn't work with @;" is because of the "@H" right? (If not then my bad, never mind my comment) \$\endgroup\$ – Dada Sep 29 '16 at 9:56
  • \$\begingroup\$ Yes, because of the @H After I made the post I did a bit more experimenting and saw the problem was the string interpolation so I removed the "somehow" because at least the direct reason was clear. But until you referred me to that article I still didn't know WHY that kind of interpolation doesn't work. Now I realize it's a conscious choice by the developers so users will get surprised less often by unexpected array interpolation since most users are not very aware of the punctuation variables. \$\endgroup\$ – Ton Hospel Sep 29 '16 at 10:05
  • \$\begingroup\$ Oh sorry, I misread your previous comment : I read "wasn't very useful" instead of "was very useful". Well we agree then! \$\endgroup\$ – Dada Sep 29 '16 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.