Supervised Learning

• Supervised machine learning uses training data in pairs of inputs (x,y)(\mathbf{x}, y)(x,y), where x∈Rd\mathbf{x}\in{\mathcal{R}}^dx∈Rd is the d-dimensional input instance and yyy is its label.
• Training data is denoted as D=\left{(\mathbf{x}_1, y_1),\dots,(\mathbf{x}_n, y_n)\right}\subseteq {\cal R}^d\times \mathcal{C}.
• The data points (xi,yi)(\mathbf{x}_i, y_i)(xi​,yi​) are drawn from some unknown distribution P(X,Y)\mathcal{P}(X, Y)P(X,Y).
• The goal is to learn a function hhh such that for a new pair (x,y)∼P(\mathbf{x}, y)\sim {\mathcal{P}}(x,y)∼P, we have h(x)=yh(\mathbf{x})=yh(x)=y with high probability (or h(x)≈yh(\mathbf{x})\approx yh(x)≈y).
• Before finding a function hhh, the type of function, such as an artificial neural network or a decision tree, must be specified.
• The set of possible functions is called the hypothesis class, encoding assumptions about the problem being solved.
• The No Free Lunch Theorem states that every successful ML algorithm must make assumptions, implying no single algorithm works for every setting.
• There are two steps in learning a hypothesis function h()h()h():
  • Select an appropriate machine learning algorithm, defining the hypothesis class H\mathcal{H}H.
  • Find the best function within this class, h∈Hh\in\mathcal{H}h∈H, which often involves optimization.
• The learning process involves finding a function hhh within the hypothesis class that makes the fewest mistakes on the training data, often choosing the "simplest" function.
• A loss function evaluates a hypothesis h∈Hh\in{\mathcal{H}}h∈H on training data, indicating how bad it is; a higher loss means worse performance and zero loss signifies perfect predictions.
• Loss is commonly normalized by the number of training samples, nnn, to represent the average loss per sample, independent of nnn.

Loss Functions

• The zero-one loss counts the number of mistakes an hypothesis function hhh makes on the training set.
• It assigns a loss of 1 for mispredicted examples and 0 for correct predictions.
• The normalized zero-one loss returns the fraction of misclassified training samples, also known as the training error.
• The zero-one loss is used to evaluate classifiers in multi-class/binary classification but is not useful to guide optimization because it is non-differentiable and non-continuous.
• Formally, the zero-one loss is: $\mathcal{L}{0/1}(h)=\frac{1}{n}\sum^n{i=1}\delta_{h(\mathbf{x}i)\ne y_i}, \mbox{ where }\delta{h(\mathbf{x}_i)\ne y_i}=\begin{cases} 1,&\mbox{ if h(xi)≠yih(\mathbf{x}_i)\ne y_ih(xi​)=yi​}\ 0,&\mbox{ o. w.} \end{cases}$.
• The squared loss function is used in regression settings and calculates the loss as (h(xi)−yi)2\left(h(\mathbf{x}_i)-y_i\right)^2(h(xi​)−yi​)2.
• Squaring ensures the loss is nonnegative and grows quadratically with the absolute mispredicted amount.
• This encourages predictions to avoid being too far off, but can give little attention to predictions very close to correct.
• If the label yyy is probabilistic according to P(y∣x)P(y|\mathbf{x})P(y∣x), the optimal prediction to minimize the squared loss is the expected value, $h(\mathbf{x})=\mathbf{E}{P(y|\mathbf{x})}[y].Formallythesquaredlossis:. Formally the squared loss is: .Formallythesquaredlossis:$\mathcal{L}{sq}(h)=\frac{1}{n}\sum^n_{i=1}(h(\mathbf{x}_i)-y_i)^2.$$
• The absolute loss function is also used in regression, with penalties of ∣h(xi)−yi∣|h(\mathbf{x}_i)-y_i|∣h(xi​)−yi​∣.
• It grows linearly with mispredictions, making it suitable for noisy data.
• If yyy is probabilistic according to P(y∣x)P(y|\mathbf{x})P(y∣x), the optimal prediction to minimize absolute loss is the median value, h(x)=MEDIANP(y∣x)[y]h(\mathbf{x})=\textrm{MEDIAN}_{P(y|\mathbf{x})}[y]h(x)=MEDIANP(y∣x)​[y].
• Formally, the absolute loss can be stated as: $$\mathcal{L}{abs}(h)=\frac{1}{n}\sum^n{i=1}|h(\mathbf{x}_i)-y_i|.$$

Minimizing Loss

• Given a loss function, the goal is to find the function hhh that minimizes the loss: h=argminh∈HL(h)h=\textrm{argmin}_{h\in{\mathcal{H}}}\mathcal{L}(h)h=argminh∈H​L(h).
• Machine learning focuses on how to efficiently perform this minimization.
• A function h(⋅)h(\cdot)h(⋅) with low loss on data DDD may not generalize well to examples not in DDD, leading to overfitting.
• An example of overfitting is a "memorizer" function: h(x)=\begin{cases} y_i,&\mbox{ if ∃(xi,yi)∈D\exists (\mathbf{x}_i, y_i)\in D∃(xi​,yi​)∈D, s. t., x=xi\mathbf{x}=\mathbf{x}_ix=xi​},\ 0,&\mbox{ o. w.} \end{cases}
• With the function above, you get 00%0 error on the training data DDD, but does horribly with samples not in DDD.
• Data splitting into Train, Validation, and Test sets must be done carefully.
• The test set should simulate a real-world test scenario, predicting the future from the past when a temporal component exists.
• If no temporal component exists, it is best to split uniformly at random, avoiding splitting alphabetically or by feature values.

Assumptions

• Every ML algorithm must make assumptions to choose a hypothesis class H\mathcal{H}H, depending on the data and encoding assumptions about the data set/distribution P\mathcal{P}P.
• There is no one perfect H\mathcal{H}H for all problems.
• Determining the value of yyy for a given x\mathbf{x}x is impossible without assumptions.
• The most common assumption of ML algorithms is that the function to be approximated is locally smooth.