Case-Based Representation and Learning of Pattern Languages

Abstract

Pattern languages seem to suit case-based reasoning particularly well. Therefore, the problem of inductively learning pattern languages is paraphrased in a case-based manner. A careful investigation requires a formal semantics for case bases together with similarity measures in terms of formal languages. Two basic semantics are introduced and investigated. It turns out that representability problems are major obstacles for case-based learnability. Restricting the attention to so-called proper patterns avoids these representability problems. A couple of learnability results for proper pattern languages are derived both for case-based learning from only positive data and for case-based learning from positive and negative data. Under the so-called competing semantics, we show that the learnability result for positive and negative data can be lifted to the general case of arbitrary patterns. Learning under the standard semantics from positive data is closely related to monotonic language learning.