14. Machine Learning

By examining the plots in Fig. 14.3, it is easy to see which samples are from the dark gray area and which are from the light gray area. For the left sensor, the values of the light gray area are in the range 500–550, while the values of the dark gray area are in the range 410–460. For the right sensor, the ranges are 460–480 and 380–400. For the left sensor, a threshold of 480 would clearly distinguish between light and dark gray, while for the right sensor a threshold of 440 would clearly distinguish between light and dark gray. But how can these optimal values be chosen automatically and how can we reconcile the thresholds of the two sensors?

Let us first focus on the left sensor. We are looking for a discriminant, a value that distinguishes samples from the two colors. Consider the values \( max _{dark}\), the maximum value returned by sampling dark gray, and \( min _{{light}}\), the minimum value returned by sampling light gray. Under the reasonable assumption that \( max _{dark} < min _{light}\), any value x such that \( max _{dark}< x < min _{light}\) can distinguish between the two shades of gray. The midpoint between the two values would seem to offer the most robust discriminant.

From Fig. 14.3 we see that \( max _{dark}\approx 460\) occurs at about 10 s and \( min _{{light}}\approx 500\) occurs at about 60 s, so we choose their average 480 as the discriminant. While this is correct for this particular data set, in general it is not a good idea to use the maximum and minimum values because they could be outliers: extreme values resulting from unusual circumstances, such as a hole in the paper which would incorrectly return a very high value in the dark gray area.

A better solution is to use all the data and the simplest function of all the data is the mean of the values. Let \(\mu _{{dark}}\) denote the mean of the dark gray samples and \(\mu _{{light}}\) the mean of the light gray samples. A good discriminant \(\varDelta \) is the midpoint between the two means:For the data in Fig. 14.3 the means for the left sensor and the discriminant are²:A similar computation gives the discriminant for the right sensor:In order to obtain optimal recognition, we want an algorithm that is able to automatically decide which of the two discriminants is better. This is a preliminary stepping stone to the method described in Sect. 14.2, where a discriminant is computed by combining data from both sensors.

Intuitively, the greater the difference between the means of the light and dark areas:the easier it will be to place a discriminant between the two classes. The difference between the means of the left sensor (88) is a bit greater than the difference between the means of the right sensor (84). This leads us to choose the discriminant (475) computed from the means of the left sensor. However, from the plot in Fig. 14.4 it appears that this might not be the best choice because of the large variation in the samples of the left sensor.

A better discriminant can be obtained if we consider not only the difference of the means but also the spread of the sample values around the mean. This is called the variance of the samples. The variance \(s^2\) of a set of values \(\{x_1,x_2,\ldots ,x_{n-1},x_n\}\) is³:where \(\mu \) is the mean of the values in the set.

The variance computes the average of the distances of each sample from the mean of the samples. The distances are squared because a sample can be greater than or less than the mean, but we want a positive distance that shows how far the sample is from the mean.

The brackets in Fig. 14.4 show the four variances for the sets of samples of the light and dark areas for the left and right sensors. The difference between the left means is somewhat greater than the difference between the right means:but the variances of the right sensor are much smaller than the corresponding variances of the left sensor:The use of the variances enables better classification of the two sets, since a sensor with less variance is more stable and this facilitates classification.

A good discriminant can be obtained by combining information from the means and the variances. The quality of a discriminant \(J_k\), for \(k= left , right \), is given by:To maximize J, the numerator—the distance between the means—should be large, and the denominator—the variances of the samples—should be small.

Table 14.1 displays the computations for the data set from Fig. 14.4. The quality criterion J for the right sensor is much larger than the one for the left sensor. It follows that the midpoint between the means of the right sensor:is a better discriminant than the midpoint of the means of the left sensor that would be chosen by considering only the differences of the means \(|\mu _{{dark}}-\mu _{{light}}|\), which is slightly larger for the left sensor than for the right sensor.

These computations are done by the robot itself, so the choice of the better discriminant and the better sensor is automatic. The details of the computation are given Algorithms 14.1 and 14.2.⁴

There are two classes \(C_1\), \(C_2\) and two sensors. During the learning phase, the robot samples areas of the two gray levels independently and then computes the criterion of quality J. The sampling and computation are done for each sensor, either one after another or simultaneously. After the learning phase, the robot uses midpoint of the means with the best J value for recognition of gray levels.

To understand the advantages of combining samples from two sensors, suppose that we need to classify objects of two colors: electric violet (ev) and cadmium red (cr). Electric violet is composed largely of blue with a bit of red, while cadmium red is composed largely of red with a bit of blue. Two sensors are used: one measures the level of red and the other measures the level of blue. For a set of samples, we can compute their means \(\mu _j^k\) and variances \((s_j^k)^2\), for \(j= ev , cr \), \(k= blue , red \).

The left plot in Fig. 14.5 shows samples of the electric violet objects contained within a dashed ellipse at the upper left and samples of the cadmium red objects contained within a dashed ellipse at the lower right. The centers of the ellipses are the means because the samples are symmetrically distributed with respect to the ellipses. The y-coordinate of \(\mu _{ev}\) is the mean of the samples of the electric violet objects by the blue sensor and its x-coordinate is the mean of the samples of these objects by the red sensor. The means of the sensors when sampling the cadmium red objects are similarly displayed. It is easy to see that the electric violet objects have more blue (they are higher up the y-axis), while the cadmium red objects have more red (they are further out on the x-axis).

From the diagram we see that there is a larger difference between the means for the blue sensor than between the means for the red sensor. At first glance, it appears that using the blue sensor only would give a better discriminant. However, this is not true: the dashed lines show that the red-only discriminant completely distinguishes between electric violet and cadmium red, while the blue-only discriminant falsely classifies some electric violet samples as cadmium red (some samples are below the line) and falsely classifies some cadmium red samples as electric violet (some samples are above the line).

The reason for this unintuitive result is that the blue sensor returns values that are widely spread out (have a large variance), while the red sensor returns values that are narrowly spread out (have a small variance), and we saw in Sect. 14.1 that classification is better if the variance is small. The right plot in Fig. 14.5 shows that by constructing a discriminant from both sensors it is possible to better separate the electric violet objects from the cadmium red objects. The discriminant is still linear (a straight line) but its slope is no longer parallel to one of the axes. This line is computed using the variances as well as the means. The method is called linear discriminant analysis because the discriminant is linear.

Figure 14.5 is an x–y plot of data sampled from two sensors. Each value is plotted at the point whose x-coordinate is the value returned by the red sensor and whose y-coordinate is the value returned by the blue sensor. Similarly, Fig. 14.6 is an x–y plot of the data from Figs. 14.3 and 14.4 that were collected as the robot moved over two gray areas. In those graphs, the sensor values were plotted as function of time, but time has no role in classification except to the link samples that were measured at the same time by the two sensors.

In Fig. 14.6, classification based only on the left sensor corresponds to the vertical dashed line, while classification based only on the right sensor corresponds to the horizontal dashed line. Both the horizontal and vertical separation lines are not optimal. Suppose that classification based on the left sensor (the vertical line) is used and consider a sample for which the left sensor returns 470 and the right sensor returns 460. The sample will be classified as dark gray even though the classification as light gray is better. Intuitively, it is clear that the solid diagonal line in the graph is a far more accurate discriminant than either of the two discriminants based on a single sensor.

How can such a linear discriminant be defined mathematically so that it can be discovered automatically?⁵ The general equation for a line in the plane is \(y=mx+a\), where m is the slope and a is the intersect of the line and the y-axis when \(x=0\). Another equation for a line is:where \(x_1\) is the horizontal axis for the left sensor values, \(x_2\) is the vertical axis for the right sensor values. c is a constant and \(w_1,w_2\) are coefficients of the variables.

It is convenient to represent the coefficients as a column vector:In this representation the vector \(\mathbf {w}\) is normal to the discriminant line and therefore defines its slope, while the constant c enables the discriminant to be any line of that slope, that is, any one of the infinite number of parallel lines with a given slope. Once the slope of \(\mathbf {w}\) is determined, c is obtained by entering a given point (\(x_1\),\(x_2\)) into Eq. 14.2.

Linear discriminant analysis automatically defines the vector \(\mathbf {w}\) and constant c that generates an optimal discriminant line between the data sets of the two classes. The first step is to choose a point on the discriminant line. Through that point there are an infinite number of lines and we have to choose the line whose slope gives the optimal discriminant. Finally, the value c can be computed from the slope and the chosen point. The following subsections describe each of these steps in detail.

How can we choose a point? LDA is based upon the assumption that the values of both classes have the same distribution. Informally, when looking at an x–y plot, both sets of points should have similar size and shape. Although the distributions will almost certainly not be exactly the same (say a Gaussian distribution) because they result from measurements in the real world, since both sensors are subject to the same types of variability (sensor noise, uneven floor surface) it is likely that they will be similar.

If the two distributions are similar, the means of the samples of each sensor will be more-or-less in the same place with respect to the distributions. The average of the means for each sensor will be equidistant from corresponding points in the data sets. The discriminant is chosen to be some line that passes through the point M (Fig. 14.6) whose coordinates are:

Once we have chosen the point M on the discriminant line, the next step is to choose the slope of the line. From Fig. 14.6, we see that there are infinitely many lines through the point M that would distinguish between the two sets of samples. Which is the best line based on the statistical properties of our data?

In Sect. 14.1 we looked for a way to decide between two discriminants, where each discriminant was a line parallel to the y-axis at the midpoint between the means of the values returned by a sensor (Fig. 14.4). The decision was based on the quality criterion \(J_k\) (Eq. 14.1, repeated here for convenience):where \(k=\textit{left},\textit{right}\). The discriminant with the larger value of \(J_k\) was chosen. To maximize \(J_k\), the numerator—the distance between the means—should be large, and the denominator—the variances of the samples—should be small.

Now, we no longer want to compute a quality criterion based on the values returned by each sensor separately, but instead to compute a criterion from all the values returned by both sensors. Figure 14.7 shows an x–y plot of the values of two sensors, where the values of the two classes are represented by red squares and blue circles. Clearly, there is significant overlap along the x or y axes separately and it is impossible to find lines parallel to the axes that can distinguish between the groups. However, if we project the groups of measurements onto the line defined by a vector:the two groups can be distinguished by the separator line defined by Eq. 14.2:where c is defined by a point on the projection line situated between the red and blue points. In analogy with Eq. 14.3, we need to define a quality criterion \(J(\mathbf {w})\), such that larger values of \(J(\mathbf {w})\) give better discriminant lines. Then, we need to find the value of \(\mathbf {w}\) that maximizes \(J(\mathbf {w})\) by differentiating this function, setting the derivative to zero and solving for \(\mathbf {w}\).

The definition of \(J(\mathbf {w})\) is based on the means and variances of the two classes but is too complex for this book. We give without proof that the value of \(\mathbf {w}\) that maximizes \(J(\mathbf {w})\) is:where: are the mean vectors of the two classes and \(\mathbf {S}^{-1}\) is the inverse of the average of the covariance matrices of the two classes⁶: Compared with the single-sensor \(J_k\), the means are two-dimensional vectors because we have one mean for each of the sensors. The sum of variances becomes the covariance matrix, which takes into account both the individual variances of the two sensors and the covariances that express how the two sensors are related.

When the values of M and \(\mathbf {w}\) have been computed, all that remains is to compute the constant c to fully define the discriminant line. This completes the learning phase of the LDA algorithm. In the recognition phase, the robot uses the line defined by \(\mathbf {w}\) and c for classifying new samples.

The computation is formalized in Algorithms 14.3 and 14.4, where we want to distinguish between two classes \(C_1, C_2\) using two sensors. Compare this algorithm with Algorithm 14.1: the two sets of samples \(\mathbf {X_1},\mathbf {X_2}\) and the means \(\varvec{\mu _1},\mathbf {\mu _2}\) and variances \(\mathbf {s_1},\mathbf {s_2}\) are vectors with two elements, one element for each of the sensors.

Figure 14.8 is a plot of the samples from two ground sensors measured as a robot moves over two very similar gray areas, one that is \(83.6\%\) black and the other \(85\%\) black. The levels are so close that the human eye cannot distinguish between them. Can the linear discriminant computed by Algorithm 14.3 do better?

Class \(C_1\) is the light gray area and class \(C_2\) is the dark gray area. The elements of the sets of vectors \(\mathbf {X_1}[n_1],\mathbf {X_2}[n_2]\) are vectors:of samples measured by the left and right sensors, where \(n_1=192\) and \(n_2=205\).

First we compute the means of the data of Fig. 14.8:More samples were taken from the second area (205) than from the first area (192), but that is not important for computing the means. As expected, the means \(\varvec{\mu _1}\) of the samples from the light gray area are slightly higher (more reflected light) than the means \(\varvec{\mu _2}\) of the samples from the dark gray areas. However, the left sensor consistently measures higher values than the right sensor. Figure 14.9 shows the data from Fig. 14.8 with thin dashed lines indicating the means. There are two lines for each area: the horizontal line for the right sensor and the vertical line for the left sensor.

The covariance matrix is composed from the variances of the two individual sensors and their covariance. For \(i=1,2\): For the data from Fig. 14.8, the variances of the samples of the light gray area are:Equation B.4 from Appendix B.4 is used to compute the covariance. Since covariance is symmetric, the value need be computed only once.Putting the results together and performing a similar computation for \(X_2\) gives the covariance matrices:The next step is to compute the mean of the covariance matrices:and to find its inverse⁷:We can now use Eq. 14.4 to compute \(\mathbf {w}\):The vector \(\mathbf {w}\) gives the direction of the projection line which is perpendicular to discriminant line. We now use Eq. 14.2, repeated here:to compute the constant c, assuming we know the coordinate \((x_1,x_2)\) of some point. But we specified that the midpoint between the means must be on the discriminant line. Its coordinates are:Therefore:and the equation of the discriminant line is:The discriminant line is shown as a solid line in Fig. 14.9. Given a new sample (a, b), compare the value of \(0.28a + 0.17b\) to 162: If it is larger, the sample is classified as belonging to class \(C_1\) and if it is is smaller, the sample is classified as belong to class \(C_2\).

If we compare the linear discriminant found above with the two simple discriminants based upon the means of a single sensor, we see a clear improvement. Because of the overlap between the classes in a single direction, the simple discriminant for the right sensor correctly classifies only \(84.1\%\) of the samples, while the simple discriminant for the left sensor is somewhat better, classifying \(93.7\%\) of samples correctly. The linear discriminant found using LDA is better, correctly classifying \(97.5\%\) of the samples.

It might be surprising that there are discriminant lines that can correctly classify all of the samples! One such discriminant is shown by the thick dashed line in Fig. 14.9. Why didn’t LDA find this discriminant? LDA assumes both classes have a similar distribution (spread of values) around the mean and the LDA discriminant is optimal under this assumption. For our data, some points in the second class are far from the mean and thus the distributions of the two classes are slightly different. It is hard to say if these samples are outliers, perhaps caused by problem when printing the gray areas on paper. In that case, it is certainly possible that subsequent sampling of the two areas would result in distributions that are similar to each other, leading to the correct classification by the LDA discriminant.

Activities for LDA are collected in this section.

Consider a robot exploring difficult terrain. It is important that the robot identify steep slopes so it won’t fall over, but it is difficult to specify in advance all dangerous situations since these depend on characteristics such as the geometry of the ground and its properties (wet/dry, sand/mud). Instead, we wish to train the robot to adapt its behavior in different environments.

To simplify the problem, assume that the robot can move just forwards and backwards, and that it has accelerometers on two axes relative to the body of the robot: one measures acceleration forwards and backwards, and the other measures acceleration upwards and downwards. A robot that is stationary on a level surface will measure zero acceleration forwards and backwards, and an downwards acceleration of 9.8 m/sec\(^{2}\) due to gravity. Gravitational acceleration is relatively strong compared with the acceleration of a slow-moving robot, so the relative values of the accelerometer along the two axes will give a good indication of its attitude.

Figure 14.13 shows a robot moving forwards on a slope. The values returned by both accelerometers are similar, \( acc _1\approx acc _2\), so we can infer that the robot is on a slope. If \( acc _2\gg acc _1\), we would infer that the robot is on level ground because the up/down accelerometer measures the full force of gravity while the front/back accelerometer measures only the very small acceleration of the moving robot. The task is to distinguish between a safe position of the robot and one in which the slope starts to become too steep so that the robot is in danger of falling.

Figure 14.14 shows data acquired during a training session as the robot moves down a slope. When the operator of the training session determines that the robot is stable (class \(C_1\)), she initiates a measurement indicated by a red \(\times \); when she determines that the robot is in a dangerous situation (class \(C_2\)), she initiates a measurement indicated by a black triangle. The challenge is to find a way of distinguishing samples of the two classes.

The dashed lines in the figure show the means for the two data sets. It is clear that they do not help us classify the data because of the large overlap between the two sets of samples. Furthermore, LDA is not appropriate because there is no similarity in the distributions: samples when the robot is stable appear in many parts of the plot, while samples from dangerous situations are concentrated in a small area around their mean.

A perceptron is an artificial neuron with a specific structure (Fig. 14.15). It has a summation unit with inputs \(\{x_1,\ldots ,x_n\}\) and each input \(x_i\) is multiplied by a factor \(w_i\) before summation. An additional input \(x_0\) has the constant value 1 for setting a bias independent of the inputs. The output of the perceptron is obtained by applying a function f to the result of the addition.

When used as a classifier, the inputs to the perceptron are the values returned by the sensors for a sample to be classified and the output will be one of two values that indicate the class to which the sample is assigned. Usually, the output function f is just the sign of the weighted sum:where one class corresponds to \(+1\) and the other to \(-1\).

The data are normalized so that all inputs are in the same range, usually \(-1\le x_i\le +1\). The data in Fig. 14.14 can be normalized by dividing each value by 30.

Given a set of input values \(\{x_0=1,x_1,\ldots ,x_n\}\) of a sample, the object of a training session is to find a set of weights \(\{w_0,w_1,\ldots ,w_n\}\) so that the output will be the value \(\pm 1\) that assigns the sample to the correct class.

If the sample is close to the border between two classes, the weighted sum will be close to zero. Therefore, a perceptron is also a linear classifier: to distinguish between outputs of \(\pm 1\), the discriminant dividing the two classes is defined by the set of weights giving an output of zero:orThe presentation of LDA for a two-dimensional problem (\(n=2\)) led to Eq. 14.2, which is the same as Eq. 14.6 when \(c=-w_0\). The difference between the two approaches is in the way the weights are obtained: in LDA statistics are used while for perceptrons they result from an iterative learning process.

The iterative search for values of the weights \(\{w_0,w_1,\ldots ,w_n\}\) starts by setting them to a small value such as 0.1. During the learning phase, a set of samples is presented to the perceptron, together with the expected output (the class) for each element of the set. The set of samples must be constructed randomly and include elements from all the classes; furthermore, the elements from a single class must also be chosen randomly. This is to prevent the learning algorithm from generating a discriminant that is optimal in one specific situation, and to ensure that the process converges rapidly to an overall optimal discriminant, rather than spending too much time optimizing for specific cases.

The adjustment of the weights is computed as follows:This is essentially the Hebbian rule for ANNs (Sect. 13.​5.​2). \(w_i(t)\) and \(w_i(t+1)\) are the i’th weights before and after the correction, \(\eta \) defines the learning rate, \(x_i\) is the normalized input, and y is the desired output. Since the sign function is applied to the sum of the weighted inputs, y is 1 or \(-1\), except on the rare occasions where the sum is exactly zero.

Equation 14.7 corrects the weights by adding or subtracting a value that is proportional to the input, where the coefficient of proportionality is the learning rate. A small value for the learning rate means that the corrections to the weights will be in small increments, while a high learning rate will cause the corrections to the weights to be in larger increments. Once learning is completed, the weights are used to classify subsequent samples.

Algorithms 14.5 and 14.6 are a formal description of classification by perceptrons. The constant N is the size of the set of samples for the learning phase, while n is the number of sensor values returned for each sample.

When should the learning phase be terminated? One could specify an arbitrary value, for example: terminate the learning phase when \(98\%\) of the samples are classified correctly. However, it may not be possible to achieve this level. A better method is to terminate the learning phase when the magnitudes of the corrections to the weights become small.

We return to the robot that is learning to avoid dangerous slopes and apply the learning algorithm to the data in Fig. 14.14. The perceptron has three inputs: \(x_0\) which always set to 1, \(x_1\) for the data from the front/back accelerometer, and \(x_2\) for the data from the up/down accelerometer. The data is normalized by dividing each sample by 30 so that values will be between 0 and 1. We specify that an output of 1 corresponds to class \(C_1\) (stable) and an output of \(-1\) corresponds to class \(C_2\) (dangerous).

Select a random sample from the input data, for example, a sample in class \(C_1\) whose sensor values are \(x_{1}=14\) and \(x_{2}=18\). The normalized input is \(x_{1}=14/30=0.47\) and \(x_{2}=18/30=0.6\). The output of the perceptron with initial weights 0.1 is:This output is correct so the weights need not be corrected. Now choose a random sample in class \(C_2\) whose sensor values are \(x_{1}=17\) and \(x_{2}=15\). The normalized input is \(x_{1}=17/30=0.57\) and \(x_{2}=15/30=0.5\). The output of the perceptron is:This output is not correct: the sample is from class \(C_2\) which corresponds to \(-1\). The weights are now adjusted using Eq. 14.7 with a learning rate \(\eta = 0.1\):These will be the new weights for the next iteration. If we continue for 2000 iterations, the weights evolve as shown in Fig. 14.16. At the end of the learning process, the weights are:

These weights can now be used by the recognition phase of the classification Algorithm 14.6. The discriminant line built by the perceptron (Eq. 14.6) is:The coordinates of this line are the normalized values, but they can be transformed back into the raw values obtained from the accelerometers. The line is shown in Fig. 14.17 and considering the large overlap of the classes, it does a reasonably good job of distinguishing between them.

The performance of a perceptron is determined by the number of iterations and the learning rate. Figure 14.16 shows that there is a strong variation in the weights at the beginning, but the weights stabilize as the number of iterations increases. Thus it is relatively simple to monitor the weights and terminate the computation when the weights stabilize.

This evolution of the weights depends strongly on the learning rate. Increasing the learning rate speeds the variation at the beginning, but strong corrections are not beneficial when the weights begin to stabilize. From Fig. 14.16, it is clear that even at the end of the run, there are significant variations in the weights which oscillate around the optimal value. This suggests that we reduce the learning rate to reduce the oscillations, but doing so will slow down the convergence to the optimal weights at the beginning of the learning phase.

The solution is to use a variable learning rate that is not constant. It should start out large to encourage rapid convergence to the optimal values, and then become smaller to reduce oscillations. For example, we can start with the learning rate of 0.1 and then decrease it continually using the equation:Figure 14.18 shows the evolution of the weights when this variable learning rate is used. The exponential decrease of \(\eta \) is also plotted in the figure. A comparison of Figs. 14.16 and 14.18 clearly shows the superiority of the variable learning rate and this improvement is obtained with very little additional computation.