Entropy for developers
Tags: datascience, machinelearning, programming
Published: 2020-12-20 17:27:29

[Entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)) is a mathematical concept which quantifies the amount of information in an observation.

This makes entropy useful to you, as a programmer, whenever you are working with data. When working with large datasets, entropy-based heuristics can tell you where to focus your attention to get the most bang for your buck.

At [Bugout](https://bugout.dev), we have a tagging system for knowledge bases very similar to the tags that [DEV](https://dev.to) uses for their posts. We calculate the informative power of each tag using entropy. We use these calculations to help our users categorize their knowledge and navigate their knowledge bases more efficiently. Entropy helps us power these user experiences with simple calculations we do in our database as opposed to using complicated machine learning models.

Entropy and related information theoretic notions are very useful in machine learning, as well.

[Decision tree algorithms tend to use entropy](https://towardsdatascience.com/entropy-how-decision-trees-make-decisions-2946b9c18c8) to learn effective branching structures.

When training neural networks, entropy is usually incorporated into the training process via a loss function. [Cross entropy](https://datascience.stackexchange.com/questions/9302/the-cross-entropy-error-function-in-neural-networks), for example, is a commonly used loss function when training classifiers. A good understand of entropy not only helps you understand the behavior of such models, it also helps you tune your models more effectively.

If you are curious to learn more about entropy and start using it to improve your data-related work, this post will get you started.

Towards the end of the post, I also describe some instances during my career where the concept of entropy has come in handy.

*This post assumes a basic understanding of probability and some familiarity with mathematical notation.*

### Definition

Say you have a probability distribution with outcomes {% katex inline %}1, 2, \ldots, n{% endkatex %}, each of which can occur with probabilities {% katex inline %}p_1, p_2, \ldots, p_n{% endkatex %}.

The entropy of this probability distribution is:
{% katex %}
H(p_1, \ldots, p_n) := -\sum_{j=1}^n p_j log(p_j)
{% endkatex %}

### Properties

Much more important than the definition are the properties that it embodies.

First, **entropy increases with the number of (equally likely) outcomes**:
{%katex%}H\left(\frac{1}{n}, \ldots, \frac{1}{n}\right) < H\left(\frac{1}{n+1},\ldots,\frac{1}{n+1}\right){%endkatex%}

{% details Example: Coins and dice %}
{%katex%}H(1/2, 1/2) < H(1/6, 1/6, 1/6, 1/6, 1/6, 1/6),{%endkatex%}
which says that the roll of a fair die contains more information than the flip of a fair coin.
{% enddetails %}

Second, **entropy is maximized when outcomes are equally likely**:
{%katex%}
H(p_1, \ldots, p_n) < H\left(\frac{1}{n}, \ldots, \frac{1}{n}\right)
{%endkatex%}
for any probability distribution {%katex inline%}(p_1, \ldots, p_n){%endkatex%} for which some {%katex inline%}p_j \neq 1/n{%endkatex%}.

This feeds into our intuition that the **amount of information in an event is the amount of uncertainty it resolves for us**.

{% details Example: Fair coins and biased coins %}
{%katex%}
H(1/4, 3/4) < H(1/2, 1/2),
{%endkatex%}
which says that we get much less information when flipping a coin which is biased to land on heads only 25% of the time than when flipping a coin.
{% enddetails %}

### Units

One of the choices you have to make when calculating the entropy of a probability distribution is the base you will choose for the logarithm.

This choice doesn't usually matter much. This is because changing the base only changes the calculation by a constant factor. Since you usually use entropy to make comparisons between probability distributions, multiplying all calculations by a constant factor doesn't affect how they are placed relative to each other.

Consider the calculation of
{%katex%}
H(1/2, 1/2) = -\left[\frac{1}{2}log\left(\frac{1}{2}\right) + \frac{1}{2}log\left(\frac{1}{2}\right)\right] = -log\left(\frac{1}{2}\right)
{%endkatex%}

If you take the logarithm to the base of 2, you get {%katex%}H(1/2, 1/2) = 1{%endkatex%}

If you generalize this calculation to powers of 2, you get:
{%katex%}H(1/2^n, \ldots, 1/2^n) = n{%endkatex%}

For any probability distribution with equally likely outcomes, using a base of 2 on the logarithm, entropy counts the minimum number of bits required to represent the possible outcomes from the distribution.

Claude Shannon, father of information theory (pictured above), made this connection more explicit:
{% wikipedia https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem %}

The important takeaway here is that you can think of entropy as answering the question, **"What is the smallest number of bits I need to represent a sample from this probability distribution?"**

### Real-world applications

I list a few examples from my own career where knowing about entropy was extremely useful.

#### Bugout tags

[Bugout](https://bugout.dev) is a knowledge base that accepts knowledge from a variety of sources (Slack, GitHub, IDEs, terminals), and makes it discoverable to users wherever they work.

This is what it looks like when someone adds knowledge to their knowledge base from Slack:
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/18yvkd20sq9kg50ya2tv.png)

We place no restriction on the number of tags a user can associate with an entry in their knowledge base. Instead, we rely on intelligently suggesting tags to users when they create content and when they are searching for knowledge.

The first iteration of our tag suggestions were based on how frequently tags were used in a given knowledge base. Tags which appeared more commonly were higher up in the list of suggestions.

The `engineering` tag shows up on close to 80% of the entries in our team knowledge base. It certainly doesn't help too much when searching through a knowledge base. As developers repeatedly accept `engineering` as a suggested tag when adding content into their knowledge base, the informative power of the `engineering` tag just decreases as its frequency of use increases.

We have found entropy to be a much better quantification of the importance of a tag than frequency. It delivers a much better user experience especially for users navigating a knowledge base.

For each tag in a knowledge base, we think of each entry as an observation of whether or not the tag appears. With {%katex inline%}p_{tag}{%endkatex%} as the proportion of entries having the given tag, the entropy of the tag is {%katex inline%}H(p_{tag}, 1-p_{tag}){%endkatex%}.

The best thing about this is that it's easy to calculate in our Postgres database. Here is an example of an (unoptimized) entropy query for tags in Bugout knowledge bases (internally, knowledge bases are represented as `journals`):
```sql
select tag,
    journal_id,
    num_entries_with_tag,
    num_entries,
    num_entries_with_tag / num_entries as proportion_entries,
    case num_entries_with_tag/num_entries
        when 0 then 0
        when 1 then 0
        else -(num_entries_with_tag / num_entries) * ln(num_entries_with_tag/num_entries) - ((num_entries - num_entries_with_tag) / num_entries) * ln((num_entries - num_entries_with_tag)/num_entries)
    end
    as entropy
from (
        select journal_entry_tags.tag as tag,
            journals.id as journal_id,
            cast (count(journal_entries.id) as float) as num_entries_with_tag,
            cast (
                (
                    select count(*)
                    from journal_entries
                    where journal_entries.journal_id = journals.id
                ) as float
            ) as num_entries
        from journal_entries
            inner join journal_entry_tags on journal_entries.id = journal_entry_tags.journal_entry_id
            inner join journals on journals.id = journal_entries.journal_id
        group by journals.id,
            journal_entry_tags.tag
    ) as intermediate_stats;
```

#### Outperforming Amazon, Google, and Microsoft APIs on image classification tasks

I used to run the AI team at [Doc.ai](https://doc.ai). At the time, we built image models that provided our users and their medical providers with valuable insights about their physical and mental health.

Being serious about user privacy, especially when dealing with sensitive health data, we built our classification models to run on our users' mobile phones. This meant we couldn't just plug into AWS Rekognition, the Google ML APIs or Microsoft Cognitive Services, as that would leak user health information to Amazon, Google, and Microsoft.

We set out to train models which were competitive with the major cloud APIs by collecting a LOT of relevant images (10s of millions) and boostrapping our model with the classifications returned by the cloud APIs.

At the end of the day, we were able to outperform the cloud APIs in the many cases because of how we used entropy to our advantage.

You can think of image classification results as a probability vector over the possible classes represented in an image or in a segment of that image. We calculated the entropy of the classification results that the cloud APIs returned for each of the images in our dataset. This calculation quantified the amount of uncertainty their models had about their results. This uncertainty decomposed into two components:
1. The quality of the cloud API model in question
2. The quality of the image for the given classification task

For a given cloud API, we could take the entropy (largely) as a measure of image quality. Thus, filtering on entropy allowed us to cheaply build very high quality training and evaluation datasets without contracting any kind of labeling service (which would have been exorbitantly expensive at the scale of data we were working with).

Entropy heuristics were also very important in helping us understand the hyperparameter spaces of the models we trained. For each model, during our hyperparameter tuning phase, we would run ~30 experiments concurrently, and it cost us thousands of dollars a week. As a tiny startup, it was important that we be efficient about hyperparameter tuning. Simple entropy and cross entropy calculations over our dataset and classifications performed by various model checkpoints helped us narrow in on high-performing hyperparameters very quickly.

My team at Doc.ai released a lot of this work as the open source Tensor/IO framework (which also allows you to train models across many user devices using [federated learning](https://en.wikipedia.org/wiki/Federated_learning)):
{% github https://github.com/doc-ai/tensorio %}

- - -

Happy to answer any questions and continue the discussion. Just leave a comment below. :)