Houghton St. Egham

The theory of “probably approximately correct” learnability, as introduced by Valiant (Vali), and developed by many researchers, is described, and a new sample-size bound in terms of the VC dimension of the hypothesis space is obtained. We discuss Wille's formal concept analysis and apply learnability results to this framework. A context is an incidence structure (X, A, I). For any C CX, I (C) denotes the members of A incident with C, and I (D) is dually defined for D C A. A formal concept is a pair (CAD) with C Ç X and D CA such that I (C)= D and I (D)= C. Here, a,