Computational Learning Theory

"Computational Learning Theory (COLT) is a reasearch field devoted to studying the design and analysis of algorithms for making predictions about the future based on past experiences. The emphasis in COLT is on rigorous mathematical analysis. As a field with roots in theoretical computer science, COLT is largely concerned with computational and data efficiency. Much of the work in COLT can be traced to Valiant's seminal paper on "A theory of the learnable" (1984) as well as Gold's "Language identification in the limit" (1967). The annual Conference on Computational Learning Theory began in 1988; the European Conference on Computational Learning Theory and the Workshop on Algorithmic Learning Theory were formed soon after. COLT has strongly encouraged interaction with other fields that work on problems of prediction such as applied machine learning, statistics, information theory, pattern recognition and statistical physics, as well as other areas of computer science such as artificial intelligence, complexity theory and cryptography."
Freund and Schapire

Wikipedia: Computational learning theory

Books

ANTHONY, M. and N. BIGGS, 1997. Computational Learning Theory. [Cited by 268]
KEARNS, Michael J. and Umesh V. VAZIRANI, 1994. An Introduction to Computational Learning Theory. [Cited by 410]

Web Site

COLT: Computational Learning Theory

See also "Proceedings of the (nth) Annual Workshop on Computational Learning Theory"

Bibliography

ABE, N., M.K. WARMUTH and J. TAKEUCHI, 1991. Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence. … the fourth annual workshop on Computational learning theory. [Cited by 20] (1.23/year)
AMARI, S., N. FUJITA and S. SHINOMOTO, 1992. Four types of learning curves. Neural Computation. [Cited by 51] (3.35/year)
ANGLUIN, D., 1987. Learning regular sets from queries and counterexamples. Information and Computation. [Cited by 470] (23.23/year)
ANGLUIN, D., 1992. Computational learning theory: survey and selected bibliography. Proceedings of the twenty-fourth annual ACM symposium on …. [Cited by 96] (6.30/year)
ANTHONY, M., N. BIGGS and J. SHAWE-TAYLOR, 1990. The learnability of formal concepts. … the third annual workshop on Computational learning theory. [Cited by 23] (1.33/year)
ANTHONY, M.H.G., 1992. [BOOK] Computational Learning Theory: An Introduction. books.google.com. [Cited by 321] (21.07/year)
BARRERA, J., E.R. DOUGHERTY and N.S. TOMITA, 1996. [BOOK] … by Design of Statistically Optimal Operators in the Context of Computational Learning Theory. spie.org. [Cited by 35] (3.12/year)
BARTO, A.G., S.J. BRADTKE and S.P. SINGH, 1995. Learning to act using real-time dynamic programming. Artificial Intelligence. [Cited by 499] (40.78/year)
BAUM, E.B., 1990. On learning a union of half spaces. Journal of Complexity. [Cited by 33] (1.91/year)
BAUM, E.B., 1990. The perceptron algorithm is fast for nonmalicious distributions. Neural Computation. [Cited by 34] (1.97/year)
BAUM, E.B. and D. HAUSSLER, 1990. What size net gives valid generalization?. Neural Computation. [Cited by 693] (40.21/year)
BENEDEK, G.M. and A. ITAI, 1988. Learnability by fixed distributions. … the first annual workshop on Computational learning theory. [Cited by 78] (4.06/year)
BENVENISTE, A., P. PRIOURET and M. M?TIVIER, 1990. Adaptive algorithms and stochastic approximations - all 2 versions ». Springer-Verlag New York, Inc. New York, NY, USA. [Cited by 417] (24.19/year)
BERTSEKAS, D.P., 1987. Dynamic programming: deterministic and stochastic models. Prentice-Hall, Inc. Upper Saddle River, NJ, USA. [Cited by 708] (34.99/year)
BERTSEKAS, D.P., 1995. Dynamic Programming and Optimal Control - all 5 versions ». Athena Scientific. [Cited by 998] (81.57/year)
BERTSEKAS, D.P. and J.N. TSITSIKLIS, 1996. Neuro-Dynamic Programming - all 5 versions ». Athena Scientific. [Cited by 1452] (129.23/year)
BLUM, A., 1994. Relevant examples and relevant features: Thoughts from computational learning. AAAI Fall Symposium on Relevance. [Cited by 18] (1.36/year)
BLUM, A. and M. SINGH, 1990. Learning functions of k terms. … the third annual workshop on Computational learning theory. [Cited by 29] (1.68/year)
BLUM, A. and R.L. RIVEST, 1988. Training a 3-node neural network is NP-complete. … the first annual workshop on Computational learning theory. [Cited by 245] (12.74/year)
BLUM, M. and S. MICALI, 1984. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing. [Cited by 609] (26.21/year)
BLUMER, A., et al., 1987. Occam's razor. Information Processing Letters. [Cited by 339] (16.75/year)
CASE, J. and C. LYNES, 1982. Machine Inductive Inference and Language Identification. Proceedings of the 9th Colloquium on Automata, Languages and …. [Cited by 68] (2.69/year)
CLAUSEN, M., et al., 1991. On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. Theoretical Computer Science. [Cited by 44] (2.71/year)
CSISZAR, I. and J.G. KORNER, 1982. Information Theory: Coding Theorems for Discrete Memoryless Systems. Academic Press, Inc. Orlando, FL, USA. [Cited by 733] (29.05/year)
DALEY, R., et al., 1991. Relations between probabilistic and team one-shot learners (extended abstract). … the fourth annual workshop on Computational learning theory. [Cited by 23] (1.42/year)
DE, L., 1997. Logical settings for concept-learning. Artificial Intelligence. [Cited by 90] (8.79/year)
DEAN, T. and K. KANAZAWA, 1989. A model for reasoning about persistence and causation. Computational Intelligence. [Cited by 381] (20.89/year)
EHRENFEUCHT, A., D. HAUSSLER and M. KEARNS, 1989. Learning decision trees from random examples needed for learning. Information and Computation. [Cited by 77] (4.22/year)
EISENBERG, B. and R.L. RIVEST, 1990. On the sample complexity of pac-learning using random and chosen examples. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA. [Cited by 21] (1.22/year)
FREIVALDS, R., 1991. Inductive Inference of Recursive Functions: Qualitative Theory. Lecture Notes In Computer Science; Vol. 502. [Cited by 31] (1.91/year)
FREUND, Y., 1995. Boosting a weak learning algorithm by majority. Information and Computation. [Cited by 461] (37.68/year)
FULK, M.A., 1990. Prudence and other conditions on formal language learning. Information and Computation. [Cited by 49] (2.84/year)
FURST, M.L., J.C. JACKSON and S.W. SMITH, 1991. Improved learning of AC 0 functions. … the fourth annual workshop on Computational learning theory. [Cited by 32] (1.97/year)
GASARCH, W.I. and M.G. PLESZKOCH, 1989. Learning via queries to an oracle. … the second annual workshop on Computational learning theory. [Cited by 20] (1.10/year)
GEMAN, S., E. BIENENSTOCK and R. DOURSAT, 1992. Neural networks and the bias/variance dilemma. Neural Computation. [Cited by 1138] (74.69/year)
GILES, C.L., et al., 1992. Learning and extracting finite state automata with second-order recurrent neural networks. Neural Computation. [Cited by 238] (15.62/year)
GOLDBERG, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning - all 8 versions ». Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA. [Cited by 19220] (1,054.00/year)
GURVITS, L., 2001. A note on a scale-sensitive dimension of linear bounded functionals in Banach spaces. Theoretical Computer Science. [Cited by 39] (6.25/year)
HAGERUP, T. and C. R?B, 1990. A guided tour of Chernoff bounds. Information Processing Letters. [Cited by 274] (15.90/year)
HANCOCK, T. and L. HELLERSTEIN, 1991. Learning read-once formulas over fields and extended bases. … the fourth annual workshop on Computational learning theory. [Cited by 22] (1.36/year)
HANCOCK, T. and Y. MANSOUR, 1991. Learning monotone ku DNF formulas on product distributions. … the fourth annual workshop on Computational learning theory. [Cited by 27] (1.66/year)
HANCOCK, T.R., 1991. Learning 2u DNF formulas and ku decision trees. … the fourth annual workshop on Computational learning theory. [Cited by 29] (1.79/year)
HANCOCK, T.R., 1990. Identifying ?-formula decision trees with queries. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA. [Cited by 24] (1.39/year)
HARRISON, M.A.A. and M.A. HARRISON, 1978. Introduction to Formal Language Theory - all 2 versions ». Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA. [Cited by 560] (19.15/year)
HAUSSLER, D., 1988. Quantifying inductive bias: AI learning algorithms and Valiant's learning framework. Artificial Intelligence. [Cited by 274] (14.24/year)
HAUSSLER, D., 1992. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation. [Cited by 400] (26.25/year)
HAUSSLER, D., 1995. Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension. Journal of Combinatorial Theory Series A. [Cited by 93] (7.60/year)
HELMBOLD, D.P. and P.M. LONG, 1991. Tracking drifting concepts using random examples. … the fourth annual workshop on Computational learning theory. [Cited by 21] (1.29/year)
HORNIK, K., 1991. Approximation capabilities of multilayer feedforward networks. Neural Networks. [Cited by 573] (35.29/year)
H?STAD, J., 1987. Computational limitations of small-depth circuits - all 3 versions ». MIT Press Cambridge, MA, USA. [Cited by 177] (8.75/year)
IBARRA, O.H. and T. JIANG, 1988. Learning regular languages from counterexamples. … the first annual workshop on Computational learning theory. [Cited by 25] (1.30/year)
JAIN, S. and A. SHARMA, 1990. Finite learning by a “team”. … the third annual workshop on Computational learning theory. [Cited by 17] (0.99/year)
JANTKE, K.P., 1991. Monotonic and non-monotonic inductive inference. New Generation Computing. [Cited by 25] (1.54/year)
KEARNS, M. and L. PITT, 1989. A polynomial-time algorithm for learning k-variable pattern languages from examples. … the second annual workshop on Computational learning theory. [Cited by 34] (1.86/year)
KEARNS, M.J. and U.V. VAZIRANI, 1994. [BOOK] An Introduction to Computational Learning Theory. books.google.com. [Cited by 557] (42.08/year)
KLIVANS, A.R. and R.A. SERVEDIO, 2004. Learning DNF in time 2 ? (n 1/3). Journal of Computer and System Sciences. [Cited by 28] (8.65/year)
KOHONEN, T., 1989. Self-organization and associative memory - all 6 versions ». Springer-Verlag New York, Inc. New York, NY, USA. [Cited by 4739] (259.88/year)
LAIRD, P.D., 1988. Learning from good and bad data - all 2 versions ». Kluwer Academic Publishers Norwell, MA, USA. [Cited by 73] (3.80/year)
LANGE, S. and R. WIEHAGEN, 1991. Polynomial-time inference of arbitrary pattern languages. New Generation Computing. [Cited by 59] (3.63/year)
LAVRAC, N. and S. DZEROSKI, 1993. Inductive Logic Programming: Techniques and Applications - all 2 versions ». Routledge New York, NY, 10001. [Cited by 457] (32.10/year)
LITTLE, R.J.A. and D.B. RUBIN, 1986. Statistical analysis with missing data - all 8 versions ». John Wiley & Sons, Inc. New York, NY, USA. [Cited by 4184] (197.03/year)
LITTLESTONE, N., 1991. Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow. … the fourth annual workshop on Computational learning theory. [Cited by 92] (5.67/year)
LITTLESTONE, N., 1990. Mistake bounds and logarithmic linear-threshold learning algorithms. [Cited by 118] (6.85/year)
LITTLESTONE, N., 1989. From on-line to batch learning. … the second annual workshop on Computational learning theory. [Cited by 56] (3.07/year)
LLOYD, J.W., 1987. Foundations of logic programming - all 7 versions ». Springer-Verlag New York, Inc. New York, NY, USA. [Cited by 3150] (155.67/year)
MAASS, W., 1991. On-line learning with an oblivious environment and the power of randomization. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA. [Cited by 20] (1.23/year)
MAASS, W. and G. TUR?N, 1994. How fast can a threshold gate learn?. MIT Press Cambridge, MA, USA. [Cited by 33] (2.49/year)
MACHTEY, M. and P. YOUNG, 1978. An Introduction to the General Theory of Algorithms - all 3 versions ». Elsevier Science Inc. New York, NY, USA. [Cited by 150] (5.13/year)
MOTOKI, T., T. SHINOHARA and K. WRIGHT, 1991. The correct definition of finite elasticity: corrigendum to identification of unions. … the fourth annual workshop on Computational learning theory. [Cited by 30] (1.85/year)
NEWELL, A., 1990. Unified theories of cognition - all 2 versions ». Harvard University Press Cambridge, MA, USA. [Cited by 2070] (120.10/year)
OSHERSON, D.N., M. STOB and S. WEINSTEIN, 1986. Systems that learn: an introduction to learning theory for cognitive and computer scientists - all 2 versions ». MIT Press Cambridge, MA, USA. [Cited by 123] (5.79/year)
PAPADIMITRIOU, C.H. and M. YANNAKAKIS, 1991. Shortest paths without a map. Theoretical Computer Science. [Cited by 190] (11.70/year)
PITT, L., 1989. Inductive Inference, DFAs, and Computational Complexity. Springer-Verlag London, UK. [Cited by 108] (5.92/year)
PITT, L. and C.H. SMITH, 1988. Probability and plurality for aggregations of learning machines. Information and Computation. [Cited by 54] (2.81/year)
PITT, L. and M.K. WARMUTH, 1990. Prediction-preserving reducibility. Journal of Computer and System Sciences. [Cited by 88] (5.11/year)
QUINLAN, J.R. and R.L. RIVEST, 1989. Inferring decision trees using the minimum description length principle. Information and Computation. [Cited by 392] (21.50/year)
RAGHAVAN, V. and S.R. SCHACH, 1990. Learning switch configurations. … the third annual workshop on Computational learning theory. [Cited by 17] (0.99/year)
RENEGAR, J., 1992. On the computational complexity and geometry of the first-order theory of the reals. Par I: …. Journal of Symbolic Computation. [Cited by 304] (19.95/year)
RISSANEN, J., 1989. Stochastic Complexity in Statistical Inquiry Theory - all 2 versions ». World Scientific Publishing Co., Inc. River Edge, NJ, USA. [Cited by 1226] (67.23/year)
RIVEST, R.L. and R. SLOAN, 1988. Learning complicated concepts reliably and usefully. … the first annual workshop on Computational learning theory. [Cited by 27] (1.40/year)
ROGERS, H., 1987. Theory of recursive functions and effective computability - all 3 versions ». MIT Press Cambridge, MA, USA. [Cited by 1551] (76.65/year)
SACKS, G.E., 1990. Higher recursion theory - all 2 versions ». Springer-Verlag New York, Inc. New York, NY, USA. [Cited by 105] (6.09/year)
SAKAKIBARA, Y., 1991. On learning from queries and counterexamples in the presence of noise. Information Processing Letters. [Cited by 21] (1.29/year)
SAMUEL, A.L., 1995. Some studies in machine learning using the game of checkers. Computers & thought table of contents. [Cited by 589] (48.14/year)
SCHAPIRE, R.E., 1990. Pattern languages are not learnable. … the third annual workshop on Computational learning theory. [Cited by 27] (1.57/year)
SCHRIJVER, A., 1986. Theory of linear and integer programming - all 5 versions ». John Wiley & Sons, Inc. New York, NY, USA. [Cited by 2282] (107.46/year)
SCHWEFEL, H.P., 1981. Numerical Optimization of Computer Models. John Wiley & Sons, Inc. New York, NY, USA. [Cited by 911] (34.72/year)
SHACKELFORD, G. and D. VOLPER, 1988. Learning k-DNF with noise in the attributes. … the first annual workshop on Computational learning theory. [Cited by 34] (1.77/year)
SHAFER, G. and J. PEARL, 1990. Readings in uncertain reasoning. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA. [Cited by 176] (10.21/year)
SHAPIRO, E.Y., 1983. Algorithmic Program DeBugging - all 4 versions ». MIT Press Cambridge, MA, USA. [Cited by 543] (22.41/year)
SLOAN, R., 1988. Types of noise in data for concept learning. … the first annual workshop on Computational learning theory. [Cited by 37] (1.92/year)
VALIANT, L.G., 1994. Circuits of the mind. Oxford University Press, Inc. New York, NY, USA. [Cited by 96] (7.25/year)
VAN, J.H., 1998. Introduction to Coding Theory - all 6 versions ». Springer-Verlag New York, Inc. Secaucus, NJ, USA. [Cited by 479] (51.87/year)
VAPNIK, V.N., 2000. [BOOK] The Nature of Statistical Learning Theory. books.google.com. [Cited by 8157] (1,127.38/year)
VAPNIK, V.N., 1998. Statistical learning theory. Wiley New York. [Cited by 6126] (663.32/year)
VELAUTHAPILLAI, M., 1989. Inductive inference with bounded number of mind changes. … the second annual workshop on Computational learning theory. [Cited by 17] (0.93/year)
WEGENER, I., 1987. The complexity of Boolean functions - all 7 versions ». John Wiley & Sons, Inc. New York, NY, USA. [Cited by 516] (25.50/year)
WIDROW, B. and S.D. STEARNS, 1985. Adaptive signal processing - all 5 versions ». Prentice-Hall, Inc. Upper Saddle River, NJ, USA. [Cited by 2768] (124.49/year)
WRIGHT, K., 1989. Identification of unions of languages drawn from an identifiable class. … the second annual workshop on Computational learning theory. [Cited by 61] (3.35/year)
ZEUGMANN, T. and S. LANGE, 1995. A Guided Tour Across the Boundaries of Learning Recursive Languages. Lecture Notes In Computer Science. [Cited by 65] (5.31/year)