Name
Abstract | ||
|---|---|---|
Abstract. In the k-Restricted-Focus-of-Attention (k-RFA) model, only k of the n attributes of each example are revealed to the learner, although the set of visible attributes in each example is determined by the learner. While the k-RFA model is a natural extension of the PAC model, there are also signiflcant difierences. For example, it was previously known that learnability in this model is not characterized by the VC-dimension and that many PAC learning algorithms are not applicable in the k-RFA setting. In this paper we further explore the relationship between the PAC and k-RFA models, with several interesting results. First, we develop an information-theoretic characterization of k-RFA learnability upon which we build a general tool for proving hardness results. We then apply this and other new techniques for studying RFA learning to two particularly expressive function classes, k-decision-lists (k-DL) and k-TOP, the class of thresholds of parity functions in which each parity function takes at most k inputs. Among other results, we prove a hardness result for k-RFA learnability of k-DL, k • n¡2. In sharp contrast, an (n¡1)-RFA algorithm for learning (n¡1)-DL is presented. Similarly, we prove that 1-DL is learnable if and only if at least half of the inputs are visible in each instance. In addition, we show that there is a uniform-distribution k-RFA learning algorithm for the class of k-DL. For k-TOP we show weak learnability by a k-RFA algorithm (with e‐cient time and sample complexity for constant k) and strong uniform-distribution k-RFA |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1023/A:1007458528570 | Machine Learning - Special issue on the ninth annual conference on computational theory (COLT '96) |
Keywords | Field | DocType |
Restricted Focus of Attention,PAC-Learning,Learning Algorithms,Boolean Function Classes,Decision Lists,Threshold of Parities,Fourier Transform | Boolean function,Discrete mathematics,Parity function,Decision list,Artificial intelligence,If and only if,Sample complexity,Parity (mathematics),Learnability,Machine learning,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 1 | 1573-0565 |
ISBN | Citations | PageRank |
0-89791-811-8 | 13 | 0.68 |
References | Authors | |
22 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Birkendorf | 1 | 40 | 3.28 |
| Eli Dichterman | 2 | 80 | 5.16 |
| Jeffrey C. Jackson | 3 | 298 | 57.80 |
| Norbert Klasner | 4 | 43 | 7.95 |
| Hans-Ulrich Simon | 5 | 567 | 104.52 |