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

О том как перемножать матрицы n×n
(II. или о случайных блужданиях на flip-graph)

Продолжаем решать задачу о поиске оптимального алгоритм для умножения матриц (начало в посте выше). Хотим найти за наименьшее число троек (триад) n²-мерных векторов (u, v, w) разложение Tᵢⱼₖ = Σ uᵢ vⱼ wₖ . Число троек называют рангом r. Дальше правильное разложение буду обозначать за UVW(r).

Рассмотрим некоторое разложение UVW(r=n²), такое всегда существует. Если у двух триад совпадает один из векторов, то можем сделать flip и перейти к новому UVW(r). Продолжаем делать случайные флипы, пока у двух триад не совпадёт два вектора, тогда можем сделать reduction и попасть в UVW(r-1). Если к операциям добавить ещё путь к UVW(r+1), то получим образующие для flip-graph, но нам часто достаточно ходить горизонтально и вниз.

Просто случайными блужданиями по flip-графу здесь (и тут с учётом симметрий) и нашли рекордные на сегодня схемы: r=93 для n=5 и r=153 для n=6 (было 98 и 160). Интересно, можно ли как-то сделать блуждания направленными.

Мою PyTorch реализацию (ну приятно же на gpu случайно блуждать) можно потыкать на
github.com/k1242/flip-graph
(или поддержать звёздочками). Для n=3 находит оптимальные алгоритмы за 10с, а это, между прочим, поиск кратчайшего пути на графе в 2⁷²⁹ ~ 10²¹⁹ вершин :)

О том как перемножать матрицы n×n
(I. или как метрополисом оптимально по графу на 2⁶⁴ вершин шагал)

На компьютере хорошо складывать числа, а не умножать, поэтому если бы умножать матрицы 2х2 можно было бы не за 8 умножений, а за 7, то всё стало бы немного быстрее. И в 1968 году Штрассен выяснил, что да, можно!)

Операция умножения матриц Cᵢⱼ = Aᵢₖ Bₖⱼ является билинейной и может быть переписана в виде Cᵢ = Tᵢⱼₖ Aⱼ Bₖ (сплющили матрицы в 4d векторы). Тензор Tᵢⱼₖ определяется только размерами матриц и универсален для всех (C, A, B). Осталось сделать декомпозицию тензора Tᵢⱼₖ = Σ uᵢ vⱼ wₖ по минимальному набору триад (u, v, w), а это уже NP-complete задача. Если воспринимать добавление триады как шаг на графе, а тензоры Tᵢⱼₖ как вершины, то формально мы ищем кратчайший путь в графе на 2^(n⁶) вершин степени 2^(3n²). Даже для n=2 у нас уже 2⁶⁴ вершин.

Зато можем попробовать отжиг (как тут или тут). И это работает, на графике d представлен мой процесс отжига для n=2, который по итогу 8 минут работы находит таки оптимальную декомпозицию на 7 умножений (даже 14 разных её реализаций, среди которых и аналогичная Штрассену). А на графиках a, b, c иллюстрация декомпозиции из AlphaTensor (которые своим RL понаходили такие разложения вплоть до n=5).

P.S. В комментариях можно найти минимальную реализацию отжига в пределах 100 строк)

О том как stockfish смотрит на шахматную доску ♟
(или о выученных фильтрах для оценки позиции)

Последние лет 5 на соревнованиях среди шахматных программ выигрывает stockfish, а всё благодаря тому что в 2020 году перешёл на оценку позиции нейросетью архитектуры NNUE (и это что-то само по себе прекрасное).

Рассмотрим одну из версий архитектуры. Шахматная доска кодируется one-hot через (piece_square, piece_type, piece_color) — положение фигуры, тип фигуры и цвет фигуры, всего получается 8×8×6×2=768 чисел на вход, из которых не более 32 единичек (не более 32 фигур), а остальные нолики. Первый слой отображает этот one-hot вектор в 64 features, которые потом дорабатываются в маленьком MLP.

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

Тут явно видно, как ходят фигуры. А ещё, что вклад черных это буквально отрицательный вклад белых. Да, вы смотрите прямо в мозги stockfish :)

С наступающим Новым Годом!)🎄

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

P. S. Мы тут в лабе из атомов собрали и сфотографировали микро оленя, не могу не поделиться. Да, каждая светящаяся точка это 1-4 атома ⁶Li, удерживаемых своим лазерным пинцетом)

P.P.S. Если хотите помочь добавить новые реакции, тут можно бустануть канал 👉👈

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

Возьмём в диапазоне [-π, π] для θ₁ и θ₂ решётку двойных маятников, и посмотрим на их эволюцию (на рис. cos(θ₂)), демонстрирующую хаотическое поведение для достаточно больших энергий (чувствительны к начальным условиям).

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

P.S. сюжет появился в комментариях замечательного канала "человек наук", спасибо за вдохновение)
P.P.S. кстати это всего 20 строчек кода и около секунды вычислений, см. в комментариях)

О монетках (и центре масс)

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

О цвете неба 🌅
(и чувствительности зрения)

Почему небо голубое, а закат красный? Потому что для нашей атмосферы основной вклад вносит Рэлеевское рассеяние, для которого сечение рассеяния ~1/λ⁴. Спектр излучения солнца (самое черное тело в ближайшем окружении, излучает по Планку с температурой около 6000K) смещается из-за рассеяния, и потом перемножается с чувствительностью наших в глазах колбочек (~ гауссовы пички, см. RGB на картинке).

Цвет неба — рассеянный свет, вот и получается голубой. Цвет заката — то что осталось после рассеяния. Можем сказать что доходящий до нас свет это exp(-L•relay(λ))•sun(λ) по Бугеру-Ламберту-Бэру. Получается, что чем длиннее L (путь света через атмосферу), тем больше смещается цвет в красный. Вот и получается алый закат)

P.S. а почему на Марсе наоборот? 👀

Как атмосферные эффекты влияют на изображение звезды?
#astro

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

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

Анимация: как изображение звезды поплывёт под таким "ветром". Слева условная плотность атмосферы в пересчёте на толщину фазовой пластинки, справа – непосредственно изображение. Ноутбук в комментариях.

А почему заряд электрона равен заряду протона?

О стекле и воде
(точнее их дисперсионных свойствах)

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

Показатель преломления падает при увеличении длины волны (для стекла|воды от n=1.53|1.34 для синего до n=1.51|1.33 для красного). Изменения показателя преломления связаны с тем, что нейтральные частички внутри поляризуются, электроны начинают следовать за внешним ЭМ-излучением (светом). И они гораздо активнее это делают приближаясь к резонансам, которые мы получается ожидаем увидеть в УФ области.

И действительно, стекло (силикатное) и вода непрозрачны для УФ до 300 нм (дома особо не загоришь), что прилично портит жизнь работающим с УФ лазерами лабораториям. Чуть лучше кварцевое стекло, пропускающее до 200 нм. Но в УФ диапазоне фотоны становятся настолько бодрыми и энергичными, что что-нибудь обязательно возбудят и обязательно поглотятся. Так в соседней лабе светят на He+ 60нм, и им приходится сразу после генерации света без зеркал и оптики ставить пойманные ионы гелия.

Воот, в общем теперь вы знаете почему стекло прозрачное и откуда берётся дисперсия)