$30.00
Description
Weekly homeworks are individual work. See the Course Information handout^{2} for detailed policies.

[4pts] Information Theory. The goal of this question is to help you become more familiar with the basic equalities and inequalities of information theory. They appear in many contexts in machine learning and elsewhere, so having some experience with them is quite helpful. We review some concepts from information theory, and ask you a few questions.
Recall the de nition of the entropy of a discrete random variable X with probability mass

P
_{p(}^{1}_{x)} . Here the summation is over all possible values of
function p: H(X) = _{x} p(x) log_{2}
x 2 X , which (for simplicity) we assume is nite. For example, X might be f1; 2; : : : ; Ng.
(a) [1pt] Prove that the entropy H(X) is nonnegative.
An important concept in information theory is the relative entropy or the KLdivergence of two distributions p and q. It is de ned as

KL(pjjq) =
X
p(x)
p(x) log_{2}
:
q(x)
x
The KLdivergence is one of the most commonly used measure of di erence (or divergence) between two distributions, and it regularly appears in information theory, machine learning, and statistics.
If two distributions are close to each other, their KL divergence is small. If they are exactly the same, their KL divergence is zero. KL divergence is not a true distance metric (since it isn’t symmetric and doesn’t satisfy the triangle inequality), but we often use it as a measure of dissimilarity between two probability distributions.

[2pt] Prove that KL(pjjq) is nonnegative. Hint: you may want to use Jensen’s Inequality, which is described in the Appendix.

[1pt] The Information Gain or Mutual Information between X and Y is I(Y ; X) = H(Y ) H(Y jX). Show that
I(Y ; X) = KL(p(x; y)jjp(x)p(y));
P
where p(x) = _{y }p(x; y) is the marginal distribution of X.

[2pts] Bene t of Averaging. Consider m estimators h_{1}; : : : ; h_{m}, each of which accepts an input x and produces an output y, i.e., y_{i} = h_{i}(x). These estimators might be generated
through a Bagging procedure, but that is not necessary to the result that we want to prove. Consider the squared error loss function L(y; t) = ^{1}_{2} (y t)^{2}. Show that the loss of the average
estimator
h(x) =
m
1 X
h_{i}(x);
m
i=1
is smaller than the average loss of the estimators. That is, for any x and t, we have

1
m
L(h(x); t) _{m}
X_{i}
L(h_{i}(x); t):
=1
Hint: you may want to use Jensen’s Inequality, which is described in the Appendix.

[3pts] AdaBoost. The goal of this question is to show that the AdaBoost algorithm changes the weights in order to force the weak learner to focus on di cult data points. Here we consider
the case that the target labels are from the set f 1; +1g and the weak learner also returns a classi er whose outputs belongs to f 1; +1g (instead of f0; 1g). Consider the tth iteration of AdaBoost, where the weak learner is

2H
N
X_{i}
(i)
(i)
argmin
^{h}t
w_{i}Ifh(x ) 6= t g;
h
=1
the wweighted classi cation error is
N
err_{t} =
_{i=1} w_{i}Ifh_{t}(x^{(i)}) 6= t^{(i)}g
;
P
_{i=1} ^{w}i
N
1
err
and the classi er coe cient is _{t} =
log
1 ^{P}_{t}
. (Here, log denotes the natural logarithm.)
2
err_{t}
AdaBoost changes the weights of each sample depending on whether the weak learner h_{t} classi es it correctly or incorrectly. The updated weights for sample i is denoted by w_{i}^{0} and is

w_{i}^{0}
w_{i} exp_{t}t^{(i)}h_{t}(x^{(i)}) :
Show that the error w.r.t. (w^{0}
; : : : ; w^{0}
) is exactly
1
. That is, show that
2
1
N
P
N
w^{0} h_{t}(x^{(i)}) = t^{(i)}
1
err^{0} =
i=1 i^{If}
_{i=1} w_{i}^{0}
6 g
=
:
2
N
t
P
Note that here we use the weak learner of iteration t and evaluate it according to the new weights, which will be used to learn the t + 1st weak learner. What is the interpretation of this result?
Tips:
Start from err^{0}_{t} and divide the summation to two sets of E = fi : Ifh_{t}(x^{(i)}) 6= t^{(i)}gg and its complement E^{c} = fi : Ifh_{t}(x^{(i)}) = t^{(i)}gg.
Note that
P
i2E ^{w}^{i} _{= err}_{t}_{:}
PN
_{i=1} ^{w}i
2Appendix: Convexity and Jensen’s Inequality. Here, we give some background on convexity which you may nd useful for some of the questions in this assignment. You may assume anything given here.
Convexity is an important concept in mathematics with many uses in machine learning. We brie y de ne convex set and function and some of their properties here. Using these properties are useful in solving some of the questions in the rest of this homework. If you are interested to know more about convexity, refer to Boyd and Vandenberghe, Convex Optimization, 2004.
A set C is convex if the line segment between any two points in C lies within C, i.e., if for any x_{1}; x_{2} 2 C and for any 0 1, we have
x_{1} + (1 )x_{2} 2 C:
For example, a cube or sphere in R^{d} are convex sets, but a cross (a shape like X) is not.
A function f : R^{d} ! R is convex if its domain is a convex set and if for all x_{1}; x_{2} in its domain, and for any 0 1, we have
f( x_{1} + (1 )x_{2}) f(x_{1}) + (1 )f(x_{2}):
This inequality means that the line segment between (x_{1}; f(x_{1})) and (x_{2}; f(x_{2})) lies above the graph of f. A convex function looks like `. We say that f is concave if f is convex. A concave function looks like a.
Some examples of convex and concave functions are (you do not need to use most of them in your homework, but knowing them is useful):
Powers: x^{p} is convex on the set of positive real numbers when p 1 or p 0. It is concave for 0 p 1.
Exponential: e^{ax} is convex on R, for any a 2 R.
Logarithm: log(x) is concave on the set of positive real numbers.
Norms: Every norm on R^{d} is convex.
Max function: f(x) = maxfx_{1}; x_{2}; : : : ; x_{d}g is convex on R^{d}.
Logsumexp: The function f(x) = log(e^{x}1 + : : : + e^{x}d ) is convex on R^{d}.
An important property of convex and concave functions, which you may need to use in your homework, is Jensen’s inequality. Jensen’s inequality states that if (x) is a convex function of x, we have
(E [X]) E [ (X)] :
In words, if we apply a convex function to the expectation of a random variable, it is less than or equal to the expected value of that convex function when its argument is the random variable. If the function is concave, the direction of the inequality is reversed.
Jensen’s inequality has a physical interpretation: Consider a set X = fx_{1}; : : : ; x_{N} g of points on R. Corresponding to each point, we have a probability p(x_{i}). If we interpret the probability as mass, and we put an object with mass p(x_{i}) at location (x_{i}; (x_{i})), then the centre of gravity of these objects, which is in R^{2}, is located at the point (E [X] ; E [ (X)]). If is convex `, the centre of gravity lies above the curve x 7! (x), and vice versa for a concave function a.
3