Gausian distributions form a monoid

Abstraction: Abstract algebra monoid and group structure enables parallelizable ML training

Key points:

• Gaussian distributions form a semigroup under a merge operation (<>); merging two pre-trained Gaussians takes O(1) time regardless of dataset size, vs O(n) for retraining from scratch.
• They also form a group (monoid with inverse), enabling O(1) "subtraction" of a sub-dataset from an already-trained Gaussian.
• Any HomTrainer (semigroup homomorphism) automatically gains an online algorithm (add1dp), a parallel algorithm, and faster cross-validation for free.
• Parallel training via parallel train achieves near-perfect speedup: 1.91 sec serial vs 0.96 sec on 2 cores on 10^8 samples (vs 2.85 sec for the statistics package).
• The Haskell HLearn library implements this pattern; variance is stored as m2 = sum((x-mean)^2) * (n-1) to avoid division by zero and reduce FP divisions.
• The identity element of the Gaussian monoid is the Gaussian trained on an empty dataset (mempty).

Connections: Hlearn · Abstract Algebra · Gaussian Distribution · Monoids · Machine Learning

Source: http://izbicki.me/blog/gausian-distributions-are-monoids