Bias, Version Spaces and Valiant's Learning Framework

This work presents an overview of some recent theoretical results in the learning framework introduced by Valiant and a comparison to the work of Mitchell on version spaces, and discusses learning problems for both attribute-based and structural domains.

Abstract

We present an overview of some recent theoretical results in the learning framework introduced by Valiant in (Valiant, 1984) and further developed in (Valiant 1985; Blumer, et. al., 1986, in press; Pitt & Valiant, 1986; Haussler, 1986; Angluin & Laird, 1986; Angluin, 1986; Rivest, 1986; Haussler, 1987; Kearns, et. al., 1987). Our focus is on applications to AI problems of learning from examples as given in (Haussler, 1986, 1987) and (Kearns, et. al., 1987), along with a comparison to the work of Mitchell on version spaces (Mitchell, 1982). We discuss learning problems for both attribute-based and structural domains.