Toward PAC-Learning of Weights from Qualitative Distance Information

Ken Satoh and Seishi Okamoto

This paper discusses a mathematical analysis for learning weights in a similarity function. Although there are many works on theoretical analyses of casebased reasoning systems, none has yet theoretically analyzed methods of producing a proper similarity function in accordance with a tendency of cases which many people have already proposed and empirically analyzed. In this paper, as the first step, we provide a PAC learning framework for weights with qualitative distance information. Qualitative distance information in this paper represents how a case is similar to another case. We give a mathematical analysis for learning weights from this information. In this setting, we show that we can efficiently learn a weight which has an error rate such that the size of pairs in qualitative distance information is polynomilally bounded in the dimension, n, and the inverses of e and 6, and the running time is polynomially bounded in the size of pairs.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.