×

Can PAC learning algorithms tolerate random attribute noise? (English) Zbl 0837.68094

Summary: This paper studies the robustness of PAC learning algorithms when the instance space is \(\{0,1\}^n\), and the examples are corrupted by purely random noise affecting only the attributes (and not the labels). For uniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that PAC learns monomials for any (unknown) noise rate less than \({1 \over 2}\). Contrasting this positive result, we show that product random attribute noise, where each attribute \(i\) is flipped randomly and independently with its own probability \(p_i\), is nearly as harmful as malicious noise — no algorithm can tolerate more than a very small amount of such noise.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Angluin and P. Laird. Learning from noisy examples.Machine Learning, 2(4):343-370, 1988.
[2] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension.Journal of the ACM, 36(4):929-965, 1989. · Zbl 0697.68079 · doi:10.1145/76359.76371
[3] D. Haussler, M. Kearns, N. Littlestone, and M. K. Warmuth. Equivalence of models for polynomial learnability.Information and Computation, 95(2): 129-161, 1991. · Zbl 0743.68115 · doi:10.1016/0890-5401(91)90042-Z
[4] W. Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58(301): 13-30, 1963. · Zbl 0127.10602 · doi:10.2307/2282952
[5] M. Kearns and Ming Li. Learning in the presence of malicious errors.SIAM Journal of Computing, 22(4): 807-837, 1993. · Zbl 0789.68118 · doi:10.1137/0222052
[6] P. D. Laird.Learning from Good and Bad Data. Kluwer International Series in Engineering and Computer Science. Kluwer Academic, Boston, 1988. · Zbl 0722.68091
[7] N. Littlestone. Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow.Proceedings of the Fourth Workshop on Computational Learning Theory, 1991, pp. 147-156.
[8] J. R. Quinlan. The effect of noise on concept learning. InMachine Learning, An Artificial Intelligence Approach, Volume II, Morgan Kaufmann, Los Altos, CA, 1986, Chapter 6, pp. 149-166.
[9] G. Shackelford and D. Volper. Learning k-DNF with noise in the attributes.Proceedings of the First Workshop on Computational Learning Theory, Cambridge, MA, August 1988. Morgan Kaufmann, Los Altos, CA, 1988, pp. 97-103.
[10] R. H. Sloan. Types of noise in data for concept learning.Proceedings of the First Workshop on Computational Learning Theory, Cambridge, MA, August 1988. Morgan Kaufmann, Los Altos, CA, 1988, pp. 91-96.
[11] L. G. Valiant. A theory of the learnable.Communications of the ACM, 27(11):1134-1142, 1984. · Zbl 0587.68077 · doi:10.1145/1968.1972
[12] L. G. Valiant. Learning disjunctions of conjunctions. InProceedings IJCAI 85. Morgan Kaufmann, Los Altos, CA, 1985, pp. 560-566.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.