stepleton/5100NonExecutableROSDecode

I was into the IBM 5100 way before
John Titor, if “before” makes sense
with that guy.

Sure, I never used one when they were new, but one of my favourite high school
teachers egged on a budding interest in old computers by giving me some IBM
5100 junk from his undergrad engineering classes: a textbook and a DC300 tape
cartridge. I finally
tracked down a working 5100 a few decades later, although the tape is long gone
now.

Having found one at last, it was worrying to find remarks like this online:

(“ROS” is IBM-speak for ROM and stands for “read-only storage”.)

I like to dabble in hardware, but I’m no
@brouhaha. Better to get him that ROS dump now
so that he’ll have the replacement worked out before bit rot comes for my own
machine 😃

The few times I’ve had the lid off of my 5100 have all been anxious moments, as
I have no idea where I’d find replacements for any of the ICs or SLT modules inside the machine.
I resolved early on that my recovery of the 5100’s non-executable ROS—the ROS
that contains the programming for the 5100’s BASIC and APL interpreters—would
be as minimally-invasive as possible.

In accomplishing this recovery I may have used more compute than all the IBM
5100s ever built have carried out over the past 44 years.

Table of contents

• The non-executable ROS in more detail, and stage 1
• Stage 2 is video
• Machine learning challenges
• Stage 3: image preparation
• Stage 4 means training data
• Well why don’t we just try classifying and call it Stage 5
• Stage 6 uses disagreement to purify the data
• Perhaps a step backwards in Stage 7: masking
• Fine, then, neural networks for Stage 8
• Stage 9 feeds Stage 9 into Stage 9 into Stage 9
• Ensembles: the second trick of classifying, and the first trick of Stage 10
• The eleventh, final stage: vote, and verify
• Epilogue: what if we had tried to do all of this with IBM 5100s?
• Acknowledgements
• Who, where, when
• Comments section

The non-executable ROS in more detail, and stage 1

For more information on what the non-executable ROS contains or the very first
steps of saving it, see this document.

For those who didn’t do that, the basic idea is that I can load chunks of the
ROS into the 5100’s RAM (or, RWS as IBM likes to call it—“read-write store”).
This will be its first stopping place on a lengthy journey.

Stage 2 is video

The 5100’s built-in monitor program, DCP1, lets you page the computer’s RAM in
hexadecimal, 32 bytes at a time. You can hold down the up and down arrow keys
and watch the digits stream by. With a camera pointed at the 5100’s display, I recorded the entire contents
of the non-executable ROS to thirty-two fairly boring videos. Here is a still
frame from one of them:

and if that seems exciting to you, the entire one-minute experience of that
portion of the APL ROS is on YouTube. The image shows the native
640×480 resolution of the video, since for some reason I was feeling
especially frugal about SD card space at the time.

With the videos on SD cards, the non-executable ROS was rescued at last onto
“modern” computer media, and so job done, I suppose. Still, it wasn’t quite
satisfying to leave things this way. People making emulators and hardware
prostheses need bytes, not pictures, and someday I might need them, too.

Machine learning challenges

With all the data in image form, there should be no further need to open up or
even turn on the 5100 again—perfect for my “minimally invasive” recovery.
All I have to do is work out an automated way to turn the numbers in the video
frames into binary data. As nice as it would be to feed the images into a free
OCR program like Tesseract, these
systems are designed to recognise natural language texts and fail on my hex
dumps. I need to come up with my own solution, and since I’m not going to
transcribe the images by hand (even if I felt like doing that, it would
probably be prone to errors), machine learning is the only practical strategy.

If you’ve read anything about machine learning in the last ten years, you’ve
probably encountered these villains:

These are three samples from the MNIST database, a collection of 70,000
handwritten digits as 28×28 greyscale images. MNIST has been called the “Hello
World” of machine learning: a common starter exercise for a
classification
system or technique is to throw it at MNIST and see whether it can learn to
recognise digits. In a way, the field of machine learning has been studying
digit recognition devoutly for several decades. This is a good thing, since I
have some digits, too: over three million of them. They come in sets of four,
like this:

My images are smaller than MNIST: 29×16 (the pictures above are shown “to
scale”). The digits themselves are much more regular than handwriting, but
they’re still not perfect. The old display hardware can wiggle display
scanlines around a little bit, light-blocking dust is trapped between the
plastic display shield and the CRT in places, and the screen geometry isn’t
perfectly linear in all directions. Sometimes a B can look a bit like an 8
or vice-versa. Speaking of B, there’s also the fact that I need to classify
the sixteen possible hexadecimal digits instead of MNIST’s ten. Then there’s
gibberish like this:

Recall that my images come from videos. My camera isn’t synchronised precisely
with the 5100 display, and sometimes the (virtual) shutter stays open during
the transition between two pages of digits. The result is a mess:

In addition to recognising the sixteen hex digits 0-9A-F, I’ll also need to
have some process for filtering out those non-digits, or else hallucinated
data derived from them will “contaminate” my recovered ROS.

Finally, speaking of contamination, a useful backup requires perfect
accuracy. At time of writing, the best reported MNIST classification error
fraction is 0.21%, or 21 in 10,000 (a
scoreboard; some background).
This is impressive, but the 5100 will not run properly if even one byte of
its non-executable ROS is out of place. 100% accuracy is a tall order for
machine learning, but with luck the 5100’s more regular digits will give it a
fighting chance.

Stage 3: image preparation

Warning! This section is even more boring than the rest of the writeup.
Feel free to skip ahead.

MNIST digits may be irregularly shaped, but the images they live in are regular
in important ways. The contrast and the brightness have been normalised so that
pixels range in intensity from totally dark (#00) to totally bright (#FF).
Even more importantly: the digits are centred. To maximise my odds of perfect
classification, I need to convert my video files into very regular, tiny images
of four-digit clusters like the ones shown above. Here are my steps, listed in
part as commands I ran (from a bash shell) on my Linux laptop:

1. Dump the movies to per-frame .png files.

I begin with each of the movies I recorded sitting in its own subdirectory.
That is, I’m assuming this arrangement:

./APL/APL_LROS_0000.MOV   ./APL/APL_LROS_2000.MOV
./APL/APL_LROS_4000.MOV   ./APL/APL_LROS_6000.MOV
./APL/APL_LROS_8000.MOV   ./APL/APL_LROS_A000.MOV
./APL/APL_LROS_C000.MOV   ./APL/APL_LROS_E000.MOV

./APL_ii/APL_LROS_ii_0000.MOV   ./APL_ii/APL_LROS_ii_2000.MOV
./APL_ii/APL_LROS_ii_4000.MOV   ./APL_ii/APL_LROS_ii_6000.MOV
./APL_ii/APL_LROS_ii_8000.MOV   ./APL_ii/APL_LROS_ii_A000.MOV
./APL_ii/APL_LROS_ii_C000.MOV   ./APL_ii/APL_LROS_ii_E000.MOV

./BCom/BCom_0000.MOV   ./BCom/BCom_2000.MOV
./BCom/BCom_4000.MOV   ./BCom/BCom_6000.MOV
./BCom/BCom_8000.MOV   ./BCom/BCom_A000.MOV
./BCom/BCom_C000.MOV   ./BCom/BCom_E000.MOV

./BCom_ii/BCom_ii_0000.MOV   ./BCom_ii/BCom_ii_2000.MOV
./BCom_ii/BCom_ii_4000.MOV   ./BCom_ii/BCom_ii_6000.MOV
./BCom_ii/BCom_ii_8000.MOV   ./BCom_ii/BCom_ii_A000.MOV
./BCom_ii/BCom_ii_C000.MOV   ./BCom_ii/BCom_ii_E000.MOV

Then:

# In each movie subdirectory
mkdir 00_originals
# In 00_originals, e.g.
ffmpeg -i ../../APL_LROS_0000.MOV %04d.png

2. Crop the per-frame .png files.

This step produces cropped images like the multi-digit “mess” shown just above.
Note the conversion from colour to greyscale. The cropping rectangle (the
argument to the -crop flag) was identified by hand.

# In each movie subdirectory:
mkdir 01_cropped
# In 00_originals:
for i in *.png; do convert -crop 350x75+39+151 +repage -colorspace RGB -colorspace Gray $i ../01_cropped/$i; done

3. Trim the per-frame .png files to useful frames.

The beginning and ending of each movie have extra frames that were recorded
while I moved my hands between the camera and the 5100’s keyboard. These are
not of much use. I went into each 01_cropped subdirectory and deleted the
extras by hand, leaving only about five to ten beginning and ending frames.

4. Crop individual 4-digit words.

This step does most of the work. From the coarsely-cropped images in step 2, a
Python program uses a crude gradient descent optimisation procedure to
gradually adjust the locations of tiny cropping windows placed around each of
the 4-digit words.

The technique sounds fancier than it is. The objective is to centre the windows
on the words as precisely as possible—in fact, with subpixel precision (that
is, we’d like to specify the locations of the windows in fractional pixels). To
do this, we iterate the following procedure for each window:

1. Use image interpolation to sample a picture of the
   4-digit word within the window.
2. Treating pixel intensities much like physical weights arranged on a grid,
   find the “centre of gravity” of the sampled picture.
3. Shift the window slightly in the direction of the centre of gravity—if it
   is left-of-centre in the sampled picture, for example, nudge the window
   leftward.

Although effective, this procedure isn’t perfect. For starters, it takes a long
time: on my slightly-old laptop, the better part of a day to crop all 1,010,070
word-images in the coarse crops from step 3. A more important issue comes from
the “centre of gravity” strategy in the first place: some digits like 8 or B
have more “on” pixels than others like 0 or 1, and so 008B cropped will not
quite line up with B800:

In the end I chose to move on and hope for the best. If I were starting over
from scratch, I might try a different technique that makes use of the
morphological operators and connected components-based methods I used in
recovering the 5100’s executable ROS.

Code and data files used by this step:

• crop_word.py: library for cropping single digit images.
• crop_words.py: program for cropping multiple digit images.
• crop_list.csv: initial window locations, prior to
  optimisation; these were created by hand.
• crop_all_words.sh: shell script for applying the
  digit-image cropping program to all coarsely-cropped images.

And on the command line:

# In the top-level directory, make more subdirs:
for i in `find . -name 01_cropped`; do j=`echo $i|sed s/1_cropped/2_words/`; mkdir $j; done
# Now run the cropping script and waaaaaaaaait.
./crop_all_words.sh

It’s worth mentioning that crop_words.py also attempts to adjust image
brightness and contrast, which varies in the original images owing to
banding from camera
shutter/5100 display synchronisation issues. You can see this banding for
yourself at the YouTube link
from earlier.

Stage 4 means training data

Training data is the only essential ingredient for successful machine learning.
All other details are basically fashion decisions.

For a classifier like the one I want to make, training data amounts to pictures
of 4-digit words (the input to the classifier) paired with the correct
numerical label (the four-digit output we’d like the classifier to produce).
For example:

(, 22A0)

(, 92DC)

(, 955A)

(, 6000)

(, 4770)

With loads of training data, you can recognise anything simply: just scan all
of your pairs like an enormous identity parade (police lineup) and emit the
label associated with the closest match. This turns out to be a real machine
learning technique.

As it will turn out, 7,046 of the words in the non-executable ROS—over 4% of
them—will appear there only once. Unless all of these singletons wind up in
the training data, they won’t be identifiable via simple matching. More
sophisticated classification methods learn to generalise from training
examples in sophisticated ways, allowing them to decode input that they’ve
never seen before. This is most of the learning in “machine learning”. The
best techniques are distinguished by how much generalisation they can do.

So, if I use a good technique, how much training data will I need? It’s
difficult to know. In machine learning research, fully 60,000 of the 70,000
MNIST digits are commonly reserved as training data—over 85% of the entire
dataset. Hoping that I won’t need such an extreme ratio, and knowing that my
dataset isn’t MNIST, I choose an arbitrary minimum number of training data
examples: 100,000.

The first 11,000 by hand: a quiet New Year’s week

I’ve got some good friends who’ve helped me out on various projects over the
years, but I think I’m on my own for the tedious task of labelling all of this
training data. The least I can do is try to make it less painful for myself.

Jotting down labels into a text editor would be pretty slow; instead, I decide
to make a custom program that presents word images and collects digits as fast
as I can type them. It looks like this:

This is an ordinary command-line program with interspersed graphics, made
possible by using a terminal emulator that supports
Sixel graphics. This method for showing
screen images inline with text was introduced in the early 1980s by Digital
to provide graphics capabilities for their VT240 and VT241 terminals.

(From the VT240 owner’s manual)

Since I don’t have one of those, I’ll use mlterm on my laptop instead. The program itself
comes in two parts: the interface and a database backend library (where the
“database” is really just an enormous .csv file). Both are written in
ordinary Python, but the interface makes use of the UNIX-only termios and
tty modules. (Windows users might be able to get it working under
cygwin.) Here is the (hastily-written!) code:

• labelthon.py: The main program and interface.
• label_database.py: The database backend.

To use this program, you’ll need an empty database first. Assuming you’ve
followed all of the steps so far, this one,
uncompressed, will work for you. (Beware: it’s over 54 MiB, but there’s a lot
of duplicated text, so lzip compresses it
down to a measly 255 KiB.) You will need to run the “labelthon” program from a
directory where all of the paths in the database are valid, like so:

./labelthon.py -n 100000 --mark-apl-ros-c000-zeros database.csv

Now you and mlterm are ready to sit down for days and days of hand-labelling.
You’ve even got a head start: you can tell by watching that all data words in
APL_LROS_C000.MOV and APL_ii_LROS_C000.MOV (the second filming of the same
thing) are 0000, so the --mark-apl-ros-c000-zeros flag labels all of the
images from those movies accordingly. “labelthon” will select randomly from
the other word images and show them to you, and you’ll type in the letters you
see.

Human error is a problem, so the program will want to collect two identical
labellings from you before it believes the label you’ve chosen for a particular
word image. At a minimum, then, you’ll need to type in 200,000 labels, although
due to the way “labelthon” chooses between showing you a new image or asking
you to verify an old one (controllable by flags), you’re likely to do even more
than that.

If you see a “gibberish” image like the one above, type m to mark it as
nonsense. If the image is clearly 0000 (many word images are, even after
applying --mark-apl-ros-c000-zeros), the shortcut z saves you from typing
four digits. If you get tired of this madness, type q to quit.

On New Years Day, I set to work:

Blue marks show times when I’m working (the database library saves
timestamped backups of the database in the background). The minor horizontal
ticks are hours. The count goes down on the 4th and the 5th because I change
the flags to force “verification mode” and wind up clearing out errors.

By the 6th, BBC iPlayer runs out of episodes of Ambulance Australia to watch
in the background, and I’m pretty tired of typing digits. I consider
crowdsourcing the 90,000 labels I had left to go, but getting reliable results
from crowdsourcing can be harder than it seems, and a browse through
r/HITsWorthTurkingFor
suggests that Amazon’s gig economy workforce probably has better things to do.
Fair enough—if I don’t like the job so much, why inflict it on others?

To 62,000 labels by logic analyser

What? Yes, I’ve had a logic analyser this whole time.

The graph above actually shows a zoom of the overall labelling progress, which
looks more like this:

Fed up with labelling by the 7th, I’m off doing other things for a while, but
before long I decide that I ought to save the 5100’s executable ROS (the other
important ROS in the computer). This is a different project described
elsewhere,
but suffice it to say that it means opening up the 5100 again after I’d hoped
to keep the covers shut. That recovery was fairly straightforward, and I might
have been wise to adapt those techniques to the non-executable ROS, but then
again, I’d already gone to so much trouble for the existing
approach.

In any case, with the covers off, it’s not hard to attach my logic analyser to
the appropriate bus inside the 5100 and re-run the program that loads
non-executable ROS data into memory. My device, a Rigol MSO2202A-S,
has plenty of memory to record the data from each load. Surely with these
traces I can easily reconstruct the entire non-executable ROS and forget all
about machine learning, right? So, I make my recordings, gently untangle the
logic probes from the 5100’s circuitry, and close its case again, hopefully now
for months or even years. A look at the data afterwards reveals two issues:

First, I cleverly forgot to capture any kind of clock signal to help identify the boundaries
between bytes in the eight data bit streams I’d recorded. A long stream of
$00 values could be a run of five $00 bytes, or one or three or fifteen. There
is no way to know for certain.

Second, though, my MSO2202A-S is terrible at saving recorded data.

It can store oscilloscope traces in a variety of formats, but as far as I can
tell, only the .csv files it writes contain recordings from the logic probes.
Obviously I have no problem with large .csv files, but the Rigol sure does, as
the files it gives you are corrupt. Occasionally it loses track of the data
it’s writing to the file and shovels in a bunch of $00 bytes
(nonprintable—cheeky for a .csv) instead in hopes that you won’t notice.
It’s not uncommon for several hundred bytes to go missing this way. This graph
shows the damage:

Each tiny bar in this bar chart represents a byte in a recorded data stream.
The height of the bar is how long the byte lingered on the data lines before
a different byte value replaced it. While a legitimate run of identical values
(e.g. fifty $00 bytes in a row) would have a slightly taller bar, the massive
spikes are gaps where the Rigol chose to drop the data.

It might have occurred to me to make multiple recordings of the same data
stream (as I’d done with the videos) since the logic analyser might not have
put the gaps in the same places the second time around. Sadly, this did not
occur to me, and by the time it did, the 5100 was buttoned up once again.

So, to try and salvage the good parts of the recordings I had, I make another
Sixel-enhanced Python program:

This program allows me to align 32-byte snippets of logic analyser data with
screen images from the video, with search features to make it easier to
navigate through the recording. After a snippet is successfully aligned,
pressing the space bar commits the data to the corresponding word images. A
boring YouTube movie shows
how this program works in more detail.

This way is much faster than typing hex digits by hand. After going through all
of the logic analyser recordings, I recover an additional 50,000 training
examples, give or take. It still takes a few days. Getting training data is a
drag.

Code used by this step:

• rigol/00_dedup.py: A first preprocessing step for the
  logic analyser recordings, this script filters unprintable characters and
  corrupted lines from .csv files, then deletes successive repetitions of the
  same byte value (essentially achieving a time-based run-length encoding of the data).
• rigol/01_invert.py: A simple second preprocessing step
  for recordings that flips all of the bits in the byte data, since the logic
  lines for non-executable ROS data in the 5100 are active low.
• labels_from_traces.py: The interactive program for
  aligning preprocessed logic analyser data with video still images, then
  deriving training data from the aligned recordings.

In case you don’t have your own MSO2202A-S but still want to use some of this
code, all you need are .csv files made entirely of lines that look like this:
12345,A7, or a time in nanoseconds, a comma, and a byte in hexadecimal. You
should also throw in a bunch of NUL bytes here and there for the full Rigol
experience.

Finally, on the command line, assuming you’ve placed your .csv files in a
subdirectory called rigol/00_originals, and you’re using a bash-like shell:

# Preprocess the logic analyser recordings.
mkdir rigol/01_deduped
mkdir rigol/02_inverted

cd rigol/00_originals
for i in *.csv; do ../00_dedup.py $i > ../01_deduped/$i; done

cd ../rigol/01_deduped
for i in *.csv; do ../01_invert.py $i > ../02_inverted/$i; done

# Back in the top-level directory, start aligning recordings to video images.
# Here, we'll try to match data between video and traces for the portion of
# the APL ROS starting at word address $4000.
cd ../../
./labels_from_traces.py database.csv 
    rigol/02_inverted/apl4000.csv 
    ./APL/APL_LROS_4000/01_cropped/

Well why don’t we just try classifying and call it Stage 5

I’ve done about as much labelling as I want to do, and I’m only 60,000 training
examples in, well short of my arbitrary 100,000-example goal. I don’t want to
do any more hand-labelling or take the cover off of the 5100 again;
crowdsourcing is out, and an earlier effort to send bytes out of the
oddly-tilted I/O ports at the back
of the computer didn’t work.

What if I already have enough data? Why not just give classifying a try now?

With hindsight, I can compute my accuracy as I refined the dataset and tried
different techniques over time:

But that’s getting ahead of things a bit.

Support-vector machines
(SVMs) are a classic machine learning technique, and since they had worked so
well for the 5100’s executable ROS,
it’s natural to try that first. I devise a procedure that actually trains
four multi-class
(“multi” since there are 16 ways to interpret a digit: 0, 1, 2, …, F)
SVM-based classifiers simultaneously: one for the first digit, one for the
second, and so on. This was 9 February, and as the leftmost graph point shows,
it works pretty well by machine learning standards, giving an error rate of
0.36%. Sadly, this still means over 3,000 word images are read incorrectly,
and I need to work that down to 0.

At the time I don’t actually know the true accuracy of my procedure, but I can
hold out some of my training data as a test set,
and it shows something similar. So, what follows is the classic machine
learning exercise of tweaking stuff and seeing what happens. Beyond SVMs, the
scikit-learn Python library offers a smörgåsbord of
plug-and-play multi-class classification techniques, and each one of those
comes with configuration options as well.

I can’t remember everything I try, but when I see the test set accuracy start
to plateau at an error rate just over 0.15%, it suggests I’ve hit tweaking’s
limits. My training data probably isn’t comprehensive enough to teach these
algorithms all the varied ways that digits can look, and perhaps it even has
some flaws in it.

As it turns out, though, even errors in classifiers can be useful.

Code used by this step:

• labels_classification.py
• labels_diff.py

And some commands:

# Try classifying the data, using the "ground truth" labels in `database.csv`
# and placing the results in `database_classified_00.csv`.
./labels_classification.py database.csv database_classified_00.csv

# Edit the `train_classifier` function in the classification code to try
# a different type of scikit-learn classifier.
vi labels_classification.py

# At this point you'd repeat the above two commands, writing results to a new
# `database_classified_XX.csv` file each time. Each file will be slightly
# different due to different methods and the way the program randomly allocates
# data to the training and test sets (so, it learns from different data each
# time. In order to see how two classifications disagree (in this example, the
# sixth and the thirteenth), you can do this:
./labels_diff.py 
    database_classified_05.csv 
    database_classified_12.csv 
    --skip-XXXX-from=database.csv

# The last flag causes the diff to ignore label images that were marked as
# nonsense in the "ground truth" database. You can use a similar invocation
# to inspect how the classifier chose to classify the ground truth data
# itself---a good way to spot the kinds of mistakes the classifier makes, or
# in some cases find errors in the ground truth labels themselves. You'll see
# this idea crop up again later, too...

Stage 6 uses disagreement to purify the data

Now and then a machine learning paper makes an impressive show of referencing
one of the most famous opening lines in all of literature. Papers that do this
are all alike. They observe that collections of classifiers (or other kinds of
learning systems) all tend to produce the same answer when they evaluate
unambiguous data, but then yield different answers when applied to messy,
noisy information. By now I’ve got plenty of classification results from
Stage 5, and
thanks to the garbled digits that we saw show up during transitions between
frames, I’ve also got plenty of messy, noisy
information for the results to disagree about.

I decide to write another program that detects these disagreements and allows
me to flag all word images from the corresponding video frame as ignorable
nonsense. The interface looks like this:

Operation is straightforward: you view each cropped video frame that yielded
images that caused the classifiers to disagree, then specify whether the frame
had garbled digits. I’m able to mark word images from over 7,000 video frames
as invalid using this tool, flagging nearly all of the corrupt label images.

Code used by this step:

• labels_exploit_disagreement.py

Command:

# The first argument is the database to modify, the second is the name we gave
# to subdirectories holding per-frame cropped images, and the rest list at
# least two databases of classification results that we want to compare to find
# disagreements.
./labels_exploit_disagreement.py 
    database.csv 
    01_cropped 
    database_classified_05.csv 
    database_classified_12.csv

Perhaps a step backwards in Stage 7: masking

Marking garbled images label was a useful step (it helps labels_diff.py
ignore meaningless disagreements between classification results, for example),
but it hasn’t really changed the ground truth data that trains the classifier.
I’m still just about as far on that front as I was after Stage 5. By now, though,
I’ve started to think about an even fancier tweak to try: masking each digit in
word images prior to any classification.

Generic classification methods like the ones I’m using don’t come with
sophisticated preconceived notions about the data they’re analysing. Even
though people know that, generally speaking, none of the other digits ever
affect the fact that the second digits of 540C and 144A are both 4, my
classifier has no such built-in bias. For all it knows, in the rare cases where
the last three digits are 473 or 4AB, it should emit 5 instead of 4 for
the second digit. Why not? The classifier has no real notion of “four” or
“five” or “digit” or “second”. All it sees are abstract patterns of pixels with
certain measurable similarities. Why should one subset of the pixels be more
important than any other subset?

So, it occurs to me that it might be beneficial to contribute my own problem
understanding to the process. If the classifier for the second digit only saw
images with all of the other digits censored, it wouldn’t need to learn on its
own to ignore the other digits, and less to learn means less training data is
needed. Maybe we wouldn’t need 100,000 ground truth labels after all.

Thus, from each word image, I’d like to derive four masked images like these:

My strategy for segmenting the digits is simple. Summing all of the columns
of pixels in the image gives you a one-dimensional graph of peaks and valleys.
The gaps between digits form the deepest valleys, since these gaps have only
dark pixels and sum up to small values:

Regrettably, this method doesn’t always work. In some images, digits abut
so closely that their gaps are not so dim after all:

Here, the third-deepest valley turns out to be the middle column of the
trailing C digit, just barely—so my approach can be fooled. I don’t realise
this right away, but my first classification results with masking enabled are
so much poorer that they form their own valley: the deepest in the progress
graph shown earlier. After spotting the
problem, I try mitigating it with quick hacks like allowing digit splits to
occur only on certain columns, and that works most of the time. Of course,
sometimes it doesn’t:

In the end, the masking tweak seems to wind up being a wash, trading familiar
kinds of errors (partly attributable to the classifiers not “knowing” to limit
their scope to a particular digit and nothing else) for new kinds (badly-masked
images). Additionally, it’s not 100% clear that the classifiers really should
ignore other digits. Just as seeing the letter Q in English text makes it
likely that the next letter will be a U, some patterns recur in the ROS data.
If the first digit of a word is 4, the second will be 7 over 3/8ths of the
time. Nearly one time in nine, the entire word will be 47f0 (an unconditional
jump instruction in System/370 machine code). Our classifier might do better
if it has the opportunity to learn and exploit these regularities.

Either way, after some hacking to improve the masking, classification accuracy
does climb back up out of the deepest valley, but this probably has more to do
with something else I’m trying at the same time…

Code used by this step:

• labels_classification.py (once again)
• show_digit_mask.py

Commands:

# The new --mask-digits flag enables the most refined (i.e. tweaked) version
# of the digit masking described above.
./labels_classification.py --mask-digits database.csv database_classified_25.csv

# Or, to visualise digit masking at work on a word image, provided your
# terminal supports Sixel graphics:
./show_digit_mask.py APL/APL_LROS_0000/02_words/0314_0_1.png

Fine, then, neural networks for Stage 8

So far the classifier techniques I’ve been using are well-established,
well-understood methods with interpretable inner workings and strong
theoretical guarantees. Who cares about rigour, though, when there’s a
massively hyped method that works even better?

Simple feed-forward neural networks are explained in countless
YouTube videos,
so it suffices for here to say that I try them out. The scikit-learn package
I’ve been using includes such networks in its suite of classifier methods, so
putting them to work requires only an easy modification of my code. Next, since
nobody knows the “right way” to design a neural network (in this case, to
choose the number and size of its layers, among other hyperparameters), the only
thing to do is “wing it” and try a bunch of configurations. By the time I get
bored of doing that, my last network has three hidden layers of 50, 40, and 30
ReLU units. I
can tell from results on the test set that performance is considerably
better than what the other methods had achieved, with misclassifications
now down in the single and low double digits.

I’m convinced I could improve even further, though. Virtually all neural
networks that do serious image processing make use of convolutional layers, about which there
are abundant further explainey YouTube videos. It has been Officially Decided
that these very capable and ubiquitous network structures are out of scope for scikit-learn,
though, so I switch to using Keras, a “real” library for
neural networks. Once again, random tweaking is the lowest effort way to
explore the space of network architectures. In later stages, I settle on a
network with a single 16 3×3 filter convolutional layer, a 2×2 max-pooling
layer, and then two hidden layers similar to the first two from the previous
network.

It takes longer to train the new network in any configuration: much longer,
nearly half a day (remember, my laptop is no speed demon). The network is more
complicated this time, and it happens that I’m also processing about six times
more data in training now than I was before, but the runtime increase still
seems disproportionate. Oh well. When training completes at last, the
performance improvement is present, but slight: perhaps one or two fewer
test-set misclassifications. 100% correctness is closer than ever, but it still
feels a long way off.

Code used by this step:

• labels_classification.py (for the last time)
• labels_classification_keras.py

Commands:

# Both classification programs are invoked in the usual way.
./labels_classification.py database.csv database_classified_30.csv
./labels_classification_keras.py database.csv database_classified_31.csv

Stage 9 feeds Stage 9 into Stage 9 into Stage 9

Once again, the secret to all successful machine learning is training data. If
the classifier needs improvement, get more training data.

I’m still stuck at 60,000 training examples without any appetite for making
more. The results of my existing classifiers are pretty good, but still not
perfect. Well, fine, what if I just use these results themselves as training
examples?

Most practitioners would regard this idea as risky, generally speaking. An
error in a classifier’s output-turned-training-data could be amplified in an
“offspring” classifier that learns to replicate the mistake; after enough
generations, several of these errors might proliferate, causing the
classifications to become increasingly nonsensical. There is another
possibility, though: the abundance of correct labels could overwhelm the
sporadic errors and draw successive generations of classifications toward a
more consistent and correct final output. Mathematically, we are suggesting
that this iteration of training and classification converges toward a useful
fixed point. If x
is the original training data, we could call the function

f(x)

the output of training a classifier on the original training data and then
computing its classification of the entire dataset. Next,

f(f(x))

would be the result of training a second classifier on the result of the first
and obtaining its classification of all of the data. This iteration can
repeat as often as you like, so

f(f(f(f(f(f(f(f(x))))))))

would be eight generations away from the training data we made in Stage 4. Is this actually worthwhile? Will this process
converge on anything useful? Neural networks are so complicated that no
mathematics exists today that would help us answer this question using theory
alone—the only way to find out is to try it and see what happens.

To be honest, I’m not quite that brave. If I do exactly this iteration without
any intervention, my suspicion is that the procedure will have a fixed
point—a very boring one! Consider the classifier for the first digit: a
relatively minor, random error might cause one generation to misclassify the
first digit of a few training examples as a 3; in the next generation, the
output 3 covers slightly more of the input and may cause the first digit in
several more images to receive a 3 misclassification; this process repeats
and reinforces itself until, many generations later, all digits are
classified as 3! I never try this “pure” iteration and so don’t know if this
is what would really happen, but I think it’s pretty likely.

Instead, I use an approach with two modifications. First, rather than train
“offspring” classifiers on the entire output of their parents, I only use 60%
of the parents’ output. I don’t bother writing a formal program for this:
instead, I just run a throwaway snippet in an interpreter:

with open('database.csv', 'r') as din:
    with open('database_classified_40.csv', 'r') as dc:
        with open('database_tmp_hybrid.csv', 'w') as dth:
            while True:
                l1 = next(din)
                l2 = next(dc)
                num = int(l1.split(',')[2][1:-2]) if count > 0 else 2
                count += 1
                if num >= 2 or random.random() < 0.6:
                    dth.write(l1)
                else:
                    dth.write(l2)

(It’s not even slightly good code! I couldn’t be bothered to use
itertools.izip, so the loop terminates with a StopIteration exception.)

My reason for omitting the entire dataset relates to the Anna Karenina gimmick
discussed in Stage 6.
“Iterated retraining” (for lack of a better term) will lead to the “generation
loss“-like errors I worry about
above, but my hope is that the subsampling will increase the diversity of the
errors that emerge from one generation to the next, making it a bit less likely
that successive generations will repeat the same mistakes.

This diversity is also helpful for the second modification to the “pure”
iteration, as a prompt for manual intervention. After computing the next
generation of classifier outputs, I compare it to several of the earlier
outputs and manually supply the correct classification answer. I do this in
hopes of stopping any remaining gradual inter-generational error proliferation
right when it starts. For this slightly more complicated operation, I write
another custom program:

This program lets me resolve disagreements between classifier outputs
myself—a handy way to provide additional training data labels for word images
that might be critically ambiguous. Sometimes I find more garbled digits I’d
missed in Stage 6, so I can
also mark entire frames as invalid.

Soon the strategy seems like it might be paying off. The number of
misclassified word images in the test data falls into single digits. Busy with
other things (or maybe I’m just getting bored), I spend over a month in a daily
routine of resolving classification disagreements, sampling new training data,
tweaking the network parameters, and kicking off a new training+classification
iteration to run in the background. Errors remain few; sometimes they even fall
to zero. Is this real performance, though, or is each new classifier generation
increasingly delusional?

Code used by this step (besides the quick-and-dirty Python):

• labels_resolve_disagreement.py

Commands:

# The first argument is the database to modify, the second is the name we gave
# to subdirectories holding per-frame cropped images, and the rest list at
# least two databases of classification results that we want to compare to find
# disagreements.
./labels_resolve_disagreement.py 
    database.csv 01_cropped 
    database_classified_44.csv 
    database_classified_45.csv

Ensembles: the second trick of classifying, and the first trick of Stage 10

After a month of kicking the can down the road, I can’t put it off any longer.
It’s time to try compiling all of my classified word images into the
non-executable ROS data.

Even though I’m seeing very low error rates on the test data, it seems unwise
to trust the results of a single classifier run. Instead, it’s probably better
to collect “votes” across multiple classifications and go with the majority
interpretation. In machine learning, this is a kind of ensemble method, a class of old tricks that
have helped obtain contest-winning classifier performance now and then over the
years. In particular, it’s very similar to a method called “bagging“. The main difference is
the way I train new classifiers on old classifier output—in machine learning,
such approaches are known as “totally weird”.

Not only can I combine classifications from different classifiers, I can also
combine them across multiple video frames, since each “page” in the DCP1
monitor program stays on the screen for around a tenth of a second (about three
frames), and also because I recorded all the data twice for redundancy’s sake.
It’s very helpful too that the DCP1 display always shows the memory locations
of the data on the screen:

Those are the words in the magenta box. To the right of 1AE0 are the 16 bytes
of data stored at that location, and likewise for 1AF0 beneath it. So, here’s
the plan:

• Collect several recent classifier runs from Stage 9. Then examine each
  classifier run:

  • For each video frame in the classifier run, note which chunk of the ROS
    was being recorded (recall from Stage 1 and Stage 2 how the whole ROS had to be split across sixteen
    separate videos—although I have 32 videos from recording each chunk
    twice). Then:

    • For each data word in the frame, identify its memory location from its
      position in the image along with the values of the address words at left
      (as read by the classifier).

    • Record a “vote” for the classifier’s reading of the data word as the
      value of the data at the deduced memory location in the current ROS
      chunk.

I write a program that assembles these votes into a text database and run it on
the outputs of the 28 most recent classifier runs. Even though most memory
locations receive comfortably more than 100 votes each, I’m surprised by the
degree of consensus: there are only 137 words in the entire ROS that receive
multiple interpretations, and only one of them has three readings (the rest
have only two). In nearly all cases, the majority is overwhelming, with
runner-up interpretations claiming only one or two votes.

Huh. With a little bit of mental arithmetic you can convince yourself that, in
a sense, I’ve put in a lot of unnecessary effort. It must be the case that for
most of my classifier runs, I could examine the run individually and, by
counting votes from different frames for just that run, achieve the same
majority interpretation of the entire dataset that I get from considering all
of the classifier runs together. There just simply aren’t enough disagreements
for more than one or two of the classifier runs to have a different voting
result.

Oh well. Anyway, it’s 2019. Everyone knows by now that a majority vote is no
guarantee of a good outcome. All of my classification results may agree, but
they could still be deluded in the same way. Ponder that one, Tolstoy…

Code used by this step:

• assemble_labels.py
• assemble_all_labels.sh

Commands:

# Unlike other stages, this stage operates the assemble_labels.py program with
# a shell script. You should edit it first and specify the classifier outputs
# you'd like to poll for votes.
vi assemble_all_labels.sh

# Then just run the script. The result is a handful of text vote tally
# databases with names like assembly_APL_LROS_6000.txt, one for each of the
# chunks of non-executable ROS from the original video recordings.
./assemble_all_labels.sh

The eleventh, final stage: vote, and verify

The votes are in. If the majority are correct, I might be nearly finished, so I
rush to supply all of the missing pieces. First is a small program, written
even more hastily than usual, to take the tally databases compiled by
assemble_labels.py and emit binary data reflecting the most popular
interpretations of each of the word images.

Soon I have two candidate binary ROS dump files, one for the APL interpreter
and one for the BASIC interpreter and the common ROS. At 128 KiB each, both are
larger than they need to be: APL should only take 96 KiB, and the BASIC/common
code only uses 54 KiB. I’m still hopeful that the true data is embedded
somewhere within. To find it, and to check that the decoding was correct in the
first place, I’ll use the same data integrity check that the IBM 5100 uses to
make sure the non-executable ROS is in good shape.

When you flip the big red switch to turn on an IBM 5100, the computer growls to
life and immediately begins its bring-up diagnostic. Gradually probing its
internal mechanisms, starting from the most fundamental logic and memory
components and working outward to the interfaces and stored programs that it
uses to interact with the world, it marks progress with letters of the alphabet
printed to the top-left corner of the screen. The most interesting test to us
is the ninth, where the computer begins by displaying this:

 ABCDEFGHI
18

The 5100 is testing the integrity of the non-executable ROS. 18 is the first
portion the computer examines: it refers to a 6144-byte chunk of “common” code.
Next, the bring-up counts through additional portions of the ROS depending on
which language you’ve selected: if APL, sixteen of them numbered sequentially
as 20 through 2F. BASIC uses only eight marked 10 through 17. (You can
watch a video of my 5100 doing both sequences.)

The integrity check for each chunk uses a 16-bit CRC calculation (excellent
video lesson). To apply the same
check on a more modern computer, I first had to identify exactly what the 5100
was doing in a disassembly of the 5100’s executable ROS, and
after an evening of digging (aided by early hints from Christian Corti in that
linked disassembly), I spotted the key loop at memory location $5F3C and the
core of the calculation at $5F94. I might have carefully analysed its
operations and devised an implementation of the same algorithm in a
contemporary language, but honestly, it was much easier to do this:

def update_crc(byte: int, crc: Tuple[int, int]) -> Tuple[int, int]:
  """Update a 16-bit CRC given a new byte."""
  # Set up the 16 registers of the 5100.
  r = [(0, 0) for _ in range(16)]
  r[9] = (crc[0] & 0xff, crc[1] & 0xff)
  r[10] = (0, byte & 0xff)

  r[14] = (r[14][0], r[9][0])                                   # MHL R14, R9
  r[14] = (r[14][0], r[14][1] ^ r[10][1])                       # XOR R14, R10
  r[1] = r[14]                                                  # MOVE R1, R14
  r[15] = r[14]                                                 # MOVE R15, R14
  r[15] = (r[15][0], (r[15][1] << 4 & 0xff) | (r[15][1] >> 4))  # SWAP R15
  r[14] = (r[14][0], r[14][1] ^ r[15][1])                       # XOR R14, R15
  r[14] = (r[14][0], r[14][1] & 0xf0)                           # CLR R14, #$0F
  r[14] = (r[14][0], r[14][1] ^ r[9][1])                        # XOR R14, R9
  r[9] = r[1]                                                   # MOVE R9, R1
  r[15] = (r[15][0], r[15][1] & 0x0f)                           # CLR R15, #$F0
  r[9] = (r[9][0], r[9][1] ^ r[15][1])                          # XOR R9, R15
  r[1] = (r[1][0], (r[1][1] << 5 & 0xff) | (r[1][1] >> 3))      # ROR3 R1
  r[15] = r[1]                                                  # MOVE R15, R1
  r[15] = (r[15][0], r[15][1] & 0x1f)                           # CLR R15, #$E0
  r[14] = (r[14][0], r[14][1] ^ r[15][1])                       # XOR R14, R15
  r[1] = (r[1][0], r[1][1] & 0xe0)                              # CLR R1, #$1F
  r[9] = (r[9][0], r[9][1] ^ r[1][1])                           # XOR R9, R1
  r[15] = (r[15][0], (r[15][1] << 4 & 0xff) | (r[15][1] >> 4))  # SWAP R15
  r[1] = r[15]                                                  # MOVE R1, R15
  r[15] = (r[15][0], r[15][1] & 0xe0)                           # CLR R15, #$1F
  r[9] = (r[9][0], r[9][1] ^ r[15][1])                          # XOR R9, R15
  r[1] = (r[1][0], r[1][1] & 0x01)                              # CLR R1, #$FE
  r[14] = (r[14][0], r[14][1] ^ r[1][1])                        # XOR R14, R1
  r[9] = (r[14][1], r[9][1])                                    # MLH R9, R14
  return r[9]                                                   # RET R8

In other words, I set up a Python array of tuples like the 5100’s registers and
carefully manipulated them step-by-step in the same way the machine
instructions from the CRC update routine do. I still have no idea how this code
works, and there’s no reason I’ll ever need to learn.

Time to find out whether my decoding has succeeded:

Sure enough. Just like that, the IBM 5100 non-executable APL ROS is
“officially” recovered as the 96 KiB at the beginning of the binary data
“undumped” by our ensemble of neural networks. A slightly more complicated
exploration procedure was required to understand the layout of the raw
BASIC/common ROS data (see the data supplement for details), but
before long this was recovered as well.

Code used by this step:

• assembly_to_binary.py: Compile tally databases from
  Stage 10
  into binary data.
• finalise.sh: Assemble the final ROS data files from the “raw”
  binary files derived from the tally databases.
• binary_check.py: Perform the 5100’s own 16-bit CRC
  integrity check on binary data.

Commands:

# Compile tally databases into "raw" binary data files for the APL and
# BASIC/common non-executable ROS.
./assembly_to_binary.py assembly_APL_LROS_* > binary_APL_LROS_raw_undump.bin
./assembly_to_binary.py assembly_BCom_* > binary_BCom_raw_undump.bin

# Extract actual ROS data from the raw files.
./finalise.sh

# Validate the contents of the final recovered data.
./binary_check.py binary_APL_LROS.bin
./binary_check.py binary_BCom.bin

Epilogue: what if we had tried to do all of this with IBM 5100s?

Well, it would have taken a heck of a lot longer—and about a tonne and a
half of the machines.

To start, let’s take one of the simpler neural networks used in this
project—the ordinary feed-forward neural network with three hidden layers of
size 50, 40, and 30. Input images have 29 * 16 = 464 pixels, so if we only
count multiplications (and not additions or other operations), a single
classification operation for a single digit requires

  464       50       40       30
x  50     x 40     x 30     x 16
-----     ----     ----     ----
23200  +  2000  +  1200  +   480  =  26880 floating point multiplications.

We have 1,010,070 word images in our dataset and four digits per word image.
Evaluating all of the digits therefore requires the computer to multiply over
108 billion times.

The IBM 5100’s processor runs at just under 2 MHz, and if we assume that each
instruction takes one cycle (which I suspect is unlikely), that’s 500ns per
operation. The processor’s arithmetic unit only handles eight-bit
integers—larger ones must be processed piecemeal—and it possesses no
integer multiplication or division operations. Don’t even think about floating
point numbers: you do all of that in software. How? Well, some Googling
suggests that similarly-impoverished microcontroller programmers sometimes use
a technique called Horner’s method,
which can do floating point multiplication and division using only additions
and bit-shifts.
This article
shows a microcontroller implementation of multiplication in 32 operations,
although it’s really multiplication by one hard-coded factor—to change the
factor, you would need to rewrite the code. Very well, though, let’s generously
consider 32 operations a rule-of-thumb (under)estimate of how many operations a
5100 spends to do a floating point multiply, or, in other words, 16
microseconds.

Under these very friendly assumptions, classification of a single digit will
take 16us * 26880 = 430.1ms, a bit under half a second. To classify the entire
dataset of over four million digits, then, a 5100 would take a little more than
twenty days to accomplish the multiplications alone. This only applies, though,
if we have a fully-trained neural network; what we also need to know is how
long it must have taken our 5100 to arrive at this network in the first place.
The training regime in labels_classification.py
specifies that our learning procedure carry out up to 10,000 iterations of
training on 5,000-image batches sampled from the dataset, so in addition to
the million word images to classify at the end, we need to think about the
50,000,000 word images the computer must process during training. That many
images takes

20.11 days * 50000000 / 1010070 = 988.88 days = 2.73 years

of multiplying, although our training procedure might stop sooner if it senses
that it’s doing particularly well. Still, we’ve been pretty generous in our
estimates, so we can probably hedge a bit in the opposite direction too.

So far our multiplication count has only concerned the process of evaluating an
image with a classifier—what’s known in neural networks as the “forward
pass”. To actually update the network’s parameters so that it learns to make
better predictions, you have to compare its classifications to the actual
ground truth labels from the dataset, determine how wrong the network was in
its classifications, and then go back and tweak all of the network parameters
so that they won’t be quite so wrong next time. This is called
backpropagation or the
“backward pass”, and we had better account for it in our estimate, too. For
this, let’s just multiply our 2.73 year tally by two, giving 5.45 years. We
mustn’t forget to add on the final 20-day classification for all of our data,
which brings us up to 5.47.

Of course, I never trained just one neural network—thanks to continued
tweaking and the “inbreeding” of Stage 9, I wound up training about
49 of them. For the 5100, we’re now a month and some change shy of 270 years.

Let’s change units. The 5100 was introduced late in the summer of 1975—about
44 years ago. If we had bought some 5100s when Rod Stewart’s “Sailing” topped the UK charts and set them
all right to work, we would have needed (270 ÷ 44) just over six of them
running flat-out around-the-clock to be done today.

Recall that the 49 networks weren’t all like the one we’ve just examined—we
did switch to a more complicated network and a different learning system
altogether at one point, so perhaps we should update our estimate. Our new
network’s convolutional layer alone would have required something like

29 * 16 * 3 * 3 * 16 = 66816

multiplications on its own to process a single image. The subsequent
max-pooling operation would then reduce the result to a 14 * 2 * 16 = 448-value
quantity, so the new number of multiplications would become

            448       48       38
          x  48     x 38     x 16
          -----     ----     ----
66816  +  21504  +  1824  +   608  =  90752

A classification of all of the word images now takes just under 68 days on the
5100, but I guess it’s worth it for the improved accuracy.

Switching to Keras for the new network meant rewriting the training code to
some degree. I didn’t pay very close attention as I was writing it, but where
we had previously processed 50,000,000 word images during training, the new
Stage 9 training methods
were examining 312,000,000 of them. This would occupy the 5100 for about eleven
days more than 115 years; or, for the 26 networks I trained in this way, nearly
2,991 years altogether. Or, if you preferred in 1975, you could start the work
on 68 5100s running in parallel and receive the answer today. (Let’s not
forget to allocate an additional three 5100s to tackle the 23 earlier networks,
which were mostly much simpler.)

I haven’t been able to find out how many IBM 5100s were built. This timeline cites a New York Times article claiming that IBM
shipped 6,000 “desktop computers” in 1980, a year before it unveiled the IBM PC
and a time when multiple options like the 5110 and 5120 were available for
sale. Prices were similar to the 5100’s, though, so let’s say that IBM achieved
similar sales from ’75 through ’78, when the 5100 was discontinued. That’s
18,000 machines total. I suspect this may be an overestimate.

If we take the 44 years spent by 71 machines and spread it out across the
entire fleet, our project would require all 5100 owners to donate

44 * 365.25 * 71 / 18000 = 63.39 days

of continuous operation to our project. That’s not too bad, but let’s respect
the eight-hour workday: a bit over 190 days, or 73% of an American work year.

How much use did an average 5100 get over its lifespan? 190 full work days
sounds fairly normal; maybe an underestimate. Remember though that I’ve made a
lot of other low estimates. If I’m under by a factor of 10 through a
combination of underestimates (and I suspect the estimated number of cycles
needed by floating-point multiply could be that far off on its own), then we
need 7.3 work years per machine from the whole fleet, and I doubt there were
more than a few hundred IBM 5100s in regular use in 1983.

Did my project to recover the non-executable ROS then use more compute
(specifically, multiplications) than all the 5100s ever made have ever used in
their entire history? I don’t really know, but I like my odds.

Acknowledgements

• Christian Corti’s excellent IBM 5110 technical webpage (German,
  English)
  as well as helpful remarks from Christian over email.
• The source code for Christian’s IBM 5110 emulator (available at the same link, or try it in your web browser), which helpfully
  clarified what certain IBM 5100/5110 instructions really did.
• bitsavers.org, for its archived IBM 5100 and IBM 5110 technical
  documentation.
• Andrew M. for technical advice.

Who, where, when

Tom Stepleton, London, 2019-06-27

If you’d like to add a comment of your own and make this document even
longer, edit this file and copy the template that follows to just above this
text. When you’re done, send a pull request against head on this repository and
I’ll merge it, provided it’s not objectionable. Should work for a low-traffic
discussion (but then will there be any traffic at all?).

Here’s the title of my comment

by @stepleton, 2019-06-27 12:34 BST

The body of the comment goes here. This is a pretty practical way to host a
discussion forum, for sure! Just remember that the most important thing is to
include the backslash character after your title.