SOLUTION MANUAL
SOLUTION MANUAL
Chapter 1. Introduction Chapter 2. Supervised Learning Chapter 3. Bayesian Decision Theory Chapter 4. Parametric Methods Chapter 5. Multivariate Methods Chapter 6. Dimensionality Reduction Chapter 7. Clustering Chapter 8. Nonparametric Methods Chapter 9. Decision Trees Chapter 10. Linear Discrimination Chapter 11. Multilayer Perceptrons Chapter 12. Deep Learning Chapter 13. Local Models Chapter 14. Kernel Machines Chapter 15. Graphical Models Chapter 16. Hidden Markov Models Chapter 17. Bayesian Estimation Chapter 18. Combining Multiple Learners Chapter 19. Reinforcement Learning Chapter 20. Design and Analysis of Machine Learning Experiments
Introduction to Machine Learning Fourth Edition
Solutions Manual
Ethem Alpaydın The MIT Press
1
Introduction
1. Imagine we have two possibilities: We can scan and email the image, or we can use an optical character reader (OCR) and send the text file. Discuss the advantage and disadvantages of the two approaches in a comparative manner. When would one be preferable over the other? The text file typically is shorter than the image file but a faxed document can also contain diagrams, pictures, etc. After using an OCR, we lose properties such as font, size, etc (unless we also recognize and transmit such information) or the personal touch if it is handwritten text. OCR may not be perfect, and for ambiguous cases, OCR should identify those image blocks and transmit them as they are. A fax machine is cheaper and easier to find than a computer with scanner and OCR software. OCR is good if we have high volume, good quality documents; for documents of few pages with small amount of text, it is better to transmit the image. 2. Let us say we are building an OCR and for each character, we store the bitmap of that character as a template that we match with the read character pixel by pixel. Explain when such a system would fail. Why are barcode readers still used? Such a system allows only one template per character and cannot distinguish characters from multiple fonts, for example. There are standardized fonts such as OCR-A and OCR-B—the fonts we typically see on the packaging of stuff we buy—which are used with OCR software (the characters in these fonts have been slightly changed to minimize the similarities between them). Barcode readers are still used because reading barcodes is still a better (cheaper, more reliable, more avail-
2
1
Introduction
able) technology than reading characters in arbitrary font, size, and styles. 3. Assume we are given the task of building a system to distinguish junk email. What is in a junk email that lets us know that it is junk? How can the computer detect junk through a syntactic analysis? What would we like the computer to do if it detects a junk email—delete it automatically, move it to a different file, or just highlight it on the screen? Typically, text-based spam filters check for the existence/absence of words and symbols. Words such as “opportunity,” ”viagra,” ”dollars,” and characters such as ’$’ and ’!’ increase the probability that the email is spam. These probabilities are learned from a training set of example past emails that the user has previously marked as spam. We see many algorithms for this in later chapters. The spam filters do not work with 100 percent reliability and may make errors in classification. If a junk mail is not filtered, this is not good, but it is not as bad as filtering a good mail as spam. We discuss how we can take into account the relative costs of such false positives and false negatives later on. Therefore, mail messages that the system considers as spam should not be automatically deleted but kept aside so that the user can see them if he/she wants to, especially in the early stages of using the spam filter when the system has not yet been trained sufficiently. Spam filtering is probably one of the best application areas of machine learning where learning systems can adapt to changes in the ways spam messages are generated. 4. Let us say we are given the task of building an automated taxi. Define the constraints. What are the inputs? What is the output? How can we communicate with the passenger? Do we need to communicate with the other automated taxis, that is, do we need a “language”? An automated taxi should be able to pick a passenger and drive him/her to a destination. It should have some positioning system (GPS/GIS) and should have other sensors (cameras) to be able to sense cars, pedestrians, obstacles, etc on the road. The output should be the sequence of actions to reach the destination in the smallest time with minimum inconvenience to the passenger. The automated taxi needs to communicate with the passenger to receive commands and may also need to interact with other automated taxis and possibly with a centralized
3 control to exhange information about road traffic or scheduling, load balancing, etc. 5. In basket analysis, we want to find the dependence between two items X and Y . Given a database of customer transactions, how can we find these dependencies? How would we generalize this to more than two items? This is discussed in section 3.5 of the book. 6. In a daily newspaper, find five sample news reports for each category of politics, sports, and the arts. Go over these reports and find words that are used frequently for each category, which may help you discriminate between different categories. For example, a news report on politics is likely to include words such as “government,” “recession,” “congress,” and so forth, whereas a news report on the arts may include “album,” “canvas,” or “theater.” There are also words such as “goal” that are ambiguous. I have checked the web page for the New York Times of Feb 10th, 2010 and found the following words. For politics: republican, party, senate, vote, administration; for sports: medal, athlete, freestyle, ski, snowboard; for the arts: show, celebrity, debut, vocal, resonance. News categorization systems have a preprocessing stage to handle suffixes, such as votes vs vote, or snowboarding vs snowboard. Note that sports is a metaphor used in politics and many ways of life that involve competition, so the use of few keywords is tricky and one needs to take context into account by employing hundreds/thousands of keywords. In a class of students, it would be interesting to see the overlap of the words students find. 7. If a face image is a 100 × 100 image, written in row-major, this is a 10,000-dimensional vector. If we shift the image one pixel to the right, this will be a very different vector in the 10,000-dimensional space. How can we build face recognizers robust to such distortions? Face recognition systems typically have a preprocessing stage for normalization where the input is centered and possibly resized before recognition. This is generally done by first finding the eyes and then translating the image accordingly. There are also recognizers that do not use the face image as pixels but rather extract structural features from the image, for example, the ratio of the distance between the two
4
1
Introduction
eyes to the size of the whole face. Such features would be invariant to translations and size changes. 8. Take, for example, the word “machine.” Write it ten times. Also ask a friend to write it ten times. Analyzing these twenty images, try to find features, types of strokes, curvatures, loops, how you make the dots, and so on, that discriminate your handwriting from that of your friend’s. I leave this to the reader. One personal comment: Over the years, I have noticed that though many western nations use some version of the roman alphabet, there are noticable distinctions between their writing styles. I notice for example that french and italian handwritings are more cursive, connected, and flowery, whereas german, british and american handwritten characters are stroke-based, formed of separate characters. This may just be my impression and in a class formed of students from different nationalities, this may be an interesting thing to check. 9. In estimating the price of a used car, it makes more sense to estimate the percent depreciation over the original price than to estimate the absolute price. Why? Depreciation is generally measured as some percentage of the original price. Cars having different prices may suffer the same loss in the same amount of time or mileage; for example in Turkey, the general belief is that a car, on the average, loses 10-20 per cent of its value in its first year. 10. Consider your purchases from your local supermarket. What are the typical associations between the products you buy? How do they depend on the season? Try to devise general rules that explain your purchasing behavior. I buy bread regularly irrespective of the season. When I buy beer, I also buy crips. I buy ice cream in summer and I buy more tea in winter than in summer. 11. List all the companies or institutions that have some data about you and what they know about you. Check their policies for data security and privacy. My employer has my personal information. I’m very careful submitting my personal information over the web, and never share any with any
5 site that I do not know. Whenever I share confidential information, I make sure that the communication is secure. 12. What do you think is the difference between a “data engineer” and a “data scientist”‘? The former is closer to implementation and the latter is more focused on theory. Neither one is superior to the other; we need both.
2
Supervised Learning
1. Let us say our hypothesis class is a circle instead of a rectangle. What are the parameters? How can the parameters of a circle hypothesis be calculated in such a case? What if it is an ellipse? Why does it make more sense to use an ellipse instead of a circle? In the case of a circle, the parameters are the center and the radius (see figure 2.1). We then need to find S and G where S is the tightest circle that includes all the positive examples and G is the largest circle that includes all the positive examples and no negative example; any circle between them is a consistent hypothesis. It makes more sense to use an ellipse because the two axes need not have the same scale and an ellipse has two separate parameters for the widths in the two axes rather than a single radius. Actually, price and engine power are positively correlated; the price of a car tends to increase as its engine power increases, and hence it makes more sense to use an oblique ellipse—we will see such models in chapter 5. 2. Imagine our hypothesis is not one rectangle but a union of two (or m > 1) rectangles. What is the advantage of such a hypothesis class? Show that any class can be represented by such a hypothesis class with large enough m. In the case when there is a single rectangle, all the positive instances should form one single group; with two rectangles, for example (see figure 2.2), the positive instances can form two, possibly disjoint clusters in the input space. Note that each rectangle corresponds to a conjunction on the two input attributes, and having multiple rectangles corresponds to a disjunction. Any logical formula can be written
8
Supervised Learning
x2: Engine power
2
C cc
c2
r
c1
x1: Price
Figure 2.1 Hypothesis class is a circle with two parameters, the coordinates of its center and its radius.
x2: Engine power
as a disjunction of conjunctions. In the worst case (m = N), we have a separate rectangle for each positive instance.
h1
C
h2
x1: Price
Figure 2.2
Hypothesis class is a union of two rectangles.
3. In many applications, wrong decisions—namely, false positives and false
11 8. How can we estimate w2 , w1 , w0 for the quadratic model of equation 2.18 ? We derive it just like we did in the previous exercise, but this time we will have three equations in three unknowns: N
E(w1 , w0 |X) =
i2 1 Xh t r − (w2 (xt )2 + w1 xt + w0 ) N i=1
Take derivatives wrt w2 , w1 , w0 , set them equal to 0, and solve for w2 , w1 , w0 . 9. Assume our hypothesis class is the set of lines, and we use a line to separate the positive and negative examples, instead of bounding the positive examples as in a rectangle, leaving the negatives outside (see figure 2.3). Show that the VC dimension of a line is 3.
x2
(2.1)
x1 Figure 2.3
A line separating positive and negative instances.
As we see in figure 2.4, for all possible labeling of three points, there exist a line to separate positive and negative examples. With four points, no matter how we place these four points in two dimensions, there is at least one labeling where we cannot draw a line such that on one side lie all the positives and on the other lie all the negatives. 10. Show that the VC dimension of the triangle hypothesis class is 7 in two dimensions. (Hint: For best separation, it is best to place the seven points equidistant on a circle.)
12
Supervised Learning
x2
x2
2
x1 All possible labelings of three points can be separated using a line.
x1 These four points cannot be separated using a line.
Figure 2.4 A line separating positive and negative instances.
x2
x2
As we can see in figure 2.5, for all possible labeling of seven points, we can draw a triangle to separate the positive and negative examples. We cannot do the same when there are eight points.
x1 These seven points can be separated using a triangle no matter how they are labeled.
x1 These eight points with this labeling cannot be separated using a triangle.
Figure 2.5 A triangle can shatter seven points but not eight.
11. Assume as in exercise 8 that our hypothesis class is the set of lines. Write down an error function that not only minimizes the number of misclassifications but also maximizes the margin. We will need to write an error function that sums margins, that is, distances to the boundary, and not only 0/1 misclassifications, which only checks whether we are on the correct side of the boundary; but we do this only if an instance is on the wrong side of the boundary.