Графики каждый день (почти) Telegram Gönderileri

О пространных рассуждениях
(или о попытках поднять IQ нейросеток)

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

Ему же и посвящено идущее соревнование (за скачок до human perfomance 85% вам предлагают $0.5M) , в котором open-source LLM добрались до 46%. В целом часть задачек неплохо решаются и обычной маленькой CNN (тут можно глянуть мой код), но их ещё пинать и пинать до обобщения. Аккуратно тыкая (см. nature) gpt4 писать код по идее можно добиться и 50% (как тут), но это долго, масштаб часов или даже дней.

Зато вчера вышла o1 от OpenAi (ссылка на обзор), которую не могу обойти стороной. Всего за 2 минуты на генерацию при самых наивных промтах она решила 5/14 предложенных arc задач с первой попытки (тут составил пример диалогов и результатов генерации)! Всё же саморефлексия для моделей это большое благо.

P.S. как думаете, как будут выглядеть капчи лет через 10?)

О генераторах случайных чисел
(или о кубиках и шестеричной системе)

Как в домашних условиях равновероятно выбрать число от 1 до 216? Бросить три игральных кубика!

Я вот только сегодня посмотрел на бросок костей, как на равновероятное сэмплирование чисел в шестеричной системе исчисления. Действительно, давайте обозначим результат броска - 1 за xⱼ, тогда ваше число это
y = 6⁰ x₀ + 6¹ x₁ + 6² x₂ + ...

Бросок {1, 2, 2} превратится в 42, а {1, 4, 5, 6} в 1242. Бросая 5 кубиков вы выбираете из 7k вариантов, а делая так 2 раза уже из 60M. По разному группируя кубики в шестеричные числа можно получить достаточно богатый набор распределений, что и показано на графике)

О кратчайшем пути на графе III
(или о том что случайные блуждания как оценка расстояния до целевой вершины работает)

Кажется вместе с @sberlogasci мы вышли на SOTA уровень по сборке кубика 3x3x3 (вроде NP-complete problem) на основе этого подхода (without human knowledge)! В таблице красным выделен лучший опубликованный результат AlphaCube (14M parameters) и синим наш результат (4M parameters).

Поиграться с моделями и посмотреть на решения можно на kaggle.

// но для 333 это не столь содержательно, так как тут и тут предпосчитали большой Pattern Databases, на котором можно за 2с имея 200GB ram найти решение :)

О том как составлять и решать лабиринты
(или о параллельных удобствах алгоритма Прима и BFS)

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

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

P.S. код доступен на kaggle, буду рад upvotes)

Об одномерном Хаббарде, DMRG и mean field 🌾
#qm

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

А дальше работает очень простая логика: если U » μ,t то все частички просто будут сидеть по одной на узле и никуда не двигаться, это Mott Insulator (MI). Но если t начнём доминировать, то система перейдёт к сверхтекучей фазе (SF). Для MI характерно целочисленное заполнение и экспоненциально спадающие корреляции, а вот для SF наоборот заполнение может быть любым и корреляции спадают полиномиально, что в итоге приводит к расходящейся корреляционной длине ξ.

Можно написать mean field решение для ground state гамильтониана, оно отмечено штрихованной линией. Однако можно найти и истинную границу фаз, например через тензорные сети, одним из параметром которых является bond dimension D — связь между узлами. Так вот, забавный факт: D=1 сводится к mean field решению, но это D повышая вы потихоньку выйдете на истину, что на графике и нарисовано: δn это отличие среднего заполнения от единичного.

// P.S. подробнее в файлике в комментариях

Ода Wolfram Mathematica I
(или об интерактивных удобствах WM)

Хочу поделиться одним из примеров, почему мне так нравится WM: простая интерактивность блокнотов. Например, мне нужно было быстро примерно нарисовать на моём графике точки графика из статьи, и вот за 4 строчки кода получается некоторое окружение, что тыкая на точку на картинке вы сохраняете её относительные координаты в нужном вам массиве)

Ода жадности
(или об удобствах beam search)
#rl

Есть такая головоломка 0hh1, в которой нужно расставить красные и синие квадратики так, чтобы их количество в каждой строке и столбце совпадало, не было одинаковых строк и столбцов, и не было 3 в ряд. Часть из них изначально зафиксированы. Полное пространство состояний 2¹⁴⁴, но у нас есть понятная эвристика -- количество неудовлетворенных условий.

Но давайте из состояния делать все возможные шаги (тут это 12²), а потом оставлять из них B лучших, с точки зрения эвристики. Всё, получился жадный алгоритм beam search (похожим образом генерируются ответы gpt). Не так страшны локальные оптимумы, мы можем позволить себе локально оптимальные шаги.

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

Флип-графы

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

Количество вершин во флип-графе растет экспоненциально от n. Можно задать следующий вопрос: если случайно блуждать по флип-графу полиномиальное время, придем ли мы в примерно случайное состояние (то есть, верно ли, что mixing time соответствующей цепи Маркова полиномиально от n)? Для облаков точек общего вида это открытый вопрос. Для точек в выпуклом положении ответ "да".

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