Unsupervised Machine Learning

In this case, we do not have any data on the results that are expected from our analysis. This is a more classical approach to finding patterns and trying to determine what the data is “telling” us. We focus on finding generic patterns in the dataset and using these to gain insights. Unsupervised learning algorithms can be divided into three categories.

Supervised Machine Learning

Here we supervise how the model learns by giving it labeled data. The labeled data contains the expected values of outputs of (Ys) for each data point of features (Xs). For example, from the medical records dataset, we may have data showing which patients have a condition like hypertension. Now we can establish a relationship among the Xs—blood pressure, sugar, cholesterol, etc.—to the presence or absence of hypertension (the Y). This is supervised learning. Usually the thing that we are looking for is considered a positive. So, if we are looking for patients with hypertension, those patient data points are positives (absolutely nothing to do with the sentiment of the word—data scientists are weird that way!). Here the output labels are very important. If we incorrectly label a patient with healthy metrics as positive, our model will learn the wrong patterns and make false predictions. It's like teaching a child bad stuff like stealing is good!

The ML model generated by supervised learning is basically a relationship between the Xs and the Ys. It's a function or an analytic that we saw in Figure 1.9 from Chapter 1. In other words, we are mapping the Xs to the Ys and the function or relation that gives us this mapping is called the model. Once you have the model, you can give it the Xs and it will predict the Ys for those specific inputs. The way this internal relationship is stored in the model uses special parameters called weights. Whether you have a simple linear regression model or a complex neural network, it is essentially a way of representing inputs as a function of outputs using weights.

When we first define a model and initialize these weights, the model will not be able to predict the Ys correctly. We need to conduct a process of training the model so that it can learn patterns from training data. This learning process basically involves optimizing these internal weights so that the model can make predictions close to expected results. So ultimately the ML problem boils down to an optimization problem where you are adjusting weight parameters of the model to make it fit the training data.

For optimization, we need an objective function that we must minimize or maximize. Here our objective function is called a Cost or Error function that measures the difference in predicted and expected outputs. Our model training process tries to minimize this cost function iteratively. We use a popular optimization technique called gradient descent to optimize the weights. In this method, we use the partial derivative or gradient of the cost function with respect to each weight to calculate a correction to be applied to that weight. This correction is expected to improve the weight so that the model makes better predictions. In optimization terms, this correction will take us closer to the objective or minima.

We iterate through our training data and keep correcting the model weights. This is also called the model training process. The amount by which the weight improves is controlled by a parameter called the learning rate. Parameters that are not learned during training are called hyper‐parameters and we need to define them at the beginning of the training process. We look at all these concepts in detail in the next section with an example on linear regression.

Supervised ML is normally divided into two areas, discussed next.

Reinforcement Learning

This is very different from the earlier two areas. In RL, we try to build agents that learn patterns and can take actions. These agents “observe” the real world as a person makes decisions and tries to learn the policies used for making these decisions. For example, you may have read about AI beating humans at chess and Go—that's using RL. Also, all your favorite video games like Call of Duty and GTA have an AI engine that's using RL.

It's best to understand the ML methods using real examples. I start with a very simple example to explain the concept. Each method has several algorithms to build a model. In this book, we will not go into the details of every algorithm. My focus is to show how you apply the algorithm and get results and then evaluate your results. I have many references that explain each algorithm in detail.

We will first start with a very basic dataset. Then we will get into some more detailed datasets from UCI. I share the Python code for each algorithm using the popular Scikit‐Learn library. The code will be heavily commented so you can easily re‐create it in a different language.

All right, let's get started.

Unsupervised Learning

Let's just look at two features—size (or area) and locality—and see if we find any patterns. We will intentionally not include price because we want to see if size and locality influence the price. We will start with unsupervised learning, in particular the clustering method. Say we want to divide these houses into three groups—high‐priced, medium, and low‐priced. We know the number of clusters we want, so we can use the K‐Means algorithm. The principle behind K‐Means is to find K number of clusters in the dataset and separate the data into these clusters. The clusters are organized so that relative to all features, the data is grouped such that similar data points are together in a cluster. For each cluster, the centroid mean is used as the representation. For any point in the dataset, the shortest distance to the cluster centroid determines to which cluster it is assigned.

We will use this same concept and find clusters in our data. First let's use the Pandas library to load our dataset. The dataset is loaded from a CSV file that is stored on disk or Cloud storage like S3 or Google. Pandas loads the data and creates an in‐memory object called a data frame.

A data frame is a common way of representing structured data in data science tools like Pandas and R. A data frame stores the data like a table with features as columns with distinct headings and rows with data. They are optimized so that we could easily search for data by querying a feature/column and getting the matching data points or records. Also, since they are stored as binary objects they can be used to run statistical calculations like mean, median, etc., quickly. We will load data from the CSV file into a Pandas data frame. See Listing 2.3.

Now we will apply the K‐Means algorithm to divide the dataset into clusters and assign each record to a particular cluster. We will apply this to our independent variables or Xs—which are area/size and locality. The intent is to see if the clustering can find patterns and then we will relate these patterns to pricing. We do not use the Ys to supervise our algorithm. This is a case of unsupervised learning. See Listing 2.4.

The result is interesting. We see a grouping of points for the three clusters corresponding to the three groups we saw in the chart earlier. We see houses with specific combinations of area/size and locality as clusters 0, 1, and 2. The logic that our brain can see by looking at the visual aid (the chart) was determined by the clustering algorithm on its own (see Figure 2.6). This was a very simple and limited dataset. By just observing the data in Figure 2.6, you can see that the houses with a similar size/area and locality rating are grouped together. However, in the real world, when you have thousands of data points and hundreds of features, you cannot easily find these patterns through observation. This is where a clustering algorithm can quickly find patterns in complex data.

Now let's sort our results on the cluster value and see if we find any relationship to the price (see Listing 2.5).

We see the houses in a cluster following a similar pricing structure. Our algorithm captured the variation in the data using area/size and locality and organized the data into groups. These groups show the same variation with respect to a third value of price. In the real world, you will not have clean separation like this. You will need to experiment with different parameters like number of clusters to look for and see what combination gives you the best results.

The number of clusters in this case is a fixed value we provide to the algorithm and is not something that the algorithm learns. These parameters are called hyper‐parameters in ML. Hyper‐parameters normally depend on the algorithm we use. In K‐Means, our hyper‐parameter is the number of clusters. If we use Random Forests, it will be the number of trees and the maximum height of the tree. We will cover Random Forests with an algorithm later in this chapter.

Now using unsupervised learning, we saw some patterns in the data. We see clusters of similar houses and they have similar prices. Let's see if we can apply supervised learning to find the relationship between the area/size and locality and the price of the house. Since we are predicting a value—Price—we will use a regression algorithm. The most popular and simplest algorithm is linear regression.

Supervised Learning: Linear Regression

Linear regression tries to extract a linear relationship from the Xs by fitting a line through the data. Let's take an even simpler example with just one X and one Y and plot the data. See Figure 2.7.

For a simple case with just one X variable, the linear regression equation can be written as shown in Listing 2.6.

What this means is that Y is expressed as a linear function of X. So as X increases, Y will increase and vice versa. This is the simplest of relationships between variables. In the real world, very few cases will show a clean linear relationship that can be expressed as a simple equation. However, data scientists sometimes make an assumption of linearity and try to fit a linear equation to get results quickly. Linear regression usually takes less processing power since there are many statistical shortcuts to solving these problems. These are built into an ML library like Scikit‐Learn to make life easy for us.

w and b are the weights that we want to learn. w is a regular weight associated with a variable (X), while b is known as the bias. Even if the variable becomes zero, the bias term will still give us some value of Y. The bias is equivalent to some assumptions made by the model on predicted outcome even in absence of the influence of inputs.

We collect many samples of X and Y values and use these to calculate w and b. Using basic statistics, we use the X and Y samples collected to find these weight or parameter values. w is the slope of the line and b is the intercept point.

In the simple dataset with just one X and one Y, we will keep changing the weights w and b to see if the line fits the data well. Let's see some examples. We start with zero values and then slowly change values to see how the line starts fitting our data. In the final figure shown in Figure 2.8, the values of w and b seem to be a good assumption for a linear model.

You can see that we will never get a straight line that passes through every data point. The fourth line is our best model. This is the model that gives us minimum error—that is, the minimum distance between the model line and every point in our dataset.

This is how we fit a model on our dataset. However, we normally don't use a manual approach like this because it would take forever. We have clever optimization techniques that help us fit and get the best model. We will see this through an example. Let's look back at our area/size and locality dataset from Listing 2.3.

If we want to fit a linear regression model on this information, we will want to express a relation like the one shown in Listing 2.7.

We see that this is very similar to the single X problem we saw earlier. Now we have two X values. Our job as part of the training process is to find the optimal values for weights w1, w2 and bias b. Again, since we are assuming a linear relation this is a pretty straightforward problem. As we get into more complex ML and DL problems, we will start looking at non‐linear relationships and use very complex equations with many variables. However, the ML training technique you learn here is applicable to those problems as well.

We have a very small dataset with 10 points. Before starting any ML analysis, it is recommended to divide the data into training and validation datasets. The training set contains most of the records, which we will use to build our model. After building the model, we want to see how effective it is with data it has never seen before. That will be done by running the model against the validation set. The code in Listing 2.8 takes the top eight points for training and the remaining two for validation. In practice, we will use functions in the Scikit‐Learn library to do this separation at random. We will cover that in the next example.

We will use the training dataset to learn the weights of the model and the validation dataset to check that the model predicts unseen data properly. Let's understand the model training process. Model training basically involves adjusting weight values (w, b) such that they best fit our training dataset.

How do we decide what best fit is? For that we need a Cost function. The Cost function is basically a way to measure how much our prediction is off from the expected value.

Let's say we choose some random weights initially, just as we did with the single X problem. Based on these values we can pass each of the eight data points from our training set through the model (our equation) and get the corresponding predicted Y values. These predicted Y values will most likely be different from the expected Y values in our training set. Our Cost function needs to quantify the difference between predicted and actual values in the training set. If we are predicting numerical outputs (Regression), we can find a difference of the expected and actual for each training point and combine the difference. If we are predicting a Class membership (Classification), we could use a function that quantifies our error in classification. The Cost function is also known as the Error function—simple because it helps us quantify the error in our predictions.

Now that we passed all our training data through the initial model, our task is to adjust the weights so that we get better at predicting. In other words, we need to adjust weights so that our Cost or Error function reduces. We can now use the Cost function as our objective function for optimization. We optimize the weight values so as to minimize the Cost function. This now becomes a classical optimization problem. We can use popular optimization methods like gradient descent to get the optimal weights—ones that “fit our training data to minimize cost.”

Gradient Descent Optimization

Gradient descent is a popular optimization technique used for training ML algorithms. This is a general‐purpose optimization technique where you try to modify the weights and bias terms so as to build a relationship between your independent variables (Xs) and dependent variables (Ys). We start with an initial approximation of weights and bias terms and build an initial model. We run all the Xs through this model and predict the Ys. We compare predictions to actual and find the errors. Next, we find the gradient of the Cost function we found earlier with respect to each weight and bias term. The gradient is basically the partial derivative of the Cost function with respect to each weight/bias term. Now this gradient will give you the direction and magnitude of how much that particular weight or bias influences your Cost. Using this value, you adjust the weight and bias terms in a direction that reduces Cost. We also account for a learning rate, which is a factor that controls the size of step we take to modify the weight or bias. If we take too big steps we may overshoot our minimum value, but if we take too small steps our convergence to the minimum value may take a long time. Let's apply this to our linear regression example.

For the simple linear regression example earlier, we want to optimize the values of w0, w1, and b in order to minimize the Cost function. When the Cost is the minimum our model gives us the best predictions. Our Cost function has to capture the difference between the predicted and actual values in the training dataset. We don't really care about the sign of the difference—but the actual value of distance. Hence, for linear regression the Cost function we use is either Mean Absolute Error or Mean Squared Error. Let's see the steps in gradient descent, shown in Figure 2.9.

At a high‐level, this is how the gradient descent algorithm works:

• Initiate the weight values to zero or random values. Make a prediction on each X value and get the predicted outcome—let's call it Y'.
• Compare Y' with the actual Y value from training data and find the error, which is equal to Y‐Y'.
• Positive and negative errors may cancel each other—so either take absolute error or squared error so that the sign of error doesn't affect the calculation.
• Find the mean of the total error term using one of the following terms:

  Mean Absolute Error (MAE) 
  = Sum of |Y – Y’| / # training samples
   
  Mean Square Error (MSE) 
  = Sum of (Y – Y’)2 / # training samples
  This is our Cost function! 

Use any one of these Cost functions and try to minimize this Cost (objective) by adjusting the weights—w0 and w1. Now this becomes an optimization problem with w0 and w1 as terms you modify.

Calculate the partial derivative (the gradient) of the Cost function with respect to the weight we want to modify. As shown in the chart in Figure 2.9, the gradient is a Calculus term that gives us the slope of the curve. Gradient tells us in which direction we should modify the weight value (shown with the arrow).

The amount by which we should modify the gradient is controlled by a constant parameter known as the learning rate. If we choose a high learning rate then we may miss the minimum value and overshoot to the other side of curve. A small learning rate will make the learning process very slow since weights don't get changed much. In general, 0.05 is a good learning rate to start with.

Now use the gradient to adjust the weights w0 and w1. Use the learning rate to control how much the weights change at each iteration. Keep optimizing until the Cost is minimum:

w0 = w0 - lambda * d(Cost)/dw0
w1 = w1 - lambda * d(Cost)/dw1 

Here lambda is the learning rate. d is the notation for derivative.

We adjust weights after all the training points have been evaluated for specific weight values. Then we repeat this for new weights and again adjust the weights. This iterative process keeps getting us close to minimum values of the Cost function. We may end our training after so many iterations or once our error is below a particular value.

Applying Gradient Descent to Linear Regression

Let's apply linear regression to our data and find the model weights. Now you see the code in Listing 2.9 is pretty simple and all the complex details of gradient descent are hidden from you—you don't even specify a learning rate. Also, Scikit‐Learn uses some statistical shortcuts to quickly calculate the optimum w0 and w1 values based on training data. However, as we progress to complex models—especially models that combine many learning units together into a network—we will have to carefully configure optimization parameters. These networks of learning units—also referred to as neural networks in ML—are excellent at learning complex non‐obvious patterns in data, but need lots of manual tuning. We discuss tuning these factors (called hyper‐parameters) in Chapter 4.

We fit a linear regression model to our training data and it predicts the equation that relates house price to the area/size and locality. The equation is:

Price = 0.2037 (Area) + 13.5670 (Locality) – 46.3958 

We can also manually solve this using the preceding equation for Area = 95 and Locality = 5:

Price = 0.2037 (95) + 13.5670 (5) – 46.3958 = 40.7910 

This is how linear regression works. Of course, this was an extremely simple dataset. We see that for a complex dataset we may not be able to fit data accurately with a linear model. The metric of MSE or MAE is used to evaluate regression models and when we are left with high values then possibly we have to look at other models. We could look at other regression models like Support Vector Regression, which uses different way to form a model and check for MSE or MAE.

If we keep getting high error values with linear models, then usually we need to start looking at more complex non‐linear models. Most popular in the non‐linear regression methods are neural networks. Using neural networks, you can capture the non‐linearity in the data and try to find models that give you a low error value. Also, for complex models like neural networks we will see a very clever algorithm called back‐propagation that helps us propagate the error between actual and predicted values through the network and quickly calculate gradient values for the Cost function with respect to each weight and bias term. This algorithm developed by Geoffrey Hinton totally revolutionized the field of AI and brought neural networks into prominence. So much so that today they are considered the de facto standard for solving complex problems like computer vision and text and speech recognition.

We talk more about neural networks and back‐propagation later in this chapter.

Supervised Learning: Classification

Now let's talk about the other form of supervised ML—a more popular and common one in real‐world ML—which is classification. In classification, your outcome or dependent variable is not a value but a membership in a class. The outcome can take an integer value from 0 to the number of classes. Extending the earlier example, let's say you have data for location and price of houses and you want to predict if you will buy this or not. This is a common decision we encounter. Our brain makes a mental model of this decision and as we see new data of houses, we decide to buy or not. Now using Machine Learning, we will try to build a model of this decision. This is the most common form of ML problems in the real world. You will have to understand the various features and decide what class each belongs to. We will show a few examples with code to solve this.

This particular problem is a binary classification problem and the output variable can have one of two values—Buy or Don't Buy. We represent this as 0 (Don't Buy) and 1 (Buy). Let's say the data we collected looks like Figure 2.10 when plotted. We have the Price on the y‐axis and the location rating (1–10) on the x‐axis.

A couple of very basic decisions would be to consider only one feature or independent variable. Let's only consider location or price and make a decision. We will define a decision boundary that will help us decide. Figures 2.11 and 2.12 show two such decisions.

Figure 2.11 shows a decision that anything above a particular locality rating we will buy, while Figure 2.12 says that if the house has a price below a particular value, we will buy it.

But, in reality we have to consider both factors together. We can try to fit a linear relation between the variables. So just like the earlier linear regression, we fit a line between the points, but instead of predicting a value, our line tries to separate the data into two classes, as shown in Figure 2.13.

The line is our decision boundary and it separates the points into two classes—buy and don't buy. This approach is known as a logistic regression. For any new point, we can predict a buy or not decision based on where it lies with respect to the model line. Though we use the term “regression,” this technique is a classification technique.

Mathematically, logistic regression does the following:

Buy/NotBuy = LogisticFunction(function(Price, Locality)) 

An alternative way of looking at this is visually as a network, as shown in Figure 2.14.

First, we learn a linear relationship between the variables (new variable Z1)—just like in linear regression. Then we convert that linear term into a number between 0 and 1 using a function. Here we use a function known as a logistic function or Sigmoid function. I will not go into the formula but essentially it produces a result (variable A1) between 0 and 1. This is analogous to a threshold.

Of the Z1 value, which is the linear weighted sum if above a certain threshold—the value gets close to 1; otherwise, it is close to 0. This threshold is what the ML algorithm learns. It uses the results produced—A1—to classify data points into one of two classes. This is a binary classification since we have two classes represented by 0 and 1. We can extend this to multi‐class problems using neural networks. We will see this with examples in Chapter 4.

We use this activation value A1 to classify our data point. If this number is close to 1, then result is one class and if it's close to 0, it's the other class. Depending on the training data, the class membership is decided between 0 and 1. Let's look at a real example and some code.

Let's collect the house area/size, location, and price data and add one more column for Buy or Not. This column will have 0 if you will not buy and 1 if you will buy. Now we want the computer to predict your mental model of why you will predict buy or not. There could be several criteria for buy and don't buy. Based on the data given to us, let's try to build a model that predicts if we will buy a house; see Figure 2.15.

As with the earlier example, let's separate the data into training and validation sets. We take the last two points as test data points, as shown in Listing 2.10.

Now we will fit a logistic regression model on this training data. Then we use the trained model to make a prediction on the two testing data points. See Listing 2.11.

Here are the results:

[1 0]
[1 0] 

From the very limited data, we get pretty good results. However, logistic regression has the limitation that it cannot capture the non‐linear relationship in the data. For example, if we wanted to get a decision boundary like the one shown in Figure 2.16, logistic regression will not help.

This decision boundary has a non‐linear relationship between the variables, so advanced classification methods need to be employed. Some of these are K‐means, decision trees, random forests, and the more complex neural networks.

Metrics for Accuracy: Precision and Recall

Before we get started with training, let's discuss the metrics we will use. Metrics are very important to compare different algorithms and models and see which is accurate. Also, by adjusting the hyper‐parameters, we can achieve significant improvement in prediction, which again needs to be measured and benchmarked.

The accuracy of Machine Learning models is measured using two popular metrics—precision and recall. Figures 2.19 and 2.20 explain the two.

Precision is what we usually attribute to accuracy. If we are playing a game of darts and hit three bull's‐eye targets out of four attempts, our precision is 3/4 or 0.75 or 75%. It's what we use in our everyday lives as a metric of accuracy.

Recall is more complex. It is concerned with the overall outcome we wish to achieve and how our model performs against this. Many times, precision and recall are conflicting metrics—you may have to lower your precision to improve recall.

Let's take an example. Say you are playing a shooting game like Call of Duty. You are in a combat zone facing five enemy shooters. You fire three bullets and take down three of the enemy shooters. Your accuracy is three out of three, which is 100%. However, you have not eliminated the problem. There are still two shooters who can get you. So the high accuracy doesn't really help unless you solve the problem. That is why accuracy alone is not enough and you need a different metric—recall.

In this scenario, your recall is 3/5 which is 60%. Precision focuses on how good you are, while recall tells you if the problem is actually solved. Now say you fire three more shots. You miss one and hit the two remaining targets with the next two shots. Precision tells you how many selected items are relevant. Out of six total shots, five are relevant. Your precision is five out of six, which is 83%. Recall tells us how many relevant items are selected. So out of five shooters, all are shot. Recall is five out of five, or 100%. In this example, we sacrificed our precision to improve the recall.

Let's consider these metrics in terms of true and false positives and negatives.

For the first case with three shots fired, your true positives (shots hitting targets) was three, and your false positives (misses) were zero, which makes the precision 100%. The formula for precision is as follows:

Precision = True Positives / (True Positives + False Positives) 

And the formula for recall is:

Recall = True Positives / (True Positives + False Negatives) 

In our example of the Call of Duty game:

True Positives = Shots fired that got Enemies
False Positives = Shots fired but missed
False Negatives = Enemies that did not get hit 

If you notice, the false negatives are more the property of the environment—while true and false positives measure your skill. If you want to get all the enemies, you need to take more shots and thus risk lowering your precision.

When you took three more shots and got the two enemies, but missed one shot, your new metrics are:

Precision = 5/(5+1) = 83.3%
 
Recall = 5/(5+0) = 100% 

You sacrificed your precision to go after more enemies and achieve 100% recall. As a data scientist, you will often face this scenario. It's not enough to achieve a high precision. You also need to focus on solving the problem at hand.

Now let's get back to building our classification ML model. This is the more popular application of ML, where you predict the outcome as a particular class. Most Deep Learning techniques you will see later are also classification models, but are more complex.

Model‐Based RL

With this approach, we build or have a model of the environment we are building our agent to control. This model can help us answer questions like what result (new state) we will get when taking an action A on the environment in state S to get a reward R. The term model here is used for the environment rather than an ML model of the agent itself—one which we are trying to build. This is a mathematical model that captures the dynamics of the environment. Now we can use a planning algorithm to find the optimal action at any state to get the maximum reward. Basically, we can try several combinations of actions for each state and use the model to get the next state and reward and find the optimal rewarding policy. It comes down to a pure optimization problem.

In the real world, however, it's very difficult to get a true model of your environment. You have to consider the internal physics of the system you are dealing with. Then there are so many noise factors to consider. It becomes highly impractical to build a model of a system that can capture all the states, as well as their transitions and the rewards for different actions. Hence, these techniques are useful for limited and highly simplistic systems.

Let's consider a simple analogy to understand this a little better. Say that Fred is borrowing money from his friend, Anna. Anna has $200 and Fred can ask for any amount. Anna will accept or reject his ask based on some internal rule she has in her mind. Fred doesn't know what is going on inside of Anna's mind, so he doesn't know how much money to ask for.

Here we can think of Anna as our environment E. The state S of environment E is defined by a single variable—the amount of money Anna has. The initial state is that Anna has $200 with her, that is s0 = 200. Fred is our RL agent who takes an action A on the environment E. The action in this case is asking for a certain amount of money. Based on the amount of money he asks for, Anna will provide a reward R, which may be positive (accepts the ask) or negative (rejects the ask). So, our job is to figure out how much money Fred can ask Anna for, without her saying no. Figure 2.30 shows this concept.

Model‐based RL is where we know the internal dynamics of our environment. In this example, if we know what Anna is thinking and how much money she is willing to part with, we have a simple solution to how much we should ask her for. Say Anna feels that as long as she has at least $100, then she is good. Fred can ask for up to $100 and she will most likely say yes. Here we have the environment E modeled and we know its internal workings. It's a highly simplified example, but the bottom line is that we know enough about the environment E to influence our action A and find a simple solution.

However, the real world is not so simple. There are many variables and constraints to consider as well as factors affecting how the environment behaves. It is very difficult to find the right model of the environment.

Consider a real‐world example of driving a car. We want an agent that controls the throttle position and braking so that we can drive from point A to point B. There are too many variables involved. We have to consider the dynamics of the actual car and its components like engine, brakes, throttle, etc. We have to consider wind resistance and ground friction. We have to consider safety features like spotting pedestrians and other vehicles and avoiding them. You can see how quickly this problem becomes big and it's almost impossible to accurately model such a complex environment. Hence, we need an alternate means of building our agents other than using deterministic models. That is where model‐free RL agents come into play. In fact, model‐free agents are the most popular RL methods for practical applications.

Model‐Free RL

In this case, we don't have a model of the environment. Rather we take a trial‐and‐error approach to determine the patterns for how the environment behaves. We run trials on the real system or a simulator and observe the results and learn from these observations. Through trial and error, our agent learns the patterns of actions that maximize rewards for particular states.

Let's consider an example of this approach with our friends Fred and Anna. Without any knowledge of how Anna decides on giving money out, Fred is left with no option but to try out a few requests, as shown in Figure 2.31.

You can see that since Fred does not know what Anna is thinking—or the agent does not know the model of the environment—he keeps taking actions and tries to understand how Anna will react. He initially starts asking for small amounts, such as $20 and $40, and increases his ask until he gets rejected. After a rejection, he makes his ask smaller until he gets acceptance again. He also tries a new approach where he returns $20 and asks for it so that he knows how much Anna will give away.

This is the process of learning a policy that Fred is going through. The policy is what will drive his actions and, through this trial‐and‐error approach, Fred or our agent learns a good action‐making policy. The different RL algorithms like SARSA, Q‐Learning, and Deep Q Networks (DQN) take different approaches to analyzing the data and learning a good policy. The key thing that affects how an algorithm learns is how it strikes a balance between exploitation and exploration. Let's look at this in some detail:

• Exploitation means focusing on the current positive reinforcement and continuing actions along the same policy. So, if Fred got a positive reinforcement when he asked for $40 and then a negative response when he asked for $50, he can learn that as a policy and stop right there. From here, he can assume that Anna will not part with anything more than $140. Now he can keep exploiting this further by returning and borrowing the same amounts by following a strict policy that Anna's net has to be above $140. In some problems, exploitation may serve as a good strategy, especially when you arrive at a good solution immediately. However, in this case you can see that it is not.
• Exploration is when you deviate from the current policy and try something new. After being rejected for $50, Fred explores the environment further and asks for a lower amount, $30. This time he gets acceptance so the exploration approach worked. Now he can keep exploring further and try to arrive at a better policy. Again, we see that the final policy he learns in Figure 2.31 is not optimal. He could try to borrow $10 more after Anna's net reaches $110 and it will work.

RL algorithms may use different types of policies to determine the right action for the agent based on the state. For example, a random policy will have the agent take random actions. In this case, Fred will keep borrowing and returning random amounts of money until he learns the threshold amount beyond which Anna won't lend. Another policy may be a greedy policy, where Fred keeps asking for more money and chooses actions that get him the most immediate rewards.

This is how model‐free RL works. The agent tries several exploration and exploitation strategies to find an optimal policy, which can be used to take further actions. Let's next discuss a couple of the most popular RL model‐free algorithms used in practice—Q‐Learning and DQN.

Q‐Learning

The idea of Q‐Learning is to choose a policy that maximizes long‐term rewards. The concept here is to use a calculation, called the Q‐Value, that measures the long‐term reward achieved by taking a particular action when the environment is at a particular state. Hence, the Q‐Learning table, or Q‐Table, has a number of rows equal to the number of possible states and a number of columns for all the possible actions. It is usually initialized with all zero values. The cells with unrelated states and actions remain at zero.

Now we run the training or learning process, where we run each trial from start to end and find the rewards collected. For each trial, we calculate the Q‐Value for each state‐action combination using an equation called the Bellman equation. Figure 2.32 shows this Bellman equation. We will not go into details on the equation here, but I do provide references at end of the book for it. The idea is that the Bellman equation helps calculate a long‐term reward for that state‐action combination based on the results of that trial. Since this is an iterative learning process, after each trial, the appropriate Q‐Value for that state‐action cell is updated.

Let's consider a simple example to understand this better and more practically. Say you have a problem of traveling from point S (for start) to point E (end). You can travel different paths with middle points represented by M1, M2, etc. By traveling each path, you get a reward represented by a number. Now you have to find an optimal path to travel to maximize your rewards. This problem is represented as a Markov Decision Process (MDP) in Figure 2.33. MDP shows different states and the connections representing state transitions. It also captures the rewards for each state transition.

The MDP shows us two possible paths from state S to E. Keep in mind that if we know this MDP beforehand, this becomes a model‐based RL problem and we can easily find the optimal path with maximum reward. We see that path S‐M2‐E is the most rewarding one. However, let's assume we don't know the MDP and through trial and error we have to find the best path. We will apply Q‐Learning. We will take each path run and calculate the Q‐Value for each state‐action pair using the Bellman equation. Over the iterations, this Q‐Value is updated in the table and you get a table like one in Figure 2.33.

Since this is a very simple problem, we only have three trials to run and calculate Q‐Values for updating the table. From the Q‐Table, we see that for each state we can choose the best action based on a maximum Q‐Value. So, we take the start state S and find the action that gives us the maximum Q‐Value. That turns out to be S‐M2 and then M2‐E gives us the best path. There we have it—S‐M2‐E is our most rewarding path, and we found this in a model‐free way.

In a real‐world problem, you'll have too many variables and state‐action combinations to consider. Imagine playing the game of chess with your friend. From the starting state where all pieces are laid out, there are almost an unimaginable number of moves and combinations of moves you can make. You need to know what your friend is thinking, anticipate her move, and make yours. Unless you are a genius like Sherlock Holmes (albeit fictitious), who can think 10–15 moves ahead of your opponent, it's pretty much impossible to consider all possible combinations.

Q‐Learning, although extremely effective, has major limitations. It works well for a finite state set that we can build in a finite table that will fit in the computer's memory. However, as the problem becomes more complex and the number of states goes from a few hundred to millions, it becomes ineffective. You can easily see that if we don't have a value in the Q‐Table for a particular state, the agent will not know what action to take.

To solve this problem, a new technique has gained popularity. It's called Deep Q Networks (DQN). Let's look at it now.

Deep Q Networks (DQN)

As we saw in the last section, Q‐Learning can handle a finite set of states. For any unseen states, it cannot predict actions to take. With real‐world systems, it is very difficult to plan for the entire state space and feed it to a Q‐Learning algorithm. Hence, we need a way to predict the Q‐Value given the state and action combination. This is done using a neural network called the Deep Q Network.

DQN trains a neural network for different combinations of state and action pairs and tries to build the Q‐Value as a dependent variable of these. DQN can now predict a Q‐Value for states that are not known to it and select the best action.

Another problem is that building a state space is often difficult. Say for a game of chess, modeling the different positions of chess pieces on the 8×8 board can be pretty challenging. A technique that is gaining popularity is feeding the images of the input medium like a chessboard and using this to decode the state. A neural network first decodes the state from an image, which is an array of pixel values. Then this decoded state is used to learn how to predict the Q‐Value.

Figure 2.34 shows how the images are fed to the network and a Q‐Value estimator is developed. The network uses convolution layers to extract features from images. These tell us where the pieces are located on the board. Then, using Supervised Learning, the prediction patterns are learned. The network starts to predict Q‐Values for different state‐action combinations. Based on highest Q‐Value, we can select that action and plan our moves.

This is an active area of research. Companies like Google's DeepMind are actively investigating new techniques for building DQNs that can solve complex problems. One of the most significant achievements of DQN has been the AlphaGo program that defeated the champion of the game Go. Go is supposed to be more complex than chess, with many more combinations, and AlphaGo was able to predict the best action for all of these.

Deep RL is a highly active and growing area. We should expect many more innovations in this space helping us reach significant milestones in fields like medical treatment, robotics, and transportation. Of course, the video game industry has been one of the front runners of using these algorithms inside games.

That's all about Reinforcement Learning for now. We will now return to general ML techniques and specifically focus on Deep Learning.