首页 >
> 详细

COMS 4771 SP21 HW2

Due: Mon Feb 22, 2021 at 11:59pm

This homework is to be done alone. No late homeworks are allowed. To receive credit, a typesetted

copy of the homework pdf must be uploaded to Gradescope by the due date. You must show

your work to receive full credit. Discussing possible solutions for homework questions is encouraged

on piazza and with your peers, but you must write your own individual solutions and not share

your written work/code. You must cite all resources (including online material, books, articles, help

taken from specific individuals, etc.) you used to complete your work.

1 Cost-sensitive classification

Suppose you have a binary classification problem with input space X = R and output space

Y = {0, 1}, where it is c times as bad to commit a “false positive” as it is to commit a “false negative”

(for some real number c ≥ 1). To make this concrete, let’s say that if your classifier predicts 1

but the correct label is 0, you incur a penalty of $c; if your classifier predicts 0 but the correct label

is 1, you incur a penalty of $1. (And you incur no penalty if your classifier predicts the correct label.)

Assume the distribution you care about has a class prior with π0 = 2/3 and π1 = 1/3, and the

class conditional are Gaussians with densities N(0, 1) for class 0, and N(2, 1/4) for class 1. Let f∗: R → {0, 1} be the classifier with the smallest expected penalty.

(i) Assume 1 ≤ c ≤ 14. Specify precisely the subset of R in which the classifier f

∗ predicts 1.

(E.g., [0, 5c] ∪ [6c, +∞).)

(ii) Now instead assume c ≥ 15. Again, specify precisely the region in which the classifier f

∗

predicts 1.

2 Making data linearly separable by feature space mapping

Consider the infinite dimensional feature space mapping

Φσ : R → R.

(It may be helpful to sketch the function f(α) := max{0, 1 − |α|} for understanding the mapping

and answering the questions below)

(i) Show that for any n distinct points x1, . . . , xn, there exists σ > 0 such that the mapping Φσ

can linearly separate any binary labeling of the n points.

1

(ii) Show that one can efficiently compute the dot products in this feature space, by giving an

analytical formula for Φσ(x) · Φσ(x0) for arbitrary points x and x0.

3 Learning DNFs with kernel perceptron

Suppose that we have S = {(x(i), y(i))}ni=1 with x

(i) ∈ {0, 1}d

and y(i) ∈ {−1, 1}. Let ϕ :{0, 1}

d → {0, 1} be a “target function” which “labels” the points. Additionally assume that ϕ is

a DNF formula (i.e. ϕ is a disjunction of conjunctions, or a boolean “or” of a bunch of boolean

“and”s). The fact that it “labels” the points simply means that 1[y

(i) = 1] = ϕ(x(i)).

For example, let ϕ(x) = (x1 ∧ x2) ∨ (x1 ∧ x¯2 ∧ x3) (where xi denotes the ith entry of x),

(i) Give an example target function ϕ (make sure its a DNF formula) and set S such that the data

is not linearly separable.

Part (i) clearly shows that running the perceptron algorithm on S cannot work in general since the

data does not need to be linearly separable. However, we can try to use a feature transformation and

the kernel trick to linearize the data and thus run the kernelized version of the perceptron algorithm

on these datasets.

Consider the feature transformation φ : {0, 1}

d → {0, 1}3d

which maps a vector x to the vector

of all the conjunctions of its entries or of their negations. So for example if d = 2 then φ(x) =1 x1 x2 x¯1 x¯2 x1 ∧ x2 x1 ∧ x¯2 x¯1 ∧ x2 x¯1 ∧ x¯2T

(note that 1 can be viewed as the

empty conjunction, i.e. the conjunction of zero literals).

Let K : {0, 1}

d × {0, 1}

d → R be the kernel function associated with φ (i.e. for a, b ∈ {0, 1}

d:K(a, b) = φ(a) · φ(b)).

(ii) Find a way to compute K(a, b) in O(d) time.

(iii) Show that w∗

linearly separates φ(S) (φ(S) is just a shorthand for {(φ(x

(i)), y(i))}ni=1) and

find a lower bound for the margin γ with which it separates the data. Remember that γ =

min(φ(x(i)),y(i))∈φ(S) yi. Your lower bound should depend on s, the number

of conjunctions in ϕ.

(iv) Find an upper bound on the radius R of the dataset φ(S). Remember that

R = max

(φ(x(i)),y(i))∈φ(S)kφ(x(i))k.2

(v) Use parts (ii), (iii), and (iv) to show that we can run kernel perceptron efficiently on this transformed

space in which our data is linearly separable (show that each iteration takes O(nd)

time only) but that unfortunately the mistake bound is very bad (show that it is O(s2d)).

There are ways to get a better mistake bound in this same kernel space, but the running time then

becomes very bad (exponential). It is open whether there are ways to get both polynomial mistake

bound and running time.

4 Understanding model complexity and overfitting

Here we will empirically study the tradeoff between model complexity and generalizability using

handwritten digits dataset.

Download the datafile digits.mat. This datafile contains 10,000 images (each of size 28x28

pixels = 784 dimensions) of handwritten digits along with the associated labels. Each handwritten

digit belongs to one of the 10 possible categories {0, 1, . . . , 9}. There are two variables in this

datafile: (i) Variable X is a 10,000x784 data matrix, where each row is a sample image of a handwritten

digit. (ii) Variable Y is the 10,000x1 label vector where the i

th entry indicates the label of

the i

th sample image in X.

Special note for those who are not using Matlab: Python users can use scipy to read in the mat file,

R users can use R.matlab package to read in the mat file, Julia users can use JuliaIO/MAT.jl.

Octave users should be able to load the file directly.

To visualize this data (in Matlab): say you want to see the actual handwritten character image of the

77th datasample. You may run the following code (after the data has been loaded):

figure;

imagesc(1-reshape(X(77,:),[28 28])’);

colormap gray;

To see the associated label value:

Y(77)

(i) Build a decision tree classifier for the handwritten digit dataset. In building your decision

tree, you may use any reasonable uncertainty measure to determine the feature and threshold

to split at in each cell. Make sure the depth of the tree is adjustable with hyperparameter K.

You must submit your code to receive full credit.

(ii) Ensure that there is a random split between training and test data. Plot the training error and

test error as a function of K.

(iii) Do the trends change for different random splits of training and test data?

(iv) How do you explain the difference in the behavior of training and testing error as a function

of K?

(v) Based on your analysis, what is a good setting of K if you were deploy your decision tree

classifier to classify handwritten digits?

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28