Computational learning theory

What is computational learning theory?

Computational learning theory (CoLT) is a branch of AI concerned with using mathematical methods or the design applied to computer learning programs. It involves using mathematical frameworks for the purpose of quantifying learning tasks and algorithms.

It seeks to use the tools of theoretical computer science to quantify learning problems. This includes characterizing the difficulty of learning specific tasks.

Computational learning theory can be considered to be an extension of statistical learning theory or SLT for short, that makes use of formal methods for the purpose of quantifying learning algorithms.

• Computational Learning Theory (CoLT): Formal study of learning tasks.
• Statistical Learning Theory (SLT): Formal study of learning algorithms.

This division of learning tasks vs. learning algorithms is arbitrary, and in practice, there is quite a large degree of overlap between these two fields.

Computational learning theory is essentially a sub-field of artificial intelligence (AI) that focuses on studying the design and analysis of machine learning algorithms.

How important is computational learning theory?

Computational learning theory provides a formal framework in which it is possible to precisely formulate and address questions regarding the performance of different learning algorithms. Thus, careful comparisons of both the predictive power and the computational efficiency of competing learning algorithms can be made. Three key aspects that must be formalized are:

• The way in which the learner interacts with its environment,
• The definition of success in completing the learning task,
• A formal definition of efficiency of both data usage (sample complexity) and processing time (time complexity).

It is important to remember that the theoretical learning models are abstractions of real-life problems. Close connections with experimentalists are useful to help validate or modify these abstractions so that the theoretical results reflect empirical performance. The computational learning theory research has therefore close connections to machine learning research. Besides the model’s predictive capability, the computational learning theory also addresses other important features such as simplicity, robustness to variations in the learning scenario, and an ability to create insights to empirically observed phenomena.

‍

What is computational learning theory in machine learning?

These are sub-fields of machine learning that a machine learning practitioner does not need to know in great depth in order to achieve good results on a wide range of problems. Nevertheless, it is a sub-field where having a high-level understanding of some of the more prominent methods may provide insight into the broader task of learning from data.

Theoretical results of computational learning in machine learning mainly deal with a type of inductive learning called supervised learning. In supervised learning, an algorithm is given samples that are labeled in some useful way. For example, the samples might be descriptions of mushrooms, and the labels could be whether or not the mushrooms are edible. The algorithm takes these previously labeled samples and uses them to induce a classifier. This classifier is a function that assigns labels to samples, including samples that have not been seen previously by the algorithm. The goal of the supervised learning algorithm is to optimize some measure of performance such as minimizing the number of mistakes made on new samples.

In addition to performance bounds, computational learning theory studies the time complexity and feasibility of learning. In computational learning theory, a computation is considered feasible if it can be done in polynomial time.

There are two kinds of time complexity results:

• Positive results – Showing that a certain class of functions is learnable in polynomial time.
• Negative results – Showing that certain classes cannot be learned in polynomial time.

Negative results often rely on commonly believed, but yet unproven assumptions, such as:

• Computational complexity – P ≠ NP (the P versus NP problem);
• Cryptographic – One-way functions exist.

‍

What is the difference between Computational Learning Theory and Statistical Learning Theory?

While both frameworks use similar mathematical analysis, the primary difference between CoLT and SLT is their objectives. CoLT focuses on studying “learnability,” or what functions/features are necessary to make a given task learnable for an algorithm. Whereas SLT is primarily focused on studying and improving the accuracy of existing training programs.

‍

What is machine learning theory?

Machine Learning Theory, also known as Computational Learning Theory, aims to understand the fundamental principles of learning as a computational process. This field seeks to understand at a precise mathematical level what capabilities and information are fundamentally needed to learn different kinds of tasks successfully, and to understand the basic algorithmic principles involved in getting computers to learn from data and to improve performance with feedback. The goals of Computational learning theory in machine learning are that both to aid in the design of better automated learning methods and to understand fundamental issues in the learning process itself.

Machine Learning Theory draws elements from both the Theory of Computation and

Statistics and involves tasks such as:

• Creating mathematical models that capture key aspects of machine learning, in which one can analyze the inherent ease or difficulty of different types of learning problems.
• Proving guarantees for algorithms (under what conditions will they succeed, how much data and computation time is needed) and developing machine learning algorithms that probably meet desired criteria.
• Mathematically analyzing general issues, such as: “Why is Occam’s Razor a good idea?”, “When can one be confident about predictions made from limited data?”, “How much power does active participation add over passive observation for learning?”, and “What kinds of methods can learn even in the presence of large quantities of distracting information?”

‍

What is 'Probably Approximately Correct' Learning?

PAC learning, also known as Probably Approximately Correct learning is a theoretical machine learning framework created by Leslie Valiant. PAC learning aims to quantify the difficulty involved in a learning task and it might be considered to be the main sub-field of computational learning theory.

PAC learning bothers about the amount of computational effort that is needed in order to identify a hypothesis (fit model) that is a close match for the unknown target function.

What is VC Dimension

The Vapnik–Chervonenkis theory (VC Theory) is a theoretical machine learning framework created by Vladimir Vapnik and Alexey Chervonenkis.

It aims to quantify the capability of a learning algorithm and could be considered to be the main sub-field of statistical learning theory.

One of the main elements of the VC theory is the Vapnik-chervonenkis dimension (VC dimension). It quantifies the complexity of hypothesis space. It comes up with an estimation of the capability or capacity of a classification machine learning algorithm for a particular dataset (number and dimensionality of examples)