# Occam razor vs. machine learning

*Whenever possible, substitute constructions out of known entities for inferences to unknown entities*

Occam's razor (Russell's version)

If Russell was studying Machine Learning our days, he’d probably throw out all of the textbooks.

The reason is that ML introduces too many terms with subtle or no difference. It’s hard understand the scale of the problem without a good example.

You can ask your ML-experienced friends how many of the **entities**
are there in this list of **terms**?

- mean squared error (MSE)
- logistic loss
- cross-entropy
- Kullback-Leibler (KL) divergence
- logarithmic scoring rule
- quadratic scoring rule
- Brier scoring rule
- Gini splitting criterion (Gini impurity) for decision tree (not Gini coefficient)
- entropy splitting criterion for decision tree
- binomial / multinomial deviance
- ordinary least squares
- mutual information
- logarithmic loss
- information gain
- softmax classifier

Not to name some trivial things like sum of squared errors
is the same **entity** as MSE.

The answer is: 2.

This is enough to say that terminology used in ML today is very unfriendly and requires some minimization.

Group 1 contains different synonyms of MSE:

- mean squared error (MSE)
- quadratic scoring rule
- Brier scoring rule
- Gini splitting criterion (Gini impurity)
- ordinary least squares

It is not obvious that **Gini is a particular version of MSE splitting**, but I demonstrate this below.

Group 2 contains different versions of cross-entropy:

- logistic loss
- cross-entropy
- Kullback-Leibler (KL) divergence
- logarithmic scoring rule
- entropy splitting criterion for decision tree
- binomial / multinomial deviance
- mutual information
- logarithmic loss
- information gain
- softmax classifier

Entropy is cross-entropy of distribution with itself. KL-divergence is difference of cross-entropy and entropy.

There are many other ways to define the same concept in particular cases: softmax classifier corresponds to optimization of log-likelihood for Bernoulli distribution (in case of two classes) or categorical distribution (in case of more than two classes).

Non-trivial thing here: **entropy splitting criterion is the same as logloss minimization**.

## Why Gini splitting = MSE?

Simplest case is binary classification: $y_i = 0 \text{ or } 1$. Let’s first revisit MSE splitting criterion.

Suppose we split space in leafs $ \text{leaf} = 1, 2,\dots , L$.

In this case MSE is equal to:

Penalty for a single leaf depends only on the number of samples $n_{leaf, 0}, n_{leaf, 1}$ from classes 0 and 1:

So, while building decision tree, we greedily optimize the following global function (but each split optimizes only two terms in the sum):

Let’s also introduce $n_\text{leaf} = n_{leaf, 0} + n_{leaf, 1} $ – number of all samples in the leaf and portions of class 1 in leaf: $ p_{leaf, 1} = \dfrac{n_{leaf, 1}}{n_{leaf}} $. Using the new terms:

… which is nothing but Gini impurity summed over leaves. It is easy to notice that in case of classification with multiple classes we need to first perform one-hot encoding and then minimize MSE to get the same splitting rule as provided by Gini.

## Why Entropy splitting = LogLoss minimization?

Let’s start from writing down the LogLoss for the decision tree:

(where $y_{i,c}$ is 1 if event $i$ belongs to class $c$ and 0 otherwise; $p_{i,c}$ is predicted probability to belong to class $c$).

When selecting optimal predictions in the leaf, we optimize:

Easy to prove that optimal point is $p_{leaf, c} = \dfrac{n_{leaf, c}}{n_{leaf}} $

… and we got entropy impurity.

# See also

- my post about ROC curve with tons of definitions for binary classification problem
- Statistics vs. Machine Learning, fight!