[Solved] CSC411 Assignment 1-Nearest Neighbours and the Curse of Dimensionality
5.0
1 customer review
Digital download
Digital download
$25.00
- Availability
- In stock
- Checkout
- One item
Need a hand?
Message us on WhatsApp for payment or download support.
- Nearest Neighbours and the Curse of Dimensionality. In this question, you will verify the claim from lecture that most points in a high-dimensional space are far away from each other, and also approximately the same distance. There is a very neat proof of this fact which uses the properties of expectation and variance. If its been a long time since youve studied these, you may wish to review the Tutorial 1 slides[1], or the Metacademy resources4.
- First, consider two independent univariate random variables X and Y sampled uniformly from the unit interval [0,1]. Determine the expectation and variance of the random variable Z, defined as the squared distance Z = (X Y )2. You are allowed to evaluate integrals numerically (e.g. using integrate.quad or scipy.integrate.dblquad), but you should explain what integral(s) you are evaluating, and why.
- Now suppose we sample two points independently from a unit cube in d Observe that each coordinate is sampled independently from [0,1], i.e. we can view this as sampling random variables X1,,Xd,Y1,,Yd independently from [0,1]. The squared Euclidean distance can be written as R = Z1 ++Zd, where Zi = (Xi Yi)2. Using the properties of expectation and variance, determine E[R] and Var[R]. You may give your answer in terms of the dimension d, and E[Z] and Var[Z] (the answers from part (a)).
- [for your own benefit, not to be handed in] Based on your answer to part (b), compare the mean and standard deviation of R to the maximum possible squared Euclidean distance (i.e. the distance between opposite corners of the cube). Why does this support the claim that in high dimensions, most points are far away, and approximately the same distance?
- Decision Trees. This question is taken from a project by Lisa Zhang and Michael Guerzhoy.
- Write a function load_data which loads the data, preprocesses it using a vectorizer
- Write a function select_model which trains the decision tree classifier using at least 5 different values of max_depth, as well as two different split criteria (information gain and Gini coefficient), evaluates the performance of each one on the validation set, and prints the resulting accuracies of each model. You should use DecisionTreeClassifier, but you should write the validation code yourself. Include the output of this function in your solution PDF (pdf).
- Now lets stick with the hyperparameters which achieved the highest validation accuracy. Extract and visualize the first two layers of the tree. Your visualization may look something like what is shown below, but it does not have to be an image: it is perfectly fine to display text. It may be hand-drawn. Include your visualization in your solution PDF (pdf).
- Write a function compute_information_gain which computes the information gain of a split on the training data. That is, compute I(Y,xi), where Y is the random variable signifying whether the headline is real or fake, and xi is the keyword chosen for the split.