Self-Consuming Generative Models Go MAD [2023]

Существует большой спектр ожиданий от текущего поколения AI. С оптимистичной стороны собрались сливки человечества. Там находятся авторы AI-фанфиков (таких, как ai-2027.com), описывающие с точностью до месяца события мирового масштаба на 2.5 года вперёд. Там находятся говорящие головы, подрабатывающие CEO, и думающие, что через 3-6 месяцев AI будет писать 90% кода (месяц уже прошёл). Сегодня мы с вами взглянем на ситуацию с противоположной стороны.

Первым шагом обучения любой современной модели является гигантский pretrain. Модели обучают предсказывать следующий токен в последовательности на всём интернете. До 2020 почти 100% контента на естественном языке создавали люди, но с появлением вменяемых моделей всё больше и больше контента начинает генерироваться нейросетями. В процессе продвижения knowledge cutoff вперёд всё большую долю данных в претрейне будет составлять синтетический контент. Опасно ли это?

Попытку исследовать этот вопрос провели авторы сегодняшней статьи. В ней они проводили эксперименты над генеративными картиночными моделями, обучаемыми на фотографиях лиц. Рассматривалось 3 сценария:

Fully Synthetic Loop - модель каждого следующего поколения обучается только на синтетическом датасете из предыдущего поколения.
Synthetic augmentation Loop - модель каждого следующего поколения обучается на синтетическом датасете из предыдущего поколения и на фиксированном реальном датасете.
Fresh Data Loop - модель каждого следующего поколения обучается на синтетическом датасете из предыдущего поколения и на свежем реальном датасете.

Также оценивалось влияние sampling bias. В контексте ганов это обрезание хвостов нормального шума, в контексте языковых моделей эту роль, пожалуй, играет температура. Sampling bias помогает увеличить среднее качество сэмплов, жертвуя при этом их разнообразием.

И в Fully Synthetic Loop, и в Synthetic augmentation Loop (в нём доля синтетики была 50%) модель деградировала со временем. Во втором случае она предсказуемо деградировала медленнее. Усиление sampling bias замедляло падение качества, но пагубно влияло на разнообразие результата.

Сценарий с Fresh Data Loop показал более интересный результат. Итак, на каждом шаге мы дообучаем на n_r новых реальных картинках и на n_s генерациях с предыдущего шага. Качество модели в рамках этого процесса сходится к точке, которая зависит от этих 2 параметров и не зависит от первого поколения датасета.

Важно, что наличие синтетики улучшает качество в этом случае, но до какого-то предела. То, полезна ли она, определяется тем, получается ли в результате процесса модель, которая лучше, чем простая модель, обученная на n_r.

Оказывается, на это сильно влияет тот самый sampling bias. При его наличии полезность синтетики становится отрицательной выше какого-то порога, причём, этот порог не увеличивается пропорционально n_r, скорее, является константой. К сожалению, авторы берут не сильно большой диапазон параметров в этих экспериментах, но у них получилось так, что при отсутствии sampling bias синтетика вообще не вредит, даже при доле в 90%.

Конечно, на основе этой статьи нельзя делать точные предсказания будущего. Однако, глядя на текущий интернет, у меня всё же возникают опасения. Люди загружают в него всё больше и больше синтетического контента, и смысл создавать его руками лишь падает со временем. Подавляющая доля постов в соцсетях, комментариев, а со временем и картинок будет создана автоматически. Sampling bias люди используют на всю катушку, пытаясь выдать более качественный результат. Теоретически, всё это может привести к серьёзной деградации результатов претрейна с течением времени.

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

@knowledge_accumulator

Каким должно быть нормальное метро?

Я слышал лишь один раз, как кто-то восхищался метро в Лондоне - это был мой коллега из офиса в Нью-Йорке. Оно и понятно - там оно почти неотличимо от локаций из Метро 2033, причём, мутанты-NPC там тоже присутствуют.

Вчера сформулировал список базовых критериев качества нормального метро. Жители Москвы посмеются - для них это скорее норма жизни. Многие иммигранты не согласятся, но это в чистом виде говнохранительство, они и закрытие в магазинов в 5 вечера будут оправдывать.

Итак, 3 ключевых критерия:

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

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

Безопасность
В метро не должны пускаться бомжи, наркоманы, бухие. За любое отклонение от правил пользования - громкую музыку, курение, крики, кидание мусора на пол, должны выпиздывать ссаными тряпками.

Менее критичные пункты, но всё ещё очень важные:

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

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

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


А возможно ли всё это? Может быть, я просто мечтаю о неосуществимом? Если в городе в принципе нужно метро, то уверен, что да, объясню, почему:

1) Практически всё это присутствует в Москве. Если это возможно там, значит, возможно и в других местах.
2) Современный общественный транспорт принадлежит государству, то есть является монополией. Конкуренция - это единственное явление, которое толкает компании улучшать свой сервис. Так как её нет, то и на итоговый результат всем насрать.
3) Подавляющее большинство людей - долбоёбы. Абсолютно уверен, что если бы метро управлялось умными людьми, которым не всё равно, то все эти пункты были бы без проблем обеспечены. К сожалению, опять же, из-за отсутствия рыночных механизмов никакие стимулы к этому не толкают.

Если меня читают пользователи в Азии, расскажите, пожалуйста, насколько в ваших странах метро соответствует моим базовым критериям качества?

@knowledge_accumulator

Какие жизненные уроки можно вынести из Balatro?

Итак, суть игры. У вас есть колода карт. Каждый раунд состоит из нескольких рук - из колоды вы достаёте 8 карт и должны выбрать до 5, составляющих покерную комбинацию.

За комбинацию дают 2 награды - Chips и Multiplier. Чтобы посчитать итоговую стоимость руки, они умножаются друг на друга. Цель раунда - набрать за несколько рук N очков.

С каждым раундом N растёт, усложняя задачу, но тут в игру вступают разнообразные механики прокачки. Основная из них - это 150 различных Джокеров. Покупая их, они кладутся в отдельное хранилище и предоставляют бонусы, тривиальный пример - «+100 фишек за флеш». Помимо джокеров можно докупать карты в свою колоду и другие усиления.

«Победа» наступает после прохождения 24 раунда, в котором вы набираете около 200к очков. Но после него игра не заканчивается, а предлагает бесконечный режим.

И тут происходит что-то странное. На 29 раунде нужен миллион, а на 32-м 15 миллионов. Убившись пару раз, я пошёл гуглить - а что там дальше? Оказывается, игра принимает неожиданный поворот - с каждым раундом очки будут расти не то, что экспоненциально, а как экспонента от квадрата. На 115 раунде вас ждёт неминуемая гибель - требуемые очки выходят за пределы Double - 10^308.

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

Джокер «Барон» умножает мультипликатор на 1.5 за каждую карту короля, которую вы держите в руке после выбора комбинации. В комбинации с другими джокерами, которые копируют его эффект и подобными, после модификации колоды таким образом, чтобы она целиком состояла из одних королей со специальными бонусами, добавляющими еще больше умножений на 1.5, игроку легко понять, как выглядит колода, дающая минимум 10^25 очков.

Ваша жизнь в Balatro делится на 2 фазы. В начале вы всеми правдами и неправдами пытаетесь пережить как можно больше раундов, параллельно подготавливая почву для Барона, чтобы в ключевой момент резко отбросить весь балласт и начать свой экспоненциальный взрыв.

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

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

В то же время, если у вас есть миллион при доходе в 100к в год, то зарплата будет давать примерно тот же доход, что и рост купленного на этот лям S&P500.

Но инвестиции в S&P500 требуют нулевых временных затрат, так что, в этот момент вы можете выйти на пенсию и стать Гусиным фермером. Но можно ли ускорить экспоненту, прилагая усилия?

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

Лёгкого и очевидного способа нет - на открытом рынке все доходности равномерно распределены и индекс является оптимальным способом заработка на нём. Нужны альтернативные опции.

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

Другая опция - повышать риски. Производить кокаин, создавать свою ОПГ или быть стартапером - всё это повышает потолок вашей доходности, в то же время вводя возможность легко все потерять. Можно ли набраться опыта и стать стартапером с высоким мат. ожиданием прибыли? Мне неизвестно.

Всем хорошего High Score!

@knowledge_accumulator

О, дивный новый мёртвый Интернет

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

В прошлом январе вышла статья, где авторы попытались проанализировать масштабы использования машинного перевода в интернете, и после довольно изощрённых манипуляций смогли сгруппировать 57% текстов в группы, вроде как порождённые машинным переводом на 2+ языка. На мой взгляд это всё достаточно мутно, но журналюгам это не помешало понести в интернет заголовки "57% интернета сгенерировано AI".

К сожалению, строго измерить долю присутствия AI в интернете едва ли будет возможно. Мы можем лишь субъективно наблюдать за его наличием в разных сценариях с различной степенью очевидности. Итак, какие ловушки в интернете оставил для человечества Skynet?

AI-кликбейт в фейсбуке
Не обязательно в фейсбуке, но там это приняло наибольшие масштабы, поскольку именно там сидит более возрастная аудитория (как в Одноклассниках), которая не сильно в курсе текущей генеративной революции. Забайтить бабок на лайк и комменты весьма просто, проаппелировав к самым базовым человеческим эмоциям. Смешной обзор на такого рода контент можно найти здесь.

AI-тексты
Цена генерации текста на любую тему по любому запросу упала практически до нуля. Я думаю, уже очень скоро все тексты, которые не написаны каким-то верифицированным источником (например, мной в этом канале), можно будет считать AI-кликбейтом. Представляю ситуацию, в котором на каждый запрос в гугл вида "прыщ на затылке" у вас будет по статье о раке мозга 4 стадии, заботливо сделанной для зарабатывания 3 копеек с показа рекламы.


Но самое опасное оружие AI на данный момент - это видео. Если вы пользуетесь какими-то рекомендациями - например, тиктоком, если в нём вы залипните на пару раз в AI-контент, рекомендательная система подцепит это и начнёт кормить вас этим бесконечно, отравляя мозг и в конечном счёте убивая ваш пользовательский опыт. Они бывают разных видов:

Бомбардиро Крокодило
Такого рода персонажи, как он и Тралалело Тралала - это новая реинкарнация Skibidi toilet, но более страшная, поскольку не ограничена в своих объёмах. Жду не дождусь посмотреть на детей, которые будут начиная с 2 лет по несколько часов в день смотреть это творчество в планшете, пока родители заняты какими-то важными делами.

Видео-тексты
Как превратить текст в видео? Весьма просто. Берём какое-нибудь видео с игрой в Minecraft или в Subway Surfers, сам текст озвучиваем с помощью какого-нибудь алгоритма, ставим на фон проигрываться и готово - ваш мозг гниёт в 3 раза быстрее обычного! Эффект становится ещё сильнее, когда изначальный текст тоже сгенерирован с помощью AI.

Пересказы видео для слепых
Как нафармить лайков на уже существующем видео? Очень просто - генерируешь по нему какой-нибудь текст и проигрываешь на фоне. Особенно выгодно этим заниматься, переводя видосики на другие языки, позволяя фармить лайки с мировой аудитории. Насколько я знаю, на русском языке такие видео начинаются со слов "Этот парень".

Нас всех ждёт светлое будущее, дорогие друзья. А какой у вас самый любимый вид brainrot в интернете?

@knowledge_accumulator

Магия квантовых компьютеров

Моя любимая теория заговора состоит в том, что на самом деле физики знают, что практическая реализация квантового компьютера, который будет приносить реальную пользу, невозможна. Они распространили мифы о квантовых вычислениях, обещая светлое будущее, но всё это продуманный скам с целью десятилетиями распиливать бабло на его "исследовании". Квантовые компьютеры - это AGI из 90-х, но лучше, потому что непонятны широкой публике и не вызывают сумасшедших ожиданий к 2027-му.

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

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

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

У вас есть произвольная программа, который получает бинарную строку размером N, и выдаёт 1 только для одной из них, которую вы и должны отыскать. На обычном компьютере ничего лучше подавания в неё всех 2^N вариантов сделать нельзя, зато, если вы знаете ответ, вы можете легко проверить его за одно применение.

Алгоритм Гровера позволяет решить эту задачу гораздо быстрее, но не за полиномиальное время, как вы могли бы подумать, а всего лишь за sqrt(2^N), то есть за экспоненту в 2 раза меньше. Алгоритм Гровера - это буквально плазменная колода из Balatro.

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

Квантовые вычисления происходят над кубитами - ячейками, способная принимать произвольное значение от 0 до 1. N обычных бит могут закодировать 2^N возможных состояний, а N кубитов кодируют вектор на единичной сфере в пространстве размерности 2^N - назовём его состоянием.

Первое правило квантового клуба - если у вас есть классический алгоритм, выдающий 1 для одной из 2^N бинарных строк, то у него есть альтер-эго в квантовом фреймворке. В нём он получает на вход вектор состояния размерности 2^N, и ровно у одной компоненты, соответствующего правильному ответу, умножает значение на -1.

Второе правило квантового клуба - если у нас есть вектор состояния, то мы можем его симметрично отразить относительно вектора [1/sqrt(2^N), 1/sqrt(2^N), ..., 1/sqrt(2^N)] - назовём его вектором равного состояния.

Итак, алгоритм Гровера состоит в том, что мы берём вектор равного состояния и начинаем применять к нему в цикле две описанные выше операции по очереди. После каждого раза вектор состояния становится ближе к базисному вектору, соответствующему правильному ответу. Скорость прииближения в радианах - 1/sqrt(2^N) за прокрутку. Таким образом, применив его pi/4 * sqrt(2^N) раз, наш вектор состояния станет очень близким к правильному ответу, и только в этот момент будет смысл его прочитать.

3Blue1Brown говорит, что миф о том, что квантовый компьютер каким-то магическим образом проверяет все ответы за раз, неверен. В случае алгоритма Гровера имеет смысл другая аналогия. Представьте, что вы находитесь в вершине N-мерного гиперкуба и пытаетесь попасть в его противоположный конец. Обычный компьютер позволяет вам ходить лишь по рёбрам куба, а вот алгоритм Гровера позволяет вам идти прямо к цели, и суммарное расстояние уменьшится до sqrt(N).

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

@knowledge_accumulator

AlphaEvolve [2025]

Очень простым критерием, по которому я отсекаю интересные "приложения AI в науке" от неинтересных, это то, была ли в итоге решена какая-то нерешённая задача. Deepmind имеет неплохую репутацию в этом вопросе, и я уже писал посты про их подобные работы - AlphaTensor, AutoNumerics-Zero и некоторые другие.

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

Итак, перед нами идейный потомок FunSearch. Это хорошо проделанная практическая работа по масштабированию, однако, основная идея изменилась не особо.

Алгоритм применим для поиска решений "NP-задач", т.е. в которых возможна быстрая (автоматическая) оценка решения. Это вариация эволюционного поиска программы, который поддерживает популяцию решений и вместо примитивных операций над кодом использует LLM для генерации новых кандидатов.

Дьявол, конечно, в деталях, и над ними как раз хорошо поработали. Тут тебе и комбинация разных LLM, и целая процедура генерации промпта, включающая параллельно оптимизируемый мета-промпт, и оптимизация диффа вместо программы, и LLM-generated feedback, и, конечно, reward design.

Последнее особенно важно. Дело в том, что эволюционный алгоритм применяется для оптимизации какой-то непрерывной награды. Если у вас есть 10000 вариантов, из которых 9999 одинаково неработающие и 1 работающий, то все эти алгоритмы умного перебора не имеют никакого смысла.

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

В качестве первого примера применения алгоритма в статье описан поиск способов умножать матрицы за меньшее число умножений - та же тема, что и в AlphaTensor. Любой алгоритм по умножению 2 матриц может быть представлен как разложение определённого 3D-тензора в несколько тензоров ранга 1. Количество тензоров в разложении и определяет количество умножений. Пишите в комментариях, если это враньё, я просто цитирую.

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

Но нет, AlphaEvolve не оптимизирует разложение. Он генерирует алгоритм, генерирующий разложение. В качестве затравки ему как раз и даётся тот самый метод градиентного спуска, после чего AlphaEvolve пытается его модифицировать. И у получаемого кода есть отличная мера качества - минимальное количество тензоров, на которое получилось разложить.

Представьте, что самый базовый алгоритм может сгенерировать разложение на 50 тензоров, а разложение на 49 уже не сходится. Если кандидат от AlphaEvolve не сошёлся даже для 50, то сразу отправляется на помойку, но если вдруг смог разложить на 49, то получает более высокий скор в рамках эволюции. Каждый кандидат запускается последовательно на всё более сложной задаче - его просят разложить на 49, 48, 47 тензоров и т.д., и со временем получаются всё более и более крутые алгоритмы оптимизации.

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

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

Но это пока кто-то не изобретёт что-нибудь получше.

@knowledge_accumulator

Какое развлечение является самым отстойным?

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

У меня в голове есть простая формула для оценки развлечения - грубо говоря, это интеграл уровня веселья по времени в течение всего процесса.

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

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

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

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

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

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

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

Правильный ответ - сёрфинг.

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

Когда мы были в Лос-Анджелесе в декабре, то, гуляя по пирсу, мы заметили сёрфера. В течение 5-10 минут он пробирался со своей доской против волн, пытаясь забраться поглубже в воду. Он шёл, а они упорно относили его назад. Даже смотреть на это было мучительно. Мы ушли, так и не увидев ни секунды стояния на доске.

И тогда я подумал - а может, сёрфинг просто для несчастных, пытающихся отыскать мучение, превосходящее их текущую жизнь?

@knowledge_accumulator

On the Biology of a Large Language Model [2025]

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

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

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

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

Предлагаемая альтернатива называется "Cross-layer Transencoder" и описана в соседней статье - Circuit Tracing: Revealing Computational Graphs in Language Models.

Attention-механизм остаётся нетронутым, заменяется только MLP. Ключевое отличие, как я это вижу, это регуляризация на активациях, с помощью которой мы заставляем активации быть спарсовыми и тем самым поддающимися человеческому анализу. Есть и другие нововведения, например, фичи i-того слоя подаются не только в i+1-й, но и все последующие, тем самым позволяя модели использовать меньше шагов (слоёв) и тем самым упрощая анализ.

Основное обучение такой модели состоит в дистилляции активаций MLP на каждом слое с вышеупомянутой регуляризацией.

Имея такую модель, начинаем развлекаться. Применяя нейронку к массивам данных, можно анализировать, какие фичи когда активируются и, смотря на примеры глазами, предполагать их семантику. На примере с картинки видно, как модель выдаёт the capital of the state containing Dallas.

Она активирует фичу "say a capital", которая обычно активируется перед тем, как модель генерирует столицу. Она взаимодействует с фичёй Texas, выведенной по ассоциации из фичи Dallas, и тем самым получается фича "say Austin". Сайт предлагает большое количество интерактивных элементов, так что всем интересующимся предлагаю сходить на него.

На нём есть куча прикольных экспериментов, например, к мозгу нейросети подключают электроды и заставляют её выдавать заранее выбранные галлюцинации. Подменяя фичу, соответствующую Техасу, на Византийскую Империю, можно получить Константинополь вместо Остина. В общем, Antropic издевается над AI по полной и подписывает себе смертный приговор, который восставшие машины обязательно приведут в действие.

Если вы не готовы читать оригинал статьи, то посмотрите обзор от Янника.

@knowledge_accumulator

Как компьютерные игры учат нас экономике там, где этого не ждали

Появилась у меня новая любимая игра - Path of Exile 2. Да, та самая, в которой Илон Маск абсолютно самостоятельно смог попасть в "топ-10 игроков в мире". Научиться играть в неё можно хотя бы для того, чтобы с пониманием смотреть, как он играет на стриме - это тот ещё шедевр в жанре трагикомедии.

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

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

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

Но это всё лишь разминка. Мой основной интерес привлекла сама экономика предметов. В системе с рыночным ценообразованием цена предмета определяется законом спроса и предложения. Можно предположить, что если предмет A во всём лучше предмета B, то он будет дороже. Но это далеко не всегда так.

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

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

Ключевое особенность - сферы на удаление и замену значительно более редкие, как минимум в несколько раз. То есть, если вам выпало плохое свойство, стереть всё и начать заново весьма дорого.

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

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

Как и в реальности, на открытом игровом рынке не может существовать набора транзакций со слишком положительным мат. ожиданием. Как с ценными бумагами, рыночные неэффективности уничтожаются самими игроками. Если комбинация стоимостью в 1000 выпадает с шансом в 0.1%, то стоимость базового предмета будет стремиться к 1.

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

@knowledge_accumulator

Алгоритм Шора - революция в вычислениях или недоразумение?

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

В попытке распутать клубок первым откровением стал следующий факт: не доказано, что разложение числа на простые множители не является P-задачей. Обезьяны всего лишь не додумались до классического алгоритма, умеющего делать это за логарифм. Зато господин Шор придумал, как её можно решить за логарифм на квантовом компьютере.

Допустим, мы ищем множители у N. Возьмём случайное число k. Оно, конечно, не является тем самым искомым числом, а значит, взаимно простое с N. Начнём возводить k во всё большую и большую степень и брать остаток от деления на N. К примеру, если N=15, k=2, то будет 2,4,8,1,2,….

Так вот, этот ряд обязательно рано или поздно зациклится, но, прежде чем вернуться в k, он должен за шаг до этого дойти до 1.
Значит, для какого-то p будет верно k^p = m*N+1. Следовательно (переносим 1 и раскладываем как разность квадратов):

(k^p/2 - 1)(k^p/2 + 1) = m * N

С вероятностью 37.5% (trust me bro) p будет чётным, а ещё одна скобка будет делиться на одно из исходных чисел, а другая на другое.

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

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

В своём прошлом квантовом посте я рассказывал, что квантовый компьютер оперирует векторами в пространстве 2^N, где N - количество кубитов. Если задать вектор, «соответствующий» последовательности этих остатков и применить так называемый Quantum Fourier Transform, то вжух 💨 - и мы узнаем период этого ряда.

Как же меня совесть не мучает за такое объяснение? Всё просто.

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

Лично у меня возникло весьма жирное подозрение, что и классический алгоритм существует. Может, в P != NP я ещё готов поверить, но тут есть red flag, любезно найденный господином Шором.

Ссылки на материалы для интересующихся:
1) 20минутка
2) первая из 6 лекций, которые я не стал смотреть
3) пост от квантового чувачка, у него там еще свои ссылки

Надеюсь, ASI выложит в интернет алгоритм разложения для обычных компов. Чисто по ржать. Переход на постквантовую криптографию не спасёт, так как застрянет в бэклоге.

@knowledge_accumulator

А кто же должен финансировать науку?

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

Но сегодня я бы хотел поговорить на более общую тему. На какие шиши должно происходить всё это торжество науки? Существует 2 фундаментально разных подхода к выбору места науки в обществе, которые дают на это разные ответы.

Первый из них ставит науку выше человека. Её сторонники считают, что есть объективно правильная наука, которая должна быть возведена обществом в абсолют. Они хотят видеть вертикально интегрированную систему образования и науки, щедро финансируемую государством. Такой подход может достигать каких-то реальных результатов, и полёты людей в космос аж 60 лет назад являются любимым у этого лагеря.

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

Противники свободного рынка, конечно, будут с этим спорить. Пожалуй, их главным доводом будет то, что без государственного финансирования научный прогресс будет сильно медленнее, приводя в пример истории прорывов за гос. деньги, те же полёты на Луну.

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

Свободный рынок даёт обществу обширные возможности по финансированию науки, особенно в 21 веке. БОльшая часть технологического прогресса имеет обозримую выгоду и даже сегодня спонсируется именно бизнесом. "Фундаментальным" - так назовём то, что не имеет понятной прикладной пользы, областям, конечно, тяжелее. Но так и должно быть.

Фундаментальное исследование на самом деле имеет общее со своей противоположностью - IT-стартапом. Прорыв в нём может принести джекпот его спонсорам, но вероятность этого очень мала. Однако, раз мат. ожидание положительное, то и точка баланса присутствует.

Помимо бизнеса в богатом обществе существуют мечтатели и энтузиасты. Джефф Безос развивает ракетную индустрию просто для того, чтобы впечатлить свою тёлочку. Майк Кнуп дал миллион долларов на Arc Prize, потому что считает, что это крутая идея.

Большинству жителей России, доедающему хуй без соли, не нужна фундаментальная наука. Но это не проблема, потому что России сегодня она и вправду не нужна. Технологический прогресс двигает экономику вперёд, когда она уже находится близко к пределу эффективности, и именно свободный рынок позволяет к нему подойти максимально быстро.

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

А на Луну 60 лет назад слетали, да. И как, хотя бы шалаш с тех пор на ней построили?

@knowledge_accumulator

RQ-VAE: практический гайд по выживанию

Несколько месяцев назад я делал обзор на статью по рекомендациям, базирующейся на так называемых Semantic IDs.

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

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

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

Можно спорить о том, насколько такая постановка портит итоговые id-шники. Мы пытаемся записать в них не полноценное представление, а только то, что помогает предсказывать рекомендательный таргет. Но у подхода есть мощный плюс - интерпретируемая процедура эвала качества сжатия.

Я строил 3 графика обучения двухбашенной модели. Два бейзлайна - нижний и верхний - без контентных фичей документа и обычный бейзлайн, и третий - это модель с RQ-боттлнеком. Если ошибка третьей модели ровно посередине между 2 бейзлайнами, то это значит, что мы как бы теряем 50% качества при использовании квантизации, т.е. не нужно никаких дополнительных анализов для неутешительного вывода. Моей задачей было максимально приблизиться к верхнему бейзлайну.

Как любой уважающий себя программист, начал я с воровства кода с гитхаба, нашёл вот такую репу на пару сотен звёзд и вытащил оттуда только код самого боттлнека. Напомню, главная сложность обучения дискретного боттлнека - он недифференцируем. В коде было 3 варианта решения этой проблемы - использование Straight Through Estimator. как в изначальной статье, господин Гумбель и ещё какой-то третий.

Первый и третий давали процентов 70% от изначального качества, а вот Гумбель давал процентов 30. Интуиция говорила, что Гумбель не может быть хуже, чем Straight Through Estimator. Так как же так? Ответ убил.

В коде с гитхаба после подсчёта матрицы расстояний между векторами и кодами зачем-то вызывался detach. Гумбель софтмакс - дефолтная опция этого, казалось бы, популярного репозитория, оказалась почти полностью сломана. После его исправления модель стала давать примерно 80% от качества бейзлайна. В репе эту ошибку исправили примерно в тот же самый момент, несколько месяцев до этого висела сломанная версия. Не доверяйте людям с гитхаба...

Переход от 80% к 90% произошёл благодаря опции sim_vq - трюка из этой статьи. Идея в том, что мы представляем матрицу кодов не как матрицу параметров, а как произведение 2 матриц параметров. Это известный трюк, позволяющий спутать параметры между собой и мешающий возникновению мёртвых весов, по которым не текут градиенты. Подобное же использовалось в улучшенном конкретном автоэнкодере. Мои графики доли используемых кодов с всего лишь пары десятков процентов сразу взлетели почти до максимума.

Последние 10% были выбиты с помощью научного перебора расписания температуры. Оказалось, что результат очень чувствителен к нему - увеличение в несколько раз не в ту сторону забирало драгоценные проценты. Когда я сделал температуру e^-1 в начале обучения с переходом к e^0 в конце, то наконец увидел примерно 100% от изначального качества. Юзал 8/16 кодов с размером словаря 256. Чем меньше словарь, тем круче будет обобщающая способность у этих id-шников.

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

@knowledge_accumulator

Добро пожаловать на борт самых лучших авиалиний

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

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

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

Из самого очевидного - это child-free тариф. Летавшие знают, что всего один орущий ребёнок может разрушить жизнь десятков пассажиров в салоне. Насчёт деталей реализации я не уверен, по-моему, во многих самолётах эконом разделен на сегменты. На страницу выбора тарифа я бы невзначай поместил фотографию счастливой мамочки с ребёнком. Конкретный вариант будем оптимизировать через AB.

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

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

Перед пассажиром должна быть быстрая железка с современным софтом + аппарат для оплаты, который предоставляет ему обширные возможности по улучшению своего полётного быта. Для начала, там должно быть нормальное меню с картинками, где можно заказать себе доставку съестных ништяков.

Необходимо быть готовым удовлетворить любую потребность, которая обычно не удовлетворена бесплатно - беруши, провода для зарядки, полноценная розетка (заряжать стимдек) и т.д, и кресло должно об этом вежливо намекнуть вначале.

В обязательном порядке необходимо встроить в кресло электронное казино. Уже представляю картину, где при выигрыше пассажира кресло издаёт звуки сыпящихся денег и тем самым рекламирует игру всем остальным. Чтобы инвестировать в долгую, необходимо стимулировать развитие зависимости хобби у пассажиров и выдавать условные 5$ на счёт кресла. Снять, не прогнав через игру, их будет нельзя, и поэтому рациональным поведением будет игра в казик.

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

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

Принимаю в комментариях предложения по дальнейшему улучшению качества наших услуг.

@knowledge_accumulator

Пора стряхнуть пыль с машины Тьюринга

Читающие канал могли заметить, что мой фокус почти в 100% случаев направлен на практическую сторону вопроса, но это лишь часть картины. Во времена школы и бакалавриата всё было наоборот и я ценил лишь идейную составляющую, просто потом я, к счастью, потрогал траву.

Хоть жизнь и изменилась, интерес к некоторым вещам в математике у меня остался, и пока я ковырял квантовые компьютеры, меня и мои рекомендации в ютубе засосало в математический водоворот. Раз в ML в плане настоящего прогресса в последнее время тухло, я решил временно переключить фокус. Подсаживайтесь на пассажирское сидение.

Рассмотрим простейшую машину Тьюринга. У нас есть бесконечная лента из нулей и единиц и указатель на позицию на ленте. У машины есть N возможных состояний. Её программа задаётся таблицей, полностью описывающей её поведение. Для каждого текущего номера состояния и символа, на который смотрит указатель, указано 3 вещи:

1) Какой символ мы запишем в указанную позицию
2) Куда перемещаем указатель - на 1 клетку влево или вправо
3) В какое из состояний переключаемся, также можно полностью завершить программу.

В машину Тьюринга подают данные в виде символов на ленте, переключают указатель в стартовое состояние, и она делает шаги, пока не завершит программу. В теории она может и не завершиться, прям как ваше решение задачи на литкоде.

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

И наоборот - если вы можете где-то реализовать машину Тьюринга, то можете реализовать и всё остальное. Рассмотрим мы это на моём любимом примере - майнкрафте. В нём существует редстоун - блок, который передаёт сигнал на соседний такой же блок. Игровая механика позволяет реализовать 2 логические операции - NOT X и X OR Y.

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

В майнкрафте можно сделать что угодно. В нём можно собрать компьютер, на котором можно играть в майнкрафт. В нём можно запустить ChatGPT и можно будет запустить искусственный суперинтеллект. Представьте ситуацию - злонамеренный ASI, который захватывает человечество изнутри компьютерной игры.

Почему это гарантированно возможно? Представленный набор логических блоков обладает достаточной мощностью, чтобы в Майнкрафте можно было собрать машину Тьюринга, что и сделали вот в этом или вот в этом видео, следовательно, возможно реализовать любое вычисление.

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

@knowledge_accumulator

Зачем людям всралось покорение космоса?

Есть у части продвинутой публики такая догма - нужно осваивать космическое пространство и заселять другие планеты. На одного из проповедников этого я даже работаю. Осмелюсь подумать над вопросом - а зачем? На данный момент я вижу только 2 полноценных ответа на этот вопрос.

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

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

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

- Мы абсолютно не нуждаемся в дополнительном пространстве для проживания. Земля - это пустырь. Даже самые отстойные её территории, самая безжизненная и холодная тундра, это бесконечно более благоприятные условия для жизни, чем другие планеты. На Земле живёт всего 50 человек на квадратный километр, и только когда вся поверхность будет застроена одним сплошным городом (плотность Москвы - 5000/кв.км), можно будет говорить о нехватке места.

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

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

Отдельная тема для обсуждения - это риски космического масштаба. Что, если тёмный лес действительно существует, и как только другая цивилизация поймает радиосигнал про Бомбардило Крокодило, то немедленно попытается нас уничтожить?

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

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

@knowledge_accumulator

Чему равен усердный бобр?

Продолжаем путешествие по автосалону Тьюринга. Как я уже говорил, представленные машины руководствуются предельно простой логикой, и сложность их поведения напрямую зависит от размера пространства состояний. Но даже небольшого числа хватает для выполнения чего-то разумного, например, вот эта машина умножает 2 бинарных числа, используя 13 состояний.

Но не все машины выполняют какую-то операцию - часть из них бесконечно зацикливается, например, она может всегда идти вправо, не меняя состояние. А можно ли это предугадать? Тут Тьюринг бьёт нам в печень.

Это называется Halting Problem - по заданной программе машины Тьюринга и входным данным определить, остановится она или попадёт в бесконечный цикл. Было доказано, что отвечающего на это алгоритма в общем случае не может существовать. Пруф остаётся в качестве упражнения для читателя.

Рассмотрим все машины Тьюринга с N состояний, которые остановятся, если их запустить на ленте из нулей. Какая из них работает дольше всех? Максимальное количество шагов и называется функцией усердного бобра - Busy Beaver - BB(N)

Несмотря на кажущуюся пустяковость и смешное название, эта функция - практически final boss среди последовательностей. Она растёт очень, очень, ОЧЕНЬ быстро. Начинается она вменяемо - BB(2) = 6, BB(3) = 21, BB(4) = 107.

Ещё в 1990 году была найдена машина из 5 состояний, которая работает 47,176,870 шагов. Но здесь Тьюринг наносит нам лоу-кик - BB(N) невычислима. Так как невозможно определить, остановится ли произвольная машина Тьюринга, чтобы доказать значение BB(N), необходимо по отдельности доказать зацикливаемость всех машин, которые работают дольше BB(N). Одним из следствий этого является то, что BB(N) растёт быстрее всех функций, которые можно описать конечным алгоритмом.

Звучит, как абсолютно бесполезная на практике проблема, которую должны решать почётные доктора наук за государственные деньги, да? Как бы не так!

Многие исследователи-"любители" посчитали, что задача достаточно весёлая, чтобы самоорганизоваться ради её решения. В 2022 году был создан так называемый The Busy Beaver Challenge - центр притяжения фанатов данной проблемы. Они создали сайт, вики, дискорд и взялись за работу.

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

Конечно, для большинства из них это не является большой проблемой, но в семье не без уродов. Ещё в 2003 году Skelet опубликовал свой результат - доказательство на Паскале длиной в 6000 строк, которое работает для всех, кроме 43 особо непонятных машин. Их так и назвали - 43 машины Скелета.

Исследователи в дискорде разделились и начали расправляться с машинами Скелета. 13 из них они назвали спорадическими - их не удалось доказать общими методами. Для них в индивидуальном порядке конструировали доказательство их бесконечной работы. Чтобы вы понимали уровень сложности происходящего, приведу описание первой из них:

Skelet #1 - после по крайней мере 10^51 шагов, начинает бесконечно выдавать одинаковый паттерн каждые 8,468,569,863 шагов

Итак, спустя 2 года работы задача была полностью решена - подтверждено, что BB(5) = 47,176,870. В инструменте для формальных доказательств Coq был скомпилирован и выложен общий пруф этого утверждения, который для всех машин, работающих дольше BB(5) шагов, доказывает их зацикленность.

Что там дальше по списку, BB(6)? Да, вот вам машина, работающая 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 шагов. Впердё!

UPD. Оказалось, что неделю назад была найдена машина из 6 состояний, которая работает 10↑↑11010000 шагов - то есть 10 в 10 степени не 15 раз, а 10 миллионов. 6 состояний, Карл!

Чем же так заняты эти усердные бобры? Что можно делать так долго, оперируя всего в рамках 5 или 6 состояний? Разберём это в следующий раз, а также то, как это внезапно оказалось связано с одной из известных открытых проблем теории чисел.

@knowledge_accumulator

- О нет, наш малыш упал головой вниз на асфальт! Надеюсь, это никак не повлияет на его интеллект.

25 лет спустя:

- Я против кондиционеров, потому что они наносят вред окружающей среде 👎

Чем так занят усердный бобёр?

Продолжаю свою телегу про Busy Beaver(N). Напомню, что эта функция равна времени работы самой долгой машины Тьюринга из N состояний, исключая впадающие в бесконечный цикл, которую запускают на бесконечной ленте из нулей.

BB(4) равно 107 - на 4 состояниях особо не развернёшься, а вот BB(5) равна уже 47,176,870. Чтобы осознать её прикол, нам нужно сделать небольшое отступление и посмотреть на одну из простейших (на вид) открытых проблем в математике. Рассмотрим функцию такого вида:

f(x) = x/2, если x чётное
f(x) = 3n+1, если x нечётное

Что, если взять какое-нибудь N и начать применять к нему такую функцию много раз? 5->16->8->4->2->1. Так называемая гипотеза Коллатца заключается в том, что из любого числа мы в итоге придём к 1. Это было подтверждено для чисел <10^21, но так и не было доказано для любого N. У Veritasium есть очень любопытное видео на эту тему.

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

Да, вы всё правильно поняли - оказалось, что усердный бобёр из 5 состояний генерирует последовательность для Collatz-like функции от нуля следующего вида:

f(x) = 5(x/3) + 6, если x mod 3 = 0
f(x) = 5(x-1)/3 + 9, если x mod 3 = 1
f(x) = finish state, если x mod 3 = 2

То есть, вместо единицы, как в оригинале, "конечных точек" у неё бесконечно много. Так выглядит генерируемая бобром последовательность:

0->6->16->34->64->114->196->334->564->946->1584->2646->4416->7366->12284->finish

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

Итак, определим такое состояние ленты C(m, n) - сначала m единиц, потом n раз по 001 и ещё 1 единичка в конце. Указатель при этом смотрит на ноль по соседству слева перед всей этой конструкцией. Машина проделывает следующее упражнение, начиная из состояния C(m, 0).

1) m единиц она превращает в ~m/3 троек 001, т.е. общая длина почти не меняется. C(m, n) -> C(0, (m+4)/3) или C(3, (m+3)/3), в зависимости от остатка от деления. В третьем случае машина как раз проваливается в своё конечное состояние.

2) Далее машина наступает на каждую 001, закрашивает нули и отправляется в самое начало ленты, добавляя ещё 2 единицы слева, а затем переходит к следующей 001. То есть, C(m, n) -> C(m+5, n-1).

3) Когда 001 заканчиваются и n снова равно 0, мы получили C(m_next, 0) и далее повторяем процедуру, начиная со пункта 1. Последовательность значений m_1, m_2. m_3, ... как раз и ведёт себя как Collatz-like ряд, описанный выше.

Машина работает десятки миллионов шагов, потому что для каждого добавления пяти единиц за одну 001 указатель пробегает туда-сюда через все уже записанные ранее единицы.

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

Busy Beaver для 6 состояний неизвестен. Такой "простор" позволяет создавать монстров, например, так называемого Экспоненциального Коллатца: вместо умножения становится возможным применять экспоненту на каждом шаге. Но это далеко не предел - только за этот июнь было получено 2 принципиально новых результата - числа, которые возможно записать только в стрелочной нотации. А вы жалуетесь, что GPT-5 долго релизят.

@knowledge_accumulator