epsilon correct

Доход и счастье

На днях вышла статья в коллаборации с Канеманом. Она по сути опровергает довольно вредный мем (который пошёл с более ранней статьи того же Канемана) о том, что после доходов $75000 в год уровень счастья (emotional well-being) людей в среднем не растёт. В новой статье показывается, что в общем грустным людям уровень счастья деньгами действительно не повысишь, а вот людям из верхних персентилей деньгами гораздо проще сделать приятно. В исследовании 2010 года Канеман смешал все группы, и эффект пропал – похоже на парадокс Симпсона, только менее ярко выраженный. Та статья довольно плотно критиковалось.

Отдельно стоит отметить то, как статья была написана. В отличие от подавляющего большинства статей, которые пишутся коллаборативно, эта статья – продукт adversarial collaboration. Идея проста: находим учёного, у которого противоположная точка зрения на то, что означают данные, и пытаетесь друг друга убедить в обратном, проводя дополнительные эксперименты и анализы. В результате получаются статьи лучшего качества, так как самая серьёзная критика оказывается уже рассмотрена. Жаль, в methods research так не получится.

Тулзы: GNU Parallel

Раз уж пошла речь о железе, нужно чуток рассказать о том, как его эффективно использовать. Эксперименты к статьям – это чаще всего усредение по десяткам запусков методов на разных датасетах. Если мы говорим не про нейросети, которые гоняются на ГПУшках, то почти всегда *гораздо* эффективнее запустить X параллельных процессов, чем один процесс на X ядрах. Поможет нам в этом GNU parallel.

Я строил свои эксперименты примерно следующим образом:
1. Создавал бинарник с флагами, по которым шел перебор – датасеты, параметры, сиды. Бинарник пишет свой выход в уникальный файлик.
2. Простеньким питоновским скриптом генерировал текстовый файл с командой на каждой строке, перебирая все интересующие значения флагов.
3. parallel --ungroup -j N_CORES --nice 19 < command.txt. Флаг nice задаёт задачам низкий приоритет, чтобы ОС могла выполнять свои задачи. ungroup отвечает за то, чтобы вывод всех программ выводился на экран параллельно.
4. Ещё одним простым скриптом собираем данные с выхода в удобную табличку.

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

Про железо для рисерча

Часто читаю в интернете жалобы о том, что не хватает железа, чтобы сделать свой классный рисёч. Мне тяжело это понять, потому что только для очень небольшого процента опубликованных исследований на условном ICML нужен был по-настоящему большие ресурсы. Да, у всех на слуху последние огромные сетки от индустриальных лаб с тысячами GPU, но ведь большинство статей выходит без подобных излишеств. Более того, научной новизны в статьях "а давайте TPU сделают brrr" меньше, чем в среднем по больнице.

В начале моего PhD у нас в группе не было серверов. Ни одного. Все эксперименты для моей первой статьи запускались на довольно обычном домашнем ПК. Потом ситуация чуть наладилась, и появилось два 40-ядерных сервера с 256Gb RAM – ничего сверхъестественного. Б/Ушные такие сервера сейчас стоят около $2000 – такое может себе позволить плюс-минус любой.

Если возможностей заиметь железо вообще нет, AWS, Google Cloud и Miscorsoft Azure дают железные гранты на довольно внушительные суммы. Также на Google Cloud есть $300 бесплатных кредитов, что примерно равно цене месяца 20-ядерного CPU инстанса. В те же $350 в месяц обойдется сервер с двумя V100 на vast.ai – и это если его не выключать и тренировать 24/7. Всё решаемо.

Забавной применение моей старой статьи – оказывается, по структуре графа взаимодействия персонажей можно определить, является ли произведение комедией или трагедией (по крайней мере, у Шекспира :)

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

В Нью-Йоркере очень классная колонка, которая предлагает довольно мощную метафору для ChatGPT. Редкий пример качественной научно-популярной журналистики, которая заинтересовала многих исследователей и что-то новое рассказала обывателям.

Правильный HPO: Vizier

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

Надеюсь, опен-сорсная версия окажется такой же полезной, как и внутренний продукт. К слову, он продается в Google Cloud, и теперь не совсем понятно, как эти два продукта будут сосуществовать (classic Google).

LaTeX, который пригождается в жизни

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

Называются эти пакеты PGF/TikZ и pgfplots. Начнем с TikZ, так как он является базовым для pgfplots. Свои названием – TikZ ist kein Zeichenprogramm – нам намекают на то, что рисовать у нас в ней не получится, но подготавливать технические иллюстрации, даже очень сложные, получается очень хорошо. Модель программирования в TikZ через примитивы, соединенные между собой линиями, очень проста, но позволяет красиво рисовать небольшие технические иллюстрации в векторе намного красивее, чем в каком-нибудь Inkscape.

Второй пакет – pgfplots – я очень люблю за то, что позволяет отделять при рисовании графиков код для подготовки от кода для рисования. Чаще всего я обрабатываю результаты экспериментов в питоновском ноутбуке и сохраняю csv со всеми результатами. Дальше можно играться со стилем графиков сколько угодно. Это особенно удобно, когда через N месяцев после написания статьи резко нужно чуть-чуть поправить что-нибудь на каком-то графике. Соавторы, конечно, поначалу сильно удивляются, когда забредают в TikZ или pgfplots файлы, но потихоньку учатся там что-то менять по своему усмотрению.

Отдельно стоит отметить документацию обоих пакетов - у TikZ она занимает 1321 страницу, у последней версии pgfplots – книжка на 573. В документации всё очень легко ищется и много примеров, которые работают "из коробки".

Для вдохновления иногда посматриваю сайт tikz.net и гитхаб с иллюстрациями про графы, которые делает Petar Veličković. Анимацию для нашего с Джоном поста в Google AI Blog делал я в pgfplots.

Пост-дедлайн пост

В четверг был дедлайн подачи на ICML, и я таки успел кое-как состряпать туда статью. По такому поводу стоит записать немного мыслей – как раз перестал дергаться глаз от выпитого редбулла.

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

Одной из ошибок было то, что я не сразу запустил все эксперименты, которые в итоге пошли в статью, в итоге пришлось кучу времени потратить на решение технических проблем. Из-за багов файловой системы (ха-ха!) эксперименты приходилось запускать в максимально ручном режиме, следя, чтобы файлы с результатами записывались, куда надо. Кажется, на будущее стоит все-таки разобраться, как подобные задачи решаются на внутренней архитектуре, а то мои велосипеды с отловом ошибок ФС приличными назвать никак нельзя.Из-за этих проблем долго не мог заставить себя писать текст – непонятно же, про что! В результате текст был написан почти без редактуры в полтора прохода. Пока пару недель решил его не читать, чтобы сильно не расстраиваться. На архив пока выгладывать не буду – стыдно за текст, да и код надо переписать и почистить.

Из уроков на будущее – в подобных проектах надо пушить MVP всех экспериментов, и только потом садиться качественно писать статью. И все-таки постараться убедить хоть кого-то помочь со статьей, а то делать всё самому получается накладно.

А теперь пора толкать прод, шоб не уволили.

Вдогонку вам график инфляции в США в 70х и сейчас. Вызывает опаску, что у Пауэлла сейчас намного меньше политической независимости, чем в свое время было у Волкера. Научились ли мы эффективно бороться с инфляцией?

Сокращения в гугле

Ну вот и до гугла добрались сокращения – уволили 12к человек, или около 5% персонала. Вышло довольно ожидаемо, учитывая безумный постковидный хайринг и высокую ключевую ставку. Нашу команду это не затронуло от слова совсем, в целом, сокращения в рисёрче были минимальными. Из того, что я увидел, сокращали несколько типов людей:
1. Команды, которые приносили мало импакта и в продукт, и во внешний мир (в случае рисерча - почти не публиковались).
2. Очень дорогие люди в не очень успешных продуктах.
3. Исторические лоу перформеры.

Соболезную людям на визах, которым дано 60 дней, чтобы найти новую работу. Получается вот такая печальная мотивация писать статьи на ICML и KDD, и побыстрее получать гринкарту. This is America. :)

Непопулярные статьи, выпуск 1

Одной из причин, почему я хотел завести свой канал, было желание делиться не очень известными статьями, на которые я набредаю в ходе своей работы. Первой в этом списке по праву будет "On the Behavior of Intrinsically High-Dimensional Spaces: Distances, Direct and Reverse Nearest Neighbors, and Hubness" авторства Fabrizio Angiulli (без всяких там et aliī). В статье длиной в 60 страниц и 38 теорем – которые, между прочим, все аккуратно доказываются в конце – скурпулёзно разбирается то, как работают расстояния до ближайших соседей в пространствах высокой размерности для случайных данных.

Почему это важная статья? Потому что даже в текущем мире с гигантскими языковыми моделями поиск ближайших соседей – одна из самых базовых операций, на которой работают практически все сервисы рекомендации контента и поиска в мире. На практике оказывается, что очень сложно задать конкретный порог ε для поиска ближайших соседей для произвольной точки – даже для равномерно распределённых данных мы с высокой вероятностью получим либо ноль, либо кучу соседей. Скорее всего, в реальных данных с кучей кластеров дела обстоят только хуже. В статье также разбираются несколько случаев расстояний до k-го ближайшего соседа в данных с разными распределениями.

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

Ссылка на статью: https://www.jmlr.org/papers/volume18/17-151/17-151.pdf

Еретики

С конца 2022 всё никак не может улечься волна хайпа ChatGPT – каждый уважающий себя блогер успел поделиться своим бесценным анализом способностей и, сильно реже, ограничений новой диалоговой модели. Сама модель мне стала не очень интересна после того, как она усердно пыталась убедить меня в том, что граф – это график, но ни в коем случае не математический объект. С другой стороны, интересно подумать о разных

Почему-то многие люди думают, что в этой нашей "серьёзной науке" нет места моде и стадному поведению. Это, очевидно, не так – достаточно последить за статьями на "топовой троице" ML конференций – ICML/NeurIPS/ICLR. Лет пять назад был расцвет генеративных состязательных сетей, сейчас им пришли на смену диффузионные модели. Да и само обучение гигантских моделей градиентным спуском тоже является текущей модой.

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

К слову, Costică Brădățan не так давно написал отличную статью про еретиков и нонконформистов в науке в мой любимый aeon.co – очень рекомендую.

Stop using the elbow method

В почти любом курсе introduction to ML разбирается k-means, и на вопрос, как же выбирать заветный параметр k, обычно даётся "пацанский" ответ – "метод локтя" (elbow method). Заключается он вот в чём – берётся график зависимости ошибки метода от количества кластеров k и на нём ищется "перегиб". Для более продвинутых поисков есть много разных алгоритмических методов (сами представьте, сколько разных способов найти перегиб в функции).

Ожидаемо, такой метод работает очень плохо. В статье сравниваются 8 разных методов поиска "локтя" – и ни один не даёт вменяемый результат на довольно простых моделях синтетических данных. Что лучше использовать? У авторов хорошо отработали variance-ratio criterion, Bayesian Information Criterion (BIC), и Gap statistic. Из них легко можно посчитать VRC и BIC. Пользуясь случаем, авторы напоминают, что k-means крайне чувствителен к препроцессингу данных, и приводят пару визуальных примеров того, где можно налажать.

2023 год набирает обороты, а проблема оптимального выбора k до сих пор не решена даже для простейших моделей данных.

Статья: https://arxiv.org/abs/2212.12189

NeurIPS'22, часть 2

Вторая часть про NeurIPS – теперь чуть-чуть о науке.

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

1. Много интересных работ про self-supervised learning (SSL) – наверное, было больше десятка постеров про имплементацию для разных модальностей данных, и несколько – про теорию. Например, "Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods" подробно разбирает, как линеаризовать популярные лоссы для SSL и что из этого получается (спойлер: классические методы снижения размерности).

2. Сумасшедших результатов в анализе больших графов не было, а в графовых сетках для молекул разбираться у меня сил и времени нет. Из интересного, но не очень полезного "Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks" показывает, как сконструировать небольшие графовые сети, которые симулируют тест Вейсфейлера-Лемана. Это важно для теории экспрессивности графовых сетей, потому что предыдущие конструкции зависели от структуры графа.

3. Было несколько интересных статей по TCS. "Faster Linear Algebra for Distance Matrices" предлагает быстрые алгоритмы для матрично-векторных произведений матриц расстояний. "Approximate Euclidean lengths and distances beyond Johnson-Lindenstrauss" улучшает скорость оценки норм строк произвольной матрицы.

NeurIPS'22, часть 1

Пару недель назад закончилось одна из самых масштабных конференций этого года – NeurIPS. Вместе в ICML и ICLR, NeurIPS в тройке лучших конференций по машинному обучению, на которые (в теории) попадают лучшие работы из разных областей ML от CV до NLP. В этом году, кстати, одной из самых популярных тем стали графы и графовые нейросетки.

В этом году я приехал на конференцию с туториалом, статьёй в основной секции и двумя – на воркшопах. "Раз начал ~заниматься рисёрчем~, то иди в своём увлечении до конца".

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

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

Во-вторых, почти невозможно разобраться в новых работах на лету. На обычных конференциях постерные сессии следуют за презентациями, но на перегруженных ML конфах такое организовать просто невозможно, поэтому от презентаций отказались. Но и постеров оказывается катастрофически много – в этом году было 6 двухчасовых сессий с ±400 постерами на каждой. Разобраться в таком потоке информации просто нереально.

В-третьих, плотность распорядка. На обычных конференциях мне интересы пара приглашённых лекций, несколько статей, и один воркшоп. Тут, из-за размера и престижности интересно всё, и времени на фланирование не остаётся. Приходится жертвовать, например, туториалом по conformal prediction, который мне ещё предстоит посмотреть на праздниках.

Так как пост получился длинным, о науке на NeurIPS я напишу отдельно.

Просить то, чего ты хочешь.

Сегодня я должен был лететь с пересадкой из Нового Орлеана в Нью-Йорк. Самолёт задержали, и на пересадку я не успевал. American Airlines решили, что хорошо бы мне полететь на следующий день, убив лишний день на перелёт. Я бы и согласился – в таких случаях предоставляют отель поспать – но в этот раз я попробовал испытать удачу и поспрашивать, нет ли рейса в соседний Нью-Джерси. Оказалось, что есть, и лечу я в сумме всего на 2 часа дольше. Надо было только попросить – ведь авиакомпания не могла знать, что я не против прилететь в соседний аэропорт.

С "неправильным" паспортом быть академиком значительно тяжелее. Например, на то, чтобы доехать до нипса, с момента принятия статьи даётся 76 дней. За это время почти ни в одной стране не записаться на американскую визу, это ещё не говоря про административную проверку, которая светит любому посетителю. Приходится стратегически посылать статьи в те места, до которых доехать можно проще, или мириться с тем, что презентовать свою статью придется доверить коллеге.

Channel created