The Secret Rules of Modern Living: Algorithms


The Secret Rules of Modern Living: Algorithms

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

Download Subtitles

SRT

ASS