Computational learning theory: Difference between revisions

Revision as of 09:39, 8 January 2004

Revision as of 09:42, 8 January 2004

Line 13:

Cryptographic - One way functions exits.

These are good surveys of COLT:

A list of important COLT papers

Surveys

• [Angluin, 92] Angluin, D. 1992. Computational learning theory: Survey and selected bibliography. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (May 1992), pp. 351--369.

* [Hau,90] D. Haussler. Probably approximately correct learning. In AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, pages 1101--1108. American Association for Artificial Intelligence, 1990.

This is a good paper on negative results:

• [KV,89] M. Kearns and L. G. Valiant. 1989. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433--444, New York. ACM.

* [DH,94] A. Dhagat and L. Hellerstein. PAC learning with irrelevant attributes. In Proceedings of the IEEE Symp. on Foundation of Computer Science, 1994. To appear.

* [Gold, 67] E. M. Gold. Language identification in the limit. Information and Control, 10:447--474, 1967.

A list of important COLT papers

* [GG96] O. Goldreich, D. Ron. On universal learning algorithms.

* [DHKV,9489] AM. DhagatKearns and L. HellersteinG. PACValiant. 1989. Cryptographic limitations on learning withboolean irrelevantformulae attributesand finite automata. In Proceedings of the IEEE21st Symp.Annual ACM Symposium on FoundationTheory of ComputerComputing, Sciencepages 433--444, 1994.New ToYork. appearACM.

* [Sch, 90] Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197--227, 1990

[Gold, 67] E. M. Gold. Language identification in the limit. Information and Control, 10:447--474, 1967.

* [Valiant, 84] L. Valiant. A Theory of the Learnable. Communications of the ACM, 27(11):1134--1142, 1984.

[GG96] O. Goldreich, D. Ron. On universal learning algorithms.

[KV,89] M. Kearns and L. G. Valiant. 1989. Cryptographic limitations on learning boolean formulae and finite automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433--444, New York. ACM.

[Sch, 90] Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197--227, 1990

[Valiant, 84] L. Valiant. A Theory of the Learnable. Communications of the ACM, 27(11):1134--1142, 1984.