代写IEOR4525 Fall 2021 Final代写留学生Python语言

IEOR4525 Fall 2021 Final

December 17, 2021

1 Feed-forward Neural Networks (22 pts)

1.1    Architecture and Computation (10 pts)

Consider a network with a single hidden layer. Following information is given to you:

•  data: x ∈ Rdi    and y ∈ Rdo

hidden vector: h(1) Rn

output vector: ˆ(y) Rdo

•  activation function: σ (applied to the hidden layer (i.e.  from input to hidden vector), but NOT to the output layer (i.e. from hidden vector to output) of the network)

Let W (1) , b(1)  denote the weight and bias in the hidden layer, and W (2) , b(2)  denote the weight and bias in the output layer.

1.  (4 pts) Specify the shape of the networks parameters W (1) , b(1) , W (2) , b(2) .

2.  (2 pts) Compute the total number of trainable parameters in this network.

3.  (2 pts) Specify the forward pass computation, including how to compute the hidden vector h(1)  and output vector ˆ(y) of the network.

4.  (2 pts) Compute the computational complexity  (using big-O notation) of the forward pass, for the single data point (x,y).

1.2 Activation Functions (12 pts)

1.  (4 pts) Write out the function expressions for the sigmoid and ReLU activations, respectively.

2.  (6 pts) ”Leaky ReLU” is another kind of activaition that is similar to ReLU, with the expression

for some small value α > 0.  Write out the derivatives of sigmoid, ReLU, and leaky ReLU, respectively.

3.  (2  pts) By comparing the derivatives of ReLU and leaky ReLU, what do you think could be the potential advantage of using leaky ReLU, rather than ReLU, in a neural network model.  Explain why you think so.  (Hint:  think about how the derivative of the activation function influences the whole backpropagation process.)

2 PCA (16 pts)

Consider the following 3 data points in R2 : x1  = (−1, −1), x2  = (0, 0), x3  = (1, 1).

1.  (4 pts) Show the first principal component of the dataset.

2.  (6  pts) Now consider projecting each data point onto the subspace spanned by the first principal component.  What are the coordinates of each data point in this space?  And what is the variance of the projected data?

3.  (6 pts) Now let us see how well 1-d PCA captures the original data.  For each data point, compute the square difference between its representation in terms of the first principal component and its original form.

3 Matrix Completion (16 pts)

Let Ω be the subset of observed indices for a matrix completion problem.   Recall the following matrix completion optimization problems:

Suppose we are given the following partially-observed matrix Suppose we solve

with r = 1. Is there a unique solution? If yes, what is it? If not, explain why.

2. (8 pts) Suppose we are given the same matrix as in the previous question, and we solve (1) with r = 2.
Is there a unique solution? If yes, what is it? If not, explain why.

4 Clustering (16 pts)

1.  (2 pts) Write a high-level description of the repeated steps performed by the k-means algorithm.

2.  (8 pts) Let’s consider the data points 1, 2, 9, 12, 20 ∈ R and the Euclidean distance.  Apply the k-means algorithm with the following values for k and the following initializations. Write down all the steps.

(a)  μ 1  = 1, μ2  = 20, k = 2 (b)  μ 1  = 9, μ2  = 12, k = 2 (c)  μ 1  = 1, μ2  = 2, k = 2

3.  (6 pts) Hierarchical clustering:

With the same data points as before, write down the iterations for the hierarchical clustering algorithm in the following cases:

(a)  Agglomerative hierarchical clustering with single linkage

(b)  Agglomerative hierarchical clustering with complete linkage

5 Tree-based Methods and Boosting (30 pts)

5.1 Decision Tree (5 pts)

Figure 1 shows a dataset with 4 data points. Each data point in the dataset has two inputs features x and y, and a positive (+) or negative (−) label, as depicted in the figure.  Draw a decision tree which correctly classifies each data point in the dataset.  (Note:  you need to draw the diagram of the decision tree in your answer. Please do NOT simply draw the decision boundary in Figure 1.)

Figure 1: Example data set

5.2 Universality of Decision Trees (10 pts)

1.  Show that any binary classifier g : {0, 1}D  → {0, 1} can be implemented as a decision tree classifier. That is, for any classifier g there exists a decision tree classifier T with k nodes n1 , . . . , nk   (each ni with a corresponding threshold ti  ), such that g(x) = T(x) for all x ∈ {0, 1}D .

2. What is the best possible bound one can give on the maximum height of such a decision tree T (from part one)? Give an example of g that achieves this bound.

5.3 Boosting (15 pts)

Figure 2: Sample training data for boosting algorithm

We here study how boosting algorithm behaves on a very simple classification dataset shown in Figure 2. We use decision stump for each weak classifier hi.  Decision stump classifier chooses a constant value c and classifies all points where x > c as one class and other points where x ≤ c as the other class.

1.  (3 pts) What is the initial weight for each data point?

2.  (3 pts) Suppose that the decision stump is trained to minimize the classification error. Write down the decision boundary for the first decision stump. Indicate the positive and negative side of the decision boundary.  (There might be multiple valid decision stumps for this problem.  You only need to write one, and use it for the following questions.)

3.  (3 pts) Write down the point whose weight increases during the first iteration of the boosting process.

4.  (3 pts) Write down the weight that is assigned to each data point at the end of the first iteration of boosting algorithm.

5.  (3 pts) Can boosting algorithm perfectly classify all the data points shown in Figure 2?  If no, briefly explain why. If yes, what is the minimum number of iterations?





热门主题

课程名

mktg2509 csci 2600 38170 lng302 csse3010 phas3226 77938 arch1162 engn4536/engn6536 acx5903 comp151101 phl245 cse12 comp9312 stat3016/6016 phas0038 comp2140 6qqmb312 xjco3011 rest0005 ematm0051 5qqmn219 lubs5062m eee8155 cege0100 eap033 artd1109 mat246 etc3430 ecmm462 mis102 inft6800 ddes9903 comp6521 comp9517 comp3331/9331 comp4337 comp6008 comp9414 bu.231.790.81 man00150m csb352h math1041 eengm4100 isys1002 08 6057cem mktg3504 mthm036 mtrx1701 mth3241 eeee3086 cmp-7038b cmp-7000a ints4010 econ2151 infs5710 fins5516 fin3309 fins5510 gsoe9340 math2007 math2036 soee5010 mark3088 infs3605 elec9714 comp2271 ma214 comp2211 infs3604 600426 sit254 acct3091 bbt405 msin0116 com107/com113 mark5826 sit120 comp9021 eco2101 eeen40700 cs253 ece3114 ecmm447 chns3000 math377 itd102 comp9444 comp(2041|9044) econ0060 econ7230 mgt001371 ecs-323 cs6250 mgdi60012 mdia2012 comm221001 comm5000 ma1008 engl642 econ241 com333 math367 mis201 nbs-7041x meek16104 econ2003 comm1190 mbas902 comp-1027 dpst1091 comp7315 eppd1033 m06 ee3025 msci231 bb113/bbs1063 fc709 comp3425 comp9417 econ42915 cb9101 math1102e chme0017 fc307 mkt60104 5522usst litr1-uc6201.200 ee1102 cosc2803 math39512 omp9727 int2067/int5051 bsb151 mgt253 fc021 babs2202 mis2002s phya21 18-213 cege0012 mdia1002 math38032 mech5125 07 cisc102 mgx3110 cs240 11175 fin3020s eco3420 ictten622 comp9727 cpt111 de114102d mgm320h5s bafi1019 math21112 efim20036 mn-3503 fins5568 110.807 bcpm000028 info6030 bma0092 bcpm0054 math20212 ce335 cs365 cenv6141 ftec5580 math2010 ec3450 comm1170 ecmt1010 csci-ua.0480-003 econ12-200 ib3960 ectb60h3f cs247—assignment tk3163 ics3u ib3j80 comp20008 comp9334 eppd1063 acct2343 cct109 isys1055/3412 math350-real math2014 eec180 stat141b econ2101 msinm014/msing014/msing014b fit2004 comp643 bu1002 cm2030
联系我们
EMail: 99515681@qq.com
QQ: 99515681
留学生作业帮-留学生的知心伴侣!
工作时间:08:00-21:00
python代写
微信客服:codinghelp
站长地图