Abstract
The problem we address in this paper is to label datapoints when the information about them is provided primarily in terms of their subsets or groups. The knowledge we have for a group is a likelihood value for each group member to belong to same class. These likelihood values are computed using a model, either explicit or implicit, of the pattern we wish to learn. By defining a Markov Random Field (MRF) over the labels of data, we formulate the problem as an MRF inference problem. A submodular function is defined as clique potential function for this MRF. We identified a special form of this clique potential function that results in a simple and efficient inference method with linear running time with respect to the number of datapoints and subsets. The formulation allows augmentation of energy functions for data with several different size subsets. We present experimental results in applications where the proposed method produces improved performances over other methods.