首页
网站开发
桌面应用
管理软件
微信开发
App开发
嵌入式软件
工具软件
数据采集与分析
其他
首页
>
> 详细
COMP9417代做、Python程序设计代写
项目预算:
开发周期:
发布时间:
要求地区:
COMP9417 - Machine Learning
Homework 2: Numerical Implementation of Logistic
Regression
Introduction In homework 1, we considered Gradient Descent (and coordinate descent) for minimizing
a regularized loss function. In this homework, we consider an alternative method known as Newton’s
algorithm. We will first run Newton’s algorithm on a simple toy problem, and then implement it from
scratch on a real data classification problem. We also look at the dual version of logistic regression.
Points Allocation There are a total of 30 marks.
• Question 1 a): 1 mark
• Question 1 b): 2 mark
• Question 2 a): 3 marks
• Question 2 b): 3 marks
• Question 2 c): 2 marks
• Question 2 d): 4 mark
• Question 2 e): 4 marks
• Question 2 f): 2 marks
• Question 2 g): 4 mark
• Question 2 h): 3 marks
• Question 2 i): 2 marks
What to Submit
• A single PDF file which contains solutions to each question. For each question, provide your solution
in the form of text and requested plots. For some questions you will be requested to provide screen
shots of code used to generate your answer — only include these when they are explicitly asked for.
• .py file(s) containing all code you used for the project, which should be provided in a separate .zip
file. This code must match the code provided in the report.
• You may be deducted points for not following these instructions.
• You may be deducted points for poorly presented/formatted work. Please be neat and make your
solutions clear. Start each question on a new page if necessary.
1
• You cannot submit a Jupyter notebook; this will receive a mark of zero. This does not stop you from
developing your code in a notebook and then copying it into a .py file though, or using a tool such as
nbconvert or similar.
• We will set up a Moodle forum for questions about this homework. Please read the existing questions
before posting new questions. Please do some basic research online before posting questions. Please
only post clarification questions. Any questions deemed to be fishing for answers will be ignored
and/or deleted.
• Please check Moodle announcements for updates to this spec. It is your responsibility to check for
announcements about the spec.
• Please complete your homework on your own, do not discuss your solution with other people in the
course. General discussion of the problems is fine, but you must write out your own solution and
acknowledge if you discussed any of the problems in your submission (including their name(s) and
zID).
• As usual, we monitor all online forums such as Chegg, StackExchange, etc. Posting homework questions on these site is equivalent to plagiarism and will result in a case of academic misconduct.
When and Where to Submit
• Due date: Week 7, Monday March 25th, 2024 by 5pm. Please note that the forum will not be actively
monitored on weekends.
• Late submissions will incur a penalty of 5% per day from the maximum achievable grade. For example, if you achieve a grade of 80/100 but you submitted 3 days late, then your final grade will be
80 − 3 × 5 = 65. Submissions that are more than 5 days late will receive a mark of zero.
• Submission must be done through Moodle, no exceptions.
Page 2
Question 1. Introduction to Newton’s Method
Note: throughout this question do not use any existing implementations of any of the algorithms
discussed unless explicitly asked to in the question. Using existing implementations can result in
a grade of zero for the entire question. In homework 1 we studied gradient descent (GD), which is
usually referred to as a first order method. Here, we study an alternative algorithm known as Newton’s
algorithm, which is generally referred to as a second order method. Roughly speaking, a second order
method makes use of both first and second derivatives. Generally, second order methods are much
more accurate than first order ones. Given a twice differentiable function g : R → R, Newton’s method
generates a sequence {x
(k)} iteratively according to the following update rule:
x
(k+1) = x
(k) −
g
0
(x
(k)
)
g
00(x
(k))
, k = 0, 1, 2, . . . , (1)
For example, consider the function g(x) = 1
2
x
2 − sin(x) with initial guess x
(0) = 0. Then
g
0
(x) = x − cos(x), and g
00(x) = 1 + sin(x),
and so we have the following iterations:
x
(1) = x
(0) −
x
(0) − cos(x
0
)
1 + sin(x
(0))
= 0 −
0 − cos(0)
1 + sin(0) = 1
x
(2) = x
(1) −
x
(1) − cos(x
1
)
1 + sin(x
(1))
= 1 −
1 − cos(1)
1 + sin(1) = 0.750363867840244
x
(3) = 0.739112890911362
.
.
.
and this continues until we terminate the algorithm (as a quick exercise for your own benefit, code this
up, plot the function and each of the iterates). We note here that in practice, we often use a different
update called the dampened Newton method, defined by:
x
(k+1) = x
(k) − α
g
0
(xk)
g
00(xk)
, k = 0, 1, 2, . . . . (2)
Here, as in the case of GD, the step size α has the effect of ‘dampening’ the update. Consider now the
twice differentiable function f : R
n → R. The Newton steps in this case are now:
x
(k+1) = x
(k) − (H(x
(k)
))−1∇f(x
(k)
), k = 0, 1, 2, . . . , (3)
where H(x) = ∇2f(x) is the Hessian of f. Heuristically, this formula generalized equation (1) to functions with vector inputs since the gradient is the analog of the first derivative, and the Hessian is the
analog of the second derivative.
(a) Consider the function f : R
2 → R defined by
f(x, y) = 100(y − x
2
)
2 + (1 − x)
2
.
Create a 3D plot of the function using mplot3d (see lab0 for example). Use a range of [−5, 5] for
both x and y axes. Further, compute the gradient and Hessian of f. what to submit: A single plot, the
code used to generate the plot, the gradient and Hessian calculated along with all working. Add a copy of the
code to solutions.py
Page 3
(b) Using NumPy only, implement the (undampened) Newton algorithm to find the minimizer of the
function in the previous part, using an initial guess of x
(0) = (−1.2, 1)T
. Terminate the algorithm
when
∇f(x
(k)
)
2
≤ 10−6
. Report the values of x
(k)
for k = 0, 1, . . . , K where K is your final
iteration. what to submit: your iterations, and a screen shot of your code. Add a copy of the code to
solutions.py
Question 2. Solving Logistic Regression Numerically
Note: throughout this question do not use any existing implementations of any of the algorithms
discussed unless explicitly asked to do so in the question. Using existing implementations can
result in a grade of zero for the entire question. In this question we will compare gradient descent and
Newton’s algorithm for solving the logistic regression problem. Recall that in logistic regresion, our
goal is to minimize the log-loss, also referred to as the cross entropy loss. Consider an intercept β0 ∈ R,
parameter vector β = (β1, . . . , βm)
T ∈ R
m, target yi ∈ {0, 1} and input vector xi = (xi1, xi2, . . . , xip)
T
.
Consider also the feature map φ : R
p → R
m and corresponding feature vector φi = (φi1, φi2, . . . , φim)
T
where φi = φ(xi). Define the (`2-regularized) log-loss function:
L(β0, β) = 1
2
kβk
2
2 +
λ
n
Xn
i=1
yi
ln
1
σ(β0 + β
T φi)
+ (1 − yi) ln
1
1 − σ(β0 + β
T φi)
,
where σ(z) = (1+e
−z
)
−1
is the logistic sigmoid, and λ is a hyper-parameter that controls the amount of
regularization. Note that λ here is applied to the data-fit term as opposed to the penalty term directly,
but all that changes is that larger λ now means more emphasis on data-fitting and less on regularization.
Note also that you are provided with an implementation of this loss in helper.py.
(a) Show that the gradient descent update (with step size α) for γ = [β0, βT
]
T
takes the form
γ
(k) = γ
(k−1) − α ×
"
−
λ
n
1
T
n
(y − σ(β
(k−1)
0
1n + Φβ
(k−1)))
β
(k−1) −
λ
nΦ
T
(y − σ(β
(k−1)
0
1n + Φβ
(k−1)))#
,
where the sigmoid σ(·) is applied elementwise, 1n is the n-dimensional vector of ones and
Φ =
φ
T
1
φ
T
2
.
.
.
φ
T
n
∈ R
n×m, y =
y1
y2
.
.
.
yn
∈ R
n
.
what to submit: your working out.
(b) In what follows, we refer to the version of the problem based on L(β0, β) as the Primal version.
Consider the re-parameterization: β =
Pn
j=1 θjφ(xj ). Show that the loss can now be written as:
L(θ0, θ) = 1
2
θ
T Aθ +
λ
n
Xn
i=1
yi
ln
1
σ(θ0 + θ
T bxi
)
+ (1 − yi) ln
1
1 − σ(θ0 + θ
T bxi
)
.
where θ0 ∈ R, θ = (θ1, . . . , θn)
T ∈ R
n, A ∈ R
n×n and for i = 1, . . . , n, bxi ∈ R
n. We refer to this
version of the problem as the Dual version. Write down exact expressions for A and bxi
in terms
of k(xi
, xj ) := hφ(xi), φ(xj )i for i, j = 1, . . . , n. Further, for the dual parameter η = [θ0, θT
]
T
, show
that the gradient descent update is given by:
η
(k) = η
(k−1) − α ×
"
−
λ
n
1
T
n
(y − σ(θ
(k−1)
0
1n + Aθ(k−1)))
Aθ(k−1) −
λ
nA(y − σ(θ
(k−1)
0
1n + Aθ(k−1)))#
,
Page 4
If m n, what is the advantage of the dual representation relative to the primal one which just
makes use of the feature maps φ directly? what to submit: your working along with some commentary.
(c) We will now compare the performance of (primal/dual) GD and the Newton algorithm on a
real dataset using the derived updates in the previous parts. To do this, we will work with the
songs.csv dataset. The data contains information about various songs, and also contains a class
variable outlining the genre of the song. If you are interested, you can read more about the data
here, though a deep understanding of each of the features will not be crucial for the purposes of
this assessment. Load in the data and preform the follwing preprocessing:
(I) Remove the following features: ”Artist Name”, ”Track Name”, ”key”, ”mode”, ”time signature”,
”instrumentalness”
(II) The current dataset has 10 classes, but logistic regression in the form we have described it here
only works for binary classification. We will restrict the data to classes 5 (hiphop) and 9 (pop).
After removing the other classes, re-code the variables so that the target variable is y = 1 for
hiphop and y = 0 for pop.
(III) Remove any remaining rows that have missing values for any of the features. Your remaining
dataset should have a total of 3886 rows.
(IV) Use the sklearn.model selection.train test split function to split your data into
X train, X test, Y train and Y test. Use a test size of 0.3 and a random state of 23 for
reproducibility.
(V) Fit the sklearn.preprocessing.MinMaxScaler to the resulting training data, and then
use this object to scale both your train and test datasets so that the range of the data is in
(0, 0.1).
(VI) Print out the first and last row of X train, X test, y train, y test (but only the first 3 columns of
X train, X test).
What to submit: the print out of the rows requested in (VI). A copy of your code in solutions.py
(d) For the primal problem, we will use the feature map that generates all polynomial features up to
and including order 3, that is:
φ(x) = [1, x1, . . . , xp, x3
1
, . . . , x3
p
, x1x2x3, . . . , xp−1xp−2xp−1].
In python, we can generate such features using sklearn.preprocessing.PolynomialFeatures.
For example, consider the following code snippet:
1 from sklearn.preprocessing import PolynomialFeatures
2 poly = PolynomialFeatures(3)
3 X = np.arange(6).reshape(3, 2)
4 poly.fit_transform(X)
5
Transform the data appropriately, then run gradient descent with α = 0.4 on the training dataset
for 50 epochs and λ = 0.5. In your implementation, initalize β
(0)
0 = 0, β(0) = 0p, where 0p is the
p-dimensional vector of zeroes. Report your final train and test losses, as well as plots of training
loss at each iteration. 1 what to submit: one plot of the train losses. Report your train and test losses, and
a screen shot of any code used in this section, as well as a copy of your code in solutions.py.
1
if you need a sanity check here, the best thing to do is use sklearn to fit logistic regression models. This should give you an idea of
what kind of loss your implementation should be achieving (if your implementation does as well or better, then you are on the right
track)
Page 5
(e) For the primal problem, run the dampened Newton algorithm on the training dataset for 50 epochs
and λ = 0.5. Use the same initialization for β0, β as in the previous question. Report your final
train and test losses, as well as plots of your train loss for both GD and Newton algorithms for all
iterations (use labels/legends to make your plot easy to read). In your implementation, you may
use that the Hessian for the primal problem is given by:
H(β0, β) =
λ
n
1
T
nD1n
λ
n
1
T
nDΦ
λ
nΦ
T D1n Ip +
λ
nΦ
T DΦ
,
where D is the n × n diagonal matrix with i-th element σ(di)(1 − σ(di)) and di = β0 + φ
T
i β. what to
submit: one plot of the train losses. Report your train and test losses, and a screen shot of any code used in
this section, as well as a copy of your code in solutions.py.
(f) For the feature map used in the previous two questions, what is the correspongdin kernel k(x, y)
that can be used to give the corresponding dual problem? what to submit: the chosen kernel.
(g) Implement Gradient Descent for the dual problem using the kernel found in the previous part.
Use the same parameter values as before (although now θ
(0)
0 = 0 and θ
(0) = 0n). Report your final
training loss, as well as plots of your train loss for GD for all iterations. what to submit: a plot of the
train losses and report your final train loss, and a screen shot of any code used in this section, as well as a
copy of your code in solutions.py.
(h) Explain how to compute the test loss for the GD solution to the dual problem in the previous part.
Implement this approach and report the test loss. what to submit: some commentary and a screen shot
of your code, and a copy of your code in solutions.py.
(i) In general, it turns out that Newton’s method is much better than GD, in fact convergence of the
Newton algorithm is quadratic, whereas convergence of GD is linear (much slower than quadratic).
Given this, why do you think gradient descent and its variants (e.g. SGD) are much more popular
for solving machine learning problems? what to submit: some commentary
Page 6
软件开发、广告设计客服
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-23:00
微信:codinghelp
热点项目
更多
代做ceng0013 design of a pro...
2024-11-13
代做mech4880 refrigeration a...
2024-11-13
代做mcd1350: media studies a...
2024-11-13
代写fint b338f (autumn 2024)...
2024-11-13
代做engd3000 design of tunab...
2024-11-13
代做n1611 financial economet...
2024-11-13
代做econ 2331: economic and ...
2024-11-13
代做cs770/870 assignment 8代...
2024-11-13
代写amath 481/581 autumn qua...
2024-11-13
代做ccc8013 the process of s...
2024-11-13
代写csit040 – modern comput...
2024-11-13
代写econ 2070: introduc2on t...
2024-11-13
代写cct260, project 2 person...
2024-11-13
热点标签
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
联系我们
- QQ: 9951568
© 2021
www.rj363.com
软件定制开发网!