# Строим концлагерь по Scrum

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

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

Меня позвали в офис познакомиться с командой исследовательского центра Х-компании, показать условия, убедить меня принять офер. Они рассказывали о своих задачах: занимаются фундаментальной наукой с такими ресурсами, как не получится даже в университетах. Одна из команд изучает методы нейроморфных вычислений: как делать нейронные сети без обратного распространения ошибки. ML/DL давно вышел на плато и явно нужен какой-то качественный сдвиг для дальнейшего продвижения, и эти ребята занимаются одной из вещей, которая может им стать. Очень круто.

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

Мне рассказывали про процесс: таски в канбане, agile и scrum, юнит-тесты, KPI и ревью, выступления на конференциях, конкуренция между отделами, динамичные кросс-функциональные команды. И про специфику: когда-то в Российском офисе Х-компании сидел специальный китаец, который мониторил по камерам как ты работаешь, и вежливо задавал вопросы, если ты отходил на лишний час. Работа была по часам, нужно было писать объяснительные за опоздания. Я слышу: они взяли наши скрамы, аджайлы, конкуренцию и капитализм, вовзвели всё это в людоедский абсолют и поставили на службу построения антиутопии. Копают эту яму для всех нас ребята с таким подходом: "Если забыть о том, что это китайцы...". Как это остановить? Возможно ли это остановить?

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

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

Серега (https://t.me/seryogaBombit) включи уже комментарии, чтобы можно было орать в них

Я конечно ничего не понимаю в RL, но уже пол статьи прочитал. Это очень круто. Позже будет обзор (когда я нагуглю все непонятные слова)

Молния-тейк от моего друга: христианство это трансгуманизм.

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

Разберёмся: медицина борется со старением. В пределе: борется с самой смертью. Заходя ещё дальше можно представить, что однажды мы научимся оживлять мертвых. Если такое случится, станем ли мы оживлять всех, даровав им вечную жизнь? Вряд ли мы захотим оживить, скажем, Гитлера. Значит будет комиссия, суд и в "рай" попадут не все. Тогда стоит вести себя достойно сейчас, чтобы это оценили потом.

Спорно конечно, как именно наши потомки будут нас судить, и как именно стоит себя вести. Но несложно представить, как себя вести не стоит.

Красота: вот как можно визуализировать эффективность вакцинации, как это сделал чувак с Reddit. Зелёные квадраты — это 100 тысяч вакцинировавшихся. Красный квадрат — заболевшие, несмотря на прививку. Жёлтый квадратик — количество умерших после прививки. Это всего один (!) человек.

Больше красивой пропаганды вакцинации!

# Обзор: Open-Ended Learning Leads to Generally Capable Agents, Deepmind 2021

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

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

Как? В статье 54 странцы, но я перескажу всю суть за несколько постов. Если вкратце:
- Авторы создали динамическую генерацию миров и заданий. Это гладкое пространство огромного множества возможных игр, от тривиальных до очень сложных, от кооперативных до соревновательных, от мультагентных до синглплеерных, от сбалансированных до абсолютно нечестных. Приведу цитату: "Создание более хороших агентов и создание более хорошей среды для обучения это одна и та же задача".
- Авторы придумали функцию ошибки, которая позволяет оценивать общую способность агента. Агенту недостаточно быть очень хорошим только в определенных заданиях, он обязан уметь как-то решать любые задачи.
- Сложность заданий изменяется динамически. Агенты всегда решают не слишком простые и не слишком сложные задачи. Для этого агенты тренируются поколениями (population based training), где результат каждого поколения задает планку сложности для следующего. Каждое следующее поколение учится (через policy distillation) у лучшего агента предыдущего.

Важные детали про статью:
- Предлагается настоящая теория RL, прям с теоремами и доказательствами. Что такое игра, что такое цель игры, как посчитать расстояние между игровыми мирами, как определить сложность, сбалансированность и кооперативность игры, какие у всего этого upper bounds и lower bounds.
- Используется множество разных методов, чтобы заглянуть внутрь агентов, выяснить почему и как они что-то делают. В статье нет ни одного утверждения, не подтвержденного эмпирическим экспериментом. На каждый элемент системы приводится albation study. Статью можно отдельно изучать как сборник методов для интерпретации нейронок.
- Решена очень нетривиальная задача: как сделать тестовый и валидационный сет при динамической генерации миров? Как сделать такие миры, чтобы они не встретились при обучении? Это вам не просто import train_test_split.
- ТРАНСФЕР ЛЕРНИНГ в RL. Пока только обещается. Авторы намекают, что при достаточно общей среде обучения агенты изучают переносимые на другие задачи навыки, требующие лишь небольшого дообучения под конкретную задачу. Например способность к навигации и запоминанию среды вокруг может быть применена везде. В пользу этого говорит хорошее zero-shot качество агентов. Если это правда, то статья может начать новую эру в RL похожую на CV и NLP, когда условный Google 6 месяцев обучает в своем симуляторе агента, а вы потом за час дообучаете его на ноутбуке развозить посылки по району. Возможно после этого RL перейдет из разряда дорогих игрушек в настоящий инструмент ML-работяги.

Дисклеймер: название хайповое и результаты тоже, но это всё ещё никакой не стронк AI, можете не волноваться. Пиксельные человечки могут построить один трамплин, но не могут повторить этот трюк два раза. Они так же не могут научиться не застревать в ямах, если яма лежит между ними и целью. Они так же испытывают очень большие трудности в том, чтобы предугадывать поведение других агентов (как я их понимаю): теории разума пока не появилось. Из логических задачек пока только способность разложить три кубика в нужном порядке.

Если вас зацепило, то советую читать статью. Она написана отлично, и даже такой профан в RL как я понял большую часть. Далее несколькими постами я расскажу конкретно про ключевые поинты работы.

Можно ещё позалипать в видосики результатов.

Пиксельные человечки достигают уровня разума игроков в шутеры и используют spawn camping:
https://youtu.be/lTmL7jwFfdw?t=54

Человечки мочат друг друга, хотя им выгодно работать вместе:
https://youtu.be/lTmL7jwFfdw?t=424

Человечки смогли договориться и все получили награды:
https://youtu.be/lTmL7jwFfdw?t=486

Человечки занимаются бесполезной работой, прям как в армии РФ:
https://youtu.be/lTmL7jwFfdw?t=583

Самое интересное, логическая задача:
https://youtu.be/lTmL7jwFfdw?t=651

Человечки делают рандомную фигню до тех пор, пока у них не получается то, что хотелось:
https://youtu.be/lTmL7jwFfdw?t=769

# Обзор Open-Ended Learning 2: пространство заданий

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

Определим терминологию, чтобы не запутаться:
1. Мир — уровень в игре. Включает в себя платформы, по которым можно ходить, освещение и динамические объекты (желтые шары, красные пирамидки, места появления игроков).
2. Игрок — пиксельный человечек, который играет в игру.
3. Агент — черный ящик, который управляет игроком и стремится выполнить цели игрока. Именно его мы обучаем.
4. Цель игрока — состояние, в котором он получает награду.
5. Игра — набор целей игроков.
6. Задание — набор (мир, игра, действия игроков).

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

Цели в данной работе бинарные: держать желтый шар, стоять на красном полу, не быть в поле зрения синего игрока, итд. Цель или достигнута или нет. Далее из нескольких простых целей составляются более сложные цели через операторы И, ИЛИ, например: (держать желтый шар И стоять на красном полу) ИЛИ (синий игрок не держит желтый шар). Это представление называется дизьюнктивной нормальной формой (DNF). Крутость таких целей в том, что агент учиться выбирать, какую из опций (разделенную ИЛИ) проще выполнить. Это порождает планирование. Например, в игре захват флага, возникает сложная стратегия: агенту бывает выгодно упустить награду сейчас и сосредоточиться на устранении противника, чтобы заработать побольше очков потом. Второй прикол DNF целей: их можно записать как матрицу и подать на вход агенту.

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

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

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

# Обзор Open-Ended Learning 3: оценка агентов

Итак, у нас есть возможность динамически создавать разные игры. Как оценить, насколько хорошо играет агент? Как выбрать лучшего?

Мы хотим получить таких агентов, которые:
1. Проваливают как можно меньше заданий.
2. Хорошо выполняют как можно больше заданий.
3. Отдают предпочтение общим способностям, а не узкой компетентности.

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

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

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

Вывод: одного числа недостаточно. Нужно рассмотреть распределение наград агента. Авторы предлагают считать нормализованные перцентили наград. Алгоритм такой:
1. Запускаем популяцию (несколько разных агентов примерно одного уровня) играть в одни и те же несколько игр.
2. Для каждого агента получили его очки в каждой игре, а так же самый лучший результат в этой игре среди всей популяции.
3. Для каждой игры делим очки агента на самый лучший результат в этой игре. Вместо наград непонятного масштаба получили числа от 0 до 1 - нормализованные награды.
4. Для каждого агента считаем с 0 по 50 перцентили нормализованных наград.

Напомню, что перцентиль q это такое число, что q% чисел в последовательности меньше или равны этому числу, а (100-q)% больше этого числа. Например перцентиль 50% это медиана: половина чисел больше этого числа, половина меньше.

На выходе мы получили для каждого агента 50 чисел - перцентили его нормализованных наград. Их несложно интерпретировать. Перцентиль 0 показывает сколько очков агент получил в самой сложной игре: это наш минимум. Прцентиль 50 это медианная награда агента, его "типичное качество". А первое ненулевое число k среди перцентилей показывает, что агент получает хоть какую-то награду в (100-k)% игр. В итоге мы получили вектор, который описывает всё распределение наград агента.

Если надо сравнить двух агентов можно сделать так: агент А лучше агента Б тогда, когда агент А во всех перцентилях не хуже агента Б и хотя бы в одном лучше (на языке шарящих: агент А лучше агента Б если А Парето-доминирует Б).

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

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

Релевантная пикча.

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

Если вы вдруг ищете удаленную работу, то на ACX сейчас тема с объявлениями и много вакансий. Тусовка ламповая и маленькая, поэтому без булщита. Именно так я когда-то и нашел свою предыдущую работу в Mindsdb, так что советую этот путь

https://astralcodexten.substack.com/p/classifieds-thread-82021

Например

# Обзор Open-Ended Learning 4/4: Population based training

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

Весь пайплайн состоит аж из двух видов негладкой оптимизации: Reinforcement Learning и эволюционного алгоритма. Сначала агенты популяции независимо обучаются с помощью RL, затем происходит шаг эволюционного алгоритма. Если один агент лучше другого (по нормализованным перцентилям), то его веса и гиперпараметры лучшего агента копируются с небольшими мутациями. В статье описано какие конкретно мутации происходят, и если честно там ничего интересного: вручную подобранные бедными PhD студентами операции.

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

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

На этом разбор "Open-Ended Learning..." закончен. Я не покрыл ещё много клевых фишек из статьи (там короче нейроны Кохонена, которые визуализируют внутреннее состояние агента и выглядит это прямо как МРТ мозга!), но их там слишком много. Пока можно сказать, что RL это впечатляющий и поражающий воображение трехэтажный набор костылей.

# Унижаем Deep Learning

Всё время слышим про чудеса машинлернинга, но сегодня всё по-другому. В эфире велосипеды от Бориса и сегодня мы будем ощущать своё превосходство.

Итак, задача бинарной классификации. Даны признаки X и ответы Y и нужно понять, какая связь между X и Y. Данные в таблице:

x0 | x1 | y
-----------
0  |  0 | 0
0  |  1 | 1
1  |  0 | 1
1  |  1 | 0

Ответ: если единиц нечетное количество y=1, иначе y=0.

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

Машинное обучение на такой подвиг неспособно.

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

Если мы применим линейную модель, например логистическую регрессию, то она ожидаемо научится выдавать всегда 1, или всегда 0, и мы получим точность около 50%. Можно подумать, что ей нехватает данных, поэтому я пробовал сгенерить для неё большой датасет, но результат такой же.

Возможно дело в линейности. Возьмем KNN, нелинейнее некуда. Но он не умеет экстраполировать. Если ему подать на вход датасет с повторами, то он получит точность 100% на трейн сете и 0% на тестовом сете. Если же без повторов, то просто 0% на обоих. Аналогично ведет себя RandomForest.

Последним я мучал перцептрон. В теории глубокая нейронная сеть способна выучить любую функцию, и наверняка sum(x) % 2 == 0 ей по силам. Однако на практике оказывается, что он моментально переобучается под трейн сет. То есть он выучивает какую-то зависимость, возможно просто запоминает весь трейн сет, но выдает полную чушь на тестовом сете. Я так и не придумал, как ему объяснить, что надо учить вот эту вот истиную зависимость, а не что-то там супер-сложное. Получается, что у DL проблема не такая как у остальных алгоритмов: перцептрон способен выучить нужную функцию, но он не способен понять, какой она должна быть.

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

Приглашаю всех желающих потыкать примеры в коллабе:
https://colab.research.google.com/drive/1Lb7cuVcPTcDPSzBT5NBC6IuN-FSK9gXS?usp=sharing

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