На днях Adrian Dumitrescu
опубликовал препринт статьи “A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications”. Это довольно удивительный теоретический результат, где существенно ускоряется то, что интуитивно ускоряться не должно: поиск треугольника в графе. Как модно в последние годы, алгоритм вероятностный, но это не мешает порушить сразу несколько гипотез, на которых полагалась куча статей:

- the O(n^7/3) runtime surpasses the long-standing fastest algorithm for triangle detection based on matrix multiplication running in O(n^ω)=O(n^2.372) time, due to Itai and Rodeh (1978).
- the O(m^4/3) runtime surpasses the long-standing fastest algorithm for triangle detection in sparse graphs based on matrix multiplication running in O(m^2ω/(ω+1))=O(m^1.407) time due to Alon, Yuster, and Zwick (1997).
- the O(n^7/3) time algorithm for triangle detection leads to a O(n^(25/9)logn) time combinatorial algorithm for n×n Boolean matrix multiplication, by a reduction of V. V. Williams and R. R. Williams (2018).This invalidates a conjecture of A. Abboud and V. V. Williams (FOCS 2014).
- the O(m^4/3) runtime invalidates a conjecture of A. Abboud and V. V. Williams (FOCS 2014) that any combinatorial algorithm for triangle detection requires m3/2−o(1) time.
- as a direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the k-clique problem, surpassing an almost 40 years old algorithm of Nešetřil and Poljak (1985). This result strongly disproves the combinatorial k-clique conjecture.
- as another direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the Max-Cut problem, surpassing an almost 20 years old algorithm of R. R. Williams (2005).

Если результат подтвердится, существенно подвинутся по сложности алгоритмы, которые основаны на булевом перемножении матриц. Запасаемся попкорном на следующие FOCS/STOC. 🍿


EDIT: похоже, в статье всё-таки есть проблемы, прекрасного будущего не ожидается. 😟

Мне интересно тестировать большие языковые модели на теоретическом компьютерсаенсе. Для этой статьи Clause 3 Opus корректно находит ошибку в алгоритме, если подсказать, где искать. У людей пока выходит лучше, но то, что модель вообще смогла найти ошибку, очень воодушевляет! 💪

Запись доклада. ✨
Постараюсь дописать пост про раскладки на выходных.

Дизайн собственной раскладки: подход

Буковок на тему клавиатур получилось очень много, поэтому выход один – бить 🦯 на посты. Для начала – дисклэймер: всё, что написано дальше (и в следующих постах) – моё ИМХО. Сколько людей – столько и мнений. Второй дисклэймер: оптимизация раскладки – это сугубо мой хобби-проект, к реальным проблемам имеющий довольно отдалённое отношение.

SotA в эргономичных клавиатурах последние несколько лет – низкопрофильные ортолинейные сплит-клавиатуры типа ZSA Voyager. Если хочется максимизировать эргономичность в ущерб портативности, можно смотреть в сторону Glove80. Для себя я выбрал Corne с Kailh Choc свитчами из-за возможности беспроводного использования. На картинке к посту – именно она. ❤️

Как видим, оптимизировать почти нечего! В Corne цифры спрятаны на отдельный слой, который вызывается по специальной клавише. Вообще говоря, слои – довольно интуитивная штука, например, никого не смущают символы !@#$% поверх цифр 12345, так что научиться ими пользоваться несложно.

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

В итоге получилось сформировать задачу: оптимизируем расположение 30 символов – [a-z] и ,./; на прямоугольной решётке размером 3×10. Оптимизация комбинаторная, никакой выпуклостью там и не пахнет даже для довольно простых метрик. А вот как с такими задачами работать, расскажу в следующей серии. 👉

Дизайн собственной раскладки: данные

Предыдущие части: экскурс в историю, общий подход.

Прежде чем погрузиться в метрики, их на чём-то нужно считать. Как мы знаем, много данных = стабильные метрики, сходящаяся оптимизация, достаток и процветание 🤴. Датасет хотелось подготовить самому, не у Норвига с Карпатым же брать. Изначально мне хотелось собрать статистику с датасета архива, но выкачка данных там только с Amazon S3 за свой счёт, да и формат довольно всратый. В итоге я остановился на Reddit-е, дамп которого с недавних пор (клятые LLMки 🤬) доступен только с торрентов. В сумме сжатых данных получается 2.5Tb, что с комфортом процессится на домашнем компьютере.

Для обработки за пару часов с помочью ChatGPT и такой-то матери был написан и отлажен простенький шелл-скрипт, который читает файлы с помощью jq и считает комбинации букв на awk. Особенно хочется отметить jq – он делает работу с JSONами суперприятной – всякие сложные селекты отрабатывают максимлаьно быстро 📈 без противного парсинга. Файлики с результатами я выложу в комментариях. В следующий раз поговорим о метриках и, наконец, оптимизации. ✨

Сегодня поздравим с днём рождения Славоя Жижека и, заодно, автора канала. 😛

Пожелаем закончить серию статей про чёртовы клавиатуры и наконец-то начать писать про интересные статьи.

Дорогие подписчики могут порадовать (если не завалялось парочки Blackwell), забустив канал – если наберётся достаточно желающих, введу на канале официальные лягухо-реакшены. 🙌

Без громких анонсов 🚨 команда Google Scholar пару дней назад выпустила расширение, которое существенно упрощает чтение статей, не отвлекаясь на поиск референсов. Я на нём сижу уже пару месяцев, очень удобно, что такое доступно в хроме, без отдельного громоздкого приложения. Скачать можно тут. 👍

Дизайн собственной раскладки: метрики
Предыдущие части: экскурс в историю, общий подход, данные.

Сколько людей, столько и метрик. Я, на свой вкус, собрал лучшее 🤴 из этого мира. На картинке к посту – интерактивный анализатор от cyanophage, как по мне, один из самых достойных. Из других интересных ресурсов есть мега-документ на 180 страниц 🥁. Всего получилось ~10 комплементарных метрик. Я опишу 6 главных из них и покажу одно из слов, которые её максимизируют (в QWERTY-раскладке). Поехали! 🏄‍♂️

1. Same Finger Bigrams (SFB) – последовательное нажатие клавиш одним пальцем, особенно, когда ему приходится перескакивать через две строки. Примеры: unfunny, aluminum.

2. Pinkie / ring scissors – количество неудобных движений мизинцем и безымянным пальцами, когда мизинцу приходится тянуться вниз или наверх. Примеры: example, throwaway.

3. Skip bigram ratio – количество перескакиваний через две строки. Одна из важных метрик, потому что движение кистей рук в основном зависит от количества таких перескакиваний. Чтобы прочувствовать, попробуйте набрать service или recently.

4. Lateral stretch bigrams – количество перескакиваний для указательных и средних пальцев. Хотя указательный палец – самый мобильный, перегружать его тоже не стоит. Примеры: beginning, thinking.

5. Redirects – количество перенаправлений набора триграмм. Например, asd печатать на QWERTY очень удобно, а вот ads – нет. Примеры неприятных слов: starcraft, interstate.

6. Rolls – упрощённо, количество наборов клавиш-соседей, например, re или as. В отличие от предыдущих метрик, набор соседей – дело довольно приятное, так что его мы будем максимизировать. Примеры удобных слов: powered, remastered.

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

В прошлом году я писал про книгу Ави Видгерзона, которую очень люблю. Сегодня он получил премию Тьюринга, с чем его и поздравим! 💐

Мне в личке задали вопрос, ответ на который, как мне показалось, может заинтересовать дорогих подписчиков. Вопрошают следующее (перефразировано):

Насколько глубокая математика нужна для ML ресерча, что чаще всего приходится использовать? Например, нужно ли знать какие-нибудь сложные дифуры или тензорные вычисления необходимо, может какие-то специфичные теоремы из мат. анализа или теории оптимизации? Или быть может "базового" набора хватает?

Как не написано в приветственном посте о себе (ой), до PhD я учился в ныне-подсанкционном Сколтехе, а ещё раньше – на факультете бизнес-информатики (тепереча кличущаяся высшей школой бизнеса) НИУ ВШЭ. Заглянем в диплом бакалавра: на тройку сдана дискретная математика и линейная алгебра, на четвёрку – мат. анализ. В магистратуре были сданы линейная алгебра и методы оптимизации на четвёрочки. Это – полный список курсов. Если честно, я вообще не помню, что в сколтехе были опты. 🎒

Из этого почётного списка должно было стать понятно, что формального математического образования у меня меньше, чем у авторов многих уважаемых телеграм-каналов. Конечно, иногда хочется быть Терри Тао и зарешивать одну нерешённую проблему за другой 🤴. На практике, приходится довольствоваться интуитивными знаниями о системах, с которыми работаешь. Для развития интуиции хорошо работают задачки Ферми, где нужно прикинуть какое-то значение при довольно грубых приближениях. Из того, что мне понадобилось сегодня – “сколько проекций нужно LSH для достижения нужной полноты (recall) поиска?” 🧐

Машинное обучение – область науки с ярко выраженными теоретическими и инженерными составляющими. Хочешь – доказывай теоремы про VC-размерность, хочешь – пили сота-модели на исключительно инженерных трюках. Между этими крайностями – много возможностей для того, чтобы сделать более или менее практический вклад в науку. У разных конференций разный фокус – на ICML будет чуть меньше чисто-практических статей, на NeurIPS – больше. Из того, что я вижу – хорошие исследователи получаются из тех, кто не стесняется разбираться в данных и моделях – примерно как Андрей Карпатый, который пишет LLMки на C или Chris Olah, который развивал distill.pub. 🫡

Мне кажется, невозможно заранее знать всю математику для всего MLя: сегодня нужна теория игр для GANов, завтра – диффуры для диффузионок, послезавтра – арифметику для LLMок. При этом не знать совсем ничего – точно не полезно! Обычно у исследователей нарабатывается какой-то математический инструментарий, который используется для написания статей. Если выбрать что-то одно, мне кажется, что вычислительная линейная алгебра (включая мои любимые вероятностные алгоритмы) – один из наиболее универсальных инструментов.

У рисёрчера нет цели, есть только путь до ближайшей конфы на багамах. Если для статьи нужна какая-то математика, в ней всегда можно попробовать разобраться, ну или найти соавтора ☺️, они для того и нужны.

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

На эту тему написано множество книг (и ещё больше телегам-постов), но, надеюсь, моя точка зрения кому-то приглянется. Нижеприведённые качества обычно вырабатываются у людей за Ph.D., но, как мне кажется, их можно осознанно тренировать. Как? Записывайтесь на мои курсы осознанности.

Во-первых, (этот пойнт был и в предыдущем посте, но кто ж меня читает) у всех отличных исследователей, кого я знаю, есть неутолимая тяга разбираться в предмете. Где в модели не текут градиенты? Откуда берутся артефакты на картинках? На каких примерах происходят ошибки? Сходится ли модель на игрушечных данных? Последний вопрос – мой любимый; хочется уделить ему особое внимание. Дело в том, что в машинном обучении чаще всего вот эти вот все "настоящие данные" с "ground truth"ом – это всё дикий шумный лес, за которым порой бывает сложно разглядеть, куда, собственно, надо улучшать метод. 🤔

Приведу пример из одной из моих статей. Писал я её в ковидном заточении ⛓, когда я увидел на архиве статью под названием "Mincut pooling in Graph Neural Networks" (почему-то после публикации моей статьи её переименовали в куда более модное "Spectral Clustering with Graph Neural Networks for Graph Pooling" 🤔). Я начал играться с их лоссом, но на некоторых графах он у меня не сходился. Для дебага я написал простенький генератор синтетических данных – две гауссианы и k-NN граф на их основе – такой должен хорошо кластеризоваться. Потыкав с генератором, я заметил, что на нецентрированных данных MinCut лосс из статьи не работает. После этого достаточно было разделить лосс на две компоненты и посмотреть, как они оптимизируются в процессе обучения, чтобы понять, что в их статье (шок) никакой кластеризации графа не происходит – происходит только ортогонализация фичей вершин. Это позволило мне понять, куда копать, и написать неплохую статью, которую после трёх лет страданий всё же опубликовали в JMLR. Эти эксперименты, конечно, в финальную версию статьи не прошли.

Во-вторых, это умение отделять зёрна от плевел (pop quiz: кто помнит, кто такие плевелы?) в чужих статьях. Такое вот умение читать между строк и сквозь них 🤔 – вот это утвеждение сделано потому что авторам нужно было что-то сказать или они и правда проверили все остальные альтернативы? Правда ли в этом месте нужен вот этот компонент или его ввернули ради красивой теоремы в аппендиксе? Звучит довольно очевидно, но слишком часто мне приходится разубеждать инженеров, которые вычитывают в литературе какую-нибудь неподтверждённую дрянь и кидаются её реализовывать.

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

Horace He (блог) – товарищ из команды питорча, который очень любит неожиданные микробенчмарки. На картинке – обычное матричное умножение на обычных A100, вот только почему-то для более "простых" данных вроде разных констант или нулей производительность существенно быстрее, почти на треть. Для любителей подумать 🤪 перед ответом – код для воспроизведения, а ответ – под спойлером ниже.

По заветам Данилы Багрова, правда в силе (тока). В смысле, в энергопотреблении. ⚡️ Дело в том, что транзисторы в GPU потребляют существенно больше электричества, если они меняют своё состояние. Если мы используем весь GPU на полную, с такой мощностью источник питания видеокарты не справляется, и частота снижается (троттлится), снижая скорость вычислений. Если мы забиваем матрицы нулями, это позволяет большему количеству транзисторов не менять своё состояние, увеличивая производительность. Больше деталей – в блогпосте автора.

Железо порой интереснее, чем все эти ваши новомодные нейроархитектуры. 👌

#book_review "Праведный разум" – Джонатан Хайдт, 2012.
[на английском]

Почему мы не можем аргументированно спорить на политически заряженные темы? Как мы принимаем суждения о моральности тех или иных вещей?

Хайдт – профессор, хоть и этики бизнеса 🤑, но с ашиндексом, которому позавидуют светила машинного обучения. К сожалению, он – автор нескольких книг, написанных в типично-американском научпоп-стиле. Кто-то когда-то придумал, что каждую идею надо заворачивать в метафору, а потом повторять на десяти-пятнадцати примерах в течение книги – и вот тогда уж люди поймут и запомнят! "Праведный разум" – из этой серии, хоть и начинается с увлекательной истории о том, как белый привилегированный автор 🏳️‍🌈 в своё бытиё студентом узнаёт, что вообще-то есть общества с другими системами ценностей. 🧐

При этом я не могу сказать, что книга настолько плоха. Скорее, даже наоборот – беглым поиском мне не удалось найти ни одной негативной рецении! Но что-то – возможно, повторения, возможно – чрезмерные упрощения – всё-таки не даёт расслабиться и получать удовольствие ☺️. Чтобы не быть голосоловным, зафиксирую конкретную критику. Теории, представленные в книге – дескриптивные, предсказания по ним делать сложно, а вот консалтерских слайдов (или статей, тут по вкусу) наклепать – пожалуйста. Во-вторых, Хайдт выделяет несколько моральных столпов, на которых зиждется интерсубъективное понятие морали (тут всё очень по Дюркгейму, графы так и просятся). Только вот откуда они берутся? Ах, это мы объясняем в статье, а методология там – "как в лучших домах ЛондОна". Ну и считать читателей за дураков, которым надо повторять всё по нескольку раз, я повторю, неуважительно.

Короче, 3/5, дорогие подписчики, можно найти много занятий лучше. Всем поменьше повторяться. 🦯

Долго не получалось ничего писать, так что начинаем исправляться начиная с сейчас!

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

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

🏳️‍🌈. Нашу работу над способностями Gemini в математике показали на Google I/O. Про 91% на Hendrycks MATH порадовался даже Сундар – три года назад модели выбивали на этом бенчмарке всего 6%.

🎩. Канал зафичерили в sci_career, так что дорогим подписчикам теперь придётся иногда слушать про карьеру.

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

Классы алгоритмической сложности для трансформеров

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

Про трансформерные модели мы знаем довольно много: они Тюринг-полные – правда, при polylog-числе слоёв, а при константной глубине они ограничены классом TC0. Это всё, конечно, очень интересно 😐, но хочется изучать трансформеры в более реалистичных сценариях.

Вот тут на сцену выходим мы🤴! В статье мы анализируем девять графовых алгоритмов 👥, которые трансформеры решают в трёх разных режимах параметров. Под параметрами в статье понимаем ширину слоя m, глубину сети L, и аналог chain-of-though токенов, которые позволяют модели покряхтеть над задачкой подольше. 🤔

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

Совсем простые задачи 😛, например, как подсчет узлов или рёбер, могут быть решены трансформерами глубины один с шириной log 𝐍. Трансформеры также могут выполнять параллельные алгоритмы - мы нашли три задачи, которые могут быть эффективно решены с помощью трансформеров глубины log 𝐍.

А ещё на графах мы можем сравнить трансформеры с графовыми нейросетями. Теоретически мы показываем случаи, где трансформерам нужно меньше вычислений для решения разных задач, и на практике показываем, как с некоторыми алгоритмическими задачами трансформеры справляются лучше GNNок. Да, практическая часть в статье тоже весёлая – мы попробовали посравнивать трансформеры, натренированные для конкретной задачи с файнтьюненными LLMками! А получилось – читать продолжение в источнике…

Статья получилась жирная 🥁 на теоремы и эмпирику, но, надеюсь, кому-нибудь да понравится.

G-RAG: готовим графы знаний правильно

Вторая статья, вышедшая на той неделе – про retrieval-augmented generation (RAG). Конечно же, со вкусом графов – куда ж без них?

RAG – это такой лейкопластырь, которым мы залепливаем проблему контекста в языковых моделях. Поиск мы умеем делать довольно неплохо, поэтому давайте-ка прикрутим поиск к LLMкам и будем всем счастье – ну, то есть релевантные ответы, актуальная информация, вот это вот всё.

При этом всём, information retrieval (IR), заточенный на людей, для LLMок подойдёт как минимум неидеально: люди читают первые пару заголовков, а LLMки могут прожевать десяток-другой статей (если не Gemini 1.5 с миллионой длиной контекста, конечно).

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

Тут нужно лирическое отступление на тему графов знаний. Я эту дедовскую 👴 идею про идеально точное и полное описание сущностей отрицаю всей душой и сердцем. Ни у кого в мире не получилось построить корректно работающий граф знаний, и полагаться на одну статическую структуру для такой динамической задачи, как вопросы в свободной форме – тотальный харам. Поэтому вместо статического графа у нас динамический, который мы на этапе запроса строим по документам, которые наш ретривер вытащил на первом этапе. Это можно делать очень быстро, потому что графы по каждому документу мы можем посчитать заранее, а на этапе запроса их слепить вместе. ☺️

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

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

Надо сделать тортик. 🥁

Test of Time: A Benchmark for Evaluating LLMs on Temporal Reasoning

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

Существует несколько работ, которые меряют способности ЛЛМок рассуждать во времени на каких-нибудь реальных фактах (чаще всего из Wikidata), но так мы не можем понять, откуда пришёл правильный ответ – из памяти или при помощи рассуждений. Пример на картинке выше – ЛЛМка корректно отвечает про футбольного тренера, но с треском проваливается, если в той же задаче заменить сущности на анонимизированные айдишники.

На нашем бенчмарке Gemini 1.5 Pro обошёл GPT-4 почти во всех категориях. Может, модель всё-таки хорошая? 🧐