Последовательности, суммы, пределы
Прогрессии
| Арифметическая | Геометрическая | |
|---|---|---|
| Правило | $a_{n} = a_1 + (n-1)d$ | $b_n = b_1 q^{n-1}$ |
| Сумма n членов | $\frac{(a_1 + a_n)\,n}{2}$ | $b_1 \frac{1 - q^n}{1 - q}$ |
| Бесконечная сумма | расходится (при $d \ne 0$) | $\frac{b_1}{1 - q}$ при $\lvert q\rvert < 1$ |
| Где в ML | линейный warmup LR | дисконт $\gamma^t$ в RL, EMA, затухание LR |
Сумма $1 + 2 + \dots + 100 = \frac{(1 + 100) \cdot 100}{2} = 5050$ (история про юного Гаусса).
Пределы — «к чему стремится»
$\lim_{n \to \infty} a_n = L$ — члены последовательности сколь угодно близко подходят к $L$.
- $\lim \frac{1}{n} = 0$, $\lim (1 + \frac{1}{n})^n = e$, $\lim q^n = 0$ при $\lvert q\rvert < 1$.
- Сходимость обучения — это тоже предел: лосс по шагам стремится к некоторому значению.
- Производная — предел отношения $\frac{f(x + h) - f(x)}{h}$ при $h \to 0$ (раздел Б7).
Скорость роста и O-нотация
$O(f(n))$ — «растёт не быстрее, чем $f(n)$, с точностью до константы». Иерархия:
$$ 1 \ll \log n \ll \sqrt{n} \ll n \ll n\log n \ll n^2 \ll n^3 \ll 2^n \ll n! $$
| Операция | Сложность |
|---|---|
| Поиск по индексу HNSW | ≈ $O(\log n)$ |
| Сортировка | $O(n \log n)$ |
| Self-attention по длине последовательности | $O(n^2)$ |
| Умножение матриц $n \times n$ | $O(n^3)$ |
| Перебор всех подмножеств признаков | $O(2^n)$ — невозможно уже при $n = 50$ |
🏋️ Практика Б6
Б6.1. Learning rate растёт линейно от 0 до 3e-4 за 2000 шагов warmup. Какой LR на шаге 500?
▶️ Ответ
$3 \cdot 10^{-4} \cdot 500/2000 = 7.5 \cdot 10^{-5}$.Б6.2. Найдите $\sum_{t=0}^{\infty} 0.95^t$.
▶️ Ответ
$1/(1 - 0.95) = 20$. «Горизонт» агента с $\gamma = 0.95$ — около 20 шагов.Б6.3. Контекст увеличили с 4K до 32K токенов. Во сколько раз выросло время self-attention?