Representing uncertainty on set-valued variables using belief functions

A formalism is proposed for representing uncertain information on set-valued variables using the formalism of belief functions. A set-valued variable X on a domain Ω is a variable taking zero, one or several values in Ω. While defining mass functions on the frame Ω22 is usually not feasible because of the double-exponential complexity involved, we propose an approach based on a definition of a restricted family of subsets of Ω2 that is closed under intersection and has a lattice structure. Using recent results about belief functions on lattices, we show that most notions from Dempster–Shafer theory can be transposed to that particular lattice, making it possible to express rich knowledge about X with only limited additional complexity as compared to the single-valued case. An application to multi-label classification (in which each learning instance can belong to several classes simultaneously) is demonstrated.