Hallucinating chatbots

Why can’t you trust what an AI says?

by Paul Curzon, Queen Mary University of London

postcards of cuba in a rack
Image by Sunrise from Pixabay

Chatbots that can answer questions and write things for you are in the news at the moment. These Artificial Intelligence (AI) programs are very good now at writing about all sorts of things from composing songs and stories to answering exam questions. They write very convincingly in a human-like way. However, one of the things about them is that they often get things wrong. Apparently, they make “facts” up or as some have described it “hallucinate”. Why should a computer lie or hallucinate? What is going on? Writing postcards will help us see.

Write a postcard

We can get an idea of what is going on if we go back to one of the very first computer programs that generated writing. It was in the 1950s and written by Christopher Strachey a school teacher turned early programmer. He wrote a love letter writing program but we will look at a similar idea: a postcard writing program.

Postcards typically might have lots of similar sentences, like “Wish you were here” or “The weather is lovely”, “We went to the beach” or “I had my face painted with butterflies”. Another time you might write things like: The weather is beautiful”, “We went to the funfair” or “I had my face painted with rainbows”. Christopher Strachey’s idea was to write a program with template sentences that could be filled in by different words: “The weather is …”, “We went to the …”, “I had my face painted with …”. Then the program picks some sentence templates at random, and then picks words at random to go in their slots. In this way, applied to postcard writing it can write millions of unique postcards. It might generate something like the following, for example (where I’ve bolded the words it filled in):

Dear Gran,

I’m on holiday in Skegness. I’ve had a wonderful time.  The weather is sunny,   We went to the beach. I had my face painted with rainbows. I’ve eaten lots strawberry ice cream. Wish you were here!

Lots of love from Mo

but the next time you ask it to it will generate something completely different.

Do it yourself

You can do the same thing yourself. Write lots of sentences on strips of card, leaving gaps for words. Give each gap a number label and note whether it is an adjective (like ‘lovely’ or ‘beautiful’) or a noun (like ‘beach’ or ‘funfair’, ‘butterflies’ or ‘rainbows’). You could also have gaps for verbs or adverbs too. Now create separate piles of cards to fit in each gap. Write the number that labels the gap on one side and different possible words of the right kind for that gap on the other side of the cards. Then keep them in numbered piles.

To generate a postcard (the algorithm or steps for you to follow), shuffle the sentence strips and pick three or four at random. Put them on the table in front of you to spell out a message. Next, go to the numbered pile for each gap in turn, shuffle the cards in that pile and then take one at random. Place it in the gap to complete the sentence. Do this for each gap until you have generated a new postcard message. Add who it is to and from at the start and end. You have just followed the steps (the algorithm) that our simple AI program is following.

Making things up

When you write a postcard by following the steps of our AI algorithm, you create sentences for the postcard partly at random. It is not totally random though, because of the templates and because you chose words to write on cards for each pile that make sense there. The words and sentences are about things you could have done – they are possible – but that does not mean you did do them!

The AI makes things up that are untrue but sound convincing because even though it is choosing words at random, they are appropriate and it is fitting them into sentences about things that do happen on holiday. People talk of chatbots ‘hallucinating’ or ‘dreaming’ or ‘lying’ but actually, as here, they are always just making the whole thing up just as we are when following our postcard algorithm. They are just being a little more sophisticated in the way that they invent their reality!

Our simple way of generating postcards is far simpler than modern AIs, but it highlights some of the features of how AIs are built. There are two basic parts to our AI. The template sentences ensure that what is produced is grammatical. They provide a simple ‘language model‘: rules of how to create correct sentences in English that sound like a human would write. It doesn’t write like Yoda :

“Truly wonderful, the beach is.”

though it could with different templates.

The second part is the sets of cards that fit the gaps. They have to fit the holes left in the templates – only nouns in the noun gaps, adjectives in the adjectives gap, and also fit

Given a set of template sentences about what you might do on holiday, the cards provide data to train the AI to say appropriate things. The cards for the face paining noun slot need to be things that might be painted on your face. By providing different cards you would change the possible sentences. The more cards the more variety in the sentences it writes.

AIs also have a language model, the rules of the language and which words go sensibly in which places in a sentence. However, they also are trained on data that gives the possibilities of what is actually written. Rather than a person writing templates and thinking up words it is based on training data such as social media posts or other writing on the Internet and what is being learnt from this data is the likelihood of what words come next, rather than just filling in holes in a template. The language model used by AIs is also actually just based on the likelihood of words appearing in sentences (not actual grammar rules).

What’s the chances of that?

So, the chatbots are based on the likelihood of words appearing and that is based on statistics. What do we mean by that? We can add a simple version of it to our Postcard AI but first we would need to collect data. How often is each face paint design chosen at seaside resorts? How often do people go to funfairs when on holiday. We need statistics about these things.

As it stands any word we add to the stack of cards is just as likely to be used. If we add the card maggots to the face painting pile (perhaps because the face painter does gruesome designs at Halloween) then the chatbot could write

“I had my face painted with maggots”.

and that is just as likely as it writing

“I had my face painted with butterflies”.

If the word maggots is not written on a card it will never write it. Either it is possible or it isn’t. We could make the chatbot write things that are more realistic, however, by adding more cards of words that are about things that are more popular. So, if in every 100 people having their face painted, almost a third, 30 people choose to have butterflies painted on their face, then we create 30 cards out of 100 in the pack with the word BUTTERFLY on (instead of just 1 card). If 5 in a 100 people choose the rainbow pattern then we add five RAINBOW cards, and so on. Perhaps we would still have one maggot card as every so often someone who likes grossing people out picks it even on holiday. Then, over all the many postcards written this way by our algorithm, the claims will match statistically the reality of what humans would write overall if they did it themselves.

As a result, when you draw a card for a sentence you are now more likely to get a sentence that is true for you. However, it is still more likely to be wrong about you personally than right (you may have had your face painted with butterflies but 70 of the 100 cards still say something else). It is still being chosen by chance and it is only the overall statistics for all people who have their face painted that matches reality not the individual case of what is likely true for you.

Make it personal

How could we make it more likely to be right about you? You need to personalise it. Collect and give it (ie train it on) more information about you personally. Perhaps you usually have a daisy painted on your face because you like daisies (you personally choose a daisy pattern 70% of the time). Sometimes you have rainbows (20% of the time). You might then on a whim choose each of 10 other designs including the butterfly maybe 1 in a hundred times. So you make a pile of 70 DAISY cards, 20 RAINBOW cards and 1 card for each of the other designs, Now, its choices, statistically at least, will match yours. You have trained it about yourself, so it now has a model of you.

You can similarly teach it more about yourself generally, so your likely activities, by adding more cards about the things you enjoy – if you usually choose chocolate or vanilla ice cream then add lots of cards for CHOCOLATE and lots for VANILLA, and so on. The more cards the postcard generator has of a word, the more likely it is to use that word. By giving it more information about yourself, it is more likely to be able to get things about you right. However, it is of course still making it up so, while it is being realistic, on any given occasion it may or may not match reality that time.

Perfect personalisation

You could go a step further and train it on what you actually did do while on this holiday, so that the only cards in the packs are the ones you did actually do on this holiday. (You ate hotdogs and ice cream and chips and … so there are cards for HOTDOG, ICE CREAM, CHIPS …). You had one vanilla ice cream, two chocolate and one strawberry so have that number of each ice cream card. If it knows everything about you then it will be able to write a postcard that is true! That is why companies behind AIs want to collect every detail of your life. The more they know about you the more they get things right about you and so predict what you will do in future too.

Probabilities from the Internet

The modern chatbots work by choosing words at random based on how likely they are in a similar way to our personalised postcard writer. They pick the most likely words to write next based on probabilities of those words coming next in the data they have been trained on. Their training data is often conversations from the Internet. If the word is most likely to come next in all that training data, then the chatbot is more likely to use that word next. However, that doesn’t make the sentence it comes up with definitely true any more than with our postcard AI.

You can personalise the modern AIs too, by giving them more accurate information about yourself and then they are more likely to get what they write about you right. There is still always a chance of them picking the wrong words, if it is there as a possibility though, as they are still just choosing to some extent at random.

Never trust a chatbot

Artificial Intelligences that generate writing do not hallucinate just some of the time. They hallucinate all of the time, just with a big probability of getting it right. They make everything up. When they get things right it is just because the statistics of the data they were trained on made those words the most likely ones to be picked to follow what went before. Just as the Internet is full of false things, an Artificial Intelligence can get things wrong too.

If you use them for anything that matters, always double check that they are telling you the truth.

More on …

Related Magazines …

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

Protecting your fridge

by Jo Brodie and Paul Curzon, Queen Mary University of London

Ever been spammed by your fridge? It has happened, but Queen Mary’s Gokop Goteng and Hadeel Alrubayyi aim to make it less likely…

Image by Gerd Altmann from Pixabay

Gokop has a longstanding interest in improving computing networks and did his PhD on cloud computing (at the time known as grid computing), exploring how computing could be treated more like gas and electricity utilities where you only pay for what you use. His current research is about improving the safety and efficiency of the cloud in handling the vast amounts of data, or ‘Big Data’, used in providing Internet services. Recently he has turned his attention to the Internet of Things.

It is a network of connected devices, some of which you might have in your home or school, such as smart fridges, baby monitors, door locks, lighting and heating that can be switched on and off with a smartphone. These devices contain a small computer that can receive and send data when connected to the Internet, which is how your smartphone controls them. However, it brings new problems: any device that’s connected to the Internet has the potential to be hacked, which can be very harmful. For example, in 2013 a domestic fridge was hacked and included in a ‘botnet’ of devices which sent thousands of spam emails before it was shut down (can you imagine getting spam email from your fridge?!)

A domestic fridge was hacked
and included in a ‘botnet’ of devices
which sent thousands of spam emails
before it was shut down.

The computers in these devices don’t usually have much processing power: they’re smart, but not that smart. This is perfectly fine for normal use, but to run software to keep out hackers, while getting on with the actual job they are supposed to be doing, like running a fridge, it becomes a problem. It’s important to prevent devices from being infected with malware (bad programs that hackers use to e.g., take over a computer) and work done by Gokop and others has helped develop better malwaredetecting security algorithms which take account of the smaller processing capacity of these devices.

One approach he has been exploring with PhD student Hadeel Alrubayyi is to draw inspiration from the human immune system: building artificial immune systems to detect malware. Your immune system is very versatile and able to quickly defend you against new bugs that you haven’t encountered before. It protects you from new illnesses, not just illnesses you have previously fought off. How? Using special blood cells, such as T-Cells, which are able to detect and attack rogue cells invading the body. They can spot patterns that tell the difference between the person’s own healthy cells and rogue or foreign cells. Hadeel and Gokop have shown that applying similar techniques to Internet of Things software can outperform other techniques for spotting new malware, detecting more problems while needing less computing resources.

Gokop is also using his skills in cloud computing and data science to enhance student employability and explore how Queen Mary can be a better place for everyone to do well. Whether a person, organisation or smart fridge Gokop aims to help you reach your full potential!

More on …

Related Magazines …

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

The gender shades audit

by Jo Brodie, Queen Mary University of London

Face recognition technology is used widely, such as at passport controls and by police forces. What if it isn’t as good at recognising faces as it has been claimed to be? Joy Buolamwini and Timnit Gebru tested three different commercial systems and found that they were much more likely to wrongly classify darker skinned female faces compared to lighter or darker skinned male faces. The systems were not reliable.

Different skin tone cosmetics
Image by Stefan Schweihofer from Pixabay

Face recognition systems are trained to detect, classify and even recognise faces based on a bank of photographs of people. Joy and Timnit examined two banks of images used to train the systems and found that around 80 percent of the photos used were of people with lighter coloured skin. If the photographs aren’t fairly balanced in terms of having a range of people of different gender and ethnicity then the resulting technologies will inherit that bias too. The systems examined were being trained to recognise light skinned people.

The pilot parliaments benchmark

Joy and Timnit decided to create their own set of images and wanted to ensure that these covered a wide range of skin tones and had an equal mix of men and women (‘gender parity’). They did this using photographs of members of parliaments around the world which are known to have a reasonably equal mix of men and women. They selected parliaments both from countries with mainly darker skinned people (Rwanda, Senegal and South Africa) and from countries with mainly lighter skinned people (Iceland, Finland and Sweden).

They labelled all the photos according to gender (they had to make some assumptions based on name and appearance if pronouns weren’t available) and used a special scale called the Fitzpatrick scale to classify skin tones (see Different Shades below). The result was a set of photographs labelled as dark male, dark female, light male, light female, with a roughly equal mix across all four categories: this time, 53 per cent of the people were light skinned (male and female).

Testing times

Joy and Timnit tested the three commercial face recognition systems against their new database of photographs (a fair test of a wide range of faces that a recognition system might come across) and this is where they found that the systems were less able to correctly identify particular groups of people. The systems were very good at spotting lighter skinned men, and darker skinned men, but were less able to correctly identify darker skinned women, and women overall. The tools, trained on sets of data that had a bias built into them, inherited those biases and this affected how well they worked.

As a result of Joy and Timnit’s research there is now much more recognition of the problem, and what this might mean for the ways in which face recognition technology is used. There is some good news, though. The three companies made changes to improve their systems and several US cities have already banned the use of this technology in criminal investigations, with more likely to follow. People worldwide are more aware of the limitations of face recognition programs and the harms to which they may be (perhaps unintentionally) put, with calls for better regulation.

Different Shades
The Fitzpatrick skin tone scale is used by skin specialists to classify how someone’s skin responds to ultraviolet light. There are six points on the scale with 1 being the lightest skin and 6 being the darkest. People whose skin tone has a lower Fitzpatrick score are more likely to burn in the sun and are at greater risk of skin cancer. People with higher scores have darker skin which is less likely to burn and have a lower risk of skin cancer. A variation of the Fitzpatrick scale, with five points, is used to create the skin tone emojis that you’ll find on most messaging apps in addition to the ‘default’ yellow.

More on …

Related Magazines …

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

Playing the weighting game

by Paul Curzon, Queen Mary University of London

In the spotlight - bright lights dazzling in circles and stars
Image by Gerd Altmann from Pixabay

Imagine having a reality TV show where yet again Simon Cowell is looking for talent. This time it’s talent with a difference though, not stars to entertain us but ones with the raw ability to help find webpages. Yes, this time the budding stars are all words. Word Idol is here!

The format is simple. Each week Simon’s aim is to find talented words to create a new group: a group with star quality, a group with meaning. Like any talent competition, there are thousands of entries. Every word in every webpage out there wants to take part. They all have to be judged, but what do the specialist judges look for?

OK, we’re getting carried away. Simon Cowell may not be interested but there is big money in the idea. It’s a talent show that is happening all the time. The aim is to judge the words in each new webpage as it appears so that search engines can find it if ever someone goes looking. The real star of this show isn’t Simon Cowell but a Cambridge professor, Karen Spärck Jones. She came up with the way to judge words.

Karen worked out that to do this kind of judging a computer needs a thesaurus: a book of words. It just lists groups of words that mean the same thing. A computer, Karen realised, could use one to understand what words mean.

There is big money in the idea!

The fact that there are so many ways to say the same thing in human languages, makes it really hard for a computer to understand what we write. That is where a thesaurus comes in. If you ask a computer to search for web pages about whales, for example, it helps to know that, a page that talks about orcas is about whales too. Worse still, most words have more than one meaning, a fact that keeps crossword lovers in business.

Take the following example: “Leona is the new big star of the music business.”

The word ‘star’ here obviously means a celebrity, but how do you know? It could also mean a sun or a shape. The fact that it’s with the word ‘music’ helps you to work out which meaning is right even if you have no idea who or what Leona is. As Karen realised, a computer can also work out the intended meanings of words by the other words used with them. A thesaurus tells it what the critical groupings are, but what Karen wanted was a way a computer could work the thesaurus out for itself and now she had a way.

Her early approach was to write a program that takes lots and lots of documents and make lists of the words that keep appearing close together. If ‘music’ appears with ‘star’ lots then that is a new meaning. After building up a big collection of such lists of linked words, the program can then use it to decide which pages are talking about the same thing and so which ones to suggest when a search is done. So Karen had found the first way to judge whether a word has the right ‘talent’ to go in a group. The more often words appear together the higher the score or ‘weighting’ they should be given. Simple!

The only trouble is it doesn’t really work. That is where Karen’s big insight came. She realised that if two words appear together in a lot of different documents then, surprisingly perhaps, putting them together in a group isn’t actually that useful for finding documents! Do a search and they will just tell you that lots of web pages match. What you really want is to be told of the few web pages that contain the meaning you are looking for, not lots and lots that don’t.

The important word groupings are actually only in a small number of web pages. That suggests they give a very focused meaning. Word groups like that help you narrow down the search. So Karen now had a better way to judge word talent. Give high marks for pairs that do appear together but in as few web pages as possible. Rather than a talent show, it is more like a giant game of the quiz show Pointless where you win if you pick the words few other people did.

That idea was the big breakthrough and led to what is now called IDF weighting. It is the way to judge words, and is so good that it’s now used by pretty much every search engine out there. Playing the IDF weighting game may not make great TV but thanks to Karen it really does make for great web.

More on …

Related Magazines …

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

Collecting mini-beasts and pocket monsters

by Paul Curzon, Queen Mary University of London

A Pokemon creature int he grass
Image by  Ramadhan Notonegoro from Pixabay

Satoshi Tajiri created one of the biggest money-making media franchises of all time. It all started with his love of nature and, in particular, mini-beasts. It also eventually took gamers back into the fresh air.

As a child, Satoshi Tajiri, loved finding and collecting minibeasts, so spent lots of time outside, exploring nature. But, as Japan became more and more built up, his insect searching haunts disappeared. As the natural world disappeared he was drawn instead inside to video game arcades and those games became a new obsession. He became a super-fan of games and even created a game fanzine called Game Freak where he shared tips on playing different games. It wasn’t just something he sold to friends either: one issue sold 10,000 copies. An artist, Ken Sugimori, who started as a reader of the magazine, ultimately joined Satoshi, illustrating the magazine for him.

Rather than just writing about games, they wanted to create better ones themselves, so morphed Game Freak into a computer game company, ultimately turning it into one of the most successful ever. The cause of that success was their game Pokemon, designed by Satoshi with characters drawn by Ken. It took the idea of that first obsession, collecting minibeasts, and put it into a fun game with a difference.

It wasn’t about killing things, but moving around a game world searching for, taming and collecting monsters. The really creative idea, though, came from the idea of trading. There were two versions of the game and you couldn’t find all the creatures in your own version. To get a full set you had to talk to other people and trade from your collection. It was designed to be a social game from the outset.

It has been suggested that Satoshi is neuro-diverse. Whether he is or not, autistic people (as well as everyone else) found that Pokemon was a great way to make friends, something autistic people often find difficult. Pokemon, also became more than just a game, turning into a massive media franchise, with trading cards to collect, an animated series and a live action film. It also later sparked a second game craze when Pokemon Go was released. It combined the original idea with augmented reality, taking all those gamers back outside for real, searching for (virtual) beasts in the real world.

 

More on …

Related Magazines …

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

“Tlahcuilo”, a visual composer

by Rafael Pérez y Pérez of the Universidad Autónoma Metropolitana, México

A main goal of computational creativity research is to help us better understand how this essential human characteristic, creativity, works. Creativity is a very complex phenomenon that we only just understand: we need to employ all the tools that we have available to fully comprehend it. Computers are a powerful tool that can help us generate that knowledge and reflect on it. By building computer models of the processes we think are behind creativity, we can start to probe how creativity really works.

When you hear someone claiming that a computer agent, whether program, robot or gadget, is creative, the first question you should ask is: what have we learned? What does studying this agent help us to realise or discover about creativity that we did not know before? If you do not get a satisfactory answer, I would hardly call it a computer model of creativity. As well as being able to generate novel, and interesting or useful, things, a creative agent ought to fulfil other criteria: using its knowledge, creating knowledge and evaluating its own work.

Be knowledgeable!

Truly creative agents should draw on their own knowledge to build the things, such as art, that they create. They should use a knowledge-base, not just create things randomly. We aren’t, for example, interested in programs that arbitrarily pick a picture from the web, randomly apply a filter to it and then claim they have generated art.

Create knowledge!

A creative agent must be able to interpret its own creations in order to generate novel knowledge, and that knowledge should help it produce more original pieces. For example, a program that generates story plots must be able to read its own stories and learn from them, as well as from stories developed by others.

Evaluate it!

To deserve to be called creative, an agent also ought to be able to tell whether the things it has created are good or bad. It should be able to evaluate its work, as well as that produced by similar agents. It’s evaluation should also influence the way the generation process works. We don’t want joke creation programs that churn out thousands of ‘jokes’ leaving a human to decide which are actually funny. A creative agent ought to be able to do that itself!

Design me a design

At the moment few, if any, systems fulfil all these criteria. Nevertheless, I suggest they should be the main goals of those doing research in computational creativity. Over the past 20 years I’ve been studying computer models of creativity, aiming to do exactly that. My main research has focused on story generation, but with my team I’ve also developed programs that aim to create novel visual designs. This is the kind of thing someone developing new fabric, wallpaper or tiling patterns might do, for example. With Iván Guerrero and María González I developed a program called TLAHCUILO. It composes visual patterns based on photographs or an empty canvas. It employs geometrical patterns, like repeated shapes, in the picture and then uses them as the basis of a new abstract pattern.

The word “tlahcuilo” refers to painters and writers
in ancient México responsible for preserving
the knowledge and traditions of their people.

To build the system’s knowledge-base, we created a tool that human designers can use to do the same creative task. TLAHCUILO analyses the steps they follow as they develop a composition and registers what it has learnt in its knowledge base. For example, it might note the way the human designer adds elements to make the pattern symmetrical or to add balance. Once these approaches are in its knowledge base it can use them itself in its own compositions. This is a little like the way an apprentice to a craftsman might work, watching the Master at work, gradually building the experience to do it themselves. Our agent similarly builds on this experience to produce its own original outputs. It can also add its own pieces of work to its knowledge-base. Finally, it is able to assess the quality of its designs. It aims to meet the criteria set out above.

Design me a plot

One of TLAHCUILO’s most interesting characteristics is that it uses the same model of creativity that we used to implement MEXICA, our story plot generator. This allows us to compare in detail the differences and similarities between an agent that produces short-stories and an agent that produces visual compositions. We hope this will allow us to generalise our understanding.

Creativity research is a fascinating field. We hope to learn not just how to build creative agents but more importantly to understand what it takes to be a creative human.

More on …

Related Magazines …

Issue 22 Cover Creative Computing

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

Follow those ants

by Paul Curzon, Queen Mary University of London

Ants climbing on a mushroom obstacle course
Image by Puckel from Pixabay

Ant colonies are really good at adapting to changing situations: far better than humans. Sameena Shah wondered if Artificial Intelligence agents might do better by learning their intelligent behaviour from ants rather than us. She has suggested we could learn from the ants too.

Inspired by staring at ants adapting to new routes to food in the mud as a child, and then later as adult ants raided her milk powder, Sameena Shah studied for her PhD how a classic problem in computer science, that of finding the shortest path between points in a network, is solved by ant colonies. For ants this involves finding the shortest paths between food and the nest: something they are very good at. When foraging ants find a source of food they leave a pheromone (i.e., scent) trail as they return, a bit like Hansel and Gretel leaving a trail of breadcrumbs. Other ants follow existing trails to find the food as directly as possible, leaving their own trails as they do. Ants mostly follow the trail containing most pheromone, though not always. Because shorter paths are followed more quickly, there and back, they gain more pheromone than longer ones, so yet more ants follow them. This further reinforces the shortest trail as the one to follow.

There are lots of variations on the way ants actually behave. These variations are being explored by computer scientists as ways for AI agents to work together to solve problems. Sameena devised a new algorithm called EigenAnt to investigate such ant colony-based problem solving. If the above ant algorithm is used, then it turns out longer trails do not disappear even when a shorter path is found, particularly if it is found after a long delay. The original best path has a very strong trail so that it continues to be followed even after a new one is found. Computer-based algorithms add a step whereby all trails fade away at the same rate so that only ones still being followed stay around. This is better but still not perfect. Sameena’s EigenAnt algorithm instead removes pheromone trails selectively. Her software ants select paths using probabilities based on the strength of the trail. Any existing trail could be chosen but stronger trails are more likely to be. When a software ant chooses a trail, it adds its own pheromones but also removes some of the existing pheromone from the trail in a way that depends on the probability of the path being chosen in the first place. This mirrors what real ants do, as studies have shown they leave less pheromone on some trails than others.

Sameena proved mathematical properties of her algorithm as well as running simulations of it. This showed that EigenAnt does find the shortest path and never settles on something less than the best. Better still, it also adapts to changing situations. If a new shorter path arises then the software ants switch to it!

Sameena won the award
for the best PhD in India

There are all sorts of computer science uses for this kind of algorithm, such as in ever-changing computer networks, where we always want to route data via the current quickest route. Sameena, however, has also suggested we humans could learn from this rather remarkable adaptability of ants. We are very bad at adapting to new situations, often getting stuck on poor solutions because of our initial biases. The more successful a particular life path has been for us the more likely we will keep following it, behaving in the same way, even when the situation changes. Sameena found this out when she took her dream job as a Hedge Fund manager. It didn’t go well. Since then, after changing tack, she has been phenomenally successful, first developing AIs for news providers, and then more recently for a bank. As she says: don’t worry if your current career path doesn’t lead to success, there are many other paths to follow. Be willing to adapt and you will likely find something better. We need to nurture lots of possible life paths, not just blindly focus on one.

More on …

Related Magazines …

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

The first computer wizard

by Paul Curzon, Queen Mary University of London

A rainbow coloured checkers board
Image by CS4FN

Christopher Strachey did a series of firsts in computer programming, and that was just when he was playing.

With father a cryptographer, mother a suffragist, Christopher Strachey was a school teacher when he first started ‘playing’ with computers in the early 1950s. He had been given the chance to write programs, first for the National Physical Laboratories’ ACE computer and then the Manchester Mark 1: two of the earliest working computers in the world. The range of things he achieved is amazing. He probably created the first serious computer game you could play against (a draughts playing game), the first recorded computer music, the first “creative” program (a love letter writing program) … and he was just enjoying himself.

He went on to do serious computing, becoming an early computer consultant and later led the Oxford University Programming Research Group. He invented the idea of time-sharing computers, developed the CPL language (the ancestor of C and so many modern programming languages, so has had a powerful effect on all subsequent programming language design). Perhaps most notably, with Dana Scott he pioneered the idea of using maths to describe the meaning of programming languages, called denotational semantics. Oh, and he was a wizard debugger too, famous for quickly debugging his own and other people’s programs. He achieved all of this despite poor performance at school and university when younger, and despite suffering a nervous breakdown when at university that interrupted his studies. It has been suggested that the breakdown might have been due to him coming to terms with the fact that he was homosexual: now legal, homosexuality was then illegal in the UK.

More on …

Related Magazines …

This blog is funded by UKRI, through grant EP/W033615/1.

A Godlike Heart

A short story by Rafael Pérez y Pérez of the Universidad Autónoma Metropolitana, México translated from the original Spanish by Paul Curzon, Queen Mary University of London

(From the archive)

Mexican deity Quetzalcoatl
Image by Alexa from Pixabay

Divinity, all the gods and all the forces that man fails to understand, are sources of inspiration, a supreme gift which can be introduced in the heart or movement of men to make them a yoltéotl, a “heart deified”. (Miguel León-Portilla, The Old Mexican, Mexico: FCE, 1995 page 180)

Part I

Allow me a moment, Your Excellency. Now that I’m older, it’s hard to remember. But don’t worry, I will tell the whole story so that your priests can record it.

It all started that afternoon, on the day of Huey Tozoztli, just before the celebration to the maize goddess Centéotl. On the horizon you could see large pools of blood – the result of the endless struggle of the gods maintaining order in the cosmos – which, when mixed with the clouds and rays of sunshine on the background blue of the universe, drenched the sky with reddish, orange and yellow. As usual, I spent most of my free time watching everything that went on in Tlatelolco market.

What most caught my attention amongst that huge convergence of smells, sounds and forms were grasshoppers; not only lovely to eat roasted on a tortilla, but also alive and full of dynamism, sometimes in the air and sometimes on the floor, sometimes in flight and sometimes sluggishly bound to the Earth – watching me. I was mesmerised for hours. I would line them up in rows of three insects, each row identified by a symbol and each grasshopper with its own number. I then watched the various patterns that arose when some reacted and tried to flee, “grasshoppers 1 and 3 in the first row jumped, while grasshopper 2 did not move.” Sometimes they were impossible to control!

That afternoon I came across Donají, the daughter of a famous Jaguar Knight. She wore a shawl across her shoulders so that you could barely see the long necklace of seashells hanging from her neck that, all tangled up, reached to just above her ankles. To see her made my heart begin to beat so, so fast! Although it was not the first time I had seen her, I had never had the opportunity to introduce myself. I stood beside her, but my mouth failed to produce a sound. No doubt she noticed my nervousness. I spent anxious moments just stuttering, until I said, ‘I’m Tizoc’. A grin spread across her face and she continued on her way without a word. She had ignored me! I felt humiliated. Who was Donají to treat me that way! I wanted to run and hide. Despite her arrogance, I felt a great attraction to her; I promised that one day I would show her who Tizoc really was and how wrong she was to treat me that way.

Part II

Several moons passed when one morning I woke up to hear a terrifying story: Donají had been kidnapped by a thug who was sentenced to death! A search was immediately organised, directed by her father, the great Jaguar Knight, which everyone joined. Eight units were formed. I was assigned to the group that went to Coyoacan. Once there, the warrior commanded us to spread out throughout the area in pairs to speed the search of the area. Because of my youth and inexperience I was appointed as an assistant to Sayil, a retired warrior of the Mexican army. We spent the first night by a stream. While looking for some dry branches to make a fire, I kept wondering how Donají would be feeling. After eating some fruit and roasted snake, I decided to distract myself and I started to enjoy my favourite pastime: watching the world! I was absorbed by a group of fireflies: while flying they would disappear without a trace only to then appear from nowhere. They formed groups of flying dancers in the darkness, following the rhythm of imaginary drums with lit torches plugged into their bodies. It seemed like a ceremony executed by priests in honour of some deity. I was completely immersed in my thoughts, admiring the ritual, when I discovered something surprising: fireflies and crickets share an essence! Grasshoppers jump or stand still on the ground; the flying fireflies were lit or unlit. In both cases, part of their behaviour can be described in terms of two states: jumping or landing; lit or unlit. It was what the priests called the divine essence! I was completely absorbed in my thoughts, when a voice interrupted me:

– ‘Tizoc, are you all right?’, asked Sayil.

– ‘I’m watching the fireflies: I want to see what they can communicate to me’, I replied.

– ‘Communicate?’

– ‘See how some fireflies are lit and others are off. Imagine that if two fireflies flying next to each other are on. We are receiving the message: ‘We are happy’. Now, imagine that we have three fireflies, one lit, then another lit but the third not lit. They are wanting to confess to us: “Walk to the lake and you will find a basket full of cocoa”. We both laughed. I continued: ‘We should call this “the behaviour of the two states.”‘

– ‘I once saw a fortune-teller use the same method’, commented Sayil yawning. I listened intently. ‘He had three figurines made of opossum bones representing Tlahuizcalpantecuhtli, the malevolent God of Venus, who fires darts both at people and at other objects, causing bad things to happen. People asked the fortune-teller questions like “Will the harvest be good this year?” Then he put the figurines in a jar and tossed them: he predicted the future based on how many landed on their back and how many fell on their front – or in terms of fireflies, how many were lit and how many unlit – together with the order in which they fell.’

Sayil’s words left me paralysed for a moment: the priests communicated with the deities through messages made of patterns represented as two states! I was excited and shouted:

– ‘I knew that the grasshoppers and fireflies were connected with the gods!’

Sayil didn’t really understand what I was saying, and he was too tired to ask. A few minutes later he fell asleep, though I only went to sleep late in to the night.

Very early the next morning we continued the search. In some thickets we found the necklace of seashells that I had seen Donají wearing in the market. After a while we came to a crossroads; Sayil, despite all his experience, was not sure which way to turn. So I suggested:

– ‘Let’s ask the gods which path is the right one’.

– ‘What do you mean?’

I pulled out a small leather pouch containing three round stones, which the night before I had painted on one side with green dye made from vegetable plants. I had left the other side its natural grey colour. I put them into a jar and threw them so they landed in a line and said:

– ‘If the green painted side is facing up, it is equivalent to a firefly turned on. If the grey side is exposed it is equivalent to an off’.

– ‘You want to play the soothsayer? We don’t know how to interpret the gods!’

– ‘But we can ask them to guide us’, I said.

– ‘How?’ The warrior asked impatiently.

– ‘Assign to each of the five directions of the universe, a pattern in the stones. Implore the gods for their advice and throw them. I am sure the pattern representing the direction that arises will give us the correct way to go. It is the same as it was when the soothsayer asked about the harvest.’ Sayil didn’t seem to understand my idea, so I continued saying: ‘the combination of stones grey-grey-grey represents the centre, that is, stay where we are. Grey-grey-green means walking towards where the nomadic people are, to the north. Grey-green-grey means walk towards the Zapotec lands in the South. Grey-green-green, means walk to where Tonatiuh, the Sun God emerges, and green-grey-grey means walk in the opposite direction.

I clearly remember that Sayil thought this seemed a silly idea. However, time was short and we didn’t have another way to decide which road to take. So, rather than do nothing he decided to go with my idea:

– ‘How will we know how many steps to go?’ He asked now even more impatiently.

– ‘Once we know the direction we go back to throwing stones. There are eight possible patterns.’

– ‘How do you know?’

– ‘Believe me. I spent a long time watching the grasshoppers jumping! Each pattern represents a number from zero to seven. Then, if we get the pattern 0 we move 20 steps; if pattern 1 appears move 40 steps; if 2 appears we move 80 steps, and so on.

– ‘Tizoc, I think you’ve lost your mind’, Sayil said desperately.

– ‘Trust me. So the first throw will be a statement that tells us where to walk. The second will tell us the number of steps forward. We continue doing this until the instruction appears as the green-green-green pattern, which will mean we have received all the directions.

I put the pebbles in a jar, prayed to the gods for help and threw:

– ‘Grey-green-grey. We have to move towards the land of the Zapotecs! Now, let’s see how many steps: green-green-green, it means …2,560 steps’. I went back to throwing the stones: ‘then we head towards where Tonatiuh rises and walk … 640 steps’.

– ‘Tizoc, are you going to spend all morning throwing stones while Donají is about to die? When are you going to finish this?’

– ‘When the gods tell me to.’

I threw the stones again and to Sayil’s surprise the green-green-green combination appeared: end of the message! We followed the instructions sent by our gods and even though I hadn’t been able to make Sayil believe, we did finally find the hideout of the kidnapper.

Donají was inside a small cave whose entrance was blocked; on seeing her my heart began to pound! Unfortunately, a surprise awaited us, we saw that the kidnapper had two accomplices: this complicated things greatly as we would need support for the rescue. We decided Sayil would go for help while I stayed to monitor the situation, so without wasting more time my partner set off.

Near dark I tried to get as close as possible to let Donají know that she would soon be rescued; I was sure she would be glad of my presence. Unfortunately, one of the thugs discovered me. I was immediately thrown into the cave:

– ‘What are you doing here?’ She asked, shocked to see me.

– ‘Donají! Don’t worry; help will be here soon’, I replied, stuttering again! She immediately realised that there was no else out there to rescue us. Her face contorted in anger and she shouted:

– ‘Why didn’t you go in search of my father instead of getting caught!’

She burst into a flood of tears, weeping and weeping for a long time until she finally fell asleep. I felt a failure. But I swore by the gods to get her out of there!

I tried to stay calm when the three thugs approached: first the leader, who was very young; then a burly one, who seemed a bit of an idiot; and finally a slave who, I suppose, had simply taken the opportunity to get away. The idiot and slave dragged me out of the cave and tied me by my wrists to a tree branch. The noise woke up Donají. I was very scared. The leader began to punch me in the stomach. He wanted to know how many people knew the hiding place. I will never give him the information he wants I told myself. He repeatedly punched me until he grew bored. Then he took a leg of venison, clutching the hoof tightly with both hands he crashed it into my nose! I thought I would die! Donají screamed desperately until finally they took me back to the cave.

From the twisted material of her shawl she made presses and bandages. She wiped my face carefully and all my wounds trying to stem the bleeding. She spent the whole night giving me water to drink and mopping my brow. I will never forget her courage and fortitude! Unfortunately, the next morning, things got worse:

– ‘Tizoc, we have to get up.’

– ‘Are we leaving? Where are we going?’

– ‘I overheard them say that we will go to a valley that is a half-day along the path to Totolhuacalco. The sky is cloudy, so surely it will rain later. If we start today, there is no way anyone will work out where we have gone.’

The situation was critical and I had to come up with something before we left …

Part III

The next day, we were already installed in the new hideout, watching our new surroundings when Donají asked:

– ‘What are your thinking about, Tizoc’?

– ‘The gods have sent me a vision’, I answered.

– ‘A vision? What do you mean?’

– ‘Listen: today, at dawn, Sayil arrived with reinforcements to our former hideout, but was surprised to find it abandoned. Now how could he find us? The rain had washed away all traces of our departure. How would he explain to the great Jaguar Knight that he had lost the trail of his daughter? Sayil and the others, now desperate, reviewed the surroundings and, entering the cave where we had stopped, discovered some strange signs.’

– ‘Do you mean the symbols you drew on the wall?’

– ‘That’s right! One of the soldiers said “It looks like a big fly”. Sayil immediately understood the meaning of the drawings and shouted “No, it’s a firefly!”‘

– ‘What are you talking about?’ Donají asked confused.

At that moment we heard loud cries and Sayil, along with a group of Mexica warriors, began the attack on the new hideout. The slave tried to flee, but was captured immediately; the idiot resisted, but the warriors took a stone and split his head in two; the leader tried to attack Donají, but Sayil grabbed him and strangled him. In just a few moments it had all ended for the trio! Donají wept with happiness. My plan had worked! I was ecstatic! I had finally shown to Donají my worth! It was an unforgettable day for me.

How did they find us? Let me explain, Your Excellency, just let me drink a little water … thank you. It all happened as follows. That day I had to devise a way to communicate to Sayil where we were being taken. I was well aware that our lives depended on it, but was paralysed. Unexpectedly, I heard what I thought was a message from the gods: grasshoppers singing! Two states! That was the solution! I estimated the number of steps required to travel half a day along the Totolhuacalco path and using the same code that Sayil and I had used to find Donají, I left the approximate position of our new location on the cave wall! The kidnappers never suspected that those drawings were instructions of how to find us. So Sayil was given the key to finding us! … Thank you, Your Excellency! I know it was ingenious. Thank you very much. Am I sorry? … What do you mean? “What happened to Donají?”… Your question opens old wounds. I think that you and your brothers would never understand what I mean when I say that, although I never saw her again, my heart was forever linked to hers. I’m tired. With your permission, I would like to go to sleep now.

Two states: divine essence! What can they teach us? What wonders can man create with them? Because while enduring the fifth sun, hearts will be deified. (Tizoc)

The End.

More on …

Related Magazines …

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

Mary Clem: getting it right

by Paul Curzon, Queen Mary University of London

Mary Clem was a pioneer of dependable computing long before the first computers existed. She was a computer herself, but became more like a programmer.

A tick on a target of red concentric zeros
Image by Paul Curzon

Back before there were computers there were human computers: people who did the calculations that machines now do. Victorian inventor, Charles Babbage, worked as one. It was the inspiration for him to try to build a steam-powered computer. Often, however, it was women who worked as human computers especially in the first half of the 20th century. One was Mary Clem in the 1930s. She worked for Iowa State University’s statistical lab. Despite having no mathematical training and finding maths difficult at school, she found the work fascinating and rose to become the Chief Statistical Clerk. Along the way she devised a simple way to make sure her team didn’t make mistakes.

The start of stats

Big Data, the idea of processing lots of data to turn that data into useful information, is all the rage now, but its origins lie at the start of the 20th century, driven by human computers using early calculating machines. The 1920s marked the birth of statistics as a practical mathematical science. A key idea was that of calculating whether there were correlations between different data sets such as rainfall and crop growth, or holding agricultural fairs and improved farm output. Correlation is the the first step to working out what causes what. it allows scientists to make progress in working out how the world works, and that can then be turned into improved profits by business, or into positive change by governments. It became big business between the wars, with lots of work for statistical labs.

Calculations and cards

Originally, in and before the 19th century, human computers did all the calculations by hand. Then simple calculating machines were invented, so could be used by the human computers to do the basic calculations needed. In 1890 Herman Hollerith invented his Tabulator machine (his company later became computing powerhouse, IBM). The Tabulator machine was originally just a counting machine created for the US census, though later versions could do arithmetic too. The human computers started to use them in their work. The tabulator worked using punch cards, cards that held data in patterns of holes punched in to them. A card representing a person in the census might have a hole punched in one place if they were male, and in a different place if they were female. Then you could count the total number of any property of a person by counting the appropriate holes.

Mary was being more than a computer,
and becoming more like a programmer

Mary’s job ultimately didn’t just involve doing calculations but also involved preparing punch cards for input into the machines (so representing data as different holes on a card). She also had to develop the formulae needed for doing calculations about different tasks. Essentially she was creating simple algorithms for the human computers using the machines to follow, including preparing their input. Her work was therefore moving closer to that of a computer operator and then programmer’s job.

Zero check

She was also responsible for checking calculations to make sure mistakes were not being made in the calculations. If the calculations were wrong the results were worse than useless. Human computers could easily make mistakes in calculations, but even with machines doing calculations it was also possible for the formulae to be wrong or mistakes to be made preparing the punch cards. Today we call this kind of checking of the correctness of programs verification and validation. Since accuracy mattered, this part of he job also mattered. Even today professional programming teams spend far more time checking their code and testing it than writing it.

Mary took the role of checking for mistakes very seriously, and like any modern computational thinker, started to work out better ways of doing it that was more likely to catch mistakes. She was a pioneer in the area of dependable computing. What she came up with was what she called the Zero Check. She realised that the best way to check for mistakes was to do more calculations. For the calculations she was responsible for, she noticed that it was possible to devise an extra calculation, whereby if the other answers (the ones actually needed) have been correctly calculated then the answer to this new calculation is 0. This meant, instead of checking lots of individual calculations with different answers (which is slow and in itself error prone), she could just do this extra calculation. Then, if the answer was not zero she had found a mistake.

A trivial version of this general idea when you are doing a single calculation is to just do it a second time, but in a different way. Rather than checking manually if answers are the same, though, if you have a computer it can subtract the two answers. If there are no mistakes, the answer to this extra check calculation should be 0. All you have to do is to look for zero answers to the extra subtractions. If you are checking lots of answers then, spotting zeros amongst non-zeros is easier for a human than looking for two numbers being the same.

Defensive Programming

This idea of doing extra calculations to help detect errors is a part of defensive programming. Programmers add in extra checking code or “assertions” to their programs to check that values calculated at different points in the program meet expected properties automatically. If they don’t then the program itself can do something about it (issue a warning, or apply a recovery procedure, for example).

A similar idea is also used now to catch errors whenever data is sent over networks. An extra calculation is done on the 1s and 0s being sent and the answer is added on to the end of the message. When the data is received a similar calculation is performed with the answer indicating if the data has been corrupted in transmission. 

A pioneering human computer

Mary Clem was a pioneer as a human computer, realising there could be more to the job than just doing computations. She realised that what mattered was that those computations were correct. Charles Babbages answer to the problem was to try to build a computing machine. Mary’s was to think about how to validate the computation done (whether by a human or a machine).

More on …

Related Magazines …

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