Entropy in machine learning — applications, examples, alternatives

Entropy is a machine learning term borrowed from thermodynamics that measures randomness or disorder in any system. Why measure disorder? Consider a real-life system like your office desk. The number of ways you can organize the items on your desk is limited, but the number of ways to mess it up is unlimited! Mathematics uses entropy to measure this chaos — or, more specifically, the probability of chaos.

Claude E. Shannon introduced the concept of entropy to data science in his famous 1948 paper, the Mathematical Theory of Communication. He defined entropy as the expected surprise of a random event. For example, let’s say you purchase a lottery ticket. If you don’t win the lottery, you’ll not be surprised because the chance of that happening is very low. But if you did win the lottery — you would be AMAZED. Entropy can give you a mathematical number on how surprised you’ll be!

In other words, entropy measures the unexpectedness in any system. The higher the entropy, the more randomness in your system. This article explores the mathematical basis behind entropy and its usage in machine learning. We also look at scenarios where entropy may not be the best fit and suggest alternatives.

What is entropy in machine learning?What is entropy in machine learning?

Entropy is an important concept in supervised machine-learning techniques. Supervised learning models (algorithms) analyze large pre-labeled data sets and use the information learned to label new data. For example, you may label many financial transactions as fraudulent or genuine and train the model. Then, when you give the model a new transaction not found in its dataset, the model can accurately predict if it is fraudulent. The labels (like “fraudulent” and “genuine”) are also called class labels.

Entropy is the quantitative assessment of the unpredictability of the distribution of your class labels. You can use it to understand how evenly or unevenly your data points are distributed across different classes. The higher the entropy, the harder it will be for your supervised machine-learning algorithm to make accurate predictions.

Let’s look at a simple example to understand the concept further. Consider a dataset of customers who either purchased a product or didn’t. The entropy is high if there is a near-equal distribution of customers in both classes. Predicting whether the next customer will buy the item is hard — the probability is nearly equal.

However, if most customers purchase the product, entropy drops. The data is more organized, and it is easier to predict the outcome for the next customer.

Source

Mathematical formula for entropyMathematical formula for entropy

Now that we have theoretically understood the concept, let’s look at the math behind it. In data science, you can calculate the entropy for every class label. It relates to the data distribution for that label.

Remember that entropy is a measure of surprise. It calculates your surprise if the machine learning algorithm classifies a new data point with that specific label. For example, going back to your customers, if most customers purchased the product, and your machine learning algorithm classified the next customer as “purchaser, ” you’ll be less surprised (low entropy). But if it classified the customer as “not purchasing, ” you’ll be more surprised (high entropy).

Entropy is thus inversely proportional to the probability of an event occurring. Shannon bases the formula on the logarithmic scale. For any data factor (individual label x):
$$Entropy(x) = p(x)·log_2 p(x),$$ where $p(x)$ represents the probability of that classification outcome.

Why is the log multiplied by the probability?Why is the log multiplied by the probability?

When $p(x)=1$, $log_2 p(x)=0$ and when $p(x) = 0.5$, $log_2 p(x)=1$.

Since probability is a value between 0 and 1, entropy should also be between 0 and 1. But as the value $p(x)$ moves to 0, the value of $log_2 p(x)$ becomes greater than 1. (Cells with values 1.7 and 3.3 in the table below. Table shows approximate values.)

However, we want it to move to 0 as well. If there is no possibility of an outcome, there is no possibility of surprise for that outcome. Multiplying by p (x) evens that out. (last column of the table)

Net entropyNet entropy

You can calculate the total entropy in your data by summating individual values.
$$H(x) = \sum_{x=0}^{n}p(x)·log_2 p(x)$$ Machine learning algorithms often try to minimize net entropy to make the best possible prediction for new data.

Net entropy distribution curve. Source

Entropy in machine learning modelsEntropy in machine learning models

Entropy helps machine learning models make accurate decisions about unknown data. It gives a mathematical basis for the model to classify data. The models can reduce entropy to mathematically co-relate different data points.

Let’s dive deep into decision trees to understand the practical applications better. They are the most common algorithms designed around the entropy concept.

Decision tree overviewDecision tree overview

Decision trees combine the if-else programming paradigm with entropy to efficiently classify data. They split the dataset into smaller and smaller subsets based on entropy conditions.

Key components of a decision tree:

1. Root node: The topmost node, representing the entire dataset, where the first split or decision occurs.

2. Internal nodes: These nodes represent the decision points where the dataset is further split based on feature values.

3. Branches: These are the possible outcomes of a decision at an internal node, leading to other nodes.

4. Leaf nodes: The terminal nodes representing the final output or classification.

Use of entropy in decision treesUse of entropy in decision trees

The tree tries to split the data at every node based on specific attributes so the classification is as neat as possible. The lower the entropy, the neater the split. The algorithm splits the data at every internal node based on the feature that minimizes entropy and maximizes information gain.

Information gain is computed as follows:
$$IG(n)=1 - \sum_{i=1}^{J} p^2 (i)$$ Information gain represents the change or reduction in entropy. It compares the parent node’s entropy with the average entropy of all child nodes. High information gain indicates more reduction in entropy. Low information gain indicates less reduction in entropy.

Example of entropy in machine learningExample of entropy in machine learning

Consider media algorithms trying to predict the movie genre by analyzing the movie poster. Initially, entropy is high as there is a mix of objects and landscapes in the images. But you can reduce entropy by zooming in on the central image object. A fighting animal indicates fantasy, a human holding sports equipment indicates a sports movie, and so on.

You train your decision tree on movie posters pre-labeled with their genre. The algorithm self-learns, trying to identify correlations between the image data and its corresponding label.

The first split is on the image at the center of the poster, as it reduces the entropy the most. The next level split categorizes the central image into human, animal, or object. The level after that tries to identify what the central image is doing. At every level, the algorithm tries to reduce the chaos or uncertainty that entropy creates and reach certainty or a definite answer to the question — “What is the movie genre based on its poster?”

More applications of entropy in machine learningMore applications of entropy in machine learning

Beyond decision trees and information gain, entropy is the basis for several other important measures that help quantify relationships between data, probability distributions, or models.

Mutual informationMutual information

Mutual information mathematically quantifies the relationship or dependency between two random variables. It measures how knowing one variable reduces the uncertainty (entropy) about the other.

For two variables, x and y:

$$I(x;y)=H(x)-H(x|y)$$

$H(x)$ is the entropy of x, and $H(x|y)$ represents the remaining uncertainty about x after knowing y. $H(x|y)$ is also called conditional entropy. If knowing y completely determines x, the conditional entropy is zero because there’s no remaining uncertainty in x.

Consider a scenario where you’re trying to predict a student’s exam result x (pass or fail) based on their class attendance y. If y is greater than 90%, the student always passes. In this case, the conditional entropy will be close to zero because knowing y reduces nearly all the uncertainty about x.

A common use case of mutual information is in evaluating the quality of a clustering solution. Clustering algorithms try to find patterns in a dataset without any pre-labeling. You can check their output using mutual information. Data points within a cluster should have high mutual information, while the inter-cluster data should have low mutual information.

Relative entropyRelative entropy

Relative entropy, or Kullback-Leibler (KL) divergence, measures the difference between two probability distributions of the same variable.