=== p1 === Introduction to Artificial Intelligence Chapter 19 Learning from Examples Wei-Ta Chu (朱威達) 1 === p2 === • An agent is learning if it improves its performance on future tasks after making observations about the world. • From a collection of input–output pairs, learn a function that predicts the output for new inputs. • Why would we want an agent to learn? • (1) the designers cannot anticipate all possible situations • (2) the designers cannot anticipate all changes over time • (3) sometimes human programmers have no idea how to program a solution themselves Introduction 2 === p3 === • The function h is a hypothesis. Learning is a search through the space of possible hypotheses for one that will perform well, even on new examples beyond the training set. • To measure the accuracy of a hypothesis we give it a test set of examples that are distinct from the training set. Supervised Learning 3 === p4 === • When the output y is one of a finite set of values, the learning problem is called classification. When y is a number, the learning problem is called regression. • Fitting a function of a single variable to some data points. Supervised Learning 4 === p5 === • Figure 18.1(b) shows a high-degree polynomial that is also consistent with the same data. This illustrates a fundamental problem in inductive learning: how do we choose from among multiple consistent hypotheses? One answer is to prefer the simplest hypothesis consistent with the data. This principle is called Ockham’s razor. • Figure 18.1(c) shows a second data set. There is no consistent straight line for this data set; in fact, it requires a degree-6 polynomial for an exact fit. A straight line that is not consistent with any of the data points, but might generalize fairly well for unseen values of x, is also shown in (c). Supervised Learning 5 === p6 === • In general, there is a tradeoff between complex hypotheses that fit the training data well and simpler hypotheses that may generalize better. In Figure 18.1(d) we expand the hypothesis space H to allow polynomials over both x and sin(x), and find that the data in (c) can be fitted exactly by a simple function of the form ax + b + c sin(x). This shows the importance of the choice of hypothesis space. Supervised Learning 6 === p7 === • Supervised learning can be done by choosing the hypothesis h* that is most probable given the data: By Bayes’ rule this is equivalent to Then we can say that the prior probability P(h) is high for a degree-1 or -2 polynomial, lower for a degree-7 polynomial. Supervised Learning 7 === p8 === • There is a tradeoff between the expressiveness of a hypothesis space and the complexity of finding a good hypothesis within that space. • Fitting a straight line to data is an easy computation; fitting high- degree polynomials is somewhat harder. • Most work on learning has focused on simple representations. Supervised Learning 8 === p9 === • We will build a decision tree to decide whether to wait for a table at a restaurant. The aim here is to learn a definition for the goal predicate WillWait. Learning Decision Trees 9 === p10 === Learning Decision Trees 10 [IMAGE-ONLY] === p11 === • An example for a Boolean decision tree consists of an (x, y) pair, where x is a vector of values for the input attributes, and y is a single Boolean output value. A training set of 12 examples is shown in Figure 18.3. The positive examples are the ones in which the goal WillWait is true (x1, x3, . . .); the negative examples are the ones in which it is false (x2, x5, . . .). Learning Decision Trees 11 === p12 === • We want a tree that is consistent with the examples and is as small as possible. • Always test the most important attribute first. By “most important attribute,” we mean the one that makes the most difference to the classification of an example. • Figure 18.4(a) shows that Type is a poor attribute, because it leaves us with four possible outcomes, each of which has the same number of positive as negative examples. Learning Decision Trees 12 === p13 === • In (b), we see that Patrons is a fairly important attribute, because if the value is None or Some, then we are left with example sets for which we can answer definitively (No and Yes, respectively). If the value is Full, we are left with a mixed set of examples. • In general, after the first attribute test splits up the examples, each outcome is a new decision tree learning problem in itself, with fewer examples and one less attribute. Learning Decision Trees 13 === p14 === Learning Decision Trees 14 [IMAGE-ONLY] === p15 === Learning Decision Trees 15 [IMAGE-ONLY] === p16 === • Choosing attribute tests • Entropy is a measure of the uncertainty of a random variable; acquisition of information corresponds to a reduction in entropy. A random variable with only one value—a coin that always comes up heads—has no uncertainty and thus its entropy is defined as zero; thus, we gain no information by observing its value. • A flip of a fair coin is equally likely to come up heads or tails, 0 or 1, and we will soon show that this counts as “1 bit” of entropy. The roll of a fair four-sided die has 2 bits of entropy, because it takes two bits to describe one of four equally probable choices. Learning Decision Trees 16 === p17 === • Choosing attribute tests • The entropy of a random variable V with values vk, each with probability P(vk), is defined as Learning Decision Trees 17 === p18 === Learning Decision Trees 18 • Choosing attribute tests • The entropy of a Boolean random variable that is true with probability q: • If a training set contains p positive examples and n negative examples, then the entropy of the goal attribute on the whole set is • The restaurant training set in Figure 18.3 has p = n = 6, so the corresponding entropy is B(0.5) or exactly 1 bit. A test on a single attribute A might give us only part of this 1 bit. We can measure exactly how much by looking at the entropy remaining after the attribute test. === p19 === • Choosing attribute tests • An attribute A with d distinct values divides the training set E into subsets E1, . . . , Ed. Each subset Ek has pk positive examples and nk negative examples, so if we go along that branch, we will need an additional B(pk/(pk + nk)) bits of information to answer the question. A randomly chosen example from the training set has the kth value for the attribute with probability (pk + nk)/(p + n), so the expected entropy remaining after testing attribute A is Learning Decision Trees 19 === p20 === • Choosing attribute tests • The information gain from the attribute test on A is the expected reduction in entropy: Learning Decision Trees 20 === p21 === • In many areas of industry and commerce, decision trees are usually the first method tried when a classification method is to be extracted from a data set. One important property of decision trees is that it is possible for a human to understand the reason for the output of the learning algorithm. This is a property not shared by some other representations, such as neural networks. Learning Decision Trees 29 === p22 === • We want to learn a hypothesis that fits the future data best. To make that precise we need to define “future data” and “best.” We make the stationarity assumption: that there is a probability distribution over examples that remains stationary over time. • Each example data point (before we see it) is a random variable Ej whose observed value ej = (xj, yj) is sampled from that distribution, and is independent of the previous examples: and each example has an identical prior probability distribution: Evaluating and Choosing the Best Hypothesis 30 === p23 === • Examples that satisfy these assumptions are called independent and identically distributed or i.i.d.. • The next step is to define “best fit.” We define the error rate of a hypothesis as the proportion of mistakes it makes—the proportion of times that for an (x, y) example. A hypothesis h has a low error rate on the training set does not mean that it will generalize well. • Randomly split the available data into a training set from which the learning algorithm produces h and a test set on which the accuracy of h is evaluated. Evaluating and Choosing the Best Hypothesis 31 === p24 === • k-fold cross-validation: First we split the data into k equal subsets. We then perform k rounds of learning; on each round 1/k of the data is held out as a test set and the remaining examples are used as training data. The average test set score of the k rounds should then be a better estimate than a single score. • The extreme is k = n, also known as leave-one-out cross-validation or LOOCV. Evaluating and Choosing the Best Hypothesis 32 === p25 === • Users frequently invalidate their results by inadvertently peeking at the test data. A learning algorithm has various “knobs” (旋鈕) that can be twiddled to tune its behavior. The researcher generates hypotheses for various different settings of the knobs, measures their error rates on the test set, and reports the error rate of the best hypothesis. Alas, peeking has occurred! • The reason is that the hypothesis was selected on the basis of its test set error rate, so information about the test set has leaked into the learning algorithm. Evaluating and Choosing the Best Hypothesis 33 === p26 === • Peeking is a consequence of using test-set performance to both choose a hypothesis and evaluate it. The way to avoid this is to really hold the test set out—lock it away until you are completely done with learning. • If the test set is locked away, but you still want to measure performance on unseen data as a way of selecting a good hypothesis, then divide the available data (without the test set) into a training set and a validation set. Evaluating and Choosing the Best Hypothesis 34 === p27 === • Model selection: Complexity versus goodness of fit • In the polynomial fitting problem, choosing the degree of the polynomial is an instance of the problem of model selection. • Think of the task of finding the best hypothesis as two tasks: model selection defines the hypothesis space and then optimization finds the best hypothesis within that space. • Usually we start with the smallest, simplest models (which probably underfit the data), and iterate, considering more complex models at each step, until the models start to overfit. Evaluating and Choosing the Best Hypothesis 35 === p28 === • Model selection: Complexity versus goodness of fit Evaluating and Choosing the Best Hypothesis 36 === p29 === • From error rates to loss • In machine learning it is traditional to express utilities by means of a loss function. • The loss function is defined as the amount of utility lost by predicting when the correct answer is : This is the most general formulation of the loss function. Often a simplified version is used, . Evaluating and Choosing the Best Hypothesis 37 === p30 === • From error rates to loss • Two functions that implement that idea are the absolute value of the difference (called the L1 loss), and the square of the difference (called the L2 loss). • We can also use the L0/1 loss function, which has a loss of 1 for an incorrect answer and is appropriate for discrete-valued outputs: Evaluating and Choosing the Best Hypothesis 38 === p31 === • From error rates to loss • The learning agent can theoretically maximize its expected utility by choosing the hypothesis that minimizes expected loss over all input– output pairs it will see. • It is meaningless to talk about this expectation without defining a prior probability distribution, P(X, Y) over examples. Let be the set of all possible input–output examples. Then the expected generalization loss for a hypothesis h (with respect to loss function L) is Evaluating and Choosing the Best Hypothesis 39 === p32 === • From error rates to loss • The best hypothesis, h*, is the one with the minimum expected generalization loss: • Because P(x, y) is not known, the learning agent can only estimate generalization loss with empirical loss on a set of examples, E: Evaluating and Choosing the Best Hypothesis 40 === p33 === • Regularization • Search for a hypothesis that directly minimizes the weighted sum of empirical loss and the complexity of the hypothesis, which we will call the total cost: We select the value of λ that gives us the best validation set score. • This process of explicitly penalizing complex hypotheses is called regularization. Evaluating and Choosing the Best Hypothesis 41 === p34 === • Univariate linear regression • A univariate linear function (a straight line) with input x and output y has the form , where w0 and w1 are real-valued coefficients (weights) to be learned. • We’ll define w to be the vector [w0, w1], and define • The task of finding the hw that best fits these data is called linear regression. Regression and Classification with Linear Models 42 === p35 === • Univariate linear regression Regression and Classification with Linear Models 43 === p36 === Regression and Classification with Linear Models 44 • Univariate linear regression • To fit a line to the data, it is traditional to use the squared loss function, L2, summed over all the training examples: === p37 === Regression and Classification with Linear Models 45 • Univariate linear regression • Many forms of learning involve adjusting weights to minimize a loss. Consider the weight space—the space defined by all possible settings of the weights. • For univariate linear regression, the weight space defined by w0 and w1 is two-dimensional, so we can graph the loss as a function of w0 and w1 in a 3D plot. === p38 === Regression and Classification with Linear Models 46 • Univariate linear regression • To go beyond linear models, we will need to face the fact that the equations defining minimum loss will often have no closed-form solution. • Such problems can be addressed by a hill-climbing algorithm that follows the gradient of the function to be optimized. === p39 === Regression and Classification with Linear Models 47 • Univariate linear regression • The parameter α, which we called the step size in Section 4.2, is usually called the learning rate when we are trying to minimize loss in a learning problem. It can be a fixed constant, or it can decay over time as the learning process proceeds. === p40 === Regression and Classification with Linear Models 48 • Univariate linear regression === p41 === Regression and Classification with Linear Models 49 • Univariate linear regression • For N training examples, we want to minimize the sum of the individual losses for each example. The derivative of a sum is the sum of the derivatives, so we have: These updates constitute the batch gradient descent learning rule for univariate linear regression. === p42 === Regression and Classification with Linear Models 50 • Univariate linear regression • Stochastic gradient descent (SGD): It randomly selects a small number of training examples at each time step, and updates according to Equation (18.5). • SGD is widely applied to models other than linear regression, in particular neural networks. === p43 === Regression and Classification with Linear Models 51 • Multivariate linear regression • We can easily extend to multivariate linear regression problems, in which each example xj is an n-element vector. • Then h is simply the dot product of the weights and the input vector === p44 === Regression and Classification with Linear Models 52 • Multivariate linear regression • The best vector of weights, w*, minimizes squared-error loss over the examples: • Gradient descent will reach the (unique) minimum of the loss function; the update equation for each weight wi is === p45 === Regression and Classification with Linear Models 53 • Multivariate linear regression • It is common to use regularization on multivariate linear functions to avoid overfitting. Recall that with regularization we minimize the total cost of a hypothesis, counting both the empirical loss and the complexity of the hypothesis: === p46 === Regression and Classification with Linear Models 54 • Multivariate linear regression • For linear functions the complexity can be specified as a function of the weights. • With q = 1 we have L1 regularization, which minimizes the sum of the absolute values; with q = 2, L2 regularization minimizes the sum of squares. Which regularization function should you pick? That depends on the specific problem, but L1 regularization has an important advantage: it tends to produce a sparse model. === p47 === Regression and Classification with Linear Models 55 • Linear classifiers with a hard threshold • Linear functions can be used to do classification as well as regression. • Given these training data, the task of classification is to learn a hypothesis h that will take new (x1 , x2 ) points and return either 0 for earthquakes or 1 for explosions. === p48 === Regression and Classification with Linear Models 56 • Linear classifiers with a hard threshold === p49 === Regression and Classification with Linear Models 57 • Linear classifiers with a hard threshold • A decision boundary is a line (or a surface, in higher dimensions) that separates the two classes. In Figure 18.15(a), the decision boundary is a straight line. A linear decision boundary is called a linear separator and data that admit such a separator are called linearly separable. === p50 === Regression and Classification with Linear Models 58 • Linear classifiers with a hard threshold • Alternatively, we can think of h as the result of passing the linear function through a threshold function: • There is a simple weight update rule that converges to a solution provided the data are linearly separable. For a single example (x, y), we have which is essentially identical to the update rule for linear regression. This rule is called the perceptron learning rule. (18.7) === p51 === Regression and Classification with Linear Models 59 • Linear classifiers with a hard threshold === p52 === Regression and Classification with Linear Models 60 • The perceptron rule may not converge to a stable solution for fixed learning rate. === p53 === Regression and Classification with Linear Models 61 • Linear classification with logistic regression • The linear classifier always announces a completely confident prediction of 1 or 0, even for examples that are very close to the boundary; in many situations, we really need more gradated predictions. • All of these issues can be resolved to a large extent by softening the threshold function— approximating the hard threshold with a continuous, differentiable function. • The logistic function === p54 === Regression and Classification with Linear Models 62 • Linear classification with logistic regression === p55 === Regression and Classification with Linear Models 63 • Linear classification with logistic regression • With the logistic function replacing the threshold function, we now have An example of such a hypothesis for the two-input earthquake/explosion problem is shown in Figure 18.17(c). • The process of fitting the weights of this model to minimize loss on a data set is called logistic regression. === p56 === Regression and Classification with Linear Models 64 • Linear classification with logistic regression === p57 === Regression and Classification with Linear Models 65 • Linear classification with logistic regression Proportion correct Proportion correct Proportion correct === p58 === • Linear regression use the training data to estimate a fixed set of parameters w. That defines our hypothesis hw(x), and at that point we can throw away the training data, because they are all summarized by w. A learning model that summarizes data with a set of parameters of fixed size is called a parametric model. • A nonparametric model is one that cannot be characterized by a bounded set of parameters. For example, suppose that each hypothesis we generate simply retains within itself all of the training examples and uses all of them to predict the next example. Nonparametric Models 66 === p59 === • Nearest neighbor models • Given a query xq , find the k examples that are nearest to xq. This is called k-nearest neighbors lookup. We’ll use the notation NN(k, xq) to denote the set of k nearest neighbors. • To do classification, first find NN(k, xq), then take the plurality vote of the neighbors (which is the majority vote in the case of binary classification). To avoid ties, k is always chosen to be an odd number. • To do regression, we can take the mean or median of the k neighbors, or we can solve a linear regression problem on the neighbors. Nonparametric Models 67 === p60 === • Nearest neighbor models Nonparametric Models 68 === p61 === • Nearest neighbor models • Nonparametric methods are still subject to underfitting and overfitting, just like parametric methods. In this case 1-nearest neighbors is overfitting; it reacts too much to the black outlier in the upper right and the white outlier at (5.4, 3.7). The 5-nearest-neighbors decision boundary is good; higher k would underfit. As usual, cross-validation can be used to select the best value of k. Nonparametric Models 69 === p62 === • Nearest neighbor models • The word “nearest” implies a distance metric. How do we measure the distance from a query point xq to an example point xj? Typically, distances are measured with a Minkowski distance or Lp norm, defined as With p = 2 this is Euclidean distance and with p = 1 it is Manhattan distance. • With Boolean attribute values, the number of attributes on which the two points differ is called the Hamming distance. Nonparametric Models 70 === p63 === • Nearest neighbor models • The total distance will be affected by a change in scale in any dimension. If we change dimension i from centimeters to miles while keeping the other dimensions the same, we’ll get different nearest neighbors. • It is common to apply normalization to the measurements in each dimension. One simple approach is to compute the mean μi and standard deviation σi of the values in each dimension, and rescale them so that xj,i becomes (xj,i − μi)/σi. • A more complex metric known as the Mahalanobis distance takes into account the covariance between dimensions. Nonparametric Models 71 === p64 === • Curse of dimensionality • In low-dimensional spaces with plenty of data, nearest neighbors works very well. However, it’s not in high-dimensional spaces! • Consider k-nearest-neighbors on a data set of N points uniformly distributed throughout the interior of an n-dimensional unit hypercube. The k-neighborhood of a point is the smallest hypercube that contains the k-nearest neighbors. Let be the average side length of a neighborhood. Then the volume of the neighborhood (which contains k points) is and the volume of the full cube (which contains N points) is 1. So, on average, . Taking nth roots of both sides we get . Nonparametric Models 72 === p65 === • Curse of dimensionality • To be concrete, let k=10 and N=1,000,000. In two dimensions (n=2; a unit square), the average neighborhood has , a small fraction of the unit square, and in 3 dimensions is just 2% of the edge length of the unit cube. But by the time we get to 17 dimensions, is half the edge length of the unit hypercube, and in 200 dimensions it is 94%. This problem has been called the curse of dimensionality. Nonparametric Models 73 === p66 === • Finding nearest neighbors with k-d trees • A balanced binary tree over data with an arbitrary number of dimensions is called a k-d tree, for k-dimensional tree. • To construct a k-d tree, we start with a set of examples and at the root node we split them along the ith dimension by testing whether xi ≤ m. We chose the value m to be the median of the examples along the ith dimension; thus half the examples will be in the left branch of the tree and half in the right. We then recursively make a tree for the left and right sets of examples, stopping when there are fewer than two examples left. Nonparametric Models 74 === p67 === • Finding nearest neighbors with k-d trees • k-d trees are appropriate only when there are many more examples than dimensions, preferably at least 2n examples. Thus, k-d trees work well with up to 10 dimensions with thousands of examples or up to 20 dimensions with millions of examples. If we don’t have enough examples, lookup is no faster than a linear scan of the entire data set. Nonparametric Models 75 === p68 === • Locality-sensitive hashing • Hash tables have the potential to provide even faster lookup than binary trees. Hash codes randomly distribute values among the bins, but we want to have near points grouped together in the same bin; we want a locality- sensitive hash (LSH). Nonparametric Models 76 === p69 === • Locality-sensitive hashing • Approximate near-neighbors problem: Given a data set of example points and a query point xq, find, with high probability, an example point (or points) that is near xq. • To be more precise, we require that if there is a point xj that is within a radius r of xq, then with high probability the algorithm will find a point xj′ that is within distance cr of xq. If there is no point within radius r then the algorithm is allowed to report failure. The values of c and “high probability” are parameters of the algorithm. Nonparametric Models 77 === p70 === • Locality-sensitive hashing • We need a hash function g(x) that has the property that, for any two points xj and xj′ , the probability that they have the same hash code is small if their distance is more than cr, and is high if their distance is less than r. Nonparametric Models 78 === p71 === • Locality-sensitive hashing • The trick of LSH is to create multiple random projections and combine them. A random projection is just a random subset of the bit-string representation. We choose different random projections and create hash tables, . We then enter all the examples into each hash table. Then when given a query point xq, we fetch the set of points in bin gk(q) for each k, and union these sets together into a set of candidate points, C. Nonparametric Models 79 === p72 === • Locality-sensitive hashing • Then we compute the actual distance to xq for each of the points in C and return the k closest points. With high probability, each of the points that are near to xq will show up in at least one of the bins. • With large real-world problems, such as finding the near neighbors in a data set of 13 million Web images using 512 dimensions, locality- sensitive hashing needs to examine only a few thousand images out of 13 million to find nearest neighbors; a thousand-fold speedup over exhaustive or k-d tree approaches. Nonparametric Models 80 === p73 === • Nonparametric regression Nonparametric Models 81 === p74 === • Nonparametric regression • (a) When noise is low, this trivial method is actually not too bad. But when the data are noisy, the resulting function is spiky, and does not generalize well. • (b) k-nearest-neighbors regression (Figure 18.28(b)) improves on connect-the-dots. Instead of using just the two examples to the left and right of a query point xq, we use the k nearest neighbors (here 3). we have the k-nearest-neighbors average: h(x) is the mean value of the k points, Nonparametric Models 82 === p75 === • Nonparametric regression • (c) k-nearest-neighbors linear regression (Figure 18.28(c)) finds the best line through the k examples. This does a better job of capturing trends at the outliers, but is still discontinuous. • (d) Locally weighted regression (Figure 18.28(d)) gives us the advantages of nearest neighbors, without the discontinuities. The idea of locally weighted regression is that at each query point xq, the examples that are close to xq are weighted heavily, and the examples that are farther away are weighted less heavily or not at all. The decrease in weight over distance is always gradual, not sudden. Nonparametric Models 83 === p76 === • Nonparametric regression • We decide how much to weight each example with a function known as a kernel. A kernel function looks like a bump; in Figure 18.29 we see the specific kernel used to generate Figure 18.28(d). Nonparametric Models 84 === p77 === • Nonparametric regression Nonparametric Models 85 === p78 === • In the early 2000s, the support vector machines (SVM) model class was the most popular approach for “off-the-shelf” supervised learning, for when you don’t have any specialized prior knowledge about a domain. • SVMs construct a maximum margin separator • SVMs create a linear separating hyperplane, but they have the ability to embed the data into a higher-dimensional space, using the so-called kernel trick. • SVMs are a nonparametric method Support Vector Machines 86 === p79 === Support Vector Machines 87 [IMAGE-ONLY] === p80 === • In Figure 18.30(a), we have a binary classification problem with three candidate decision boundaries, each a linear separator. Each of them is consistent with all the examples, so from the point of view of 0/1 loss, each would be equally good. • Logistic regression would find some separating line; the exact location of the line depends on all the example points. The key insight of SVMs is that some examples are more important than others, and that paying attention to them can lead to better generalization. Support Vector Machines 88 === p81 === • SVMs address this issue: Instead of minimizing expected empirical loss on the training data, SVMs attempt to minimize expected generalization loss. • We call this separator, shown in Figure 18.30(b) the maximum margin separator. The margin is the width of the area bounded by dashed lines in the figure—twice the distance from the separator to the nearest example point. • How do we find this separator? Support Vector Machines 89 === p82 === • The separator is defined as the set of points {x : w · x + b=0}. We could search the space of w and b with gradient descent to find the parameters that maximize the margin while correctly classifying all the examples. • We don’t directly solve it, but turns it into the dual representation. The optimal solution is found by solving Support Vector Machines 90 (18.13) === p83 === • This is a quadratic programming optimization problem. • Once we have found the vector α we can get back to w with the equation , or we can stay in the dual representation. • There are three important properties of Equation (18.13). First, the expression is convex; it has a single global maximum that can be found efficiently. Support Vector Machines 91 === p84 === • Second, the data enter the expression only in the form of dot products of pairs of points. This second property is also true of the equation for the separator itself; once the optimal αj have been calculated, it is • A final important property is that the weights αj associated with each data point are zero except for the support vectors—the points closest to the separator. Because there are usually many fewer support vectors than examples, SVMs gain some of the advantages of parametric models. Support Vector Machines 92 === p85 === • What if the examples are not linearly separable? Support Vector Machines 93 === p86 === • Clearly, there is no linear separator for Fig. 18.31(a). Now, suppose we map each input vector x to a new vector of feature values, F(x). In particular, let us use the three features • Figure 18.31(b) shows the data in the new, three-dimensional space defined by the three features; the data are linearly separable in this space! If data are mapped into a space of sufficiently high dimension, then they will almost always be linearly separable. In general (with some special cases excepted) if we have N data points then they will always be separable in spaces of N − 1 dimensions or more. Support Vector Machines 94 === p87 === • Now, we would not usually expect to find a linear separator in the input space x, but we can find linear separators in the high-dimensional feature space F(x) simply by replacing xj·xk in Equation(18.13) with F(xj)·F(xk). • It turns out that F(xj)·F(xk) can often be computed without first computing F for each point. In our three-dimensional feature space defined by Equation (18.15), a little bit of algebra shows that (That’s why the √2 is in f3.) Support Vector Machines 95 === p88 === • The expression (xj·xk)2 is called a kernel function, and is usually written as K(xj,xk). The kernel function can be applied to pairs of input data to evaluate dot products in some corresponding feature space. So, we can find linear separators in the higher-dimensional feature space F(x) simply by replacing xj·xk in Equation (18.13) with a kernel function K(xj,xk). Thus, we can learn in the higher-dimensional space, but we compute only kernel functions rather than the full list of features for each data point. • Other kernel functions: Support Vector Machines 96 === p89 === • Kernel trick: Plugging these kernels into Equation (18.13), optimal linear separators can be found efficiently in feature spaces with billions of (or, in some cases, infinitely many) dimensions. The resulting linear separators, when mapped back to the original input space, can correspond to arbitrarily wiggly, nonlinear decision boundaries between the positive and negative examples. Support Vector Machines 97 === p90 === • The idea of ensemble learning methods is to select a collection, or ensemble, of hypotheses from the hypothesis space and combine their predictions. • For example, during cross-validation we might generate twenty different decision trees, and have them vote on the best classification for a new example. • Consider an ensemble of K = 5 hypotheses and suppose that we combine their predictions using simple majority voting. For the ensemble to misclassify a new example, at least three of the five hypotheses have to misclassify it. The hope is that this is much less likely than a misclassification by a single hypothesis. Ensemble Learning 98 === p91 === • Another way to think about the ensemble idea is as a generic way of enlarging the hypothesis space. That is, think of the ensemble itself as a hypothesis and the new hypothesis space as the set of all possible ensembles constructable from hypotheses in the original space. Ensemble Learning 99 === p92 === • We generate K distinct training sets by sampling with replacement from the original training set. We then run our machine learning algorithm on a training set to get hypothesis. Repeat this process K times, getting K different hypotheses. For classification, taking the majority vote. For regression, the final output is the average • Bagging tends to reduce variance and is a standard approach when there is limited data or when the base model is seen to be overfitting. Ensemble Learning -- Bagging 100 === p93 === • The random forest model is a form of decision tree bagging in which we take extra steps to make the ensemble of K trees more diverse. • The key idea is to randomly vary the attribute choices (rather than the training examples). At each split point in constructing the tree, we select a random sampling of attributes, and then compute which of those gives the highest information gain. • Further improvement: for each selected attribute, we randomly sample several candidate values from a uniform distribution. Then we select the value that has the highest information gain. Ensemble Learning – Random forests 101 === p94 === • All the hyperparameters can be trained by cross-validation: the number of trees K, the number of examples used by each tree N, the number of attributes used at each split point, and the number of random split points tried. • Random forests are resistant to overfitting. • Breiman (2001) gives a mathematical proof that (in almost all cases) as you add more trees to the forest, the error converges. Ensemble Learning – Random forests 102 === p95 === • The technique of stacked generalization (or stacking for short) combines multiple base models from different model classes trained on the same data. • For example, given the restaurant data set, the first row is: x1=Yes, No, No, Yes, Some, $$$, No, Yes, French, 0-10; y1=Yes • We use the training set to train three separate base models – SVM, logistic regression, and a decision tree. • In the next step we take the validation data set and augment each row with the predictions made from the three base models, giving us rows look like this x2=Yes, No, No, Yes, Full, $, No, No, Thai, 30-60, Yes, No, No; y2=No Ensemble Learning – Stacking 103 === p96 === • We use this validation set to train a new ensemble model, let’s say a logistic regression model. The ensemble model can use the predictions and the original data as it sees fit. • This method is called “stacking” because it can be thought of as a layer of base models with an ensemble model stacked above it, operating on the output of the base models. • Stacking reduces bias, and usually leads to performance that is better than any of the individual base models. Ensemble Learning – Stacking 104 === p97 === • The most widely used ensemble method is called boosting. • To understand the idea, we need first to explain the idea of a weighted training set. In such a training set, each example has an associated weight wj ≥ 0. The higher the weight of an example, the higher is the importance attached to it during the learning of a hypothesis. Ensemble Learning -- Boosting 105 === p98 === • Boosting starts with wj = 1 for all the examples (i.e., a normal training set). From this set, it generates the first hypothesis, h1. This hypothesis will classify some of the training examples correctly and some incorrectly. We would like the next hypothesis to do better on the misclassified examples, so we increase their weights while decreasing the weights of the correctly classified examples. • From this new weighted training set, we generate hypothesis h2. The process continues in this way until we have generated K hypotheses. The final ensemble hypothesis is a weighted-majority combination of all the K hypotheses, each weighted according to how well it performed on the training set. Ensemble Learning -- Boosting 106 === p99 === Ensemble Learning -- Boosting 107 [IMAGE-ONLY] === p100 === • ADABOOST has a very important property: if the input learning algorithm L is a weak learning algorithm—which means that L always returns a hypothesis with accuracy on the training set that is slightly better than random guessing —then ADABOOST will return a hypothesis that classifies the training data perfectly for large enough K. Ensemble Learning -- Boosting 108 === p101 === • Let us see how well boosting does on the restaurant data. We will choose as our original hypothesis space the class of decision stumps, which are decision trees with just one test, at the root. • The lower curve in Figure 18.35(a) shows that unboosted decision stumps are not very effective for this data set, reaching a prediction performance of only 81% on 100 training examples. When boosting is applied (with K = 5), the performance is better, reaching 93% after 100 examples. Ensemble Learning -- Boosting 109 === p102 === Ensemble Learning -- Boosting 110 Training accuracy Test accuracy === p103 === • So far, everything we have done in this chapter has relied on the assumption that the data are i.i.d. (independent and identically distributed). On the one hand, that is a sensible assumption: if the future bears no resemblance to the past, then how can we predict anything? On the other hand, it is too strong an assumption: it is rare that our inputs have captured all the information that would make the future truly independent of the past. Ensemble Learning – Online learning 111 === p104 === • What to do when the data are not i.i.d.? • In this case, it matters when we make a prediction, so we will adopt the perspective called online learning: an agent receives an input xj from nature, predicts the corresponding yj, and then is told the correct answer. Then the process repeats with xj+1, and so on. Ensemble Learning – Online learning 112 === p105 === • Let us consider the situation where our input consists of predictions from a panel of experts. For example, each day a set of K pundits (權威者) predicts whether the stock market will go up or down, and our task is to pool those predictions and make our own. One way to do this is to keep track of how well each expert performs, and choose to believe them in proportion to their past performance. This is called the randomized weighted majority algorithm. Ensemble Learning – Online learning 113 === p106 === • We can describe it more formally: Ensemble Learning – Online learning 114 === p107 === • Online learning is helpful when the data may be changing rapidly over time. It is also useful for applications that involve a large collection of data that is constantly growing, even if changes are gradual. • For most learning algorithms based on minimizing loss, there is an online version based on minimizing regret. Ensemble Learning – Online learning 115 === p108 === • Problem formulation • You need to specify a loss function, which should be correlated with your true goals. • When you have decomposed your problems into parts, you may find that there are multiple components that can be handled by old-fashioned software engineering, not machine learning. • Part of problem formulation is deciding whether you are dealing with supervised, unsupervised, or reinforcement learning. Developing Machine Learning Systems 116 === p109 === • Data collection, assessment, and management • Every machine learning project needs data. • Freely available datasets, crowdsourcing • When data are limited, data augmentation can help. • Unbalanced classes problem – undersample or over-sample. You can use a weighted loss function that gives a larger penalty to missing a fraudulent case. • You should carefully consider outliers in your data. An outlier is a data point that is far from other points. Developing Machine Learning Systems 117 === p110 === • Feature engineering • You may preprocess the data to make it easier to digest. • Quantization, normalization, one-hot encoding • You can also introduce new attributes based on your domain knowledge • Exploratory data analysis and visualization • Cluster your data and then visualize a prototype data point at the center of each cluster. • It is also helpful to detect outliers that are far from the prototypes Developing Machine Learning Systems 118 === p111 === • Exploratory data analysis and visualization • t-distributed stochastic neighbor embedding (t-SNE) Developing Machine Learning Systems 119 === p112 === • Model selection and training • There is no guaranteed way to pick the best model class, but there are some rough guidelines. • Random forests are good when there are a lot of categorical features and you believe that many of them may be irrelevant. • Nonparameteric methods are good when you have a lot of data and no prior knowledge. • Logistic regression does well when the data are linearly separable. Developing Machine Learning Systems 120 === p113 === • Model selection and training • SVMs are good to try when the data set is not too large. • Problems dealing with pattern recognition are most often approached with deep neural networks. • Choosing hyperparameters can be done with a combination of experience and search. As you run more experiments you will get ideas for different models to try. Developing Machine Learning Systems 121 === p114 === • Trust, interpretability, and explainability • Doing well on metric is a necessary but not sufficient condition for your to trust your model. • Interpretability: We say a machine learning model is interpretable if you can inspect the actual model and understand why it got a particular answer for a given input. • Explainability: An explainable model is one that can help you understand “why was this output produced for this input?” Developing Machine Learning Systems 122