Logic, not similarity

Two ways to sort instruments

Imagine sorting musical instruments into guitars and bass guitars. One approach is by resemblance: a new instrument goes with whichever known instruments it looks most like in size, shape and colour. The other approach is by rule: count the strings. Six or twelve strings means guitar, four means bass. The rule is compact, it has few exceptions, and once known it needs very few examples to be applied perfectly.

Popular machine learning tools, such as random forests or nearest-neighbour methods, work mostly by resemblance. They are excellent when things that look alike belong together, and lost when the grouping follows a rule that resemblance cannot see. The logic replicant is designed to go after the rule.

Models such as the random forest evaluate, at every node, a rule on a single feature, forming a conjunction of one-feature tests; the k-nearest neighbours algorithm directly compares Euclidean distances to learned samples. Both recognise similarities. A semantic description, by contrast, defines an element by its intrinsic logic: the rational numbers as a quotient \(p/q\), or the French flag by its colours. A compact logic identifies elements of a larger set by a relation that involves more than one feature at a time, such as the individuals who spend more calories than they consume, or the phases of matter given by the Clausius–Clapeyron equation from boiling temperature, vapour pressure, heat of vaporisation and the gas constant.

Try it: the parity switchboard

The clearest example is the parity function, a generalisation of XOR. Eight switches can each be on (1) or off (0). The output is 0 when an even number of switches are on and 1 when the number is odd. Flip any single switch and the answer flips.

Switching one input variable produces the opposite output, so aggregating instances by similarity gives no information about the class of a new instance. A model can memorise every seen case, but that gives no clue about unseen ones. The only way to generalise is to find and replicate the underlying logic. In the paper's experiment a random forest reached 100% on the training cases and 0.20% on the test cases; the logic replicant reached 98.63%. Full results for the parity function.

What this means for the transformed space

The logic replicant redraws every example onto a new map where examples are grouped by the rule, not by how they look. Two examples of the same class that look nothing alike can land side by side, and two near-identical examples can land far apart. Only enough examples need to form groups for the classification to work.

The logic replicant projects each instance \(\boldsymbol{x}\) to a point \(\boldsymbol{q}=L(\boldsymbol{x})\) in a space \(Q\) where instances are grouped by the logic, not by their original features. Two instances of the same class with very different features may land close together in \(Q\), and two instances that are almost identical in \(X\) may land far apart. In terms of the Euclidean norm, both \(\|L(\boldsymbol{x}_1)-L(\boldsymbol{x}_2)\|\ll\|\boldsymbol{x}_1-\boldsymbol{x}_2\|\) and \(\|L(\boldsymbol{x}_1)-L(\boldsymbol{x}_2)\|\gg\|\boldsymbol{x}_1-\boldsymbol{x}_2\|\) are possible, depending on \(L\) and on the problem. Only some instances, similar or not in \(X\), need to form groups in \(Q\) for the classification to work.

This is a matter of inductive bias. Similarity-based models assume that neighbours share a class and excel when that holds. The logic replicant assumes that a compact logic exists and goes looking for it. On problems where such a logic exists it generalises from few examples; on problems where similarity is itself the simplest logic, it can exploit that too.