Cheatsheet
Большие данные и машинное обучение — all topics on one page
Современные методы машинного обучения
Gradient boosting, ансамблевые методы, reinforcement learning
Разложение ошибки: смещение и дисперсия → Бэггинг: снижение дисперсии → Бустинг: снижение смещения → Современные реализации → Численный пример → Применения в реальном мире
Один классификатор почти всегда хуже коллектива: разные модели делают разные ошибки, и их объединение снижает суммарную ошибку. Ансамблевые методы — фундамент победных решений в машинном обучении на реальных данных.
Ошибка любого алгоритма раскладывается: Err = Bias² + Variance + Irreducible noise. Смещение (Bias) — систематическая ошибка из-за неправильных предположений модели: слишком простая модель «не попадает» в правильный ответ даже на бесконечных данных. Дисперсия (Variance) — чувствительность модели ...
Интуиция: стрелок с высоким смещением целится в сторону от мишени; стрелок с высокой дисперсией — метко, но непоследовательно. Хочется ни того ни другого.
Бэггинг (Bootstrap Aggregation, Breiman, 1994): обучаем B моделей на B бутстрэп-выборках (каждая — случайная выборка с возвращением из исходных n объектов), затем усредняем предсказания. Для регрессии: F̂ = (1/B)ΣF_b(x). Для классификации — большинство голосов.
Марковский процесс принятия решений (MDP) → Q-learning и DQN → Policy Gradient методы → Численный пример: Grid World → Применения
- •S — пространство состояний (state space): возможные ситуации, в которых может оказаться агент
- •A — пространство действий (action space): что агент может сделать
- •P(s'|s, a) — вероятность перехода из состояния s в s' при действии a
- •R(s, a, s') — немедленная награда при переходе
- •γ ∈ [0, 1) — коэффициент дисконтирования будущих наград (γ = 0.99: будущие награды почти так же важны, как текущие)
Обучение с подкреплением — парадигма, в которой агент учится действовать в среде, получая сигналы награды за свои решения. В отличие от supervised learning, правильных ответов нет: агент должен сам открыть оптимальную стратегию через взаимодействие. Именно RL позволил компьютеру победить чемпиона...
Цель агента: найти политику π(a|s) (вероятность действия a в состоянии s), максимизирующую дисконтированную сумму наград: max E[Σₜ γᵗrₜ].
Функция ценности состояния: V^π(s) = E_π[Σₜ γᵗrₜ | s₀ = s] — ожидаемая сумма наград при начале в s и следовании политике π.
Q-функция (action-value function): Q^π(s,a) = E_π[Σₜ γᵗrₜ | s₀=s, a₀=a] — ценность действия a в состоянии s. Зная Q*, оптимальная политика тривиальна: π*(s) = argmax_a Q*(s,a).
Проблема оптимизации гиперпараметров → Neural Architecture Search (NAS) → Автоматизация feature engineering → MLOps: ML в производстве → Численный пример
Разработка ML-пайплайна — это последовательность сложных выборов: алгоритм, предобработка, гиперпараметры, архитектура. Каждый выбор требует экспертизы и сотен экспериментов. AutoML автоматизирует эти выборы, делая машинное обучение доступным для непрофессионалов и ускоряя работу экспертов.
Гиперпараметры (learning rate, глубина дерева, размер скрытого слоя) не обучаются через backprop — их нужно искать внешним методом. Задача: найти конфигурацию λ ∈ Λ, минимизирующую ошибку на валидации: λ* = argmin_{λ∈Λ} L_val(f_{λ}(D_train)).
Проблема: вычисление L_val(f_λ) = «запустить полное обучение» — дорого! Пространство Λ может быть комбинаторно большим (условное — если kernel='rbf', появляются параметры ядра).
Случайный поиск (Bergstra & Bengio, 2012): лучше сетки при высокоразмерных пространствах: если только 2 из 10 гиперпараметров важны, сетка 10^10 конфигураций тратит ресурсы на незначимые оси. Случайный поиск исследует все оси равномерно.
Математические основы Deep Learning
Теория аппроксимации, backpropagation, трансформер
Теорема об универсальной аппроксимации → Преимущество глубины → Нейронные тангентные ядра (NTK) → Double Descent → Численный пример → Применения теории
- •1 скрытый слой, 10 нейронов (ReLU): ошибка ≈ 0.05 (кусочно-линейная)
- •1 слой, 100 нейронов: ошибка ≈ 0.005
- •2 слоя × 10 нейронов (20 параметров суммарно): ошибка ≈ 0.003
Почему нейронные сети работают? Какой класс функций они могут аппроксимировать? Зачем нужна глубина — можно ли обойтись одним широким слоем? Теория аппроксимации отвечает на эти вопросы математически строго, обосновывая практический успех глубокого обучения.
Классическая теорема (Cybenko, 1989; Hornik, Stinchcombe, White, 1989): Однослойная нейронная сеть с сигмоидными нейронами, достаточным числом скрытых нейронов и любой непостоянной сигмоидной функцией активации может аппроксимировать любую непрерывную функцию f: [0,1]^n → ℝ с точностью ε > 0.
Ограничение теоремы: не говорит, сколько нейронов нужно (может быть астрономически много), не говорит, как обучить.
Теорема Баррона (1993): для функций с ограниченным первым моментом Фурье-спектра ||C_f|| < ∞ однослойная сеть из n нейронов достигает ошибки аппроксимации O(C_f²/n) в L₂. Важно: размерность пространства входа не входит в оценку — нет «проклятия размерности» для этого класса функций.
Стохастический градиентный спуск (SGD) → Адаптивные методы → Learning Rate Schedules → Нормализация → Численный пример
Обучение нейронной сети — это решение задачи оптимизации min_θ L(θ) в пространстве с миллиардами переменных. Ландшафт функции потерь L(θ) сложен: седловые точки, плоские плато, овраги. Понимание методов оптимизации — ключ к успешному обучению глубоких моделей.
Полный градиент ∇L(θ) = (1/n)Σᵢ ∇lᵢ(θ) дорог при n = миллионы. Стохастическая аппроксимация: берём мини-батч B ⊂ {1,...,n} и аппроксимируем: ĝₜ = (1/|B|) Σᵢ∈B ∇lᵢ(θₜ). Обновление: θₜ₊₁ = θₜ − αₜ ĝₜ.
Ключевое свойство: E[ĝₜ] = ∇L(θₜ) — несмещённая оценка. Дисперсия Var[ĝₜ] = σ²/|B| убывает с размером батча.
Теорема сходимости (выпуклый случай): При убывающем lr αₜ = O(1/√t) и L-гладкой выпуклой функции: E[L(θ_T)] − L(θ*) ≤ O(1/√T). Для μ-сильно выпуклой при αₜ = O(1/t): O(σ²/(μT)).
Scaled Dot-Product Attention → Multi-Head Attention → Архитектура трансформера → Улучшения для эффективности → Законы масштабирования → Численный пример
- •QKᵀ — матрица скалярных произведений всех пар запрос-ключ: насколько «совместим» каждый запрос с каждым ключом. Элемент [i,j] — релевантность позиции j для позиции i.
- •/√d_k — масштабирование для предотвращения насыщения softmax (при больших d_k произведения становятся большими → softmax концентрируется на одной позиции → исчезающий градиент).
- •softmax(...) — нормировка в вероятности: строки суммируются в 1 — «распределение внимания» над позициями.
- •· V — взвешенная сумма значений: выход = смесь значений всех позиций с весами внимания.
Трансформер (Vaswani et al., «Attention Is All You Need», 2017) — революционная архитектура, устранившая рекуррентность в обработке последовательностей. Механизм self-attention позволяет каждому элементу последовательности взаимодействовать с любым другим за один шаг, открыв путь к масштабировани...
Ключевая операция трансформера. Три матрицы: Q (queries) ∈ ℝ^{n×d_k}, K (keys) ∈ ℝ^{n×d_k}, V (values) ∈ ℝ^{n×d_v}.
Для одного токена «The cat sat»: запрос «sat» смотрит на ключи «The»(0.1), «cat»(0.8), «sat»(0.1) — механизм внимания нашёл, что «сидел» → кот.
Один механизм внимания видит только один тип взаимодействий. Multi-head Attention использует h параллельных «голов» с разными проекциями:
Статистика высокой размерности
Проклятие размерности, разреженность, LASSO, Ridge, PCA
Парадоксы высоких измерений → Лемма Джонсона–Линденштрауса → PCA и метод главных компонент → Robust PCA и Sparse PCA → Численный пример
Большинство наших геометрических интуиций сформировалось в 2D и 3D. Но данные о людях, текстах, молекулах живут в пространствах размерности d = 100, 1000, 100000. В этих пространствах всё работает иначе — и понимание «проклятия размерности» критично для ML-практика.
Объём «скорлупы»: В ℝᵈ объём шара Bᵈ(r) = πᵈ/²rᵈ/Γ(d/2+1). При d → ∞ почти весь объём шара сосредоточен в тонком слое вблизи поверхности. Точнее: для X ~ Uniform(Bᵈ), E[||X||] ≈ r·√(d/(d+2)) → r, а Var(||X||) → 0.
Практическое следствие: все случайные точки в шаре находятся примерно на одном расстоянии от центра → расстояние от центра — не различительный признак.
Случайные векторы почти ортогональны: Для X, Y ~ N(0, Iᵈ/d): cos(∠XY) = Xᵀ Y/(||X|| ||Y||) → N(0, 1/d). При d=1000 стандартное отклонение угла ≈ 1/√1000 ≈ 0.03 радиана ≈ 1.8°. Почти все случайные векторы почти ортогональны — это и хорошо (easy to embed many directions) и плохо (кластеризация неэф...
Основная теорема Compressed Sensing → Случайные матрицы удовлетворяют RIP → Алгоритмы восстановления → Применения → Структурная разреженность: Group LASSO и Total Variation → Численный пример
Представьте: вы хотите записать МРТ-снимок, но у пациента мало времени — нельзя получить все измерения. Или нужно передать сигнал через канал с ограниченной пропускной способностью. Теория compressed sensing (Candès, Romberg, Tao; Donoho, 2006) говорит: если сигнал «разреженный», нескольких линей...
Постановка задачи: x ∈ ℝⁿ — сигнал (например, изображение из пикселей). A ∈ ℝ^{m×n}, m ≪ n — матрица измерений. Наблюдаем y = Ax (m << n измерений — явно недоопределённая система). Цель: восстановить x.
Условие разреженности: x имеет не более s ненулевых компонент: ||x||₀ = s ≪ n. Большинство сигналов разреженны в каком-то базисе: изображения — в вейвлет-базисе, аудио — в Фурье-базисе.
Здесь: ||x||₁ = Σᵢ |xᵢ| (L1-норма), σₛ(x) — ошибка наилучшей s-разреженной аппроксимации. Ключевое: задача L1-минимизации (выпуклая!) решает, казалось бы, невозможную задачу восстановления из m ≪ n измерений.
Вариационный автоэнкодер (VAE, Kingma & Welling, 2013) → Generative Adversarial Networks (GAN, Goodfellow et al., 2014) → Диффузионные модели (Ho et al., DDPM, 2020) → Сравнение трёх семейств → Численный пример
| Метод | Качество | Разнообразие | Скорость | Управляемость |
|---|---|---|---|---|
| VAE | Среднее | Высокое | Быстро | Хорошая (в z) |
| GAN | Высокое | Низкое (mode collapse) | Быстро | Сложная |
| Diffusion | SOTA | Высокое | Медленно | Очень хорошая |
- •Reconstruction loss E[log p_θ(x|z)]: насколько хорошо декодер восстанавливает x из z — качество реконструкции
- •KL-дивергенция KL(q||p): насколько апостериорное распределение z|x близко к априорному p(z)=N(0,I) — регуляризация латентного пространства
Дискриминативные модели отвечают на вопрос «какой класс?». Генеративные модели отвечают на «как это выглядит?». Они учатся представлению распределения данных и могут создавать новые образцы — изображения, молекулы, музыку. Три семейства определили современный AIGC: VAE, GAN и диффузионные модели.
Постановка: Дано x (изображение). Хотим обучить генеративную модель p_θ(x) = ∫ p_θ(x|z) p(z) dz, где z — латентный код (скрытые факторы). Интеграл по всем z — неаналитичен.
Вариационный вывод (ELBO): вводим энкодер q_φ(z|x) ≈ p(z|x) и максимизируем нижнюю границу (Evidence Lower BOund):
Reparameterization trick: z ~ q_φ(z|x) = N(μ_φ(x), σ_φ²(x)I). Нельзя взять градиент через стохастическую выборку. Трюк: z = μ_φ(x) + σ_φ(x) ⊙ ε, где ε ~ N(0,I). Теперь случайность в ε (не зависит от параметров), градиент ∂z/∂φ аналитичен.
Выпуклая оптимизация для ML
Методы проксимального градиента, Adam, SGD, теория сходимости
Выпуклые функции и задачи → Методы градиентного спуска → Проксимальные методы → ADMM: декомпозиция задачи → Координатный спуск → Численный пример
Formulas
- •Выпуклая, L-гладкая: f(x_T) − f* ≤ L||x₀−x*||²/(2T). Сходимость: O(1/T).
- •μ-сильно выпуклая, L-гладкая: ||xₜ−x*||² ≤ (1−μ/L)ᵗ ||x₀−x*||². Сходимость: O(exp(−t/κ)).
- •g(x) = λ||x||₁: prox = sign(v)·max(|v|−αλ, 0) (мягкое пороговое, soft-thresholding)
- •g(x) = λ||x||₂: prox = max(1−αλ/||v||, 0)·v (проекция на шар)
- •g = I_C (индикатор выпуклого множества C): prox = проекция на C
Многие задачи ML имеют выпуклую структуру: линейная регрессия, логистическая регрессия, SVM, LASSO, Ridge, метод опорных векторов. Для таких задач гарантирован глобальный оптимум, и существует богатая теория эффективных алгоритмов. Знание выпуклой оптимизации — фундамент понимания того, «почему р...
Определение выпуклости: Функция f: ℝⁿ → ℝ выпуклая, если для всех x, y ∈ dom(f) и α ∈ [0,1]:
Геометрически: хорда между любыми двумя точками лежит выше графика. Следствие: локальный минимум = глобальный.
L-гладкость: f дважды дифференцируема с ||∇²f(x)|| ≤ L (наибольшее собственное значение гессиана ограничено). Эквивалентно: ||∇f(x) − ∇f(y)|| ≤ L||x−y|| — градиент не меняется слишком быстро. Следствие (descent lemma):
Стохастический градиентный спуск: теория → Adam: теоретический анализ → Variance Reduction: SVRG и SARAH → Федеративное обучение → Численный пример
Formulas
- •Убывающий: αₜ = α₀/√t → сходимость O(σ/√T) (конвексный случай)
- •Постоянный: αₜ = α → сходимость к окрестности, но не к оптимуму
- •Убывающий для SC: αₜ = 2/(μ(t+1)) → O(σ²/(μT)) (сильно выпуклый)
- •Batch size = 256, lr = 2e-4, warmup = 10000 шагов
- •Adam: β₁=0.9, β₂=0.999, ε=1e-8, weight decay=0.01
- •После 1M шагов (~10 дней на 8×A100): val perplexity = 3.8
Современные нейронные сети обучаются на миллиардах примеров и имеют миллиарды параметров. Вычисление точного градиента невозможно — нужны стохастические методы. Понимание их теоретических свойств позволяет настраивать обучение и диагностировать проблемы.
Постановка: min_θ f(θ) = (1/n) Σᵢ fᵢ(θ). Стохастический градиент: gₜ = ∇fᵢₜ(θₜ), где iₜ выбирается случайно. Ключевые свойства: E[gₜ] = ∇f(θₜ) (несмещённость), Var[gₜ] = σ² (конечная дисперсия).
Mini-batch: gₜ = (1/|B|)Σᵢ∈Bₜ ∇fᵢ(θₜ). Дисперсия уменьшается: Var[gₜ] = σ²/|B|. Линейное ускорение до критического размера батча B_crit ≈ σ²/||∇f||² — дальше параллелизм помогает только по времени, не по итерациям.
mₜ = β₁ mₜ₋₁ + (1−β₁) gₜ (сглаженное среднее градиента) vₜ = β₂ vₜ₋₁ + (1−β₂) gₜ² (сглаженное среднее квадрата) m̂ₜ = mₜ/(1−β₁ᵗ), v̂ₜ = vₜ/(1−β₂ᵗ) (коррекция смещения) θₜ₊₁ = θₜ − α · m̂ₜ/(√v̂ₜ + ε)
Глобальная vs локальная интерпретируемость → SHAP: аксиоматически обоснованный метод → Adversarial Robustness → Calibration: корректность уверенности модели → Дрейф данных и OOD Detection → Численный пример
Нейронная сеть предсказывает рак по МРТ-снимку. Врач спрашивает: «Почему?» Банк отказывает в кредите. Клиент требует объяснений. Регулятор проверяет модель. Интерпретируемость — не академическая игрушка, а юридическое и этическое требование. GDPR в ЕС гарантирует «право на объяснение» автоматизир...
Глобальная: понять, как модель работает в целом — какие признаки важны для всех предсказаний. Пример: feature importance в случайном лесу — средняя MDI по всем деревьям.
Локальная: объяснить конкретное предсказание — почему модель решила так для этого конкретного объекта. Критична для применений с высокими ставками (медицина, кредитование, юстиция).
Расшифровка: усредняем предельный вклад признака i по всем возможным коалициям S других признаков. |S|!(|F|−|S|−1)!/|F|! — вес данной коалиции (соответствует случайному порядку добавления признаков).
Алгоритмы для Big Data
Рандомизированная линейная алгебра, хеширование, потоковые алгоритмы
Рандомизированное SVD → Приближённый поиск ближайших соседей (ANNS) → Потоковые алгоритмы: большие данные малой памятью → Численный пример
Formulas
- •Истинный ранг матрицы ≈ 100
- •Точное SVD: 480K × 17K × 100 ≈ 816 × 10⁹ операций (~4 часа)
- •Random SVD (k=100, q=2): ~240 × 10⁹ → ~1 час, ошибка <1%
Матрица данных 10 миллионов пользователей × 100 тысяч продуктов. Полное SVD — невозможно: O(mn·min(m,n)) ≈ 10¹⁷ операций. Рандомизированные алгоритмы снижают сложность до O(mnk) при теоретических гарантиях близости к точному решению. Это не «приближение из-за лени» — это математически строгая тео...
Задача: вычислить лучшее ранг-k приближение матрицы A ∈ ℝ^{m×n}: min_{rank(B)≤k} ||A − B||_F.
Шаг 1. Случайная матрица Ω ∈ ℝ^{n×k}: Ωᵢⱼ ~ N(0,1/k). Sketch Y = AΩ ∈ ℝ^{m×k}. Смысл: Y аппроксимирует «пространство столбцов» A — проецируем A на k случайных направлений.
Шаг 2. QR-разложение Y = QR, Q ∈ ℝ^{m×k} — ортонормированный базис пространства столбцов Y.
MapReduce: парадигма параллельных вычислений → Apache Spark: in-memory вычисления → GPU-вычисления: параллелизм на уровне ядра → Эффективный инференс → Численный пример
- •MapReduce (Hadoop): ~45 минут (disk I/O доминирует)
- •Spark (RDD, in-memory): ~8 минут (6× ускорение)
- •Spark (DataFrame + Parquet): ~3 минуты (колонковое хранение + Catalyst)
- •MapReduce: 60 итераций × 5 мин = 5 часов
- •Spark с cacheRDD: 60 итераций × 30 сек = 30 минут
Один компьютер с 512 ГБ RAM и быстрым SSD мощен, но данные современных компаний — петабайты. Распределённые вычислительные системы позволяют обрабатывать эти данные на кластерах из тысяч машин. Понимание этих систем критично для ML-инженера, работающего с реальными данными.
Идея (Dean & Ghemawat, Google, 2004): разбить вычисление на два этапа, каждый из которых параллелизуется по данным.
Map(k, v) → список (k', v'): применяется независимо к каждой записи. Пример: подсчёт слов — Map("hello world", 1) → [("hello",1), ("world",1)].
Shuffle: система автоматически группирует все пары (k',v') по ключу k'. Самый дорогой шаг — data movement по сети.
Предобучение: задача языкового моделирования → Архитектурные детали LLM → RLHF и постобучение → Законы масштабирования и возможности → Численный пример
- •Архитектура: 32 слоя, 32 Q-головы, 4 KV-головы (GQA), d_model=4096
- •KV-кэш (32K контекст, FP16): 32 × 4096 × 2 × 32768 × 2 байта ≈ 8 ГБ — больше весов!
- •Скорость генерации (A100): ~50 токен/с (без batching)
- •После DPO fine-tuning (10K preference pairs): MT-Bench score +1.2 балла
GPT-4, Claude, Gemini — большие языковые модели (LLM) произвели революцию в AI за 2020–2024 годы. Чтобы эффективно применять и дорабатывать эти модели, необходимо понимать их архитектуру, процесс обучения и методы адаптации.
Авторегрессивное языковое моделирование: P(x₁,...,xₙ) = Πᵢ P(xᵢ|x₁,...,xᵢ₋₁). Потери при предобучении: L_LM = −(1/n) Σᵢ log P(xᵢ|x₁,...,xᵢ₋₁;θ). «Следующий токен» — простая задача, которая вынуждает модель понимать семантику, синтаксис, фактологию, причинность.
Токенизация: Byte-Pair Encoding (BPE) — итеративно объединяет наиболее частые пары байт. Словарь 32K–256K токенов. «Moscow» → [«Mos», «cow»] или как один токен.
Данные: Common Crawl (фильтрованный интернет), Books, Wikipedia, GitHub, arXiv, StackExchange. Трекинги: The Pile (800GB, EleutherAI), RedPajama, Dolma. Качество фильтрации критично: неаккуратная фильтрация → деградация.