О точности вычислений: как не потерять данные в цифровом шуме
«По мере того, как сложность возрастает,
точные утверждения теряют значимость,
а значимые утверждения теряют точность»,
—
математик Лотфи Заде
Специалист отдела перспективных исследований компании «Криптонит» Игорь Нетай изучил процесс потери точности вычислений и написал библиотеку, доступную на GitHub, которая помогает разработчикам контролировать точность расчётов на каждом этапе вычислений. Данная библиотека особенно актуальна в сфере машинного обучения и анализа (больших) данных, где накопление ошибок может сильно искажать результат.
Пример подсветки неточных знаков при использовании библиотеки XNumPy
Мы привыкли доверять машинным расчётам, а в случае их несоответствия реальности — разводить руками со словами «компьютер так посчитал». В чём же причина ошибок, если железо работает исправно, а в софте нет багов, влияющих на вычисления?
Если вам не чужды математика и программирование, то вы, возможно, знаете о проблемах представления вещественных чисел значениями типа float. Даже когда мы используем длинный вариант float64 (FP64), всё равно математические действия с ним оказываются неточными, это не зависит от длины представления числа. Более того, элементарные операции сложения и умножения могут становиться неассоциативными, то есть — приводить к разному результату в зависимости от порядка слагаемых или множителей:
a + (b + c) ≠ (a + b) + c
a · (b · c) ≠ (a · b) · c
Вычитание близких чисел — это ещё одно действие, при котором точность неминуемо теряется, и порой — очень сильно. Если у нас было два точных числа FP64 (точны все 53 бита мантиссы), но числа совпадали в первых 30 битах, то у результата будет не более 23 точных битов мантиссы.
Таким образом, если в анализируемой выборке будет хотя бы одна пара очень близких чисел, то результат вычислений будет заведомо неточным, а вывод может стать недостоверным. Почему «может»? Степень влияния ошибки зависит от алгоритма. Если мы вычитаем, возводим в квадрат и опять суммируем, то потеря точности сгладится, потому что все неточные числа будут маленькими, а более точные окажутся больше.
Однако возможна и другая ситуация. Например, если мы выполняем численное дифференцирование и идём малыми приращениями, либо численно решаем уравнение в частных производных, то таких ошибок становится много. Они накапливаются и сильно искажают результат.
Кроме того, результаты вычислений могут измениться в зависимости от целого ряда факторов:
· используемый набор процессорных векторных инструкций (SSE, AVX);
· версии системных библиотек типа glibc (даже тангенс 60° может принимать разные значения на машинах с Ubuntu 20.04 и Ubuntu 22.04 из-за разных версий этой библиотеки, хотя математически это просто sqrt{3});
· особенности реализации многопоточности в ОС, так как не во всех реализациях детерминирован порядок операций с числами при параллельной обработке данных;
· в разных версиях CUDA и OpenCL даже обеспечение воспроизводимости результатов одного вычисления на графическом процессоре часто представляет сложность;
· в кластере на перечисленные выше проблемы могут наложиться всяческие сетевые эффекты (по аналогии с реализацией многопоточности).
Большим данным — большие ошибки
При обработке больших данных (а также многих статистических расчётах, дающих уровни значимости и значения корреляций), даже с использованием тщательно выверенных библиотек могут вкрасться ошибки вычислений. Например, при использовании метода главных компонент промежуточно вычисляемые собственные значения и векторы разрывно зависят от начальных данных. На плохо обусловленных матрицах вычисление приводит к вычитанию близких неточно определённых собственных чисел. За счёт этого собственные векторы имеют очень низкую точность. Тогда точность дальнейших вычислений легко может быть потеряна, а результатам не имеет смысла доверять.
Появление таких ошибок — не баг, а фича: они появляются по естественным математическим причинам и следуют из природы приближённых вычислений (то есть любых вычислений с плавающей точкой).
Есть хороший пример. Если вы вычислите arcsin (pi/2), вы получите »?.???». Казалось бы, почему? Ведь это табличная константа! Но полученное в вычислении значение (а ведь библиотечное pi само по себе имеет конечную точность представления) имеет погрешность. Численные методы (см. Бахвалова) учат нас, что в точках с большой производной ошибка будет умножаться на большой коэффициент. Поэтому математически верное утверждение при численном расчёте может давать неточный результат.
Замена на точный ответ, который вы знаете, может повысить точность. Если вы получили незначимый результат, ищите другой путь вычисления.
Когда нейросети сходят с ума
Другой пример, приводящий к накоплению ошибок — сложение большого числа и множества маленьких. Вопреки выученному нами в школе, здесь от перестановки слагаемых сумма очень даже меняется (повторюсь, сложение перестаёт быть ассоциативным). Например, если мы станем суммировать гармонический ряд, то результат будет зависеть от того, с какой стороны мы пойдём. Для суммирования массивов даже есть специальный алгоритм Кэхэна, позволяющий делать суммирование «точно» (максимально в пределах достижимой точности для данной разрядности чисел). Но для всех возможных сценариев численных вычислений таких алгоритмов не напасёшься.
На практике сложение больших чисел с маленькими встречается чаще, чем кажется. Например, это градиентный спуск при обучении нейросетей. Проблема в том, что там мы не можем поменять порядок сложений, потому что следующая эпоха делается на основе предыдущего влияния градиентов. Это типичный итерационный процесс.
Кстати, в научных расчётах есть множество других итерационных алгоритмов. Например, моделирование 3D-структуры химического соединения методом молекулярных орбиталей, или скоринг — сопоставление определённому положению лиганда точного числа для расчёта взаимодействий между лигандом, белками и нуклеиновыми кислотами. Эти методы широко применяются при изучении биохимических реакций и разработке лекарств. Накопление ошибки точности — одна из причин, почему в клинических испытаниях порой всё происходит совсем не так, как в цифровой модели.
Влияние накопления ошибок на поведение нейросетей представляет отдельный интерес. Ранее автор изучил этот вопрос и получил ряд интересных результатов. Главный из них можно сформулировать так: По мере обучения и работы нейросетей, в них постепенно нарастает шум. Если не контролировать число точно вычисленных знаков на промежуточных этапах, то мы не отследим тот момент, когда уровень шума неизбежно превысит критический, и он сделает логический вывод нейросети (inference) бесполезным.
Процесс потери точности вычислений происходит во всех нейросетях. Разработчики выполняют ряд тестов, показывают впечатляющие метрики и выпускают нейросетевой продукт на рынок, после чего он начинает жить своей жизнью, доставляя всё больше неприятны сюрпризов. Ошибки навигации, приводящие к столкновению беспилотников, ложноположительные результаты распознавания лиц, ложные оповещения умных часов об аритмии, блокировка легитимных операций «умным» алгоритмом банка… всё это может быть следствием постепенной потери точности вычислений. Ещё хуже, когда ошибки игнорируются разработчиками по незнанию и эксплуатируются злоумышленниками.
Разработчикам было бы проще избегать всяких инцидентов, если бы такие численные ошибки где-то отображались. Например, если бы в логах записывалось предупреждение о том, что инференс на нейросети в конкретном случае не имеет смысла. Тогда для разрешения инцидента достаточно было бы прочитать логи и убедиться, что и в самом деле, срабатывание ложное. Ещё лучше научиться контролировать это заранее и не делать заведомо искажённый вывод, который с большой вероятностью доставит кому-то проблемы. Увы, такие численные ошибки обычно не контролируются.
На пути к решению
Осмелимся сказать, что до настоящего момента эта широко известная проблема не получала должного внимания. Множество разработчиков предпринимали шаги для косвенного снижения уровня шумов тех же нейросетей, но никто (насколько известно автору) не решал эту проблему алгебраически. Безусловно, в документации к ряду библиотек (например, в том же pytorch) упоминается, что некоторые алгоритмы имеют разную численную устойчивость, но это обычно качественные утверждения. В них просто декларируется, что что-то «более численно устойчиво». При этом не указывается способ это проверить и получить хотя бы какую-то информацию о том, как «сыграла» более устойчивая схема в реализации алгоритма.
Стремясь заполнить этот пробел, Игорь Нетай написал свободно распространяемую библиотеку XNumPy. Она базируется на популярной библиотеке NumPy и дополняет её классами для работы с числами типа float, автоматически по мере вычислений делающих оценки точности. Это первая в своём роде разработка, позволяющая выполнять вычисления с подсчётом числа точных битов на каждом этапе.
Вы можете спросить, а чем плоха давно существующая библиотека boost/intervals под C++? (Для читателей, не знакомых с этой библиотекой, поясним: она работает с интервалами значений вместо одиночных чисел и делает округления так, чтобы результирующий интервал охватывал все возможные результаты для аргументов-чисел из соответствующих интервалов). Отвечу: хотя бы тем, что библиотека boost/intervals не даёт информации о точности проведённых вычислений, а XNumPy — даёт. С помощью последней вы получите наглядное представление о том, в каком знаке произошла потеря точности: значения в нём и во всех последующих разрядах будут заменены при печати знаками вопроса. Кроме того, если ваше вычисление было сделано на Numpy, вы получите не совершенно другое вычисление, а просто дополните своё оценкой точности, получив те же числа. При этом переписать вычисления с массивами на Python в стиле NumPy большинству проще, чем на C++ в intervals, а производительность в ряде случаев даже повысится.
В качестве одного из примеров, выложенных на странице проекта XNumPy в GitHub, рассмотрим решение квадратного уравнения двумя способами: по формуле и чуть похитрее — через максимальный по модулю корень и теорему Виета. В обоих случаях при выводе значений пользователь получит некоторые числа, но в первом случае на месте меньшего корня он увидит что-то вроде »?.???» вместо числа и поймёт, что этому значению нельзя доверять. В самом деле, в этом решении даже старший бит мантиссы ошибочен!
Во втором случае пользователь увидит числа со многими значимыми цифрами. Это уже валидный до некоторой известной (!) степени результат. Если же использовать стандартную библиотеку NumPy, то в выводе не получится увидеть цифрового мусора. С ней можно и не догадываться, что какому-то промежуточному значению верить нельзя, и продолжать использовать его в вычислениях.
Естественно, библиотека XNumPy не даёт полного ответа о точности. Его нельзя получить, не сделав все вычисления до требуемой точности. В библиотеке XnumPy происходит оценка точности «сверху», и библиотека может гарантировать: если что-то она помечает как неточное, вы можете быть уверены, что этому нельзя верить. Её оценки обоснованы математически и не зависят от того, на какой платформе вы считаете. В отличие от железа и людей, математика сбоев не даёт!
Истина где-то там
Мы надеемся, что смогли вас убедить, что результатам вычислений можно доверять только до некоторой степени, а воспроизводимость результатов в том же или другом окружении всегда остаётся сложным вопросом.
Откуда можно узнать, каким вычислениям, с каким софтом и железом можно верить, а каким нет? Верить нельзя никому, даже себе! Нам — можно. :-)
XNumPy не пытается решить проблему воспроизводимости результатов в разных окружениях. Наоборот, вы сохраните те же значения, на которые опираетесь, и вам ничего не придётся менять в выводах по результатам вычислений. Просто с ней появится возможность избежать слишком неточных расчётов и заведомо бессмысленных выводов.
Технические подробности данного исследования и разработки будут представлены в докладе на 20-й конференции HighLoad++, которая пройдёт 27 и 28 ноября в Москве.
