Stanford CS229 Machine Learning

The policy gradient estimator is necessary because the dependency on parameters ($ heta$) is complex. The fundamental property that $ abla_{ heta} ext{E}_{ ext{P}_{ heta}}[ abla_{ heta} ext{log } ext{P}_{ heta}(a|s)]$ equals zero shows that without a reward function, there are no preferences to optimize for.

PPO is designed to stabilize RL training by using importance sampling and clipping the objective function. This prevents the new policy ($ heta$) from deviating too far from the old policy ($ heta_{old}$), which helps maintain stable learning.

The LLM generation process is modeled as a Markov Decision Process (MDP). The state ($s_t$) includes the history, and the action ($a_t$) is the next generated token. The reward function is typically applied only at the end of the trajectory based on whether the final answer matches the ground truth.

To train models for complex reasoning, RL can be used to reward the entire trajectory based on the final answer's correctness. This approach bypasses the need for explicit labeling of the internal 'thinking tokens,' focusing only on verifiable outcomes.

RL addresses sequential decision-making where actions have long-term ramifications. It requires balancing the trade-off between exploitation (using current best knowledge) and exploration (gathering information). Learning relies on maximizing a scalar reward signal rather than explicit labels or supervision.

An MDP formally describes an environment using five components: State Set ($S$), Action Set ($A$), Transition Dynamics ($P(s'|s, a)$), Reward Function ($R$), and Discount Factor ($\gamma$). The Markov property ensures that the future state transition depends only on the current state and action, not on history.

The value function $V^{\pi}(s)$ estimates the expected total payoff starting at state $s$ under policy $\pi$. The optimal value, $V^*(s)$, is the maximum possible return. These values are solved recursively using the Bellman equation, which relates the current state's value to the expected discounted future rewards.

The Policy Gradient algorithm optimizes a stochastic policy $\pi_{\theta}(a|s)$ by maximizing the expected return $E[R]$. The gradient is computed using the log-probability trick, allowing the calculation of $\nabla_{\theta} E[R]$ through sampling, even when the dependency on $\theta$ only affects the sampling distribution.

The standard self-attention mechanism has $O(T^2)$ complexity (where T is sequence length). To mitigate this, techniques like Grouped Query Attention (GQA) reduce the number of keys and values used across heads by mapping multiple query groups to a smaller set of shared keys/values. Similarly, Sliding Window Attention limits attention to only recent history, reducing complexity to $O(T imes W)$ where W is the window size.

MoE allows models to have a large total parameter count (e.g., 30B) while keeping the active computation small (e.g., 3B). This is achieved by using a routing module that directs an input vector to only a subset of specialized expert sub-networks, significantly improving compute efficiency.

For downstream tasks (e.g., sentiment analysis), models can be adapted using In-Context Learning (ICL). This involves concatenating task examples and the test input into the prompt sequence without updating model parameters, which is fundamentally different from traditional fine-tuning.

SFT involves collecting data in an instruction/answer pair format and training the model by minimizing the negative log likelihood of predicting the answer ($Y$) given the instruction ($X$). This is a supervised process that updates the model's weights.

LLMs model language distribution by decomposing the joint probability into a product of conditional probabilities: $P(X_t | X_{1...t-1})$. This requires generating tokens sequentially, making the process auto-regressive.

To handle rare or long words efficiently, models use subword tokenization (e.g., BPE), which breaks down text into smaller units (tokens). This allows leveraging common prefixes and suffixes to understand novel words.

The attention mechanism calculates the relevance between all tokens in a sequence using Query ($Q$), Key ($K$), and Value ($V$) vectors via an inner product: $ ext{Softmax}(Q K^T / ext{scale}) V$. The output is a weighted linear combination of $V$ vectors.

To ensure the model only predicts based on previous tokens (required for generation), a masking technique is applied to the attention matrix, setting all future dependencies to $- ext{infinity}$ before applying Softmax.

The standard self-attention mechanism has a computational and memory complexity that scales quadratically with sequence length $T$ (i.e., $O(T^2)$). This is the primary limitation for processing very long contexts.

The training objective is derived from the lower bound on $\log p_ heta(x_0)$, simplifying to minimizing a sum of terms ($\mathcal{L}_{t-1}$) that compares the mean predicted reconstruction ($\mu_{ heta, t}$) with the true process mean ($\mu_{ ilde{t}, t}$). This loss function is used to train the model to predict noise/reconstruct missing information at each time step.

Modern LLMs utilize a paradigm shift involving pre-training on massive unlabelled data and adapting via zero-shot or few-shot learning, reducing the need for collecting extensive downstream labeled datasets. The goal is to build a general foundation that can be adapted to unlimited tasks.

To adapt massive pre-trained models without changing all parameters ($\theta$), LoRA restricts the weight update matrix $\Delta W$ to a low rank ($A B$). This significantly reduces the number of trainable parameters and is critical for memory efficiency, especially when serving multiple users.

These models are generative frameworks that can be applied to images, videos, and robotics actions. They are noted as a superior approach compared to GANs and Variational Autoencoders (VAEs) for image generation.

The forward process is a fixed, known noising process that transforms $X_0$ to noise $X_T$. The reverse process is the learned component, parameterized by $ heta$, which predicts $p_ heta(X_{t-1}|X_t)$—the step-by-step denoising path.

The goal is to maximize the marginal likelihood $ ext{log } p_ heta(X_0)$ by applying the Evidence Lower Bound (ELBO). This involves minimizing the KL divergence between the true posterior $q(X_{t-1}|X_t, X_0)$ and the parameterized model's distribution.

The gradient computation (backward pass) can be viewed as traversing a differentiable circuit. This method allows for efficient calculation because it reuses intermediate results, unlike expanding the function into a traditional mathematical formula.

The fundamental theorem states that if a differentiable circuit of size $N$ computes a real-valued function, its gradient can also be computed in time complexity $O(N)$. This means the forward pass (evaluating loss) and the backward pass (calculating gradients) have similar computational costs.

Backpropagation is an application of the Chain Rule. By knowing the gradient with respect to an intermediate variable ($U$), one can compute the gradient with respect to its input ($Z$) using matrix multiplication involving the Jacobian (or transpose of the Jacobian). This process allows computation to proceed layer by layer.

Test error is decomposed into three components: noise (intrinsic data error), squared bias (how far the average prediction is from the true function, dependent on model class), and variance (how much the prediction jumps around across different training sets). Minimizing test error requires balancing these three sources of error.

Regularization techniques, such as adding an $L_2$ penalty (Ridge Regression), constrain the model weights ($ heta$) to prevent them from becoming too large. This stabilizes the model, significantly reducing variance while accepting a small increase in bias.

The classical Bias-Variance curve suggests that test error must rise after a certain model complexity threshold. However, modern models can exhibit 'Double Descent,' where the test error decreases again in the massively overparameterized regime (i.e., having more parameters than data points).

To prevent information leakage from the test set, techniques like K-fold cross validation are used. For compute efficiency in tuning hyperparameters (e.g., regularization strength $ ho$), algorithms like Hyperband efficiently allocate computational resources to promising model configurations.

Many common distributions (Bernoulli, Gaussian, Multinomial) can be written into a single functional form. This allows for the generalization of model building and analysis across different data types.

The structure of the exponential family ensures that key statistical operations, such as computing the expected value (inference) and performing maximum likelihood estimation (learning), follow a consistent mathematical pattern regardless of the specific distribution used.

The Softmax function is presented as the standard mechanism for multiclass classification, allowing prediction over $K$ discrete values. Mathematically, it fits within the exponential family structure and generalizes logistic regression (the two-class case).

The GLM framework ties the abstract error models to practical supervised learning. The model predicts a distribution over $Y$ given features $X$, and the loss function is derived directly from maximizing the log-likelihood of this distribution.