代写Machine Learning中的SVM和Adaboost算法，并进行对比和性能分析。
Support Vector Machine classifiers
Use the LibSVM package to train a SVM classifier: a simple example of its use is provided in demo libsvm.m. The first 3 bullet items outline the steps followed in SVM.
- Use a Gaussian kernel, and use 10-fold cross-validation to choose the cost and precision parameters (referred to as -c: cost / -g: gamma parameters in LibSVM documentation).
Visualize the cross-validation error (a 2D function) using imagesc.
Once you have picked the best combination of cost and precision evaluate the classifier’s generalization error on the test-set - report the number of misclassified points. - Plot the decision boundaries, by appropriately modifying the code from the previous exercises. Superimpose on your plot also the support vectors, using the code outlined in SVM.m.
If you work is working right, you should be getting results of the following form for the cross-validation error and the decision boundaries:
Adaboost
In Adaboost.m your task is to train an Adaboost classifier with synthetic data. For reference, you are provided with the posterior P(y = 1|x), x {[0, 1] [0, 1]} regularly sampled on the [0, 1] [0, 1] domain, so that you will see how the output of the Adaboost classifier better approximates the posterior at each round.
- Implement the Adaboost algorithm described in class. This involves iterating over the following steps:
- Find the best decision stump at each round.
- Evaluate the weak learner’s weighted error, and estimate t.
- Update the distribution over the training samples.
- Plot as a function of the boosting round. Make sure that E is monotonically decreasing with time (otherwise your code is wrong). Verify that E(y(x) f(x)) provides an upper bound for the number of errors.
- Show the response of your strong learner side-by-side with the posterior. Make sure that they look increasingly similar at larger iterations.
If you code is working right, you should be getting results of the following form for the cross-validation error and the decision boundaries: strong learner round 10 strong learner round 50 strong learner round 100strong learner round 400
Top row: strong learner scores, displayed within [-1, 1] for dierent numbers of boosting rounds.
Bottom row: left: loss function of Adaboost for increasing training rounds; middle: class posterior (groundtruth); right: adaboost-based approximatiot to posterior, at round 400.
Some clarifications
- The form of a decision stump, where d is the the dimension along which the decision is taken, s is 1 if is true and 0 otherwise, is the threshold applied along dimension d and s {-1, 1} is the polarity of the decision stump.
SVM vs. Adaboost
- When searching for the best decision stump you need in principle to consider all possible combinations of d. As discussed in class, for a given dimension d the only values of that you actually need to work with are the values taken on by the training set features along that dimension.
SVM vs. Adaboost BONUS
Compare the performance of the classifier you obtained from the previous part of the exercise with that of Adaboost. Use the same training and test sets for both classifiers. As above, make sure you have reproducible results, by appropriately setting the seed variable in rand,randn+.
Report their average misclassification errors on the training set and on the test set. What do you observe?
Fast weak learner selection BONUS
When picking the best weak learner at each round a substantial speedup can be gained by a clever implementation of the threshold selection. Below some hints are provided, you can try to implement it quickly based on these hints.
Consider that we are searching for the best weak learner that operates with the k th feature dimension, f(k) . Our task is to choose the best threshold for a decision stump of the form.
The naive implementation is to consider all possible thresholds, where N is the training sample size, and for each of those evaluate the associated weighted error.
The complexity of this computation is O(N^2), since for every of the N threshold values we need to perform N summations and multiplications.
Instead of this, a faster algorithm will first sort the N training samples according to their value of k; namely k consider that we have a permutation of the training set such that f[i], respectively. Using these, we then have the following recursion for C(i).
The first and second equations follow from the definition in Eq. 2 and the fact that f have been sorted. The third equation can be verified by substitution. Sorting has O(N log N) complexity, while the recursion can be implemented in O(N) time, so the overall complexity goes down from O(N^2) to O(N log N). In the code provided to you, this idea has been used to accelerate the weak learner selection.
Inspect the code provided to you and reply to the following questions in no more than 100 words (the shorter, the better):
- What is the code in lines 22-26 doing?
- What is the code in lines 28-38 doing?
Note: if you do not understand the code by looking at it, this is perfectly normal. Before “leaking” the solution, the assignment was asking you to write all of this code. Now, since the solution is leaked, we are asking you to spend time to understand what is going on in the provided solution. Running the code and observing the variables is an option to help you with doing this.
But, since this is a bonus exercise, you are expected to “go the extra mile” to get the bonus.