This article is inspired by a keynote talk Wendy Hall gave at the ITiCSE conference in Madrid, 2008.
What inspires researchers to dedicate their lives to study one area? In the case of computer scientist Dame Wendy Hall it was a TV programme called Hyperland starring former Dr Who Tom Baker and writer Douglas Adams of Hitchhiker’s Guide to the Galaxy fame that inspired her to become one of the most influential researchers of her area.
A pioneer and visionary in the area of web science, many of Dame Wendy’s ideas have started to appear in the next generation web: the ‘great web that is yet to come’ (as Douglas Adams might put it), otherwise known as the semantic web. She has stacked up a whole bunch of accolades for her work. She is a Professor at the University of Southampton, a former President of the British Computer Society and now the first non-US President of the most influential body in computer science, the Association for Computing Machinery. She is also a Fellow of the Royal Academy of Engineering and this year she topped it all and gaining her most impressive sounding title for sure by being made a Dame Commander of the British Empire.
So how did that TV programme set her going?
Douglas Adams and Tom Baker acted out a vision of the future, a vision of how TV was going to change. At the time the web didn’t exist and TV was just something you sat in front of and passively watched. The future they imagined was interactive TV. TV that was personal. TV that did more than just entertain but served all your information needs.
In the programme Douglas Adams was watching TV, vegetating in front of it…and then Tom Baker appeared on Douglas’s screen. He started asking him questions…and then he stepped out of the TV screen. He introduced himself as a software agent, someone who had all the information ever put into digital format at his fingertips. More than that he was Douglas’s personal agent. He would use that information to answer any questions Douglas had. Not just to bring back documents (Google-style) that had something to do with the question and leave you to work out what to do with it all, but actually answer the question. He was an agent that was servant and friend, an agent whose character could even be changed to fit his master’s mood.
Wendy was inspired…so inspired that she decided she was going to make that improbable vision a reality. Reality hasn’t quite caught up yet, but she is getting there.
Most people who think about it at all believe that Tim Berners-Lee invented the idea of the web and of hypertext, the links that connect web pages together. He was the one that kick-started it into being a global reality, making it happen, but actually lots of people had been working in research labs round the world on the same ideas for years before, Wendy included, with her Microcosm hypermedia system. Tim’s version of hypermedia – interactive information – was a simple version, one simple enough to get the idea off the ground. Its time is coming to an end now though.
What is coming next? The semantic web: and it will be much more powerful. It is a version of the web much closer to that TV program, a version where the web’s data is not just linked to other data but where words, images, pictures, videos are all tagged with meaning: tags that the software agents of the future can use to understand.
The structure is now there for it to happen. What is needed is for people to start to use it, to write their web pages that way, to actually make it everyday reality. Then the web programmers will be able to start innovating with new ideas, new applications that use it, and the web scientists like Wendy will be able to study it: to work out what works for people, what doesn’t and why.
Then maybe it’s your turn to be inspired and drive the next leap forward.
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.
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.
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.
– Paul Curzon, Queen Mary University of London
(from the archive, originally in our special issue “The women are here”)
Google, one of the most powerful companies in the world, is famous for being founded by Larry Page and Sergey Brin, but a key person, the 20th person employed, was engineer, programmer and believer in detail, Marissa Mayer. Her attention to detail made a gigantic difference to Google’s success. She was involved in most of their successful products, from the search engine to Gmail to Adwords and if she wasn’t convinced about a new feature or change, then it didn’t happen. When a designer suggested a new shade of blue for the links of ads, for example, she had to be persuaded. But how could she be sure she did make the right decisions? She used a centuries old idea from medicine, first used to help cure scurvy in sailors, and applied it to software design: the randomized controlled trial.
Randomized controlled trials revolutionized medicine. They could revolutionize many other aspects of our lives too, from education to prison reform, if they were used more. Computer Scientists realized that, and more trials are now used on software than medicines. It’s part of the Big Data revolution and is the way to avoid relying on hunches, instead relying on scientific method to find out what the right answer really is.
But what if …?
The problem with the way we do most things is “what-if”. We make decisions, but never know what would have happened if we took the other choice. If things go well we pat ourselves on the back and tell ourselves we are right. But things might have gone even better had we only made the other decision. We will never know. However good or bad it seems, there is no way of knowing actually if our decision was the right one, if all we do is make it. We then delude ourselves, and so keep doing bad things, over and over. That’s why illness was treated by getting leeches to suck blood for centuries!
Controlled trials overcome this. The big idea boils down to making sure you do both alternatives! Not only do you make the change, you also leave things alone too! That sounds impossible, but it’s simple. Split your population (patients, users, prisoners, students, …) into two groups at random. Apply the change to one group, but leave the other group alone. Then at the end of a suitable period, long enough so you can see any difference, compare the results. You see not only the result of making the change, but also what would have happened if you didn’t. Only then, with hard data about the consequences of both possibilities, do you take the decision.
The first medical trial like this involved sailors who were ill with scurvy – a disease that killed more wartime sailors than enemy action in the 18th century. Scottish Navy surgeon James Lind waited until his ship had been at sea long enough for many sailors to get scurvy. He then split a dozen into 6 pairs: one group had oranges and lemons on top of the normal food, and the others were given different alternatives like cider or vinegar instead. Within a week, the two eating fruit were virtually recovered. More to the point, there was no difference in any of the others apart from an improvement in the pair given cider. Eating fruit was clearly the right decision to cure scurvy. All new drugs are now tested in trials like this to find out if they really do make patients better or not. Because you know what happens to those not given the new treatment, you know any improvement wouldn’t have happened any way.
So how do computer scientists use this sort of trial? The way Marissa Mayer’s team did it is a classic example. One of Google’s designers was suggesting they use a slightly different shade of blue for the links on ads in Google’s mail program. Rather than take his word that it was an improvement, they ran a trial. They created a version of the program that had multiple colours possible for the links, each a different shade of blue. They then split all the users of the program into groups and gave each a different shade of blue for their links, tracking the results. One particular shade led to more clicks on the ads than any other. That was the shade Marissa chose (and it wasn’t the shade the designer had suggested!)
Software trials like this are called A/B Testing. They have become the mainstay of hi-tech companies wanting an edge. It actually leads to a new way of developing software. Rather than get a perfect product at the outset you get something basic that works well enough quickly. Then you set to work running trials on lots of small details, making what are called ‘marginal gains’, as soon as possible. One small detail may not make a big difference, but when you pile them up, each known to be a definite improvement because of the trial, then very quickly your software improves. Trials can give better results than intelligent design!
Does it make a difference? Well the one decision about that shade of blue of Marissa’s team supposedly made Google $200 million a year, as a result of more people clicking on ads. Google now run tens of thousand of trails like this each year. Add the benefits of lots and lots of small improvements and you get one of the most powerful companies on the planet.
Little Gains in Life
The idea of developing software through marginal gains is actually based on the process used by nature: evolution by natural selection. Each species of animal seems perfectly designed for its environment, not because they were designed, but because only the fittest individuals survive to have babies. Any small improvement in a baby that gives it a better ability to survive means the genes responsible for that improvement are passed on. Over many generations the marginal gains add up to give creatures perfectly adapted to their environment.
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?
The first computers transformed the way research is done. One of the very first computers, EDSAC (Electronic Delay Storage Automatic Calculator), contributed to the work of three Nobel prize winners: in Physics, Chemistry and Medicine. Astronomer, Joyce Wheeler was an early researcher to make use of the potential of computers to aid the study of other subjects in this way. She was a Cambridge PhD student in 1954 investigating the nuclear reactions that keep stars burning. This involved doing lots of calculations to work out the changing behaviour and composition of the star.
Joyce had seen EDSAC on a visit to the university before starting her PhD, and learnt to program it from its basic programming manual so that she could get it to do the calculations she needed. She would program by day and let EDSAC number crunch using her programs every Friday night, leaving her to work on the results in the morning, and then start the programming for the following week’s run. EDSAC not only allowed her to do calculations accurately that would otherwise have been impossible, it also meant she could run calculations over and over, tweaking what was done, refining the accuracy of the results, and checking the equations quickly with sample numbers. As a result EDSAC helped her to estimate the age of stars.
What can Computer Scientists learn from a remarkable woman and the improvements she made to animal welfare and the meat processing industry?
Temple Grandin is an animal scientist – an animal welfare specialist and a remarkable innovator on top. She has extraordinary abilities that allow her to understand animals in ways others can’t. As a result her work has reduced the suffering of countless farm animals. She has designed equipment, for example, to restrain animals. It makes it easier to give them shots because, in contrast to the equipment it replaces, it does not discomfort the animals as they enter. By being able to see the detail that an animal perceives she is able to design to overcome the problems. Paradoxically perhaps for someone who cares so much about animals, she works with slaughter houses – Meat Processing factories like those of McDonalds.
Her aim, given people do eat meat, is to ensure the animals are treated humanely throughout the process of rearing an animal until its death. Her work has been close to miraculous in the changes she has brought about to ensure that farm animals do not suffer. She is good for business too. If cattle are spooked by something as they enter the processing factory (also known as a ‘plant’), whether by the glint of metal or a deep shadow, the plant’s efficiency drops. Fewer animals are processed per hour and that is a big problem for managers.
As a result of her work she has turned round plants, both in welfare terms and in terms of rescuing plants that might otherwise have been shut down. Suddenly plants she audits are treating their livestock humanely.
See the Bigger Picture
Where do Temple’s extraordinary abilities come from? In fact she was originally labelled as being mentally disabled. She is actually autistic. As a result her brain doesn’t quite work the way most people’s do. Autistic people as a result of these brain differences often have difficulties socialising with others. They can find it very hard to understand the nuances of human-human communication that the rest of us take for granted. This is in part because autistic people perceive the world differently. A non-autistic person misses vast amounts of the detail in front of their eyes. Instead just a bigger picture of what they are seeing is passed to their conscious selves. An autistic person doesn’t have that sub-conscious ability to filter out detail, but instead perceives every small thing all at once. That is why autistics can sometimes be overcome by their surroundings, finding the world too much to cope with. They think in terms of a series of pictures full of detail, not abstractly in words.
Temple Grandin argues that that is what makes her special when it comes to understanding farm animals. In some ways they see the world very much like she does. Just as a cow does, she notices the shadows and the glint of metal, the bright patch on the floor from the overhead lights or the jacket laid over the fence that is spooking it. The plant managers and animal handlers don’t even register them never mind see them as a problem.
Who ya gonna call?
Because of this ability to quickly spot the problems everyone else has missed, Temple gained a reputation for being the person to call when a problem seemed intractable. She has also turned it into a career as an animal welfare auditor, checking processing plants to ensure their standards are sufficiently high. This is where she has helped force through the biggest improvements, and it all boils down to checklists.
Tick that box
Checking that lists of guidelines are being adhered to is a common way to audit quality in many areas of life. Checklists are used in a computer science context as checks for usability (for example that a new version of some application is easy to use) and accessibility (could a blind person, or for that matter someone who was autistic, successfully use a website say). Checklists tend to be very long. After all it must be the case that the more you are checking, the higher the quality of the result, mustn’t it? Surprisingly that turns out not always to be true! That is why Temple Grandin has been so successful. Rather than have a checklist with hundreds of things to check she boiled her own set of questions to ask down to just 10.
Traditional animal welfare audits have checklist questions such as “Is the flooring slippery?” and “Is the electric prod used as little as possible?”. Even apart from the number to work through this kind of checklist can be very hard to follow, not least due to the vagueness.
Ouch!
Temple’s checklist includes questions like: “Do all animals remain unconscious after being stunned?”, “Do no more than 3% of animals vocalise during handling or stunning?” (a “Moo” in this situation means “Ouch”) They are precise, with little room for dispute – it isn’t left to the inspectors judgement. That also means everyone knows the target they are working towards. The fact that there are only 10 also means it is easy for everyone involved to know them all well. Perhaps most importantly they do not focus on the state of the factory, or the way things are done. Instead, they focus on the end results – that animals are humanely treated. The point is that one item covers a multitude of sins that could be causing it. If too many animals are crying out in pain then you have to fix ALL the causes, even if it is something new that no-one thought of putting on a checklist before.
Temple’s 10 point approach to checklists can apply to more than just animal welfare of course. The principles behind it could just as well apply to other areas like usability and accessibility of websites.
Some usability evaluation techniques do follow similar principles. Cognitive Walkthrough, a method of auditing that systems are easy to use on first encounter, has some of the features of this kind of approach. The original version involved a longish set of questions that an expert was to ask him/herself about a system under evaluation. After early trials the developers of the method Cathleen Wharton, John Rieman, Clayton Lewis and Peter Polson quickly realised this wasn’t very practical and replaced it by a 4 question version. It has since then even been replaced by a 3-question walkthrough. One of the questions, to be asked of each step in achieving a task, is: “Will a user know what to try and do at this point?” This has some of the flavour of the Grandin approach – it is about the end result not about some specific thing going wrong.
Let’s look at accessibility. Currently, where web designers think about it at all (UK law requires them to) the long checklist approach tends to be followed. Typical items to check are things like “Ensure that all information conveyed with colour is also available without colour”. Automatic systems are often used to do audits. That is good in one sense as the criteria have then to be very precise for a mere computer to make the decision. On the other hand it encourages items in the checklist to just be things a computer can check. It also encourages the long list of fine detail approach that Temple rejected. Worse, it also can lead to people conforming to the checklist without deeply understanding what the point actually is. A classic example is a web designer adding as the last item on a web page “If you are partially sighted click here”. As far as an automatic checker is concerned they may have done everything right – even providing alternative facilities that are clearly available (if you can see them). A partially sighted person however would only get to that instruction on the screen after they have struggled through the rest of the page. The designer got the right idea but missed the point.
Temple Grandin’s approach would suggest instead having checklists that ask about the outcomes of using the page: “Do 97% of partially-sighted people successfully complete their objective in using the site?” for example. That is why “user testing” is so important, at least as one of the evaluation approaches you follow. User testing involves people from a wide variety of backgrounds actually trying using your prototype software or web pages before they are released. It allows you to focus on the big picture. Of course if you are trying to ensure a web page is accessible your users must include people with different kinds of disabilities.
The Big Picture
One of Temple Grandin’s main messages is that the big advantage that arises as a result of her autism is that she thinks in concrete pictures not in abstract words. Whilst thinking verbally is good in some situations it seems to make us treat small things as though they were just as important as the big issues.
So whatever you are doing, whether looking after animals or designing accessible websites, don’t get lost in the detail. Focus on the point of it all.
Computer scientists rely on maths a lot. As mathematicians devise new mathematical theories and tools, computer scientists turn them into useful programs. Mathematicians who are interested in computing and how to make practical use of their maths are incredibly valuable. Ingrid Daubechies is like that. Her work has transformed the way we store images and much besides. She works on the maths behind digital signal processing – how best to manipulate things like music and images in computers. It boils down to wiggly lines.
Pixel pictures
The digital age is founded on the idea that you can represent signals: whether sound or images, radio waves, or electrical signals, as sequences of numbers. We digitise things by breaking them into lots of small pieces, then represent each piece with a number. As I look out my window, I see a bare winter tree, with a robin singing. If I take a picture with a digital camera, the camera divides the scene into small squares (or pixels) and records the colour for each square as a number. The real world I’m looking at isn’t broken into squares, of course. Reality is continuous and the switch to numbers means some of the detail of the real thing is lost. The more pieces you break it into the more detail you record, but when you blow up a digital image too much, eventually it goes blurry. Reality isn’t fuzzy like that. Zoom in on the real thing and you see ever more detail. The advantage of going digital is that, as numbers, the images can be much more quickly and easily stored, transmitted and manipulated by Photoshop-like programs. Digital signal processing is all about how you store and manipulate real-world things, those signals, with numbers.
Curvy components
There are different ways to split signals up when digitising them. One of the bedrocks of digital signal processing is called Fourier Analysis. It’s based on the idea that any signal can be built out of a set of basic building blocks added together. It’s a bit like the way you can mix any colour of paint from the three primary colours: red, blue and yellow. By mixing them in the right proportions you can get any colour. That means you can record colours by just remembering the amounts of each component. For signals, the building blocks are the pure frequencies in the signal. The line showing a heartbeat as seen on a hospital monitor, say, or a piece of music in a sound editing program, can be broken down into a set of smooth curves that go up and down with a given frequency, and which when added together give you the original line – the original signal. The negative parts of one wave can cancel out positive parts of another just as two ripples meeting on a pond combine to give a different pattern to the originals.
This means you can store signals by recording the collection and strength of frequencies needed to build them. For images the frequencies might be about how rapidly the colours change across the image. An image of say a hazy sunset, where the colours are all similar and change gradually, will then be made of low frequencies with rolling wave components. An image with lots of abrupt changes will need lots of high frequency, more spiky, waves to represent all those sudden changes.
Blurry bits
Now suppose you have taken a picture and it is all a bit blurry. In the set of frequencies that blurriness will be represented by the long rolling waves across the image: the low frequencies. By filtering out those low frequencies, making them less important and making the high frequency building blocks stronger, we can sharpen the image up.
more like keyhole surgery on a signal than butchering the whole thing.
By filtering in different ways we can have different effects on the image. Some of the most important help compress images. If a digital camera divides the image into fewer pixels it saves memory by storing less data, but you end up with blocky looking pictures. If you instead throw away information by losing some of the frequencies of a Fourier version, the change may be barely noticeable. In fact, drawing on our understanding of how our brains process the world to choose what frequencies to drop we might not see a change in the image at all.
The power of Fourier Analysis is that it allows you to manipulate the whole image in a consistent way, editing a signal by editing its frequency building blocks. However, that power is also a disadvantage. Sometimes you want to have effects that are more local – doing something that’s more like keyhole surgery on a signal than butchering the whole thing.
Wiggly wavelets
That is where wavelets come in. They give a way of focussing on small areas of the signal. The building blocks used with wavelets are not the smooth, forever undulating curves of Fourier analysis, but specially designed functions, ie wiggly lines, that undulate just in a small area – a bit like a single heart beat signal. A ‘mother’ wavelet is combined with variations of it (child wavelets) to make the full set of building blocks: a wavelet family.
Wavelets were perhaps more a curiosity than of practical use to computer scientists, until Ingrid Daubechies came up with compact wavelets that needed only a fixed time to process. The result was a versatile and very practical tool that others have been able to use in all sorts of ways. For example, they give a way to compress images without losing information that matters. This has made a big difference with the FBI’s fingerprint archive, for example. A family of wavelets allows each fingerprint to be represented by just a few wavelets, so a few numbers, rather than the many numbers needed if pixels were stored. The size of the collection takes up 20 times less storage space as wavelets without corrupting the images. That also means it can be sent to others who need it more easily. It matters when each fingerprint would otherwise involve storing or sending 10 Megabytes of data.
People have come up with many more practical uses of Wavelets, from cleaning up old music to classifying stars and detecting earthquakes. Not bad for a wiggly line.
From the archive: This article by Dean Miller, is an edited version of one of the 2006 winning essays from the Queen Mary University of London, Department of Computer Science, first year essay competition.
May I ask you a question? When you think of the computer what names ring a bell? Bill Gates? Or for those more in touch with the history behind computers maybe Charles Babbage is a familiar name? May I ask you another question please? Do you know who Dr Mark Dean is? No, well you should. Do not worry yourself though, you are definitely not alone. I did not know of him either.
Allow me to enlighten you..
Mark Dean is in my opinion a very creative and inspirational black computer scientist. He is a vice-president at IBM and holds 3 of IBM’s first 9 patents on the personal computer. He has over 30 patents pending. He won the Black Engineer of the Year Presidents Award and was made an IBM fellow in 1995. An IBM fellow is IBM’s highest technical honor. Only 50 of IBM’s employee’s are fellows and Mark Dean was the first black one. Prior to joining IBM in 1980 he earned degrees in Electrical Engineering before going back to school to gain a PhD in the field from Stanford University. He was born in 1957 in Jefferson City, Tennessee and was one of the first black students to attend Jefferson City High School. He was an exceptional student and enjoyed athletics. Early manifestations of his desire to create were shown when he and his father built a tractor from scratch when he was just a boy.
Upon joining IBM Mark Dean and a partner led the team that developed the interior architecture (ISA systems bus) which allowed devices like the keyboard and printer to be connected to the motherboard making computers a part of our lives. It was that which earned him a spot in the National Inventors Hall of Fame. While at IBM he has been involved in numerous positions in computer system hardware architecture and design. He was responsible for IBM’s research laboratory in Austin, Texas where he focused on developing high performance microprocessors, software, systems and circuits. It is here where he made history by leading the team that built a gigahertz chip which did a billion calculations per second. In 2004, he was chosen as one of the 50 most important Blacks in Research Science.
He and his father built a tractor from scratch when he was just a boy
I think that such a man should be well recognized in computer science, especially to black computer science students because from what I can see we are rare. We as a minority need an inspirational figure like Mark Dean. He inspires me, I wanted to share that with you. Before this small article it is very probable you had no knowledge of this man. So if there comes a time where you are asked about important names in the field of computers, I hope Dr Mark Dean springs to mind and rings a bell for you to hear loud and clear.
Animation isn’t a new field – artists have been creating animations for over a hundred years. While the technology used to create those animations has changed immensely during that time, modern computer generated imagery continues to employ some of the same techniques that were used to create the first animations.
The hard work of hand drawing
During the early days of animation, moving images were created by rapidly showing a sequence of still images. Each still image, referred to as a frame, was hand drawn by an artist. By making small changes in each new frame, characters were created that appeared to be walking, jumping and talking, or doing anything else that the artist could imagine.
In order for the animation to appear smooth, the frames need to be displayed quickly – typically at around 24 frames each second. This means that one minute of animation required artists to draw over 1400 frames. That means that the first feature-length animated film, a 70-minute Argentinean film called The Apostle, required over 100,000 frames to create.
Creating a 90-minute movie, the typical feature length for most animated films, took almost 130,000 hand drawn frames. Despite these daunting numbers, many feature length animated movies have been created using hand-drawn images.
Drawing with data
Today, many animations are created with the assistance of computers. Rather than simply drawing thousands of images of one character using a computer drawing program, artists can create one mathematical model to represent that character, from which all of his or her appearances in individual frames are generated. Artists manipulate the model, changing things like the position of the character’s limbs (so that the character can be made to walk, run or jump) and aspects of the character’s face (so that it can talk and express emotions). Furthermore, since the models only exist as data on a computer they aren’t confined by the physical realities that people are. As such, artists also have the flexibility to do physically impossible things such as shrinking, bending or stretching parts of a character. Remember Elastigirl, the stretchy mum in The Incredibles? All made of maths.
Once all of the mathematical models have been positioned correctly, the computer is used to generate an image of the models from a specific angle. Just like the hand-drawn frames of the past, this computer- generated image becomes one frame in the movie. Then the mathematical models representing the characters are modified slightly, and another frame is generated. This process is repeated to generate all of the frames for the movie.
The more things change
You might have noticed that, despite the use of computers, the process of generating and displaying the animation remains remarkably similar to the process used to create the first animations over 100 years ago. The animation still consists of a collection of still images. The illusion of smooth movement is still achieved by rapidly displaying a sequence of frames, where each frame in the sequence differs only slightly from the previous one.
The key difference is simply that now the images may be generated by a computer, saving artists from hand drawing over 100,000 copies of the same character. Hand-drawn animation is still alive in the films of Studio Ghibli and Disney’s recent The Princess and the Frog, but we wonder if the animators of hand-drawn features might be tempted to look over at their fellow artists who use computers and shake an envious fist. A cramped fist, too, probably.
Edie Schlain Windsor was a senior systems programmer at IBM. There is more to life than computing though. Just like anyone else, Computer Scientists can do massively important things aside from being very good at computing. Civil rights and over-turning unjust laws are as important as anything. She led the landmark Supreme Court Case (United States versus Windsor) that was a milestone for the rights of same-sex couples in the US.
Born to a Jewish immigrant family, Edie worked her way up from an early data entry job at New York University to ultimately become a senior programmer at IBM and then President of her own software consultancy where she helped LGBTQ+ organisations become computerised.
Having already worked as a programmer at an energy company called Combustion Engineering, she joined IBM on completing her degree in 1958 so was one of the early generation of female programmers, before the later idea of the male programmer stereotype took hold. Within ten years she had been promoted to the highest technical position in IBM, that of a Senior Systems Programmer: so one of their top programmers lauded as a wizard debugger. She had started out programming mainframe computers, the room size computers that were IBM ‘s core business at the time. They both designed and built the computers as well as the operating system and other software that ran on them. Edie became an operating systems expert, and a pioneer computer scientist also working on natural language processing programs, aiming to improve the interactivity of computes. Natural Language Processing was then a nascent area but that by 2011 IBM led spectacularly with its program Watson winning the quiz show Jeopardy! answering general knowledge questions playing against human champions.
Before her Supreme Court case overturned it, a law introduced in 1996 banned US federal recognition of same-sex marriages. It made it federal law that marriage could only exist between a man and a woman. Individual states in the US had introduced same-sex marriage but this new law meant that such marriages were not recognised in general in the US. Importantly, for those involved it meant a whole raft of benefits including tax, immigration and healthcare benefits that came with marriage were denied to same-sex couples.
Edie had fallen in love with psychologist Thea Spyer in 1965, and two years later they became engaged, but actually getting married was still illegal. They had to wait almost 30 years before they were even allowed to make their partnership legal, though still at that point not marry. They were the 80th couple to register on the day such partnerships were finally allowed. By this time Thea had been diagnosed with multiple sclerosis, a disease that gradually leads to the central nervous system breaking down, with movement becoming ever harder. Edie was looking after her as a full time carer, having given up her career to do so. They both loved dancing and did so throughout their life together even once Thea was struggling to walk, using sticks to get on to the dance floor and later dancing in a wheelchair. As Thea’s condition grew worse it became clear she had little time to live. Marriage was still illegal in New York, however, so before it was too late, they travelled to Canada and married there instead.
When Thea died she left everything to Edie in her will. Had Edie been a man married to Thea, she would not have been required to pay tax on this inheritance, but as a woman and because same-sex marriages were deemed illegal she was handed a tax bill of hundreds of thousands of dollars. She sued the government claiming the way different couples were treated was unfair. The case went all the way to the highest court, the Supreme Court, who ruled that the 1996 law was itself unlawful. Laws in the US have as foundation a written constitution that dates back to 1789. The creation of the constitution was a key part of the founding of the United States of America itself. Without it, the union could easily have fallen apart, and as such is the ultimate law of the land that new laws cannot overturn. The problem with the law banning same sex marriage was that it broke the 5th amendment of the constitution added in 1791, one of several amendments made to ensure people’s rights and justice was protected by the constitution.
The Supreme Court decision was far more seismic than just refunding a tax bill, however. It overturned the law that actively banned same-sex marriage, as it fell foul of the constitution, and this paved the way for such marriages to be made actively legal. In 2014 federal employees were finally told they should perform same-sex marriages across the US, and those marriages gave the couple all the same rights as mixed-sex marriages. Because Edie took on the government, the US constitution, and so justice for many, many couples prevailed.
cs4fn 