The autors study the computational feasibility of learning boolean expressions from examples. Their goals are to prove results and develop general techniques that shed light on the boundary between the classes of expressions that are learnable in polynomial time and those that are apparently not. They employ the distribution-free model of learning. Their results fall into three categories: closure properties of learnable classes, negative results, and distribution-specific positive results.
|Original language||English (US)|
|Number of pages||11|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1987|
ASJC Scopus subject areas