Content from live lectures and self-study videos from weeks 5 - 9 inclusive (but not including Deep Learning)
Streaming Ensemble Methods. Feature Extraction, Dimensionality Reduction, Word Embeddings, SVM, Clustering Algorithms and Evaluation Measures, Anomaly Detection
Was originally scheduled for March 11, will now be March 18-20
The test will either be Crowdmark as a mixture of multiple-choice questions and submitted answers of calculations or derivations.
For multiple-choice questions it is possible for there to be multiple correct answers, if you choose any of the correct answers you will get the points, but selecting any incorrect answers will deduct a point.
Submitted answer questions can be either:
Given the points (purple circles) in the figure below, and the current means (red crosses) for each cluster boundary shown. In the next round of k-means some points will be assigned to different clusters.
Fill in a table with the coordinates, in the form , of the points that would move, and the cluster they move to.
Note: For all calculations use Manhatten distance, for example, , for any pair of points in .
Note: this is example code for your table only, it is not implied how many points you should enter.
| Point (X,Y) | Moves to ... |
| --------- | ---------- |
| $(x,y)$ | $K$ |
| $(x,y)$ | $K$ |
| $(x,y)$ | $K$ |
| $(x,y)$ | $K$ |
Point (X,Y) | Moves to … |
---|---|
Referring to figure below, calculate the inter- and intra-cluster distances and decide on merging clusters.
| $d(X,Y)$ | Single Link | Complete Link |
| --- | --- | --- |
| $d(A,B)$ | ?? | ?? |
| $d(A,C)$ | ?? | ?? |
| $d(B,C)$ | ?? | ?? |
| Merge $X$ and $Y$ | ?? | ?? |
Single Link | Complete Link | |
---|---|---|
6 | 11 | |
5 | 12 | |
4 | 10 | |
Merge and | (B,C) | (B,C) |
You will compare the following pairs of classification or clustering algorithms by drawing datasets that one algorithm (X) can find a perfect separation and another algorithm (Y) cannot. This means that given a labelling for the points (you can draw them as X and O, or squares and circles) algorithm X will define an enclosing shape, or dividing lines, that perfectly group all the points correctly into their classes. For unsupervised clustering algorithms, we can also assume we know the true labels of the data points, even though the algorithm does not.
Case | Algorithm X Finds Perfect Classification/Cluster Separation | Algorithm Y Does Not Find A Perfect Classification/Cluster Separation |
---|---|---|
A | X=DBScan | Y=k-means |
B | X=k-means | Y=DBScan |
C | X=Decision Trees | Y=linear SVM |
In each case you should have two parts to your answer:
Note: For each part, be sure to clearly label the question A.1, A.2, B.1, B.2 etc. All the answers can be written on paper (or tablet) and uploaded as a photo (or saved as a pdf).
Assume that the optimization problem for finding a subspace is as follows. Let be the projection matrix onto the subspace and let be a symmetric matrix.
Solve the optimization problem for finding the projection matrix.
subject to
Note: the answer can be typed in with markdown and latex or written on paper (or tablet) and attached as an image or pdf file.
Even though it is linear, soft-margin SVM is a powerful algorithm because the support vectors are on the optimal hyperplane for dividing the points given the constraints.
True or False?
False. The support vectors are the closest points to the dividing hyperplane, they are not on the hyperplane.`
Gaussian Kernel SVM with Soft Margins
RBF Kernel SVM with Soft Margins
Some detailed description involving which points are support vectors and which and how they would influence the optimization. Full marks for discussing that alpha will be zero for points which are not the support vectors.