Blog

Jan 30, 2017 · post

The Algorithms Behind Probabilistic Programming

We recently introduced our report on probabilistic programming. The accompanying prototype allows you to explore the past and future of the New York residential real estate market.

This post gives a feel for the content in our report by introducing the algorithms and technology that make probabilistic programming possible. We’ll dive even deeper into these algorithms in conversation with the Stan Group Tuesday, February 7 at 1 pm ET/10am PT. Please join us!

Bayesian Inference

Probabilistic programming enables us to construct and fit probabilistic models in code. At its essence, Bayesian inference is a principled way to draw conclusions from incomplete or imperfect data, by interpreting data in light of prior knowledge of probabilities. As pretty much all real-world data is incomplete or imperfect in some way, it’s an important (and old!) idea.

Bayesian inference might be the way to go if you:

  • want to make use of institutional knowledge (suspicions, beliefs, logical certainties) about the quantities you want to measure and predict, rather than learn solely from the data
  • have several different datasets that you want to learn from
  • need to quantify the probability of all possibilities, not just determine which is most likely
  • want to do online learning (i.e., continually update your model as data arrives)
  • want to do active learning (i.e., gather more information until your predictions reach some threshold of confidence)
  • want to use data to decide if a more complicated model is justified
  • need to explain your decisions to customers or regulators
  • want to use a single model to answer several questions
  • have sparse data with a shared or hierarchical structure

Many — perhaps most — analytics and product problems are like this. And the central idea of Bayesian inference is centuries old. Why, then, do relatively few data analysts, data scientists, and machine learning engineers use the approach?

The Algorithmic Building Blocks

The problem is that, until recently, the algorithms that make product and business problems tractable using Bayesian methods have been difficult to implement and computationally expensive to run. Probabilistic programming systems abstract away many of these difficulties by baking inference algorithms in as building blocks of the language. Morever, these algorithms are robust, so don’t require problem-specific hand-tuning.

One powerful example is sampling from an arbitrary probability distribution, which we need to do often (and efficiently!) when doing inference. The brute force approach, rejection sampling, is problematic because acceptance rates are low: as only a tiny fraction of attempts generate successful samples, the algorithms are slow and inefficient. See this post by Jeremey Kun for further details.

Until recently, the main alternative to this naive approach was Markov Chain Monte Carlo sampling (of which Metropolis Hastings and Gibbs sampling are well-known examples). If you used Bayesian inference in the 90s or early 2000s, you may remember BUGS (and WinBUGS) or JAGS, which used these methods. These remain popular teaching tools (see e.g. STATS331 by Brendon Brewer, our favorite elementary introduction to Bayesian data analysis). But MCMC samplers are often too slow for problems with rich structure or internet-scale data.

Bayesian inference research in the last 5-10 years has therefore focused on two new approaches that use clever ideas to make sure the sampler spends more time in regions of high probability, raising efficiency. Those are Hamiltonian Monte Carlo and Variational inference.

Hamiltonian Monte Carlo and the No U-Turn Sampler

Hamiltonian Monte Carlo (HMC) treats the probability distribution as a physical surface. It uses an elegant and computationally efficient idea from 19th-century physics to explore that surface using calculus, as if under the influence of gravity. This method doesn’t work for discrete parameters, but the user doesn’t need to differentiate functions by hand.

To use HMC, you need to tune a sensitive hyperparameter, which makes its application expensive and error-prone. The invention of the No U-Turn Sampler (NUTS), a robust algorithm that tunes this parameter automatically, was crucial for making probabilistic programming useful and practical.

Variational Inference and Automatic Differentation

Variational inference (VI) samples from a distribution by building a simple approximation of the distribution. That approximation is so simple that it can be sampled from directly, entirely circumventing the need for approximate sampling algorithms like MCMC or HMC.

To do this, we start with simple distributions that we understand well (e.g., Gaussians) and perturb them until they match the real distribution from which we want to sample. The bulk of this work is done by stochastic gradient descent (SGD). Given its widespread use in machine learning (e.g., it’s used to train deep neural networks), SGD is well understood and optimized.

Converting a probabilistic model from a sampling approach to VI used to require complex math, making it hard for non-experts. Automatic Differentiation Variational Inference solves this problem by using automatic differentation (having computers take exact derivatives of arbitrary functions) to differentiate functions at the CPU instruction level, allowing a probability distribution to be explored efficiently.

Probabilistic Programming Languages

ADVI and HMC with NUTS are the two fundamental algorithmic innovations that have made probabilistic programming possible. Their inclusion in leading probabilistic programming environments (which can be traced back to these two blog posts from 2010) makes inference a one-liner. The end user doesn’t need to tune parameters or differentiate functions by hand. And because they’re built on Hamiltonian Monte Carlo or variational inference, they’re fast.

But fast and robust algorithms are not all that’s required to make Bayesian inference a practical proposition. Probabilistic programming languages also make life simpler by providing a concise syntax to define generative models using a library of built-in probability distributions. Probabilistic concepts are primitive objects defined in the core language. Specifying the model is therefore a declarative problem for the user, who declares what is known to be true and lets the language figure out how to derive conclusions.

The most popular probabilistic programming tools are Stan and PyMC3. Edward is a newcomer gaining a lot of attention. Stan experts Eric Novik and Daniel Lee will walk us through how Stan works and what problems they’ve used it to solve in our online event February 7.

For more on PyMC3 see our interview with Thomas Wiecki a PyMC3 core developer (and Director of Data Science at Quantopian). We also enjoyed Chris Fonnesbeck’s blog post that accompanied the recent official release of PyMC3.

In the report we go into more detail on the strengths and weaknesses of these two languages, and discuss some of the many other options. Whichever language you use, the claim of probabilistic programming - that it hides the complexity of Bayesian inference - is more true than ever.

Mike

Read more

Newer
Feb 9, 2017 · announcement
Older
Jan 25, 2017 · interview

Latest posts

Nov 15, 2020 · post

Representation Learning 101 for Software Engineers

by Victor Dibia · Figure 1: Overview of representation learning methods. TLDR; Good representations of data (e.g., text, images) are critical for solving many tasks (e.g., search or recommendations). Deep representation learning yields state of the art results when used to create these representations. In this article, we review methods for representation learning and walk through an example using pretrained models. Introduction Deep Neural Networks (DNNs) have become a particularly useful tool in building intelligent systems that simplify cognitive tasks for users.
...read more
Jun 22, 2020 · post

How to Explain HuggingFace BERT for Question Answering NLP Models with TF 2.0

by Victor · Given a question and a passage, the task of Question Answering (QA) focuses on identifying the exact span within the passage that answers the question. Figure 1: In this sample, a BERTbase model gets the answer correct (Achaemenid Persia). Model gradients show that the token “subordinate ..” is impactful in the selection of an answer to the question “Macedonia was under the rule of which country?". This makes sense .. good for BERTbase.
...read more
Jun 16, 2020 · notebook

Evaluating QA: Metrics, Predictions, and the Null Response →

by Melanie · A deep dive into computing QA predictions and when to tell BERT to zip it! In our last post, Building a QA System with BERT on Wikipedia, we used the HuggingFace framework to train BERT on the SQuAD2.0 dataset and built a simple QA system on top of the Wikipedia search engine. This time, we’ll look at how to assess the quality of a BERT-like model for Question Answering.
qa.fastforwardlabs.com
May 19, 2020 · notebook

Building a QA System with BERT on Wikipedia →

by Melanie · So you’ve decided to build a QA system. You want to start with something simple and general so you plan to make it open domain using Wikipedia as a corpus for answering questions. You want to use the best NLP that your compute resources allow (you’re lucky enough to have access to a GPU) so you’re going to focus on the big, flashy Transformer models that are all the rage these days.
qa.fastforwardlabs.com
Apr 28, 2020 · notebook

Intro to Automated Question Answering →

by Melanie · Welcome to the first edition of the Cloudera Fast Forward blog on Natural Language Processing for Question Answering! Throughout this series, we’ll build a Question Answering (QA) system with off-the-shelf algorithms and libraries and blog about our process and what we find along the way. We hope to wind up with a beginning-to-end documentary that provides:
qa.fastforwardlabs.com
Apr 1, 2020 · newsletter

Enterprise Grade ML

by Shioulin · At Cloudera Fast Forward, one of the mechanisms we use to tightly couple machine learning research with application is through application development projects for both internal and external clients. The problems we tackle in these projects are wide ranging and cut across various industries; the end goal is a production system that translates data into business impact. What is Enterprise Grade Machine Learning? Enterprise grade ML, a term mentioned in a paper put forth by Microsoft, refers to ML applications where there is a high level of scrutiny for data handling, model fairness, user privacy, and debuggability.
...read more

Popular posts

Oct 30, 2019 · newsletter
Exciting Applications of Graph Neural Networks
Nov 14, 2018 · post
Federated learning: distributed machine learning with data locality and privacy
Apr 10, 2018 · post
PyTorch for Recommenders 101
Oct 4, 2017 · post
First Look: Using Three.js for 2D Data Visualization
Aug 22, 2016 · whitepaper
Under the Hood of the Variational Autoencoder (in Prose and Code)
Feb 24, 2016 · post
"Hello world" in Keras (or, Scikit-learn versus Keras)

Reports

In-depth guides to specific machine learning capabilities

Prototypes

Machine learning prototypes and interactive notebooks
Library

NeuralQA

A usable library for question answering on large datasets.
https://neuralqa.fastforwardlabs.com
Notebook

Explain BERT for Question Answering Models

Tensorflow 2.0 notebook to explain and visualize a HuggingFace BERT for Question Answering model.
https://colab.research.google.com/drive/1tTiOgJ7xvy3sjfiFC9OozbjAX1ho8WN9?usp=sharing
Notebooks

NLP for Question Answering

Ongoing posts and code documenting the process of building a question answering model.
https://qa.fastforwardlabs.com
Notebook

Interpretability Revisited: SHAP and LIME

Explore how to use LIME and SHAP for interpretability.
https://colab.research.google.com/drive/1pjPzsw_uZew-Zcz646JTkRDhF2GkPk0N

About

Cloudera Fast Forward is an applied machine learning reseach group.
Cloudera   Blog   Twitter