Learning algorithm

Definition

The term learning algorithm is used to refer to the part of a machine learning problem that specifically involves optimization of the (possibly regularized) cost function using the training data. Learning algorithms may proceed as iterative algorithms, that start with an initial guess for the parameter vector and then refune that guess, or as non-iterative algorithms, that directly proceed to solve for the parameter vector.

Evaluation of learning algorithms

There are two ways of judging the success of a learning algorithm:

• Measurement of the cost function on the training data: This is a narrow view of the learning algorithm: the smaller the cost function on the training data, the better the learning algorithm.
• Measurement of the cost function on separate data (cross-validation or test data): This is a broader view of the learning algorithm, namely, it measures how well the algorithm does on data that was withheld from it.

These two different views of how the learning algorithm should be measured relate with different views of the relationship between the learning algorithm and the regularization choice made to avoid overfitting. One view is that the problems are cleanly separable: regularization (through the addition of a regularization term to the cost function) serves the goal of addressing overfitting, and the learning algorithm's goal is simply to minimize the regularized cost function on the training set. The alternate view is that the regularization method and the learning algorithm are intricately intertwined, and the learning algorithm is responsible not just for doing well with the regularized problem on the training data but also for doing well with the original problem on the cross-validation or test data.