HLearn cross-validates >400x faster than Weka

Abstraction: Algebraic structure exploits cut cross-validation from Θ(kn) to Θ(n)

Key points:

• Weka takes 70 minutes for leave-one-out cross-validation on census income dataset; Haskell HLearn library takes 9 seconds — 465x faster
• Key insight: naive Bayes classifier has algebraic structure of a monoid, group, and vector space
• Standard k-fold cross-validation is Θ(kn); algebraic algorithm is Θ(n) — runtime independent of number of folds k
• Algebraic cross-validation produces the exact same answer as standard cross-validation, not an approximation
• Weka's leave-one-out cross-validation shows quadratic runtime growth; HLearn's is linear
• HLearn is open-source on GitHub; approach generalizes to any model with suitable algebraic structure

Connections: Hlearn · Weka · Cross Validation · Machine Learning

Source: http://izbicki.me/blog/hlearn-cross-validates-400x-faster-than-weka