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. © 2010 Elsevier B.V. All rights reserved.