Strong separation of learning classes
John Case, Keh-Jiann Chen, Sanjay K. Jain · Journal of Experimental & Theoretical Artificial Intelligence · 1992
Suppose LC 1 and LC 2 are two machine learning classes each based on a criterion of success. Suppose, for every machine which learns a class of functions according to the LC 2 criterion of success, there is a machine which learns this class according to the LC 2 criterion. In the case where the converse does not hold LC, is said to be separated from LC 2. It is shown that for many such separated learning classes from the literature a much stronger separation holds: (∀𝒞∈LC 1) (∃𝒞' ∈LC 2 - LC 1(( [' ⊃𝒞] It is also shown that there is a pair of separated learning classes from the literature for which the stronger separation above does not hold. A philosophical heuristic toward the design of artificially intelligent learning programs is presented with each strong separation result.