В курсе "Графические вероятностные модели" в пятницу начали говорить о приближённом выводе, а точнее, о сэмплировании:

СПбГУ — 2026.03.27 — Сэмплирование
(слайды и доска, как всегда, на странице курса)

При чём оно в курсе машинного обучения? Да при том, что в ML постоянно надо считать какие-то сложные математические ожидания; собственно, предсказательное распределение модели — это ожидание по апостериорному распределению. И это распределение обычно даже не дано само по себе в виде плотности, а дано нам в ощущениях как произведение правдоподобия на априорное; то есть мы не умеем даже считать p(x), а умеем считать только что-то пропорциональное p(x).

А ещё ведь проклятие размерности! В размерности 2-3 всегда можно и посэмплировать, и ожидания посчитать, просто накрыв распределение чем-нибудь или приблизив по сеточке. Но в больших размерностях (которые в ML и нужны) не пройдут ни такие трюки, ни более разумные выборку с отклонением (rejection sampling) и выборку с весами значимости (importance sampling), которые мы тоже изучили.

И тем не менее, даже при таких вводных вполне можно что-то сделать! Для этого нужны методы Markov chain Monte Carlo (MCMC): алгоритм Метрополиса-Гастингса и его важный частный случай, сэмплирование по Гиббсу. Их мы тоже подробно обсудили.

А в следующий раз мы будем изучать мой любимый пример в этом курсе: SIR-модели из эпидемиологии.

#spsu #lectures #pgm2026

Пропустил день дураков вчера, а сегодня у меня для вас уже без дураков большой содержательный пост.

Статья "TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate" сейчас завирусилась после того, как попала на ICLR 2026; вот и Google Research выпустил блогпост про неё только сейчас. Акции производителей памяти — Samsung, SK Hynix, Micron — упали на 3–6% за один день, и маркетинговые заголовки зазвучали в духе "$450B Wiped Out - Google TurboQuant Just Crashed RAM Prices 30% Overnight".

На это ужасно смешно смотреть, потому что на самом деле статья висит на arXiv с апреля 2025 года, ей уже год. А математика, на которой она стоит, — теория кодирования Шеннона, алгоритм Ллойда-Макса, лемма Джонсона-Линденштраусса — и вовсе вечна.

В сегодняшнем посте разберёмся, почему эта работа действительно красивая и важная, несмотря на несвоевременный хайп:

Вечная математика TurboQuant: как сжать KV-кэш до предела Шеннона

Пост длинный, я постарался объяснить всё подробно от самого начала (но без особенных доказательств), так что здесь напишу только подробную структуру и сокращённое заключение.

1. Зачем нужна квантизация: контекст проблемы

— Числа с плавающей точкой — это дорого
— Идея квантизации
— Типы квантизации
— Проблема нормализации

2. Нижняя граница Шеннона: почему лучше почти невозможно

— Теорема Шеннона о кодировании с искажением
— Применение к единичной сфере
— От MSE к скалярным произведениям
— Минимакс Яо

3. PolarQuant: полярные координаты убирают overhead

— Проблема: выбросы и нормализация
— Идея PolarQuant
— Почему это работает
— Результаты PolarQuant

4. TurboQuant: ключевые идеи

— Шаг 0: нормализация
— Шаг 1: случайный поворот
— Шаг 2: оптимальная скалярная квантизация (Lloyd-Max)
— Теорема 1 (MSE-гарантия TurboQuant)

5. Проблема смещения: зачем нужен второй этап

— QJL: однобитовый метод
— Собственно TurboQuant
— Теорема 2 (качество квантизации для скалярных произведений)

6. Эксперименты: что на практике

— KV-кэш
— Поиск ближайших соседей

7. Что сделало сообщество

8. Другой подход: KVTC от Nvidia

9. Заключение

Мимо истории TurboQuant пройти было невозможно.

Во-первых, это тот самый пример, когда вечная математика — в данном случае теория информации и довольно глубокие результаты из теории вероятностей — напрямую приводит к state-of-the-art результатам в задаче, которая имеет очень большое практическое значение. Для TurboQuant не нужно обучать мета-модель, не нужен reinforcement learning, не нужны архитектурные или инженерные трюки. Только случайный поворот, оптимальный скалярный квантизатор шестидесятилетней давности и однобитовая добавка на невязку, и всё.

Во-вторых, результат доказуемо близок к оптимальному. Это тоже редко бывает в машинном обучении, и это всегда приятно и интересно видеть.

В-третьих, это data-oblivious алгоритм, работающий онлайн. Его codebooks зависят только от размерности и числа бит, и один и тот же квантизатор работает для любой модели.

В-четвёртых, опять подтвердилась восходящая по крайней мере к 1880-м цитата: “In theory, there is no difference between theory and practice; in practice, there is”. Практические реализации тут же показали, что QJL-этап, который теоретически необходим для несмещённости, на практике может вредить, или что ключи и значения нужно квантизовать асимметрично.

Ну и наконец, сам по себе факт того, что сжатие KV-кэша подходит к пределу Шеннона, означает, что гонка за сжатие в этом конкретном направлении приближается к завершению. В рамках data-oblivious подхода выжать сильно больше уже невозможно, так что дальнейший прогресс будет за счёт data-dependent методов (как KVTC) или гибридных подходов; а может, появятся какие-то совершенно другие парадигмы.

А математика и правда вечна. В этом посте мы упоминали работы Шеннона (1948, 1959), Ллойда (1957) и Макса (1960), Джонсона и Линденштраусса (1986) — и именно они оказались ключевыми для самой громкой инженерной новости марта 2026 года. Занимайтесь математикой, не прогадаете!

#blog #ai #longreads

Вчера забыл выложить сразу, а сегодня что-то целый день вообще сил нет никаких, никакого для вас контента.

Пусть хотя бы фоточка с семинара будет.)

#markovlab #seminar #spsu

Прошла ещё одна лекция в курсе "Введение в глубокое обучение" в ЮФУ:

ЮФУ — 2026.04.04 — Encoder-decoder и механизмы внимания
(слайды и доска на странице курса)

Сначала обсудили архитектуры типа кодировщик-декодировщик и их очень важный частный случай, автокодировщики. Это главный трюк в глубоком обучении, позволяющий сделать из обучения без учителя обучение с учителем: попробуем сжать вход так, чтобы его можно было из сжатого латентного кода восстановить.

А основная часть лекции была посвящена вниманию. Сначала тому вниманию, которое у людей, даже видео про две команды, пасующие баскетбольный мяч, показал коллегам. А потом механизмам внимания в глубоком обучении: как они сначала появились для того, чтобы сэкономить пиксели на входе, а потом позволили собственно архитектурам типа encoder-decoder решить их главную проблему — невозможно выбрать правильный размер латентного кода, будет или слишком короткий, или слишком длинный.

В следующий раз уже отступать будет некуда, обсудим self-attention и трансформеры!

#sfu #lectures #dsfrontiers

Семинар лаборатории Маркова входит в обычный режим университетских семинаров — в следующий раз студент МКН расскажет обзор важной и интересной темы. Поговорим о том, как ускорять порождение картинок в современных диффузионных моделях:

Ускорение сэмплирования в порождающих моделях: от сотен шагов до одного
Ссылка на трансляцию (пятница 10 апреля, 14:00)

Андрей Яременко (Санкт-Петербургский государственный университет)

Диффузионные модели и flow matching получили широкое распространение в ряде задач, от порждения изображений и видео до планирования траекторий роботов. Одним из ключевых ограничений в их применении является высокая вычислительная стоимость: нужно "прогонять" нейросеть последовательно десятки или даже сотни раз для достижения высокого качества порождения.

На семинаре мы рассмотрим различные методы ускорения сэмплирования в этих моделях, вплоть до одного шага (включая Consistency Models, Shortcut Models и Mean Flows), а также разберём Drifting Models — новый подход к построению порождающих моделей, достигающий SotA результатов в задачах порождения изображений при одном вызове модели.

#markovlab #seminar #spsu

Выступаю сегодня на Data Fusion, и вот узнал, что наша сессия (панель про новости AI research) прямо сию секунду будет транслироваться в открытом доступе:

https://data-fusion.ru/

Присоединяйтесь :) в 13 начало, то есть прямо сейчас (ну, после вручения премии). В 14:20 буду на ещё одной сессии выступать, про то, "что будет после LLM", туда тоже подключайтесь!)

Update от 14:20 - начинаем вторую панель)

#events #talks #travel