by Howard Williams, Queen Mary University of London
(From the archive)
Can computers lend a creative hand to the production of new magic tricks? That’s a question our team, led by Peter McOwan at Queen Mary, wrestled with.
The idea that computers can help with creative endeavours like music and drawing is nothing new – turn the radio on and the song you are listening to will have been produced with the help of a computer somewhere along the way, whether it’s a synthesiser sound, or the editing of the arrangement, and some music is created purely inside software. Researchers have been toiling away for years, trying to build computer systems that actually write the music too! Some of the compositions produced in this way are surprisingly good! Inspired by this work, we decided to explore whether computers could create magic.
The project to build creative software to help produce new magic tricks started with a magical jigsaw that could be rearranged in certain ways to make objects on its surface disappear. Pretty cool, but what part did the computer play? A jigsaw is made up of different pieces, each with four sides – the number of different ways all these pieces can be put together is very large; for a human to sit down and try out all the different configurations would take many hours (perhaps thousands, if not millions!). Whizzing through lots of different combinations is something a computer is very good at. When there are simply too many different combinations for even a computer to try out exhaustively, programmers have to take a different approach.
Evolve a jigsaw
A genetic algorithm is a program that mimics the biological process of natural selection. We used one to intelligently search through all the interesting combinations that the jigsaw might be made up from. A population of jigsaws is created, and is then ‘evolved’ via a process that evaluates how good each combination is in each generation, gradually weeding out the combinations that wouldn’t make good jigsaws. At the end of the process you hope to be left with a winner; a jigsaw that matches all the criteria that you are hoping for. In this particular case, we hoped to find a jigsaw that could be built in two different ways, but each with a different number of the same object in the picture, so that you could appear to make an object disappear and reappear again as you made and remade it. The idea is based on a very old trick popularised by Sam Lloyd, but our aim was to create a new version that a human couldn’t, realistically, have come up with, without a lot of free time on their hands!
To understand what role the computer played, we need to explore the Genetic Algorithm mechanism it used to find the best combinations. How did the computer know which combinations were good or bad? This is something creative humans are great at – generating ideas, and discarding the ones they don’t like in favour of ones they do. This creative process gradually leads to new works of art, be they music, painting, or magic tricks. We tackled this problem by first running some experiments with real people to find out what kind of things would make the jigsaw seem more ‘magical’ to a spectator. We also did experiments to find out what would influence a magician performing the trick. This information was then fed into the algorithm that searched for good jigsaw combinations, giving the computer a mechanism for evaluating the jigsaws, similar to the ones a human might use when trying to design a similar trick.
More tricks
We went on to use these computational techniques to create other new tricks, including a card trick, a mind reading trick on a mobile phone, and a trick that relies on images and words to predict a spectator’s thought processes. You can find out more including downloading the jigsaw at www.Qmagicworld.wordpress.com
Is it creative, though?
There is a lot of debate about whether this kind of ‘artificial intelligence’ software, is really creative in the way humans are, or in fact creative in any way at all. After all, how would the computer know what to look out for if the researchers hadn’t configured the algorithms in specific ways? Does a computer even understand the outputs that it creates? The fact is that these systems do produce novel things though – new music, new magic tricks – and sometimes in surprising and pleasing ways, previously not thought of.
Are they creative (and even intelligent)? Or are they just automatons bound by the imaginations of their creators? What do you think?
Having reliable news always matters to us: whether when disasters strike, of knowing for sure what our politicians really said, or just knowing what our favourite celebrity is really up to. Nowadays social networks like Twitter and Facebook are a place to find breaking news, though telling fact from fake-news is getting ever harder. How do you know where to look, and when you find something how do you know that juicy story isn’t just made up?
One way to be sure of stories is from trusted news-providers, like the BBC, but how do they make sure their stories are real. A lot of fake news is created by Artificial Intelligence bots and Artificial Intelligence is part of the solution to beat them.
Sameena Shah realised this early on. An expert in Artificial Intelligence, she led a research team at news provider Thomson Reuters. They provide trusted information for news organisations worldwide. To help ensure we all have fast, reliable news, Sameena’s team created an Artificial Intelligence program to automatically discover news from the mass of social networking information that is constantly being generated. It combines programs that process and understand language to work out the meaning of people’s posts – ‘natural language processing’ – with machine learning programs that look for patterns in all the data to work out what is really news and most importantly what is fake. She both thought up the idea for the system and led the development team. As it was able to automatically detect fake news, when news organisations were struggling with how much was being generated, it gave Thomson Reuters a head-start of several years over other trusted news companies.
Sameena’s ideas and work putting them in to practice has helped make sure we all know what’s really happening.
(This is an updated version of an article that first appeared in Issue 23 of the CS4FN magazine “The women are (still) here”)
(Based on a section from Computing Without Computers, a free book by Paul to help struggling students understand programming concepts).
Object-oriented programming is a popular kind of programming. To understand what it is all about it can help to think about cooking a meal (Hitchhiker’s Guide to the Galaxy style) where the meal cooks itself.
People talk about programs being like recipes to follow. This can help because both programs and recipes are sets of instructions. If you follow the instructions precisely in the right order, it should lead to the intended result (without you needing any thought of how to do it yourself).
That is only one way of thinking about what a program is, though. The recipe metaphor corresponds to a style of programming called procedural programming. Another completely different way of thinking about programs (a different paradigm) is object-oriented programming. So what is that about if not recipes?
In object-oriented programming, programmers think of a program, not as a series of recipes (so not sets instructions to be followed that do distinct tasks) but as a series of objects that send messages to each other to get things done. Different objects also have different behaviours – different actions they can perform. What do we mean by that? That is where The Hitchhiker’s Guide to the Galaxy may help.
In the book “The Restaurant at the End of the Universe”, by Douglas Adam, part of the Hitchhiker’s Guide to the Galaxy series, genetically modified animals are bred to delight in being your meal. They take great personal pride in being perfectly fattened and might suggest their leg as being particularly tasty, for example.
We can take this idea a little further. Imagine a genetically engineered future in which animals and vegetables are bred to have such intelligence (if you can call it that) and are able to cook themselves. Each duck can roast itself to death or alternatively fry itself perfectly. Now, when a request comes in for duck and mushroom pizza, messages go to the mushrooms, the ducks, etc and they get to work preparing themselves as requested by the pizza base, who on creation and addition of the toppings, promptly bakes itself in a hot oven as requested. This is roughly how an object-oriented programmer sees a program. It is just a collection of objects come to life. Each different kind of object is programmed with instructions about all the operations that it can perform on itself (its behaviours). If such an operation is required, a request goes to the object itself to do it.
Compare these genetically modified beings to a program, which could be to control a factory making food, say. In the procedural programming version we write a program (or recipe) for duck and mushroom pizza, that set out the sequence of instructions to follow. The computer, acting as a chef, works down the instructions in turn. The programmer splits the instructions into separate sets to do different tasks: for making pizza dough, adding all the toppings, and so on. Specific instructions say when the computer chef should start following new instructions and return to previous tasks to continue with old ones.
Now, following the genetically-modified food idea instead, the program is thought of as separate objects, one for the pizza base, one for the duck one for each mushroom, so the programmer has to think in terms of what objects exist and what their properties and behaviours are. She writes instructions (the program) to give each group of objects their specific behaviours (so a duck has instructions for how to roast itself, instructions for how to tear itself into pieces, for how to add its pieces on to the pizza base; a mushroom has instructions for how to wash itself, slice itself, and so on). Parts of those behaviours the programmer programs are instructions to send messages to other objects to get things done: the pizza base object, tells the mushroom objects and duck object to get their act together and prepare themselves and jump on top, for example.
This is a completely different way to think of a program based on a completely different way of decomposing it. Instead of breaking the task into subtasks of things to do, you break it into objects, separate entities that send messages to each other to get things done. Which is best depends on what the program does, but for many kinds of tasks the object-oriented approach is a much more natural way to think about the problem and so write the program.
So ducks that cook themselves may never happen in the real universe (I hope), but they could exist in the programs of future kitchens run by computers if the programmers use object-oriented programming.
Follow the news and it is clear that the chatbots are about to take over journalism, novel writing, script writing, writing research papers, … just about all kinds of writing. So how about writing for the CS4FN magazine. Are they good enough yet? Are we about to lose our jobs? Jo asked ChatGPT to write a CS4FN article to find out.Read its efforts before reading on…
As editor I not only wrote but also vet articles and tweak them when necessary to fit the magazine style. So I’ve looked at ChatGPT’s offering as I would one coming from a person …
ChatGPT’s essay writing has been compared to that of a good but not brilliant student. Writing CS4FN articles is a task we have set students in the past: in part to give them experience over how you must write in different styles for different purposes. Different audience? Different writing. Only a small number come close to what I am after. They generally have one or more issues. A common problem when students write for CS4FN is sadly a lack of good grammar and punctuation throughout beyond just typos (basic but vital English skills seem to be severely lacking these days even with spell checking and grammar checking tools to help). Other common problems include a lack of structure, no hook at the start, over-formal writing so the wrong style, no real fun element at all and/or being devoid of stories about people, an obsession with a few subjects (like machine learning!) rather than finding something new to write about. They are also then often vanilla articles about that topic, just churning out looked-up facts rather than finding some new, interesting angle.
How did the chatbot do? It seems to have made most of the same mistakes. At least, chatGPT’s spelling and grammar are basically good so that is a start: it is a good primary school student then! Beyond that it has behaved like the weaker students do… and missed the point. It has actually just written a pretty bog standard factual article explaining the topic it chose, and of course given a free choice, it chose … Machine Learning! Fine, if it had a novel twist, but there are no interesting angles added to the topic to bring it alive. Nor did it describe the contributions of a person. In fact, no people are mentioned at all. It is also using a pretty formal style of writing (“In conclusion…”). Just like humans (especially academics) it also used too much jargon and didn’t even explain all the jargon it did use (even after being prompted to write for a younger audience). If I was editing I’d get rid of the formality and unexplained jargon for starters. Just like the students who can actually write but don’t yet get the subtleties, it hasn’t got the fact that it should have adapted its style, even when prompted.
It knows about structure and can construct an essay with a start, a middle and end as it has put in an introduction and a conclusion. What it hasn’t done though is add any kind of “grab”. There is nothing at the start to really capture the attention. There is no strange link, no intriguing question, no surprising statement, no interesting person…nothing to really grab you (though Jo saved it by adding to the start, the grab that she had asked an AI to write it). It hasn’t added any twist at the end, or included anything surprising. In fact, there is no fun element at all. Our articles can be serious rather than fun but then the grab has to be about the seriousness: linked to bad effects for society, for example.
ChatGPT has also written a very abstract essay. There is little in the way of context or concrete examples. It says, for example, “rules … couldn’t handle complex situations”. Give me an example of a complex situation so I know what you are talking about! There are no similes or metaphors to help explain. It throws in some application areas for context like game-playing and healthcare but doesn’t at all explain them (it doesn’t say what kind of breakthrough has been made to game playing, for example). In fact, it doesn’t seem to be writing in a “semantic wave” style that makes for good explanations at all. That is where you explain something by linking an abstract technical thing you are explaining, to some everyday context or concrete example, unpacking then repacking the concepts. Explaining machine learning? Then illustrate your points with an example such as how machine learning might use movies to predict your voting habits perhaps…and explain how the example does illustrate the abstract concepts such as pointing out the patterns it might spot.
There are several different kinds of CS4FN article. Overall, CS4FN is about public engagement with research. That gives us ways in to explain core computer science though (like what machine learning is). We try to make sure the reader learns something core, if by stealth, in the middle of longer articles. We also write about people and especially diversity, sometimes about careers or popular culture, or about the history of computation. So, context is central to our articles. Sometimes we write about general topics but always with some interesting link, or game or puzzle or … something. For a really, really good article that I instantly love, I am looking for some real creativity – something very different, whether that is an intriguing link, a new topic, or just a not very well known and surprising fact. ChatGPT did not do any of that at all.
Was ChatGPT’s article good enough? No. At best I might use some of what it wrote in the middle of some other article but in that case I would be doing all the work to make it a CS4FN article.
ChatGPT hasn’t written a CS4FN article in any sense other than in writing about computing.
Was it trained on material from CS4FN to allow it to pick up what CS4FN was? We originally assumed so – our material has been freely accessible on the web for 20 years and the web is supposedly the chatbots’ training ground. If so I would have expected it to do much better at getting the style right. I’m left thinking that actually when it is asked to write articles or essays without more guidance it understands, it just always writes about machine learning! (Just like I always used to write science fiction stories for every story my English teacher set, to his exasperation!) We assumed, because it wrote about a computing topic, that it did understand, but perhaps, it is all a chimera. Perhaps it didn’t actually understand the brief even to the level of knowing it was being asked to write about computing and just hit lucky. Who knows? It is a black box. We could investigate more, but this is a simple example of why we need Artificial Intelligences that can justify their decisions!
Of course we could work harder to train it up as I would a human member of our team. With more of the right prompting we could perhaps get it there. Also given time the chatbots will get far better, anyway. Even without that they clearly can now do good basic factual writing so, yes, lots of writing jobs are undoubtedly now at risk (and that includes a wide range of jobs, like lawyers, teachers, and even programmers and the like too) if we as a society decide to let them. We may find the world turns much more vanilla as a result though with writing turning much more bland and boring without the human spark and without us noticing till it is lost (just like modern supermarket tomatoes so often taste bland having lost the intense taste they once had!) … unless the chatbots gain some real creativity.
The basic problem of new technology is it reaps changes irrespective of the human cost (when we allow it to, but we so often do, giddy with the new toys). That is fine if as a society we have strong ways to support those affected. That might involve major support for retraining and education into new jobs created. Alternatively, if fewer jobs are created than destroyed, which is the way we may be going, where jobs become ever scarcer, then we need strong social support systems and no stigma to not having a job. However, currently that is not looking likely and instead changes of recent times have just increased, not reduced inequality, with small numbers getting very, very rich but many others getting far poorer as the jobs left pay less and less.
Perhaps it’s not malevolent Artificial Intelligences of science fiction taking over that is the real threat to humanity. Corporations act like living entities these days, working to ensure their own survival whatever the cost, and we largely let them. Perhaps it is the tech companies and their brand of alien self-serving corporation as ‘intelligent life’ acting as societal disrupters that we need to worry about. Things happen (like technology releases) because the corporation wants them to but at the moment that isn’t always the same as what is best for people long term. We could be heading for a wonderful utopian world where people do not need to work and instead spend their time doing fulfilling things. It increasingly looks like instead we have a very dystopian future to look forward to – if we let the Artificial Intelligences do too many things, taking over jobs, just because they can so that corporations can do things more cheaply, so make more fabulous wealth for the few.
Am I about to lose my job writing articles for CS4FN? I don’t think so. Why do I write CS4FN? I love writing this kind of stuff. It is my hobby as much as anything. So I do it for my own personal pleasure as well as for the good I hope it does whether inspiring and educating people, or just throwing up things to think about. Even if the chatBots were good enough, I wouldn’t stop writing. It is great to have a hobby that may also be useful to others. And why would I stop doing something I do for fun, just because a machine could do it for me? But that is just lucky for me. Others who do it for a living won’t be so lucky.
We really have to stop and think about what we want as humans. Why do we do creative things? Why do we work? Why do we do anything? Replacing us with machines is all well and good, but only if the future for all people is actually better as a result, not just a few.
(First appeared in Issue 23 of the CS4FN magazine “The women are (still) here”)
The stereotype of a computer scientist is someone who doesn’t understand people. For many, how people behave is exactly what they are experts in. Kavin Narasimhan is one. When a student at QMUL she studied how people move and form groups at parties, creating realistic computer models of what is going on.
We humans are very good at subtle behaviour, and do much of it without even realising it. One example is the way we stand when we form small groups to talk. We naturally adjust our positions and the way we face each other so we can see and hear clearly, while not making others feel uncomfortable by getting too close. The positions we take as we stand to talk are fairly universal. If we understand what is going on we can create computational models that behave the same way. Most previous models simulated the way we adjust positions as others arrive or leave by assuming everyone tries to both face, and keep the same distance from, the midpoint of the group. However, there is no evidence that that is what we actually do. There are several alternatives. Rather than pointing ourselves at some invisible centre point, we could be subconsciously maximising our view of the people around. We could be adjusting our positions and the direction we face based on the position only of the people next to us, or instead based on the positions of everyone in the group.
Kavin videoed real parties where lots of people formed small groups to find out more of the precise detail of how we position and reposition ourselves. This gave her a bird’s eye view of the positions people actually took. She also created simulations with virtual 2D characters that move around, forming groups then moving on to join other groups. This allowed her to try out different rules of how the characters behaved, and compare them to the real party situations.
She found that her alternate rules were more realistic than rules based on facing a central point. For example, the latter generates regular shapes like triangular and square formations, but the positions real humans take are less regular. They are better modelled by assuming people focus on getting the best view of others. The simulations showed that this was also a more accurate way to predict the sizes of groups that formed, how long they formed for, and how they were spread across the room. Kavin’s rules therefore appear to give a realistic way to describe how we form groups.
Being able to create models like this has all sorts of applications. It is useful for controlling the precise movement of avatars, whether in virtual worlds or teleconferencing. They can be used to control how computer-generated (CGI) characters in films behave, without needing to copy the movements from actors first. It can make the characters in computer games more realistic as they react to whatever movements the real people, and each other, make. In the future we are likely to interact more and more with robots in everyday life, and it will be important that they follow appropriate rules too, so as not to seem alien.
So you shouldn’t assume computer scientists don’t understand people. Many understand them far better than the average person. That is how they are able to create avatars, robots and CGI characters that behave exactly like real people. Virtual parties are set to be that little bit more realistic.
When we watch a film, it’s not just the pictures that make the experience, it’s the soundtrack too. The music and sound effects play a big part in setting the mood of a film. They matter. If you are to get the sinking feeling in your stomach or feel the shivers down your spine, it’s probably the music. QMUL’s Antonella Mazzoni wondered if other senses could contribute too … and designed a Mood Glove to find out.
Vibrations
We use touch as well as sight and sound to sense the world. This kind of ‘haptic feedback’ is used, for example, in phones that vibrate to tell us someone is calling. Antonella wondered if haptic feedback could heighten our mood while watching films in the way sounds do. To test her ideas she created a series of gloves. They had simple electronics built in to them that caused small pads to vibrate against the hand. She could control the order they vibrated and also the strength and frequency of the vibration. Early experiments showed it was best to make the pads vibrate on the back of the hand: when placed on the palm they tended to tickle too much. She also found that the positions of the vibrations did not make a big difference to moods, so she placed them in a simple circle.
Moods
Our moods and emotion can be broken into two parts: our levels of ‘arousal’ and of ‘valence’. Arousal is to do with the intensity of the mood. Being angry, delighted, alarmed and excited are all high arousal moods, whereas being bored, tired, sleepy and calm are low arousal ones. Valence is instead about the level of pleasure involved. High valence moods are pleasant and include being delighted, happy or calm, whereas low valence moods are unpleasant, such as being afraid, annoyed, depressed or bored. Together they give a standard way to rate mood.
Antonella next collected lots of film clips for use in her experiments. A series of volunteers watched the clips while wearing the glove and rated the experience in terms of their arousal and valence while watching them. Using these ratings as a baseline, she then ran experiments to explore if, and how, different kinds of vibration in the glove changed the wearer’s mood while watching the clips.
Suspense
In one experiment, she investigated suspense. Suspense is where the audience knows something about the plot that the characters don’t, leading to a gradual buildup of tension or expectation. Suspense can be linked to both positive and negative feelings so is not specifically about valence. It involves gradually increasing arousal. It is something that the score of a film can make a big difference to: transforming a clip with little suspense to one full of it. Antonella wondered if our sense of touch, through her Mood Glove, could deliver a similar enhancement? Perhaps, for example, a gradually building pattern of vibration on our hand could increase the build-up of arousal and so suspense. To find out, she chose 60 film clips that involved suspense. Volunteers rated them in terms of valence and arousal, and she used the 16 with most agreement. These final choices included clips from films like Inception, North by Northwest and Gravity.
Effects
Volunteers experienced heightened levels of suspense
Next she designed some simple effects to test. In her ‘buildup’ effect there was a gradual increase of both the strength and frequency of the vibration. The ‘fade in’ effect just increased the strength of the vibrations, starting from nothing and building to a peak. She also created an illusion that the effect moved across the hand, using the different vibration pads. A new set of volunteers watched the chosen film clips while wearing the glove. It gave different vibration patterns in time to each film. They rated their mood while watching the clips and Antonella also interviewed them about the experience afterwards. She found that the volunteers did experience heightened levels of suspense from certain kinds of vibration patterns for some clips. What worked differed for different clips suggesting a need to design the effect to fit the film.
Jobs
New technology creates new jobs that didn’t previously exist. You can see this in the ever increasing lengths of the credits of films, as new kinds of special effects lead to new jobs. Perhaps in future there will be a new career to follow as a `haptic composer’ for films, just as there are currently jobs composing soundtracks.
Originally Published in the CS4FN “Women are Here” special
Rebecca Stewart CC BY 2.0 Thomas Bonte
Some (female) computer scientists and electronic engineers were asked what they most liked about their job and the subject. Each quote is given with the job they had at the time of the quote. many have moved on or upwards since.
Here is what the real Pros think …
“Building software that protects billions of people from online abuse … I find it tremendously rewarding…Every code change I make is a puzzle: exciting to solve and exhilarating to crack; I love doing this all day, every day.”
Despoina Magka, Software engineer, Facebook
“Taking on new challenges and overcoming my limitations with every program I write, every bug I fix, and every application I create. It has and continues to inspire me to grow, both professionally and personally.”
Kavin Narasimhan, Researcher, University of Surrey
“Because computer science skills are useful in nearly every part of our lives, I get to work with biologists, mathematicians, artists, designers, educators and lately a whole colony of naked mole-rats! I love the diversity.”
Julie Freeman, artist and PhD student, QMUL
“The flexibility of working from any place at any time. It offers many opportunities to collaborate with, and learn from, brilliant people from all over the world.”
Greta Yorsh, Lecturer QMUL, former software engineer, ARM.
Shauna, Kavin and Greta
“Possibilities! When you try to do something that seems crazy or impossible and it works, it opens up new possibilities… I enjoy being surrounded by creative people.”
Justyna Petke, Researcher, UCL
“That we get to study the deep characteristics of the human mind and yet we are so close to advances in technology and get to use them in our research.” – Mehrnoosh Sadrzadeh, Senior Lecturer, QMUL
“I get the opportunity to understand what both business people and technologists are thinking about, their ideas and their priorities and I have the opportunity to bring these ideas to fruition. I feel very special being able to do this! I also like that it is a creative subject – elegant coding can be so beautiful!”
Jill Hamilton, Vice President, Morgan Stanley
“You never know what research area the solution to your problem will come from, so every conversation is valuable.”
Vanessa Pope, PhD student, QMUL
“I get to ask questions about people, and set about answering them in an empirical way. computer science can lead you in a variety of unexpected directions”
Shauna Concannon, Researcher, QMUL
“It is fascinating to be able to provide simpler solutions to challenging requirements faced by the business.”
Emanuela Lins, Vice President, Morgan Stanley
“I think the best thing is how you can apply it to so many different topics. If you are interested in biology, music, literature, sport or just about anything else you can think of, then there’s a problem that you can tackle using computer science or electronic engineering…I like writing code, but I enjoy making things even more.”
Becky Stewart, Lecturer, QMUL
“… you get to be both a thinker and a creator. You get to think logically and mathematically, be creative in the way you write and design systems and you can be artistic in the way you display things to users. …you’re always learning something new.”
Yasaman Sepanj, Associate, Morgan Stanley
“Creating the initial ideas, forming the game, making the story… Being part of the creative process and having a hands on approach“,
Nana Louise Nielsen, Senior Game Designer, Sumo Digital
“Working with customers to solve their problems. The best feeling in the world is when you leave … knowing you’ve just made a huge difference.“
Hannah Parker, IT Consultant, IBM
“It changes so often… I am not always sure what the day will be like“
Madleina Scheidegger, Software Engineer, Google.
“I enjoy being able to work from home“
Megan Beynon, Software Engineer, IBM
“I love to see our plans come together with another service going live and the first positive user feedback coming in“
Kerstin Kleese van Dam, Head of Data Management, CCLRC
“…a good experienced team around me focused on delivering results”
Anita King, Senior Project Manager, Metropolitan Police Service
“I get to work with literally every single department in the organisation.”
Pick up any computer or smart gadget and you’ll find small, colourful pictures on the screen. These ‘icons’ tell you which app is which. You can just touch them or click on them to open the app. It’s quick and easy, but it wasn’t always like that.
Up until the 1980s if you wanted to run a program you had to type a written command to tell the device what to do. This made things slow and hard. You had to remember all the different commands to type. It meant that only people who felt quite confident with computers were able to play with them.
Computer scientists wanted everyone to be able to join in (they wanted to sell more computers too!) so they developed a visual, picture-based way of letting people tell their computers what to do, instead of typing in commands. It’s called a ‘Graphical User Interface’ or GUI.
An artist, Susan Kare, was asked to design some very simple pictures – icons – that would make using computers easier. If people wanted to delete a file they would click on an icon with her drawing of a little dustbin. If people wanted to edit a letter they were writing they could click on the icon showing a pair of scissors to cut out a bit of text. She originally designed them on squared paper, with each square representing a pixel on the screen. Over the years the pictures have become more sophisticated (and sometimes more confusing) but in the early days they were both simple and clear thanks to Susan’s skill.
Try our pixel puzzles which use the same idea. Then invent your own icons or pixel puzzles. Can you come up with your own easily recognizable pictures using as few lines as possible?
You may not think of computers as argumentative, but some of them do actually bicker quite a lot, and for good reason. Many hi-tech systems we depend on rely on the right computers getting their way, and the problems involved are surprisingly tricky to get right. Barbara Liskov’s contributions to this fiendishly difficult problem of making sure the right computers win their arguments helped her scoop the world’s top computing prize in 2009.
The ACM Turing Award, which Barbara won, is the computing equivalent of a Nobel Prize. She was awarded it for more than 40 years’ work. Her early work on programming languages has been used in every significant new language that has been invented since. More recently she has moved on to problems about ‘distributed systems’: computer systems involving lots of separate computers that have to work together. That’s where the arguing comes in.
Barbara has been working on an area of distributed computing called ‘Byzantine fault tolerance’. It’s all about providing a good service despite the fact that just about anything can go wrong to the computers or the network connecting them. It’s so important because those computers could be doing anything from running an ecommerce site over the Internet to keeping an airliner in the air.
Happy birthday
Here’s a thought experiment to show you how tricky distributed computing problems can be. Alice is a cellist in an orchestra and it turns out that the birthday of the conductor, Cassie, is on the day they are playing a concert. Jo, the conductor’s partner, has asked Alice to arrange for the orchestra to play Happy Birthday mid-concert as a surprise. The rest of the orchestra were enthusiastic. The only trouble is they didn’t have the chance to agree which break to do it in. In fact, no one’s sure they’re definitely doing it at all, and now they are now all sitting in their places ready to start.
For it to work they all have to start precisely together or it will just sound horrible. If anyone starts on their own they will just look and sound silly. Can it be done, or should they all just forget the whole thing?
Alice decides to go ahead. She can tell the others it’s on by whispering to those next to her and telling them to pass the message on. As long as her message gets to enough people across the different sections it will be ok. Won’t it?
Actually no.
The problem is: how will she know enough people did get the message? It has to be passed when people aren’t playing, so some could presumably not get it in time. How will she know? If the whispers didn’t get through and she starts to play, she will be the embarrassed one.
Are you in?
That seems an easy thing to solve though – when each person gets the message they just send one back saying, “I’m in”. If she gets enough back, she knows it’s on, doesn’t she? Ahh! There the problem lies. She knows, but no one else can be sure she knows. If any are in doubt they won’t play and it will still go horribly wrong. How does she let everyone know that enough people are willing to go for it? Alice is in the same situation she was at the start! She doesn’t know it will happen for sure and neither does anyone else.
She can start whispering messages again saying that enough people have agreed but that won’t help in the end either. How does she know all the new messages get through?
Change the problem
A computer scientist might have a solution for Alice – change the problem. Following this advice, she starts by whispering to everyone that she will stand up and conduct at an appointed time. Are they in? Now all she needs to be sure of is that when she stands up, enough people have agreed to play so that she won’t look silly. The others send back their message saying ‘I’m in’, but no one else needs to know in advance whether the song is definitely going ahead. If she doesn’t stand up they won’t play. If she does, they go ahead.
Delivering a good service
General knowledge It’s called Byzantine Fault Tolerance after some imaginary generals in the ancient days of the Eastern Roman Empire, whose capital was Byzantium. The original problem was about how two generals could know to attack a city at the same time.
Byzantine fault tolerance is about designing this kind of system: one that involves lots of ‘agents’ (people or computers) that have to come to an agreement about what they know and will do. The aim is for them to work together to deliver a service. That service might be for an orchestra to play Happy Birthday, but is more likely to be something like taking airline bookings over the Internet, or even deciding on action to take to keep the airliner they are flying in the air. The separate computers have to agree as a group even when some could stop working, make mistakes due to software bugs or even behave maliciously due to a virus at any point. Can a way be engineered that allows the system as a whole to still behave correctly and deliver that service? This is the problem Barbara Liskov has been working on with Miguel Castro at MIT. Of course they weren’t thinking of birthdays and orchestras. They were interested in providing the service of looking after documents so they can be accessed anytime, anywhere. A simple computer does this with a file system. It keeps track of the names of your documents and where it has stored them in its memory. When you open a document it uses the records it has kept to go and fetch it from wherever it was put. With this kind of file system, though, if something goes wrong with your machine you could lose your documents forever.
Spread it around
A way to guard against this is to create a file system that distributes copies of each file to different computers around the Internet. When you make changes, those changes are also sent to all the other computers with copies. Then if the copy on one machine is corrupted, perhaps by a hacker or just by a disk crash, the file system as a whole can still give you the correct document. That is where the computers need to start arguing. When you ask for your document back how do all the computers with (possibly different) copies decide which is the correct, uncorrupted version? That sounds easy, but as the orchestra example shows, as soon as you create a situation where the different agents (whether human or computer) are distributed, and worse you can’t trust anyone or anything for sure, there are lots of subtle ways it can all go horribly wrong.
The way Barbara and Miguel’s solution to this problem works is similar to what Alice was doing. One computer acts as what is called the ‘primary’ (Alice played this role). It is where the request from the client (Jo) goes. The primary sends out a request to all the backup machines for the document, just like Alice’s whispered messages. All the backups reply with their copy of the document. As soon as more than some predetermined number come back with the same document, then that is the good copy.
Not so simple
Of course the detail of Barbara and Miguel’s method is a lot trickier than that. They’ve had to figure out how to cope if something goes wrong with the primary (Alice herself) to ensure that the client still gets their document. Their version also works without any synchronisation to make things happen in lockstep (suppose Alice is at the back so can’t stand up and conduct to keep things in time). There are lots of other details in Barbara and Miguel’s version too. Messages are timestamped, for example, so that the recipients can tell if a message is new or just a copy of an old one.
Practically perfect
The particularly special thing about Barbara and Miguel’s way of providing fault tolerance, though, is that it doesn’t take an excessively long time. Various people had come up with solutions before, but they were so slow no one could really use them. The new method is so fast it’s almost as if you weren’t bothering about fault tolerance at all. Better still, the fact that it doesn’t need synchronisation – no conducting – means it also works when the replicated services are on the Internet where the computers act independently and there is no way to keep them in lockstep.
Barbara’s work might never actually help with an orchestral surprise like Alice’s, However, because of it future computers will be in a better position to shrug off their own kind turning rogue due to hackers, cosmic rays or even just plain old breakdowns. Not a bad reason to have a byzantine argument.
Social media is full of people’s opinions, whether about politics, movies, things they bought, celebrities or just something in the news. However, sometimes there is just too much of it. Sometimes, you just want an overview without having to read all the separate comments yourself. That is where programs that can summarise text come in. The idea is that they take lots of separate opinions about a topic and automatically give you a summary. It is not an easy problem, however, and while systems exist, researchers continue to look for better ways.
That is what Queen Mary PhD student Jiayu Song is working on with her supervisor, Professor Maria Liakata. Some sources of opinions are easier to work with than others. For example reviews, whether of movies, restaurants or gadgets, tend to be more structured so more alike in the way they are written. Social media posts on the other hand are unlikely to have any common structure. What is written is much more ‘noisy’ and that makes it harder to summarise different opinions. Jiayu is particularly interested in summarising these noisy social media posts, so has set herself the harder problem of the two.
What does distance of meaning mean?
Think of posts to be summarised as points scattered on a piece of paper. Her work is based on the idea that there is a hypothetical point (so hypothetical social media post) that is in the middle of those other points (a kind of average point) and the task is to find that point so summary post. If they were points on paper then we could use geometry to find a central point that minimises the total distance to all of them. For written text we need first to decide what we actually mean by ‘distance’ as it is no longer something we can measure with a ruler! For text we want some idea of distance in meaning – we want a post that is as close as possible to those it is summarising but by “close” here we mean close in meaning. What does distance of meaning mean? King and Queen for example might be the same distance apart as boy and girl in meaning whereas tree is further away in meaning.
King and Queen for example might be the same distance apart as boy and girl in meaning
Jiayu’s approach is based on finding a middle point for posts using a novel (for this purpose) way of determining distance called the Wasserstein distance. It gives a way of calculating distances between distributions of probabilities. Imagine you collected the marks people scored in a test and plotted a graph of how many got each mark. That would give a distribution of marks (likely it would give a hump-like curve known as normal distribution.). This could be used to estimate the distribution of marks you would get from a different class. If we did that for lots of different classes each would actually have a slightly different distribution (so curve when plotted). A summary of the different distributions would be a curve as similar (so as “close”) as possible to all of them so a better predictor of what new classes might score.
From distance to distribution
You could do a similar thing to find the distribution of words in a book, counting how often each word arises and then plotting a curve of how common the different words are. That distribution gives the probability of different words appearing so could be used to predict how likely a given word was in some new book. For summarising, though it’s not words that are of interest but the meanings of words or phrases, as we want to summarise the meaning whatever the words that were actually used. If the same thing is expressed using different words, then it should count as the same thing. “The Queen of the UK died today.” and “Today, the British monarch passed away.” are both expressing the same meaning. It is not the distance apart of individual word meanings we want though, but of distributions of those meanings. Jiayu’s method is therefore first based on extracting the meanings of the words and working out the distribution of those meanings in the posts. However, it turns out it is useful to create two separate representations, one of these distributions of meanings but also another representing the syntax, so the structure of the words actually used too, to help put together the actual final written summary.
Once that decoding stage has been done, creating new versions of the texts to be summarised as distributions, Jiayu’s system uses that special Wasserstein distance to calculate a new distribution of meanings that represents the central point of all those that are being summarised. Even given a way to calculate distances there are different versions of what is meant by “central” point and Jiayu uses a version that helps with the next stage. That involves, a neural network based system, like those used for machine learning systems more generally, is used to convert the summary distributions back into readable text. That summary is the final output of the program.
Does it work?
She has run experiments to compare the summaries from her approach to existing systems. To do this she took three existing datasets of opinions, one from Twitter combining opinions about politics and covid, a second containing posts from Reddit about covid, and a final one of reviews posted on Amazon. A panel of three experts then individually rated the summaries from Jiayu’s system with those from two existing summarising systems. The experts were also given “gold standard” summaries written by humans to judge all the summaries against. They had to rate which system produced the best and worst summary for each of a long series of summaries produced from the datasets. The expert’s ratings suggested that Jiayu’s system preserved meaning better than the others, though did less well in other categories such as how fluent the output was. Jiayu also found that there was a difference when rating the more structured Amazon reviews compared to the other more noisy social media posts and in these two cases a different approach was needed to decode the summary generated back into actual text based on the extra syntax representation created.
Systems like Jiayu’s, once perfected, could have lots of uses: they could help journalists quickly get on top of opinions being posted of a breaking story, help politicians judge the mood of the people about their policies or just help the rest of us decide which movie to watch or whether we should buy some new gadget or not.
Perhaps you have an opinion of whether that would be useful or not?
cs4fn 