講演 PAC Analysis of Learning Weights in Multi-Objective Function by Pairwise Comparison

概要

論文の詳細を見る
This paper presents a theoretical analysis for a learning method of weights in multi-objective function. Although there are several learning methods proposed in the literature [Dyer79, Srinivasan73a, Srinivasan73b, Tamura85], 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 [Srinivasan73a, Srinivasan73b]. In this setting, we show that we can efficiently learn a weight which has an error rate less than θ with a probability more 1-δ such that the size of pairs is polynomially bounded in the dimension, n for a solution, and θ^<-1> and δ^<-1>, and the running time is polynomially bounded in the size of pairs.
一般社団法人情報処理学会の論文
2000-05-12