Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory (A14678W1)

The printed cover dates this paper to 12 June 2015. All three questions are solved below. The zero-dimensional exception in 1(b), the distinction between affine and homogeneous separators in 1(d), and the endpoint convention in the AdaBoost update are made explicit.

The hypothesis class $H$ shatters a set $S$ when it realizes every binary labelling of $S$: for every function $g:S\to \{0,1\}$ there is an $h\in H$ with $h{|}_S=g$. Identifying each classifier with its positive set, this sayswhere $\mathcal{P}(S)$ is the power set. Different labellings may require different members of the hypothesis class.

The VC dimension isIt is infinite if arbitrarily large finite sets are shattered. A hypothesis class has VC dimension zero when it shatters no one-point set; for a nonempty hypothesis class, the empty set is always shattered.

The shattering coefficient, also called the growth function of a hypothesis class, counts the largest number of labellings obtainable on $m$ inputs:When $X$ has at least $m$ points, the same value is obtained by maximizing $|\{h{|}_S:h\in H\}|$ over $m$-point sets $S$. Always ${\Pi }_H(m)\le 2^m$, with equality exactly when some $m$-point set is shattered.

The Sauer-Shelah lemma says that a hypothesis class of finite VC dimension $d$ satisfiesIn particular, for $m\ge d\ge 1$,Here the binomial coefficients count small subsets. One way to obtain the last inequality is to set $t=d/m\le 1$: since $t^j\ge t^d$ for $j\le d$,Thus finite VC dimension replaces the unrestricted exponential number of labellings by a polynomial bound in the sample size.

Fix an $m$-point set $S$. The restriction of an intersection $c_1\cap c_2$ to $S$ is determined by the ordered pair of restrictions $c_1{|}_S,c_2{|}_S$. Some pairs can yield the same intersection, so the growth function of a hypothesis class satisfiesAssume first that $d\ge 1$. If $12d$ points were shattered by $H_2$, the Sauer-Shelah lemma would implyBut $e<3$, so $(12e{)}^2<36^2=1296<4096=2^{12}$. Raising this strict inequality to the positive integer power $d$ gives a contradiction. No $12d$-point set can therefore be shattered; neither can any larger set, since shattering passes to subsets. ConsequentlyThe printed strict inequality needs $d\ge 1$. For example, on a nonempty domain let $H$ contain only the identically zero classifier. Then $\mathrm{VC}(H)=\mathrm{VC}(H_2)=0$, whereas the stated conclusion would require $0<0$. More generally, a nonempty hypothesis class of VC dimension zero has only one distinct labelling function, since two different functions would shatter a point on which they differ. Its self-intersection class also has VC dimension zero.

Choose distinct points $x_1,\dots ,x_{d+2}$ of $S$. The $d+2$ vectors $(x_i,1)$ lie in the $(d+1)$-dimensional vector space ${\mathbb{R}}^{d+1}$, so they are linearly dependent. Hence there are real numbers ${\lambda }_i$, not all zero, such thatThe second equality forces both a positive and a negative coefficient. Put $I_{+}=\{i:{\lambda }_i>0\}$, $I_{-}=\{i:{\lambda }_i<0\}$, andRearranging the first equality givesEach side is a convex combination: the coefficients are positive and sum to one. Thus $z$ belongs to both convex hulls. Place the points with indices in $I_{+}$ in $A$, those with indices in $I_{-}$ in $B$, and assign every zero-coefficient point and every remaining point of $S$ to $A$. Then $A,B$ are nonempty, disjoint, and have union $S$. Adding points cannot shrink a convex hull, soThis proves the intersecting convex hull partition theorem, including when $S$ has more than $d+2$ points or is infinite: only the initial finite collection was needed.

Expanding the squared Euclidean norm givesIn lifted coordinates $(z,t)=\Phi (x)=(x,\Vert x{\Vert }^2)$, this is the closed half-spaceEvery labelling of the original points obtainable by a Euclidean ball is therefore obtainable on their lifted images by an affine linear classifier. The feature map is injective, since it preserves the first $d$ coordinates; distinct original points remain distinct. If the original points are shattered, every labelling of the lifted points is realized, as required.

Here “linear separator” means a separator with an intercept, namely an affine hyperplane. If a convention demands strict separation on the finite sample, increase the constant term of the positive score $r^2-\Vert c{\Vert }^2+2c\cdot z-t$ by a sufficiently small positive amount. Positive points then have strictly positive score, and the finitely many negative scores remain strictly negative. A homogeneous separator can alternatively be obtained after adjoining one more constant coordinate; this distinction matters for dimension counts.

For $d\ge 1$, take the $d+1$ vertices $v_0,\dots ,v_d$ of a regular simplex in ${\mathbb{R}}^d$, centered at zero and scaled so that $\Vert v_j\Vert =1$. For example, realize them asin the $d$-dimensional vector subspace $\{z\in {\mathbb{R}}^{d+1}:{\sum }_j{z}_j=0\}$, identified isometrically with ${\mathbb{R}}^d$. These vertices are affinely independent.

Assign arbitrary desired signs $s_j\in \{-1,1\}$, positive for inclusion. Affine independence implies that there is an affine function $\ell (x)=a\cdot x+b$ with $\ell (v_j)=s_j$ for every $j$: the $d+1$ interpolation conditions form an invertible linear system. For a sufficiently small $\eta >0$, chooseAt every vertex,Thus the Euclidean ball contains exactly the positively labelled vertices, with none on its boundary. This construction also covers the all-positive and all-negative labellings. Therefore

An affine linear classifier in ${\mathbb{R}}^k$ has VC dimension $k+1$. The upper bound follows from the intersecting convex hull partition theorem: for any $k+2$ points, label the two parts oppositely. The two convex hulls cannot be strictly separated by an affine hyperplane, since they intersect. A weak boundary convention gives the same contradiction: an affine score is nonnegative on the positive convex hull and strictly negative on the negative convex hull. The lower bound comes from the $k+1$ affinely independent vertices of a simplex, because an affine score can interpolate arbitrary signs there.

Consequently, parts (i) and (ii) immediately giveThe one-sided orientation of the lifted separators permits the sharper, exact conclusionTo prove the remaining upper bound, take any $d+2$ distinct points and a nonzero affine dependence ${\lambda }_i$ as in part (c). Write $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2$. Reverse every coefficient if necessary so that $Q\ge 0$. Prescribe positive labels when ${\lambda }_i>0$ and negative labels when ${\lambda }_i<0$; zero coefficients may be labelled arbitrarily. If a Euclidean ball realized these labels, its score $g(x)=r^2-\Vert x-c{\Vert }^2$ would satisfyIndeed, every positive-coefficient term is nonnegative and every negative-coefficient term is strictly positive, with at least one of the latter. On the other hand, expanding the score and using the two affine dependence identities givesa contradiction. No $d+2$ points are shattered, completing the exact determination of the VC dimension of Euclidean balls. In the exceptional zero-dimensional Euclidean space, every positive-radius Euclidean ball is the whole singleton space, so the VC dimension is zero.

Take labels $y_i\in \{-1,1\}$ and fix the standard normalization in which the squared weight penalty has coefficient $1/2$. The squared-slack support vector machine, a form of soft-margin support vector machine, has primal problemThe slack variables of a support vector machine permit margin violations. Penalizing $\Vert w{\Vert }^2$ favors a wide support-vector-machine margin, while $C>0$ sets the cost of the violations. The intercept $b$ is unpenalized, and the resulting classifier is $h(x)=\mathrm{sign}(w\cdot x+b)$, with a fixed choice at zero. The square on ${\xi }_i$ is essential to the Lagrangian dual problem below.

Use Lagrange multipliers ${\alpha }_i\ge 0$ for $1-{\xi }_i-y_i(w\cdot x_i+b)\le 0$ and ${\mu }_i\ge 0$ for $-{\xi }_i\le 0$. The optimization Lagrangian isThe Lagrange dual function is the infimum over the now unconstrained primal variables. The first-order optimality conditions in $w$ and $b$ giveIf the latter equality fails, the infimum over $b$ is $-\infty$. The first-order optimality condition in ${\xi }_i$ givesSubstitution, or completing the square separately in $w$ and each ${\xi }_i$, producesprovided ${\sum }_i{\alpha }_i{y}_i=0$. For fixed nonnegative ${\alpha }_i$, this expression is maximized over ${\mu }_i\ge 0$ at ${\mu }_i=0$. Thus the simplest Lagrangian dual problem isIn particular, there is no upper box constraint ${\alpha }_i\le C$. That constraint belongs to the linear-slack penalty; squared slack instead contributes the displayed diagonal quadratic penalty. With $Y=\mathrm{diag}(y_1,\dots ,y_m)$ and Gram matrix $G_{ij}=x_i\cdot x_j$, the objective can also be writtenSince $G$ is positive semidefinite and $C>0$, the matrix in parentheses is positive-definite. The objective of the Lagrangian dual problem is therefore strictly concave, and the feasible maximizer is unique.

The primal problem is a convex optimization problem, and $w=0,b=0,{\xi }_i=2$ is strictly feasible for both families of inequalities. Slater's condition gives strong duality, so an optimum of the Lagrangian dual problem yields a primal optimum. The Karush-Kuhn-Tucker conditions supplyFor any $i$ with ${\alpha }_i>0$, the intercept is consequentlyAll such choices agree at an exact optimum. If all labels have one sign, the optimal coefficients can all be zero: choose $w=0$, $\xi =0$, and any constant intercept of that sign with magnitude at least one.

A real positive-semidefinite kernel on an input set $X$ is a function $K:X\times X\to \mathbb{R}$ for which there is an inner product space $\mathcal{F}$ and a feature map $\varphi :X\to \mathcal{F}$ satisfyingEquivalently, $K$ is symmetric and every finite Gram matrix $(K(x_i,x_j){)}_{i,j}$ is positive semidefinite: ${\sum }_{i,j}{a}_i{a}_{j}K(x_i,x_j)\ge 0$ for all real coefficients $a_i$. An infinite-dimensional Hilbert space is allowed.

Replace every inner product $x_i\cdot x_j$ in part (b) by $K(x_i,x_j)$ and solveThis is precisely the Lagrangian dual problem obtained by replacing each original input by $\varphi (x_i)$ in the primal problem. The weight vector it determines isand the intercept follows from the same Karush-Kuhn-Tucker conditions. For example, if ${\alpha }_i>0$,Thus training needs only the finite Gram matrix, even if the feature map has infinitely many coordinates. This is the kernel trick. The result is an affine linear classifier in the feature space; its boundary in the original input space can be nonlinear. The squared-slack diagonal term and the equality constraint remain unchanged.

An embedding is determined by its chosen increasing sequence of positions. Accordingly, the all-subsequence embedding kernel $K(x,y)$ counts pairs of embeddings, one in $x$ and one in $y$, that spell the same subsequence. The two embeddings are distinguished even when they spell the same word as another pair. The empty word contributes exactly one pair.

Let $n=|x|$, $p=|y|$, and define $F(i,j)=K(x_1\cdots x_i,y_1\cdots y_j)$ for prefixes. When either prefix is empty, only the empty word has an embedding in both, soTo derive a dynamic programming recurrence, count pairs that do not use position $i$ of $x$ or do not use position $j$ of $y$. Inclusion-exclusion givesThe remaining pairs use both final positions. These positions must be the final letters of the common word, so they contribute nothing if $x_i\ne y_j$. If $x_i=y_j$, deleting those two final positions is a bijection to arbitrary embedding pairs on the two shorter prefixes, including their empty pair. Their contribution is therefore $F(i-1,j-1)$. HenceEquivalently, when the final symbols agree the recurrence simplifies to $F(i,j)=F(i-1,j)+F(i,j-1)$; when they differ, subtract the diagonal term. Fill the table in increasing prefix order and return $F(n,p)$. The boundary values and the disjoint counting argument prove correctness by induction on $i+j$.

A one-row implementation of this dynamic programming uses the saved old diagonal entry:The assignment to diagonal retains the value from the previous row before F[j] was overwritten. Swapping $x$ and $y$ if necessary minimizes the row length. Thus the time complexity is $O(|x||y|)$ arithmetic operations and the extra space complexity is $O(\min (|x|,|y|))$ integer cells. Empty inputs return one immediately.

These counts include multiplicity: for $x=y=aa$, the empty word contributes $1$, the word $a$ contributes $2\cdot 2=4$, and $aa$ contributes $1$, giving $K(aa,aa)=6$, not three. More generally, each result is at most $2^{n+p}$, since it counts some pairs of position subsets. Exact integers therefore require $O(n+p)$ bits; the stated quadratic bound is an arithmetic-operation bound, with a conservative $O(np(n+p))$ bound for elementary bit arithmetic.

The proposed positive-semidefinite kernel is valid: for each finite string only finitely many coordinates ${\varphi }_u(x)$ are nonzero, so $x\mapsto ({\varphi }_u(x){)}_{u\in {\Delta }^{\ast }}$ is a well-defined feature map into the inner product space of finitely supported coordinate families, and its inner product is exactly $K$.

The two-interval approximation by one interval supplies an approximation guarantee for every input probability distribution $D$. Merge overlapping target intervals, and write the target positive set as at most two disjoint ordered intervals $I_1,I_2$. Put $p_j=D(I_j)$ and $p=p_1+p_2$. If there is only one nonempty component, the target already belongs to the interval hypothesis class and has zero misclassification risk. If the interval notation permits empty intervals and the target is empty, choose that same empty interval in $H$.

In the two-component case, choosing the heavier component as the hypothesis loses only the lighter component, so its misclassification risk isAlternatively, choose the single interval $J$ spanning both components. This produces no false negatives, and its false positives lie in the gap. Its misclassification risk is at most $1-p$. Both candidates are in $H$, so there exists an interval $h^{\ast }$ withFor the last step, use $p/2\le 1/3$ if $p\le 2/3$, and $1-p\le 1/3$ if $p\ge 2/3$. This avoids any assumption that an empty interval or the whole real line belongs to $H$.

Use empirical risk minimization over intervals on independent labelled examples. The generalization result needed here is the VC uniform convergence theorem: for a binary hypothesis class of finite VC dimension $v$, there is a universal constant $A$ such that, for any labelled-data probability distribution and $0<\eta ,\delta <1$, a sample sizeensures, with probability at least $1-\delta$, that every hypothesis's empirical misclassification risk differs from its misclassification risk by at most $\eta$. This theorem does not require the labels to be realizable by the hypothesis class.^[ref]

The interval hypothesis class has VC dimension two: any two ordered points can receive all four labellings, whereas an interval cannot label three ordered points $1,0,1$. Take $\eta =1/24$ and choose an interval $\hat{h}$ minimizing the empirical misclassification risk. On the simultaneous convergence event,ThereforeSince $v$ and $\eta$ are fixed constants, $O(1+\log (1/\delta ))$ examples suffice, which is polynomial in $1/\delta$ as required by the paper's definition of weak PAC learning.

For completeness, empirical risk minimization over intervals is computationally effective. Sort the sample and group equal coordinates, since one interval cannot split identical inputs. Give each group weight equal to the number of positive labels minus the number of negative labels in that group. The number of empirical mistakes made by an interval is the total number of positives minus the total weight of the consecutive groups it contains. Select the consecutive block of maximum weight, or select a finite interval outside the sample if every nonempty block has negative weight. This enumerates all possible sample labellings by intervals and attains the minimum empirical misclassification risk; sorting and a maximum-block scan are sufficient. The time complexity is $O(m\log m)$.

Use weighted decision stump optimization with the convention $\mathrm{sign}(0)=+1$, and write $w_j=D((x_j,y_j))$. For each coordinate $i$, sort the examples by their $i$th coordinate and group all equal coordinate values. For a threshold between the $k$th and $(k+1)$st distinct values, the decision stump predicts $-1$ on the left and $+1$ on the right. Its weighted misclassification risk isStart with a threshold below the minimum observed value. Every prediction is then $+1$, and the initial error is ${\sum }_{y_j=-1}{w}_j$. Sweep the threshold from left to right. When it passes an entire group $G$ of equal coordinate values, that group's prediction changes from $+1$ to $-1$, so updateRecord the smallest value and a threshold achieving it, including the final threshold above all observations, which predicts $-1$ everywhere on the sample. Representatives can be chosen strictly between successive distinct values; the two outer representatives are finite real numbers below the minimum and above the maximum.

Every threshold has exactly the same sample predictions as one of these representatives. In particular, if a threshold equals an observed value, the equality group is on the $+1$ side under the chosen sign function convention, which duplicates the representative immediately before that group. Thus the sweep includes every possible sample labelling by the stated decision stump. Repeating for all $n$ coordinates and returning the globally smallest error proves optimality.

Sorting costs $O(m\log m)$ per coordinate and the grouped sweep costs $O(m)$. The overall time complexity iswith $O(m)$ working storage when coordinates are processed one at a time. Pre-sorted coordinate orders can be reused across repeated AdaBoost rounds, leaving $O(nm)$ work per round for changing weights. The paper allows only the orientation $\mathrm{sign}(x_i-b)$; reversing its polarity would enlarge the hypothesis class and is unnecessary here.

Write $\epsilon ={\epsilon }_t$, $\alpha ={\alpha }_t$, and $s_i=y_i{h}_t(x_i)\in \{-1,1\}$. Correctly classified observations have $s_i=1$ and total $D_t$-weight $1-\epsilon$; incorrectly classified observations have $s_i=-1$ and total weight $\epsilon$. The normalizing constant in the AdaBoost update is thereforeFor $0<\epsilon <1$, the definition of $\alpha$ givesIf observation $i$ is correct, its multiplier in the normalized update isif it is incorrect, the multiplier isThe corresponding denominators are exactly $1+s_i(1-2\epsilon )$: they are $2(1-\epsilon )$ when $s_i=1$ and $2\epsilon$ when $s_i=-1$. ConsequentlyAs a check, the new total mass on correctly classified observations is $(1-\epsilon )/(2(1-\epsilon ))=1/2$, and the mass on incorrectly classified observations is $\epsilon /(2\epsilon )=1/2$. The update thus produces a probability distribution and assigns the two groups equal aggregate mass. When $\epsilon =1/2$, $\alpha =0$ and every individual weight is unchanged.

The displayed finite update assumes $0<{\epsilon }_t<1$. The usual weak learner guarantees ${\epsilon }_t<1/2$, but it can return a perfect classifier with ${\epsilon }_t=0$; then the logarithm is infinite and the normalized exponential formula is not defined. AdaBoost stops on that perfect hypothesis rather than executing this update. Similarly, the printed formula is not an ordinary finite update at ${\epsilon }_t=1$.