What is Computational machine learning

Computational Machine Learning and learning an approximately correct hypothesis

Contents of Computational Learning

• Introduction

• Probably learning an approximately correct hypothesis

• Sample complexity for finite hypothesis space

• Sample complexity for infinite hypothesis space

• The mistake-bound model of learning

Computational Learning Theory: 

Computational learning theory is a field of machine learning that studies the mathematical properties and limitations of learning algorithms.

Introduction

Computational learning theory is a field of study that aims to understand the mathematical properties of learning algorithms. The goal is to develop a theoretical framework for understanding the limits and capabilities of machine learning algorithms.

Probably learning an approximately correct hypothesis

Probably approximately correct (PAC) learning is a framework for learning that provides a probabilistic guarantee of the accuracy of the learned hypothesis. A hypothesis is said to be PAC-learnable if there exists an algorithm that can learn the hypothesis with high probability and bounded error using a finite amount of training data.

Sample complexity for finite hypothesis space

The sample complexity of a learning algorithm is the minimum number of training examples required to PAC-learn a hypothesis with a given level of confidence and accuracy. The sample complexity depends on the complexity of the hypothesis space and the distribution of the training data.

For finite hypothesis spaces, the sample complexity is finite and can be calculated using the VC dimension, which is a measure of the complexity of the hypothesis space. The VC dimension represents the maximum number of points that can be shattered by the hypothesis space, i.e., the maximum number of different labelling points that can be realized by the hypothesis space.

Sample complexity for infinite hypothesis space

For infinite hypothesis spaces, the sample complexity is usually infinite but can be bounded by restricting the hypothesis space or by assuming some additional structure on the data distribution.

The mistake-bound model of learning

The mistake-bound model of learning is another framework for analyzing the performance of learning algorithms. In this model, the learning algorithm is allowed to make mistakes during training, and the goal is to bind the number of mistakes made by the algorithm as a function of the size of the training set and the complexity of the hypothesis space.

In summary, computational learning theory provides a framework for understanding the mathematical properties of learning algorithms. PAC learning and the mistake-bound model are two important frameworks for analyzing the performance of learning algorithms, and sample complexity is a key concept in both frameworks.

Previous(Bayesian learning)

                                                                    Continue to (Genetic Algorithms)