CS 461: Machine Learning
Instructor: Kiri Wagstaff

CS 461 Homework 3

Due: Midnight, February 7, 2008

Please your answers to these questions in <yourlastname>-hw3.txt (or PDF).

Part 1: Support Vector Machine Regression (5 points)

  1. What is the meaning of the epsilon parameter when performing SVM regression? (5 points)

Part 2: Neural Networks (40 points)

  1. Given the following perceptron:

    calculate the output y given this input: x = [ 2 -1 3 ]. (8 points)

  2. Why do perceptron learning algorithms make use of a "learning rate" parameter? (5 points)

  3. Draw a perceptron that operates on data having five features. You may draw your perceptron in ASCII text, or upload a file called <yourlastname>-hw3-perceptron.pdf (or .jpg or .gif). (8 points)

    How many weights must the perceptron learn? (2 points)

  4. Given the expression for the error rate E of a multilayer perceptron, for a single item whose true output is y and the MLP's output is y':

    E = 1/2 (y - y')2

    Derive the partial derivative dE/dy' that is used during backpropagation to update the weights w. (8 points)

  5. Consider the XOR problem, where the data set has two features and the label for a data item is positive if only one feature is 1 and negative otherwise. Why can't a single perceptron learn to classify data based on the XOR concept? (5 points)

    Why does a multilayer perceptron succeed at this problem? (4 points)

Part 3: Bayesian Methods (55 points)

  1. Assume that the probability of there being rain on any given day is 0.1, and that the (independent) probability of getting in a car accident is 0.05. What is the probability of there being a day that is both rainy and you get in a car accident? (5 points)

  2. From vehicle accident records, assume that we've determined that the probability of it being a rainy day, given that a car accident was observed, is 0.4. Using Bayes' Rule and the prior probabilities in question 1, what is the conditional probability of getting into a car accident today, given that you already know today is rainy? (8 points)

    Why is this probability different from the one you got for question 1? (2 points)

  3. I want to model the factors affecting whether a research paper will be rejected by a journal (not published). Draw a Bayesian network to capture the following information. Put your network in a file called <yourlastname>-hw3-bayesian.pdf (or .jpg or .gif). (5 points)

    The random variables, which should become nodes in your network, are shown in quotation marks.

    • The probability of getting a "grouchy reviewer" who doesn't like anything they read is 0.1.
    • The probability of there being a "technical flaw" in the paper is 0.2.
    • If there is a "grouchy reviewer" and a "technical flaw", the probability of rejection is 0.9.
    • If there is no "grouchy reviewer" and a "technical flaw", the probability of rejection is still high: 0.7.
    • If there is a "grouchy reviewer" and no "technical flaw", the probability of rejection is 0.4 (the grouchy reviewer may be overriden by a nicer reviewer).
    • If there is neither a "grouchy reviewer" nor a "technical flaw", the probability of rejection is 0.2 (there are many other reasons a paper may be rejected).

    Annotate each node with the appropriate probabilities, as in Figure 3.3 in the Alpaydin book. (5 points)

    What is the probability that the paper is rejected, given that there is a technical flaw? (10 points)

  4. Given this data set describing students, in which the class label is the person's major:

    Height Gender Wears glasses? Class (major)
    shortmaleyesComputer Science
    tallmalenoComputer Science
    tallmaleyesComputer Science
    mediumfemaleyesComputer Science
    mediumfemalenoPhysics
    tallmalenoPhysics
    tallfemaleyesPhysics
    mediummaleyesElectrical Engineering
    tallmalenoElectrical Engineering
    tallmaleyesElectrical Engineering

    Use the Naive Bayes classifier to predict this person's major (show your work): (15 points)

    Height Gender Wears glasses? Class (major)
    mediummaleno?

  5. What is an association rule? Give an example. (5 points)

What to turn in

Upload this file to CSNS under "Homework 3":

  1. <yourlastname>-hw3.txt (or <yourlastname>-hw3.pdf if you prefer to submit in PDF format)
  2. <yourlastname>-hw3-perceptron.pdf (or .gif or .jpg)
  3. <yourlastname>-hw3-bayesian.pdf (or .gif or .jpg)

Extra credit

If you wish to tackle some extra credit, you may do so here. You can earn up to 10 points to be applied to any of your homework assignments (but not to exceed 100 on any assignment). To receive these points, you must get at least a 70% on the main part of Homework 3, so finish the regular assignment before moving on to this part.

  1. Given your Bayesian network in problem 3 of part 3, what is the probability of getting a grouchy reviewer, given that the paper was rejected? (5 points)

  2. Given the data set in problem 4 of part 3, and assuming a Naive Bayes classifier, create two new students. Each student should be classified by Naive Bayes into one of the two majors not selected for the test student in problem 4. Your students may not be duplicates of any students in the training set. Show your work (as in problem 4) demonstrating how each student is assigned to a major. (5 points)

What to turn in

Upload this file to CSNS under "Homework 3: Extra Credit":

  1. <yourlastname>-hw3-extra.txt (or <yourlastname>-hw3-extra.pdf if you prefer to submit in PDF format)