Lab 9: Adaboost

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
(Update weights: admissible, barely)
(Adaboost: partially complete)
Line 83: Line 83:
Keep in mind that Adaboost has three exit conditions:
Keep in mind that Adaboost has three exit conditions:
-
TODO
+
* If H is "good enough" (see above)
 +
* If it has completed the maximum number of rounds
 +
* If the best classifier available is no good (has an error rate ε = 1/2)
 +
 
 +
Adaboost is initialized by setting all the weight of every point equal to 1/N (where N is the number of training points).  Then, Adaboost repeats the following steps until one of the three exit conditions is satisfied:
 +
# Compute the error rate of each weak classifier.
 +
# Pick the best weak classifier ''h''.  Note that "best" can mean either "smallest error rate" (<tt>use_smallest_error=True</tt>) or "error rate furthest from 1/2" (<tt>use_smallest_error=False</tt>).
 +
# Compute the voting power of the weak classifier ''h'', using its error rate ε.
 +
# TODO...
== Survey ==
== Survey ==

Revision as of 22:59, 20 November 2015

Contents


This lab is due by Friday, December 4 at 10:00pm.

To work on this lab, you will need to get the code, much like you did for the first two labs.

Online tests will be made available by the end of Tuesday, November 24. In the meantime, the local tester provides thorough unit tests for each section of the lab.

Your answers for this lab belong in the main file lab7.py.

Problems: Adaboost

In this lab, you will code the Adaboost algorithm to perform boosting.

Throughout this lab, we will assume that there are exactly two classifications, meaning that every not-misclassified training point is classified correctly.

Helper functions

Initialize weights

First, implement initialize_weights to assign every training point a weight equal to 1/N, where N is the number of training points. This function takes in a list of training points, where each point is represented as a string. The function should return a dictionary mapping points to weights.

def initialize_weights(training_points):

Calculate error rates

Next, we want to calculate the error rate ε of each classifier. The error rate for a classifier h is the sum of the weights of the training points that h misclassifies.

calculate_error_rates takes in two dictionaries:

  • point_to_weight: maps each training point (represented as a string) to its weight (a number).
  • classifier_to_misclassified: maps each classifier to a list of the training points that it misclassifies. For example, this dictionary may contain entries such as "classifier_0": ["point_A", "point_C"].

Implement calculate_error_rates to return a dictionary mapping each weak classifier (a string) to its error rate (a number):

def calculate_error_rates(point_to_weight, classifier_to_misclassified):

Pick the best weak classifier

Once we have calculated the error rate of each weak classifier, we TODO

Calculate voting power

After selecting the best weak classifier, we'll need to compute its voting power. If ε is the error rate of the weak classifier, then its voting power is:

1/2 * ln((1-ε)/ε)

Implement calculate_voting_power to compute a classifier's voting power, given its error rate 0 ≤ ε ≤ 1.

def calculate_voting_power(error_rate):

Hint: What voting power would you give to a weak classifier that classifies all the training points correctly? What if it misclassifies all the training points?

Is H good enough?

One of the three exit conditions for Adaboost is when the overall classifier H is "good enough" -- that is, when H classifies enough training points correctly. The function is_good_enough takes in four arguments:

  • H: An overall classifier, represented as a list of (classifier, voting_power) tuples. (Recall that each classifier is represented as a string.)
  • training_points: A list of all training points. (Recall that each training point is represented as a string.)
  • classifier_to_misclassified: A dictionary mapping each classifier to a list of the training points that it misclassifies.
  • mistake_tolerance: The maximum number of points that H is allowed to misclassify.

is_good_enough should return True if H is good enough (does not misclassify too many points), otherwise False. Each training point's classification is determined by a weighted vote of the weak classifiers in H.

Implement:

def is_good_enough(H, training_points, classifier_to_misclassified, mistake_tolerance=0):

Hint: You don't need to know the the actual classification of a training point. Because there are only two classifications, knowing whether the training point was misclassified should be sufficient.

Update weights

After each round, Adaboost updates weights in preparation for the next round. The updated weight for each point depends on whether the point was classified correctly or incorrectly by the current weak classifier:

  • If the point was classified correctly: new weight = 1/2 * 1/(1-ε) * (old weight)
  • If the point was misclassified: new weight = 1/2 * 1/ε * (old weight)


The function update_weights takes in 3 arguments:

  • point_to_weight: A dictionary mapping each point to its current weight. You are allowed to modify this dictionary, but are not required to.
  • misclassified_points: A list of points misclassified by the current weak classifier.
  • error_rate: The error rate ε of the current weak classifier.

Implement update_weights to return a dictionary mapping each point to its new weight:

def update_weights(point_to_weight, misclassified_points, error_rate):

Adaboost

Using all the helper functions you've written above, implement the Adaboost algorithm.

Keep in mind that Adaboost has three exit conditions:

  • If H is "good enough" (see above)
  • If it has completed the maximum number of rounds
  • If the best classifier available is no good (has an error rate ε = 1/2)

Adaboost is initialized by setting all the weight of every point equal to 1/N (where N is the number of training points). Then, Adaboost repeats the following steps until one of the three exit conditions is satisfied:

  1. Compute the error rate of each weak classifier.
  2. Pick the best weak classifier h. Note that "best" can mean either "smallest error rate" (use_smallest_error=True) or "error rate furthest from 1/2" (use_smallest_error=False).
  3. Compute the voting power of the weak classifier h, using its error rate ε.
  4. TODO...

Survey

Please answer these questions at the bottom of your lab6.py file:

  • NAME: What is your name? (string)
  • COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
  • HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)
  • WHAT_I_FOUND_INTERESTING: Which parts of this lab, if any, did you find interesting? (string)
  • WHAT_I_FOUND_BORING: Which parts of this lab, if any, did you find boring or tedious? (string)
  • (optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)


(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)

When you're done, run the online tester to submit your code.

Personal tools