Математика *

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

Допустим, мы запустили АБ‑тест, рандомизировали клиентов, и теперь хотим оценить эффект фичи на средний чек. Средний чек — это пример ratio‑метрики или метрики отношения: считаем отношение суммы покупок к их количеству. Как анализировать эффект на такую метрику?

Казалось бы, средний чек — это среднее, и можно использовать просто t‑test. Но t‑test предполагает независимость наблюдений, а чеки могут быть зависимы — один клиент может совершить несколько покупок. Как следствие, мы завышаем ошибку первого рода и находим эффект там, где его нет.

В этой статье разберём, как с этим работать: корректно считать эффект, дисперсию, p‑value и доверительный интервал. Придём к дельта‑линеаризации, которая позволяет сравнивать исходный средний чек через привычный поюзерный тест. Заодно разберём, как использовать CUPED с дельта‑методом, и покажем связь с OLS с кластерными ошибками.

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

Один из привычных способов ускорить нейросеть — квантование. Переход от вычислений с плавающей запятой к 8-битным целым числам позволяет получить более быструю модель с близкой точностью. Можно пойти дальше: ранее мы предложили 4.6-битные сети, сравнимые по скорости с 4-битными, но заметно превосходящие их по точности. Однако уменьшение разрядности — не единственное, что можно изменить в нейросетевых вычислениях. Что, если оставить веса и входные данные 8-битными, а пересмотреть способ накопления результатов умножения?

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

Математики, инженеры, экономисты – все изучают симплекс-метод. Кто-то тут же забывает, но это нормально. В этой статье попробуем простым языком, опираясь не на формулы, а на здравый смысл, объяснить, как это работает.

Ультрафинитизм — философию, которая отвергает бесконечность, — долго считали математической ересью. Но он же помогает делать открытия в математике и за её пределами. 

Дорон Цайльбергер — математик, который уверен: у всего есть конец. Как ограничены мы сами, так ограничена и природа, а значит, и числа. Выгляните в окно: там, где другие видят непрерывный мир, который неумолимо течёт от мгновения к мгновению, Цайльбергер видит Вселенную, которая тикает, как часы. 

Доброго времени суток, уважаемые посетители 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-приема.

У моей собаки Pin двенадцать сервоприводов, десять килограммов веса и ни грамма железа: она живёт в браузере. Тем не менее она трусит рысью со скоростью 35 см/с, держит курс по гироскопу и однажды села на хвост, когда я попробовал научить её прыгать.

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

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

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

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

Disclaimer: в преддверии ожидания публикации от OpenAI новых решенных задач (которые не вошли в DevDay, как хотелось бы) делюсь обзором на понимание, зачем человечеству открытые задачи науки и как они улучшают нам жизнь.

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

А вот попытка решить фундаментальную задачу часто оказывается важнее самого ответа.

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

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

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

5 октября американские исследователи Вирджиния Василевска-Уильямс, известная своими быстрыми (и безумно сложными) алгоритмами перемножения матриц за вместо и её бывший аспирант Джош Алман опубликовали препринт на arxiv.org, демонстрирующий алгоритм решения задачи 3SUM за .

Это знаковое событие в узких кругах. Во-первых, раньше предполагалось, что решить эту задачу быстрее, чем за , невозможно. Во-вторых, вместе с ней наконец решилась быстрее, чем за , задача нахождения кратчайших путей между любыми парами вершин в графе (All-Pairs Shortest Paths, APSP) — по-настоящему практическая задача вычислительной геометрии. В-третьих, мало того, что корректность работы проверяла закрытая модель Anthropic — авторы также утверждают, что Claude нашёл изначальный алгоритм, после чего учёные осознали и улучшили его.

В этой новости я очень кратко перескажу долгий путь, который привёл к этому открытию, и опишу роль LLM в финале этого пути.

В данной статье докажу, что чисел-близнецов бесконечно!

Напомню, числа-близнецы (или простые близнецы) — это пары простых чисел, которые отличаются друг от друга ровно на 2. Например, (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) и так далее.

У чисел-близнецов есть свойство которое поможет нам в доказательстве - формой представления, где все пары чисел-близнецов, кроме (3,5), имеют вид (6n-1, 6n+1).

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

Хочу рассказать, что я выяснил по этой части за пару дней.

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

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

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

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

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

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

Код и списки выложены в публичном репозитории на GitVerse по ссылке: https://gitverse.ru/mshshukin2005/real-schemes-degree8

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

Речь пойдёт о Шестнадцатой проблеме Гильберта.

Шестнадцатая проблема Ги́льберта — одна из 23 задач, которые Давид Гильберт предложил 8 августа 1900 года на II Международном конгрессе математиков.

Исходно называлась «Проблема топологии алгебраических кривых и поверхностей». Впоследствии фактически разделилась на две похожие проблемы в разных областях математики:

исследование взаимного расположения овалов вещественных алгебраических кривых степени n (и аналогичный вопрос для алгебраических поверхностей);

получение верхней оценки на число предельных циклов полиномиального векторного поля степени n (и исследование их взаимного расположения).

Источник:https://ru.wikipedia.org/wiki/Шестнадцатая_проблема_Гильберта

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

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

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

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

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

«В последние месяцы успехи искусственного интеллекта в решении крупных математических проблем всё чаще становятся новостями далеко за пределами профессионального математического сообщества. Но решение задач — это лишь средство и косвенный показатель продвижения к более глубокой цели: концептуальному пониманию и появлению новых идей. Если в мире ИИ об этой цели забыть, средство способно начать разрушать то, чему оно должно было служить. Массовое производство всё новых утверждений и ответов — «истинно» или «ложно», «доказано» или «опровергнуто» — с постоянно возрастающей скоростью может не обогатить математическую почву, а, напротив, истощить её прежде, чем на ней успеют возникнуть новые идеи.» /11 сентября 2026. Декларация 25 филдсовских лауреатов[1]/

Одна из таких задач — Гипотеза простых чисел-близнецов[2]. Подробности гонки за ее доказательством описывает Science News[3]. Заявлено, что искусственный интеллект обошел людей и улучшил до 186 рекорд для bounded gap between primes (предыдущее достижение было 246 — проект Polymath, 2014 год). Но это не настоящий финиш. И уж тем более, ничего не добавилось к пониманию проблемы. Общепризнано, что необходимы принципиально новые идеи.

Из ответа Google: «Итог: Консенсус в академической среде однозначен — чтобы превратить уменьшающийся интервал (будь то 246 или 186) в честную двойку, математическому сообществу нужен качественный ментальный сдвиг и абсолютно новые структуры, а не просто мощные суперкомпьютеры и оптимизация старых формул.»

Между тем, вожделенный новый подход уже найден (без участия ИИ)…

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

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

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

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

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

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

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

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

Многие слышали об оптоволокне и знают, что оно представляет собой магистральные каналы передачи данных (если хотите разобраться, как работает оптоволокно, вот отличный ликбез). По отповолокнам, проложенным по дну океанов, ежедневно прокачиваются Зетабайты гифок с котиками и AI слопа, а вероятность передать бит с ошибкой держиться на уровне 10^-10, т.е. один ошибочный бит (даже не байт) на 1 Гб данных. Естественно потребность в высокой скорости соединения неулонно растёт и для оптоволокна повился свой аналог закона Мура, гласящий, что скорость передачи удесеряется каждые 4 года. В этом цикле статей мы поговорим о том, есть ли предел скорости передачи данных для оптоволокна, попробуем его оценить и можно ли этот предел достигнуть на практике.