QUANTIFYING PRIOR DETERMINATION KNOWLEDGE USING THE PAC LEARNING-MODEL

Prior knowledge, or bias, regarding a concept can reduce the number of examples needed to learn it. Probably Approximately Correct (PAC) lea rning is a mathematical model of concept learning that can be used to quantify the reduction in the number of examples due to different form s of bias. Thus far, PAC learning has mostly been used to analyze synt actic bias, such as limiting concepts to conjunctions of boolean prepo sitions. This paper demonstrates that PAC learning can also be used to analyze semantic bias, such as a domain theory about the concept bein g learned. The key idea is to view the hypothesis space in PAC learnin g as that consistent with all prior knowledge, syntactic and semantic. In particular, the paper presents an analysis of determinations, a ty pe of relevance knowledge. The results of the analysis reveal crisp di stinctions and relations among different determinations, and illustrat e the usefulness of an analysis based on the PAC learning model.