[Music] without us noticing modern life has been taken over as we search for love shop travel the online even as we save lives there are step-by-step instructions working quietly behind the scenes more and more they're ruling our lives they're called algorithms algorithms are everywhere these bite-sized chunks of maths have become central to our daily lives but because they're invisible we tend to take them for granted even misunderstand them what is the most efficient way to sort a million 32-bit integers they're the secret to our digital world and so much more in this program i'm going
to show you some of my favorite algorithms to reveal where they came from algorithms are ancient how they work the challenge is to find the shortest route these are the rough instructions that you would use for returning to your starting point what they might be able to do in the future the algorithm's kind of writing itself or uh absolutely and how we can't live without them even when we're baking a cake we're following an algorithm as a mathematician i love algorithms not only are they impressive problem solvers they're also strangely beautiful tapping into the mathematical
order that underpins how the universe works welcome to the weird and wonderful world of algorithms [Music] most of us carry one of these around now you might have noticed that when you take a photo with your phone then it draws a box around any face like this this is the result of a special face detection algorithm and it helps to keep the face in the photo in focus like all algorithms this one solves a problem in this case finding a human face while it's not fooled by a face made of fruit it does detect a
human face in a photo so how does it do it at their root algorithms are little more than a series of step-by-step instructions this one works by methodically scanning the image looking for four particular abstract patterns associated with a face when these are detected one after another then the algorithm indicates it's found a human face [Music] the process taps into the underlying pattern behind all faces no matter what shape or size the end result is just one example of how algorithms have made our lives easier [Music] we tend to associate algorithms with computers smartphones and
the internet but they're not exclusive to the world of technology my day job is professor of mathematics at oxford university and one of the things i enjoy most is keeping the students on their toes here we're playing a mathematical game with a jar full of chocolates and one red hot chili [Music] the aim is not to be left for the chili at the end but what these students don't know is that i'm playing it with the help of an algorithm okay you ready okay i'm gonna go first so remember you can take one two or
three chocolates at a time so i'm not a greedy guy so i'll just take one now your turn each player takes on their turn between one and three chocolates okay so um i'm going to take two whatever my opponent does my algorithm tells me how to respond okay um i'll take two and your turn again oh yeah three i'll take one and uh me yeah so there you go let me reveal how the algorithm i was using helped me win the only way to learn [Laughter] so the key is to think about grouping things in
fours thirteen chocolates divides into three groups of four with one left over so by taking one chocolate in the first round and then four minus whatever the other player takes in the subsequent rounds this algorithm ensures that the other player is always left with the chile the essence of a really good algorithm its magic if you like is mathematics the best algorithms are those that tap into the underlying mathematical structure hiding beneath the problem okay pop the chili back [Music] i'll be introducing you to some of the algorithms that have become the beating heart of
modern life but first i want to show you that for all their modern applications algorithms are extremely old in fact they predate computers by thousands of years the oldest algorithm we know of was devised to solve a mathematical problem was first written down by the ancient greek mathematician euclid euclid's algorithm as it's known is a method for finding the greatest common divisor the greatest common divisor is the largest number that will divide into a pair of other numbers without leaving a remainder so in this case 4 divides into both 8 and 12 without a remainder
it's simple to find for small numbers but much more tricky for large ones [Music] while euclid was the greatest mathematician of his day his algorithm could have made him a fortune as a let me show you why [Music] imagine you've got a rectangular shaped floor and you want to find the most efficient way to tile it with square tiles in other words what's the largest square tile that will exactly divide the dimensions of the floor with nothing left over this is in fact a geometric version of the greatest common divisor problem the dimensions of the
floor are the two numbers and the size of the tiles which we're going to try and work out is their greatest common divisor we're going to follow euclid's algorithm step by step to show how it is able to find the perfect size square tile for this floor according to euclid's algorithm we need to start filling the rectangle with square tiles corresponding to the smallest of the two dimensions this is the first stage of the job euclid's algorithm then tells us to do exactly the same thing again with this rectangle [Music] at each stage the algorithm
tells us to select square tiles corresponding to the shortest side of the rectangle so this time our square tiles perfectly fill the leftover space now my square tile has dimensions 15 by 15. so euclid's algorithm tells us that the greatest common divisor of 150 and 345 is 15. [Music] i'm not suggesting that you use euclid's algorithm every time you need to order some tiles but the amazing thing is that this simple step-by-step method finds the perfect square tile whatever the dimensions of the floor euclid's algorithm may appear to be just a mathematical technique but it
very elegantly fulfills all the criteria for an algorithm it's a precisely stated set of instructions the procedure always finishes and it can be proven that it works in all cases [Music] the power of algorithms is that you don't have to reinvent the wheel each time they're general solutions to problems this holds us true for ancient algorithms as for modern ones [Music] in 1998 in this garage in menlo park california an important piece of algorithmic history was made inside were two phd students from stamford university larry page and sergey brin their aim was to come up
with a search engine that could find things efficiently on the world wide web [Music] out of these humble beginnings google was born but google wouldn't be google if it wasn't for the algorithm that larry and sergey created called pagerank [Music] pagerank was the algorithm at the heart of the first incarnation of the google search engine now technically it's not a search algorithm but a ranking algorithm so when you type a query into a search engine then there are literally millions of pages which will match that query what pagerank does is to rank all of those
pages such that the one at the top is the one that you're most likely to be interested in larry and sergey came up with the idea to do pagerank to use it as a ranking signal to improve the quality of web search i remember myself at the time you used the web search engine like alta vista you would have to click the next page link a lot of times to find what you were looking for page rank was one of the reasons why google was so much better than the existing search engines at the time
the inner workings of pagerank are hidden from view on the world wide web so to reveal how it does its job we're going to use the page rank algorithm to rank the players of a football team pagerank looks at two things it looks at the incoming links to a web page that is the other pages that link to the page and it looks at how important those pages are in our demonstration to show the cleverness of the pagerank algorithm the players in the football team are the web pages and the passes between them are the
web links the input for the algorithm generally speaking the page rank algorithm will give a higher rank to a website if it's got a lot of links coming from other websites so in the case of football if a player gets more passes from the rest of the team then they'll be ranked higher it's not quite that simple because the page rank algorithm actually gives more weight to a link from a website that itself has a high page rank so actually a pass from a popular player is worth more than a pass from a player is
hardly involved in the game at all this is a visualization of the algorithm at work the stats are the player's current ranking the output of the algorithm and every time there's a pass these rankings are updated when google uses this algorithm it only changes one thing the input in place of passes it uses web links note that the importance of a page depends on the importance of the pages that link to it this means that you have to compute page rank for all the pages at the same time and you actually have to repeat the
computation because each time you update the importance of all the pages and that in turn will influence the importance of the pages that those pages link to at the end of the match the job of the algorithm is done if we wanted to search for the key player in the team this is pagerank's answer player 11 has the highest page rank score i think the page rank algorithm is probably my favorite algorithm of all time and it's amazing that it can be applied not just to the world wide web but analyzing a football match as
well but for me it's the fact that there's a beautiful bit of mathematics at its heart that always seems to find the website i'm looking for within google i think page rank is seen as a very important part of google's early development pagerank was the secret to why the search engine that larry and sergey built in the 1990s was so successful now google handles over 3.5 billion searches every day it's the world's most popular search engine and the company is worth more than 450 billion dollars not bad for two phd students working out of a
garage [Applause] algorithms are simple step-by-step recipes inventing them requires incredible creativity and genius but using them is just a matter of following instructions and this is why algorithms are perfect for computers [Music] computers are just machines they just do repetitive tasks at phenomenal speeds unbelievable speeds so they're absolutely perfect for performing these repetitive tasks that are unambiguously defined and can be done in a finite amount of time [Music] computer code is basically making an algorithm specific so the algorithm is the kind of idea how would you solve the problem these are the rough instructions that
you would use and then that can be translated into particular code lots of types of algorithms have been created with the computer in mind and some of the most important are sorting algorithms now the job of a sorting algorithm is to put things in order and they have lots of uses for example on the internet information gets broken down into packets of data which then gets sent across the web now to reassemble that data sorting algorithms are absolutely crucial to putting this data back in the correct order so that we can view the picture or
read the email we've just been sent [Music] this is the system development corporation in california it's considered to be the world's first computer software company and it was here in 1963 that two computer scientists first formally wrote down one of the most iconic sorting algorithms of all time [Music] it's called bubble sort and here's an example of bubble sort in action sorting blocks instead of numbers it gets its name because with each round of the algorithm the largest unsorted object bubbles to the top like all our algorithms so far there's method in the madness to
see how this algorithm works we're going to use it to sort eight objects now the bubble sort algorithm says to consider the objects in pairs and swap them over if they're in the wrong order so we're going to start at this end here and work our way to the top so i consider these two they're in the wrong order so i swap them over consider the next pair they're in the right order so i leave them as they are consider this pair they're in the wrong order so i swap them [Music] and we just continue
doing this [Music] now the bubble sort algorithm says to go back to the beginning and repeat the process over and over again until the objects are in order [Music] the algorithm stops when there are no pairs to swap around so the bubble sort algorithm has successfully done its job i've now got the objects perfectly ordered according to ascending height bubble sword is elegantly simple and straightforward but if the scale of a sorting task is huge say organizing vast swathes of data then there might be better sorting algorithms for the job this is john von neumann
the scientific genius who helped pioneer the modern computer game theory the atomic bomb and as it turns out invented a sorting algorithm [Music] he devised it to work on this one of the world's earliest electronic computers which he'd helped design the algorithm is called merge sort [Music] the merge sword algorithm works on a principle of divide and conquer and it consists of two parts the first bit is the dividing part this involves splitting everything into smaller groups and now comes the conquering bits the groups are now merged back together but as i merge the two
groups i compare the sizes of the objects one pair at a time so that the merged group becomes sorted [Applause] [Music] [Applause] now the merge sort algorithm might look rather similar to the bubble sort but where it comes into its own is that with a larger number of objects it's much much faster so let's see how merge sort compares in speed to bubble sort it's time for a battle of the algorithms here we've got bubble sort on the bottom and merge sort on the top and we've got them sorting a thousand objects now although they'll
both produce the same end result you can already see merge sword is getting there much faster and this difference in performance gets more pronounced the more objects they're asked to sort [Music] what is the most efficient way to sort a million 32-bit integers well uh i'm maybe i'm i'm sorry maybe no no no no no i i think that's not even i i think i think the the bubble sort would be the wrong way to go [Applause] come on who told him this merge sort beats bubble sort hands down for sorting large amounts of data
but in the crazy world of algorithms there are many many different ways to sort at the last count there were over 20 different types of sorting algorithms all weirdly achieving the same result but by different means [Music] so there's a bubble sword there's merge sort insertion sort there's heap sort there's quick sort tim sort of gnome sort there's a pigeonhole sort which is also called radix sort there's bogosart which might never finish [Music] there's no such thing as the best sorting algorithm each has its own pros and cons and which one gets used often depends
on the specifics of the problem i think the beauty of studying algorithms is to try to aspire for solutions that are as elegant and efficient as possible well i actually think bubble sort's very pretty i like it mergesor is beautiful we really couldn't live without them sorting algorithms bring order to the world [Music] so far we've seen algorithms tackle the tidy problems of sizing our bathroom tiles and sorting our data but how well do they cope with a messy world of love online dating is really popular these days in fact one survey suggests that over
a third of recent marriages started online how these dating websites work is that they use something called a matching algorithm they search through the profiles trying to match people up according to their likes and dislikes personality traits and so on in fact the algorithms seem to be better than humans because recent research has shown that those who meet online tend to be happier who have longer marriages and i'll ask you to receive your prizes from his majesty the king in fact matching algorithms have quite a lot to brag about because in 2012 for the first
time a nobel prize was awarded because of an algorithm a matching algorithm created by the late david gale and the mathematician lloyd shapley seen here receiving his share of the prize the story begins in the 1960s when gail and shapley wanted to solve a problem concerned with college admissions how to match up students to colleges said everyone got a place but more importantly was happy even if they didn't get their first choice they called it the stable marriage problem the stable marriage problem goes like this suppose you've got four women and four men they want
to get married now they've ranked each other according to their preferences so for example the queen of hearts here first choice is the king of clubs second choice king of diamonds and the last choice is the king of hearts so the challenge here is to play cupid and pair up the kings and queens such that each one gets a partner but more importantly so the marriages are stable a stable marriage means that the kings and queens don't necessarily get their first choice but they get the best on offer for example if i paired the king
of hearts and the queen of hearts and the king of spades and the queen of spades this will be an unstable marriage because the king of spades doesn't really like the queen of spades he'd prefer the queen of hearts the queen of hearts in her turn doesn't really like the king of hearts she'd prefer the king of spades so these two are going to run off together in this pairing [Music] where there's a problem there's an algorithm not far behind in 1962 gail and shapley came up with their nobel prize winning algorithm a step-by-step recipe
which always finds perfectly stable marriages so in the first round of the algorithm the queens all proposed their first choice kings so the queen of spades first choice is the king of spades she proposes to the king of spades the queen of hearts first choice is the king of clubs so she proposes to the king of clubs queen of diamonds first choice is the king of spades and the queen of clubs first choice is also the king of spades so king of spades seems to be the darcy of this royal court now the king of
spades has got three proposals so he chooses his most popular queen who is actually the queen of diamonds and rejects the other two so we have two provisional engagements two rejections we now remove the rejected queen's first choices and it's time for round two so the queen of spades can propose to the king of diamonds and the queen of clubs proposes to the king of clubs but now the king of clubs has got two proposals and actually they prefer the queen of clubs so he rejects the queen of hearts his provisional engagement on the first
round of the algorithm we have to start again in each round the rejected queens propose to the next king on their list and the kings always go for the best offer they get in this round of the algorithm she proposes to the king of hearts and finally everyone's paired up with a single queen and king and all the marriages are stable [Music] the gail shapley algorithm is now used all over the world in denmark to match children to daycare places in hungary to match students to schools in new york to allocate rabbis to synagogues and
in china germany and spain to match students to universities whilst in the uk it's led to the development of a matching algorithm that for some people has saved their lives at the age of 20 suraya in south london was diagnosed with a chronic kidney disease and told she needed a transplant [Music] i was on dialysis for 18 months and very unwell i couldn't go to work and had no social life it was literally hospital three times a week for my treatment and home a close friend was willing to donate but their tissue types were not
compatible in saint albans tamir was seriously ill and his wife lindsay wanted to donate but they had the same problem we went through all the blood tests and all the work up and it turned out that we were incompatible blood groups often kidney patients who are fortunate enough to have a would-be donor find that there's a mismatch between their donor's blood group or tissue type but since 2007 the nhs has been using a special matching algorithm to find potential matches for willing donors to kidney patients all over the uk when we first looked at this
problem we really underestimated the complexity and originally we just started with swaps between two pairs so it was very simple but it soon became obvious that we needed something much more complex i became in touch with rachel johnson at the nhs and we then got involved at that stage being able to design algorithms which would allow not just pairwise exchanges but also exchanges among three couples as well the algorithm considers several scenarios the simplest is a two-way swap with two couples exchanging kidneys more complicated is a three-way swap where the kidneys get passed around in
a cycle there are 200 patients in each of our matching runs we need to look for all the possible transplants and it's surprising how many there are there are literally you know hundreds sometimes thousands of possibilities it's something that just could not be achieved without the algorithm [Music] one day saraya received the call that a match had been found 400 miles away with linda a donor living in bones near edinburgh my husband's dad needed a new kidney and he'd been ill for a bit of time and i wasn't a perfect match and i then got
a phone call and it was all go from there we got the initial phone call saying that we've been matched up in a three-way pool you're just nervous that it's not going to go ahead because your life depends on it for the matching couples all the operations had to happen simultaneously it was a major logistical challenge when my donor went to theater they called over to check that my diner was also in newcastle going to theater and they both got the exact same time they make the call and the kid needs to come out i
think they went by motorbike we were told they might go by a helicopter so i thought at least one bit of me might have been in a helicopter but no it went by motorbike [Music] and it eventually went ahead thankfully in december best christmas present personally i just imagined it was doctors behind there matching people up off this list and so yeah it's a bit strange that it comes down to maths at the end of the day it's a great scheme and it's still fairly recent and many years ago i wouldn't have had this chance
i feel a lot of gratitude to linda and also to the algorithm so yeah i'm very grateful so far more than 400 patients have benefited from the nhs scheme and its special matching algorithm it's only when we actually see media articles and we actually start to think oh hold on that person might have actually had that match through the october matching runs pairwise exchange and so on that you actually start to see the stories that are behind the anonymous data it's quite funny because david's always really concerned that the algorithm will take a long time
to run and you know it's been up to 30 minutes and he gets concerned but actually 30 minutes it you know to us it's incredible that it can do all of that in 30 minutes [Music] so far we have seen how algorithms are capable of amazing feats from solving abstract mathematical problems to helping us find stuff on the world wide web and the key thing for all of these algorithms is their speed so the important feature of a good algorithm is first that it better be correct but once you know that it's correct it's also
important that it runs quickly there's no good having an algorithm it takes um longer than your lifetime to run if you're wanting the result tomorrow this face detection algorithm is an example of an efficient algorithm because it's efficient it's able to run in real time and that's what makes it useful but just as in real life some problems are harder than others every now and then algorithms meet their match i think the most common misconception about algorithms is just that there's you know the algorithms can do anything i think people don't really know about the
limits that you know some problems simply cannot be solved by efficient algorithms there are some places where efficient algorithms cannot go lines in the sand that can't be crossed the trouble is knowing which problems they can solve and which they can't [Music] take this rubik's cube and imagine the more general challenge of trying to solve a cube of arbitrary dimensions so for example with 50 squares down each side now you might expect this to be one of the really fiendishly difficult problems but actually it belongs in the easy camp we know an algorithm that can
solve the general rubik's cube in a reasonable amount of time [Music] although it looks hard this problem can be cracked by efficient algorithms [Music] however here's one that definitely can't imagine you've got a drafts board of arbitrary size and an arrangement of pieces on the board the challenge is to work out whether white can force a win from this position now drafts is a pretty easy game but it's been mathematically proven that there's no algorithm that can solve this problem efficiently it's an inherently difficult problem the only way to solve this puzzle is through sheer
hard slog working out all the millions of possibilities [Music] so this problem lies firmly beyond the reach of efficient algorithms it can't be solved quickly [Music] but for some problems how hard they are is not clear-cut this is a large sudoku it's got 625 squares one of the nice things about sudoku is that once you've found a solution it's relatively straightforward to check whether or not it's right and this is true however large the puzzle in this case i just got to check each row column and block doesn't feature a number twice sudoku belongs to
a very special category of problems that all share this characteristic but once you've come up with a solution it's always easy to check it the mystery is whether there's an efficient algorithm to find the solution in the first place and sudoku is not alone there are lots of problems like this the most intensely studied of them all is known as the traveling salesman problem [Music] a traveling salesman travels door to door city to city selling anything from brushes and hoovers to double glazing [Music] it sounds like a straightforward job but all travelling salesmen face the
same question what's the shortest route to take [Music] so important is this problem that the clay mathematics institute has offered a million dollars for whoever can find an efficient algorithm or prove that none exists the travelling salesman problem goes like this imagine you're a salesman you've got to visit a list of cities represented by the red dots the challenge is to find the shortest route so you visit each city once before returning to your starting point now you might imagine the best thing is to just consider all the routes like this [Music] the method of
checking all possibilities is a type of algorithm and for three cities it works fine because there are only three possible routes to check but what if we add two more cities to the list with five cities there are sixty different possible routes [Music] and if we add another city then there are 360 possible routes and for 10 cities there are over 1.8 million possible routes if our algorithm chugged through them checking all of these at a rate of 10 per second it would take two days before it found the shortest so you can see a
method of trying all the different possibilities a kind of brute force algorithm if you like it's just simply impractical so if somebody found a fast algorithm for the travelling supplement problem that would be hugely significant if one of my students came up with an efficient algorithm for the traveling salesman problem i would get him to explain it to me i would kill him and then i go and claim the clay prize a million dollars but i think my students are safe the problem crops up in lots of areas from soldering circuit boards to planning the
routes for supermarket deliveries but has the travelling salesman problem secretly already been solved a team of scientists working at rothemstead research in harpendom have turned to nature to see if it has found the answer [Music] they're carrying out an elaborate experiment to study how the traveling salesman problem is tackled by the bumblebee bees have to forage for nectar in order to provision their hive um and so they have to visit possibly hundreds of flowers on each trip what they want to do is find an efficient way to go between all these flowers that they visit
the humble bumblebee faces its own traveling salesman problem the flowers are just like the cities and the bee is the travelling salesman one bee will go out foraging uh many many times every day so over the course of the day it really helps to take the most efficient possible route so what we're doing is trying to figure out exactly what rules they're using to to narrow down the possibilities [Music] joe has laid out five feeders which play the role of flowers each feeder has just enough nectar to ensure the bee has to visit all five
to give it a full honey stomach how are you actually uh knowing where it's going for this we're using a harmonic radar so as that spins round and round it's emitting a radar signal and we've attached a small antenna to the back of the b which then reflects the signal from the radar and so this allows us to see exactly where the bee has gone as she moves around the field so how does the bumblebee tackle the traveling salesman problem okay okay switching it on now [Music] with five feeders there are a total of 60
possible routes the shortest is around the outer edge this heat map shows the path taken by a single bee at first it's simply discovering the positions of the feeders then the bee appears to methodically change different parts of the root to see if it can make it shorter within 20 trips it's honed in on an efficient route [Music] this route is not always the absolute shortest but for the bee it's good enough [Music] that's amazing that just after a very few tries they've got to something which is is efficient enough for them to to do
their foraging yes that's right they can't spend days or even you know it could take months or years to try every possibility so they have to very quickly find a route that they can do again and again and again in order to efficiently provide food fantastic i think the bees become my favorite insect now so it's obviously a mathematician at heart absolutely let's be clear bees are not about to be awarded a million dollars they've not miraculously solved the traveling salesman problem because they don't always find the shortest route but their algorithm is a clever
approach in maths it's known as heuristics algorithms that are efficient that don't find the perfect solution but get as close as they can [Music] [Applause] the same heuristic approach has been used to develop an algorithm for heathrow airport let's take off 279 heathrow handles over 1300 flights a day it's europe's busiest airport four three zero for takeoff right surface wind 240 degrees at three knots the challenge for air traffic control is to maximize the number of aircraft departing every hour and ensure that the airport operates both efficiently and british airway safely lineup 27 right behind
one of the key decisions is the order of takeoff we're currently departing a group of medium aircraft which which will be separated warming apart behind that then you can see a 747 which is a large aircraft medium aircraft need to be separated from the turbulence produced by larger aircraft so the ordering of sizes is crucial guidance sequence for takeoff involves really blocking together groups of aircraft so you want large aircraft to be grouped together medium aircraft to be grouped together and that allows the separation between those aircraft to be minimized the other factor that needs
to be considered when planning takeoff is where the planes are heading once we go to the north and once we go to the south the next going to the north next going to the south if all the aircraft were going in the same direction the separation would be much greater and we wouldn't use the runways as efficiently all controllers are sitting in the control towers thinking i've got all these aircraft that are going north all these aircraft they're going south i've got these ones that are large ones so i want to try and group all
the large ones together so i don't have to go from a large one to a small one and it's a very complex pollen to solve in their heads speedway 906 november under control one two zero in 2013 an algorithm joined the team its job is to predict the most likely order for takeoff and advise air traffic control when aircraft should push back from the gates to do this involves nothing less than simulating the entire outward bound operation of the airport carrying out millions of calculations every second the algorithm works by trying to predict what order
the aircraft are going to take off in if it knows what order it they can take off in then it can work backwards and say if it needs to take off at this time then it needs to enter the runway queue at this time then it needs finishing its taxi at this time therefore it needs to start its taxi operation at this time in that case it needs to finish its push back by this time so it needs to start its pushback by this time and it can work all the way back from what time
it should take off to what time it should start pushing back [Music] [Applause] the output of the algorithm is given to air traffic control through the airport's internal computer system and displayed the pilot at the gate in the form of the t sat the recommended push back time the pilot can look on the stand entry system to actually see what time he is expecting to depart the biggest benefit of the algorithm is that it means you can hold aircraft on stand for longer without them taking off any later so there's no loss for any passengers
in terms of delays what you can do is you can start your engines later in actual fact if we sail two minutes taxi time on the way to the end of runway over a year that's actually 15 million pounds worth of fuel saving the heathrow sequencing algorithm shows just what can be accomplished with the heuristic approach just like the bees the algorithm is not finding the absolute perfect solution all the time but nevertheless makes a tough job that bit easier we're very proud of the algorithm because it actually now we feel models the real world
and is of use [Music] in the beginning algorithms were created by mathematicians for mathematicians and over the last century algorithms have been created for computers but perhaps our relationship is about to go through a dramatic revolution [Music] at microsoft research in cambridge scientists are using new techniques to develop algorithms blurring the boundary between inventor and the algorithm itself this is the connect skeletal tracking algorithm the amazing thing is that it's able to identify the different parts of my body so you can see that it's colored the top of my head in red and my right
hand here in blue you can see it's colored my neck green now this algorithm has never met me before doesn't know how i'm going to move in space but just using the data coming from this special camera here measuring the distance from the camera to my body it's able to produce this map whatever posture i take using nothing more than the input from the special depth sensing camera the algorithm is able to accurately identify pixel by pixel the different parts of my body it was developed for the microsoft xbox console to track the movement of
a player's body posture in real time but just as remarkable as what this algorithm can do is the process behind how it was created as researcher jamie shotton explains what's happening is that every pixel in the image we are running an algorithm called a decision tree and you can think of a decision tree as a game of 20 questions so the decision tree is sort of taking a pixel say on my hand and trying to decide okay i've got to color that blue because that's that's on the hand rather than on my body yes the
key to a decision tree is the fact that the 20 questions that you ask um are not the same for every pixel that we're trying to classify and the the full set of the possible questions that could be answered is exponential it's two to the twenty twenty right okay so that's over a million questions there's a lot of questions you're gonna have to program in there yes it would take far too long and be far too error-prone for us as humans to program that by hand so the algorithm's kind of writing itself or absolutely [Music]
the algorithm was not designed by jamie but instead through a process called machine learning [Music] it involved showing the algorithm millions of training images of bodies in different poses and of various shapes and sizes from the very fat to the very thin the very short the very tall and from this the algorithm essentially learned by example devising its own rules where our intelligence comes in as the designers of the system is in not in programming the algorithm per se but in designing the training data set to capture all of the kind of variations that we
expect to see when we deploy this system in people's living rooms to play their games so in the end do you actually know what the algorithm is doing we can get a sense of what it's trying to do and how it's roughly working but we couldn't possibly really understand what exactly is going on the same approach of machine learning has been used in other applications for example this algorithm is able to do something that for a long time was thought to be a skill exclusive to neurosurgeons and radiologists from an mri scan the algorithm can
identify and map a brain tumor in 3d meaning that a job that normally takes an hour can be done in a matter of minutes professor chris bishop is interested in developing the concept of machine learning even further to create algorithms that can learn just like we do directly from experience so this demonstration i think illustrates the the direction that algorithms will go in the years ahead okay i can see a lot of films up here so what is it what's the algorithm going to do what we've got is a couple of hundred of the most
commonly watched films and what it's going to do it's going to learn about your personal likes and dislikes okay now it's already been trained so it's a machine learning algorithm behind the scenes but it's already been trained on data from about 10 000 people what it's going to do now is to learn about your your preferences now the moment it knows nothing about you so these films are just arranged at random on the screen so what i need you to do is to to find one of these films either one that you like or one
that you don't like um if you like it you can drag it across to the green region if you don't like it across the red region all right so uh rushmore i'm a big fan of rushmore you like rushmore okay right so what's happening now is that if a film is down the right-hand side near the green region it's very confident you'll like it okay so down here close to the red region it's very confident you won't like it in the middle it's 50 50. it doesn't really know so what if i choose a movie
in the middle here i'm not a great austin powers fan all right let's um shoot that one okay so you see that they're beginning to spread out sideways a little it's gonna be a little bit more confident yeah yeah yeah it's pretty good here because yeah i'm a big fan of uh doctor strangelove and um yeah i'm a big fan of woody allen but um spinal tap no i think uh he thinks i'll like that so that's interesting so when when it was confident you liked them and you said you liked them not much happened
because it didn't it didn't learn much from that data yeah when it was confident you'd like it in the case of spinal tap and you said i don't like it there was a big change it's learning things from me i'm actually changing the algorithm as i interact with it exactly whereas connect was was trained in the laboratory and then frozen this algorithm continues to adapt and continues to evolve throughout its life the more films that you raters like and don't like the more it knows about you personally and the better able it is to make
good recommendations this algorithm is beginning to feel much more human in in the way that it interacts with the world is that your aim to find a way to produce algorithms for a bit like the way that we exactly it's a step down that very long road to producing machines that really are as capable as the human brain we've got a long way to go but this is a small step in that direction because it's not fixed anymore it's now continuing to learn just the same way that we continue to learn sort of in our
daily lives i think we're just starting to realize the full potential of algorithms and i have one more place i want to visit which i'm told will give me a glimpse of just how much they're able to do for us [Applause] it's a world where almost everything is automated [Music] where algorithms are in control it's the largest automated grocery warehouse on earth it belongs to the online grocery retailer ricardo and it's the equivalent of 45 supermarkets in one over two million items flow through this warehouse every day at any one time there's something like 7
000 crates going over 25 kilometers of track and controlling every aspect of this astonishing spectacle of algorithms [Music] each of those red crates is part of a customer order and and there are but and they may go on from here to find other items that they want across the warehouse until they're eventually finished loaded onto a van and then driven out by our routing systems on a on a route which is of in many ways is solving you know problems like the traveling salesman problem i mean there are decisions being made all over the place
as a regret goes this way then that way well the complexity behind all of this is beyond what you know any human could control or solve and and that is where these these algorithms these problem-solving techniques come in to overcome those challenges [Music] everywhere you look the invisible hand of the algorithm is at work forecasting algorithms monitor and replenish the stock of more than 43 000 products anticipating customer demand control system algorithms manage the traffic of the more than seven thousand crates around the warehouse and van routing algorithms control the movement of the fleet of
over 1500 vans testing over four million different route combinations every second you can almost see the mind of the machine at work and it's not a static process so that's why there's a huge amount of machine learning in here and so it's elected to self-adapting organism it's constantly having to learn how to do it better and people couldn't do that the machine has to tune itself so who would you say was actually in control of the whole thing well ultimately it's the algorithms that are in control no i i think i'm getting sort of algorithmic
hot flushes by looking at this amazing thing in some sense this warehouse is like a little microcosm of the modern world algorithms are running everything from search engines on the internet sat nav even keeping our credit card secure our world wouldn't function without the power of these algorithms the open university have produced a free pack for you to learn create and discover more about digital technology past and present to order your copy phone 0300 303 0553 or follow the link below to the open university [Applause] coming up next tonight a flash of inspiration may change
your life or just your lunch but how does it come about horizon investigates here on bbc four next [Applause] [Music] you
