Using generalized decision ensembles to solve multi-class decision problems

It becomes popular to operate with ensembles of classifiers which are based on diversified subsets of attributes. In multi-class decision problems, one of approaches is to let single classifiers return so-called generalized decisions which gather all probable (according to them) decision classes for a given input case. Then, such sets of allowed decisions delivered by single classifiers are intersected with each other in order to derive the final output. In this talk, we recall connections between generalized decisions introduced within the theory of rough sets, multivalued dependencies known from the theory of relational databases, and saturated conditional independences considered for relational semi-graphoids. We also recall formulation of the generalized decision decomposition problem, whereby the task is to find a pair (or a bigger ensemble) of the smallest subsets of attributes such that their corresponding generalized decisions intersect toward the sets of decision classes induced by the whole set of attributes, for each single case in the training data. We show new theoretical results which characterize this task. We consider two options with respect to handling new cases which did not occur in the training data. In the first one, if a new combination of input values can be matched with a shorter combination over each single subset of attributes in the ensemble, then we let reason about such a new case by means of intersecting the corresponding generalized decisions. In the second option, if such new combination did not occur in the training data, then we additionally require from the ensemble that the intersection of the corresponding generalized decisions is empty. Surprisingly (at least to the speaker), that latter option turns out to be equivalent to a very simple statement expressed in terms of the previously considered multivalued dependencies / relational conditional independences. On the other hand, that former option turns out to correspond to quite intriguing mathematical properties which were (most likely) not studied in the literature up to now.

Link to meeting: https://meet.google.com/jbj-tdsr-aop