Polynomial PAC Learnability of Learning Weights of Multi-objective Functions by Pairwise Comparison

概要

論文の詳細を見る
This paper presents a theoretical analysis for a learning method of weights in linear combination of multi-objective function. Although there are several learning methods proposed in the literature, none has yet been analyzed in terms of data complexity and computational complexity. This paper steps toward this direction of giving a theoretical analysis on learning method for multiple objective functions in the viewpoint of the computational learning theory. As the first step, this paper presents a theoretical analysis of learning method of weights from pairwise comparisons of solutions. In this setting, we show that we can efficiently learn a weight which has an error rate less than ε with a probability more than 1-δ such that the size of pairs is polynomially bounded in the dimension, η for a solution, and ε^<-1> and δ^<-1>, and the running time is polynomially bounded in the size of pairs.
一般社団法人情報処理学会の論文
2001-05-15