Математика *

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

Для Цейлбергера вера в бесконечность — это как вера в бога. Это заманчивая идея, которая льстит нашей интуиции и помогает нам осмыслить всевозможные явления. Но проблема в том, что мы не можем по-настоящему наблюдать бесконечность, и поэтому не можем по-настоящему сказать, что она собой представляет. Уравнения определяют линии, которые уходят за пределы доски, но куда? Доказательства пестрят многозначительными многоточиями. Эти уравнения и доказательства, по мнению Цейлбергера — многолетнего профессора Рутгерского университета и известного специалиста в области комбинаторики — одновременно «уродливы» и ложны. Это «полная чепуха», — сказал он, выдыхая каждый слог хриплым голосом, который, казалось, износился от того, что он доказывал свою точку зрения.

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

Бред, конечно. Мозг работает иначе, и ИИ крайне далек от понимания того, как это устроено, как мозг воспринимает реальность, превращает ее сначала в данные, а затем в информацию в привычном нам смысле. Там нет привычной для ИИ математики – дифференциалов, интегралов, байесовских схем и обратного распространения ошибки. Логика, которой следует «процессинг» мозга, качественно иной, чем логика операций над буквами, цифрами и их комбинациями; это не классическая математика и не лингвистика в узком смысле.

Обычно энтропия — мера хаоса. Но наш сегодняшний герой — IH-анализ (Information-Entropy analysis) — вычисляет информационную энтропию, чтобы измерить обратное: степень детерминированности связи между признаками и целевой переменной. Мы будем вычислять: насколько утверждение «если А, то Б, и, если не А, то и не Б» выполняется в наших данных устойчиво. Одновременная работа с категориальными и количественными признаками нас не затруднит.

Нижеприведенный блог был написан в 2019 году. Через год мы с коллегой усовершенствовали нашу систему прогнозирования и выиграли промышленное соревнование весной 2020 — в период начала пандемии COVID-19. По итогам того эпопейного соревнования я написала статью The Short-term Electricity Consumption Forecast Competition Under COVID-19 Lockdown Conditions (английская и русская версии). В январе 2022, прямо накануне ..., подала эти тезисы на International Symposium on Forecasting 2022. В апреле они были приняты и вопреки всем прогнозам я доехала до Оксфорда в июле 2022 и выступила с докладом. Ниже история о том, как все это начиналось...

Итак мы обсудили задачу классификации и метрики качества классификационных моделей.

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

И первый кандидат у нас логистическая регрессия

«На ноль делить нельзя». Все мы заучили это правило в школе, но мало кто реально понимает, как этот запрет работает под капотом.

Предлагаю закрыть этот гештальт раз и навсегда. В статье разбираем деление на ноль с двух сторон: сначала наглядно (на примере сисадмина и серверных квот), а затем строго математически (через алгебру и аксиомы).

Спойлер: делить 0 на 0 тоже нельзя, но причина там совершенно другая.

Формула интегрирования по частям для интегралов от функций одной переменной известна всем со школьной скамьи. В вузах она изучается в многомерной версии в курсах математического анализа и УРЧП. В этой статье мы приведем инвариантную геометрическую версию этой формулы и отметим некоторые конструкции теории динамических систем, с которыми она естественным образом связана.

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

Сколько нужно бит, чтобы представить одно число из континуума ℵ₁ чисел?

Ответ: ℵ₀ бит.

Сколько нужно бит, чтобы представить одно число из счётного множества ℵ₀ чисел?

Ответ: ℵ₋₁ бит.

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

ℵ₋₁ это достаточно.

В разработке ПО произведение двух целых чисел часто вычисляется до фиксированного количества битов с переполнением. Возьмём для примера 8-битные целые. Если умножить 127 на 127, то мы получим число 1 в виде 8-битного беззнакового целого с переполнением. Реальное полное произведение равно 16129. Для представления 16129 обычно используются 16 бит точности.

Таким образом у нас появляется понятие полного произведения. Полное произведение двух 32-битных чисел обычно представляется при помощи 64 бит. У меня возник вопрос, какую долю всех 64-битных чисел можно записать, как произведение двух 32-битных целых.

В первой статье я высказал простую идею: если вычисление можно свести к конечной таблице операции, его можно проверять, а не угадывать. То есть его можно свести не к "модель выдала вероятность 0,67", а просто открыть таблицу и сказать: вот ячейка, вот результат, rc=0.

Эта статья — прямое продолжение первой статьи (сейчас у меня на руках значительно отличающаяся рабочая модель ИИ-движка). Но сразу честно: я не собираюсь раскрывать здесь внутреннюю кухню "GALO AI". Ни устройство нейрона, ни приватные маршруты мышления. Покажу только основополагающую математику, вернее, маленькую конечную структуру, которую можно взять руками, прогнать скриптом и попытаться сломать контрпримером.

Ключевая идея проста до невозможности: я взял обычное сложение по модулю и изменил в его таблице ровно одну строку.

Этого хватило, чтобы структура перестала быть полем, кольцом и моноидом.

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

Во многом красота математики заключается в том, что благодаря произвольному выбору можно связать две кажущиеся далёкими концепции. Впервые я увидел этот паттерн в вопросе на Math Stack Exchange. Его задал пользователь dwymark, а ответил на него Грег Мартин; вопрос связан с распределением простых чисел, а также с рациональными аппроксимациями .

Этот пользователь баловался с созданием графиков данных в полярных координатах, то есть нанесением точек в 2D-пространстве, но не по обычным координатам XY, а по расстоянию от точки начала координат, обычно называемому (радиус), и по углу прямой относительно горизонтали, обычно называемому «тета», .

В четвертой части мы начали изучение задачи классификации и разобрали метод kNN.

Мы уже дошли до той точки, когда можем построить худо-бедно работающий классификатор. Но если нас спросят: “а насколько хорошо он работает?”,
то максимум, что мы пока сможем ответить — что-то вроде: “ну... на тестовой выборке модель правильно ответила в p% случаев”.

С одной стороны, как гласит древняя пословица: лучше иметь 500 рублей, чем 200. Но гарантирует ли высокий p% качество модели?

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

Аннотация. В статье рассматривается физическая основа измерений Ekahau Sidekick и механизм применяемого RSSI‑offset с позиций теории антенн, теории шума радиоприёмных устройств, статистической теории сигналов и стандартов IEEE 802.11. Показано, что scalar RSSI‑offset является линейным сдвигом уровня и не моделирует ни реальный SNR клиентского устройства, ни структуру QAM‑созвездия, ни алгоритм rate adaptation, ни роуминговое поведение. Помимо пяти независимых физических и системных причин неточности, рассматриваются системные упрощения Ekahau, касающиеся MIMO‑усиления, многолучёвости, оценки airtime и визуализации SNR. Приведены верифицированные численные оценки погрешности для конкретных сценариев и практические рекомендации.

В продолжение статьи Переворачивающиеся при умножении числа, которую я написал в 2024 году, представляю небольшую статью-обновление.

Переворачивающимися при умножении числами я назвал такие числа a и b с одинаковым количеством цифр, что выполняется равенство:

a ∙ b = concat(reverse(b), reverse(a)),

где операция reverse записывает разряды числа в обратном порядке, а операция concat соединяет два числа в одно. Например, выполняются такие равенства:

218252 ∙ 837281 = 182738 252812
43275098 ∙ 77535533 = 33553577 89057234
47208027 ∙ 56843862 = 26834865 72080274
и т. д.

Алгоритмы нахождения переворачивающихся чисел приведены в оригинальной статье и комментариях к ней.

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

В третьей части мы закончили с линейной регрессией. Теперь пора перейти к задаче классификации․

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

Заменив самое фундаментальное понятие в топологии, Питер Шольце и Дастин Клаузен сделали первый шаг в гораздо более масштабной программе по изучению того, почему числа ведут себя именно так.

Как понять смущающую интуицию задачу за секунду - метод экстремальных параметров.

Бывало ли у вас такое - вы смотрите на условие задачи, логику алгоритма или даже жизненную ситуацию, интуиция кричит: «Здесь всё очевидно!», а строгая логика, тесты или реальность упрямо показывают совершенно другой результат?

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

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

Долгое время, схемы выработки ЭЦП, для которых была доказана безопасность в схеме ROM считались надёжными, однако всё изменилось после публикации атаки ROS, о которой мы поговорим позже. В основе этой атаки лежит принцип параллельного выполнения, при котором противник может получить преимущество в подделке подписи, открывая множество сеансов параллельно.

Новость «ИИ опроверг важную гипотезу Эрдёша» нашумела, в том числе на Хабре. Но всем, кроме математиков, по громким заголовкам сложно понять масштаб события. Что это значит: революцию в науке или мелкую разовую удачу? Как это правильно оценить?

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

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

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