Problem A.1 (qiuzhen-qualify 2025-spring)
Section: Machine Learning Theory

Let $\mathcal{H}$ be a class of binary classifiers over a domain $\mathcal{X}$. Let $D$ be an unknown distribution over $\mathcal{X}$, and let $f$ be the target hypothesis in $\mathcal{H}$. Fix some $h \in \mathcal{H}$. Show that the variance of the empirical loss $L_S(h)$, over all possible samples $S$ of size $m$ drawn from $D$, is inversely proportional to $m$. That is, show the following relationship:

$$\operatorname{Var}_{S\sim D^m}\big[L_S(h)\big] \propto \frac{1}{m}.$$

More specifically, prove the exact expression:

$$\operatorname{Var}_{S\sim D^m}\big[L_S(h)\big] = \frac{L_{D,f}(h)\,\big(1 - L_{D,f}(h)\big)}{m}.$$

Problem A.2 (qiuzhen-qualify 2025-spring)
Section: Machine Learning Theory

Let $\mathcal{X}$ be a domain, and let $D_1, D_2, \ldots, D_m$ be a sequence of distributions over $\mathcal{X}$. Let $\mathcal{H}$ be a finite class of binary classifiers over $\mathcal{X}$, and let $f \in \mathcal{H}$. Suppose we obtain a sample $S = \{(x_1, y_1), \ldots, (x_m, y_m)\}$, where the $i$-th instance $x_i$ is sampled from $D_i$, and $y_i = f(x_i)$. Let $\bar{D}_m$ denote the average as:

$$\bar{D}_m = \frac{D_1 + \cdots + D_m}{m}.$$

Fix an accuracy parameter $\varepsilon = \tfrac{1}{4}$. Show that

$$\mathbb{P}\big[\exists\, h \in \mathcal{H} \text{ s.t. } L_{\bar{D}_m,f}(h) > \varepsilon \text{ and } L_{S,f}(h) = 0\big] \le |\mathcal{H}| e^{-m}.$$

Hint: $\ln\!\left(\tfrac{3}{8}\right) < -\tfrac{1}{4}.$

Problem A.3 (qiuzhen-qualify 2025-spring)
Section: Machine Learning Theory

Let $H$ and $H'$ be two families of functions mapping from $X$ to $\{0,1\}$ with finite VC dimensions.

(a) Show that

$$\operatorname{VCdim}(H \cup H') \le \operatorname{VCdim}(H) + \operatorname{VCdim}(H') + 1.$$

(b) Use this to determine the VC dimension of the hypothesis set formed by the union of axis-aligned rectangles and triangles in dimension 2. You may use the fact that the VC dimension of the hypothesis set formed by the union of triangles in dimension 2 is 7, without any proof.

Problem A.4 (qiuzhen-qualify 2025-spring)
Section: Machine Learning Theory

Prove the following two statements:

(a) Let $D$ be a distribution. Let $S = (z_1, \ldots, z_m)$ be an i.i.d. sequence of examples. Let $A$ be a learning algorithm that is on-average replace-one stable with rate $\varepsilon(m)$. Then:

$$\mathbb{E}_{S\sim D^m}\big[ L_D(A(S)) - L_S(A(S)) \big] \le \varepsilon(m).$$

(b) Let $\ell$ be a convex $\rho$-Lipschitz loss function. The regularised Empirical Risk Minimisation (ERM) satisfies:

$$\mathbb{E}_S\big[L_D(A(S))\big] \le L_D(w^*) + \lambda\,\|w^*\|^2 + \frac{2\rho^2}{\lambda m},$$

where

$$w^* \equiv \arg\min_{w\in\mathcal{H}} L_D(w).$$

Problem B.1 (qiuzhen-qualify 2025-spring)
Section: Deep Learning and Reinforcement Learning

Consider a classification problem: the training dataset is given as $\{(x_i, y_i)\}_{i=1}^N$, where $x_i \in \mathbb{R}^d$ represents the input features, and $y_i \in \{1,2,\ldots,C\}$ represents the class labels. A supervised deep learning pipeline typically includes preparing training data, defining a hypothesis space, designing a training scheme, and optimizing the network. Answer the following questions:

(a) Define the hypothesis space consisting of all neural networks structured with

• a feature extractor: a multi-layer perceptron (MLP) that maps the inputs to a learned feature representation,

• a classifier: a multi-layer perceptron (MLP) that maps the feature representation to class probabilities.

Please specify the input, output and the parameters for training.

(b) Specify an appropriate loss function for this classification problem and explain how stochastic gradient descent (SGD) is used to optimize the neural network.

(c) To stabilize training, batch normalization is often applied. Describe how batch normalization works during the training and testing phase.

Problem 1(d) (qiuzhen-qualify 2025-spring)

If the training error is unsatisfactory, describe what adjustments you can make to improve the expressivity of the neural network. Discuss at least two approaches.

Problem 1(e) (qiuzhen-qualify 2025-spring)

If the training error is low but the testing error is high, propose strategies to reduce overfitting. Discuss at least two approaches.

Problem 2(a) (qiuzhen-qualify 2025-spring)

Generative models aim to train a neural network generator to produce samples similar to the training data. The forward process of a diffusion model progressively adds noise to the data, transforming the data distribution into a normal distribution. The reverse process gradually denoises the data, reverting the normal distribution back to the data distribution. In score-based diffusion models, the forward process can be represented as a Stochastic Differential Equation (SDE). Consider the Variance Preserving (VP) SDE:

$$dx = -\frac{1}{2}\beta(t)\,x\,dt + \sqrt{\beta(t)}\,d\mathbf{W}_t,$$

where $\mathbf{W}_t$ is a standard Wiener process, and $\beta(t)$ is a time-dependent noise schedule.

Write down the reverse-time SDE corresponding to the forward process and explain why training the diffusion model requires score matching as follows:

$$\min_{\theta} \mathbb{E}_{\lambda(t)}\,\mathbb{E}_{\mathbf{x}_t\mid \mathbf{x}_0} \big\| s_{\theta}(\mathbf{x}_t, t) - \nabla_{\mathbf{x}_t} \log p_t(\mathbf{x}_t) \big\|_2^2,$$

where $\lambda(t)$ is a weighting function, $s_{\theta}(\mathbf{x}_t, t)$ is the neural network to train and $p_t$ is the marginal distribution of $\mathbf{x}_t$.

Problem 2(b) (qiuzhen-qualify 2025-spring)

Prove that

$$\mathbb{E}_{\mathbf{x}_t\mid \theta} \big\| \nabla_{\mathbf{x}_t} \log p_t(\mathbf{x}_t) \big\|_2^2 \equiv \mathbb{E}_{(\mathbf{x}_0,\mathbf{x}_t)\mid \theta} \big\| s_{\theta}(\mathbf{x}_t, t) - \nabla_{\mathbf{x}_t} \log p_{t\mid 0}(\mathbf{x}_t\mid \mathbf{x}_0) \big\|_2^2 + C,$$

where $C$ is a constant, $p_t(\mathbf{x}_t)$ is the marginal distribution of $\mathbf{x}_t$, and $p_{t\mid 0}(\mathbf{x}_t\mid \mathbf{x}_0)$ is the conditional distribution of $\mathbf{x}_t$ given the original data $\mathbf{x}_0$.

Problem 2(c) (qiuzhen-qualify 2025-spring)

For the given VP SDE, what is the conditional distribution $p_{t\mid 0}(\mathbf{x}_t\mid \mathbf{x}_0)$? Based on this, derive the final denoising score-matching loss function for training score-based diffusion models.

Problem C-1 (qiuzhen-qualify 2025-spring)
Section: Optimization Methods in Artificial Intelligence

L-Smoothness and $\mu$-Strong Convexity: Provide the definitions of $L$-smoothness and $\mu$-strong convexity, respectively.

Problem C-2 (qiuzhen-qualify 2025-spring)
Section: Optimization Methods in Artificial Intelligence

Combining Smoothness and Strong Convexity: Suppose that $f(x)$ is continuously differentiable $L$-smooth and $\mu$-convex.
- Show that $g(x) = f(x) - \frac{\mu}{2}\|x\|^2$ is continuously differentiable, convex and $(L - \mu)$-smooth.
- Using the fact

$$\frac{1}{L - \mu}\big\|\nabla g(x) - \nabla g(y)\big\|^2 \le \langle \nabla g(x) - \nabla g(y),\, x - y \rangle,$$

show that

$$\mu\|x - y\|^2 + \frac{1}{L}\big\|\nabla f(x) - \nabla f(y)\big\|^2 \le \left(1 + \frac{\mu}{L}\right) \langle \nabla f(x) - \nabla f(y),\, x - y \rangle.$$

Problem C-3 (qiuzhen-qualify 2025-spring)
Section: Optimization Methods in Artificial Intelligence

Recurrence Relation: Using the non-expansiveness property of prox and the optimality condition of $\mathrm{prox}_{\gamma R}$, derive the recurrence relation for $\|x^{k+1} - x^*\|^2$:

$$\|x^{k+1} - x^*\|^2 \le \big\|x^{k} - x^* - \gamma\big(\nabla f(x^{k}) - \nabla f(x^*)\big) + \xi^{k}\big\|^2.$$

Problem C-4 (qiuzhen-qualify 2025-spring)
Section: Optimization Methods in Artificial Intelligence

Variance Decomposition: What is variance decomposition? Explain how it is applied to the recurrence relation, and derive:

$$\mathbb{E}_{k}\big[\|x^{k+1} - x^*\|^2\big] \le \big\|x^{k} - x^* - \gamma\big(\nabla f(x^{k}) - \nabla f(x^*)\big)\big\|^2 + \gamma^2\sigma^2,$$

where $\mathbb{E}_{k}[\cdot]$ denotes the conditional expectation given $\xi^{k},\ldots,\xi^{0}$.

Problem C-5 (qiuzhen-qualify 2025-spring)
Section: Optimization Methods in Artificial Intelligence

Simplified Recurrence: Using the tower property, prove that when $\gamma = \tfrac{2}{\mu + L}$, the recurrence simplifies to:

$$\mathbb{E}\big[\|x^{k+1} - x^*\|^2\big] \le (1 - \rho)\,\mathbb{E}\big[\|x^{k} - x^*\|^2\big] + \gamma^2\sigma^2,$$

where $\rho = \dfrac{4\mu L}{(\mu + L)^2}$.

Problem C-6 (qiuzhen-qualify 2025-spring)
Section: Optimization Methods in Artificial Intelligence

Complexity: Prove that for any desired precision $\varepsilon > 0$, there exists a step size $\gamma$ such that

$$k \ge \frac{L/\mu + 3}{4}\,\log\frac{1}{\varepsilon}$$

implies:

$$\mathbb{E}\big[\|x^{k} - x^*\|^2\big] \le \varepsilon\,\|x^{0} - x^*\|^2 + \frac{\gamma^2\sigma^2}{\mu}.$$

Problem 1 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

In a trigram language model, how is $p(w_3 \mid w_1, w_2)$ learned from a training corpus? In real-world applications, we may encounter situations where $(w_1, w_2)$, or even $w_1$ or $w_2$, do not appear in the training corpus. How can we estimate $p(w_3 \mid w_1, w_2)$ in such cases?

Problem 2 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

What is the central idea behind representation learning? Which algorithms implement this concept?

Problem 3 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

Why do current large language models (LLMs) use top-P sampling during inference instead of greedy or beam search? Additionally, why is top-P sampling considered superior to other methods, such as top-K sampling?

Problem 4 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

List several key points that contribute to the success of current LLM based approach of Artificial General Intelligence and explain their importance.

Problem 5 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

Identify at least two advantages of the Transformer architecture compared to recurrent-based models (e.g., LSTM, GRU) for sequence-to-sequence tasks.

Problem 6 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

Explain why the data scaling law, which describes the relationship between performance and sample size, holds true from the perspective of statistical learning. Please provide a detailed analysis process, avoiding overly simplistic assumptions (such as assuming the data follows a Gaussian distribution).

Problem 7 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

We are implementing the Reinforcement Learning with Human Feedback (RLHF) procedure to train a Large Language Model (LLM). Assuming that a reward model has already been trained, explain how reinforcement learning is used to align the model with human preferences. The explanation should include details about data usage, the reinforcement learning loss function, and the gradient of the loss.

Problem 8 (qiuzhen-qualify 2025-spring)
Section: Natural Language Processing

We have a general-purpose Large Language Model (LLM), but it performs poorly on question-answering tasks in a specific problem domain due to a lack of domain-specific knowledge. Although we have collected a large corpus of documents in this domain, we do not have labeled question-answering pairs. Design a system that can accurately answer questions within this domain. You may incorporate additional components, such as embedding models, into the system.