×

Separating models of learning with faulty teachers. (English) Zbl 1142.68390

Hutter, Marcus (ed.) et al., Algorithmic learning theory. 18th international conference, ALT 2007, Sendai, Japan, October 1–4, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-75224-0/pbk). Lecture Notes in Computer Science 4754. Lecture Notes in Artificial Intelligence, 94-106 (2007).
Summary: We study the power of two models of faulty teachers in Angluin’s exact learning model. The first model we consider is learning from equivalence and incomplete membership query oracles introduced by D. Angluin and D. K. Slonim [“Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle”, Mach. Learn. 14, No. 1, 7–26 (1994; Zbl 0942.68666)]. In this model, the answers to a random subset of the learner’s membership queries may be missing. The second model we consider is random persistent classification noise in membership queries introduced by S. A. Goldman, M. J. Kearns and R. E. Schapire [“Exact identification of read-once formulas using fixed points of amplification functions”, SIAM J. Comput. 22, No. 4, 705–726 (1993; Zbl 0786.68081)]. In this model, the answers to a random subset of the learner’s membership queries are flipped.
We show that the incomplete membership query oracle is strictly stronger than the membership query oracle with persistent noise under the assumption that the problem of PAC learning parities with noise is intractable.
We also show that under the standard cryptographic assumptions the incomplete membership query oracle is strictly weaker than the perfect membership query oracle. This strengthens the result of H. U. Simon [“How many missing answers can be tolerated by query learners?”, Theory Comput. Syst. 37, No. 1, 77–94 (2004; Zbl 1101.68624)] and resolves an open question of N. H. Bshouty and N. Eiron [“Learning monotone DNF from a teacher that almost does not answer membership queries”, J. Mach. Learn. Res. 3, No. 1, 49–57 (2003; Zbl 1089.68583)].
Our techniques are based on ideas from coding theory and cryptography.
For the entire collection see [Zbl 1141.68005].

MSC:

68Q32 Computational learning theory
68T05 Learning and adaptive systems in artificial intelligence
94A60 Cryptography

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angluin, D., Slonim, D.K.: Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle. Machine Learning 14, 7–26 (1994) · Zbl 0942.68666
[2] Goldman, S., Kearns, M., Schapire, R.: Exact identification of read-once formulas using fixed points of amplification functions. SIAM Journal on Computing 22, 705–726 (1993) · Zbl 0786.68081 · doi:10.1137/0222047
[3] Simon, H.U.: How many missing answers can be tolerated by query learners? Theory of Computing Systems 37, 77–94 (2004) · Zbl 1101.68624 · doi:10.1007/s00224-003-1107-5
[4] Bshouty, N.H., Eiron, N.: Learning monotone DNF from a teacher that almost does not answer membership queries. The Journal of Machine Learning Research 3, 49–57 (2003) · Zbl 1089.68583
[5] Bshouty, N.H., Owshanko, A.: Learning regular sets with an incomplete membership oracle. In: Helmbold, D., Williamson, B. (eds.) COLT 2001 and EuroCOLT 2001. LNCS (LNAI), vol. 2111, pp. 574–588. Springer, Heidelberg (2001) · Zbl 0992.68098
[6] Goldman, S.A., Mathias, H.D.: Learning -term dnf formulas with an incomplete membership oracle. In: Proceedings of COLT, pp. 77–84 (1992) · doi:10.1145/130385.130394
[7] Chen, Z.: A note on learning dnf formulas using equivalence and incomplete membership queries. In: Arikawa, S., Jantke, K.P. (eds.) AII 1994 and ALT 1994. LNCS, vol. 872, pp. 272–281. Springer, Heidelberg (1994) · Zbl 1044.68718 · doi:10.1007/3-540-58520-6_70
[8] Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum. In: Proceedings of STOC, pp. 455–464 (1991) · doi:10.1145/103418.103466
[9] Jackson, J., Shamir, E., Shwartzman, C.: Learning with queries corrupted by classification noise. In: Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems, pp. 45–53 (1997) · Zbl 0931.68060 · doi:10.1109/ISTCS.1997.595156
[10] Feldman, V.: Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions. Journal of Machine Learning Research, 1431–1460 (2007) · Zbl 1222.68096
[11] Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1993) · Zbl 0870.94021 · doi:10.1007/3-540-48329-2_24
[12] Feldman, V., Gopalan, P., Khot, S., Ponuswami, A.: New Results for Learning Noisy Parities and Halfspaces. In: Proceedings of FOCS, pp. 563–574 (2006) · doi:10.1109/FOCS.2006.51
[13] McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. DSN progress report, 42–44 (1978)
[14] Barg, A.: Complexity issues in coding theory. Electronic Colloquium on Computational Complexity (ECCC) 4 (1997) · Zbl 0929.94028
[15] Vardy, A.: Algorithmic complexity in coding theory and the minimum distance problem. In: Proceedings of STOC, pp. 92–109 (1997) · Zbl 0962.68060 · doi:10.1145/258533.258559
[16] Kearns, M.: Efficient noise-tolerant learning from statistical queries. Journal of the ACM 45, 983–1006 (1998) · Zbl 1065.68605 · doi:10.1145/293347.293351
[17] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proccedings of STOC, pp. 84–93 (2005) · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[18] Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: Proceedings of STOC, pp. 435–440. ACM Press, New York (2000) · Zbl 1296.68122
[19] Angluin, D.: Queries and concept learning. Machine Learning 2, 319–342 (1988)
[20] Angluin, D., Krikis, M., Sloan, R., Turán, G.: Malicious Omissions and Errors in Answers to Membership Queries. Machine Learning 28, 211–255 (1997) · Zbl 0881.68094 · doi:10.1023/A:1007311411259
[21] Valiant, L.: A theory of the learnable. Communications of the ACM 27, 1134–1142 (1984) · Zbl 0587.68077 · doi:10.1145/1968.1972
[22] Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM 33, 792–807 (1986) · Zbl 0596.65002 · doi:10.1145/6490.6503
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.