To Stephen D. Scott's home page
Abstract
Recently, there has been a significant amount of research studying the multiple-instance learning model, yet all of this work has only considered this model when there are boolean labels. However, in many of the application areas for which the multiple-instance model fits, real-valued labels are more appropriate than boolean labels. In this paper we define and study a real-valued multiple-instance model in which each multiple-instance example is given a real-valued classification in [0,1]. The real-valued classification indicates the degree to which the example satisfies the target concept. To provide additional structure to the resulting learning problem, we associate a real-valued label with each point in the multiple-instance example. These values are then combined using a real-valued aggregation operator to obtain the classification for the example. Motivated by the possible application of learning geometric patterns to problems in pattern recognition and scene classification (with applications to content-based image retrieval), we provide on-line agnostic algorithms for learning real-valued multiple-instance geometric concepts defined by axis-aligned boxes in constant dimensional space. We obtain our learning algorithm by reducing the problem to one in which the exponentiated gradient (or gradient descent) algorithm can be used.We also give a novel application of the virtual weights technique. In typical applications of the virtual weights technique, all of the concepts in a group have the same weight and prediction which allows a single ``representative'' concept from each group to be tracked. However, in our application there are an exponential number of different weights (and possible predictions). Hence, boxes in each group have different weights and predictions making the computation of the contribution of a group significantly more involved. However, we are able to both keep the number of groups polynomial in the number of trials and efficiently compute the overall prediction.
Keywords: Exponentiated Gradient algorithm, multiplicative weight updates, virtual weights, geometric patterns, multiple-instance learning, real-valued labels, scene classification, content-based image retrieval, landmark matching
To Stephen D. Scott's home page
Last modified 10 November 2000.