Representing Knowledge in Learning Systems by Pseudo Boolean Functions
Haim Shvaytser · 1988
Concepts that can be expressed as solutions to multilinear pseudo boolean equations with a bounded degree are shown to be learnable in polynomial time from positive examples. This implies the leamability from positive examples of many families of boolean formulae by a unified algorithm. Some of these formulae were not previously known to be learnable, and some were known to be learn-able by different algorithms.