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

Задача о минимальном линейном расположении графа (minimum linear arrangement) – это такая дедовская задача о том, как расположить элементы в матрицы смежности таким образом, чтобы привести матрицу смежности к блочно-диагональному виду.

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

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

Кстати, первый автор на днях психанул и основал стартап по созданию и анализу опросов. На основе кластеризации и упорядочивания графов, естестенно. 💁‍♂️

Сегодня узнал, что Хинтон – пра-правнук Джорджа Буля. Вот и не верь после такого в академические династии. 🤔

Пока я катался туда-сюда, у нас приняли ещё одну статью, на этот раз в TMLR. Называется “Tackling Provably Hard Representative Selection via Graph Neural Networks”.

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

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

Доказанная в работе сложность – неподъёмная, так что приходится искать прокси-метрики для оптимизации. Мы предложили новый подход на основе графовых нейросетей, который очень сильно докидывает, когда у нас есть информация в виде структуры графа. 🤴

В реальном мире, конечно, графы есть не везде, но и тут мы показываем, как бить сильные бейзланы: можно просто построить kNN граф и всё заработает. 💁‍♂️

Ну вот и коучи по бросанию полотенец промптингу подъехали. Надеюсь, хотя бы в колесо баланса промпт раскладывает.

Хэндл AGI Utopia тоже доставляет.

P.S. Нет, аккаунт не пародийный 😮‍💨

Я тут попробовал новый для себя формат публичных выступлений – мы с Надей записали интервью со мной. Оно не техническое от слова совсем: поговорили про работу 😛, моё отношение к кофе 🙅‍♂️, вспомнили и пост про женихов.

Возможно, кому-то такой формат будет интереснее, чем буковки в телеграм-канале. Мне пока непонятно, что лучше – буковки можно переписывать, зато общение в риалтайме как-то поживее. 😟

UPD: для любителей не смотреть ✨, но слушать – ссылки на подкаст на амазоне, спотифае, apple подкастах, и ютьюбе.

Загуглил temperature, не понял, почему выдача не про софтмакс. Кажется, пора отдыхать 🤤

Не все доверительным интервалы одинаково полезны

Возвращаемся к техническим постам после научных каникул напряжённой летней работы. 🏄‍♂️

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

Один из самых известных тестов для этого – тест Вальда. Он до сих пор рекомендуется для биномиальных респределений во многих учебниках, например, в известном Casella & Berger. Однако, именно для биномиальных пропорций тест Вальда – очень плохая идея. 📉

В других учебниках часто пишут про потерю силы на маленьких выборках, но основная проблема теста в том, что он теряет силу с приближением параметра p к 0 или 1 из-за эффекта Hauck–Donner, что можно увидеть на иллюстрации к посту. Про этот эффект есть несколько статей, ну или можно почитать более простую, которая недавно вышла в Teacher's Corner журнала The American Statistician. Там призывают перестать использовать тест Уилсона. Формула там подлиннее, зато нет проблем с покрытием. 🍳

Кстати, интересно, что у других тестов вроде Agresti–Coull и Clopper–Pearson покрытие слишком консервативное (для Clopper–Peason это неудивительно, потому что покрытие там строго больше 1-α). Вот тут есть сравнение покрытия этих тестов с кодом на R (🤮).

Сейчас понял, что объясняю эмбеддинги графов как word2vec на графах, а в 2023 никто уже и не знает, что такое word2vec. 😮‍💨

Получается, поеду на NeurIPS презентовать статью трёхлетней давности, на которой 100+ цитат. Ноука. 🥛

В твиттере Джона Грина проскочил интересный вопрос – похоже, люди сильно различаются по способностям визуализировать разные вещи. Многие люди могут спокойно представить себе “картинку” объекта со всеми его свойствами, тогда как у других получится только представить концепт этого объекта, без конкретных признаков. 🤤

Интересно, как это работает у дорогих подписчиков.

На HackerNews завирусилось, что мы релизнули кусок библиотеки для анализа графов. Поскольку документации в релизе особо нет (🤦‍♂️), хочу быстренько рассказать, что там вообще сейчас есть и что будет.

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

Во-вторых, основной кусок, который заопенсоршен – про кластеризацию. У нас довольно хорошо работает иерархическая кластеризация, есть статьи на ICML/NeurIPS [1, 2, 3]. Вот её и постарались опенсорсить в первую очередь – в sklearn дай боже получится кластеризовать датасет на 20к вершин (😮‍💨) а у нас получается миллиард. 📈

До конца года хочу выпустить наш код для in-memory эмбеддингов туда же. Будет быстро, обещаю. ✨

На днях вышла интересная статья Vision Transformers Need Registers.

Vision Transformers (ViT) – одна из основных современных архитектур для больших vision-моделей. В отличие от счёрточных нейросетей, она отлично model-параллелится, так что получается эффективно тренировать большие модели, которые хорошо работают на практике. 🥁

Проблема в том, что на attention масках получаются какие-то непонятные артефакты (см. картинку) в виде пикселей с очень высокими коэффициентами. Авторы статьи решили почесать репу и разобраться, какую функцию они выполняют и как от них избавиться. 🧐

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

Мне кажется, хороший пример научного подхода ко всей этой нашей машинлёрнинговой алхимии – авторы нашли странный феномен в моделях, выяснили, как он работает, пофиксили, получили прирост на бенчмарках. 📈

Открылысь заявки на Student Researchers, Ph.D. level в наш уютный Google Research. Student Researchers – стажировки для Ph.D. первых нескольких лет, которые хотят себя попробовать в индустриальной лабе. 🤓

Очень Важно™ подаваться на стажировки прям на самом открытии – так вы сильно увеличиваете шанс на попадание 📈. Дополнительно поможет подаваться во все интересующие страны, ну и озаботиться получением реферала, конечно же.

В этом году мне дали research intern – чуть более опытного Ph.D. ближе к выпуску. Как co-host я успел поработать с двумя студентами-исследователями, и разницы в программах для них особо не заметил.

Удачи с подачами! ❤️

Наткнулся на миленький гайд по преодолению тревожности в занятиях математикой. Несколько пунктов, которые мне показались интересными:

1. Люди не делятся на “математиков” и “не-математиков”. Ей можно заниматься или не заниматься.

2. В школе и университете мы привыкли заниматься математикой на скорость – решать тесты и задачи на время. В реальной жизни редко когда важна скорость решения задачи (если вы не в хеджфонде работаете, конечно 📈).

3. Мы часто думаем, что в математике, в отличие от гуманитарных наук, есть только два типа ответов: правильный и неправильные. На самом деле, прийти к правильному ответу можно множеством разных путей. 💡

Мне кажется, в России особенно токсичное отношение к “чистоте” математики. Как вы с этим справляетесь, дорогие читатели?

Пока мудрые мысли меня не посещают, ловите немудрую. 🤤

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

Посмотрел на распределение солнечных часов в трёх городах, где я пожил достаточно долго – и точно, Нью-Йорк чуть ли не в три раза солнечнее зимой, чем Берлин. Москва зимой – это отдельный вид серых будней. Дубай не показываю, потому что там я на улицу днём почти не выходил. Всё-таки климат – не солнышком единым. 😎

Вот такой фактор выбора места дли жизни, который вам не покажут на numbeo. Интересно, есть настолько прямое влияние погоды на характер, или "Россия для грустных" – это совпадение? 🤔

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

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

1. Aeon (я читаю только раздел эссе) публикует эссе от около-академиков о философии, науке, истории и искусстве. Там можно узнать, почему английский язык такой странный или почему не стоит сравнивать мозг с компьютером. 🤓

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

У Aeon’а есть отдельный сайт про психологию – Psyche с фокусом на психологию и этику. Например, там можно найти толковый гайд про то, как бороться с синдромом самозванца.

2. Quanta много пишет про передовые исследования в естественных науках и компуктер саенсе. Примеры статей:
🙌 "New Proof Shows That ‘Expander’ Graphs Synchronize"
😏 "Complexity Theory’s 50-Year Journey to the Limits of Knowledge"

Quanta поддерживается клёвыми Simons foundation – если не слышали, они поддерживают несколько исследовательских центров в США, создали Flatiron Institute в Нью-Йорке, и вообще максимально эффективно спонсируют науку.