Efficient Möbius Transformations and their applications to Dempster-Shafer Theory

La théorie de Dempster-Shafer (DST) généralise la théorie Bayesienne des probabilités, offrant d'utiles informations supplémentaires, mais souffre d'une complexité souvent supérieure. Beaucoup de travaux ont vise à réduire la complexité de transformations utilisées pour la fusion d'information avec la règle de Dempster. Les deux principales approches exploitent soit la structure du treillis Booléen, soit l'information contenue dans les sources de croyance. Chacune a ses mérites en fonction des cas. Ici, nous proposons des séquences de graphes pour le calcul de transformations de Möbius et leur inversion qui exploite `a la fois la structure du treillis Booléen et l'information des sources de croyance de façon optimale. Nous les nommons les Efficient Möbius Transformations (EMT). Nous montrons que la complexité des EMT est toujours inférieure à celle de la Fast Möbius Transform (FMT) pour toute transformation en DST. Plus généralement, les EMT peuvent être utilisées pour calculer optimalement les transformées zeta et de Möbius pour tout treillis.