Fast Learning from Sparse Data

2013/01/23 by David Maxwell Chickering, Chickering, David Maxwell, David Heckerman +1 · 1 citation
Computer Science · #Bayesian Modeling and Causal Inference #Data Management and Algorithms #Data Mining Algorithms and Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.1301.6685

openalex publication_date 2013/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe two techniques that significantly improve the running time of several standard machine-learning algorithms when data is sparse. The first technique is an algorithm that effeciently extracts one-way and two-way counts--either real or expected-- from discrete data. Extracting such counts is a fundamental step in learning algorithms for constructing a variety of models including decision trees, decision graphs, Bayesian networks, and naive-Bayes clustering models. The second technique is an algorithm that efficiently performs the E-step of the EM algorithm (i.e. inference) when applied to a naive-Bayes clustering model. Using real-world data sets, we demonstrate a dramatic decrease in running time for algorithms that incorporate these techniques.

Cited by

• Model-Based Multiple Instance Learning

Related

• Accelerated Sparse Bayesian Learning via Screening Test and Its Applications
• Fast Marginalized Block Sparse Bayesian Learning Algorithm
• Learning Large Scale Sparse Models
• The Annealing Sparse Bayesian Learning Algorithm
• Exploiting random projections and sparsity with random forests and gradient boosting methods -- Application to multi-label and multi-output learning, random forest model compression and leveraging input sparsity