The Secret Rules of Modern Living: Algorithms


The Secret Rules of Modern Living: Algorithms

Marcus du Sautoy demystifies the hidden world of algorithms, revealing where these 2,000-year-old problem solvers came from, how they work and what they have achieved.


Similar Content

Browse content similar to The Secret Rules of Modern Living: Algorithms. Check below for episodes and series from the same categories and more!

Transcript


LineFromTo

Without us noticing, modern life has been taken over.

0:00:040:00:07

As we search for love, shop online,

0:00:100:00:14

travel the world,

0:00:140:00:18

even as we save lives,

0:00:180:00:20

there are step-by-step instructions working quietly behind the scenes.

0:00:200:00:25

More and more, they are ruling our lives.

0:00:270:00:30

They're called algorithms.

0:00:300:00:33

Algorithms are everywhere.

0:00:340:00:36

These bite-sized chunks of maths have become central

0:00:360:00:39

to our daily lives.

0:00:390:00:41

But because they are invisible, we tend to take them for granted,

0:00:410:00:44

even misunderstand them.

0:00:440:00:46

LAUGHTER

0:00:500:00:52

They are the secret to our digital world, and so much more.

0:00:530:00:57

'In this programme, I'm going to show you some of my favourite

0:00:580:01:02

'algorithms to reveal where they came from...'

0:01:020:01:05

Algorithms are ancient.

0:01:050:01:08

'..how they work...'

0:01:080:01:09

The challenge is to find the shortest route...

0:01:090:01:11

These are the rough instructions that you would use.

0:01:110:01:14

..for returning to your starting point.

0:01:140:01:17

'..what they might be able to do in the future.'

0:01:170:01:20

-The algorithm's kind of writing itself? Or...?

-Absolutely.

0:01:200:01:23

'..and how we can't live without them.'

0:01:230:01:26

Even when we're baking a cake, we're following an algorithm.

0:01:260:01:29

As a mathematician, I love algorithms.

0:01:290:01:32

Not only are they impressive problem solvers,

0:01:320:01:35

but also strangely beautiful, tapping into the mathematical

0:01:350:01:38

order that underpins how the universe works.

0:01:380:01:42

Welcome to the weird and wonderful world of algorithms.

0:01:420:01:45

Most of us carry one of these around.

0:01:540:01:57

Now, you might have noticed that when you take a photo

0:01:570:02:00

with your phone, then it draws a box around any face, like this.

0:02:000:02:05

This is the result of a special face-detection algorithm

0:02:050:02:09

and it helps to keep the face in the photo in focus.

0:02:090:02:13

'Like all algorithms, this one solves a problem.

0:02:140:02:18

'In this case, finding a human face.

0:02:180:02:21

'While it's not fooled by a face made of fruit,

0:02:210:02:24

'it does detect a human face in a photo.

0:02:240:02:28

'So, how does it do it?

0:02:280:02:31

'At their root, algorithms are little more than

0:02:310:02:34

'a series of step-by-step instructions.

0:02:340:02:37

'This one works by methodically scanning the image

0:02:370:02:40

'looking for four particular abstract patterns

0:02:400:02:43

'associated with a face.

0:02:430:02:45

'When these are detected one after another,

0:02:450:02:48

'then the algorithm indicates it's found a human face.'

0:02:480:02:52

The process taps into the underlying pattern behind all faces,

0:02:520:02:56

no matter what shape or size.

0:02:560:02:59

The end result is just one example of how algorithms have

0:02:590:03:02

made our lives easier.

0:03:020:03:05

-I'll do it!

-I'll do it!

-I was here first!

-OK.

0:03:050:03:09

So, off you go.

0:03:090:03:10

'We tend to associate algorithms with computers, smartphones

0:03:100:03:14

'and the internet.

0:03:140:03:15

'But they are not exclusive to the world of technology.

0:03:150:03:19

'My day job is Professor of Mathematics at Oxford University.

0:03:190:03:24

'And one of the things I enjoy most is keeping

0:03:240:03:26

'the students on their toes.'

0:03:260:03:29

OK, I'll take one.

0:03:290:03:31

Here, we're playing a mathematical game with a jar

0:03:310:03:33

full of chocolates and one red hot chilli.

0:03:330:03:37

'The aim is not to be left with the chilli at the end.

0:03:380:03:42

'But what these students don't know,

0:03:420:03:44

'is that I'm playing it with the help of an algorithm.'

0:03:440:03:49

-OK. Ready? BOTH:

-Yeah.

0:03:490:03:51

Right, I'm going to go first, so remember, you can take one,

0:03:510:03:54

two or three chocolates at a time.

0:03:540:03:57

I'm not a greedy guy, so I'll just take one. Now, your turn.

0:03:570:04:00

'Each player takes on their turn, between one and three chocolates.'

0:04:000:04:05

You've taken two, OK. So, I'm going to take... I'll take two.

0:04:050:04:09

'Whatever my opponent does, my algorithm that tells me

0:04:090:04:12

'how to respond.'

0:04:120:04:14

OK, I'll take two.

0:04:140:04:16

And your turn again. SHE LAUGHS

0:04:160:04:19

Oh, yeah.

0:04:190:04:20

-So I'll take...three.

-Three. And I'll take one.

0:04:200:04:24

-And just a chilli left...

-So, wait. Is that me?

-Yeah, so you have

0:04:240:04:27

-to eat the chilli.

-Oh, no!

-So, there you go.

0:04:270:04:29

'Let me reveal how the algorithm I was using helped me win.'

0:04:290:04:32

It's the only way to learn.

0:04:320:04:34

So, the key is to think about grouping things in fours.

0:04:350:04:40

13 chocolates divides into three groups of four, with one left over.

0:04:410:04:46

So, by taking one chocolate in the first round and then four

0:04:460:04:50

minus whatever the other player takes in the subsequent rounds,

0:04:500:04:54

this algorithm ensures that the other player

0:04:540:04:57

is always left with the chilli.

0:04:570:04:58

The essence of a really good

0:04:580:05:01

algorithm, its magic, if you like, is mathematics.

0:05:010:05:04

The best algorithms are those that tap into the underlying

0:05:040:05:07

mathematical structure hiding beneath a problem.

0:05:070:05:10

OK, pop the chilli back.

0:05:110:05:13

I'll be introducing you to some of the algorithms that have

0:05:140:05:17

become the beating heart of modern life.

0:05:170:05:20

But first, I want to show you that, for all their modern

0:05:210:05:24

applications, algorithms are extremely old.

0:05:240:05:28

In fact, they predate computers by thousands of years.

0:05:290:05:33

The oldest algorithm we know of was devised

0:05:350:05:38

to solve a mathematical problem.

0:05:380:05:40

It was first written down by the Ancient Greek mathematician Euclid.

0:05:400:05:44

Euclid's Algorithm, as it's known,

0:05:440:05:47

is a method for finding the greatest common devisor.

0:05:470:05:50

The greatest common devisor is the largest number that will

0:05:520:05:55

divide into a pair of other numbers without leaving a remainder.

0:05:550:06:00

So, in this case, four divides into both eight

0:06:000:06:03

and 12 without a remainder.

0:06:030:06:06

It's simple to find for small numbers,

0:06:060:06:08

but much more tricky for large ones.

0:06:080:06:10

While Euclid was the greatest mathematician of his day,

0:06:120:06:15

his algorithm could have made him a fortune as a tiler.

0:06:150:06:18

Let me show you why.

0:06:190:06:22

Imagine you've got a rectangular-shaped floor

0:06:220:06:25

and you want to find

0:06:250:06:26

the most efficient way to tile it with square tiles.

0:06:260:06:30

In other words, what's the largest square tile that will exactly

0:06:300:06:34

divide the dimensions of the floor with nothing left over?

0:06:340:06:38

This is, in fact, a geometric version

0:06:380:06:40

of the greatest common devisor problem.

0:06:400:06:43

The dimensions of the floor are the two numbers

0:06:430:06:46

and the size of the tiles, which we're going to try

0:06:460:06:48

and work out, is their greatest common devisor.

0:06:480:06:51

We're going to follow Euclid's Algorithm step by step to show

0:06:540:06:57

how it is able to find the perfect sized square tile for this floor.

0:06:570:07:01

According to Euclid's Algorithm, we need to start filling the rectangle

0:07:020:07:06

with square tiles corresponding to the smallest of the two dimensions.

0:07:060:07:10

This is the first stage of the job.

0:07:130:07:15

Euclid's Algorithm then tells us

0:07:170:07:19

to do exactly the same thing again with this rectangle.

0:07:190:07:22

At each stage, the algorithm tells us to select square tiles

0:07:240:07:28

corresponding to the shortest side of the rectangle.

0:07:280:07:31

So this time, our square tiles perfectly fill the leftover space.

0:07:330:07:38

Now, my square tile has dimensions 15x15.

0:07:380:07:42

So Euclid's Algorithm tells us

0:07:420:07:45

that the greatest common devisor of 150 and 345 is 15.

0:07:450:07:50

I'm not suggesting you use Euclid's Algorithm every time

0:07:530:07:56

you need to order some tiles,

0:07:560:07:58

but the amazing thing is that this simple step-by-step method

0:07:580:08:02

finds the perfect square tile whatever the dimensions of the floor.

0:08:020:08:06

Euclid's Algorithm may appear to be just a mathematical technique,

0:08:070:08:11

but it very elegantly fulfils all the criteria for an algorithm.

0:08:110:08:16

It's a precisely stated set of instructions, the procedure

0:08:160:08:20

always finishes, and it can be proven that it works in all cases.

0:08:200:08:24

The power of algorithms is that you don't have to reinvent

0:08:280:08:31

the wheel each time. They're general solutions to problems.

0:08:310:08:36

This holds as true for ancient algorithms as for modern ones.

0:08:360:08:40

In 1998, in this garage in Menlo Park in California,

0:08:450:08:49

an important piece of algorithmic history was made.

0:08:490:08:52

Inside were two PHD students from Stamford University.

0:08:540:08:58

Larry Page and Sergey Brin.

0:08:580:09:00

Their aim was to come up with a search engine that could find

0:09:020:09:05

things efficiently on the World Wide Web.

0:09:050:09:08

Out of these humble beginnings, Google was born.

0:09:110:09:13

But Google wouldn't be Google if it wasn't for the algorithm that

0:09:150:09:18

Larry and Sergey created, called PageRank.

0:09:180:09:21

PageRank was the algorithm at the heart of the first

0:09:300:09:34

incarnation of the Google search engine.

0:09:340:09:37

Now, technically, it's not a search algorithm, but a ranking algorithm.

0:09:370:09:42

So when you type a query into a search engine,

0:09:420:09:45

then there are literally millions of pages which will match that query.

0:09:450:09:49

What PageRank does is to rank all of those pages so the one

0:09:490:09:53

at the top is the one you're more likely to be interested in.

0:09:530:09:56

Larry and Sergey came up with the idea to do PageRank

0:09:580:10:01

and to use it as a ranking system to improve the quality of web search.

0:10:010:10:05

I remember myself at the time,

0:10:050:10:07

you used a web search engine like AltaVista.

0:10:070:10:10

You would have to click the Next Page link

0:10:100:10:12

a lot of times to find what you were looking for.

0:10:120:10:14

PageRank was one of the reasons why Google was

0:10:140:10:17

so much better than the existing search engines at the time.

0:10:170:10:20

The inner workings of PageRank are hidden from view

0:10:210:10:24

on the World Wide Web.

0:10:240:10:26

So to reveal how it does its job, we're going to use the PageRank

0:10:260:10:30

algorithm to rank the players of a football team.

0:10:300:10:33

PageRank looks at two things.

0:10:340:10:36

It looks at the incoming links to a web page, that is the other pages

0:10:360:10:42

that link to the page, and it looks at how important those pages are.

0:10:420:10:46

In our demonstration to show the cleverness of the PageRank

0:10:510:10:54

algorithm, the players in the football team are the web pages

0:10:540:10:59

and the passes between them are the web links.

0:10:590:11:02

The input for the algorithm.

0:11:020:11:05

Generally speaking, the PageRank algorithm will give a higher

0:11:050:11:09

rank to a website if it's got a lot of links coming from other websites.

0:11:090:11:13

So in the case of football, if a player gets more

0:11:130:11:16

passes from the rest of the team, then they'll be ranked higher.

0:11:160:11:20

It's not quite that simple.

0:11:200:11:21

Because the PageRank algorithm actually gives more weight to

0:11:210:11:24

a link from a website that itself has a high page rank.

0:11:240:11:28

So actually, a pass from a popular player is worth more than

0:11:280:11:32

a pass from a player who's hardly involved in the game at all.

0:11:320:11:35

This is a visualisation of the algorithm at work.

0:11:370:11:40

The stats are the players' current ranking. The output of the algorithm.

0:11:400:11:45

And every time there's a pass, these rankings are updated.

0:11:450:11:50

When Google uses this algorithm, it only changes once thing - the input.

0:11:500:11:56

In place of passes, it uses web links.

0:11:560:11:59

Note that the importance of a page depends on the importance

0:12:010:12:04

of the pages that link to it.

0:12:040:12:06

This means that you have to compute page rank for all

0:12:060:12:09

the pages at the same time.

0:12:090:12:11

And you actually have to repeat the computation because, each time,

0:12:110:12:14

you'll update the importance of all the pages.

0:12:140:12:16

And that in turn will influence

0:12:160:12:19

the importance of the pages that those pages link to.

0:12:190:12:22

At the end of the match, the job of the algorithm is done.

0:12:300:12:33

If we wanted to search for the key player in the team,

0:12:360:12:39

this is PageRank's answer.

0:12:390:12:41

Player 11 has the highest PageRank score.

0:12:430:12:46

I think the PageRank algorithm is probably

0:12:480:12:50

my favourite algorithm of all time.

0:12:500:12:52

And it's amazing that it can be applied not just to

0:12:520:12:54

the World Wide Web, but analysing a football match, as well.

0:12:540:12:58

But for me, it's the fact that there's a beautiful bit of

0:12:580:13:01

mathematics at its heart that always seems to find

0:13:010:13:03

the website I'm looking for.

0:13:030:13:05

Within Google, I think

0:13:080:13:09

PageRank is seen as a very important part of Google's early development.

0:13:090:13:14

PageRank was the secret to why the search engine that Larry

0:13:150:13:18

and Sergey built in the 1990s was so successful.

0:13:180:13:22

Now, Google handles over 3.5 billion searches every day.

0:13:230:13:28

It's the world's most poplar search engine.

0:13:280:13:31

And the company is worth more than 450 billion.

0:13:310:13:36

Not bad for two PhD students working out of a garage.

0:13:370:13:40

Algorithms are simple step-by-step recipes.

0:13:490:13:52

Inventing them requires incredible creativity and genius.

0:13:520:13:56

But using them is just a matter of following instructions.

0:13:560:14:01

And this is why algorithms are perfect for computers.

0:14:010:14:04

Computers are just machines.

0:14:080:14:10

They just do repetitive tasks at phenomenal speeds.

0:14:100:14:14

Unbelievable speeds.

0:14:140:14:15

So they're absolutely perfect for performing these repetitive tasks

0:14:150:14:20

that are unambiguously defined

0:14:200:14:23

and can be done in a finite amount of time.

0:14:230:14:27

Computer code is basically making an algorithm specific.

0:14:290:14:32

So the algorithm is the kind of idea.

0:14:320:14:33

How would you solve the problem?

0:14:330:14:35

These are the rough instructions that you would use.

0:14:350:14:37

And then that can be translated into particular code.

0:14:370:14:40

Lots of types of algorithms have been created with a computer in mind.

0:14:430:14:47

And some of the most important are sorting algorithms.

0:14:490:14:53

Now, the job of a sorting algorithm is to put things in order.

0:14:540:14:58

And they have lots of uses.

0:14:580:15:00

For example, on the internet, information gets

0:15:000:15:03

broken down into packets of data which then get sent across the web.

0:15:030:15:08

Now, to reassemble that data,

0:15:080:15:11

sorting algorithms are absolutely crucial to putting this data

0:15:110:15:15

back in the correct order so that we can view the picture,

0:15:150:15:18

or read the email we've just been sent.

0:15:180:15:21

This is the System Development Corporation in California.

0:15:260:15:30

It's considered to be the world's first computer software company.

0:15:300:15:35

And it was here in 1963 that two computer scientists first formally

0:15:350:15:40

wrote down one of the most iconic sorting algorithms of all-time.

0:15:400:15:44

It's called bubble sort.

0:15:480:15:50

And here's an example of bubble sort in action,

0:15:500:15:53

sorting blocks instead of numbers.

0:15:530:15:55

It gets its name because with each round of the algorithm,

0:15:570:16:01

the largest unsorted object bubbles to the top.

0:16:010:16:05

Like all our algorithms so far, there's method in the madness.

0:16:050:16:09

To see how this algorithm works,

0:16:140:16:16

we're going to use it to sort eight objects.

0:16:160:16:19

Now, the bubble sort algorithm says to consider the objects in pairs

0:16:200:16:24

and swap them over if they're in the wrong order.

0:16:240:16:27

So we're going to start at this end here and work our way to the top.

0:16:270:16:31

So I consider these two, they're in the wrong order, so I swap them over.

0:16:310:16:35

Consider the next pair, they're in the right order,

0:16:370:16:40

so I leave them as they are.

0:16:400:16:42

Consider this pair, they're in the wrong order, so I swap them.

0:16:420:16:45

And we just continue doing this.

0:16:480:16:51

Now the bubble sort algorithm says to go back to the beginning

0:16:580:17:01

and repeat the process over and over again until the objects are in order.

0:17:010:17:05

The algorithm stops when there are no pairs to swap round.

0:17:190:17:24

So the bubble sort algorithm has successfully done its job.

0:17:240:17:27

I've now got the objects perfectly ordered,

0:17:270:17:30

according to ascending height.

0:17:300:17:32

Bubble sort is elegantly simple and straightforward.

0:17:340:17:37

But if the scale of the sorting task is huge, say, organising vast swathes

0:17:370:17:41

of data, then there might be better sorting algorithms for the job.

0:17:410:17:45

This is John von Neumann,

0:17:500:17:52

the scientific genius who helped pioneer the modern computer,

0:17:520:17:56

game theory, the atomic bomb

0:17:560:17:58

and, as it turns out, invented a sorting algorithm.

0:17:580:18:02

He devised it to work on this, one of the world's earliest

0:18:040:18:08

electronic computers, which he'd helped design.

0:18:080:18:11

The algorithm is called merge sort.

0:18:110:18:14

The merge sort algorithm works on a principle of divide and conquer.

0:18:160:18:21

And it consists of two parts. The first bit is the dividing part.

0:18:210:18:26

This involves splitting everything into smaller groups.

0:18:280:18:31

And now comes the conquering bit.

0:18:350:18:38

The groups are now merged back together.

0:18:400:18:43

But as I merge the two groups, I compare the sizes of the objects

0:18:430:18:47

one pair at a time so that the merged group becomes sorted.

0:18:470:18:51

Now, the merge sort algorithm might look rather similar to the

0:19:000:19:03

bubble sort, but where it comes into its own is that with a larger

0:19:030:19:07

number of objects, it's much, much faster.

0:19:070:19:10

So let's see how merge sort compares in speed to bubble sort.

0:19:100:19:15

It's time for a battle of the algorithms!

0:19:150:19:18

Here we've got bubble sort on the bottom and merge sort on the top.

0:19:210:19:26

And we've got them sorting 1,000 objects.

0:19:260:19:28

Now, although they'll both produce the same end result,

0:19:280:19:31

you can already see merge sort is getting there much faster.

0:19:310:19:35

And this difference in performance gets more pronounced

0:19:350:19:38

the more objects they're asked to sort.

0:19:380:19:41

LAUGHTER

0:19:530:19:55

Well, er...

0:19:570:19:59

-I'm sorry, maybe...

-No, no, no, no, no.

0:19:590:20:02

I-I think...I think, er...

0:20:020:20:05

I think the bubble sort would be the wrong way to go.

0:20:050:20:08

LAUGHTER

0:20:080:20:10

APPLAUSE

0:20:100:20:11

Come on. Who told him this?

0:20:120:20:15

Merge sort beats bubble sort hands down

0:20:220:20:24

for sorting large amounts of data.

0:20:240:20:26

But in the crazy world of algorithms, there are many,

0:20:280:20:31

many different ways to sort.

0:20:310:20:33

At the last count,

0:20:360:20:37

there were over 20 different types of sorting algorithms.

0:20:370:20:41

All weirdly achieving the same result, but by different means.

0:20:420:20:46

-So there's bubble sort, there's merge sort.

-Insertion sort.

0:20:580:21:02

-There's heap sort, there's quick sort.

-Timsort.

0:21:020:21:06

You've got gnome sort.

0:21:060:21:07

There's pigeonhole sort, which is also called radix sort.

0:21:070:21:10

There's bogosort, which might never finish.

0:21:100:21:13

There's no such thing as the best sorting algorithm.

0:21:190:21:23

Each has its own pros and cons.

0:21:230:21:25

And which one gets used

0:21:260:21:28

often depends on the specifics of the problem.

0:21:280:21:31

I think the beauty of studying algorithms is to try to aspire

0:21:320:21:36

for solutions that are as elegant and efficient as possible.

0:21:360:21:40

I actually think bubble sort's very pretty. I like it.

0:21:400:21:44

Merge sort's beautiful.

0:21:440:21:46

We really couldn't live without them.

0:21:490:21:51

Sorting algorithms bring order to the world.

0:21:510:21:54

So far, we've seen algorithms tackle the tiny

0:22:050:22:07

problems of sizing our bathroom tiles and sorting our data.

0:22:070:22:11

But how well do they cope with the messy world of love?

0:22:120:22:16

Online dating is really popular these days.

0:22:180:22:20

In fact, one survey suggests that over a third

0:22:200:22:23

of recent marriages started online.

0:22:230:22:26

How these dating websites work is that they use something called

0:22:270:22:30

a matching algorithm.

0:22:300:22:33

They search through the profiles, try to match people up according

0:22:330:22:36

to their likes and dislikes, personality traits and so on.

0:22:360:22:40

In fact, the algorithms seem to be better than humans.

0:22:400:22:43

Because recent research has shown those who meet online

0:22:430:22:46

tend to be happier and have longer marriages.

0:22:460:22:49

I'll ask you to receive your prizes from His Majesty the King.

0:22:520:22:56

In fact, matching algorithms have quite a lot to brag about.

0:22:560:23:01

Because in 2012, for the first time, a Nobel Prize was awarded

0:23:010:23:05

because of an algorithm.

0:23:050:23:07

A matching algorithm created by the late David Gale

0:23:070:23:11

and mathematician Lloyd Shapley,

0:23:110:23:13

seen here receiving his share of the prize.

0:23:130:23:16

The story begins in the 1960s when Gale and Shapley wanted to

0:23:200:23:23

solve a problem concerned with college admissions.

0:23:230:23:27

How to match up students to colleges so that everyone got a place.

0:23:270:23:31

But, more importantly, was happy, even if

0:23:320:23:35

they didn't get their first choice.

0:23:350:23:37

They called it the stable marriage problem.

0:23:400:23:44

The stable marriage problem goes like this.

0:23:440:23:46

Suppose you've got four women and four men

0:23:460:23:49

and they want to get married.

0:23:490:23:51

Now, they've ranked each other according to their preferences.

0:23:510:23:54

So, for example, the Queen of Hearts here,

0:23:540:23:55

first choice is the King of Clubs.

0:23:550:23:57

Second choice, King of Diamonds,

0:23:570:24:00

and her last choice is the King of Hearts.

0:24:000:24:02

So the challenge here is to play Cupid and pair up the kings

0:24:020:24:06

and queens so that each one gets a partner, but, more importantly,

0:24:060:24:09

so that the marriages are stable.

0:24:090:24:12

A stable marriage means that the kings and queens don't

0:24:120:24:15

necessarily get their first choice, but they get the best on offer.

0:24:150:24:20

For example, if I paired the King of Hearts and the Queen of Hearts

0:24:200:24:25

and the King of Spades and the Queen of Spades,

0:24:250:24:28

this would be an unstable marriage.

0:24:280:24:31

Because the King of Spades doesn't really like the Queen of Spades.

0:24:310:24:34

He'd prefer the Queen of Hearts.

0:24:340:24:36

The Queen of Hearts, in her turn,

0:24:380:24:40

doesn't really like the King of Hearts.

0:24:400:24:41

She'd prefer the King of Spades.

0:24:410:24:44

So these two are going to run off together in this pairing.

0:24:440:24:48

Where there's a problem, there's an algorithm not far behind.

0:24:510:24:56

In 1962, Gale and Shapley came up with

0:24:560:24:59

their Nobel-Prize-winning algorithm.

0:24:590:25:02

A step-by-step recipe which always finds perfectly-stable marriages.

0:25:020:25:09

So in the first round of the algorithm,

0:25:090:25:11

the queens all proposed to their first-choice kings.

0:25:110:25:14

So the Queen of Spades' first choice is the King of Spades.

0:25:140:25:18

She proposes to the King of Spades.

0:25:180:25:21

The Queen of Hearts' first choice is the King of Clubs,

0:25:210:25:24

so she proposes to the King of Clubs.

0:25:240:25:26

The Queen of Diamonds' first choice is the King of Spades.

0:25:260:25:30

And the Queen of Clubs' first choice is also the King of Spades.

0:25:300:25:33

So King of Spades seems to be the Darcy of this royal court.

0:25:330:25:36

Now, the King of Spades has got three proposals.

0:25:370:25:40

So he chooses his most popular queen,

0:25:410:25:44

who is actually the Queen of Diamonds, and rejects the other two.

0:25:440:25:48

So we have two provisional engagements, two rejections.

0:25:510:25:55

We now remove the rejected queen's first choices.

0:25:550:25:59

And it's time for round two.

0:25:590:26:01

So the Queen of Spades is going to propose to the King of Diamonds.

0:26:020:26:06

And the Queen of Clubs proposes to the King of Clubs.

0:26:060:26:10

But now the King of Clubs has got two proposals

0:26:110:26:14

and actually prefers the Queen of Clubs.

0:26:140:26:17

So he rejects the Queen of Hearts, his provisional

0:26:170:26:20

engagement on the first round of the algorithm,

0:26:200:26:22

and we have to start again.

0:26:220:26:24

In each round, the rejected queens

0:26:260:26:28

propose to the next king on their list.

0:26:280:26:31

And the kings always go for the best offer they get.

0:26:310:26:34

In this round of the algorithm, she proposes to the King of Hearts

0:26:350:26:40

and finally, everyone's paired up with a single queen and king

0:26:400:26:44

and all the marriages are stable.

0:26:440:26:45

The Gale-Shapley algorithm is now used all over the world.

0:26:490:26:53

In Denmark, to match children to day-care places.

0:26:530:26:56

In Hungary, to match students to schools.

0:26:560:27:00

In New York, to allocate rabbis to synagogues.

0:27:000:27:03

And in China, Germany and Spain, to match students to universities.

0:27:030:27:07

Whilst in the UK, it's led to the development

0:27:100:27:13

of a matching algorithm that, for some people, has saved their lives.

0:27:130:27:18

At the age of 20, Seraya in south London was diagnosed

0:27:230:27:26

with a chronic kidney disease and told she needed a transplant.

0:27:260:27:31

I was on dialysis for 18 months and very unwell.

0:27:320:27:37

I couldn't go to work. I had no social life.

0:27:370:27:40

It was literally hospital three times a week for treatment and home.

0:27:400:27:44

A close friend was willing to donate,

0:27:450:27:47

but their tissue types were not compatible.

0:27:470:27:50

In St Albans, Tamir was seriously ill

0:27:530:27:55

and his wife, Lyndsey, wanted to donate.

0:27:550:27:58

But they had the same problem.

0:27:580:28:00

We went through all the blood tests and all the workup

0:28:020:28:04

and it turned out that we were incompatible blood groups.

0:28:040:28:08

Often, kidney patients who are fortunate enough

0:28:100:28:13

to have a would-be donor find there's a mismatch

0:28:130:28:16

between their donor's blood group or tissue type.

0:28:160:28:18

But since 2007, the NHS has been using a special matching algorithm

0:28:200:28:26

to find potential matches for willing donors

0:28:260:28:29

to kidney patients all over the UK.

0:28:290:28:31

When we first looked at this problem,

0:28:350:28:37

we really underestimated the complexity.

0:28:370:28:41

And originally, we just started with swaps between two pairs.

0:28:410:28:46

So it was very simple,

0:28:460:28:48

but it soon became obvious that we needed something much more complex.

0:28:480:28:53

I became in touch with Rachel Johnson at the NHS

0:28:560:29:00

and we then got involved at that stage in being able to design

0:29:000:29:02

algorithms which would allow not just pair-wise exchanges,

0:29:020:29:05

but also exchanges among three couples, as well.

0:29:050:29:08

The algorithm considers several scenarios.

0:29:100:29:13

The simplest is a two-way swap

0:29:130:29:15

with two couples exchanging kidneys.

0:29:150:29:18

More complicated is a three-way swap,

0:29:210:29:23

where the kidneys get passed around in a cycle.

0:29:230:29:26

There are 200 patients in each of our matching runs.

0:29:290:29:34

We need to look for all the possible transplants.

0:29:340:29:38

And it's surprising how many there are.

0:29:400:29:42

There are literally, you know, hundreds,

0:29:420:29:44

sometimes thousands of possibilities.

0:29:440:29:47

It's something that just could not be achieved without the algorithm.

0:29:470:29:51

One day, Seraya received the call that a match had been found

0:29:530:29:57

400 miles away with Linda, a donor living in Bowness near Edinburgh.

0:29:570:30:02

My husband's dad needed a new kidney.

0:30:030:30:06

He'd been ill for a bit of time. And I wasn't a perfect match.

0:30:060:30:11

And I then got a phone call and it was all go from there.

0:30:110:30:17

We got the initial phone call saying

0:30:190:30:20

we'd been matched up in the three-way pool.

0:30:200:30:23

You're just nervous that it's not going to go ahead

0:30:230:30:26

because your life depends on it.

0:30:260:30:28

For the matching couples,

0:30:290:30:31

all the operations had to happen simultaneously.

0:30:310:30:35

It was a major logistical challenge.

0:30:350:30:38

When my donor went to theatre, they called over to check

0:30:380:30:41

that my donor was also in Newcastle going to theatre.

0:30:410:30:44

And they both got it at the exact same time.

0:30:440:30:46

And they make the call and the kidneys come out.

0:30:460:30:49

I think they went by motorbike.

0:30:490:30:51

We were told they might go by helicopter,

0:30:510:30:53

so I thought at least one bit of me might have been in a helicopter,

0:30:530:30:56

but, no, it went by motorbike.

0:30:560:30:58

And it eventually went ahead, thankfully, in December.

0:31:020:31:06

-The best Christmas present.

-Hm!

0:31:060:31:09

Personally, I just imagined it was doctors behind there

0:31:090:31:12

matching people up off this list.

0:31:120:31:14

So, yeah, it's a bit strange

0:31:140:31:17

that it comes down to maths at the end of the day.

0:31:170:31:20

It's a great scheme and it's still fairly recent.

0:31:200:31:23

And many years ago, I wouldn't have had this chance.

0:31:230:31:27

I feel a lot of gratitude to Linda and also to the algorithm.

0:31:270:31:31

So, yeah, I'm very grateful.

0:31:310:31:33

So far, more than 400 patients have benefited from the NHS scheme

0:31:340:31:39

and its special matching algorithm.

0:31:390:31:42

It was only when we actually seen media articles

0:31:420:31:44

and we actually started to think, "Oh, hold on,

0:31:440:31:47

"that person might have actually had that match

0:31:470:31:49

"through the October matching run's pair-wise exchange," and so on,

0:31:490:31:53

that you actually start to see the stories

0:31:530:31:55

that are behind the anonymous data.

0:31:550:31:57

It's quite funny because David's always really concerned

0:31:570:32:00

that the algorithm will take a long time to run.

0:32:000:32:03

And, you know, it's been up to 30 minutes and he gets concerned.

0:32:030:32:07

But actually, 30 minutes, you know, to us,

0:32:070:32:10

it's incredible that it can do all of that in 30 minutes.

0:32:100:32:14

So far, we have seen how algorithms are capable of amazing feats.

0:32:250:32:29

From solving abstract mathematical problems

0:32:300:32:33

to helping us find stuff on the World Wide Web.

0:32:330:32:37

And they key thing for all of these algorithms is their speed.

0:32:370:32:41

So the important feature of a good algorithm is first

0:32:410:32:44

that it'd better be correct, but once you know it's correct,

0:32:440:32:47

it's also important that it runs quickly.

0:32:470:32:49

There's no good having an algorithm that takes longer

0:32:490:32:52

than your lifetime to run if you're wanting the result tomorrow.

0:32:520:32:57

This face-detection algorithm is an example of an efficient algorithm.

0:32:580:33:02

Because it's efficient, it's able to run in real time.

0:33:020:33:05

And that's what makes it useful.

0:33:050:33:07

But just as in real life, some problems are harder than others.

0:33:090:33:14

Every now and then, algorithms meet their match.

0:33:140:33:17

I think the most common misconception about algorithms

0:33:190:33:21

is just that algorithms can do anything.

0:33:210:33:24

I think people don't really know about the limits.

0:33:240:33:27

Some problems simply cannot be solved by efficient algorithms.

0:33:270:33:30

There are some places where efficient algorithms cannot go.

0:33:320:33:36

Lines in the sand that can't be crossed.

0:33:360:33:40

The trouble is knowing which problems they can solve

0:33:400:33:43

and which they can't.

0:33:430:33:44

Take this Rubik's Cube and imagine the more general challenge

0:33:480:33:51

of trying to solve a cube of arbitrary dimensions.

0:33:510:33:54

So, for example, with 50 squares down each side.

0:33:540:33:57

Now, you might expect this

0:33:570:33:58

to be one of the really fiendishly difficult problems,

0:33:580:34:01

but actually, it belongs in the easy camp.

0:34:010:34:03

We know an algorithm that can solve the general Rubik's Cube

0:34:030:34:08

in a reasonable amount of time.

0:34:080:34:09

Although it looks hard,

0:34:130:34:14

this problem can be cracked by efficient algorithms.

0:34:140:34:17

However, here's one that definitely can't.

0:34:220:34:25

Imagine you've got a draughts board of arbitrary size

0:34:270:34:30

and an arrangement of pieces on the board.

0:34:300:34:32

The challenge is to work out

0:34:320:34:34

whether white can force a win from this position.

0:34:340:34:38

Now, draughts is a pretty easy game,

0:34:380:34:40

but it's been mathematically proven

0:34:400:34:42

that there's no algorithm that can solve this problem efficiently.

0:34:420:34:46

It's an inherently difficult problem.

0:34:460:34:49

The only way to solve this puzzle is through sheer hard slog -

0:34:510:34:55

working out all the millions of possibilities.

0:34:550:34:58

So this problem lies firmly beyond the reach of efficient algorithms.

0:35:000:35:04

It can't be solved quickly.

0:35:040:35:06

But for some problems, how hard they are is not clear cut.

0:35:100:35:14

This is a large sudoku. It's got 625 squares.

0:35:140:35:19

One of the nice things about sudoku is that once you've found a solution,

0:35:200:35:24

it's relatively straightforward to check whether or not it's right.

0:35:240:35:28

And this is true however large the puzzle.

0:35:280:35:30

In this case, I've just got to check each row,

0:35:320:35:34

column and block doesn't feature a number twice.

0:35:340:35:38

Sudoku belongs to a very special category of problems

0:35:380:35:42

that all share this characteristic.

0:35:420:35:44

Once you've come up with a solution, it's always easy to check it.

0:35:440:35:48

The mystery is whether there's an efficient algorithm

0:35:490:35:53

to find the solution in the first place.

0:35:530:35:55

And sudoku is not alone. There are lots of problems like this.

0:35:580:36:02

The most intensely studied of them all

0:36:020:36:05

is known as the travelling salesman problem.

0:36:050:36:08

A travelling salesman travels door to door, city to city,

0:36:130:36:16

selling anything from brushes and Hoovers to double-glazing.

0:36:160:36:20

It sounds like a straightforward job.

0:36:220:36:25

But all travelling salesmen face the same question.

0:36:250:36:28

What's the shortest route to take?

0:36:280:36:31

So important is this problem that the Clay Mathematics Institute

0:36:330:36:37

has offered 1 million for whoever can find an efficient algorithm,

0:36:370:36:42

or prove that none exists.

0:36:420:36:44

The travelling salesman problem goes like this.

0:36:460:36:49

Imagine you're a salesman

0:36:490:36:50

and you've got to visit a list of cities represented by the red dots.

0:36:500:36:55

The challenge is to find the shortest route

0:36:550:36:57

so you visit each city once before returning to your starting point.

0:36:570:37:02

Now, you might imagine the best thing is

0:37:020:37:04

to just consider all the routes, like this.

0:37:040:37:07

The method of checking all possibilities is a type of algorithm.

0:37:130:37:18

And for three cities, it works fine

0:37:180:37:20

because there are only three possible routes to check.

0:37:200:37:23

But what if we add two more cities to the list?

0:37:270:37:30

With five cities, there are 60 different possible routes.

0:37:320:37:36

And if we add another city, then there are 360 possible routes.

0:37:390:37:44

And for ten cities, there are over 1.8 million possible routes.

0:37:440:37:49

If our algorithm chugged through them,

0:37:490:37:51

checking all of these at a rate of ten per second,

0:37:510:37:54

it would take two days before it found the shortest.

0:37:540:37:58

So you can see a method of trying all the different possibilities,

0:37:580:38:01

a kind of brute-force algorithm, if you like, is just simply impractical.

0:38:010:38:06

If somebody found a fast algorithm for the travelling salesman problem,

0:38:070:38:10

it would be hugely significant.

0:38:100:38:12

If one of my students came up with an efficient algorithm

0:38:120:38:15

for the travelling salesman problem,

0:38:150:38:17

I would get him to explain it to me,

0:38:170:38:20

I would kill him and then I'd go and claim

0:38:200:38:23

the Clay prize, 1 million.

0:38:230:38:25

But I think my students are safe.

0:38:250:38:28

The problem crops up in lots of areas.

0:38:290:38:32

From soldering circuit boards...

0:38:320:38:35

..to planning the routes for supermarket deliveries.

0:38:370:38:40

But has the travelling salesman problem secretly already been solved?

0:38:400:38:45

A team of scientists working at Rothamsted Research in Harpenden

0:38:490:38:54

have turned to nature to see if it has found the answer.

0:38:540:38:57

They're carrying out an elaborate experiment to study

0:39:030:39:06

how the travelling salesman problem is tackled by the bumblebee.

0:39:060:39:10

Bees have to forage for nectar in order to provision their hive.

0:39:130:39:17

And so they have to visit

0:39:170:39:19

possibly hundreds of flowers on each trip.

0:39:190:39:22

What they want to do is find an efficient way

0:39:220:39:25

to go between all these flowers that they visit.

0:39:250:39:28

The humble bumblebee faces its own travelling salesman problem.

0:39:310:39:35

The flowers are just like the cities.

0:39:350:39:38

And the bee is the travelling salesman.

0:39:380:39:41

One bee will go out foraging many, many times every day.

0:39:410:39:45

So over the course of a day,

0:39:450:39:47

it really helps to take the most efficient possible route.

0:39:470:39:51

So what we're doing is trying to figure out

0:39:510:39:53

exactly what rules they're using to narrow down the possibilities.

0:39:530:39:58

Joe has laid out five feeders which play the role of flowers.

0:40:000:40:04

Each feeder has just enough nectar to ensure the bee has to visit all five

0:40:050:40:10

to give it a full honey stomach.

0:40:100:40:12

And how are you actually knowing where it's going?

0:40:130:40:16

For this, we're using a harmonic radar.

0:40:160:40:18

So as that spins round and round, it's emitting a radar signal.

0:40:180:40:22

And we've attached a small antenna to the back of the bee,

0:40:220:40:25

which then reflects the signal from the radar.

0:40:250:40:27

And so this allows us to see exactly where the bee has gone

0:40:270:40:31

as she moves around the field.

0:40:310:40:32

So, how does the bumblebee tackle the travelling salesman problem?

0:40:340:40:38

OK, we're switching it on now.

0:40:380:40:40

With five feeders, there are a total of 60 possible routes.

0:40:470:40:51

The shortest is around the outer edge.

0:40:510:40:54

This heat map shows the path taken by a single bee.

0:40:580:41:02

At first, it's simply discovering the positions of the feeders.

0:41:020:41:06

Then the bee appears to methodically change different parts of the route

0:41:070:41:12

to see if it can make it shorter.

0:41:120:41:14

Within 20 trips, it's honed in on an efficient route.

0:41:160:41:20

This route is not always the absolute shortest,

0:41:260:41:29

but, for the bee, it's good enough.

0:41:290:41:31

That's amazing that just after a very few tries, they've got

0:41:360:41:40

to something which is efficient enough for them to do their foraging.

0:41:400:41:44

Yes, that's right. They can't spend days or even, you know,

0:41:440:41:47

it could take months or years to try every possibility.

0:41:470:41:50

So they have to very quickly find a route

0:41:500:41:52

that they can do again and again and again

0:41:520:41:55

-in order to efficiently provide food.

-Fantastic.

0:41:550:41:59

I think the bee's become my favourite insect now.

0:41:590:42:01

-It's obviously a mathematician at heart.

-Absolutely.

0:42:010:42:05

Let's be clear. Bees are not about to be awarded 1 million.

0:42:060:42:11

They've not miraculously solved the travelling salesman problem

0:42:110:42:15

because they don't always find the shortest route.

0:42:150:42:18

But their algorithm is a clever approach.

0:42:190:42:21

In maths, it's known as heuristics.

0:42:210:42:25

Algorithms that are efficient, that don't find the perfect solution,

0:42:250:42:29

but get as close as they can.

0:42:290:42:31

The same heuristic approach

0:42:440:42:46

has been used to develop an algorithm for Heathrow airport.

0:42:460:42:49

DISPATCHER: 'Clear for takeoff...'

0:42:510:42:54

Heathrow handles over 1,300 flights a day.

0:42:540:42:57

It's Europe's busiest airport.

0:42:570:43:00

'..430 clear for takeoff. Surface wind 247 degrees at three knots.'

0:43:000:43:04

The challenge for air traffic control

0:43:120:43:15

is to maximise the number of aircraft departing every hour

0:43:150:43:18

and ensure that the airport operates both efficiently and safely.

0:43:180:43:22

'..behind the British Airways 747, line up 27 right behind.'

0:43:220:43:29

One of the key decisions is the order of takeoff.

0:43:290:43:33

We're currently departing a group of medium aircraft,

0:43:330:43:36

which will be separated one minute apart.

0:43:360:43:39

Behind that, then, you can see a 747, which is a large aircraft.

0:43:390:43:43

Medium aircraft need to be separated from the turbulence

0:43:440:43:48

produced by larger aircraft.

0:43:480:43:50

So the ordering of sizes is crucial.

0:43:500:43:52

The ideal sequence for takeoff involves

0:43:530:43:56

really blocking together groups of aircraft.

0:43:560:43:58

So you want large aircraft to be grouped together,

0:43:580:44:01

medium aircraft to be grouped together.

0:44:010:44:03

And that allows the separation

0:44:030:44:05

between those aircraft to be minimised.

0:44:050:44:07

The other factor that needs to be considered where planning takeoff

0:44:100:44:14

is where the planes are heading.

0:44:140:44:16

We want one to be going to the north, one to the south,

0:44:190:44:22

the next going to the north, then the south.

0:44:220:44:24

If all the aircraft were going in the same direction, the separation would be much greater

0:44:240:44:29

and we wouldn't use the runways as efficiently.

0:44:290:44:31

All controllers are sitting in the control towers thinking,

0:44:310:44:34

"I've all these aircraft going north, all these going south.

0:44:340:44:37

"I've got these that are large ones,

0:44:370:44:39

"so I want to try and group all the large ones together

0:44:390:44:42

"so I don't have to go from a large one to a small one."

0:44:420:44:44

And it's a very complex problem to solve in their heads.

0:44:440:44:48

'..906 November...'

0:44:480:44:50

In 2013, an algorithm joined the team.

0:44:500:44:54

Its job is to predict the most likely order for takeoff

0:44:540:44:58

and advise air traffic control

0:44:580:45:00

when aircraft should push back from the gates.

0:45:000:45:03

To do this involves nothing less than simulating

0:45:030:45:06

the entire outward-bound operation of the airport.

0:45:060:45:09

Carrying out millions of calculations every second.

0:45:110:45:14

FAINT DISPATCHER

0:45:140:45:17

The algorithm works by trying to predict

0:45:210:45:25

what order the aircraft are going to take off in.

0:45:250:45:28

If it knows what order they can take off in,

0:45:280:45:30

then it can work backwards and say,

0:45:300:45:32

"If it needs to take off at this time,

0:45:320:45:34

"then it needs to enter the runway queue at this time,

0:45:340:45:37

"then it needs finishing its taxi at this time,

0:45:370:45:39

"so it needs to start its taxi operation at this time.

0:45:390:45:42

"In that case, it needs to finish its pushback by this time,

0:45:420:45:45

"so it needs to start its pushback by this time."

0:45:450:45:47

And it can work all the way back from what time it should take off

0:45:470:45:50

to what time it should start pushing back.

0:45:500:45:52

The output of the algorithm is given to air traffic control

0:45:550:45:58

through the airport's internal computer system

0:45:580:46:01

and displayed to the pilot at the gate in the form of the TSAT,

0:46:010:46:05

the recommended pushback time.

0:46:050:46:07

The pilot can look on the stand-entry system

0:46:100:46:12

to actually see what time he is expecting to depart.

0:46:120:46:15

The biggest benefit of the algorithm is that it means you can

0:46:170:46:21

hold aircraft on stand for longer without them taking off any later.

0:46:210:46:25

So there's no loss for any passengers in terms of delays.

0:46:250:46:28

What you can do is you can start your engines later.

0:46:280:46:30

In actual fact, if we save two minutes' taxi time

0:46:330:46:35

on the way to the end of the runway, over a year,

0:46:350:46:37

that's actually £15 million worth of fuel savings.

0:46:370:46:40

The Heathrow sequencing algorithm shows just what can be accomplished

0:46:420:46:46

with the heuristic approach.

0:46:460:46:47

Just like the bees, the algorithm is not finding

0:46:490:46:52

the absolute perfect solution all the time,

0:46:520:46:55

but nevertheless makes a tough job that bit easier.

0:46:550:46:58

We're very proud of the algorithm

0:47:000:47:02

because it actually now, we feel, models the real world and is of use.

0:47:020:47:05

In the beginning, algorithms were created

0:47:160:47:19

by mathematicians for mathematicians.

0:47:190:47:21

And over the last century,

0:47:210:47:23

algorithms have been created for computers.

0:47:230:47:26

But perhaps our relationship is about to go through a dramatic revolution.

0:47:290:47:33

At Microsoft Research in Cambridge,

0:47:390:47:41

scientists are using new techniques to develop algorithms...

0:47:410:47:46

blurring the boundary between inventor and the algorithm itself.

0:47:460:47:50

This is the Kinect skeletal-tracking algorithm.

0:47:560:47:59

The amazing thing is that it's able to identify

0:47:590:48:02

the different parts of my body.

0:48:020:48:04

So you can see it's coloured the top of my head in red

0:48:040:48:08

and my right hand here in blue.

0:48:080:48:11

You can see it's coloured my neck green.

0:48:110:48:13

Now, this algorithm has never met me before,

0:48:130:48:16

doesn't know how I'm going to move in space,

0:48:160:48:18

but just using the data coming from this special camera here,

0:48:180:48:22

measuring the distance from the camera to my body,

0:48:220:48:25

it's able to produce this map.

0:48:250:48:28

Whatever posture I take, using nothing more than the input

0:48:300:48:33

from the special depth-sensing camera,

0:48:330:48:36

the algorithm is able to accurately identify,

0:48:360:48:39

pixel by pixel, the different parts of my body.

0:48:390:48:42

It was developed for the Microsoft Xbox console

0:48:460:48:49

to track the movement of a player's body posture in real time.

0:48:490:48:53

But just as remarkable as what this algorithm can do

0:48:580:49:01

is the process behind how it was created,

0:49:010:49:04

as researcher Jamie Shotton explains.

0:49:040:49:07

What's happening is that every pixel in the image,

0:49:090:49:12

we are running an algorithm called a decision tree.

0:49:120:49:16

And you can think of a decision tree as a game of 20 questions.

0:49:160:49:19

So the decision tree is sort of taking a pixel, say, on my hand,

0:49:190:49:22

and trying to decide, OK, I've got to colour that blue

0:49:220:49:25

-because that's on the hand rather than on my body.

-Yes.

0:49:250:49:28

The key to a decision tree is the fact that the 20 questions

0:49:280:49:31

that you ask are not the same

0:49:310:49:33

for every pixel that we're trying to classify.

0:49:330:49:37

And the full set of the possible questions

0:49:370:49:39

that could be answered is exponential.

0:49:390:49:43

-It's two to the twenty.

-Right, OK. That's over a million questions,

0:49:430:49:46

a lot of questions you're going to have to program in there.

0:49:460:49:49

Yes. It would take far too long

0:49:490:49:51

and be far too error-prone for us as humans to program that by hand.

0:49:510:49:55

-So, the algorithm's kind of writing itself, or...?

-Absolutely.

0:49:550:49:58

The algorithm was not designed by Jamie

0:50:020:50:05

but instead through a process called machine learning.

0:50:050:50:08

It involved showing the algorithm millions of training images,

0:50:110:50:15

of bodies in different poses and of various shapes and sizes,

0:50:150:50:19

from the very fat to the very thin, the very short to the very tall.

0:50:190:50:23

And from this, the algorithm essentially learned by example,

0:50:240:50:28

devising its own rules.

0:50:280:50:31

Where our intelligence comes in as the designers of the system

0:50:340:50:37

is not in programming the algorithm, per se,

0:50:370:50:41

but in designing the training data set

0:50:410:50:44

to capture all of the kind of variations that we expect to see

0:50:440:50:48

when we deploy this system in people's living rooms

0:50:480:50:51

to play their games.

0:50:510:50:52

So in the end, do you actually know what the algorithm is doing?

0:50:520:50:55

We can get a sense of what it's trying to do

0:50:550:50:57

and how it's roughly working,

0:50:570:50:59

but we couldn't possibly really understand what exactly is going on.

0:50:590:51:02

The same approach of machine learning has been used in other applications.

0:51:040:51:09

For example, this algorithm is able to do something that for a long time

0:51:090:51:14

was thought to be a skill exclusive to neurosurgeons and radiologists.

0:51:140:51:19

From an MRI scan, the algorithm can identify

0:51:190:51:22

and map a brain tumour in 3-D.

0:51:220:51:26

Meaning that a job that normally takes an hour

0:51:260:51:29

can be done in a matter of minutes.

0:51:290:51:31

Professor Chris Bishop is interested in developing

0:51:340:51:37

the concept of machine learning even further.

0:51:370:51:40

To create algorithms that can learn just like we do,

0:51:400:51:44

directly from experience.

0:51:440:51:46

So this demonstration, I think, illustrates the direction

0:51:490:51:52

that algorithms will go in the years ahead.

0:51:520:51:54

OK, I can see a lot of films up here, so what is the algorithm going to do?

0:51:540:51:57

We've got a couple of hundred of the most commonly watched films,

0:51:570:52:00

and what it's going to do,

0:52:000:52:02

it's going to learn about your personal likes and dislikes.

0:52:020:52:06

It's already been trained,

0:52:060:52:08

so it's a machine-learning algorithm behind the scenes,

0:52:080:52:11

but it's already been trained on data from about 10,000 people.

0:52:110:52:14

What it's going to do now is to learn about your preferences.

0:52:140:52:18

At the moment it knows nothing about you,

0:52:180:52:20

so these films are just arranged at random on the screen.

0:52:200:52:22

What I need you to do is to find one of these films,

0:52:220:52:25

either one that you like or one that you don't like.

0:52:250:52:28

If you like it, you can drag it across to the green region,

0:52:280:52:31

if you don't like it, across to the red region.

0:52:310:52:33

Rushmore, I'm a big fan of Rushmore.

0:52:330:52:35

You like Rushmore? OK, right.

0:52:350:52:37

So what's happening now is that if a film is down the right-hand side

0:52:370:52:41

-near the green region, it's very confident you'll like it.

-OK.

0:52:410:52:44

So down here close to the red region,

0:52:440:52:46

it's very confident you won't like it.

0:52:460:52:48

In the middle, it's 50-50. It doesn't really know.

0:52:480:52:51

So if I choose a movie in the middle here,

0:52:510:52:54

I'm not a great Austin Powers fan, so let's shoot that one...

0:52:540:52:57

So you see, they're beginning to spread out sideways,

0:52:570:53:00

-it's going to be a little bit more confident.

-It's pretty good.

0:53:000:53:04

I'm a big fan of Dr Strangelove

0:53:040:53:07

and I'm a big fan of Woody Allen,

0:53:070:53:11

but Spinal Tap, it thinks I'll like that.

0:53:110:53:14

So that's interesting, so when it was confident you liked them

0:53:140:53:18

and you said you liked them,

0:53:180:53:19

not much happened because it didn't learn much.

0:53:190:53:22

When it was confident you'd like it, in the case of Spinal Tap

0:53:220:53:25

and you said, "I don't like it," there was a big change.

0:53:250:53:28

It's learning things from me.

0:53:280:53:30

I'm actually changing the algorithm as I interact with it.

0:53:300:53:33

Exactly. Whereas Kinect was trained in the laboratory and then frozen,

0:53:330:53:36

this algorithm continues to adapt

0:53:360:53:38

and continues to evolve throughout its life.

0:53:380:53:41

The more films that you rate as like and don't like,

0:53:410:53:44

the more it knows about you personally

0:53:440:53:45

and the better able it is to make good recommendations.

0:53:450:53:48

This algorithm is beginning to feel much more human

0:53:480:53:52

in the way that it interacts with the world.

0:53:520:53:54

Is that your aim, to find a way to produce algorithms

0:53:540:53:57

that are a bit like the way that we negotiate the world?

0:53:570:54:00

Exactly. It's a step down that very long road to producing machines

0:54:000:54:03

that really are as capable as the human brain.

0:54:030:54:05

We've a long way to go, but this is a small step in that direction

0:54:050:54:08

because it's not fixed any more.

0:54:080:54:10

It's now continuing to learn just the same way

0:54:100:54:12

that we continue to learn in our daily lives.

0:54:120:54:14

I think we're just starting

0:54:190:54:21

to realise the full potential of algorithms

0:54:210:54:24

and I have one more place I want to visit,

0:54:240:54:26

which I'm told will give me a glimpse

0:54:260:54:28

of just how much they are able to do for us.

0:54:280:54:31

It's a world where almost everything is automated.

0:54:400:54:43

Where algorithms are in control.

0:54:460:54:49

It's the largest automated grocery warehouse on earth.

0:54:490:54:53

It belongs to the online grocery retailer Ocado

0:54:530:54:57

and it's the equivalent of 45 supermarkets in one.

0:54:570:55:01

Over two million items flow through this warehouse every day.

0:55:020:55:06

At any one time, there are something like 7,000 crates

0:55:060:55:10

going over 25 kilometres of track,

0:55:100:55:12

and controlling every aspect of this astonishing spectacle are algorithms.

0:55:120:55:18

Each of those red crates is part of a customer order

0:55:250:55:29

and they may go on from here to find other items

0:55:290:55:32

that they want across the warehouse,

0:55:320:55:35

until they are eventually finished,

0:55:350:55:37

loaded onto a van and then driven out by our routing system

0:55:370:55:41

on a route, which in many ways,

0:55:410:55:43

is solving problems like the travelling salesman problem.

0:55:430:55:47

There are decisions being made all over the place

0:55:470:55:49

as a red crate goes this way and then that way.

0:55:490:55:52

The complexity behind all this is beyond

0:55:520:55:55

what any human could control or solve,

0:55:550:55:58

and that is where these algorithms,

0:55:580:56:01

these problem-solving techniques come in

0:56:010:56:03

to overcome those challenges.

0:56:030:56:05

Everywhere you look, the invisible hand of the algorithm is at work.

0:56:110:56:15

Forecasting algorithms monitor and replenish the stock

0:56:160:56:20

of more than 43,000 products, anticipating customer demand.

0:56:200:56:24

Control system algorithms manage the traffic

0:56:260:56:29

of the more than 7,000 crates around the warehouse.

0:56:290:56:33

And van routing algorithms control the movement of the fleet

0:56:360:56:39

of over 1,500 vans,

0:56:390:56:41

testing over four million different route combinations every second.

0:56:410:56:46

You can almost see the mind of the machine at work

0:56:480:56:51

and it's not a static process, so that's why there is a huge amount

0:56:510:56:54

of machine learning in here, so it's like a self-adapting organism.

0:56:540:56:59

It's constantly having to learn how to do it better.

0:56:590:57:02

People couldn't do that.

0:57:020:57:04

The machine has to tune itself.

0:57:040:57:06

So who would you say was actually in control of the whole thing?

0:57:100:57:14

Ultimately, it's the algorithms that are in control.

0:57:140:57:17

I think I'm getting algorithmic hot flushes

0:57:170:57:19

by looking at this amazing thing!

0:57:190:57:22

In some sense, this warehouse is like

0:57:240:57:26

a little microcosm of the modern world.

0:57:260:57:28

Algorithms are running everything from search engines on the internet,

0:57:280:57:32

sat nav, even keeping our credit cards secure.

0:57:320:57:35

Our world wouldn't function without the power of these algorithms.

0:57:350:57:39

The Open University have produced a free pack for you to learn,

0:57:450:57:48

create and discover more about digital technology past and present.

0:57:480:57:52

To order your copy, phone...

0:57:520:57:55

..or follow the link below

0:57:580:58:00

to the Open University.

0:58:000:58:01

Without us noticing, modern life has been taken over. Algorithms run everything from search engines on the internet to satnavs and credit card data security - they even help us travel the world, find love and save lives.

Mathematician Professor Marcus du Sautoy demystifies the hidden world of algorithms. By showing us some of the algorithms most essential to our lives, he reveals where these 2,000-year-old problem solvers came from, how they work, what they have achieved and how they are now so advanced they can even programme themselves.


Download Subtitles

SRT

ASS