|
|
| Line 1: |
Line 1: |
| - | <!-- {{Unreleased}} -->
| + | #REDIRECT [[Lab 4: Rule-based Systems]] |
| - | __TOC__
| + | |
| - | | + | |
| - | {{Lab_Due|when=Wednesday, December 4}}
| + | |
| - | | + | |
| - | {{Get_Code|lab=9}}
| + | |
| - | | + | |
| - | == Boosting allows us to combine the strengths of several different, imperfect classifiers ==
| + | |
| - | | + | |
| - | The machine learning classifiers we've been discussing in class are powerful when used correctly, but they are not perfect. Even the best classifiers, under the best of conditions, misclassify some samples. However, due to the nature of each different machine learning algorithm, different classifiers often make different kinds of mistakes. We can take advantage of this variety in errors, using the (reasonable) assumption that ''most'' classifiers will correctly classify each particular point, to construct an even more powerful '''ensemble''' or '''amalgam''' classifier, H, that can correctly classify all or most samples.
| + | |
| - | | + | |
| - | == Adaboost ==
| + | |
| - | | + | |
| - | The boosting algorithm we teach in 6.034 is called Adaboost, short for ''adaptive boosting''. In this lab, you will implement 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.
| + | |
| - | | + | |
| - | == A note about floats, roundoff error, and <tt>Fraction</tt>s ==
| + | |
| - | | + | |
| - | Python sometimes rounds floating point numbers, especially when adding them to dictionaries, which can result in two numbers being off by 0.0000000000000001 (10^-16) or more when they should be equal! For example:
| + | |
| - | | + | |
| - | <pre>
| + | |
| - | >>> 1/3.0
| + | |
| - | 0.3333333333333333
| + | |
| - | >>> 2/3.0
| + | |
| - | 0.6666666666666666
| + | |
| - | >>> 1 - 2/3.0
| + | |
| - | 0.33333333333333337
| + | |
| - | >>> 1/3.0 == 1 - 2/3.0
| + | |
| - | False
| + | |
| - | </pre>
| + | |
| - | | + | |
| - | To avoid dealing with this roundoff error, we recommend using the <tt>Fraction</tt> class. We've already imported it into the lab for you in <tt>utils.py</tt>, and your <tt>lab9.py</tt> file imports it from there. We've also written a function to convert floats or pairs of numbers (numerator and denominator) into fractions:
| + | |
| - | | + | |
| - | * <tt>make_fraction(n)</tt>: Returns a <tt>Fraction</tt> approximately equal to <tt>n</tt>, rounding to the nearest fraction with denominator <= 1000.
| + | |
| - | * <tt>make_fraction(n, d)</tt>: If <tt>n</tt> and <tt>d</tt> are both integers, returns a <tt>Fraction</tt> representing <tt>n/d</tt>. Otherwise, returns a <tt>Fraction</tt> approximately equal to <tt>n/d</tt>, rounding to the nearest fraction with denominator <= 1000.
| + | |
| - | | + | |
| - | You can manipulate and compare <tt>Fraction</tt>s just like any other number type. In fact, you can even make new <tt>Fraction</tt>s out of them! Here are a few examples:
| + | |
| - | | + | |
| - | <pre>
| + | |
| - | >>> frac1 = make_fraction(2,6) # make_fraction can take in two numbers and reduce them to a simple Fraction
| + | |
| - | >>> frac1
| + | |
| - | 1/3
| + | |
| - | >>> frac2 = make_fraction(1,4)
| + | |
| - | >>> frac2
| + | |
| - | 1/4
| + | |
| - | >>> frac2 == 0.25 # Fractions are considered equal to their equivalent floats or ints
| + | |
| - | True
| + | |
| - | >>> frac1 + frac2 # You can add, subtract, multiply, and divide Fractions
| + | |
| - | 7/12
| + | |
| - | >>> frac1 * 5 # You can combine a Fraction and an int to get a new Fraction
| + | |
| - | 5/3
| + | |
| - | >>> make_fraction(frac1, frac2) # You can make a new Fraction out of any two numbers -- including Fractions!
| + | |
| - | 4/3
| + | |
| - | >>> make_fraction(0.9) # make_fraction can also take in a single number (float, int, long, or Fraction)
| + | |
| - | 9/10
| + | |
| - | >>>
| + | |
| - | </pre>
| + | |
| - | | + | |
| - | In this lab, we recommend using <tt>int</tt>s or <tt>Fraction</tt>s, as opposed to floats, for nearly everything numeric. The one exception to this rule is for voting powers, which we recommend representing as floats because they involve logarithms.
| + | |
| - | | + | |
| - | <div style="background-color:#ff0; border:1px solid #fdd; padding:1ex;">
| + | |
| - | '''With all of that having being said, if you think you've implemented a function correctly but you're not passing all of the tests, make sure you're correctly using <tt>Fraction</tt>s instead of raw floats!'''
| + | |
| - | </div>
| + | |
| - | | + | |
| - | == Part 1: Helper functions ==
| + | |
| - | | + | |
| - | We will implement Adaboost piece-by-piece, modularizing the different steps of the algorithm in a similar way to how we taught Adaboost in recitation. As a brief reminder, here is the general control flow of the Adaboost algorithm:
| + | |
| - | # Initialize all training points' weights.
| + | |
| - | # Compute the error rate of each weak classifier.
| + | |
| - | # Pick the "best" weak classifier ''h'', by some definition of "best."
| + | |
| - | # Use the error rate of ''h'' to compute the voting power for ''h''.
| + | |
| - | # Append ''h'', along with its voting power, to the ensemble classifier H.
| + | |
| - | # Update weights in preparation for the next round.
| + | |
| - | # Repeat steps 2-7 until no good classifier remains, we have reached some max number of iterations, or H is "good enough."
| + | |
| - | | + | |
| - | === Initialize weights ===
| + | |
| - | | + | |
| - | First, implement <tt>initialize_weights</tt> to assign every training point a weight equal to 1/N, where N is the number of training points. This function takes in one argument, <tt>training_points</tt>, which is 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.
| + | |
| - | | + | |
| - | <tt>calculate_error_rates</tt> takes as input two dictionaries:
| + | |
| - | | + | |
| - | * <tt>point_to_weight</tt>: maps each training point (represented as a string) to its weight (a number).
| + | |
| - | * <tt>classifier_to_misclassified</tt>: maps each classifier (a string) to a list of the training points (strings) that it misclassifies. For example, this dictionary may contain entries such as <tt>"classifier_0": ["point_A", "point_C"]</tt>, indicating <tt>classifier_0</tt> misclassifies points A and C.
| + | |
| - | | + | |
| - | Implement <tt>calculate_error_rates</tt> 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 need to select the "best" weak classifier. Implement <tt>pick_best_classifier</tt> to return the name of the "best" weak classifier, or raise a <tt>NoGoodClassifiersError</tt> if the "best" weak classifier has an error rate of exactly 1/2. Note that "best" has two possible definitions:
| + | |
| - | * "smallest error rate" (<tt>use_smallest_error=True</tt>), ''or'',
| + | |
| - | * "error rate furthest from 1/2" (<tt>use_smallest_error=False</tt>)
| + | |
| - | | + | |
| - | def pick_best_classifier(classifier_to_error_rate, use_smallest_error=True):
| + | |
| - | | + | |
| - | If two or more weak classifiers have equally good error rates, return the one that comes first alphabetically.
| + | |
| - | | + | |
| - | Hint: Depending on your implementation for this function, you may be interested in using <tt>min</tt> or <tt>max</tt> on a dictionary. Recall that <tt>min</tt> and <tt>max</tt> can take an optional <tt>key</tt> argument, which works similarly to the <tt>key</tt> argument for <tt>sorted</tt>.
| + | |
| - | | + | |
| - | === Calculate voting power ===
| + | |
| - | | + | |
| - | After selecting the best weak classifier, we'll need to compute its voting power. Recall that if ε is the error rate of the weak classifier, then its voting power is:
| + | |
| - | 1/2 * ln((1-ε)/ε)
| + | |
| - | | + | |
| - | Implement <tt>calculate_voting_power</tt> to compute a classifier's voting power, given its error rate 0 ≤ ε ≤ 1. (For your convenience, the constant <tt>INF</tt> and the natural log function <tt>ln</tt> have been defined in <tt>lab9.py</tt>.)
| + | |
| - | | + | |
| - | 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 correctly classifies enough of the training points.
| + | |
| - | | + | |
| - | First, implement a helper function to determine which training points are misclassified by H:
| + | |
| - | def get_overall_misclassifications(H, training_points, classifier_to_misclassified):
| + | |
| - | | + | |
| - | The function <tt>get_overall_misclassifications</tt> takes in three arguments:
| + | |
| - | * <tt>H</tt>: An overall classifier, represented as a list of <tt>(classifier, voting_power)</tt> tuples. (Recall that each classifier is represented as a string.)
| + | |
| - | * <tt>training_points</tt>: A list of all training points. (Recall that each training point is represented as a string.)
| + | |
| - | * <tt>classifier_to_misclassified</tt>: A dictionary mapping each classifier to a list of the training points that it misclassifies.
| + | |
| - | | + | |
| - | The function returns a set containing the training points that H misclassifies.
| + | |
| - | | + | |
| - | Each training point's classification is determined by a weighted vote of the weak classifiers in H. Although we don't know any point's true classification (+1 or -1), we do know whether each point was classified correctly or incorrectly by each weak classifier, and we know that this is a binary classification problem, so there is sufficient information to determine which points were misclassified.
| + | |
| - | | + | |
| - | '''If the vote among the weak classifiers in H is ever a tie, consider the training point to be misclassified.'''
| + | |
| - | | + | |
| - | Now, we can determine whether H is "good enough". The function <tt>is_good_enough</tt> takes in the three arguments from <tt>get_overall_misclassifications</tt>, as well as fourth argument:
| + | |
| - | * <tt>mistake_tolerance</tt>: The maximum number of points that H is allowed to misclassify while still being considered "good enough."
| + | |
| - | | + | |
| - | <tt>is_good_enough</tt> should return <tt>False</tt> if H is misclassifies too many points, otherwise <tt>True</tt> (because H is "good enough").
| + | |
| - | def is_good_enough(H, training_points, classifier_to_misclassified, mistake_tolerance=0):
| + | |
| - | | + | |
| - | === 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:
| + | |
| - | <!--todo: inconsistent tone. Is "you" or "we" implementing this? Is "you" or "Adaboost" performing the algorithm?-->
| + | |
| - | * If the point was classified correctly: <tt>new weight = 1/2 * 1/(1-ε) * (old weight)</tt> <!--todo better formatting-->
| + | |
| - | * If the point was misclassified: <tt>new weight = 1/2 * 1/ε * (old weight)</tt>
| + | |
| - | | + | |
| - | | + | |
| - | The function <tt>update_weights</tt> takes in 3 arguments:
| + | |
| - | * <tt>point_to_weight</tt>: A dictionary mapping each point to its current weight. You are allowed to modify this dictionary, but are not required to.
| + | |
| - | * <tt>misclassified_points</tt>: A list of points misclassified by the current weak classifier.
| + | |
| - | * <tt>error_rate</tt>: The error rate ε of the current weak classifier.
| + | |
| - | | + | |
| - | Implement <tt>update_weights</tt> to return a dictionary mapping each point to its new weight:
| + | |
| - | def update_weights(point_to_weight, misclassified_points, error_rate):
| + | |
| - | | + | |
| - | == Part 2: Adaboost ==
| + | |
| - | | + | |
| - | Using all of the helper functions you've written above, implement the [[#Part_1:_Helper_functions|Adaboost algorithm]]:
| + | |
| - | def adaboost(training_points, classifier_to_misclassified,
| + | |
| - | use_smallest_error=True, mistake_tolerance=0, max_rounds=INF):
| + | |
| - | | + | |
| - | The function <tt>adaboost</tt> takes in five arguments:
| + | |
| - | * <tt>training_points</tt>: A list of all training points.
| + | |
| - | * <tt>classifier_to_misclassified</tt>: A dictionary mapping each classifier to a list of the training points that it misclassifies.
| + | |
| - | * <tt>use_smallest_error</tt>: A boolean value indicating which definition of "best" to use: "smallest error rate" (<tt>True</tt>) or "error rate furthest from 1/2" (<tt>False</tt>).
| + | |
| - | * <tt>mistake_tolerance</tt>: The maximum number of points that H is allowed to misclassify.
| + | |
| - | * <tt>max_rounds</tt>: The maximum number of rounds of boosting to perform before returning H. (This is equivalent to the maximum number of tuples that can be added to H.)
| + | |
| - | | + | |
| - | <tt>adaboost</tt> should return the overall classifier H, represented as a list of <tt>(classifier, voting_power)</tt> tuples.
| + | |
| - | | + | |
| - | Keep in mind that Adaboost has three exit conditions:
| + | |
| - | * If H is "good enough" (see [[#Is_H_good_enough.3F|Is H good enough?]], above)
| + | |
| - | * If it has completed the maximum number of rounds
| + | |
| - | * If the best weak classifier is no good (has an error rate ε = 1/2)
| + | |
| - | | + | |
| - | ;Important Notes
| + | |
| - | :Recall that weight updates are based on the points that were misclassified by the ''current weak classifier'', not by the overall classifier H.
| + | |
| - | | + | |
| - | :If you are failing test cases online but believe your implementation to be correct, please ensure that you are breaking ties correctly in your helper functions.
| + | |
| - | | + | |
| - | {{Survey}}
| + | |
