Crash Course pada DST

Teori Dempster – Shafer (DST) menyediakan metode untuk menggabungkan berbagai sumber bukti untuk membentuk kepercayaan. Diberikan daftar pernyataan yang mungkin (salah satunya adalah jawaban yang benar), setiap kemungkinan kombinasi pernyataan diberi "massa" yang menunjukkan tingkat bukti pendukung. Massa total semua kombinasi selalu sama dengan 1.

Dari penugasan massal ini, kita dapat membuat batas bawah yang wajar (kepercayaan) dan batas atas (masuk akal) pada kebenaran kombinasi itu. Keyakinan bel(X)setiap himpunan X adalah jumlah massa semua himpunan bagian X (termasuk dirinya sendiri). Masuk akal pl(X)dari setiap set X adalah "1 - jumlah massa semua set terpisah ke X". Diagram di bawah ini menggambarkan bagaimana keyakinan dan masuk akal terkait dengan ketidakpastian.

Misalnya, katakanlah ada lampu lalu lintas yang bisa menjadi salah satu dari Green, Yellow, atau Red. Daftar opsi dan kemungkinan tugas massal ditunjukkan di bawah ini:

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

Massa ini dapat dinotasikan dengan array [0, 0.2, 0.1, 0.05, 0.2, 0.3, 0, 0.15].

Sekarang pertanyaannya adalah, bagaimana kita memutuskan massa itu? Katakanlah kita memiliki sensor yang melihat cahaya, dan sensor ini menunjukkan bahwa lampu tidak hijau ; Namun, kita tahu bahwa ada 20% kemungkinan sensor mengirim sinyal acak palsu. Sepotong bukti ini dapat dijelaskan oleh distribusi massa di [0, 0, 0, 0.8, 0, 0, 0, 0.2]mana {Y, R} memiliki massa 0,8 dan {G, Y, R} memiliki massa 0,2.

Demikian pula, katakanlah beberapa sensor kedua menunjukkan bahwa cahayanya tidak merah , tetapi kita juga tahu bahwa ada kemungkinan 30% sensornya salah dan cahayanya benar-benar merah. Sepotong bukti ini dapat diuraikan di [0, 0.3, 0, 0, 0, 0, 0.7, 0]mana {G, Y} memiliki massa 0,7 dan {R} memiliki massa 0,3.

Untuk mengasimilasi dua bukti ini untuk membentuk distribusi massa tunggal, kita dapat menggunakan Aturan Kombinasi Dempster.

Aturan Kombinasi Dempster

Dua penugasan massal m1dan m2dapat dikombinasikan untuk membentuk m1,2menggunakan rumus berikut, di mana A, Bdan Cmewakili kemungkinan kombinasi (baris tabel di atas).

di mana K adalah ukuran "konflik," yang digunakan untuk renormalisasi, dan dihitung dengan:

Dimungkinkan juga untuk menggambarkan proses ini secara geometris, seperti pada gambar di bawah ini. Jika A = 011(Kuning atau Merah) dan B = 101(Hijau atau Merah), maka nilai m1(A) * m2(B) berkontribusi ke (ditambahkan ke) nilai m1,2(001)(Merah). Proses ini diulangi untuk semua kemungkinan kombinasi A dan B di mana A&B != 0. Akhirnya, array dinormalkan ulang sehingga nilainya bertambah hingga total 1.

Berikut adalah metode Java sederhana yang menggabungkan dua array berikut aturan 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;
}

Untuk melihat bagaimana ini bekerja dalam praktek, pertimbangkan sensor lampu lalu lintas di atas, yang secara independen memberikan massa [0, 0, 0, 0.8, 0, 0, 0, 0.2]dan [0, 0.3, 0, 0, 0, 0, 0.7, 0]. Setelah melakukan aturan Dempster, massa sendi yang dihasilkan adalah [0, 0.3, 0.56, 0, 0, 0, 0.14, 0]. Mayoritas massa ditugaskan untuk "Kuning", yang masuk akal karena dua sensor kembali "tidak hijau" dan "tidak merah". Dua massa lainnya (0,3 untuk "Merah" dan 0,14 untuk "Hijau atau Kuning") disebabkan oleh ketidakpastian pengukuran.

Tantangan

Tulis program yang mengambil dua daftar bilangan real dan hasilkan penerapan aturan Dempster ke dua daftar input. Panjang dari dua daftar input akan sama, dan panjang itu akan menjadi kekuatan 2, dan akan setidaknya 4. Untuk setiap daftar, nilai pertama akan selalu 0 dan nilai yang tersisa semua akan menjadi non-negatif dan menambahkan hingga 1.

Output harus berupa daftar dengan panjang yang sama dengan daftar input. Anda dapat mengasumsikan bahwa solusi ada (ada kemungkinan solusi tidak ada ketika ada konflik total antara bukti dan dengan demikian K = 1). Untuk menempatkan persyaratan minimum pada presisi, program Anda harus dapat menghasilkan hasil yang akurat ketika dibulatkan ke empat tempat desimal.

Contoh 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]

Perl, 68 byte

Termasuk +2 untuk -an

Berikan set pertama sebagai baris dan yang kedua sebagai kolom pada 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

Solusi golf yang cukup standar. Tidak berfungsi jika saya ganti @Hdengan@;