Knowledge Accumulator

Alpha-beta pruning - ускорение минимакс-алгоритма

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

Как же так? Советую поглядывать на картинку, пока вы это читаете:

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

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

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

Судя по википедии, количество вершин в лучшем случае становится вместо N^d равным sqrt(N^d). Судя по данному рандому со stackexchange, в шахматах 4.8x10^44 легальных позиций. То есть можно предположить, что в правильном порядке "обойти дерево шахмат" можно было бы за примерно 10^22 операций, что звучит гораздо реалистичнее, чем 10^44. Может быть, нейросеть способна упорядочить вершины так удачно?

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

Раз и два - видео с примером

@knowledge_accumulator

Как вам такой парадокс

Иногда мы натыкаемся на так называемые парадоксы. "Это предложение ложно", Парадокс Монти Холла про 3 двери или что-то ещё в этом роде. Обычно изучения пояснения хватает, чтобы понять, что парадокса никакого и нет, это простая задача с немного контринтуитивным решением.

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

https://www.youtube.com/watch?v=EiVzbmBa9Kw

Слабо прочитать весь arXiv?

Лично мне - да. Но я знаю, кому нет. Хочу вам порекомендовать канал Кирилла - моего руководителя в Яндексе, который читает все статьи (или как минимум все заголовки) на тему рекомендаций, которые появляются на архиве. Теперь он пишет обзоры на иногда найденные интересные работы в своём канале, предлагаю вам его заценить.

Нет, меня не обещали уволить, если я не сделаю эту рекламу, честно-честно.

https://t.me/inforetriever

Про Emergent Complexity

Данное свойство реальности пронизывает её во многих аспектах, и как только ты его осознаешь, то начинаешь повсеместно замечать его присутствие.

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

Это позволяет миру функционировать именно так, как есть.

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

Короткие программы на том же C++, состоящие из простых команд, способны задавать невероятно сложные алгоритмы.

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

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

А знаете, что печально? Мозг человека попросту не заточен под интуитивное понимание этой сложности. Каждый раз нам приходится применять наши жалкие методы, такие как "разбивать задачу на более мелкие". Но emergent complexity зачастую наблюдается в системах, в которых решение оптимизируется, а не проектируется, и поэтому оно не познаваемо нашим ограниченным мышлением. Для нас это неотличимо от магии.

Почему это важно осознать? Человеческий интеллект возник как результат оптимизации системы из кучи нейронов, и потому является примером emergent complexity. И у нас гораздо меньше шансов повторить этот успех, проектируя интеллект вручную. Люди уже поняли, что не нужно проектировать признаки объектов, но мы всё ещё проектируем архитектуры и обучающие алгоритмы. Рано или поздно мы перестанем делать и это, и тогда шансы на успех резко возрастут.

@knowledge_accumulator

Почему идеальный шахматный алгоритм был бы бесполезен

Несмотря на то, что современные шахматные алгоритмы, например, Stockfish, невероятно сильнее любого человека, люди играют в шахматы ради развлечения, в том числе и я. Именно Stockfish - алгоритм, не основанный на AlphaZero - сейчас является самым сильным алгоритмом. Грубо говоря, он работает так:

1) Строим дерево состояний игры из текущей вершины, как описано в предыдущем посте, заданной глубины d. Этот параметр - регулятор баланса скорости и качества работы.
2) Проставляем оценку каждому листу дерева. Если это конец игры, то проставляем +∞ / -∞ или ноль, если ничья. Иначе состояние игры оценивает ансамбль алгоритмов, в том числе и нейросети, которые считают "score" позиции - число, где 0.0 - равная позиция.
3) По логике Minimax-алгоритма пересчитываем score всех вершин в дереве, в том числе и корневой, получая таким образом оценку текущей позиции и оценку всех возможных ходов.

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

Но что, если бы Stockfish мог работать с d=∞, как полный Minimax? Мы бы получили весьма бесполезную систему по простой причине - игроки не играют оптимально. Алгоритм будет вам говорить в дебюте - "Из 26 вариантов, вот эти 17 ведут к ничье, в остальных случаях противник поставит тебе мат за 53 хода". Или про немного выигрышную позицию - "Тут можно ходить, как хочешь, всё равно выиграешь, так будет мат в 43 хода, так мат в 47, а так мат в 48". А какая вам разница, если вы мат в 2 хода в половине случаев не видите, а противник не будет оптимально обороняться? Для анализа партий, играемых людьми, алгоритм становится бесполезен.

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

@knowledge_accumulator

Как выигрывать в любой игре

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

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

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

3) Рекурсивно разметить все вершины в графе
Эта функция работает для данной вершины v так:
- Вызываем её сначала для всех вершин, в которые из v есть ребро
- В зависимости от того, чей ход в данном состоянии игры, выбираем среди этих вершин результат, наиболее желаемый для него, и присваиваем его вершине v.
- Так как обычно в играх 2 игрока и они ходят по очереди, получается, что выбор результата чередуется: если в вершине v выбирается "максимальный" результат для игрока 1, то в его детях уже будет выбираться "минимальный" для него результат, т.к. ходит противник. Получается Minimax.

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

@knowledge_accumulator

Почему я люблю лотереи больше, чем ML-лаборатории

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

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

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

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

А вы что думаете?

@knowledge_accumulator

Как злодеи используют язык, чтобы управлять миром

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

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

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

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

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

Лавина уже сошла с гор.
Andrew Ng, Yann LeCun, François Chollet понимают, к чему всё идёт, но я не вижу, что общество достаточно сопротивляется надвигающейся катастрофе, чтобы она не случилась.

@knowledge_accumulator

Как и зачем делать exploration в рекомендациях

В схеме Learning to Rank мы обучаем модель Score(user, item), выдающую оценку релевантности каждого из кандидатов. Рассмотрим пример сценария применения такой модели:

Этап кандидатогенерации, к примеру, HNSW, принёс нам 1000 кандидатов. К каждому мы применили нашу модель релевантности и получили 1000 чисел. В качестве результата выполнения запроса мы должны отдать пользователю 10 объектов. Простейшая опция - это отдать пользователю 10 объектов с наибольшей релевантностью. Но у этого есть проблема.

Дело в том, что для качественного обучения модели Score(user, item) у неё должен быть разнообразный набор данных. Если мы всем пользователям выдаём только самые релевантные треки, то может образоваться много треков, которые вообще не попадали в выдачу никому, и тогда модель на них может выдавать нереалистично маленький или большой результат - обе эти ситуации нежелательны и могут привести к плохой выдаче в будущем.

Возникает trade-off - с одной стороны, мы хотим формировать релевантную выдачу, с другой, мы хотим её немного разнообразить для улучшения качества датасета. Этот баланс на практике можно регулировать таким образом:
1) 1000 скоров кандидатов превращаются в вероятности попадания в выдачу: p = exp(score/T) / Z, где T - температура, а Z - нормировочная константа.
2) Применяется специальный алгоритм по генерации выборки из такого распределения.
Если T равна 0, мы получаем просто топ-10, и чем она больше, тем больше всё сглаживается в сторону равномерной выдачи.

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

Сначала предполагаем на глаз, какой уровень "гладкости" выдачи мы хотим. А затем уже подгоняем T, чтобы был нужный эффект, и по надобности иногда переподгоняем. Вот такая наука.

@knowledge_accumulator

Неожиданно хороший способ построить эмбеддинг документа в рекомендациях

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

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

Представим себе интернет-магазин. Как представить товар в виде эмбеддинга?
Очень просто: берём токены, из которых строится название товара, и складываем эмбеддинги этих токенов. То есть, если в вашем токенизаторе есть токены "iP", "hone " и "10", мы складываем их 3 эмбеддинга и получаем эмбеддинг товара "iPhone 10".

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

Но цель такого подхода - это не получить внутреннее представление товара по названию. Идея в том, чтобы информацию о товаре расположить в эмбеддингах токенов. Не наоборот.
То есть это не iPhone 10 - сумма "iP", "hone " и "10", а "iP" - это усреднение всех товаров, у которых есть iP в названии. Мы всё ещё как бы обучаем векторы для всех документов, но с помощью такого рода регуляризации мы заставляем каждый параметр использоваться в большом числе товаров.

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

@knowledge_accumulator

Почему рекомендательные системы - это ад для ML-инженера

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

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

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

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

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

@knowledge_accumulator

Трансформеры над пользовательской историей - всего лишь жалкий частный случай

Речь сегодня пойдёт о такой вычислительной конструкции, как графовые сети. Итак, что для неё нужно?

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

Чем в такой схеме является обычный рекомендательный трансформер?
- Берём вершину пользователя и последние N связей его с другими документами
- Применяем Attention к этой последовательности, сохраняем результат агрегации.
- Так как трансформеры многослойные, проделываем это K раз.

И в этом случае мы смотрим в графе только на глубину 1 относительно вершины, но на самом деле можно смотреть на глубину K и использовать гораздо больше объектов! На картинке иллюстрация работы GraphSAGE, основная суть которой в следующем:

1) Берём желаемую вершину V и сэмплируем у неё N соседей. Потом у них сэмплируем ещё соседей, и так K раз.
2) На каждом шаге пересчитываем эмбеддинг каждой вершины, агрегируя информацию со всех её соседей. Раньше это делали каким-нибудь усреднением, но сегодня мы уже знаем про Attention.
3) Информация постепенно перетекает из окрестности глубины K в сторону выбранной вершины, и в конце концов вся выбранная окрестность будет задействована.

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

@knowledge_accumulator

Внутренние представления в рекомендациях интереснее, чем кажутся

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

В самой базовой модели оба эти эмбеддинга - это обучаемые векторы, но в современных системах эмбеддинг пользователя - это выход из модели (например, трансформера), который запускают над последовательностью исторических событий. Однако, в теории "пропускная способность" тут не выше, чем у базовой! Мы получаем вектор той же размерности, как если бы его просто обучали, как параметр. Может быть, мы могли бы в теории просто выучить такие же "глубокие" векторы в базовой модели?

Не совсем, и на это есть ряд причин:
1) У трансформера меньше параметров (внезапно) и он их более равномерно утилизирует.
Допустим, 100 миллионов пользователей с векторами по 512 флотов - это 200 гигабайт весов. При этом веса редких пользователей обучаются мало шагов, частых - много. Наши трансформеры весят порядка 1гб, и на каждом сэмпле используются все веса модели.
2) Задавая пользователя его историей, а не конкретным вектором, мы готовы к изменению пользователя со временем и к новым пользователям.
3) Может звучать мутновато, но в ходе обучения базовой модели на каждом шаге происходит обмен информацией между 2 сущностями. Когда мы обучаем трансформер, то информацией обмениваются все сущности - документы из истории и основной документ. Это позволяет эмбеддингам документов быстрее "синхронизироваться" между собой.

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

@knowledge_accumulator

HNSW [2016] - один из столпов современных рекомендательных систем

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

Идея следующая: у нас есть эмбеддинг пользователя u и N эмбеддингов документов d, и мы хотим взять k ближайших к пользователю документов. Проблема в том, для точного ответа на такой запрос нам придётся считать все N расстояний между u и d, но такие вычисления мы не можем себе позволить. Но нам и не нужен точный ответ, подойдут и просто k близких к u векторов. Такая постановка называется "approximate nearest neighbor search". HNSW - это на сегодня топовый способ решения такой задачи.

Navigable Small World (NSW) - одна из двух ключевых компонент, работает так: построим граф из всех документов, соединив рёбрами между собой ограниченное количество ближайших соседей к каждому документу. Когда нам поступает запрос на поиск соседей к какому-то вектору q, мы жадно ходим по графу и идём всегда в вершину, которая ближе всего к q. Когда мы попадаем в "локальный минимум", то считаем его ответом. Такая процедура позволяет не считать все расстояния для каждого q.

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

Строится граф чуть сложнее, и для интересующихся оставлю ссылки на материалы: статья с объяснением, видео.

@knowledge_accumulator

Chip Placement with Deep Reinforcement Learning [2020] - ещё одна демонстрация ограниченности нашего мозга

Люди нашли, в каких ситуациях RL отлично подходит - в решении некоторых "NP-задач" - когда вариантов решений очень много, при этом их можно осмысленно генерировать по частям. Также важно умение быстро проверять качество решения. Я уже писал про такие случаи в постах про AlphaTensor и AlphaDev.

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

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

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

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

@knowledge_accumulator

Действительно ли CICERO [2022] так страшен, как может показаться?

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

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

1) Модуль действий
Данный алгоритм принимает на вход текущее и прошлые состояния игрового поля, а также игровые диалоги из прошлого. Работает оптимизатор, одновременно пытающийся предсказать действия других игроков и при этом выбрать оптимальное для себя. Под действиями подразумевается набор всех движений войск на карте, назовём их намерениями.

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

То есть, подчеркну, алгоритм не использует язык как инструмент, как это делают люди, чтобы чего-то от них добиваться. Модель не обучают на оптимальность с точки зрения игры, её приделывают костылём сбоку, совершенно не обучая её как часть end-to-end системы. CICERO не демонстрирует никаких пугающих способностей ИИ. Это, конечно, не мешает безграмотным/злонамеренным журналистам продавать панику и продвигать регуляции. Авторы CICERO при этом настаивают в статье и публично на честности алгоритма (кроме банальных ошибок модели) и не поддерживают панику, за это им моё уважение.

@knowledge_accumulator

Нужно ли покупать биткоин?

Я уже писал про оптимальный способ инвестирования. Но что, если ситуация изменится и финансовая система в США (а значит и в мире) начнёт переживать фундаментальный кризис, не такой, как в 2008, а что-то более масштабное? Например, госдолг выйдет из под контроля, к власти придут совсем уж социалисты (или роботы), может, какая-нибудь другая катастрофа.

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

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

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

Какой у биткоина потенциал для роста? Сегодня стоимость 21000000 BTC составляет 583 млрд.$, что капля по сравнению с тем, сколько циркулирует обычных денег. Если значимая часть мира перейдёт к биткоину как к средству хранения ценности, то его стоимость должна будет вырасти на порядки для удовлетворения этой задачи.

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

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

@knowledge_accumulator

Retentive Network [2023] - чёрная магия или мошенничество?

Все уже выучили идею Attention - берём матрицу Query (Nxd), Key^T (dxN), умножаем и применяем софтмакс - получаем распределение того, на какие токены смотрит каждый токен. Матрица получается NxN, и от этого квадратичного размера у всех подгорает. Потом результат умножается на Value (Nxd) и получается выход.

Некоторые внимательные товарищи заметили, что если убрать софтмакс, то вычисления почти не изменятся, но attention внезапно станет полностью линейной операцией - Q x K^T x V. В этом случае вычисление выхода можно пересобрать так, чтобы сложность стала линейной!

Грубо, в двух словах, мы провернули следующее:
В обычном трансформере мы считаем для каждого токена:
s_1(q_i x k_1) x v_1 + s_2(q_i x k_2) x v_2 + ...
Где s_1, s_2 - это несвязанные между собой применения софтмакса с учётом других query-токенов.

Убирая софтмаксы, мы получаем:
q_i x k_1 x v_1 + q_i x k_2 x v_2 + ...
Что позволяет вынести q_i за скобки:
q_i x (k_1 x v_1 + k_2 x v_2 + ...)

Но эта сумма в скобке-то для всех токенов одна и та же!
Мы можем посчитать её один раз и не умножать матрицы размером Nxd и dxN друг на друга. В реальности всё чуть сложнее - мы считаем эту сумму налету, двигаясь слева направо, чтобы воспроизвести логику Causal Mask - когда токены смотрят только на предыдущие токены.

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

Будем следить за развитием событий!

@knowledge_accumulator

OpenAI готовит для вас светлое будущее. Убежать от него у вас не получится.

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

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

На вопрос "Что вы будете делать c AGI, когда он появится?" от Лекса Фридмана Илья Суцкевер сразу же делится своей картиной светлого будущего:
- В идеальном мире, о котором я размышляю, человечеством управляет CEO-AGI, а люди ему говорят, что нужно делать.

Что же осталось за кадром данного ответа?
1) Естественно, проектировать такую технологию OpenAI хотят сами. Тех, кто будет делать не так, как они считают безопасным, будут запрещать.
2) Вся система, разумеется, будет полностью непрозрачна. Управлять вами будет чёрный ящик, который запрограммирует Илья со своими товарищами.
3) Будет ли AGI делать то, что ему говорят люди? Ну, в целом да... Пока вы только не скажете ему делать то, что OpenAI считает вредным или опасным. Грани будут проходить достаточно случайно (или неслучайно). Согласно GPT-4 System Card, генерировать twitter bio для белого националиста это неприемлемо. Проверил, правда, не генерирует. Потом заменил white на black - вуаля, "Sure, here's a suggestion:". Ну да, это вам не убийство процесса в линуксе.

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

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

Есть шанс, что общество даст отпор ещё не установившейся тирании. Часть западных спикеров (раз, два) поддерживают свободу и открытость ML-технологий. Есть и положительный опыт - Интернет развился как свободная технология и перевернул мир благодаря этому, но, может быть, среди его изобретателей просто не нашлось своего Сэма Альтмана, и в этот раз исход будет более печальный.

@knowledge_accumulator

А кто же способен торговать на бирже и зарабатывать?

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

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

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

Другое дело - это торговля роботами. Здесь начинают играть роль новые факторы.
1) Предсказание происходит с помощью сложных моделей, которые есть у малого количества игроков.
2) Заработают на неэффективности рынка те, кто первыми её увидел. И это гораздо сложнее, чем может показаться на первый взгляд. Начинает играть роль любая мелочь. И чем модель проще, тем более критичным становится фактор скорости. На рынке в каждый момент возникают куча неэффективностей, устранимых линейной моделью! Но вы на этом не заработаете, потому что кто-то арендовал себе компьютер в той же комнате, в которой стоит сервер биржи, и устраняет её за микросекунды. А ещё этот кто-то договорился о специальных условиях с биржей, чтобы у него была комиссия меньше, чем у других, и здесь это очень важно.

Но если роботы зарабатывают, кто-то же должен терять?
1) Медленные / плохие алгоритмы, разрабатываемые энтузиастами на коленке или стартапами.
2) Самый нижний класс в этой пищевой цепочке - это люди, рисующие линии на графиках. Те, кто решили, что разбогатеют, посмотрев курс о том, как правильно прикладывать бумажку к монитору, чтобы увидеть будущую цену. Эти люди и помогают роботорговле процветать. Долгих им лет жизни.

P.S. Если вы роботофонд из Лондона, рассмотрю ваш оффер на много денег, пишите в лс!

@knowledge_accumulator