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

О том как одиночные атомы фотографирую#coldatoms #masterthesis@qdiagДопустим вы хотите сфотографировать атом, один. Естественным было бы посветить на него из лазера резонансным светом и собрать флюоресцирующие фотоны. Но каждый раз поглощая фотон, атом получает толчок на h/λ в одну сторону (дрейф). К тому же излучая фотон атом толкается на h/λ в случайную сторону (диффузия). Естественно было бы убрать дрейф, если светить с двух сторон. И это оказывается ужасной идеей! Атомы сидят в решётке, достаточно близко к друг другу, поэтому хочется и дрейф и диффузию уменьшить. На fig 2b(left) видно как со временем атом сдувает вправо, fig 2b(middle) мы пробуем светить с двух сторон и атом очень быстро убегает от центра (в комментариях объяснение). Решением будет светить с двух сторон по очереди (fig 2a, fig 2b(right)), тогда атом и в среднем с нулевым импульсом и от центра далеко не уходит. И теперь можно получить замечательные фотографии, как на fig 4b(left). От каждого атома до камеры у нас доходит около 30 фотонов, и этого оказывается достаточно, чтобы их найти в 99% случаев. Немного поработав с фотографией, получается fig 4b(right), где каждый атом это такое синее пятнышко.P.S. У меня через полтора месяца диплом, так что буду рассказывать вам про графики из диплома)

О том как перемножать матрицы 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. Если хотите помочь добавить новые реакции, тут можно бустануть канал 👉👈