The Simplest Learning Machine, Pt.2 | by Victor Banev | MediumSitemapOpen in appSign up<br>Sign in

Medium Logo

Get app<br>Write

Search

Sign up<br>Sign in

The Simplest Learning Machine, Pt.2

Victor Banev

3 min read·<br>Mar 30, 2019

Listen

Share

In the previous article I outlined the concept of the Simplest Learning Machine. It’s an imaginary algorithm that uses one byte of persistent memory and learns to predict something about a stream of binary events. Can we actually write something like that? How would it work?<br>One semi-obvious thing we can learn is the rate of positive events in the stream. This would give us some predictive power, as long as that rate is different from 50%. A bit of a stretch to call this “machine learning”, sure, but I’ll get to the questions of usefulness later.<br>With just one byte of persistent memory you can’t record more than 8 events at a time and that’s not good enough for anything. But the interesting part (which is how I started thinking about this whole question to begin with) is that you can learn the rate of 1s and 0s in a bit stream without memorizing any part of the bit stream .<br>Imagine that the single byte of memory we’re afforded represents one of 256 possible states the “machine” can have. State #0 corresponds to seeing nearly no positive events. State #255 corresponds to getting almost exclusively positive events. With this kind of setup, we can “nudge” out state in the right direction every time we see an input: up for positives, down for negatives.<br>Here is the cool part. Imagine further that out “events” are physical particles like water droplets or air molecules. In real life water or air flow can be trivially measured by a spring-loaded plate of some sort. The more particles we get per unit of time, the more “force” they exert. They push the plate and eventually the whole system stabilizes at the point where the tension of the spring equals to the force exerted by the particle flow.<br>Good news is, we can trivially simulate this on a computer. Well, sort of. Here is how it works.<br>We have 265 possible states for the “learning machine”. State #0 corresponds to seeing nearly no positive events. State #255 corresponds to getting almost exclusively positive events. Each intermediate step correspond to roughly 0.39% increase in probability.<br>Every time we see a positive event, we nudge our estimated probability upwards.<br>Also, at every step we simulate “opposing events” at the rate we’re currently estimating. Those nudge the state down, like a spring resisting movement with ever increasing force.<br>When we reach the state where both real even and our simulated opposing event happen at the same rate, the system stabilizes. Sort of. It will dance around the true value.<br>That’s a lot of words, but both the concept and the code that can implement it are pretty simple. Effectively, it’s a physics-inspired Markov Model. Here is a straightforward C# implementation:<br>class RateLearner<br>static Random RandomNumber = new Random();

public byte Value { get; set; }

public float Percentage => (float) Value / (float) byte.MaxValue;

public void AddEvent(bool positive)<br>byte jitter = (byte)RandomNumber.Next();<br>if (positive && jitter > Value && Value byte.MinValue)<br>Value--;<br>}[To be clear: random numbers aren’t stored, so they don’t count towards the memory limit. If we used some sort of lookup table, it wouldn’t count towards memory limit either, because it would be shared across all learning machine instances. This particular implementation takes more than 1 byte of physical memory, because it’s a class in C#, but more efficient implementations are clearly possible.]<br>This algorithm might seem interesting or completely useless, depending on how you look at it. I find it fascinating, because it accumulates information about things that it doesn’t directly record. If I get to writing the next part of this article, it will discuss algorithm’s practical behavior and some of the possible uses cases.

Machine Learning

Algorithms

Written by Victor Banev<br>0 followers<br>·8 following

Help

Status

About

Careers

Press

Blog

Store

Privacy

Rules

Terms

Text to speech