Выпускаешь 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. 👆

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

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

Насколько глубокая математика нужна для 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 на полную, с такой мощностью источник питания видеокарты не справляется, и частота снижается (троттлится), снижая скорость вычислений. Если мы забиваем матрицы нулями, это позволяет большему количеству транзисторов не менять своё состояние, увеличивая производительность. Больше деталей – в блогпосте автора.

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