Introduction to Computational Learning Theory in AI and CoLT Models

Introduction

In the field of Artificial Intelligence, Computer scientists have been practising several experiments to learn how to construct computer programs that can deliver human-like performances, since the late 1950s. 

 

Machine Learning is all about teaching computers to learn and comprehend activities that need native human intelligence and then doing them with the assistance of artificial intelligence. Computers are also given the capacity to perform and better themselves with each performance, learning and changing as they go. 

 

Inductive reasoning scholars conducted the earliest theoretical investigations of machine learning, beginning with Gold's formulation of the first formal definition of learning. 

 

In Gold's approach, the learner is given a series of instances and is asked to make a series of guesses about the underlying rule (idea) until the sequence converges at some finite point to a single estimate that correctly labels the unknown rule. 

 

Pattern recognition is another closely related area. Much of the theory created by learning theory academics to assess the quantity of data required to learn directly adapts results from statistics and pattern recognition disciplines.

 

 It is critical for researchers to identify what is “learnable” and what is not from the start. Recently, artificial neural network research has sparked interest in the development of systems capable of executing tasks that are difficult to define algorithmically. 

 

This is where the idea of Computational Learning comes into play. In this article, we are going to discuss Computational Learning Theory and different models that are based on this theory. 

 

(Similar read: Theory of Computation)

 

 

Computational Learning Theory

 

Computational Learning Theory (CoLT) is a branch of Artificial Intelligence study that focuses with formal studies on the design of computer programmes that can learn. Essentially, it evaluates which issues may be learned using mathematical frameworks and comprehends the theoretical background of deep learning algorithms while increasing accuracy.

 

Computational Learning theory is used in many fields such as statistics, calculus and geometry, Information theory, programming optimizations and many others. It is very similar to Statistical Learning Theory (SLT) as they both use Mathematical Analysis. 

 

The basic difference between the two is that CoLT is basically concerned with the “learnability” of the machines and the necessary steps that are required to take in order to make a given task comprehensible for an algorithm. Whereas, SLT is more focused on studying and improving the accuracy of already existing programs. 

 

Computational Learning Theory is concerned with Supervised Learning, which is a type of inductive learning  in the field of Machine Learning that maps an input to an output on the basis of existing input-output pairs. It provides a formal framework for accurately formulating and answering questions about the performance of various learning algorithms, allowing for thorough comparisons of both the predictive capacity and the computational efficiency of alternative learning algorithms. 

 

According to Machine Learning Mastery, some of the questioned that might be faced by a practitioner while studying about Computational Learning Theory are:

 

• How can we tell if a model is a decent approximation to the goal function?

• How can we determine if we have a good answer at the local or global level?

• What type of hypothesis space should be employed?

• What can we do to avoid overfitting?

• How many examples of data are required?

 

Some of the models that require Computational Learning Theory are PAC Learning Model, Online Learning Model and Weak Learning Model. Let us discuss briefly about them.

 

(Also Read: Top 8 Machine learning Models)

 

 

Computation Learning Theory Models

 

1. PAC Learning Model:

 

PAC Learning or Probably Approximately Correct Learning is a framework in the theory of machine learning that aims to measure the complexity of a learning problem and is probably the most advanced sub-field of computational learning theory. It was a seminal work done by Leslie Valiant. 

 

In PAC models, examples are created according to an arbitrary probability distribution D, and the aim of a neural network is to classify any further unclassified instances with high accuracy (with regard to the distribution D). 

 

To find information about any unknown target function, the learner is given access to different examples of the functions that are drawn randomly according to some unknown target distribution D.

 

In general, a PAC algorithm may be performed on supplied data and the inaccuracy of the resulting hypothesis objectively measured. An exception is when attempting to utilise statistical query methods empirically, because most of these algorithms use the input for more than just establishing the necessary sample size. 

 

(Must read: What is Computational Science?)

 

VC-Dimension

 

As we have seen, PAC learning is the theoretical model of machine learning problems, whereas VC dimension theory or Vapnik-Chervonenkis dimension theory is the theoretical study on Machine Learning Algorithms. It is a machine learning framework developed by Vladimir Vapnik and Alexey Chervonenkis. 

 

It is a measure of the capability of a collection of functions that can be learnt by a statistical binary classification algorithm in terms of complexity, expressive power, richness, or flexibility. The cardinality of the biggest set of points that the method can shatter is specified.

 

In the context of a dataset, shatter or a shattered set implies that points in the feature space may be picked or divided from one another using hypotheses in the space such that the labels of samples in the distinct groups are right.

 

The VC dimension measures the complexity of a hypothesis space, for example, the models that can be fit given a representation and learning method. The amount of unique possibilities in a hypothesis space (space of models that might be fit) and how the space may be traversed are two ways to assess the complexity of a hypothesis space (space of models that could be fit). 

 

The VC dimension is an ingenious method that instead counts the number of cases from the target issue that can be distinguished by hypotheses in the space.

 

 

2. Online Learning Model:

 

The online learning model, also known as the mistake-bounded learning model, is a form of learning model in which the worst-case scenario is considered for all environments. There is a known conception class for each situation, and the target concept is chosen from there. 

 

The target functions and the sequence of presentation for all instances are then chosen by an opponent with limitless computer power and knowledge of the learner's algorithm. 

 

Throughout the learning session, the student gets unlabeled examples. The learner knows the right value after each learning session and can utilise the input to enhance its hypothesis. The objective of this model is to use any effective learning technique to reduce the worst-case amount of errors.

 

(Suggested reading: Hypothesis Testing)

 

 

3. Weak Learning:

 

The PAC learning model requires the learner to generate numerous hypotheses that are arbitrarily near to the goal idea. Although simple methods that are generally right are easy to find, it is extremely difficult to find a single hypothesis that is highly accurate. 

 

A Weak Learning Algorithm is a sort of training data that generates an output hypothesis that outperforms random guessing. The overall process of transforming a weak learner into a PAC learner is known as hypothesis boosting. 

 

Since Schapire's initial study, many boosting techniques have been presented. AdaBoost is an Algorithm that claims to utilise empirical formulae. The key to driving the weak learner to provide hypotheses that can be merged to produce a highly accurate hypothesis is to generate diverse distributions on which the weak learner is tested.

 

(Recommended Read: Implementing Gradient Boosting Algorithm Using Python)

 

Conclusion

 

Computational Learning Theory in the field of artificial intelligence has improved the learning capability of machines. It has helped a lot in the advancement of machine learning. In this article we have learned about Computational Learning Theory and its minor difference with Statistical Learning Theory. 

 

We have also discussed PAC Learning Model, VC dimension, Online Learning Model and Weak Learning Model. With these models, the best case for any algorithm can be determined.