Математика *

Anthropic сообщила о девятипетлевом расчёте Claude — поднявшем ранее опубликованный результат для этой амплитуды с восьми до девяти петель.

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

Материал изложен постепенно, от простого к сложному, от основ к научным результатам. От уравнения Шрёдингера и одной петли постепенно доходим до bootstrap и символов.

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

Доброго времени суток, уважаемые посетители Habr!
Данная статья будет короткой, но полезной.

В одной из предыдущих статей, уже описывал вычисление sin(x)/cos(x) с применением разложения в ряд Фурье с фиксированной точкой. Вычисление тригонометрических функций, в моем случае занимало порядка 125-130 тактов на пару (sin+cos) на процессорном ядре Cortex M7 (STM32H750). При этом, код компилировался для архитектуры Cortex M3. Точность sin/cos просчитанного таким образом составила менее 1.5LSB. Google посчитал ее как 1.2-1.3LSB, с минимальной дисперсией. Это уже дало динамический диапазон ~183dB. Для сравнения, полный динамический диапазон человеческого уха 120dB от болевого порога до шелеста листвы. А динамически диапазон звука который человек слышит одновременно порядка 40-60dB. Несколько позже поясню для чего приведено сравнение.

В общем и целом такого динамического диапазона и скорости уже достаточно чтобы производить операцию квадратурной свертки сигнала с частотой дискретизации до 450-500KHz. Кстати, на STM32F103C8T6, это заняло бы ~1.8uS на квадратурный отсчет. Т.е. с отключенными прерываниями процессор бы успел выполнить расчет одного бина честного преобразования Фурье в реальном времени. Это эквивалентно квадратурной демодуляцию на одной произвольной поднесущей до частоты 250КГц (хотя лучше брать Fsample/4 ), что позволяет работать с полосой до 125КГц, на простом контроллере в реальном времени.

Однако, этого мало для полноценной обработки сигналов. И тут я задумался. Как можно значительно повысить скорость работы и почти не потерять в точности? Первое что сделал,- разбил преобразование на блоки, фаза которых непрерывна. Это позволило работать с блоками отсчетов, которые, затем можно суммировать скользящим окном со сложностью O(1). Это привело к эффекту квадратурной демодуляции сигнала и без повышения сложности позволяло работать с малыми временными сдвигами. Фактически пришел к поблочной корреляция. Нечто вроде временного Rack-приема.

Представьте, что у вас одновременно запущено несколько десятков экспериментов. В каждом миллионы пользователей и несколько метрик с ежедневным пересчётом. У нас как раз такой кейс, поэтому ещё при проектировании платформы мы подумали, что считать метрики на уровне пользователей будет слишком дорого и медленно…

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

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

Я играю в Factorio как любой нормальный человек: для планирования фабрики пишу код матричных вычислений.

Но до этого мы ещё доберёмся. Если же вам не терпится, можете просмотреть мой новый онлайн-калькулятор.

Введение в Factorio и качество

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

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

Выпущенное в 2024 году расширение Space Age добавило новые игровые механики, в том числе и качество (Quality): у каждого изделия и рецепта теперь есть пять уровней качества: ⚀ обычное, ⚁ необычное, ⚂ редкое, ⚃ эпическое и ⚄ легендарное. Каждый уровень (в зависимости от конкретного изделия) повышает характеристики, например, ускоряя производственные машины или повышая производительность модулей продуктивности. Высококачественные изделия можно изготавливать непосредственно из ингредиентов того же качества, однако единственный способ повышения качества — это применение новых модулей качества.

Теорема о четырёх красках формулируется очень просто: можно ли на непрерывной карте раскрасить каждую область одним из четырёх цветов так, чтобы соседние области были разных цветов?

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

Один из самых знаменитых таких случаев — теорема о четырёх красках, задача, изменившая само представление математиков о своей науке.

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

В середине XIX века головоломка о раскраске карт быстро стала настоящей навязчивой идеей. И сегодня продолжаются поиски более простого решения этой обманчивой задачи — простой на первый взгляд и трудной для решения.

Всем привет! На связи Денис Зорин и Гриша Засько, мы работаем в ASL — лаборатории прикладной статистики Т-Банка. Помогаем командам проводить A/B-тесты на масштабе всей экосистемы: от дизайна эксперимента до анализа результатов. Еще мы развиваем A/B-платформу, инструменты для экспериментов и методы, которые помогают ускорять тесты без потери статистических гарантий.

Расскажем о задачке, с которой столкнулись в тестах с множественными сравнениями. Когда в эксперименте несколько целевых метрик, нужно контролировать вероятность ложноположительного результата. Часто для этого используют поправку Бонферрони: общий уровень значимости делят поровну между метриками, это простой и надежный метод.

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

Плеер показывает у трека «ми минор», но как он это узнал? Программа не слушает гармонию, как музыкант: она считает, сколько звучит каждой из 12 нот, и ищет гамму, на которую набор похож сильнее всего. Разбираю алгоритм Крумхансл-Шмуклера на реальных треках, показываю, где он путает квинту и родственную тональность, и что тут меняют нейросети.

«— Когда я вижу ответ LLM, я скорее поверю, что где‑то сидят миллион индусов, чем то, что ответ есть результат перемножения матриц. — Я тебе покажу „молекулу“ этих нейросетей и ты поверишь, что индусы заняты не этим.»

После этого диалога с Юриком, держу слово. Написал ему письмо, и решил — пусть и остальные прочтут. Прошу простить за несколько развязный тон письма, но это все‑таки личное письмо и в нашем общении оно допустимо.

«Дорогой, Юрик!»

Стало обидно и за матрицы и за индусов, и я обещал тебе, что покажу как можно спомощью первых, заменить вторых. Я обещал показать работу нейросети на примере решения ХОР, но я начну на шаг раньше, не потому, что ты этого не знаешь, а так мне, — тугодуму, легче удержать логику объяснения.

В прошлом году я написал пост про известную шифровальную машину нацистов Как работает машина Enigma M3 (для флота) / Хабр .

Enigma широко использовалась в немецких вооружённых силах, включая армию и флот.

Но куда менее известной является машина Lorenz SZ 42, хотя она была не менее важна.

Из этой статьи вы сможете узнать, как шифровали сверхсекретную связь высшего немецкого командования, как ошибка оператора в 1941 году помогла раскрыть устройство Lorenz и почему в 1944-м для чтения таких сообщений появился электронный Colossus.

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

Кроме того, в процессе работы над материалом было найдено довольно много первоисточников, которые неплохо сохранить внутри такой статьи. В самом низу есть cайты, архивы, интерактивные модели и первоисточники, в статье много кода на Python.

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

Самая первая попытка выглядела так: в Уичито, штат Канзас, по объявлению в газете набрали 60 добровольцев, и до адресата в Кембридже дошли 3 письма, каждое из которых прошло в среднем через восемь человек, то есть девять рукопожатий. Эти цифры Милгрэм так и не опубликовал, а в популярную статью попала ровно одна цепочка из трех, и, как мы дальше увидим, самая короткая.

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

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

Есть река и надо перевести на другой берег козу, капусту и волка. В лодку помещается только крестьянин и что-то одно из груза: капуста, волк или коза. Если на одном берегу без присмотра крестьянина оставить козу и капусту, то коза съест капусту. Если оставить волка и козу, то волк съест козу. Как перевести груз без потерь?

Я представил формальное решение на основе конечного автомата.

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

Итан Сигел (американский астрофизик‑теоретик и научный журналист, автор рубрики «Спросите Итана», один из пропагандистов современных научных знаний), разбирает один из нерешённых вопросов современной физики: куда девается информация о различных частицах, попадающих в чёрную дыру, при том что чёрная дыра испарится путём излучения Хокинга и исчезнет?

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

Всем привет!

Не давно сделал свою Gated RNN, то есть с другой математикой, ни как у LSTM, GRU и подобного.

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

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

Мы решили разобраться всерьёз. Можно ли построить Шри Янтру абсолютно точно? Сколько таких фигур существует? И если их много, можно ли честно, без подгонки, выбрать среди них одну — «идеальную»?

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

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

Конечно, теперь Twitter называется X, но я буду пользоваться старой терминологией и говорить о твитах, Twitter и так далее. Традиционное ограничение на длину твита составляет 280 символов. И, разумеется, в твите можно записывать числа. Например, можно просто заполнить весь твит цифрами. Допустим, я пишу твит - вот мой твит - и заполняю его цифрами: 28765 и так далее. Я могу заполнить весь твит цифрами и тем самым записать некоторое число. Какое наибольшее число можно записать таким способом?

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

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

Как показали математики Ева Миранда из Политехнического университета Каталонии в Испании и Исаак Рамос из Швейцарской высшей технической школы Цюриха, один шар, отскакивающий от стенок двумерного «бильярда» особой формы, может имитировать универсальную машину Тьюринга — такую, которая способна моделировать любую другую машину Тьюринга.

Для Миранды эта работа стала итогом многолетних попыток свести механическую систему к минимальному числу деталей, необходимому ей для работы в качестве компьютера. «Каков минимальный геометрический механизм, позволяющий физической системе выполнять универсальные вычисления, и как мы можем его обнаружить? — спрашивает она. — Бильярд представляет собой самую суровую проверку такого процесса упрощения. Одна‑единственная частица. Вся программа записана в геометрии границы».

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

Чтобы оптимизировать производительность больших языковых моделей (LLM), необходимо понимать весь программный стек. Мне не удалось найти подробную статью, которая показывала бы этот стек как общую картину, поэтому я решил написать такую статью сам. Эта статья не является исчерпывающим обзором или набором наилучших практик. Здесь я в большей степени делюсь моими общими представлениями о том, как выглядит ландшафт современных LLM‑систем.

Во‑первых, любая система проектируется с расчётом на достижение конкретных целей с учётом заданных ограничений. В LLM‑системах наиболее принципиальные цели связаны с увеличением пропускной способности и минимизацией задержек. Два этих показателя необходимо оптимизировать в рамках ограничений, задаваемых тремя принципиальными факторами: вычислительные (скорость аппаратных операций и поддерживаемые типы), память (ёмкость и иерархия) и коммуникация (ширина передачи данных в памяти и сети, задержка и иерархия). Эти концепции отлично рассмотрены в книге Scaling Book от Google, а именно в разделе Roofline.

А задумывались ли вы, почему вооон тот водитель, который объехал вас шашечками по соседней полосе, не прав? С 50-х годов прошлого века об этом много кто размышлял и даже кое-что посчитал. Только начиналось все не с нейросетей и не с анализа миллионов записей с GPS. 

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