Editing Supervised learning (section)

==How supervised learning algorithms work==

Given a set of <math>N</math> training examples of the form <math>\{(x_1, y_1), ..., (x_N,\; y_N)\}</math> such that <math>x_i</math> is the [[feature vector]] of the <math>i</math>-th example and <math>y_i</math> is its label (i.e., class), a learning algorithm seeks a function <math>g: X \to Y</math>, where <math>X</math> is the input space and <math>Y</math> is the output space. The function <math>g</math> is an element of some space of possible functions <math>G</math>, usually called the ''hypothesis space''. It is sometimes convenient to represent <math>g</math> using a [[scoring function]] <math>f: X \times Y \to \mathbb{R}</math> such that <math>g</math> is defined as returning the <math>y</math> value that gives the highest score: <math>g(x) = \underset{y}{\arg\max} \; f(x,y)</math>. Let <math>F</math> denote the space of scoring functions.

Although <math>G</math> and <math>F</math> can be any space of functions, many learning algorithms are probabilistic models where <math>g</math> takes the form of a [[conditional probability]] model <math>g(x) = \underset{y}{\arg\max} \; P(y|x)</math>, or <math>f</math> takes the form of a [[joint probability]] model <math>f(x,y) = P(x,y)</math>. For example, [[Naive Bayes classifier|naive Bayes]] and [[linear discriminant analysis]] are joint probability models, whereas [[logistic regression]] is a conditional probability model.

There are two basic approaches to choosing <math>f</math> or <math>g</math>: [[empirical risk minimization]] and [[structural risk minimization]].<ref>Vapnik, V. N. [https://books.google.com/books?id=EqgACAAAQBAJ&q=%22empirical+risk+minimization%22+OR+%22structural+risk+minimization%22 The Nature of Statistical Learning Theory] (2nd Ed.), Springer Verlag, 2000.</ref> Empirical risk minimization seeks the function that best fits the training data. Structural risk minimization includes a ''penalty function'' that controls the bias/variance tradeoff.

In both cases, it is assumed that the training set consists of a sample of [[independent and identically-distributed random variables|independent and identically distributed pairs]], <math>(x_i, \;y_i)</math>. In order to measure how well a function fits the training data, a [[loss function]] <math>L: Y \times Y \to
\mathbb{R}^{\ge 0}</math> is defined. For training example <math>(x_i,\;y_i)</math>, the loss of predicting the value <math>\hat{y}</math> is <math>L(y_i,\hat{y})</math>.

The ''risk'' <math>R(g)</math> of function <math>g</math> is defined as the expected loss of <math>g</math>. This can be estimated from the training data as

:<math>R_{emp}(g) = \frac{1}{N} \sum_i L(y_i, g(x_i))</math>.

===Empirical risk minimization===
{{Main|Empirical risk minimization}}

In empirical risk minimization, the supervised learning algorithm seeks the function <math>g</math> that minimizes <math>R(g)</math>. Hence, a supervised learning algorithm can be constructed by applying an [[Optimization (mathematics)|optimization algorithm]] to find <math>g</math>.

When <math>g</math> is a conditional probability distribution <math>P(y|x)</math> and the loss function is the negative log likelihood: <math>L(y, \hat{y}) = -\log P(y | x)</math>, then empirical risk minimization is equivalent to [[Maximum likelihood|maximum likelihood estimation]].

When <math>G</math> contains many candidate functions or the training set is not sufficiently large, empirical risk minimization leads to high variance and poor generalization. The learning algorithm is able to memorize the training examples without generalizing well (overfitting).

===Structural risk minimization===

[[Structural risk minimization]] seeks to prevent overfitting by incorporating a [[Regularization (mathematics)|regularization penalty]] into the optimization. The regularization penalty can be viewed as implementing a form of [[Occam's razor]] that prefers simpler functions over more complex ones.

A wide variety of penalties have been employed that correspond to different definitions of complexity. For example, consider the case where the function <math>g</math> is a linear function of the form

:<math> g(x) = \sum_{j=1}^d \beta_j x_j</math>.

A popular regularization penalty is <math>\sum_j \beta_j^2</math>, which is the squared [[Euclidean norm]] of the weights, also known as the <math>L_2</math> norm. Other norms include the <math>L_1</math> norm, <math>\sum_j |\beta_j|</math>, and the [[L0 "norm"|<math>L_0</math> "norm"]], which is the number of non-zero <math>\beta_j</math>s. The penalty will be denoted by <math>C(g)</math>.

The supervised learning optimization problem is to find the function <math>g</math> that minimizes

:<math> J(g) = R_{emp}(g) + \lambda C(g).</math>

The parameter <math>\lambda</math> controls the bias-variance tradeoff. When <math>\lambda = 0</math>, this gives empirical risk minimization with low bias and high variance. When <math>\lambda</math> is large, the learning algorithm will have high bias and low variance. The value of <math>\lambda</math> can be chosen empirically via [[cross-validation (statistics)| cross-validation]].

The complexity penalty has a Bayesian interpretation as the negative log prior probability of <math>g</math>, <math>-\log P(g)</math>, in which case <math>J(g)</math> is the [[posterior probability]] of <math>g</math>.