Big Data & Machine Learning

A single classifier is almost always worse than the collective: different models make different mistakes, and their combination reduces the total error. Ensemble methods are the foundation of winning solutions in machine learning on real-world data.

The error of any algorithm can be decomposed: Err = Bias² + Variance + Irreducible noise. Bias is the systematic error due to incorrect model assumptions: an overly simple model "misses" the correct answer even with infinite data. Variance is the sensitivity of the model to random fluctuations in...

The intuition: a shooter with high bias aims away from the target; a shooter with high variance is accurate but inconsistent. We want neither.

Bagging (Bootstrap Aggregation, Breiman, 1994): train B models on B bootstrap samples (each is a random sample with replacement from the original n objects), then average the predictions. For regression: $\hat{F} = (1/B)\sum F_b(x)$. For classification—majority vote.

Formulas

Reinforcement learning is a paradigm in which an agent learns to act in an environment by receiving reward signals for its decisions. Unlike supervised learning, there are no correct answers: the agent must discover the optimal strategy by interacting with the environment. It is RL that enabled c...

Agent’s goal: to find a policy π(a|s) (probability of action a in state s), maximizing the discounted sum of rewards: max E[Σₜ γᵗrₜ].

State value function: V^π(s) = E_π[Σₜ γᵗrₜ | s₀ = s] — expected sum of rewards starting from s and following policy π.

Q-function (action-value function): Q^π(s,a) = E_π[Σₜ γᵗrₜ | s₀=s, a₀=a] — value of taking action a in state s. Knowing Q*, the optimal policy is trivial: π*(s) = argmax_a Q*(s,a).

Developing an ML pipeline is a sequence of complex choices: algorithm, preprocessing, hyperparameters, architecture. Each choice requires expertise and hundreds of experiments. AutoML automates these choices, making machine learning accessible to non-experts and accelerating experts' workflows.

Hyperparameters (learning rate, tree depth, hidden layer size) are not learned via backpropagation—they must be searched for using an external method. The task: find a configuration $\lambda \in \Lambda$ that minimizes the validation error: $\lambda^* = \arg\min_{\lambda\in\Lambda} L_{val}(f_{\la...

The problem: computing $L_{val}(f_\lambda)$ = “run full training” — is expensive! The space $\Lambda$ can be combinatorially large (conditional — if kernel='rbf', kernel parameters appear).

Random search (Bergstra & Bengio, 2012): better than grid search in high-dimensional spaces: if only 2 out of 10 hyperparameters matter, a 10¹⁰ grid wastes resources on insignificant axes. Random search explores all axes uniformly.

Why do neural networks work? What class of functions can they approximate? Why is depth needed—can you make do with just one wide layer? Approximation theory answers these questions mathematically rigorously, substantiating the practical success of deep learning.

Classic theorem (Cybenko, 1989; Hornik, Stinchcombe, White, 1989): A single-layer neural network with sigmoidal neurons, a sufficient number of hidden neurons, and any nonconstant sigmoidal activation function can approximate any continuous function $f: [0,1]^n \to \mathbb{R}$ to any precision $\...

Formally: for any $\epsilon > 0$, there exists $N$ and parameters $\{\alpha_j, w_j, b_j\}$ such that

$ \sup_{x \in [0,1]^n} |f(x) - \sum_j \alpha_j \sigma(w_j^\mathrm{T} x + b_j)| < \epsilon $

Training a neural network is solving the optimization problem $\min_\theta L(\theta)$ in a space with billions of variables. The landscape of the loss function $L(\theta)$ is complex: saddle points, flat plateaus, ravines. Understanding optimization methods is the key to successful training of de...

The full gradient $\nabla L(\theta) = (1/n)\Sigma_i \nabla l_i(\theta)$ is expensive when $n =$ millions. Stochastic approximation: take a mini-batch $B \subset \{1, ..., n\}$ and approximate: $\hat{g}_t = (1/|B|)\sum_{i \in B} \nabla l_i(\theta_t)$. Update: $\theta_{t+1} = \theta_t - \alpha_t \h...

Key property: $\mathbb{E}[\hat{g}_t] = \nabla L(\theta_t)$ — unbiased estimator. Variance $\mathrm{Var}[\hat{g}_t] = \sigma^2/|B|$ decreases with batch size.

Convergence theorem (convex case): With decreasing lr $\alpha_t = O(1/\sqrt{t})$ and $L$-smooth convex function: $\mathbb{E}[L(\theta_T)] - L(\theta^*) \leq O(1/\sqrt{T})$. For $\mu$-strongly convex with $\alpha_t = O(1/t)$: $O(\sigma^2/(\mu T))$.

The Transformer (Vaswani et al., "Attention Is All You Need", 2017) is a revolutionary architecture that eliminated recurrence in sequence processing. The self-attention mechanism allows each element of the sequence to interact with any other in a single step, opening the way to scaling models up...

The key operation of the transformer. Three matrices: Q (queries) ∈ ℝ^{n×d_k}, K (keys) ∈ ℝ^{n×d_k}, V (values) ∈ ℝ^{n×d_v}.

For a single token "The cat sat": the query "sat" looks at the keys "The"(0.1), "cat"(0.8), "sat"(0.1) — the attention mechanism found that "sat" → cat.

A single attention mechanism sees only one type of interaction. Multi-head Attention uses h parallel "heads" with different projections:

Most of our geometric intuitions were formed in 2D and 3D. But data about people, texts, molecules live in spaces of dimension $d = 100, 1000, 100000$. In these spaces everything works differently, and understanding the “curse of dimensionality” is crucial for the ML practitioner.

Volume of the “shell”: In $\mathbb{R}^{d}$ the volume of the ball $B^d(r) = \pi^{d/2} r^d/\Gamma(d/2+1)$. As $d \to \infty$ almost all the volume of the ball is concentrated in a thin layer near the surface. More precisely: for $X \sim \text{Uniform}(B^d)$, $E[\|X\|] \approx r \cdot \sqrt{d/(d+2)...

Practical implication: all random points in the ball are located approximately at the same distance from the center $\to$ distance from the center is not a distinguishing feature.

Random vectors are almost orthogonal: For $X, Y \sim N(0, I^d/d)$: $\cos(\angle XY) = X^{\top} Y/(\|X\| \|Y\|) \to N(0, 1/d)$. For $d = 1000$ the standard deviation of the angle is $\approx 1/\sqrt{1000} \approx 0.03$ radians $\approx 1.8^{\circ}$. Almost all random vectors are nearly orthogonal ...

Formulas

Imagine: you want to record an MRI image, but the patient has little time—you cannot obtain all the measurements. Or you need to transmit a signal through a channel with limited bandwidth. The theory of compressed sensing (Candès, Romberg, Tao; Donoho, 2006) says: if the signal is “sparse”, sever...

Problem Statement: $x \in \mathbb{R}^n$ — signal (for example, an image of pixels). $A \in \mathbb{R}^{m \times n}$, $m \ll n$ — measurement matrix. We observe $y = Ax$ ($m \ll n$ measurements — obviously an underdetermined system). Goal: recover $x$.

Sparsity Condition: $x$ has no more than $s$ non-zero components: $||x||_0 = s \ll n$. Most signals are sparse in some basis: images — in the wavelet basis, audio — in the Fourier basis.

$(1-\delta)||x||_2^2 \leq ||Ax||_2^2 \leq (1+\delta)||x||_2^2 \quad \text{for all } s\text{-sparse } x$

Discriminative models answer the question “which class?”. Generative models answer “what does it look like?”. They learn the data distribution representation and can create new samples—images, molecules, music. Three families have defined modern AIGC: VAE, GAN, and diffusion models.

Problem statement: Given x (an image). We want to train a generative model $p_\theta(x) = \int p_\theta(x|z) p(z) dz$, where $z$ is a latent code (hidden factors). The integral over all $z$ is not analytic.

Variational inference (ELBO): we introduce an encoder $q_\phi(z|x) \approx p(z|x)$ and maximize the evidence lower bound (ELBO):

$\log p_\theta(x) \geq \mathbb{E}_{q_\phi(z|x)}[\log p_\theta(x|z)] - KL(q_\phi(z|x) \Vert p(z)) = \mathcal{L}(\theta, \phi; x)$

Formulas

Many ML problems have a convex structure: linear regression, logistic regression, SVM, LASSO, Ridge, support vector machines. Such problems guarantee a global optimum, and there is a rich theory of efficient algorithms. Knowledge of convex optimization is fundamental to understanding “why” ML mod...

Definition of convexity: A function f: ℝⁿ → ℝ is convex if for all x, y ∈ dom(f) and α ∈ [0,1]:

Geometrically: the chord between any two points lies above the graph. Consequence: local minimum = global minimum.

L-smoothness: f is twice differentiable with ||∇²f(x)|| ≤ L (the largest eigenvalue of the Hessian is bounded). Equivalently: ||∇f(x) − ∇f(y)|| ≤ L||x−y|| — the gradient does not change too rapidly. Consequence (descent lemma):

Formulas

Modern neural networks are trained on billions of examples and have billions of parameters. Computing the exact gradient is impossible — stochastic methods are required. Understanding their theoretical properties allows us to tune training and diagnose problems.

Problem statement: min_θ f(θ) = (1/n) Σᵢ fᵢ(θ). Stochastic gradient: gₜ = ∇fᵢₜ(θₜ), where iₜ is chosen at random. Key properties: E[gₜ] = ∇f(θₜ) (unbiasedness), Var[gₜ] = σ² (finite variance).

Mini-batch: gₜ = (1/|B|)Σᵢ∈Bₜ ∇fᵢ(θₜ). Variance decreases: Var[gₜ] = σ²/|B|. Linear acceleration up to the critical batch size B_crit ≈ σ²/||∇f||² — beyond this, parallelism helps only in terms of time, not iterations.

mₜ = β₁ mₜ₋₁ + (1−β₁) gₜ (smoothed mean of gradient) vₜ = β₂ vₜ₋₁ + (1−β₂) gₜ² (smoothed mean of squared gradient) m̂ₜ = mₜ/(1−β₁ᵗ), v̂ₜ = vₜ/(1−β₂ᵗ) (bias correction) θₜ₊₁ = θₜ − α · m̂ₜ/(√v̂ₜ + ε)

Formulas

A neural network predicts cancer from an MRI scan. The doctor asks: "Why?" A bank denies a loan. The client demands an explanation. A regulator audits the model. Interpretability is not an academic toy, but a legal and ethical requirement. The GDPR in the EU guarantees the “right to explanation” ...

Global: to understand how the model works as a whole — which features are important for all predictions. Example: feature importance in a random forest — average MDI across all trees.

Local: to explain a specific prediction — why the model made this decision for this particular object. Critical in high-stakes applications (medicine, lending, justice).

Shapley values (from game theory): The contribution of feature $i$ in the “coalition game” $f$:

Formulas

Matrix of data: 10 million users × 100 thousand products. Full SVD is impossible: O(mn·min(m,n)) ≈ 10¹⁷ operations. Randomized algorithms reduce complexity to O(mnk) with theoretical guarantees of closeness to the exact solution. This is not "approximation due to laziness"—this is mathematically ...

Task: Compute the best rank-k approximation of matrix $A \in \mathbb{R}^{m \times n}$: $\min_{\mathrm{rank}(B) \leq k} \|A - B\|_F$.

Exact algorithm: SVD $A = U\Sigma V^\top$, $A_k = U_{1:k}\Sigma_{1:k}V^\top_{1:k}$. Complexity O(mn²).

Step 1. Random matrix $\Omega \in \mathbb{R}^{n \times k}$: $\Omega_{ij} \sim N(0, 1/k)$. Sketch $Y = A\Omega \in \mathbb{R}^{m \times k}$. Meaning: $Y$ approximates the "column space" of $A$—we project $A$ onto $k$ random directions.

Formulas

A single computer with 512 GB RAM and a fast SSD is powerful, but modern companies’ data amounts to petabytes. Distributed computing systems allow this data to be processed on clusters of thousands of machines. Understanding these systems is critical for an ML engineer working with real-world data.

Idea (Dean & Ghemawat, Google, 2004): break the computation into two stages, each of which is parallelized by data.

Map(k, v) → list of (k', v'): applied independently to each record. Example: word count — Map("hello world", 1) → [("hello",1), ("world",1)].

Shuffle: the system automatically groups all pairs (k',v') by key k'. The most expensive step is data movement over the network.

GPT-4, Claude, Gemini — large language models (LLMs) revolutionized AI in 2020–2024. To apply and further develop these models effectively, it is necessary to understand their architecture, training process, and adaptation methods.

Autoregressive language modeling: $P(x_1,\ldots,x_n) = \prod_i P(x_i|x_1,\ldots,x_{i-1})$. Loss during pretraining: $L_{LM} = -\frac{1}{n} \sum_i \log P(x_i|x_1,\ldots,x_{i-1};\theta)$. The "next token" is a simple task that forces the model to understand semantics, syntax, factuality, and causal...

Tokenization: Byte-Pair Encoding (BPE) — iteratively merges the most frequent pairs of bytes. Vocabulary 32K–256K tokens. "Moscow" → [“Mos”, “cow”] or as a single token.

Data: Common Crawl (filtered internet), Books, Wikipedia, GitHub, arXiv, StackExchange. Trackers: The Pile (800GB, EleutherAI), RedPajama, Dolma. The quality of filtering is critical: careless filtering → degradation.