Exercise 6 (deadline: Dec 15, 2014)

Machine Learning
Winter Semester 2014/2015
Exercise 6
Niko Krasowski
[email protected]
Exercise 6
Deadline: 15.12.2014
1
Proof - ridge regression - primal vs dual (6 points)
Remember that in the primal formulation, the problem of ridge regression looks as:
minβ ky − Xβk22 + τ kβk22
(1)
where X is a N × D Matrix, β is a D dimensional vector and y is a N dimensional vector. As you
saw in the lecture the optimal βˆ is given by: Here ID is the D dimensional unit matrix.
βˆ = X T X + τ ID
−1
XT y .
(2)
From the lecture you also know that the dual formulation the problem looks like:
maxα − αT XX T + τ IN α + 2αT y
with the solution for αˆ
−1
y.
α
ˆ = XX T + τ IN
For each feasible α a corresponding feasible β is given by:
β = XT α .
Prove that the optimal βˆ corresponds to the optimal αˆ :
βˆ = X T α
ˆ.
Hint: First prove, then use the following Lemma:
X T X + τ ID
2
−1
X T = X T XX T + τ IN
−1
(3)
(4)
(5)
(6)
(7)
Kernelized (Ridge) Regression (8 points)
From the lecture you know that using the dual formulation of the ridge regression we are able to
introduce the Kernel Trick. New regressed values ynew are computed by:
−1
ynew = yT (K + τ · 1) κT .
(8)
Here we can precompute α = yT (K + τ · 1)−1 . κ = Xnew X T will be computed from a new
instance (Xnew ).
Use a gaussian kernel
"
#
2
1
|Xi1 − Xi2 |
K(Xi1 , Xi2 ) = √
exp
2σ 2
2πσ
(9)
for te task of reconstructing missing pixels (pixelvalue = 0) in a grayscale image. You can nd such
an image on https://dl.dropboxusercontent.com/u/1537789/cc_90.png. Cut o the Gaussian
at a sensible height to get a sparse Kernel. When coding the regression you have two possibilities:
either you ask in the neighborhood (inuence area of the kernel) of a query point for contributions of
the known points or you let all known points irradiate their contributions into their neighborhood.
Do the same experiment for the Kernel Regression (no Ridge).
ynew
P
yi κi
= Pi
i κi
(10)
Play with the σ of the Gaussian as well as with the τ of the Ridge Regression and nd the parameters,
that produce the optically best reconstructed image for both approaches.
1/2
Machine Learning
Winter Semester 2014/2015
3
Exercise 6
Niko Krasowski
[email protected]
Fitting Circles (6 points)
Have a look at the distribution of the 2D data you can nd here: https://dl.dropboxusercontent.
com/u/1537789/circles.npy. How many circles would you t in there as a human (Pay attention
that the axes are scaled equally. Otherwise your circles will look like ellipses). Now implement the
RANSAC-Algorithm for the tting of circles:
• Repeat
Choose randomly 3 points and determine the circle passing all of them.
Classify points that are closer than to the circle as inlier and the remaining ones as
outlier. Count the inliers.
If for this circle there exist more inliers than for the best circle so far then save this circle
and its inliers.
• If you want to t further circles delete all inliers of the last tted circle so far from the dataset
and repeat the procedure.
Plot all tted circles together with the original data and commment on the result. Is the result
sensitive to the value of , the parameter that is used to determine the inliers?
Regulations
Please hand in the python code, gures and explanations (describing clearly which belongs to which).
Non-trivial sections of your code should be explained with short comments, and variables should
have self-explanatory names. Plots should have informative axis labels, legends and captions. Please
enclose all results into a single .pdf document and hand in the .py les that created the results.
Please email the solutions to [email protected] before the deadline. You
may hand in the exercises in teams of maximally three people, which must be clearly named on the
solution sheet (one email is sucient). Discussions between dierent teams about the exercises are
encouraged, but the code must not be copied verbatim (the same holds for any implementations
which may be available on the WWW). Please respect particularly this rule, otherwise we cannot
give you a passing grade. Solutions are due by email at the beginning of the next exercise. For each
exercise there will be maximally 20 points assigned. If you have 50% or more points in the end of
the semester you will be allowed to take the exam.
2/2

Download Report