Mathematical definition · 01 / 05

Setting and entropy

The dataset, the two spaces, the Shannon entropy and the formal meaning of a low-entropy isolation.

For dummiesPlain-language view: everyday words, no equations. The full version is one click away.

In plain words

We start with a table of examples. Each example has a list of measurements (its features) and a label (its class). The logic replicant redraws every example as a point on a new map, and the question is what makes a map good.

Entropy is a measure of how mixed the classes are. For the whole table it is a fixed number that no redrawing can change. What redrawing can change is where the classes sit on the map. A good map has regions where almost every point belongs to one class, so the mixing inside that region is close to zero. The paper calls such a region a low-entropy isolation. If the map has clear isolations, classifying a new example is trivial: place it on the map and read the class of the region it falls in.

Setting

Let \(\Omega\) be a dataset whose instances \(\boldsymbol{x}\in X\subset\mathbb{R}^F\), \(F\in\mathbb{N}^+\), carry one of \(|C|\) output classes, and let \(p_c\colon\mathbb{R}^F\mapsto[0,1]\) be the probability distribution of class \(c\), with \(p_c\) also denoting the fraction of instances of \(\Omega\) classified as \(c\). The classification strategy is to transform \(\Omega\) from its original space of features \(X\) into a space \(Q\subset\mathbb{R}^D\), \(D\in\mathbb{N}^+\), where it is easier to classify.

Entropy

The Shannon entropy of the dataset is

\[H(\Omega)=-\sum_{c\in C}p_c\log_2(p_c)\](1)

It provides information about the problem as a whole, not about the space \(Q\) that can facilitate classification. Even after a transformation, the entropy of all the isolated areas considered together (the whole \(\Omega\)) is still \(H(\Omega)\). The aim is a space \(Q\) with isolated areas where the entropy is locally as low as possible.

Low-entropy isolations

To generate such areas, many instances of a class \(c\) must be mapped to an area of \(Q\) containing the fewest instances of other classes \(c'\neq c\). Inside an area with a high frequency of class \(c\),

\[\lim_{p_c\to 1}p_c\log_2(p_c)=0\](2)

\[\lim_{p_{c'}\to 0}p_{c'}\log_2(p_{c'})=0,\quad\forall c'\in C\colon c'\neq c\](3)

which guarantees a low entropy. An area of \(Q\) with this property is a low-entropy isolation (LEI). Whether a given area is a LEI is assessed with a scalar field built from the interactions of all instances, described on the next page.