What is the difference between a learning algorithm and a hypothesis?

Question

What's the distinction between a learning algorithm $A$ and a hypothesis $f$?

I'm looking for a few concrete examples, if possible.

For example, would the decision tree and random forest be considered two different learning algorithms? Would a shallow neural network (that ends up learning a linear function) and a linear regression model, both of which use gradient descent to learn parameters, be considered different learning algorithms?

Anyway, from what I understand, one way to vary the hypothesis $f$ would be to change the parameter values, maybe even the hyper-parameter values of, say, a decision tree. Are there other ways of varying $f$? And how can we vary $A$?

Answer 1

In computational learning theory, a learning algorithm (or learner) $A$ is an algorithm that chooses a hypothesis (which is a function) $h: \mathcal{X} \rightarrow \mathcal{Y}$, where $\mathcal{X}$ is the input space and $\mathcal{Y}$ is the target space, from the hypothesis space $H$.

For example, consider the task of image classification (e.g. MNIST). You can train, with gradient descent, a neural network to classify the images. In this case, gradient descent is the learner $A$, the space of all possible neural networks that gradient descent considers is the hypothesis space $H$ (so each combination of parameters of the neural network represents a specific hypothesis), $\mathcal{X}$ is the space of images that you want to classify, $\mathcal{Y}$ is the space of all possible classes and the final trained neural network is the hypothesis $h$ chosen by the learner $A$.

For example, would the decision tree and random forest be considered two different learning algorithms?

The decision tree and random forest are not learning algorithms. A specific decision tree or random forest is a hypothesis (i.e. function of the form as defined above).

In the context of decision trees, the ID3 algorithm (a decision tree algorithm that can be used to construct the decision tree, i.e. the hypothesis), is an example of a learning algorithm (aka learner).

The space of all trees that the learner considers is the hypothesis space/class.

Would a shallow neural network (that ends up learning a linear function) and a linear regression model, both of which use gradient descent to learn parameters, be considered different learning algorithms?

The same can be said here. A specific neural network or linear regression model (i.e. a line) corresponds to a specific hypothesis. The set of all neural networks (or lines, in the case of linear regression) that you consider corresponds to the hypothesis class.

Anyway, from what I understand, one way to vary the hypothesis $f$ would be to change the parameter values, maybe even the hyper-parameter values of, say, a decision tree.

If you consider a neural network (or decision tree) model, with $N$ parameters $\mathbf{\theta} = [\theta_i, \dots \theta_N]$, then a specific combination of these parameters corresponds to a specific hypothesis. If you change the values of these parameters, you also automatically change the hypothesis. If you change the hyperparameters (such as the number of neurons in a specific layer), however, you will be changing the hypothesis class, so the set of hypotheses that you consider.

Are there other ways of varying $f$?

Off the top of my head, only by changing the parameters, you change the hypothesis.

And how can we vary $A$?

Let's consider gradient descent as the learning algorithm. In this case, to change the learner, you could change, for example, the learning rate.

Answer 2

A hypothesis is a statement that suggests an as yet unproven explanation of a relationship between two or more phenomena that you intend to test. An agronomist thinks that more nitrogen on canola will always increase the crop output $$Harvest = f(N)$$, or a meteorologist thinks he can show that the path of a hurricane over the ocean can be determined by knowledge of the sea temperature and the wind speed at an altitude of 1000 feet one minute before. $$D(t,0) = f(T(t-1,1000),S(t-1,1000)$$ Both hypotheses are pegs on which later steps are based; testing follows with a conclusion whether the hypothesis can be rejected or not.

Changing a hypothesis can be simply adding or subtracting arguments to the function or changing the nature of the relationship such as the acceleration of the wind as opposed to its velocity.

A "learning" algorithm describes how the parameters of a numeric model are changed in accordance with the delta rule, that is what the learning rate is and whether momentum is to be applied.

Random Forest and Decision Tree are "classification" algorithms. They are clearly stepwise processes that proceed towards the goal of a model, but they start by specifying the shape that the model will take and place boundaries on what values the parameters may take.

Both learning and classification algorithms specify a priori what shape the model will take and by doing so limit its relevance to particular problems.