blog.gnarlyware.com

KL Divergence Online Demo

The intersection of two current events have born fruit:

I’m reading Christopher Bishop’s legendary book: “Pattern Recognition and Machine Learning”, (freely available as PDF from the book’s website!)
I recently discovered Shiny for R, which allows building interactive web apps in R.

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 $p(x)$ , which we’re trying to approximate with probability distribution $q(x)$ , then

$\text{KL}(p||q) = - \int p(x) \ln \frac{q(x)}{p(x)} dx$

can informally be interpreted as the amount of information being lost by approximating $p$ with $q$ . 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 $\text{KL}(p||q)$ (ie, making $q$ “as similar” to $p$ 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 $\text{KL}(p||q) = \text{KL}(q||p)$ ? Always? Never?
When is $\text{KL}(p||q) = 0$ ?
Let $r(x) = \mathcal{N}(0, 1)$ and $s(x) = \mathcal{N}(0, 2)$ . Which is larger: $\text{KL}(r||s) or \text{KL}(s||r)$ ? Why?
Is $\text{KL}(p||q)$ 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 $\mathcal{C}$ exists for $X$ (the set containing the elements to be covered), containing a maximum of $k$ sets

Showing the problem is in NP

Let $\mathcal{C} = \{S_1, S_2, \ldots, S_n\}$ be the certificate. We assume that each $S \in \mathcal{C}$ uniquely covers at least one $x \in X$ , so:

(1) $\begin{align*} |\mathcal{C}| &\leq |X|\\ \forall S \in \mathcal{C} : |S| &\leq |X| \end{align*}$

This gives us that we can verify that $n \leq k$ and that $\mathcal{C}$ covers $X$ in $\mathcal{O}(|X|^2)$ , 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) $\begin{equation*} \textsc{Vertex-Cover} \leq_\text{P} \textsc{Set-Cover} \end{equation*}$

Reduction

The vertex cover of an undirected graph $G = (V, E)$ is a subset $V' \subseteq V$ , such that each $e \in E$ is adjacent to at least one $v' \in V$ [1]. Its decision version is to determine whether a vertex cover of at most size $k$ exists for $G$ .

We can reduce any instance of decision-vertex-cover for $G = (V, E)$ to an instance of decision-set-cover by letting $X = E$ and letting the family of sets $\mathcal{F} = {S_v | v \in V\ \land \text{deg}(v) > 0}$ , such that $S_v$ contains all edges in $E$ adjacent to $v$ . We can perform this reduction in $\mathcal{O}(|E| + |V|)$ , which is in polynomial time.

Example of vertex cover (shaded nodes are in V’)

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

(3) $\begin{align*}\mathcal{F} = \{S_{v_1} &= \{e_1, e_3\}, \\S_{v_3} &= \{e_2, e_5\},\\S_{v_4} &= \{e_3, e_6\},\\S_{v_6} &= \{e_4, e_7, e_8\}\}\end{align*}$

We will now prove for any vertex cover $V'$ for $G$ and a set cover $\mathcal{C}$ for sets $X$ and $\mathcal{F}$ constructed in accordance with the reduction above:

(4) $\begin{equation*} \exists V'\subseteq V : |V'| \leq k \iff \exists \mathcal{C} \subseteq \mathcal{F} : |\mathcal{C}| \leq k \end{equation*}$

Since $X = E$ , and we know $V'$ is a vertex cover for $G = (V, E)$ , we can find $\mathcal{C}$ for $(X, \mathcal{F})$ by selecting from $\mathcal{F}$ all sets corresponding to $v' \in V'$ .

Similarily, if $\mathcal{C}$ exists, by the way we defined the reduction, we know it covers $X = E$ . This means We can find $V'$ by taking the vertices corresponding to $S_v \in \mathcal{C}$ .

Due to the 1:1 correspondence of vertices in $V'$ and sets in $\mathcal{C}$ : $|V'| = |\mathcal{C}|~\blacksquare$

[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 $S$ of numbers, determine whether $S$ can be partitioned into $A$ and $\overline{A} = S - A$ , such that:

(1) $\begin{equation*}\sum_{x \in A} x = \sum_{x \in \overline{A}} x\end{equation*}$

Showing the problem is in NP

Let $(A, \overline{A})$ 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) $\begin{equation*}\textsc{Subset-Sum} \leq_\text{P} \textsc{Set-Partition}\end{equation*}$

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 $m \times n$ matrix $A$ and an integer $m$ -vector $b$ , determine whether there exists an integer $n$ -vector $x$ with elements in $\{0, 1\}$ , such that:

(1) $\begin{equation*}Ax \le b\end{equation*}$

How to show a problem is NP-complete

This is the first post in a series of posts where I will attempt to give visual, easy to understand, proofs^* of NP-completeness for a selection of decision problems. In this post, I will give a “template” which can be used (and will be used for the proofs I post).