In a supervised learning problem, there will always be a dataset, defined as a finite set of real vectors with m features each:

Considering that our approach is always probabilistic, we need to consider each X as drawn from a statistical multivariate distribution D. For our purposes, it's also useful to add a very important condition upon the whole dataset X: we expect all samples to be independent and identically distributed (i.i.d). This means all variables belong to the same distribution D, and considering an arbitrary subset of m values, it happens that:

The corresponding output values can be both numerical-continuous or categorical. In the first case, the process is called regression, while in the second, it is called classification. Examples of numerical outputs are:

Categorical examples are:

We define generic regressor, a vector...

A parametric model can be split into two parts: a static structure and a dynamic set of parameters. The former is determined by choice of a specific algorithm and is normally immutable (except in the cases when the model provides some re-modeling functionalities), while the latter is the objective of our optimization. Considering n unbounded parameters, they generate an n-dimensional space (imposing bounds results in a sub-space without relevant changes in our discussion) where each point, together with the immutable part of the estimator function, represents a learning hypothesis H (associated with a specific set of parameters):

The goal of a parametric learning process is to find the best hypothesis whose corresponding prediction error is minimum and the residual generalization ability is enough to avoid overfitting. In the following figure, there's an...

Imagine that you need to design a spam-filtering algorithm starting from this initial (over-simplistic) classification based on two parameters:

We have collected 200 email messages (X) (for simplicity, we consider p₁ and p₂ mutually exclusive) and we need to find a couple of probabilistic hypotheses (expressed in terms of p₁ and p₂), to determine:

We also assume the conditional independence of both terms (it means that h_p1 and h_p2 contribute conjunctly to spam in the same way as they were alone).

For example, we could think about rules (hypotheses) like: "If there are more than five blacklisted words" or "If the message is less than 20 characters in...

A machine learning problem can also be analyzed in terms of information transfer or exchange. Our dataset is composed of n features, which are considered independent (for simplicity, even if it's often a realistic assumption) drawn from n different statistical distributions. Therefore, there are n probability density functions p_i(x) which must be approximated through other n q_i(x) functions. In any machine learning task, it's very important to understand how two corresponding distributions diverge and what is the amount of information we lose when approximating the original dataset.

The most useful measure is called entropy:

 

This value is proportional to the uncertainty of X and it's measured in bits (if the logarithm has another base, this unit can change too). For many purposes, a high entropy is preferable...

• Russel S., Norvig P., Artificial Intelligence: A Modern Approach, Pearson
• Valiant L., A Theory of the Learnable, Communications of the ACM, Vol. 27, No. 11 (Nov. 1984)
• Hastie T., Tibshirani R., Friedman J., The Elements of Statistical Learning: Data Mining, Inference and, Prediction, Springer
• Aleksandrov A.D., Kolmogorov A.N, Lavrent'ev M.A., Mathematics: Its contents, Methods, and Meaning, Courier Corporation