## Mutual Information – Categorical Variable Example

Mutual information and its cousin, the Uncertainty coefficient (Theil’s U) are useful tools from Information Theory for discovering dependencies between variables that are not necessary described by a linear relationship.

I’m short on time, and plenty of good material already exists on the subject: see Section 1.6 in “Pattern Recognition and Machine Learning” by Bishop, freely available as PDF online. What I find missing are some trivial examples to help build intuition. That’s what I will contribute here, using categorical variables.

We’ll use (and expand) the following running example: Consider a population of persons labelled , and let be the favourite dish of person , with the following distribution:

### Information contained in an observation

Let be the information measured in bits (if the natural logarithm is used instead, the unit is called “nats”) contained in observing , where the probability of is given by . Bishop refers to this quantity as “the surprise” of observing assuming it comes from the distribution described by .

Now, in our example, observing a persons favorite dish is pizza carries bits of information, whereas observing a persons favorite dish is barbecue carries bit of information (less surprise).

### Entropy of a random variable

What we then call entropy: , is the expected amount of information in the observation of a random variable:

For our example:

The information theory interpretation of this would be that is the (theoretical) minimum number of bits required per , to encode a string of successive, independent ‘s.

### Conditional entropy

If two random variables, and , are dependent (i.e. they are somehow related), then knowing something about will provide us additional information about (and vice versa), decreasing the information required (entropy) to describe . This can be expressed as conditional entropy:

can then be interpreted as the expected number of additional bits required to encode given that the value of is already known. Let’s expand our example, and let represent the nationality of person . Let the joint distribution be as follows:

Note that and are not independent here – for example, if is Italian, is expected to have a higher preference for Pizza (stereotypical, I know), than the population as a whole.

Then for our example:

Clearly in our example, meaning that if we already know the value of , less information (fewer bits) is required to describe . If we would do the same exercise for , we’d see that — This is an effect of them not being independent. They carry some amount of mutual information.

### Mutual Information

Mutual information can be defined by KL-divergence as:

Note that if and were independent, then with KL-divergence (and mutual information) being 0. An intuitive way to think about it is as a measure of dissimilarty between the distributions and .

Manipulating this algebraically, we can however also write in more familiar terms:

Thus, in our running example, bits.

To be expanded a bit when I get more time…

## KL Divergence Online Demo

The intersection of two current events have born fruit:

To try out Shiny, I created an interactive visualization for Kullback-Leibler divergence (or KL Divergence). Right now, it only supports two univariate Gaussians, which should be sufficient to build some intuition.

If you like it, let me know! If it turns out to be popular, I might add more features, or create similar visualizations for other concepts!

### What is KL Divergence? What am I seeing?

Consider an unknown probability distribution , which we’re trying to approximate with probability distribution , then

can informally be interpreted as the amount of information being lost by approximating with . As you might imagine, this has several applications in Machine Learning. A recurring pattern is to fit parameters to a model by minimizing an approximation of (ie, making “as similar” to as possible). This blog post elaborates in a fun and informative way. If you have never heard about KL divergence before, Bishop provides a more formal (but still easy to understand) introduction in Section 1.6 of PRML.

### Suggested exercises with the interactive plot

Using the visualization tool, find out (or verify) the answer to the following questions:

• Is ? Always? Never?
• When is ?
• Let and . Which is larger: ? Why?
• Is ever negative? When, or why not?

## Proving the set-covering problem is NP-complete (using reduction from the vertex-cover problem)

In this post, we will prove that the decision version of the set-covering problem is NP-complete, using a reduction from the vertex covering problem (which is NP-complete). This is Exercise 35.3-2 in CLRS3[1]. We will follow the template given in an earlier post.

## Problem statement

We will use the definition for a set cover given on page 1118 in CLRS3[1], also given on Wikipedia. Since we’re concerned with the decision version, we seek to answer whether a set cover exists for (the set containing the elements to be covered), containing a maximum of sets

## Showing the problem is in NP

Let be the certificate. We assume that each uniquely covers at least one , so:

(1)

This gives us that we can verify that and that covers in , which proves the problem is in NP.

## Showing the problem is NP-hard

We will show that the decision version of the set-covering problem is NP-hard by showing:

(2)

### Reduction

The vertex cover of an undirected graph is a subset , such that each is adjacent to at least one [1]. Its decision version is to determine whether a vertex cover of at most size exists for .

We can reduce any instance of decision-vertex-cover for to an instance of decision-set-cover by letting and letting the family of sets , such that contains all edges in adjacent to . We can perform this reduction in , which is in polynomial time.

The example image above shows a vertex cover of size. Making the reduction for this example gives:

(3)

We will now prove for any vertex cover for and a set cover for sets and constructed in accordance with the reduction above:

(4)

Since , and we know is a vertex cover for , we can find for by selecting from all sets corresponding to .

Similarily, if exists, by the way we defined the reduction, we know it covers . This means We can find by taking the vertices corresponding to .

Due to the 1:1 correspondence of vertices in and sets in :

1. [1]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press, 2009.

## Proving set-partition problem is NP complete (using reduction from subset sum)

In this post, we will prove that the set-partition problem is NP-complete using a reduction from the subset sum problem (which is NP-complete[1]). This is Exercise 34.5-5 in CLRS3[1]. We will follow the template given in an earlier post.

## Problem statement

Given a set of numbers, determine whether can be partitioned into and , such that:

(1)

## Showing the problem is in NP

Let be the certificate. We can verify the certificate in linear time by summing the elements in each set, and comparing it

## Showing the problem is NP-hard

We will show that the set-partition problem is NP-hard by showing:

(2)

Continue reading “Proving set-partition problem is NP complete (using reduction from subset sum)”

## Proving 0-1 integer programming is NP-complete (using reduction from 3-CNF-SAT)

In this post, we will prove that 0-1 integer programming is NP-complete using a reduction from 3-CNF-SAT (which is NP-complete[1]). We will follow the template given in an earlier post.

### Problem statement

The decision problem for 0-1 integer programming is formulated as follows[2]:

Given an integer matrix and an integer -vector , determine whether there exists an integer -vector with elements in , such that:

(1)

Continue reading “Proving 0-1 integer programming is NP-complete (using reduction from 3-CNF-SAT)”