An Application of Multiple-Instance Learning to Estimate Generalization Risk

An Application of Multiple-Instance Learning to Estimate Generalization Risk Daiki Suehiro Kyushu University / RIKEN Abstract We focus on several learning approaches that employ max-operator to evaluate the margin. For example, such approaches are commonly used in multi-class learning task and top-rank learning task. In general, in order to estimate the theoretical generalization risk, we need to individually evaluate the complexity of each hypothesis class used in the learning approaches. In this paper, we provide a technique to estimate a theoretical generalization risk for such learning approaches in a same fashion. The key idea is to "redundantly" reformulate the learning problem as one-class multiple-instance learning by redefining the specific input space based on the original input space. Surprisingly, we succeed to improve the generalization risk bounds for some multi-class learning and top-rank learning algorithms. 1 Introduction A lot of margin-based learning approaches such as SVMs have a strong theoretical generalization risk bound and well works in practice. In this paper, we focus on learning approaches that define a margin based on max-operator.