Шпаргалка

Большие данные и машинное обучение

Все темы на одной странице

5модулей

15статей

0определений

4формул

Современные методы машинного обучения

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).

Автоматический поиск архитектур и AutoML

Проблема оптимизации гиперпараметров → 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 и Диффузионные модели

Вариационный автоэнкодер (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: декомпозиция задачи → Координатный спуск → Численный пример

Формулы

Проксимальный оператор: prox_{αg}(v) = argmin_x {(1/2)||x−v||² + αg(x)}. Имеет аналитическое решение для многих g:Задача с ограничением: min f(x) + g(z), при Ax + Bz = c. Примеры: distributed ML, portfolio optimization.

·Выпуклая, 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 → Федеративное обучение → Численный пример

Формулы

SARAH (Nguyen et al., 2017): рекурсивное variance reduction: gₜ = ∇fᵢ(xₜ) − ∇fᵢ(xₜ₋₁) + gₜ₋₁. Теоретически ещё лучше SVRG.

·Убывающий: αₜ = α₀/√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̂ₜ + ε)

Интерпретируемость и надёжность DL-моделей

Глобальная vs локальная интерпретируемость → SHAP: аксиоматически обоснованный метод → Adversarial Robustness → Calibration: корректность уверенности модели → Дрейф данных и OOD Detection → Численный пример

Нейронная сеть предсказывает рак по МРТ-снимку. Врач спрашивает: «Почему?» Банк отказывает в кредите. Клиент требует объяснений. Регулятор проверяет модель. Интерпретируемость — не академическая игрушка, а юридическое и этическое требование. GDPR в ЕС гарантирует «право на объяснение» автоматизир...

Глобальная: понять, как модель работает в целом — какие признаки важны для всех предсказаний. Пример: feature importance в случайном лесу — средняя MDI по всем деревьям.

Локальная: объяснить конкретное предсказание — почему модель решила так для этого конкретного объекта. Критична для применений с высокими ставками (медицина, кредитование, юстиция).

Расшифровка: усредняем предельный вклад признака i по всем возможным коалициям S других признаков. |S|!(|F|−|S|−1)!/|F|! — вес данной коалиции (соответствует случайному порядку добавления признаков).

Алгоритмы для Big Data

Рандомизированная линейная алгебра, хеширование, потоковые алгоритмы

Рандомизированная линейная алгебра

Рандомизированное SVD → Приближённый поиск ближайших соседей (ANNS) → Потоковые алгоритмы: большие данные малой памятью → Численный пример

Формулы

Задача: для запроса q найти x* = argmin_{x∈X} d(q, x). Exact kNN: O(nd) за запрос. При n=10^8, d=768 (BERT embeddings) — невозможно.

·Истинный ранг матрицы ≈ 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.

Распределённые вычисления и Apache Spark

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 по сети.

Large Language Models: архитектура и обучение

Предобучение: задача языкового моделирования → Архитектурные детали 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. Качество фильтрации критично: неаккуратная фильтрация → деградация.