33. Machine-Learning Algorithms
Exercises
33.1-1
Let and consider the sum of pairwise squared distances for points within this single cluster . The derivation below uses equation (33.3) from the book and the expansion from the proof of Theorem 33.1 (in vector from). The latter helps establish the boxed equality below without repeating the details. Since the distance from a point to itself is zero (), we can drop the restriction from the summation without altering the result.
Summing this identity over all clusters proves that the objective function of equation (33.2) may be alternatively written as
33.1-2
Let the 4 points be the vertices of an equilateral triangle and its centroid . By randomly initializing the centers at and (step 1) and utilizing arbitrary tie-breaking, the algorithm may form in step 2 the and configuration, permanently trapping it in a suboptimal state, rather than finding the optimal and clustering.
33.1-3
As a first step, we create a set of unique points from the input. Afterward, we leverage the RANDOM_SAMPLE procedure from Exercise 5.3-5 with .
The only minor edge case to be aware of is if the number of unique points in the input happens to be strictly less than . In that scenario, we might need a fallback to simply select all available unique points (to maximize distinct centers) and then fill the remaining slots with arbitrary duplicates from the input.
33.1-4
Read the paper Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming.
33.2-1
The result follows from the fact that the best expert may make mistakes. Therefore, the number of times they will be removed from the set equals , which also matches the number of times that a set can become empty. Therefore, the total number of mistakes of an algorithm is at most . The +1 correctly accounts for the final operating phase after the last reset.
33.2-2
Here is another way, besides the one described in the hint. Let's create a function and prove that it is always greater than or equal to zero for the interval :
We see that . If the first derivative is non-negative on the whole interval, then the function never drops below zero. Thus,
Because the numerator is non-negative and the denominator is strictly positive, the derivative everywhere in the interval . This confirms that
Substitute to get the required inequality.
33.2-3
Let be the set of remaining experts at step , and be the number of experts in that set. Initially, . At any step , suppose an arbitrary number of experts, , make an incorrect prediction. Because the algorithm chooses an expert uniformly at random from the remaining pool , the probability of selecting an incorrect expert (and thus making a mistake) is . After the outcome is learned, the set is updated to remove all experts who made an incorrect prediction. The new size becomes . The expert who always makes the correct prediction will always remain in the set, guaranteeing the final set size .
We can bound the probability of making a mistake at step :
The total expected number of mistakes , by linearity of expectation, is the sum of the probabilities at each step (expected value of an indicator random variable for each step). Applying the bound established above generates a telescoping sum:
By equation (A.17), we have
33.2-4
Wikipedia describes in detail the randomized weighted majority algorithm including the analysis that exactly matches the form required by this exercise.
33.3-1
Let's follow the hint from the book. The proof for one-dimensional case is available at StackExchange for Mathematics. Note that the cited text assumes . The generalization to -dimensional space is a natural extension of this 1D logic. The transition simply swaps scalar multiplication for the inner product and the scalar derivative for the gradient vector. Lemma 33.6 formalizes the global bounding property.
Because a convex function always lies above its tangent hyperplane, this property is the structural reason why any local minimum is guaranteed to be a global minimum. If you find a point where the gradient , the tangent hyperplane is perfectly horizontal, meaning the entire function must sit at or above that value.
33.3-2
The proof is by induction on the number of repeated application of the definition of convexity in inequality (33.18). The base case gives that . The base case follows from inequality (33.18) with .
The inductive step is trivally proven by using and assuming the statement is true for . We have
33.3-3
The proof relies directly on the relationship between the squared Euclidean norm and the inner product, defined as . This gives
33.3-4
The Hessian matrix of a linear function is identically zero, which is a positive semi-definite matrix, confirming convexity.
33.3-5
Let be the loss function as given in equation (3.33). The -the term of the gradient is
We first compute the individual errors for all samples using the current set of weights. Afterward, a double loop can compute all entries of the gradient in time.
33.3-6
Taking the norm of the gradient derived in the previous exercise yields (in vector form):
The second line applies the triangle and the Cauchy-Schwarz inequalities. The conclusion follows from the fact only the weights are regarded as variables.
33.3-7
The partial derivative of the objective function with respect to is
Move each centroid in the opposite direction of its gradient by scaling it with a small positive step size (learning rate) :
With the centroids moved to new coordinates, you need to re-evaluate the closest points (reassign the clusters) and repeat the gradient updates until the centroids stop moving.
Problems
33-1 Newton’s method
a.
b.
We start with the equation (33.4)
Since , we have
Using the iterative formula from part (a), we get
c.
To find the number of iterations required to reach an accuracy of , we must unroll the recurrence relation created by the quadratic convergence bound. We have
Iterating the recurrence gives
We want , thus (assuming )
d.
For the provided function, Newton's method reduces to
It turns out that , which is not a quadratic convergence anymore. Because is a multiple root (the derivative is zero at the root), the assumption required for quadratic convergence is violated. We would need lots of iterations to reach a tolerance of .
The gradient descent update rule is
With , gradient descent will jump precisely to 3 and find the exact minimizer in 1 iteration.
This problem highlights a degenerate case. Because the root and the minimizer are identical, Newton's method for root-finding mathematically behaves exactly like gradient descent with a suboptimal fixed learning rate of , whereas properly tuned gradient descent solves the quadratic problem instantly.
33-2 Hedge
Read section 2.1 of the CS5275 lecture notes. See also Exercise 33.2-4.
33-3 Nonoptimality of Lloyd’s procedure in one dimension
Let with the following set of points . If the initial centroids (randomly picked) are then the procedure would create two clusters and . This is suboptimal, since and is a better solution.
33-4 Stochastic gradient descent
A good overview of this method is available in IBM's article about stochastic gradient descent. It includes a Python based implementation.
Because the index is drawn uniformly at random, the stochastic gradient computed on is an unbiased estimator of the full gradient. When you follow the standard gradient descent analysis (which relies on bounding the distance to the optimum using the gradient norm), you replace the exact gradient with the stochastic gradient. Because the expectations pass linearly through the dot products in the proof, the deterministic upper bound of standard gradient descent holds in expectation for SGD. Thus,
Last updated