Алгоритмы и структуры данных для численных вычислений с автоматической оценкой точности
Специалист отдела перспективных исследований компании «Криптонит» Игорь Нетай на протяжении нескольких лет изучал фундаментальную проблему быстрой потери точности вычислений. Она связана с повсеместно применяемым форматом экспоненциальной записи чисел и наиболее остро затрагивает сферы AI, HPC и Big Data.
Результаты исследования опубликованы в международном рецензируемом журнале IJAINN. В своей научной работе Игорь предлагает метод оценки потери точности: использовать расширенный формат чисел с плавающей точкой — xfp и написанную им свободно распространяемую библиотеку.
В новой статье Игорь Нетай подробно разбирает, как появляются и распространяются погрешности вычислений, связанные с машинным представлением чисел в формате «с плавающей точкой» по стандарту IEEE754.
Автор показывает, как оценивать погрешности при различных вычислительных операциях, как оценки могут зависеть от самих функций, а также особенностей реализации, среды вычисления и прочих факторов. Также Игорь демонстрирует, как с помощью трёхцветной схемы разметки вычислений наглядно оценить точность для некоторой коллекции функций, наиболее часто используемых для работы с массивами данных и обучения нейронных сетей.
Дополнительно для сильно оптимизированных функций, таких как умножение матриц, он предлагает метод быстрой оценки точности и предлагает, как можно улучшить эту оценку. Бонусом для поклонников математического хардкора в статье доказывается ряд теорем о точности операций с матрицами.
История вопроса
Развитию ИТ часто мешает бремя наследия. Помимо необходимости обеспечивать совместимость со старым оборудованием и программами, сейчас проявляется и более фундаментальная проблема — сам способ записи действительных чисел.
Вот уже более века используется представление чисел в формате с плавающей точкой (float point, FP). Это может стать бомбой замедленного действия. Со времён первых ЭВМ объёмы вычислений и их сложность выросли на порядки. При этом возросло повсеместное влияние неточностей и связанные с ними риски — особенно в сфере больших данных и искусственного интеллекта.
Мало кто задумывается о проблеме постепенного снижения точности вычислений. Когда требуется повысить точность, просто увеличивают разрядность. Если не хватает одинарной точности (FP32), используют двойную (FP64), а в редких случаях прибегают и к четверной точности (FP128).
К сожалению, такой грубый способ работает не всегда, поскольку длина мантиссы — лишь вершина айсберга. Есть целый ряд фундаментальных математических проблем, связанных с использованием формата FP, и мы обсудим их ниже.
В эпоху больших данных и моделей машинного обучения с миллиардами параметров повышение разрядности вовсе не практикуется. Наоборот: ради экономии памяти и повышения скорости точность вычислений часто снижают до половинной (FP16), а то и сильнее. Так работают практически все популярные ИИ-сервисы, включая ChatGPT. При жёстком ограничении машинных ресурсов (например, в дронах, носимых гаджетах и многочисленных IoT-устройствах) точность и вовсе огрубляют до uint8 FP8.
С каждым днём весь этот зоопарк приближённых вычислений работает всё менее предсказуемо. ИИ галлюцинирует, автопилоты попадают в аварии, а по биометрии оформляют кредиты на посторонних людей. Если разработчик не понимает, где и почему происходит постепенная потеря точности вычислений, он уже не контролирует поведение программ, а в особенности — нейросетевых алгоритмов. Они становятся «чёрным ящиком» с ещё более непроглядными стенками, а для несведущих в математике —словно проявляют самосознание. Более того, это «самосознание» начинают подозревать в желании навредить людям. Проще поверить в злой ИИ, чем признать собственную небрежность в обучении нейронок.
Корень проблемы
Удивительно, но факт: вычисления, в которых используются числа с плавающей точкой, практически всегда неточны. Самый простой известный пример:
Он иллюстрирует последствия неточного преобразования десятичных дробей в двоичное представление чисел с плавающей точкой.
Ещё интереснее то, что точность результата некоторых математических операций может меняться в зависимости от способа вычисления. Особенно хорошо это видно при решении квадратных уравнений, где в качестве ответа можно получить два корня, один из которых вообще не будет содержать точных бит. Так происходит, если искать корень уравнения по стандартной формуле (а не альтернативным способом — при помощи теоремы Виета, что позволяет избежать полной потери точности). Также резко теряющий точность результат может получиться при вычитании близких по значению чисел и в операциях с матрицами.
«Ну и что? — скажете вы, — подумаешь, потеряли какой-то там знак после запятой. Число пи вообще до сотых округляют в большинстве расчётов, и ничего!». Сама по себе потеря точности не является проблемой до тех пор, пока её легко обнаружить. На практике это возможно только для сравнительно простых вычислений. По мере усложнения расчётов неточности накапливаются, сильно искажая результат.
Такие искажения можно заметить по мере роста масштабов: допустили отклонение в полмиллиметра на каждый метр, и вот уже не стыкуются половины многокилометрового моста. Это явный пример из материальной действительности, но есть и не такие очевидные — из мира машинного обучения.
Самообман ИИ
Давайте вспомним, как учится любая нейросеть. Через неё прогоняют большие объёмы обучающих данных снова и снова, постепенно повышая процент успешно выполненных заданий (или другую метрику на усмотрение разработчика). Её статистические показатели растут, разработчики радуются… однако в какой-то момент качественные метрики перестают улучшаться, а затем и вовсе деградируют. Возникает переобучение модели, приводящее к ухудшению обобщающей способности модели. В ней накапливается так много неточностей, что ИИ начинает галлюцинировать. Уровни шумов и входных данных становятся величинами одного порядка. Поэтому шумы обрабатываются наряду с верными данными, и с каждой новой эпохой обучения искажают логический вывод всё сильнее.
Наиболее распространённые фреймворки для нейронных сетей (Tensorflow и Torch) основаны на автоматическом вычислении градиентов и обратном распространении ошибок. Градиенты вычисляются как частные производные для заданной коллекции функций (базовая коллекция может быть расширена пользовательскими функциями с градиентами). Таким образом, вычисления фактически не связаны с численным дифференцированием. В то же время обучение нейронной сети до малых значений функции потерь обязательно будет приводить к вычитанию близких чисел. Тогда сама loss-функция начинает вычисляться неточно. В результате градиенты могут стать неточными, а нейронная сеть потеряет численную устойчивость. Как же с этим бороться?
Статистическими методами делать это уже пробовали, получается «так себе». Когда у вас огрубляются любые входные данные и промежуточные вычисления, то сколько ни повторяй, лучше не станет. Остаются чисто математические, численные методы.
Обычной целью численного анализа является разработка алгоритмов построения максимально точных аппроксимаций математических объектов. В настоящее время для многих прикладных задач численная точность игнорируется, а вычисления строятся, опираясь на стандартные функции, предоставляемые известными библиотеками. Игорь Нетай предложил способ автоматически выполнять оценки погрешности для заданной модели и алгоритма.
Для этого он написал библиотеку XNumPy, в основе которой лежит известная NumPy. Он дополнил её стандартные функции оценками уровня ошибки вычисления, что позволяет автоматически определить, является ли результат надёжным, или же его следует отбросить, чтобы использовать более точные алгоритмы или вообще другие вычислительные подходы.
С помощью XNumPy легко выяснить точность некоторого существующего алгоритма вычислений и отслеживать оценку его погрешностей параллельно с основным потоком данных. Оценённые погрешности хранятся в памяти в виде количества точных битов мантиссы.
Раскрашиваем биты
Имея исходные данные с некоторыми значениями погрешностей, мы должны выбрать между следующими подходами:
оценивать погрешности снизу (тогда части результатов, помеченные как неточные, не имеют смысла и не должны интерпретироваться);
оценивать погрешности сверху (тогда данные, помеченные как неточные, могут иметь некоторые вычислительные ошибки, в то время как все остальные данные точны);
нечто среднее без каких-либо гарантий.
Наиболее надёжным и дорогим способом является комбинация (1) и (2). При этом биты мантиссы делятся на три группы:
«черные» биты, которые являются шумными и бессмысленными;
«белые» биты, которые являются точными и надёжными;
«серые» биты в средней части, точность которых зависит от конкретных программных и аппаратных деталей, условий вычислительного процесса и других факторов.
«Черные» биты возникают в основном из-за неточности данных и распространения математических ошибок. В то же время «серые» биты возникают из-за численной нестабильности алгоритмов. Фактически, некоторые вычисления оценивают результаты в зависимости от начальных данных скачкообразно и не могут быть реализованы с помощью какого-либо численно устойчивого алгоритма.
Например, вычисление собственных векторов для плохо обусловленной матрицы будет иметь большие «серые» части мантиссы при использовании любого алгоритма.
Стандартные функции с плавающей точкой имеют явные производные, выраженные в элементарных функциях. Учитывая количество точных бит в аргументе, мы можем вычислить относительную погрешность для значения, возвращаемого функцией. Таким образом, мы можем получить оценку точных битов результата.
В этом случае мы рассматриваем любую такую функцию как атомарную числовую операцию, и способ оценки точности не зависит от выбранной реализации. Например, реализации основных функций (например, тригонометрических) могут меняться в разных версиях библиотек, и это может приводить к различиям в значениях, но способ оценки точности при этом не меняется.
Более сложным примером атомарной операции оказывается оценка точности для произведения матриц. Если мы вычисляем произведение матриц, то полагаемся на числовые значения, предоставляемые библиотеками типа blas/cublas/mkl. Хотя эти значения менее точны, чем вычисленные по явной формуле, они вычисляются существенно быстрее, и результат тоже может меняться в зависимости от версий библиотек, устройства, на котором выполняется вычисление и прочих факторов.
Находим чёрную метку
Мы можем оценить точность некоторых вычислений разными способами. В случае сложной функции можно оценить её общий коэффициент распространения ошибки, а также сделать то же самое шаг за шагом для её частей.
Хотя большая фрагментация может дать лучшую оценку, некоторые стандартные функции могут иметь специфическую программную и аппаратную реализацию во внешних библиотеках. Это накладывает ограничение на уровень разбиения функции для оценки её точности.
Например, вычисление тригонометрических функций (обычно зависит от glibc) или суммы массива (которая может быть векторизована и зависит от наличия инструкций SSE, AVX в процессоре) должны оцениваться как атомарные числовые операции. Другой сложной атомарной операцией, которая обычно зависит от внешних библиотек, является матричное умножение.
Деатомизация сложных операций, таких как умножение матриц, требует повторной реализации соответствующих зависимостей, таких как blas/cublas/mkl. Такие очень мощные инструменты не могут быть легко модифицированы и перенесены на другие платформы и аппаратные средства.
Переходим к расширенному формату FP
Мы покусимся на святое и предложим отринуть формат FP, так долго служивший нам верой и (не)правдой. Вместо него представим числовые типы данных xf64 и другие (например, xf32, xf16, xbf16), состоящие из следующих компонентов:
— числа с плавающей точкой типа f64 (или f32, f16, bf16), представляющего вещественное значение;
— числа типа u8 (оно же байт или unsigned char), представляющего количество точных битов вещественного значения.
Договоримся о том, что будем называть их расширенными числами с плавающей точкой.
Производить арифметические операции с ними и вычислять некоторые математические функции совсем несложно. Во всех случаях мы предполагаем, что результат вычислений с вещественными значениями известен и определён в формате IEEE 754, и имеем возможность оценить точность этого результата.
Ещё у нас есть некоторые специальные значения: это нуль и NaN/Inf. Нуль всегда должен быть полностью точным, а NaN/Inf не могут иметь ни одного точного бита.
Предположим, мы складываем два двоичных числа с некоторыми заданными белыми, серыми и черными битами. Тогда черные биты результата возникают при сложении черных битов любого из слагаемых и при выравнивании слева от результата. Оценку для серых битов можно получить как сумму погрешностей аргументов. Обратите внимание, что оценка точности для суммы многих чисел может отличаться от оценки, если бы они складывались по одному, из-за возможного округления «вверх» для серых битов.
Оценка точности умножения может быть легко выведена из оценки точности сложения. Например, возьмём число 6 с одним белым, одним серым и одним чёрным битом. Подсчитаем точные биты его квадрата. Во втором примере мы видим, как при начальной полной информации о точности может получиться «серый» бит, который не является полностью бессмысленным, но и не является достоверным.
Мы видим, что серые биты могут передавать свой цвет старшим битам при переносах между разрядами, а черные — нет. Черные биты могут сделать старшие биты серыми при переносах. Если мы перемножим два бита, то цвет результата будет более тёмным из цветов аргументов.
Заключение
За ошибочными прогнозами и разного рода странностями искусственного интеллекта часто стоят проблемы точности вычислений. Современные разработчики либо не знают о них, либо игнорируют, либо пытаются бороться с ними слишком грубыми способами. Однако никакие ухищрения не заменят чисто математических методов повышения численной стабильности алгоритмов. Об этом следует вспомнить как о забытом искусстве, для возрождения которого теперь есть открытая библиотека XNumPy. Она базируется на NumPy и дополняет её классами для работы с числами в формате float point, автоматически оценивающих точность каждого результата по мере вычислений. Использование библиотеки аналогично NumPy, однако на выходе заведомо неточные знаки заменятся вопросительными. Это позволяет оценить точность результата и отбрасывать заведомо бессмысленные, в частности — не пытаться интерпретировать сильно зашумлённый логический вывод нейросети.
