Toward PAC-Learning of Weights from Qualitative Distance Information

Learning Feature Relevance: Empirical and Forman Analyses

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.