Blog has moved to http://subsubroutine.com

This blog has a new, chic home at subsubroutine.com

subsub

Advertisements

Interactive network visualisation of murders in The Wire

This month I’ve been studying network analysis and teaching myself D3.js, and I wanted to post something here which combined the two. So I’ve used D3.js to create a force-directed graph of all the murders which take place in the TV series The Wire.

Unfortunately, WordPress.com forbids javascript in its blogs so to get the interative version you’ll have to either click here or on this static picture of the network:

Each of the coloured nodes is a character in The Wire. Shown are the murdered and the murderers, with the colour indicating how they died (or if they survived). If you click through to the interactive version, you can highlight nodes to see character names, or use the out-degree distribution barchart to select characters by the number of murders they committed. You can also double-click on any character to foreground their immediate network.

Continue reading

Real-time learning in data streams using stochastic gradient descent

In a typical supervised learning problem we have a fixed volume of training data with which to fit a model. Imagine, instead, we have a constant stream of data. Now, we could dip into this stream and take a sample from which to build a static model. But let’s also imagine that, from time to time, there is a change in the observations arriving. Ideally we want a model that automatically adapts to changes in the data stream and updates its own parameters. This is sometimes called “online learning.”

We’ve looked at a Bayesian approach to this before in Adaptively Modelling Bread Prices in London Throughout the Napoleonic Wars. Bayesian methods come with significant computational overhead because one must fit and continuously updated a joint probability distribution over all variables. Today, let’s look at a more lightweight solution called stochastic gradient descent.

sgd_plot_6

Continue reading

The symbolic algebra of the medieval longbow

Today’s post is going to be a bit more abstract and a bit less applied than usual, because today I want to take Python’s Sympy symbolic algebra library for a spin. As a narrative subject, we’ll be looking at the medieval English Longbow. We’ll start with some physics by modelling the deterministic trajectory of the arrow. Then we’ll add some statistical noise to make it a bit more realistic. Lastly, we’ll do some simple Bayesian inference on the range of the longbow. And we’ll do as much of it as we can via symbolic algebra.


These are English longbowmen. The English (or Welsh) Longbow is around 1.8-2m tall, can fire 10-12 arrows per minute in the hands of a skilled archer, and its steel-tipped arrows can penetrate the armour of a medieval knight. The “draw-weight” of a longbow is considerable, and skeletons of longbow archers often have enlarged left arms. Over a lifetime, the archer’s body was actually deformed by their tool of trade. So, how far could it shoot an arrow? Let’s figure that out with physics. According to Longbow Speed Testing (!), the velocity of an arrow leaving the bow is 172-177 feet per second. Say 53m/s in metric.

The trajectory of a projectile can be computed using classical mechanics:

y = x \tan{\left (\alpha \right )} - \frac{g x^{2}}{2 v^{2} \cos^{2}{\left (\alpha \right )}}

Where:

  • y is the height of the arrow
  • x is the horizontal distance that the arrow has travelled
  • \alpha is the angle at which the arrow is fired
  • v is the velocity of the arrow as it leaves the bow
  • g is the acceleration due to gravity (~9.8 m/s^2 on the surface of the earth)
  • (We’re ignoring wind resistance)

Let’s start by loading this into Sympy:

Continue reading

A Bayesian Search for Hannibal’s marauding army during the Second Punic War

At the time of writing, the hunt is still on for Malaysia Airlines flight MH370. Bayesian search theory has become topical (again). Bayesian search has been used to find crashed planes, lost hikers, sunken submarines and even missing hydrogen bombs. Bayes’ theorem is perfectly suited to search because it provides a mathematical framework for deductive reasoning.

Let’s try it out.

Here’s our (semi-fictionalised) search scenario: In 217BC, Rome and Carthage are at war. Dido’s curse still haunts the two civilisations. Carthaginian General Hannibal Barca has just annihilated a Roman army at Lake Tresimene, 180km northwest of Rome. He had already inflicted a series of crushing defeats on the Romans to the point that, after Lake Tresimene, Rome was left virtually without any field army at all. The great fear was that Hannibal would now march his war elephants on the city of Rome itself. In times of dire emergency, the Roman republic allowed for the temporary appointment of a dictator. Five days after Lake Tresimene, the senate appointed Quintus Fabius Maximus as dictator. The first question for him was: where is Hannibal now?

Continue reading

Adaptively Modelling Bread Prices in London Throughout the Napoleonic Wars

In this post I’ll demonstrate one way to use Bayesian methods to build a ‘dynamic’ or ‘learning’ regression model. When I say ‘learning,’ I mean that it can elegantly adapt to new observations without requiring a refit.

london bread shop

Today we lay our scene in London between the years 1760-1850. The good people of London have bread and they have wheat, which is, of course, what bread is made from. One would expect that the price of bread and the price of wheat are closely correlated and generally they are, though in periods of turmoil things can come unstuck. And Europe, between 1760-1850, was a very eventful place.

Continue reading

Archaeological Illustration of Bayesian Learning

This is the first of a series of posts on Bayesian learning. The learning mechanism which is built into Bayes’ theorem can be used in all sorts of clever ways and has obvious uses in machine learning. Today we’ll build our intuition of how the mechanism works. In the next post, we’ll see how we can use that mechanism to build adaptive regression models.


Bayesian statistics work in the same way as deductive reasoning. Bayes’ theorm is a mathematical form of deductive reasoning. It took me a long time to understand this simple but profound idea. Let me say it again: Bayes’ theorm gives us a mathematical way to do deductive reasoning: it allows us to take a piece of evidence, weigh it against our prior suspicions, and arrive at a new set of beliefs. And if we have more evidence, we can do it over and over again.

Let’s do an example. It occured to me that archaeology is an excellent illustration of how this works.


We are archaeologists

We’re excavating the site of a Roman village. Our job is to try and pinpoint what year(s) the village was likely inhabited. In probability terms, we want to work out p(inhabited) for a range of years. As we uncover relics like pottery and coins, we use that evidence to refine our beliefs about when the village was inhabited.

arch - site

Continue reading