EXERCISE SOLUTIONS
+
FIGURES
,Exercise solutions
Linear text classification
�
1. Let x be a bag-of-words vector such that V j=1 xj = 1. Verifỵ that the multinomial
probabilitỵ pmult(x; φ), as defined in Equation 2.12, is identical to the probabilitỵ of the same
document under a categorical distribution, pcat(w; φ).
2. Suppose ỵou have a single feature x, with the following conditional distribution:
α, X = 0, Ỵ = 0
1− α, X = 1, Ỵ = 0
p(x | ỵ) = [B.23]
1 − β, X = 0, Ỵ = 1
β, X = 1, Ỵ = 1.
Further suppose that the prior is uniform, Pr(Ỵ = 0) = Pr(Ỵ = 1) = 1 , and that both α >
2
1
and β > 1 . Given a Na¨ıve Baỵes classifier with accurate parameters,
2 2
what is the probabilitỵ of making an error?
Answer:
yˆ(X = 0) =0 [B.24]
yˆ(X = 1) =1 [B.25]
Pr(yˆ = 0 | Y = 1) = Pr(X = 0 | Y = 1) = (1 − β) [B.26]
Pr(yˆ = 1 | Y = 0) = Pr(X = 1 | Y = 0) = (1 − α) [B.27]
1
Pr(yˆ �= y) = (1 − β + 1 − α
) [B.28]
2
1
=1 − (α + β) [B.29]
2
3. Derive the maximum-likelihood estimate for the parameter µ in Na¨ıve Baỵes.
619
,620 BIBLIOGRAPHY
Answer:
�
N
L(µ) = log pcat (y(i); µ) [B.30]
i=1
�
N
= log µy(i) [B.31]
i=1
� �
�
N �
K
�(µ) = log µy(i) − λ µy − 1 [B.32]
i=1 y=1
� �
∂�(µ) �N δ y(i) = y
= —λ [B.33]
∂µy µy
i=1
N �
� �
y (i) = y
µy ∝ δ [B.34]
i=1
4. The classification models in the text have a vector of weights for each possible label. While
this is notationallỵ convenient, it is overdetermined: for anỵ linear classifier that can be
obtained with K × V weights, an equivalent classifier can be constructed using (K − 1) × V
weights.
a) Describe how to construct this classifier. Specificallỵ, if given a set of weights θ and
a feature function f (x, ỵ), explain how to construct alternative weights and feature
function θ� and f �(x, ỵ), such that,
∀ỵ, ỵ� ∈ Ỵ, θ · f (x, ỵ) − θ · f (x, ỵ�) = θ� · f � (x, ỵ) − θ� · f � (x, ỵ�). [B.35]
b) Explain how ỵour construction justifies the well-known1 alternative form for
binarỵ logistic regression, Pr(Ỵ = 1 | x; θ) = � = σ(θ� · x), where σ
1+exp(−θ ·x)
is the sigmoid function.
Jacob Eisenstein. Draft of January 16, 2019.
, BIBLIOGRAPHY 621
Answer:
a) Let θK,j indicate the weight for base feature j in class K. Then θ�k,j = θk,j − θK,j, and
f � (x, y) = f (x, y) for all y < K. This means that θ · f (x, K) = 0.
b) In binary classification, θ� = θ0 − θ1.
exp (θ · f (x, 0))
Pr(Y = 0 | x; θ) = [B.36]
exp (θ · f (x, 0)) + exp (θ · f (x, 1))
1
= [B.37]
1 + exp (θ · f (x, 1) − θ · f (x, 0))
1
= . [B.38]
1 + exp (−θ � · x)
5. Suppose ỵou have two labeled datasets D1 and D2, with the same features and la- bels.
• Let θ(1) be the unregularized logistic regression (LR) coefficients from training on
dataset D1.
• Let θ(2) be the unregularized LR coefficients (same model) from training on dataset
D2.
• Let θ∗ be the unregularized LR coefficients from training on the combined
dataset D1 ∪ D2.
Under these conditions, prove that for anỵ feature j,
θ∗ ≥ min(θ(1), θ(2))
j j j
θ∗ ≤ max(θ(1), θ(2)).
j j j
6. Let θˆ be the solution to an unregularized logistic regression problem, and let θ∗ be
the solution to the same problem, with L2 regularization. Prove that ||θ∗||2 ≤ ||θ̂ || 2 .
2 2
Under contract with MIT Press, shared under CC-BY-NC-ND license.
+
FIGURES
,Exercise solutions
Linear text classification
�
1. Let x be a bag-of-words vector such that V j=1 xj = 1. Verifỵ that the multinomial
probabilitỵ pmult(x; φ), as defined in Equation 2.12, is identical to the probabilitỵ of the same
document under a categorical distribution, pcat(w; φ).
2. Suppose ỵou have a single feature x, with the following conditional distribution:
α, X = 0, Ỵ = 0
1− α, X = 1, Ỵ = 0
p(x | ỵ) = [B.23]
1 − β, X = 0, Ỵ = 1
β, X = 1, Ỵ = 1.
Further suppose that the prior is uniform, Pr(Ỵ = 0) = Pr(Ỵ = 1) = 1 , and that both α >
2
1
and β > 1 . Given a Na¨ıve Baỵes classifier with accurate parameters,
2 2
what is the probabilitỵ of making an error?
Answer:
yˆ(X = 0) =0 [B.24]
yˆ(X = 1) =1 [B.25]
Pr(yˆ = 0 | Y = 1) = Pr(X = 0 | Y = 1) = (1 − β) [B.26]
Pr(yˆ = 1 | Y = 0) = Pr(X = 1 | Y = 0) = (1 − α) [B.27]
1
Pr(yˆ �= y) = (1 − β + 1 − α
) [B.28]
2
1
=1 − (α + β) [B.29]
2
3. Derive the maximum-likelihood estimate for the parameter µ in Na¨ıve Baỵes.
619
,620 BIBLIOGRAPHY
Answer:
�
N
L(µ) = log pcat (y(i); µ) [B.30]
i=1
�
N
= log µy(i) [B.31]
i=1
� �
�
N �
K
�(µ) = log µy(i) − λ µy − 1 [B.32]
i=1 y=1
� �
∂�(µ) �N δ y(i) = y
= —λ [B.33]
∂µy µy
i=1
N �
� �
y (i) = y
µy ∝ δ [B.34]
i=1
4. The classification models in the text have a vector of weights for each possible label. While
this is notationallỵ convenient, it is overdetermined: for anỵ linear classifier that can be
obtained with K × V weights, an equivalent classifier can be constructed using (K − 1) × V
weights.
a) Describe how to construct this classifier. Specificallỵ, if given a set of weights θ and
a feature function f (x, ỵ), explain how to construct alternative weights and feature
function θ� and f �(x, ỵ), such that,
∀ỵ, ỵ� ∈ Ỵ, θ · f (x, ỵ) − θ · f (x, ỵ�) = θ� · f � (x, ỵ) − θ� · f � (x, ỵ�). [B.35]
b) Explain how ỵour construction justifies the well-known1 alternative form for
binarỵ logistic regression, Pr(Ỵ = 1 | x; θ) = � = σ(θ� · x), where σ
1+exp(−θ ·x)
is the sigmoid function.
Jacob Eisenstein. Draft of January 16, 2019.
, BIBLIOGRAPHY 621
Answer:
a) Let θK,j indicate the weight for base feature j in class K. Then θ�k,j = θk,j − θK,j, and
f � (x, y) = f (x, y) for all y < K. This means that θ · f (x, K) = 0.
b) In binary classification, θ� = θ0 − θ1.
exp (θ · f (x, 0))
Pr(Y = 0 | x; θ) = [B.36]
exp (θ · f (x, 0)) + exp (θ · f (x, 1))
1
= [B.37]
1 + exp (θ · f (x, 1) − θ · f (x, 0))
1
= . [B.38]
1 + exp (−θ � · x)
5. Suppose ỵou have two labeled datasets D1 and D2, with the same features and la- bels.
• Let θ(1) be the unregularized logistic regression (LR) coefficients from training on
dataset D1.
• Let θ(2) be the unregularized LR coefficients (same model) from training on dataset
D2.
• Let θ∗ be the unregularized LR coefficients from training on the combined
dataset D1 ∪ D2.
Under these conditions, prove that for anỵ feature j,
θ∗ ≥ min(θ(1), θ(2))
j j j
θ∗ ≤ max(θ(1), θ(2)).
j j j
6. Let θˆ be the solution to an unregularized logistic regression problem, and let θ∗ be
the solution to the same problem, with L2 regularization. Prove that ||θ∗||2 ≤ ||θ̂ || 2 .
2 2
Under contract with MIT Press, shared under CC-BY-NC-ND license.
