Machine Learning

\(k\)-means assigns every point to its nearest centroid, so cluster 3 holds the points that are closer to its centroid \(\boldsymbol{c}_{3}\) than to \(\boldsymbol{c}_{1}\) and \(\boldsymbol{c}_{2}\). For each other centroid \(\boldsymbol{c}_{j}\), the condition \(\lVert\boldsymbol{p} - \boldsymbol{c}_{3}\rVert^{2} \leq \lVert\boldsymbol{p} - \boldsymbol{c}_{j}\rVert^{2}\) simplifies to a linear inequality in \(\boldsymbol{p}\), that is, a half-plane. The region of cluster 3 is an intersection of half-planes, so it is convex: with any two of its points it contains the whole segment between them.

The point \((0, 1)\) is the midpoint of \((1, 1)\) and \((-1, 1)\), so it must belong to cluster 3. The points in A, B and C lie off that segment, and another centroid could be nearer to them.

Answer: D

Naïve Bayes assumes that the attributes are conditionally independent given the class, so it needs only these parameters:

• the class prior \(P(y = 1)\): one parameter, because \(P(y = 0) = 1 - P(y = 1)\);
• for each of the 2 classes and each of the \(K\) attributes, \(P(x_{k} = 1 \mid y)\): \(2K\) parameters, because \(P(x_{k} = 0 \mid y)\) follows from it.

The total is \(2K + 1\). Counts that grow like \(2^{K}\) (A and C) are what a model of the full joint distribution of the attributes within each class would need, which is exactly what the independence assumption avoids.

Answer: B

At the maximum the gradient of \(J\) is zero. Both matrices are symmetric, so by the quotient rule

\[\nabla J(u) = \frac{2 S_{B} u \,(u^{T} S_{W} u) - 2 S_{W} u \,(u^{T} S_{B} u)}{(u^{T} S_{W} u)^{2}} = 0 \;\Rightarrow\; S_{B} u^{*} = J(u^{*})\, S_{W} u^{*} = \lambda S_{W} u^{*}.\]

Since \(S_{W}\) is non-singular, multiplying by \(S_{W}^{-1}\) gives \(S_{W}^{-1} S_{B} u^{*} = \lambda u^{*}\): \(u^{*}\) is an eigenvector of \(S_{W}^{-1} S_{B}\) for its largest eigenvalue \(\lambda\).

Option B has \(\lambda\) on the wrong side (it would hold with \(1/\lambda\)), C multiplies by \(S_{W}\) instead of its inverse, and D fails because \(J\) does not depend on the length of \(u\), so \(u^{*}\) can be rescaled freely.

Answer: A

Single linkage repeatedly merges the two clusters whose closest members are nearest to each other.

• Distance 1: \(x_{1}\) joins \(x_{2}\), and \(x_{4}\) joins \(x_{5}\).
• Distance 2: \(x_{3}\) joins \(\{x_{4}, x_{5}\}\) through \(d(x_{3}, x_{4}) = 2\); the pair \(\{x_{1}, x_{2}\}\) is at least 3 from every other point.
• Distance 3: \(\{x_{1}, x_{2}\}\) joins \(\{x_{3}, x_{4}, x_{5}\}\), for example through \(d(x_{1}, x_{4}) = 3\).

Dendrogram A shows exactly this. B attaches \(x_{3}\) to \(\{x_{1}, x_{2}\}\), where its nearest link is 3, not 2. C and D pair \(x_{3}\) with \(x_{4}\) first, although \(d(x_{4}, x_{5}) = 1\) is smaller than \(d(x_{3}, x_{4}) = 2\).

Answer: A

The inputs and all weights are positive, so every neuron receives a positive value and \(ReLU\) acts as the identity. Both networks are then linear, and only the total weight from each input to the output matters.

• First layer (weights 1): the neurons receive \(x_{1} + x_{2}\), \(x_{1} + x_{3}\) and \(x_{1} + x_{2} + x_{3}\), which add up to \(s = 3x_{1} + 2x_{2} + 2x_{3}\).
• Second layer: each of its two neurons receives \(2s\).
• Output: \(3(2s) + 3(2s) = 12s\).

So Figure 1 computes \(36x_{1} + 24x_{2} + 24x_{3}\), giving \(p = 36\), \(q = 24\), \(r = 24\). Option D would need \(x_{2}\) and \(x_{3}\) to reach all three first-layer neurons, but each has only two connections.

Answer: A

A dataset is linearly separable when a single straight line puts every circle on one side and every square on the other.

• A holds: in (i) the circles have \(y \ge 2\) and the squares lie around \(y = 1\) or lower, so the line \(y = 1.6\) splits them.
• B fails: in (ii) the circle at (2, 2) is the midpoint of the squares at (1, 2) and (3, 2). A half-plane holding both squares also holds their midpoint, so the circle cannot be cut off.
• C fails: (iii) is the XOR pattern. The circles (1, 1), (3, 3) and the squares (1, 3), (3, 1) have the same midpoint (2, 2), which would have to lie on both sides.
• D holds: in (iv) the squares sit to the upper left and the circles to the lower right, so a slanted line such as \(y = x - 0.3\) works.

Answer: A, D

Information gain is the entropy of the Target minus the weighted entropy left after splitting on Pitch (logarithms to base 2).

• All 10 games: 4 Green and 6 Blue, so \(H(C) = -0.4\log_{2}0.4 - 0.6\log_{2}0.6 \approx 0.971\).
• \(S\) pitches (games 1, 2, 4, 7, 10): 3 Green and 2 Blue, the same 0.6 / 0.4 split with the colours swapped, so the entropy is again \(\approx 0.971\).
• \(F\) pitches (games 3, 5, 6, 8, 9): 1 Green and 4 Blue, so the entropy is \(-0.2\log_{2}0.2 - 0.8\log_{2}0.8 \approx 0.722\).

Each branch holds half of the games, so

\[ \text{Gain} = 0.971 - \left(\tfrac{1}{2} \times 0.971 + \tfrac{1}{2} \times 0.722\right) = \tfrac{1}{2}(0.971 - 0.722) \approx 0.1245 \]

which is 0.12 to two decimal places (the key accepts 0.12 to 0.13).

Answer: 0.12

Distances from the diamond at (2, 1):

• circle (1, 1): 1
• circle (1, 2) and square (3, 2): \(\sqrt{2} \approx 1.41\) each
• square (2, 3): 2
• square (3, 3): \(\sqrt{5} \approx 2.24\)

Now try the odd values of \(k\) in turn:

• \(k = 1\): the nearest point is a circle, so the label is circle.
• \(k = 3\): two circles and one square; the tie at \(\sqrt{2}\) does not matter because both tied points are among the three. The label is circle.
• \(k = 5\): all five points vote, 3 squares to 2 circles, so the label is square.

Answer: 5