Tag: Machine Learning

The Sweet Learning Computer: Learning Ladder

The board for the ladder game with the piece on the bottom rung
The Ladder board. Image by Paul Curzon

Can a machine learn from its mistakes, until it plays a game perfectly, just by following rules? Donald Michie worked out a way in the 1960s. He made a machine out of matchboxes and beads called MENACE that did just that. Our version plays the game Ladder and is made of cups and sweets. Punish the machine when it loses by eating its sweets!

Let’s play the game, Ladder. It is played on a board like a ladder with a single piece (an X) placed on the bottom rung of the ladder. Players take it in turns to make a move, either 1, 2 or 3 places up the ladder. You win if you move the piece to the top of the ladder, so reach the target. We will play on a ladder with 10 rungs as on the right (but you can play on larger ladders).

To make the learning machine, you need 9 plastic cups and lots of wrapped sweets coloured red, green and purple. Spread out the sheets showing the possible board positions (see below) and place a cup on each. Put coloured sweets in each cup to match the arrows: for most positions there are red, green and purple arrows, so you put a red, green and purple sweet in those cups. Once all cups have sweets matching the arrows, your machine is ready to play (and learn).

The machine plays first. Each cup sits on a possible board position that your machine could end up in. Find the cup that matches the board position the game is in when it is its go.  Shut your eyes and take a sweet at random from that cup, placing it next to the cup. Make the move indicated by the arrow of that colour. Then the machine’s human opponent makes a move. Once they have moved the machine plays in the same way again, finding the position and taking a sweet to decide its move. Keep playing alternately like this until someone wins. If the machine ends up in a position with no sweets in that cup, then it resigns.

The possible board positions showing possible moves with coloured arrows.
The 9 board positions with arrows showing possible moves. Place a cup on each board position with sweets corresponding to the arrows. Image by Paul Curzon

If the machine loses, then eat the sweet corresponding to the last move it made. It will never make that mistake again! Win or lose, put all the other sweets back.

The initial cup for board position 8, with a red and purple sweet.
The initial cup for board position 8, with a red and purple sweet. Image by Paul Curzon

Now, play lots of games like that, punishing the machine by eating the sweet of its last move each time it loses. The machine will play badly at first. It’s just making moves at random. The more it loses, the more sweets (losing moves) you eat, so the better it gets. Eventually, it will play perfectly. No one told it how to win – it learnt from its mistakes because you ate its sweets! Gradually the sweets left encode rules of how to win.

Try slightly different rules. At the moment we just punish bad moves. You could reward all the moves that led to it by adding another sweet of the same colour too. Now the machine will be more likely to make those moves again. What other variations of rewards and punishments could you try?

Why not write a program that learns in the same way – but using data values in arrays to represent moves instead of sweets. Not so yummy!

– Paul Curzon, Queen Mary University of London

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Google’s “PigeonRank” and arty-pigeon intelligence

pigeon
Pigeon, possibly pondering people’s photographs.
Image by Davgood Kirshot from Pixabay

On April Fool’s Day in 2002 Google ‘admitted’ to its users that the reason their web search results appeared so quickly and were so accurate was because, rather than using automated processes to grab the best result, Google was actually using a bank of pigeons to select the best results. Millions of pigeons viewing web pages and pecking picking the best one for you when you type in your search question. Pretty unlikely, right?

In a rather surprising non-April Fool twist some researchers decided to test out how well pigeons can distinguish different types of information in hospital photographs.

Letting the pigeons learn from training data
They trained pigeons by getting them to view medical pictures of tissue samples taken from healthy people as well as pictures taken from people who were ill. The pigeons had to peck one of two coloured buttons and in doing so learned which pictures were of healthy tissue and which were diseased. If they pecked the correct button they got an extra food reward.

Seeing if their new knowledge is ‘generalisable’ (can be applied to unfamiliar images)
The researchers then tested the pigeons with a fresh set of pictures, to see if they could apply their learning to pictures they’d not seen before. Incredibly the pigeons were pretty good at separating the pictures into healthy and unhealthy, with an 80 per cent hit rate. Doctors and pathologists* probably don’t have to worry too much about pigeons stealing their jobs though as the pigeons weren’t very good at the more complex cases. However this is still useful information. Researchers think that they might be able to learn something, about how humans learn to distinguish images, by understanding the ways in which pigeons’ brains and memory works (or don’t work). There are some similarities between pigeons’ and people’s visual systems (the ways our eyes and brains help us understand an image).

[*pathology means the study of diseases. A pathologist is a medical doctor or clinical scientist who might examine tissue samples (or images of tissue samples) to help doctors diagnose and treat diseases.]

How well can you categorise?

This is similar to a way that some artificial intelligences work. A type of machine learning called supervised learning gives an artificial intelligence system a batch of photographs labelled ‘A’, e.g. cats, and a different batch of photographs labelled ‘B’, e.g. dogs. The system makes lots of measurements of all the pictures within the two categories and can use this information to decide if a new picture is ‘CAT’ or ‘DOG’ and also how confident it is in saying which one.

Can pigeons tell art apart?

Pigeons were also given a button to peck and shown artworks by Picasso or Monet. At first they’d peck the button randomly but soon learned that they’d get a treat if they pecked at the same time they were shown a Picasso. When a Monet appeared they got no treat. After a while they learned to peck when they saw the Picasso artworks and not peck when shown a Monet. But what happened if they were shown a Monet or Picasso painting that they hadn’t seen before? Amazingly they were pretty good, pecking for rewards when the new art was by Picasso and ignoring the button when it was a new Monet. Art critics can breathe a sigh of relief though. If the paintings were turned upside down the pigeons were back to square one and couldn’t tell them apart.

Like pigeons, even humans can get this wrong sometimes. In 2022 an art curator realised that a painting by Piet Mondrian had been displayed upside down for 75 years… I wonder if the pigeons would have spotted that.

– Jo Brodie, Queen Mary University of London

Share this post

Part of a series of ‘whimsical fun in computing’ to celebrate April Fool’s (all month long!).

Find out about some of the rather surprising things computer scientists have got up to when they're in a playful mood.

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Software for Justice

by Paul Curzon, Queen Mary University of London (originally published in 2011)

A jury is given misleading information in court by an expert witness. An innocent person goes to prison as a result. This shouldn’t happen, but unfortunately it does and more often than you might hope. It’s not because the experts or lawyers are trying to mislead but because of some tricky mathematics. Fortunately, a team of computer scientists at Queen Mary, University of London are leading the way in fixing the problem.

The Queen Mary team, led by Professor Norman Fenton, is trying to ensure that forensic evidence involving probability and statistics can be presented without making errors, even when the evidence is incredibly complex. Their solution is based on specialist software they have developed.

Digital fingerprint image by ar130405 from Pixabay

Many cases in courts rely on evidence like DNA and fibre matching for proof. When police investigators find traces of this kind of evidence from the crime scene they try to link it to a suspect. But there is a lot of misunderstanding about what it means to find a match. Surprisingly, a DNA match between, say, a trace of blood found at the scene and blood taken from a suspect does not mean that the trace must have come from the suspect.

Forensic experts talk about a ‘random match probability’. It is just the probability that the suspect’s DNA matches the trace if it did not actually come from him or her. Even a one-in-a-billion random match probability does not prove it was the suspect’s trace. Worse, the random match probability an expert witness might give is often either wrong or misleading. This can be because it fails to take account of potential cross-contamination, which happens when samples of evidence accidentally get mixed together, or even when officers leave traces of their own DNA from handling the evidence. It can also be wrong due to mistakes in the way the evidence was collected or tested. Other problems arise if family members aren’t explicitly ruled out, as that makes the random match probability much higher. When the forensic match is from fibre or glass, the random match probabilities are even more uncertain.

DNA helix image by Gerd Altmann from Pixabay

The potential to get the probabilities wrong isn’t restricted to errors in the match statistics, either. Suppose the match probability is one in ten thousand. When the experts or lawyers present this evidence they often say things like: “The probability that the trace came from anybody other than the defendant is one in ten thousand.” That statement sounds OK but it isn’t true.

The problem is called the prosecutor fallacy. You can’t actually conclude anything about the probability that the trace belonged to the defendant unless you know something about the number of potential suspects. Suppose this is the only evidence against the defendant and that the crime happened on an island where the defendant was one of a million adults who could have committed the crime. Then the random match probability of one in ten thousand actually means that about one hundred of those million adults match the trace. So the probability of innocence is ninety-nine out of a hundred! That’s very different from the one in ten thousand probability implied by the statement given in court.

Norman Fenton’s work is based around a theorem, called Bayes’ theorem, which gives the correct way to calculate these kinds of probabilities. The theorem is over 250 years old but it is widely misunderstood and, in all but the simplest cases is very difficult to calculate properly. Most cases include many pieces of related evidence – including evidence about the accuracy of the testing processes. To keep everything straight, experts need to build a model called a Bayesian network. It’s like a graph that maps out different possibilities and the chances that they are true. You can imagine that in almost any court case, this gets complicated awfully quickly. It is only in the last 20 years that researchers have discovered ways to perform the calculations for Bayesian networks, and written software to help them. What Norman and his team have done is develop methods specifically for modelling legal evidence as Bayesian networks in ways that are understandable by lawyers and expert witnesses.

Norman and his colleague Martin Neil have provided expert evidence (for lawyers) using these methods in several high-profile cases. Their methods help lawyers to determine the true value of any piece of evidence – individually or in combination. They also help show how to present probabilistic arguments properly.

Unfortunately, although scientists accept that Bayes’ theorem is the only viable method for reasoning about probabilistic evidence, it’s not often used in court, and is even a little controversial. Norman is leading an international group to help bring Bayes’ theorem a little more love from lawyers, judges and forensic scientists. Although changes in legal practice happen very slowly (lawyers still wear powdered wigs, after all), hopefully in the future the difficult job of judging evidence will be made easier and fairer with the help of Bayes’ theorem.

If that happens, then thanks to some 250 year-old maths combined with some very modern computer science, fewer innocent people will end up in jail. Given the innocent person in the dock could one day be you, you will probably agree that’s a good thing.

This post was originally published in 2011 on our old CS4FN website and a copy can also be found on pages 18 and 19 in the Alan Turing issue of the CS4FN magazine, issue 14. You can download a free PDF copy of the magazine below along with our entire back issue of magazines and booklets at our downloads site.

Further reading in justice

Edie Schlain Windsor and same sex marriage – Edie was a computer scientist whose marriage to another woman was deemed ineligible for certain rights provided (at that time) only in a marriage between a man and a woman. She fought for those rights and won.

Edie Schlain Windsor and same sex marriage

Related Magazine …

EPSRC supports this blog through research grant EP/W033615/1.

Your own electrical sea

A silhouetted man holding up an umbrella as a lightning storm rages around him against a slate grey sky. He is holding a briefcase.
Image by Gerd Altmann from Pixabay

Sensing your movements

You can’t see them, but there are waves of electricity flowing around you right now. Electricity leaks out of power lines, lights, computers and every other gadget nearby. Soon a computer may be able to track your movements by following the ripples you make in your own electromagnetic sea. Scientists at Microsoft Research in the US have figured out a way to sense the position of someone’s body by using it as an antenna.

Why would you want a computer to do this? So that you could control it just by moving your body. This is already possible with systems like the Xbox Kinect, but that works by tracking you with a camera, so you have to stay in front of it or it loses you. A system that uses your body as an electric antenna could follow you throughout a room, or even a whole building.

First you need an instrument that can sense the changes you make in your own electrical field as you move around. In the future, the researchers would like this to be a little gadget you could carry in your pocket, but the technology isn’t quite small enough yet. For this experiment, they used a wireless data sensor that’s about twice the size of a mobile phone. The volunteers wore it in a little backpack. All the electrical data it picked up were transmitted to a computer that would run the calculations to figure out how the user was moving.

Get moving

In their first experiment, the researchers wanted to find out whether their gadget could sense what movements their volunteers made. To do this, they had the volunteers take their sensing devices home and use them in two different rooms: the kitchen and the living room. Those two rooms are usually different from one another in interesting ways. Living rooms are usually big open spaces with only a few small appliances in them. Kitchens, though, are often small, and cram lots of big electricals in the same room. The electrical sensors would really have to work hard to make sense through the interference.

Once the experiment was ready to go, each volunteer ran through a series of twelve movements. Their exercises included waving, bending over, stepping to the right or left, and even a bit of kicking and punching. The sensor would collect the electrical readings and then send them to a laptop. What happened after that was a bit of artificial intelligence. The researchers used the first few rounds of movements to train the computer to recognise the electrical signatures of each movement. Later on, it was the computer’s job to match up the readings it got through the sensor to the gestures it already knew. That’s a technique called machine learning.

One of the surprising things that made the sensor’s job tougher was that electrical appliances change what they are doing more often than you think. Maybe a refrigerator switches its cooling on and off, or a computer starts up its hard disk. Each of these changes means a change in the electrical waves flowing through the room, and the computer had to recognise each gesture through the changing noise.

Where’d you go?

The next step for the system was to see if it could recognise which room someone was standing in when they performed the movements. There were now eight locations to keep straight – two locations in one large room and six more scattered throughout the house. It was up to the system to learn the electrical signature for each room, as well as the signature for each movement. That’s pretty tough work. But it worked well – really well. The system was able to guess the room almost 100% of the time. What’s more, they found that the location tracking even worked on the data from the first experiment, when they were only supposed to be looking at movements. But the electrical signatures of each room were built into that data too, and the system was expert enough to pick them out.

Putting it all together

In the future the researchers are hoping that their gadgets will become small enough to carry around with you wherever you are in a building. This could allow you to control computers within your house, or switch things on and off just by making certain movements. The fact that the system can sense your location might mean that you could use the same gestures to do different things. Maybe in the living room a punch would turn on the television, but in the kitchen it would start the microwave. Whatever the case, it’s a great way to use the invisible flow of energy all around us.

– Paul Curzon, Queen Mary University of London

 Linked Magazines

This article was originally published on CS4FN and can also be found on pages 14-15 of CS4FN Issue 15, Does your computer understand you?, which you can download as a PDF. All of our free material can be downloaded here: https://cs4fndownloads.wordpress.com/

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

 

Machines Inventing Musical Instruments

cupped hands in dark Image by Milada Vigerova from Pixabay
Image by Milada Vigerova from Pixabay 

Machine Learning is the technology driving driverless cars, recognising faces in your photo collection and more, but how could it help machines invent new instruments? Rebecca Fiebrink of Goldsmiths, University of London is finding out.

Rebecca is helping composers and instrument builders to design new musical instruments and giving them new ways to perform. Her work has also shown that machine learning provides an alternative to programming as a way to quickly turn design ideas into prototypes that can be tested.

Suppose you want to create a new drum machine-based musical instrument that is controlled by the wave of a hand: perhaps a fist means one beat, whereas waggling your fingers brings in a different beat. To program a prototype of your idea, you would need to write code that could recognize all the different hand gestures, perhaps based on a video feed. You would then have some kind of decision code that chose the appropriate beat. The second part is not too hard, perhaps, but writing code to recognize specific gestures in video is a lot harder, needing sophisticated programming skills. Rebecca wants even young children to be able to do it!

How can machine learning help? Rebecca has developed a machine learning program with a difference. It takes sensor input – sound, video, in fact just about any kind of sensor you can imagine. It then watches, listens…senses what is happening and learns to associate what it senses with different actions it should take. With the drum machine example, you would first select one of the kinds of beats. You then make the gesture that should trigger it: a fist perhaps. You do that a few times so it can learn what a fist looks like. It learns that the patterns it is sensing are to be linked with the beat you selected. Then you select the next beat and show it the next gesture – waggling your fingers – until it has seen enough examples. You keep doing this with each different gesture you want to control the instrument. In just a few minutes you have a working machine to try. It is learning by example how the instrument you are wanting works. You can try it, and then adjust it by showing it new examples if it doesn’t quite do what you want.

It is learning by example how
the instrument you are wanting works.

Rebecca realised that this approach of learning by example gives a really powerful new way to support creativity: to help designers design. In the traditional ways machine learning is used, you start with lots of examples of the things that you want it to recognize – lots of pictures of cats and dogs, perhaps. You know the difference, so label all these training pictures as cats or dogs, so it knows which to form the two patterns from. Your aim is for the machine to learn the difference between cat and dog patterns so it can decide for itself when it sees new pictures.

When designing something like a new musical instrument though, you don’t actually know exactly what you want at the start. You have a general idea but will work out the specifics as you go. You tinker with the design, trying new things and keeping the ideas that work, gradually refining your thoughts about what you want as you refine the design of the instrument. The machine learning program can even help by making mistakes – it might not have learnt exactly what you were thinking but as a result makes some really exciting sound you never thought of. You can then explore that new idea.

One of Rebecca’s motivations in wanting to design new instruments is to create accessible instruments that people with a wide range of illness and disability can play. The idea is to adapt the instrument to the kinds of movement the person can actually do. The result is a tailored instrument perfect for each person. An advantage of this approach is you can turn a whole room, say, into an instrument so that every movement does something: an instrument that it’s impossible not to play. It is a play space to explore.

Playing an instrument suddenly really is just playing.

Paul Curzon, Queen Mary University of London based on a 2016 talk by Rebecca Fiebrink

More on …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos