Асимптотически нормальный канал

170 лет со дня рождения Маркова-старшего!

Совсем недавно, кстати, была первая годовщина создания лаборатории Маркова у нас на факультете — ретроспективно кажется, что можно было бы и дождаться «именин» 👀

Хотел написать небольшой пост вокруг теоремы Гаусса—Маркова, а тут такой повод. Пост будет посвящен тому, как математическая сноровка помогает видеть структуру в неожиданных местах.

Широко известно и интуитивно понятно, что если в линейной регрессии факторы сильно скоррелированы друг с другом, то у оценки их коэффициентов будет большая погрешность. Как это показать формально? Из теоремы Гаусса—Маркова мы знаем формулу ковариации коэффициентов, дальше можно применить что-нибудь в духе формулы обращения блочной матрицы и за несколько выкладок получить искомое. Этот путь концептуально несложен, но технически непрост.

В этом посте я хочу предложить другое доказательство — его можно рассказать устно, но вот придумать... Поражаюсь своим студентам, у которых иногда получается это сделать за время экзамена по ML 🥰

Текстовые квесты как инструмент оценки долговременной памяти языковых моделей

Аня Казанцева, студентка моей программы «Науки о данных», делает супер классный диплом под руководством Антона Алексеева про исследование того, насколько эффективно LLM удерживают и используют информацию о состоянии среды в многошаговых интерактивных сценариях.

Вместо синтетических тестов на извлечение фактов в духе «иголки в стоге сена» используется среда текстовых RPG-квестов с ветвлением и несколькими концовками. Такой формат заставляет модель не только помнить события 20-30 сцен назад, но и строить на их основе стратегию исследования графа состояний. Дополнительная переменная — смена языка повествования на лету для проверки влияния межъязыкового переноса на качество рассуждений.

Основная задача, которая ставится перед моделью — исследовать все дерево переходов и попасть во все концовки за минимальное количество прохождений. Пока промежуточные результаты показывают, что Mistral Small 3.2 в целом справляется что-то там поисследовать (3 концовки из 7 на 10 запусках), но еще есть куда расти. Каких-то инсайтов и интересностей пока не очень много, разве что было замечено, что модель почему-то очень редко пользуется кнопкой «Назад» в ситуациях, когда уже понятно, что дело идет к уже достигнутой ранее концовке.

Для калибровки метрик (полнота исследования дерева, количество возвратов, итерации до обнаружения новых концовок и т.п.) хочется собрать бенчмарк, полученный на людях. С этой целью Аня реализовала один из текстовых квестов в формате телеграм-бота. Если кому-то интересно поисследовать квест — бот доступен вот тут: @quests_play_bot. Квест не супер маленький (30 концовок), но можно проходить не все, а насколько хватит желания. Данные, естественно, обезличены, прохождение не предполагает никаких обязательств, кроме, собственно, прохождения 🌝

После защит обязательно расскажу, что у Ани в итоге получилось!

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

Я с братьями из @csspace делаю бесплатный онлайн-курс на Stepik для школьников по Математике ИИ. Идейки и планчики были давно, но с появлением всероса по ИИ (и теоретического тура в нем) стало понятно, что пора бы уже сделать курс, в котором алгебра, анализ и теорвер излагаются с учетом того необычного для математического образования факта, что сегодня у каждого школьника под рукой есть компьютер, на котором можно писать и запускать программы.

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

У меня нет цели пытаться запихнуть в школьников программу первого курса — с этим прекрасно справляются коллеги, пишущие учебники для сильных физмат лицеев. Многое в курсе сформулировано нестрого и неформально, но, как я надеюсь, это даст учащимся повод и мотивацию уже потом в вузе погрузиться во все тонкости математических дисциплин, чтобы разобраться, как все устроено на самом деле.

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

Интерпретация гамма-пуассоновской смеси с помощью отрицательного биномиального распределения

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

☝️ Мы знаем, что пуассоновское распределение это когда мы считаем количество активностей за фиксированный промежуток времени.

✌️ Еще мы знаем, что отрицательное биномиальное распределение это когда мы считаем, сколько случится неудач к моменту, когда случится r-й успех.

✍️ Пусть мы теперь считаем количество активностей у кучи пользователей за некоторый фиксированный промежуток времени, при этом у каждого пользователя своя интенсивность этих активностей.

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

🤔 Получается, что с одной стороны мы считаем активности, а с другой стороны мы считаем число неудач к моменту какого-то по счету успеха.

Вопрос: есть ли какая-то связь между активностями и неудачами?

Оказывается, что есть: активности это и есть неудачи. Смотрим 🤩к а р т и н о ч к и🤩 и разбираемся, почему так!

Сначала учим студентов, потом учимся у них 💖

Я довольно странный преподаватель статистики.

С одной стороны, статистика мне интересна сугубо как прикладная дисциплина (Theoretical Statistics is the Theory of Applied Statistics): мне нравится узнавать и думать о методах, которые помогают решать насущные проблемы анализа данных, и качество той или иной теории для меня в существенной степени определяется тем, насколько хорошо она позволяет с этими проблемами справляться. Этот мой интерес просачивается и в занятия, на которых я стараюсь объяснить не только теорию, но и как это все потом прикладывается к реальной жизни.

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

То ли дело мои студенты! Эти ребята сплошь и рядом работают в очень крутых командах и из первых рук получают бесценный опыт того, какие на самом деле задачи решает бизнес, какой результат он хочет видеть и какие ограничения у него при этом есть. И какое же счастье, когда они возвращаются и рассказывают, что то, чему я их учил, оказалось полезным, и теперь они передают эти знания дальше среди своих коллег!

Еще большее счастье, когда они возвращаются с фидбеком и рассказывают, как те или иные идеи и методы работают на практике и что еще интересного есть вокруг них. Такое «обратное распространение ошибки» особенно ценно тем, что с тобой как бы говорят твоими же словами, смотрят на вещи твоими глазами, думают твоими идеями. И получается, как будто это лично ты все посмотрел и проверил.

Зачем нужны вероятностные модели, если есть бустинг?

Вчера провел первую лекцию своего курса по статам в ШАД, которая практически полностью повторяет недавно выложенную лекцию про распределения в реальной жизни со студкемпа. Помимо прочего подняли вопрос, чем моделирование в духе Buy Till You Die лучше старого доброго бустинга в оценке LTV пользователя.

Привожу ответ моего студента Дани Ануфриева, который ведет практику на этом курсе, а вообще по жизни занимается разработкой крутых методов моделирования поведения пользователей в Озоне.

1️⃣ С помощью моделей типа BTYD можно почти забесплатно ответить сразу на большой список вопросов:
‣ с какой вероятностью пользователь еще активен? в каком состоянии находится?
‣ через какое время ожидаемо вернется?
‣ какое ожидаемое LTV на 30, 60, 365 дней? Или может даже какое дисконтированное LTV на бесконечности?
Причем ответы на эти вопросы выражаются часто в виде вполне понятных интерпретируемых формул от достаточных статистик пользователей.

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

Если же один раз серьезно подойти к вопросу о там, как устроен процесс поведения пользователей, то на каждый подобный запрос можно иметь под рукой хотя бы такой бейзлайн.

2️⃣ Если же у вас есть конкретная предсказательная задача (что на самом деле не так часто встречается) и «бустинг делает бррр», то артефакты BTYD или других вероятностных моделей можно использовать в качестве фичей: предсказания (не только вашего таргета, но и всего на свете, на что моделька может дать ответ), интервалы, правдоподобия, достаточные статистики и т.д. В случае поведения пользователей есть 100000000000 способов вытащить таким образом какие-нибудь нетривиальные фичи.

Кроме того, обучение и анализ вероятностных моделей может навести на правильные мысли и вообще дать полезную интуицию про физику вашего процесса.

3️⃣ Ну и наконец даже простые вероятностные модельки могут помочь решать очень разные вопросы, связанные c:
‣ пропусками в данных,
‣ нормировками для точек обучающего датасета,
‣ новыми каналами пользователей, которые уже обученный бустинг не описывает, а данных для обучения (LTV365, например) еще нет.

🔣 Вообще предсказание всяких таких поведенческих штук дело очень обреченное — не будет там мега-хороших метрик/скоров. У нас всегда будет очень много неопределенности в предсказании. И тут важно вообще понимать масштабы проблемы и какого мы вообще результата в предсказании теоретически можем добиться. В этом месте можно обратиться тоже, например, к вероятностным моделькам, чтобы посмотреть какие там достигаются теоретические границы в наших метриках качества.

Стреляем себе в ногу с помощью Манна—Уитни II
...и знакомимся с Брюннером—Мюнцелем

Как оказалось, чтобы выстрелить себе в ногу с помощью критерия Манна—Уитни, не обязательно его применять — достаточно написать о нем пост. В этом посте я сказал, что критерий проверяет гипотезу P(X < Y) = 0.5, но это неправда — и про это даже написано на википедии, если удосужиться пролистать страницу до конца.

На самом деле все обстоит еще хуже, чем я думал:
1️⃣ Статистика критерия и правда оценивает P(X < Y). На самом деле не прям вероятность, а вероятность, умноженную на mn, но это неважно.
2️⃣ При условии, что распределение X и Y одно и то же и непрерывно, критерий является точным, то есть вероятность ошибки первого рода будет равна заданному уровню значимости. При этом распределение статистики не зависит от распределения данных и при больших объемах выборок стремится к нормальному.
3️⃣ Если P(X < Y) ≠ 0.5, то критерий является состоятельным, то есть с ростом объемов выборок вероятность отклонить нулевую гипотезу с заданным уровнем значимости (т.е. мощность) будет стремиться к 1.

НО

4️⃣ Если P(X < Y) = 0.5, но распределения X и Y различаются, то распределение статистики критерия уже начинает зависеть от них, однако при больших объемах выборок все еще стремится к нормальному распределению, но с чуть большей дисперсией (если объемы выборок равны, то в худшем случае в 1.5 раза большей).
5️⃣ В случае из предыдущего пункта критерий не будет точным (даже асимптотически), но при этом не будет и состоятельным: скажем, если объемы выборок равны, то вероятность отвергнуть нулевую гипотезу с уровнем значимости 0.05 будет в худшем случае равна ≈0.11 (если не равны, то может быть побольше).

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

Можно ли с этим что-то сделать? Оказывается, что можно, но за это придется променять точность на асимптотическую точность. Решение называется критерием Брюннера—Мюнцеля. Если кратко, то он отличается от Манна—Уитни так же как t-тест Уэлча отличается от t-теста для равных дисперсий.

Учитывая, что по жизни все пользуются t-тестом Уэлча и не парятся, может быть стоит вместо Манна—Уитни сразу использовать Брюннера—Мюнцеля?

Феномен Уилла Роджерса, парадокс Симпсона и ratio-метрики

Хотел написать пост про парадокс Симпсона, но напоролся на замечательный частный его случай, который называется феноменом Уилла Роджерса. С этим феноменом я когда-то давно познакомился в форме анекдота

Петербуржцы, уезжающие жить в Москву, повышают средний IQ обеих столиц.

Если представить, что каждый такой петербуржец теряет чуточку IQ в процессе переезда, то получится стандартный парадокс Симпсона: после переезда средний IQ в столицах упал, хотя в каждой столице по отдельности вырос.

На собесах часто просят привести конкретный численный пример парадокса Симпсона и сюжет с переездом позволяет очень быстро его подобрать. Скажем, пусть до изменения группа A состояла из чисел 3 и 4, группа B из числа 1, а после изменения число 3 переехало из A в B, превратившись в 2. Тогда общее среднее уменьшилось с 8/3 до 7/3, среднее в A выросло с 3.5 до 4, а среднее в B выросло с 1 до 1.5.

Поучительный пример из статьи на вики:

Реальный пример феномена Уилла Роджерса заключается в медицинском понятии «миграции» стадий развития рака». Суть его состоит в том, что улучшение методов диагностики рака приводит к изменению состояния части людей со «здоровый» на «больной»: у людей выявляют опухоли, которые ещё не причиняют им беспокойства.

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

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

Это приводит нас к так называемым ratio-метрикам, когда у каждого пользователя (или какой-то другой единицы рандомизации, которые мы случайно раскидываем между контролем и тестом) измеряется две величины X_i и Y_i, и дальше хочется следить за величиной (sum_i X_i) / (sum_i Y_i). Парадокс Симпсона предостерегает нас от того, чтобы просто посчитать для каждого пользователя X_i / Y_i и дальше применить t-тест.

Как оценивать изменение ratio-метрики, мы узнаем в следующей серии.

Точные интервалы для квантилей

Заметим, что если X имеет непрерывное распределение, то вероятность того, что X окажется левее своего p-квантиля, равна p. Звучит безобидно, но зацените, что отсюда можно получить!

1️⃣ Если у нас есть выборка из 5 элементов, то интервал (минимум выборки, максимум выборки) является точным центральным 93,75% интервалом для медианы.

2️⃣ Если у нас есть выборка из n элементов, то количество элементов слева от p-квантиля имеет распределение Bin(n, p). Подобрав такие целые L и R, что интервал [L, R-1] накрывает ~95% распределения Bin(n, p), мы можем построить точный интервал для p-квантиля с помощью L-го и R-го элементов выборки по возрастанию.

Оказывается, эти интервалы не только точные, но еще и не особо хуже интервалов на основе асимптотической нормальности выборочного квантиля.