Applying Machine Learning Like a Responsible Adult

[Music] [Applause] hey guys my name is Ben I'm the lead AI developer at Havoc hi and my name is Lynn and I'm a PhD student at the University of Pennsylvania Aly is graduating in a few months so if you like what you hear today then you should totally hire her so first let's talk about why people don't use machine learning because there's been a lot of resistance to this in game AI uh people say it's too slow to execute it you can't really afford it in the context of a real-time game they say it's too opaque you can't figure out what it's doing when it does something wrong so you can't correct the weaknesses and of course it's too unreliable it doesn't get the right answer often enough is machine learning slow well this is an autonomous helicopter it is simultaneously flipping in place and pering it's a move known as the uh chaos accomplishing this crazy difficult feat requires adjusting four

separate control set settings 50 times a second what about opaque these are the probability models being used by a simple handwriting recognizer you may notice they basically just look like letters there is nothing opaque about this model if you want to know why c and e are being classified poorly with respect to each other well that's because their probability models look a lot alike as for unreliable this is the lifeline Auto it's an automatic defibrillator similar to those positioned throughout muscone Hall this device uses a ml model of cardiac rhythms to diagnose ventricular fibrillation this box literally makes life and death decisions based on ML and it does a pretty good job here's a cup of cold coffee the reason game AI people have had such a bad experience with ML is not that ml is inherently bad it's that we as programmers don't automatically know how to do good ml for most of us our

exposure to ml in school was basically limited to neural networks and genetic algorithms these things are easy to understand they're cool and you can program them without knowing much math statisticians in school learn about clustering and component analysis and decision trees and boosting and bagging because they have the background for them the lesson is if you really want to try out ml you'll need to step outside your comfort zone and learn some unfamiliar Concepts it's potentially very rewarding ml is at its best when solving problems that you have no idea how to code up because ml is all about understanding the underlying process for you ml can help you refine your AI automatically rather than by endless knob tweaking and testing it'll help you build NPCs with varied personalities based on captured gameplay data and a whole lot more like a lot of tools until you really know how to use ml you can't get a full full

appreciation of all the things you can use it for all right so before we continue on let's uh go over some terminology so first off the primary goal of any machine learning algorithm is generalizability um as Ben mentioned previously if we understood the process well enough to just code it up directly that's what we would do we would just code it up um so what we're trying to do instead is is based on examples we have already we're trying to learn a model which allows us to predict classify or cluster based on new examples that we've never seen before and so how do we do this uh well in general there are two steps to any machine learning algorithm the first step is the training phase where um given the examples that we have we try to fit the model so that it explains those examples as well as possible and then once we have that um we can then see how well our model works on new examples has never seen

before so what do we mean by models um so model is a very generic term and it's just the representation of the underlying process and its job is just to encode how the input should relate to the output and this under the umbrella of machine learning there are many many many different models that are tools that you might use so for example decision trees and kers neighbors are two techniques that Ben's going to talk about in a little bit but it also includes things like linear regression neural Nets knife base for Vector machines and and many many many many more so let's just talk briefly about features so the machine learning inputs are often called features and a lot of times you're going to have many different features that you're then going to collect together in a big feature vector and so again features are very domain specific they're going to look really different based on the applications that you're working on so to give an example if you're working

with image data you have here a 32x32 pixel image you might flatten that into a 1x 1024 feature Vector alternatively suppose you're working with animation data and you have motion features so one thing you might do is just put all the key frames one after each other in a big feature vector and then each key frame is itself just a list of joint rotation values so that's just a big Vector of real numbers suppose you're working with text a feature Vector you might use is um a series of word counts so for example um each element of your feature Vector will be the number of times a certain word appeared in the document that you're analyzing and then in addition just a notational thing once we have everything in these big feature vectors it's very convenient to then put them into big matrices and uh these matrices might represent a training set or a test set or new data we've never seen before and

just the idea here is each feature Vector is just stacked one on top of each other so that each row is an example and then it just follows that each column is a feature and then briefly just to talk about the term labels um the output of your machine learning algorithm are often referred to as labels particularly for classification and so some examples you might see your gesture type is fraudulent or is Spam so the the types of things that your machine learning algorithms trying to predict or classify and similarly to you know your feature vectors we might want to um combine all these things together into a convenient Matrix form so here each row is the outcome for particular uh corresponding example and that sums up uh some terminology now now I'd like to cover a small number of techniques that I think are particularly worth knowing this is nowhere near comprehensive it's not all there is to ml but it'll be a good start to understanding the various tools that are out

there uh now there's three major areas that machine learning tackles supervised learning where you train the system to answer questions unsupervised learning where you uncover patterns and relationships in the data and finally reinforcement learning where the system learns how to behave optimally in a particular task I'm going to focus specifically on supervised learning which I think is the most widely useful area most of the problems you have in ml will turn out to be supervised learning problems first of all decision trees decision trees are one of my favorite ml techniques specifically for game AI stuff they're beautifully simple in their operation there's almost nothing nonobvious about them here's a decision tree that an NPC might use to determine whether to attack or Retreat it starts at the root node and at each branch it goes up or down depending on the answer to the test in the node so first it checks whether its hit points are above 50 above 50 goes up below 50 goes down if it goes down then checks whether the player is stunned it stunned he attacks

otherwise he Retreats and if the hit points are above 50 he always attacks so nothing weird here this is just two if statements the real power here is in having the computer build the decision tree for you say you've got this big table of example play situations that your designers or your testers came up with in this situation with these hit points and that hair color and this and that and the other thing uh the correct decision was to attack looking at this table it's not easy to see which factors are important and which never matter and which are only important in certain special situations but a decision Tree Learning algorithm will take this data set and spit out a decision tree like this one decision trees are what's known as a white box algorithm you can look at a neural Network's weights all day and not have any idea why it's making some particular classification that you think it shouldn't be making uh it just isn't uh

questionable uh but everything a decision tree does is clearly exposed if you want to know what it was thinking when it gave you a particular result you simply follow the branches it took from the root to the leaf uh seeing what factors were important seeing what it branched on and at each node you can even see what training examples were relevant to splitting the tree in such and such a way and although machine learning people wouldn't normally do this you can even manually tweak and automatically built decision tree if you think some branch is stupid and it just came out from a weird quirk in your training data you can just go ahead and snip it out the algorithm most commonly used for decision trees is called ID3 and it's really easy to wrap your head around it starts with the whole training set and you decide which question you can ask to separate the different output labels as cleanly as possible in the attack or Retreat case hit points were a much better predictor than say hair color knowing just the hit points didn't

always tell you what you should do but it did give you a pretty big hint then you separate the examples based on that feature then you make those subsets Children of the decision node with that test in it if all the labels in a subset match as you can see on top all the labels are attack that becomes a leaf in your decision tree otherwise with the remaining examples you look for another feature and you keep dividing for continuous thresholds like hit points you need a way to choose a split threshold like the point at which things get divided um a really simple approach is to try splitting at a few random different thresholds and see which one works better there are more clever approaches you can use but it gets into some fairly deep stats decision Tree Learning isn't perfect it can be difficult to tune the complexity of the trees over complicated ones will fix fix at on irrelevant

features once they get down near the leaves while oversimplified ones will ignore genuine special cases entirely and they're not very good at discovering relationships between continuous features like if you should Retreat when your hit points get below the player attack strength nevertheless the Simplicity and the transparency here can be a huge benefit if you only remember one technique from today let it be the ID3 algorithm for building decision trees onto the nearest neighbor algorithm with this one there's no real training process the model is the training data when it needs to make a classification it just determines say what's the most similar training example it's seen before based on the numbers in that example being close to the input numbers According to some measure of distance which I'll talk a b about later and it just uses that example's label it's dead simple nearest neighbor by itself is really prone to

overfitting if there's any problems in your training set any examples that maybe should have been labeled differently that's going to show up in your model as classification errors this test point should probably be yellow but it happens to be closest to that red dot so what's always done instead is called K nearest neighbors where you take the closest say five examples and let them vote on what the label should be maybe giving more weight to closer examples what just happened here oh I think I went to the last slide give me a sec the higher the K is uh the more it Smooths over errors in your training set but uh it makes it harder to respect genuine special cases where the classification should differ from other nearby examples KNN has some problems of its own the big

one is dimensionality if your data set has only a few Dimensions you can do things really efficiently uh with techniques like KD trees but in higher Dimensions these things don't work very well you end up basically doing a linear scan through all your data and that can get really slow there's also a subtler problem where in really high dimensions a few training examples more or less take over the entire data set uh a little go for uh dimensionality later on the other thing is is you need to decide what distance means if your features aren't all in the same units and generally they're not then you need to scale them appropriately uh L again we'll talk about that later and distance get even gets even more difficult to work with when your examples aren't continuous but rather categorical data what should the distance between orc and Goblin be which one is closer to horse uh it's a weird question to ask but you need an answer for it if you're going to do K's Neighbors so KNN can give you really high quality

results but it's limited to low-dimensional feature spaces and you'll want your training data to be really clean genetic algorithms which is really a whole spectrum of techniques but they all have a few things in common the basic idea is to find a good solution over time by trying out a bunch of potential solutions they get tested out against some blackbox Fitness function which decides how awesome each one is the ones that do well get to pass on their genes to the next generation of solutions usually the genes are randomly changed a little bit and you keep doing that until you breed a a race of super Solutions this isn't exactly an ml technique specifically because it's not necessarily about learning from data but if you're trying to build a really good model you can use your test set as the black box and have the genetic algorithm mess around with the parameters of your model to make it as good as possible

there's a couple of decisions to be made When developing a genetic algorithm the most important one is coming up with the rules of how genes get passed down to the Next Generation a really common approach is called roulette wheel selection where you randomly pick genes directly weighted by Fitness score so if Model A scored twice as well as model B then each gene is twice as likely to come from a than from B roulette wheel selection relies on a well- behaved Fitness score if it's possible for one contestant to rack up a really high score compared to slightly inferior contestants then those other contestants genes are just going to disappear in the Next Generation even if some of them could have been useful when combined so an alternative is rank selection where instead of using the score directly you wait the selection based on what place each contestant came in so say half the genes come from the first Place solution and a quarter come

from the second place solution and so on um regardless of what the raw scores were this avoids that crowding out effect particularly in the early Generations when things are pretty random and some people just happen to be cooler uh it does however tend to slow things down it takes more generations to converge to an Optimum genetic algorithms also aren't always the way to go the big thing is they don't really know anything about the problem they're trying to solve they're just banging at it if there's an optimization method which is specific to the model like ID3 for decision trees it'll usually beat a genetic algorithm in terms of speed and precision the other problem with gas is there are a whole extra panel of knobs and buttons to mess with which isn't necessarily what you want it can be really timec consuming to go through the results of a genetic algorithm to try to figure out why it did what it did so tweaking it is usually a try andc sort of thing which is obviously not great

genetic algorithms though are really flexible and it can be tempting to think of them as the solution to every problem but I think they're best used as a backup plan once you've done everything you could with more model specific techniques okay so now let's talk about all the different things that can go wrong um starting with the wrong features cuz having good features can really help your model perform better and it's not a cut and dry process so here's a situation you might see uh you've tried a lot of different models but you keep getting disappointing results so what should you do so the first thing you should do is look at your data and do something called exploratory data analysis or Eda and what this is going to do is let you check all your assumptions so you can basically see which of your input variables actually seem to have a relationship with the outcomes that you're interested in and ALS also you'll be able to see what the shape and distributions of the various uh features

you're interested in are then once you've done that you can now boil down your data so you can remove irrelevancies such as income featur uh input features that have nothing to do with the outcome or you might even Target some of your features um for example cropping images so that the model can just focus on the aspects of the features that are probably most relevant and then once you've done that you can even look at your data some more and check whether transformations of your data help so for example you might see whether linearizing your data or normalizing your data can actually help um uh help your model work with your features so here you know we can apply a log transform and now we have something that looks like a normal distribution or conversely if we're working with images we we could desaturate the image so we work with single intensity values instead of a triplet of RGB numbers and furthermore we might even try blurring it so that the changes between pixels are gradual

and another thing we might do just in the spirit of Transformations and this is something that's come up a couple times in this session is make sure all your features have comparable scale and it's really easy to to to have an intuition about why this needs to be true um particularly if your your your algorithm is based on distance metrics um here's an example so like suppose you have a feature and it's got three uh feature Vector you got three features in it weapon power player level and gold amount and suppose gold amount has a range that's much much greater than all the other features any distance metric that's based on this feature Vector is going to be completely dominated by gold amounts so what should you do you should scale down gold amounts so that it has basically the same range as the other features in fact you might want to renormalize all these features so that they lie between zero and one so here's another thing you might see um you're feeding in 50,000 features and your classifier sucks furthermore it worked better when it was only features so what might be going on well

it's very likely that you're you've come across the curse of dimensionality and so the issue here is when when your beh uh when your features become very very very highly dimensional everything becomes far apart like our intuition about distances don't don't apply the same way they do in three and four and small uh small dimensions and and the other thing that's a problem is as your feature space grows you need more and more examples to understand it so like for the same size training set you get more bang for your buck when you have fewer features than when you have a lot so what can you do about this well you can try reducing the dimensionality of your data for example you might use a technique like principal component analysis um and so what PCA will do for you is it can take a big Vector of possibly correlated features and then reduce them down into a small um number of features that are uncorrelated and so

here's an example based on uh walking data um so classes of motion work great with PCA because a lot of the joint motions uh joint movements tend to be correlated like the arms and legs uh move together so here you know we started with a feature Vector that had 540 features in it and PCA reduces it to 29 features so here's another situation you might encounter you have insanely good in the test set but the model is still terrible in practice so here one possible problem is contamination just some of your test data snuck into your training set and you should just fix it's a bug you should just check and fix your code the other thing that might be happening which is a little more subtle is data data leakage and here what what's going on is you're using a feature for prediction that's essentially cheating like a feature that you wouldn't normally have available for for prediction and so this is something

that can particularly happen if you're you're working with log file data for example and and here you know suppose you're trying to predict score from weapon power and player level um if score is a function of kills so that the more kills you get the higher your score you don't want to use the number of kills for prediction because that's essentially cheating you don't have that data and the next possibility is uh sampling bias um and in this case the training data is just not similar enough to the real world and basically decisions of how what and when you log data can really matter and just to kind of give some intuition about why this why this can happen or why this is true um you know just think about the behaviors of players like the players who log in every day likely behave really differently than the players who log in once a week so now let's talk about when things go wrong with the wrong model so here's the situation you've tried a lot of different features but you have disappointing

results so what's a good solution well trying a different model or actually you can try lots and lots of models and uh there are tools like WCA which can come to the rescue and so in particular W will let you like U input a big Matrix of features and then run it on lots and lots of different models and give you the results and it even has uh tools for clustering and pre-processing too the other thing you might try is using an ensemble of models and uh some names for different Ensemble techniques are boosting stacking bagging and the basic idea of all of these is a bunch of weak Learners um working together can often outperform a more sophisticated learner and to give an example large Ensemble models were the best performers in the N Netflix prize a couple years ago and so now let's talk about overfitting which is another thing that's been mentioned a lot in this session so here the situation is your classifier is amazing accuracy with with the training set but performs poorly on

data it's never seen before so what's happening basically what's happening is your model is memorizing the training set and is lost its ability to generalize and this is just part of a broader challenge when you're when you're developing and designing your models where you need to balance having a model that's too simple where the data can't capture the patterns that you want to capture like so for example having a decision tree that doesn't have enough depth using a linear um uh linear model when it's not appropriate or using K's neighbor with too many neighbors versus The Other Extreme where you have a model that's way too complex it has too many parameters you can fit too many bells and whistles and you get these skitso fits with no ability to generalize and so this can happen when you have decision trees with arbitrary deaths or using only one nearest neighbor or or using U two high dimensional spline to fit your uh data points so some over fitty uh algorithms

again things that have been mentioned today K nearest neighbors with low k um artificial neural networks with lots of neurons decision trees with arbitrary dep and Ensemble models so how do you protect yourself against this um well using cross validation is is is great so so what this lets you do is estimate how well your model performs on new data um and um and how does it do that well by holding out uh it lets you hold out subsets of your training data which you can then use for testing and while you're doing this you can try different uh model parameters to determine the balance between a good balance between Simplicity and power so just let me quickly show you how it works it's very simple you split your examples into training a test set so you here we have 90 10 split train your model then you evaluate your model just on your test test data and then you redo that with totally new um training and test dat test

data and then you do the and then the average over multiple test sets is your actual estimate of how you're going to do on new data you've never seen before so now to sum up if You' fallen asleep during this talk please wake up and internalize the following points contrary to what may have been your experience in the past ml can be real time it can be transparent it can be totally reliable for your needs it can be the best way for you to do your job but in order to get good results out of it you need to step outside your comfort zone you need to take off your programmer hat uh you need to move beyond the very small and limiting number of algorithms you've learned for machine learning such as artificial neural networks and genetic algorithms you need to understand at least some of the theoretical underpinnings of features and models and you need to be aware of things like overfitting that really bite us all in the butt when we're doing this stuff

if you want more information about this there is a free online course on machine learning offered by Stanford University and a couple of other uh good reads in this area thank you for your time