A noise model on learning sets of strings

ABSTRACT

In this paper, we introduce a new noise model on learning sets of strings in the framework of PAC learning and consider the effect of the noise on learning. The instance domain is the set &Sgr;n of strings over a finite alphabet &Sgr;, and the examples are corrupted by purely random errors affecting only the instances (and not the labels). We consider three types of errors on instances, called EDIT operation errors. EDIT operations consist of “insertion”, “deletion”, and “change” of a symbol in a string. We call such a noise where the examples are corrupted by random errors of EDIT operations on instances the EDIT noise. First we show general upper bounds on the EDIT noise rate that a learning algorithm of taking the strategy of minimizing disagreements can tolerate and a learning algorithm can tolerate. Next we present an efficient algorithm that can learn a class of decision lists over the attributes “a string w contains a pattern p?” from noisy examples under some restriction on the EDIT noise rate.

REFERENCES

• AL88: Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
• GS91: Sally A. Goldman and Robert H. Sloan. The difficulty of random attribute noise. Technical Report WUCS-91-29, Department of Computer Science, Washington University, 1991.
• KL88: Michael Kearns , Ming Li, Learning in the presence of malicious errors, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.267-280, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62238]
• Li90: Ming Li. Towards a DNA sequencing theory. In Proceedings of 31st IEEE Symposium on Foundations of Computer Science, pages 125-134. IEEE Computer Society Press, 1990.
• LV88: Gad M. Landau , Uzi Vishkin, Fast string matching with k-differences, Journal of Computer and System Sciences, v.37 n.1, p.63-78, August 1988 [doi>10.1016/0022-0000(88)90045-1]
• Riv87: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• Slo88: Robert Sloan, Types of noise in data for concept learning, Proceedings of the first annual workshop on Computational learning theory, p.91-96, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• Ukk85: Esko Ukkonen, Algorithms for approximate string matching, Information and Control, v.64 n.1-3, p.100-118, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80046-2]
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• Val85: Leslie G. Valiant. Learning disjunctions of conjunctions. In Proceedings of 9ih International Joint Conference on Artificial Intelligence, pages 560-566. Morgan Kaufmann, 1985.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification