Прошло почти два месяца с моего поста, и мы наконец выпустили официальный блог-пост про релиз TensorFlow-GNN 1.0 в рисёрч-блоге и блоге TensorFlow. За это время успели пофиксить пару багов совместимости (спасибо керасу), так что попробовать графовые сеточки стало ещё проще. Для самых нетерпеливых – ссылка на GitHub. 👆

Рассказал на мл-митапе в нашей деревне про графы и то, как их варим. ☕️

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

Let Your Graph Do the Talking: Encoding Structured Data for LLMs
[arXiv]

Что мы делаем в 2024? Правильно, засовываем всё, что плохо лежит 🗑, в большие языковые модели. У нас в команде плохо лежат графы, так что в нашей новой статье они отправляются напрямую в PaLM2. 👮‍♂️

Конечно, граф нужно как-то закодировать. У коллег была статья на ICLR'24 (или будет? конференция-то будет в мае), где граф трансформируют в текст простыми способами: как список вершин и рёбер. Вместо этого мы бахнули графовую нейросетку, которая трансформирует граф в набор токенов, которые кормятся LLMке. Поскольку нам хотелось полностью погрузиться в LLM-безумие, напрямую от задачи графовая сетка градиенты не получает – только через языковую модель. Назвали модель GraphToken. 👌

Поскольку мы работаем с графами, мы можем сгенерировать их все. На 8 вершинах существует 11117 связных графов, вот на них мы и тестировались. Тестсет – так уж на все точки пространства – чего мелочиться. ✨

В статье мы показываем, что GraphToken умудряется генерализоваться как in-distribution с 1000 тренировочных примеров, так и out-of-distribution – на новые задачи, очень слабо связанные с предыдущими.

P.S. в названии – отсылка к песне Aerosmith. 😎

Выпускаешь LLM-статью.
Ожидание: слава, богатство, ашиндекс под сотню. 👀

Реальность: от тебя отказываются экс-соавторы. 😮‍💨

29 февраля и 1 марта в нашей деревне пройдёт Learning on Graphs NYC meetup (анонс). В этот раз слово “деревня” я использую почти буквально, ведь любителям графов придётся переплыть через Гудзон, в Джерси-сити. ✝️

Я расскажу про побольше рисёрча и закину пару баек из прода. Если кто ещё не решился заниматься графами, приходите, будем переубеждать. 🦯

На просторах интернета набрёл на список неожиданных эпонимов и немного офигел. Из примеров:
· MySQL
· Debian
· Taco Bell
· Mars
· German chocolate cake
· Baker's Chocolate

Все названы в честь основателей. Особенно нельзя доверять вещам, связанным с шоколадом. Очень проклято. 🤬

Альтернативные раскладки клавиатуры

Эргономика – это штука, про которую почему-то мало говорят. А есть про что! Пару недель назад я начал замечать боль в пястно-фаланговом суставе мизинца, так что пришлось пройти экспресс-курс про эргономичную печать. В кроличью нору я залез по пятки, так что трамва подвезла контента дорогим подписчикам аж на несколько постов. 👆

Началось всё в конце 19 века с изобретением механической печатной машинки. Раскладку QWERTY – да-да, той, который мы пользуемся по сей день, можно увидеть в одном из оригинальных патентов. Кстати, популярная теория о том, что QWERTY была специально разработана для того, чтобы не заедали соседние буквы, скорее всего неверна (хотя коэволюция хард- и софтвера интересна всегда). Тем не менее, на QWERTY крайне неудобно печатать 🤬– очень часто приходится водить одним пальцем туда-сюда. Это называется same-finger bigrams, или SFB. Для примера попробуйте набрать слово `aluminum` – на QWERTY это делать очень больно. Наверное, можно придумать что-то получше. 💡

В славном 1936, когда Чёрч придумал лямбда-исчисление, а вся Европа съехалась на олимпийские игры в нацистской Германии, Август (не путать с Антонином) Дворак, профессор психологии, разрабатывает и патентует одноимённую раскладку. Это была первая попытка оптимизировать раскладку научным методом – Дворак много изучал распределения сочетаний букв (насколько было тогда возможно) и физиологию рук. Получилось неплохо, но рыночную конкуренцию с QWERTY выиграть так и не удалось.

С компьютеризацией всё больше возрастает число бездельников профессиональных стучателей клавишами. Colemak был создан в 2006 году Шаем Коулманом с целью быть безболезненной заменой QWERTY – например, все сочетания клавиш (Ctrl+Z,C,V) в Colemak такие же, как в QWERTY. С раскладки Colemak началась эра машинно-оптимизированных раскладок, коих сейчас существует множество – есть даже сабреддит /r/KeyboardLayouts, где и происходит сота-рисёрч. О метриках, оптимизации и прочем задротстве я расскажу уже в следующей серии. Успехов в наборе! ⌨️

Сегодня изучаю правила подачи налогов в США на сайте IRS. 📃

Из интересного там есть:

Illegal activities

. Income from illegal activities, such as money from dealing illegal drugs, must be included in your income on Schedule 1 (Form 1040), line 8z, or on Schedule C (Form 1040) if from your self-employment activity.

Stolen property

. If you steal property, you must report its fair market value in your income in the year you steal it, unless in the same year you return it to its rightful owner.

Bribes

. If you receive a bribe, include it in your income.

Можно подумать, зачем IRS отчитываться о полученных взятках, доходах от продажи наркотиков (включив, конечно же, в правильную форму, если вы продавали их на фрилансе!) и украденном добре? 🤔

Ответ довольно прост (попробуйте догадаться сами) – чтобы при недостаточном количестве других улик можно было посадить за уклонение от уплаты налогов. Аль Капоне в своё время посадили за уклонение от уплаты налогов. 👮‍♂️

Так что платим налоги и не совершаем преступлений, дорогие подпищеки. А если будете совершать, мне не рассказывайте. ✨

#book_review: "Moral Mazes" – Robert Jackall, 1988.
[на английском]

Выбери любую книгу по менеджменту с полки книжного магазина и она окажется нормативной. "Как заставить людей работать?" Бить. "Как менеджерить миллениалов?" Через тикток. И так далее. Moral mazes, в отличие от этой ценной (если застряли в лесу, а Verbascum thapsus под рукой не оказалось) литературы – книга социологическая, изучающая менеджеров как отдельную касту людей.

Джакал рассматривает тёмную сторону 🌚менеджмента – патронаж, отказ от принятия решений, сбрасывание ответственности и присвоение себе признания за любые успехи бизнеса.🤴 Неудивительно, что книга любима хактивистом Аароном Шварцем и популярна в среде т.н. рационалистов.

Материал к книге собирался в серии глубинных интервью на протяжении нескольких лет в (анонимизированных) производственных компаниях – химической и ткацкой – и паре более мелких. Автор скрупулёзно разбирает вопросы, свойственные менеджерской системе, которые, например, выливаются в омерзительные медиа-стратегии. Пример из книги – отрицание существования биссиноза. 😮‍💨

Из минусов – у Джакала не получилось написать простую книгу. Если кто-то любить читать сурово-академическую гуманитарную литературу, проблем не будет, если нет – придётся потеть. Приведу отрывок:

In short, bureaucracy creates for managers a Calvinist world without a Calvinist God, a world marked with the same profound anxiety that characterized the old Protestant ethic but one stripped of that ideology’s comforting illusions. Bureaucracy poses for managers an intricate set of moral mazes that are paradigmatic of the quandaries of public life in our social order. Within this framework, the puzzle for many individual managers becomes: How does one act in such a world and maintain a sense of personal integrity?

Как обитателю 🦠 корпорации, в которой менеджмент наконец-то взял под контроль инженеров, мне книга показалась очень ценной. Любителям почитать про карьеру первые 3-4 главы, или хотя бы краткое содержание в HBR, прочитать однозначно стоит.

На днях 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. 👆

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