Unit 3 · Exercises
Unit 3 exercises
These exercises practice the computations behind the models of Unit 3 and the choices you face when applying them to security data. Work each one before opening its solution.
Exercise 1. A penalized gradient step
A logistic regression with one feature has parameters \(w = 0.5\) and \(b = -1\). The training data is \(x = 1, 2, 3, 4\) with labels \(y = 0, 0, 1, 1\). The loss is the mean log-loss plus an L2 penalty \(\lambda w^2\) with \(\lambda = 0.1\) (the intercept is not penalized).
(a) Compute the four predicted probabilities and the penalized loss. (b) Compute the gradient with respect to \(w\) and \(b\). (c) Take one gradient step with \(\eta = 0.5\) and check that the loss decreases.
Show the answer
(a) The scores \(wx + b\) are \(-0.5, 0, 0.5, 1\), so the probabilities are 0.3775, 0.5, 0.6225 and 0.7311. The log-losses are \(-\log(1 - 0.3775) = 0.474\), \(-\log 0.5 = 0.693\), \(-\log 0.6225 = 0.474\) and \(-\log 0.7311 = 0.313\), with mean 0.4886. The penalty adds \(0.1 \times 0.25 = 0.025\), so the loss is 0.5136.
(b) The errors \(p_i - y_i\) are 0.3775, 0.5, \(-0.3775\) and \(-0.2689\). The partial derivative \(\partial L/\partial w\) is
and \(\partial L/\partial b\) is
(c) The step gives
The new probabilities are 0.3834, 0.5197, 0.6531 and 0.7661, and the penalized loss is 0.5080, lower than 0.5136. The penalty term pulled the step in \(w\) back. Without it the gradient in \(w\) would have been \(-0.2077\) and the step almost twice as large.
Exercise 2. Naive Bayes for invoice fraud
An e-mail filter flags invoice fraud with multinomial naive Bayes. In training, 20% of e-mails are fraudulent. Fraudulent e-mails contain 2,000 tokens in total and legitimate ones 8,000, over a vocabulary of 1,000 tokens. A new e-mail contains the tokens invoice, urgent and meeting, which occur 40, 30 and 2 times in the fraudulent training e-mails and 10, 20 and 60 times in the legitimate ones.
(a) Compute the Laplace-smoothed probabilities of the three tokens in each class and their ratios. (b) Compute the posterior probability of fraud. (c) Which token pulls the decision toward legitimate, and by how much?
Show the answer
(a) With the Laplace-smoothed estimate of Lesson 3.2, the fraud-class probabilities are \(41/3{,}000 = 0.01367\), \(31/3{,}000 = 0.01033\) and \(3/3{,}000 = 0.001\), and the legitimate-class probabilities are \(11/9{,}000 = 0.00122\), \(21/9{,}000 = 0.00233\) and \(61/9{,}000 = 0.00678\). The ratios are 11.18, 4.43 and 0.148.
(b) The prior odds are \(0.2/0.8 = 0.25\), and the posterior odds are
so the probability of fraud is \(1.83/2.83 \approx 0.65\).
(c) meeting, which multiplies the odds by 0.148, roughly dividing them by seven. Without it the odds would be \(0.25 \times 11.18 \times 4.43 = 12.4\), a probability of 0.925. An attacker who knows that the filter treats meeting as evidence of legitimacy can add it to a fraudulent message, which is why the words a text model trusts deserve inspection.
Exercise 3. Margins and hinge losses
A linear SVM has \(\mathbf{w} = (2, -1)\) and \(b = -1\). Six training points, listed in the table below, have labels \(+1\) for attack and \(-1\) for normal.
| Point | Label |
|---|---|
| (2, 1) | +1 |
| (1, 0) | +1 |
| (1.5, 1.5) | +1 |
| (0, 0) | −1 |
| (1, 1.5) | −1 |
| (1, 0.5) | −1 |
(a) What is the width of the margin? (b) Compute \(y f(\mathbf{x})\) and the hinge loss of each point. (c) Which points are support vectors, which violate the margin, and which are misclassified?
Show the answer
(a) \(\lVert\mathbf{w}\rVert = \sqrt{5} = 2.236\), so the margin is \(2/\sqrt5 \approx 0.894\).
(b) The values \(f(\mathbf{x}) = 2x_1 - x_2 - 1\) are 2, 1, 0.5, \(-1\), \(-0.5\) and 0.5, so \(y f\) is 2, 1, 0.5, 1, 0.5 and \(-0.5\), and the hinge losses \(\max(0, 1 - yf)\) are 0, 0, 0.5, 0, 0.5 and 1.5.
(c) Points (1, 0) and (0, 0) lie exactly on the margin (\(yf = 1\)). Points (1.5, 1.5) and (1, 1.5) are inside the margin but on the correct side (\(0 < yf < 1\)). Point (1, 0.5) is misclassified (\(yf < 0\)). If these \(\mathbf{w}\) and \(b\) solved the soft-margin problem, the support vectors would be among the five points on or inside the margin (the three strictly inside it certainly), and point (2, 1), beyond the margin, would not affect the solution. Whether they are optimal for some \(C\) is a separate question; the exercise only evaluates them.
Exercise 4. Choosing a split
A tree node holds 200 connections, 40 of them attacks. Three candidate splits are available. The table below gives, for each split, the number of records in each child and, in parentheses, the number of attacks among them.
| Split | Left child | Right child |
|---|---|---|
failed_logins ≥ 3 |
170 (12) | 30 (28) |
dst_host_count > 100 |
150 (20) | 50 (20) |
| hour between 0 and 5 | 120 (22) | 80 (18) |
(a) Compute the decrease in Gini impurity and the information gain of each split. (b) Which split is chosen, and why does the hour split hardly help?
Show the answer
(a) The parent has \(p = 0.2\), Gini 0.32 and entropy 0.722 bits. For failed_logins the children have Gini 0.131 and 0.124 and entropy 0.368 and 0.353, so the Gini decrease is
and the gain is 0.356 bits. For dst_host_count the children have Gini 0.231 and 0.480 and entropy 0.567 and 0.971, a decrease of 0.027 and a gain of 0.054 bits. For the hour the children have Gini 0.299 and 0.349 and entropy 0.687 and 0.769, a decrease of 0.0008 and a gain of 0.002 bits.
(b) The split on failed_logins wins under both criteria, because its right child is almost pure (28 of 30 are attacks) and its left child is purer than the parent. The hour split leaves attack shares of 0.18 and 0.23, both close to the parent's 0.2, so it carries almost no information about the label.
Exercise 5. One stage of gradient boosting
Six training records have labels 1, 1, 0, 0, 0, 1. Gradient boosting with the log-loss starts from the constant log-odds of the training labels. A stump sends records 1 to 3 to the left leaf and records 4 to 6 to the right leaf.
(a) What is the initial score \(F_0\), and what are the gradients \(g_i\) and second derivatives \(h_i\)? (b) Compute the leaf values \(w^* = -\sum g_i/(\sum h_i + \lambda)\) of Lesson 3.3 with \(\lambda = 0\) and with \(\lambda = 1\). (c) With \(\lambda = 1\) and a learning rate of 0.1, what are the new probabilities?
Show the answer
(a) Half the labels are 1, so \(F_0 = \log(0.5/0.5) = 0\) and every \(p_i = 0.5\). The gradients \(g_i = p_i - y_i\) are \(-0.5\), \(-0.5\), 0.5, 0.5, 0.5 and \(-0.5\), and \(h_i = 0.25\) for all records.
(b) The left leaf has \(\sum g = -0.5\) and \(\sum h = 0.75\), so \(w^* = 0.5/0.75 = 0.667\) with \(\lambda = 0\) and \(0.5/1.75 = 0.286\) with \(\lambda = 1\). The right leaf has \(\sum g = 0.5\), giving \(-0.667\) and \(-0.286\).
(c) The left records move to \(F_1 = 0.0286\), \(p = 0.507\), and the right records to \(F_1 = -0.0286\), \(p = 0.493\). The step is small by design. Many such steps, each fitted to the current gradients of the whole ensemble, add up to the final model, and the penalty \(\lambda\) and learning rate keep any single tree from dominating.
Exercise 6. Choosing tree depth without looking at the test days
Lab 3a sets no validation days aside; its depth sweep is evaluated on the test days. Add a cell that trains decision trees of depths 1 to 20 on days 0 to 7, selects the depth with the best AP on days 8 and 9, retrains a tree of that depth on days 0 to 9, and reports its test AP. Compare the selected depth with the depth that maximizes the test curve.
Show the answer
One solution, which reuses train, prep, Xtr, ytr, Xte, yte and best_depth from the lab, together with its imports; run it after the depth-sweep cell. The preprocessing prep was fitted on days 0 to 9; for a tree this does not matter, because the log transform and the scaling are increasing in each feature and leave the possible splits unchanged (Lesson 2.1), and the one-hot encoder finds no category in days 8 and 9 that is absent from days 0 to 7.
early = train[train["day"] <= 7]
valid = train[train["day"].isin([8, 9])]
Xe, Xv = prep.transform(early), prep.transform(valid)
val_ap = {}
for d in range(1, 21):
tree = DecisionTreeClassifier(max_depth=d, random_state=0)
tree.fit(Xe, early["label"])
val_ap[d] = average_precision_score(
valid["label"], tree.predict_proba(Xv)[:, 1])
chosen = max(val_ap, key=val_ap.get)
final = DecisionTreeClassifier(max_depth=chosen, random_state=0)
final.fit(Xtr, ytr)
test_ap = average_precision_score(yte, final.predict_proba(Xte)[:, 1])
print("depth chosen on days 8 and 9:", chosen)
print("its test AP:", round(test_ap, 3))
print("depth with the best test AP in the sweep:", best_depth)
On the course data, the depth chosen on the validation days differs from the one that maximizes the test curve, and its test AP is lower than the maximum of the sweep. That gap is the optimism you would have reported by choosing on the test days, a small instance of the selection bias discussed in Lesson 2.2. The validation days also contain no beacons, so nothing in the selection can prepare the tree for them.
Exercise 7. Choosing a model for a streaming detector
An Internet service provider wants to score 50,000 flow records per second at a peering point, retrain every night on the previous week's labeled flows (about 10 million records with 40 numeric and categorical features), and give analysts a reason for each alert. Compare logistic regression trained by SGD, an RBF SVM, k-NN, and histogram gradient boosting for this task.
Show the answer
k-NN is the weakest fit. Every prediction searches the stored training set, so scoring 50,000 records per second against ten million stored records needs approximate search and much memory, and its distances depend on careful scaling. An RBF SVM has training cost that grows between quadratically and cubically with the number of records, which makes nightly training on ten million records impractical without approximations, and its prediction cost grows with the number of support vectors. Logistic regression trained by SGD scales easily to the data and the rate, can be updated incrementally, and its coefficients give a simple per-alert explanation (each feature's contribution to the log-odds is its coefficient times its standardized value); its weakness is that it cannot represent interactions unless they are engineered as features. Histogram gradient boosting trains on millions of records in reasonable time, predicts quickly (a few hundred shallow trees), handles missing values and mixed features, and usually ranks better on tabular data of this kind (Lesson 3.3); per-alert explanations need an attribution method such as SHAP values. A reasonable plan is to evaluate gradient boosting and logistic regression on a time-ordered split with an alert budget, deploy gradient boosting if it is better there, and keep logistic regression as a baseline and fallback.