Ignoring data may be the only way to learn efficiently |
| |
Authors: | ROLF WIEHAGEN THOMAS ZEUGMANN |
| |
Affiliation: | 1. Department of Computer Science , University of Kaiserslautern , P. O. Box 3049, Kaiserslautern, 67653, Germany E-mail: email: wiehagen@informatik. uni-kl. de;2. TH Darmstadt, Institut für Theoreiische Informatik , Alexanderstr. 10, Darmstadt, 64283, Germany E-mail: email: zeugmann@ti.informatik.th-darmstadt.de |
| |
Abstract: | Abstract In designing learning algorithms it seems quite reasonable to construct them in a way such that all data the algorithm already has obtained are correctly and completely reflected in the hypothesis the algorithm outputs on these data. However, this approach may totally fail, i.e. it may lead to the unsolvability of the learning problem, or it may exclude any efficient solution of it. In particular, we present a natural learning problem and prove that it can be solved in polynomial time if and only if the algorithm is allowed to ignore data. |
| |
Keywords: | |
|
|