[Из песочницы] Тестирование математических алгоритмов
Эта статья написана для людей, прямо или косвенно связанных с промышленной разработкой математических алгоритмов для бизнеса, а также для профессиональных тестировщиков, от которых мы хотим услышать критику.
Кто мыМы работаем в российской компании, которая более 10 лет занимается разработкой уникальных программных решений в области анализа данных, прогнозирования, классификации и других областей датамайнинга. Все решения — не абстрактные инструменты, а интегрированные системы для решения конкретных задач заказчиков. Наша ключевая особенность — алгоритмы собственной разработки, заточенные под высокое качество результата.В нашей компании есть чёткое разделение обязанностей между математиками и программистами. Для наглядной расстановки акцентов добавлю, что команда математиков почти не уступает по размеру команде программистов.
О какой проблеме пойдёт речь
Упрощённо, процесс создания нового решения выглядит так: После проверки идеи, наши математики разрабатывают полноценную аналитическую систему и реализуют в ней все процессы заказчика. На этой системе как правило происходит демонстрация работы наших алгоритмов в условиях, приближенных к боевым. Наши математики предпочитают работать на Matlab, поэтому их система очень удобна для быстрой проверки гипотез, но по многим причинам не может использоваться в промышленных целях. Нужно заново реализовывать тоже самое в подходящей среде разработки, например, .NET (в нашем случае). Этот момент — слабое звено процесса.Разработчик промышленного софта имеет перед собой документацию и исходники на Matlab, но не обладает образованием и опытом математика. Однако из-под его пера должен выйти точно такой же алгоритм. Здесь возникает задача: как правильно тестировать промышленную версию алгоритма на соответствие прототипу математика?
В чём сложность этой задачи? Нужно заметить, что поймать ошибку в математическом алгоритме и, например, в процессе синхронизации двух СУБД — две принципиально разные задачи. С базами данных всё более понятно: количество записей после синхронизации совпадает, контрольные суммы совпадают, значит тест пройдён. Легко понять и сравнительно легко автоматизировать.Алгоритм прогнозирования принимает на вход и выдаёт на выход десятки или сотни величин — чисел с плавающей точкой. Один алгоритм выводит эти числа на экран в Матлабе, другой, промышленный, записывает в переменную в C#-коде. Как их сравнить? Из-за ограниченной точности вычислений с плавающей точкой, совпадать до последнего знака они не будут. Чем ограничить точность сравнения? В наших условиях падение качества прогнозирования на 2–3% может быть существенно, т.к. иногда это сравнимо с эффектом, который мы даём бизнесу.
Как мы решаем проблему Процедура тестирования, к которой пришли мы, выглядит так: Генерация входных наборов данных — так называемых эталонов. Эту работу заранее делает математик в привычной среде — Matlab. Запуск системы тестирования, поглощающей эталоны и превращающей их в тесты. Эта система разработана нами на Matlab, по эталону она понимает какой алгоритм нужно запустить, в каком порядке передавать в него данные и чего ожидать на выход. Запуск прототипа на Matlab с эталонами в качестве входных данных. Эта процедура выполяется легко, т.к. и эталоны, и прототип созданы в рамках одной системы — Matlab. Запуск промышленной .NET-версии, с конвертацией входные и выходные данных из Матлаба в C# и обратно. Перепробовав несколько подходов, для построения такого моста, мы остановились на C#-интерфейсе, реализованном из коробки в последних версиях Матлаб. Он позволяет инстанциировать из Matlab практически любые типы C#-данных, загружать сборки, запускать функции. Система получает результаты работы обоих алгоритмов и запускает процедуру сравнения. Процедура сравнения выдаёт вердикт: 0 (не совпадает) или 1 (совпадает). Процедуру сравнения требуется разрабатывать вручную под каждый алгоритм, т.к. особенности округления конкретных величин дают разные допуски по значениям. Кроме того, некоторые алгоритмы включают в себя генерацию случайных величин. Шаги 2–7 автоматизируются посредством консольного запуска Matlab и запускаются по расписанию. С учётом необходимости разработки C#-Matlab интерфейса, функции сравнения, а также отладки двух систем, на сведение среднего алгоритма уходит 5–10 дней, что по трудозатратам сравнимо со временем, затрачиваемым на разработку. Это время отражает разницу между алгоритмом, который «в принципе работает и выдаёт что-то нормальное» и алгоритмом, который полностью повторяет задуманное математиком.Ещё раз, списком, сложности, с которыми мы сталкиваемся:
Входные данные нужно подавать в Matlab и в C# => нужно разрабатывать конвертации туда и обратно. Сравнение и связанные с ним проблемы округления и другие особенности — мешают писать код и вводят в заблуждение при отдадке. Синхронная отладка: чтобы понять, что не так, часто нужно синхронно запускать два отладчика под двумя системами, это работает, но требует определённого шаманства. Генерация исчерпывающего набора эталонов (задача математика). Всевозможные входы перебрать не получится, и веток в алгоритме может быть слишком много для их совместной проверки во всех комбинациях. Под каждый алгоритм необходима собственная вручную разработанная функция сравнения результатов. Особенности кодирования Разрабатывая промышленный код на C#, мы сразу думаем о том, что его придётся «сводить» с Matlab. Чтобы облегчить себе жизнь, мы используем ряд простых приёмов.Важно уделить внимание операциям сравнения. Сравнивать на равенство числа с плавающей точкой нельзя (об этом подскажет решарпер). Вместо
a == b используется Math.Abs (a — b) < eps Менее очевидно, но явно проявляется в математических алгоритмах, что сравнения <= >= < > нелегальны по той же причине: if (a <= b) => if (a < b + eps) if(a < b) => if (a < b - eps) Также важно вникнуть в детали обработки с псевдовеличинами, такими как NaN (not a number) и Infinity. Например, в Матлабе: max(0, NaN) = 0 а в C# Math.Max(0, double.NaN) = NaN Другие пути Возможные пути облегчения жизни, которыми мы не пошли или идём, но путь пока не пройден:Разработка и прототипа и продакшн версии одним человеком. Эта комбинация сильно упрощает жизнь, т.к. снимает задачу понимания этими людьми друг друга. В случаях, когда результат нужен незамедлительно, другого пути вообще нет. Но и людей, способных на такую разноплановую работу, практически не встречается. Ещё меньше людей, которые хотят ей заниматься.Нормального математика воротит от ограничений и принципов промышленной разработки, а обычный программист – это инженер, отнюдь не математик (да, мы – не яндекс). Юнит-тестирование продакшн версии (математиком или промышленным разработчиком). Вместо затратной процедуры совместного тестирования Матлаба и C# тестировать только C# на цифрах, которые выгружены из Matlab. В этом случае всё тестирование можно сделать с помощью удобных фреймворков полностью на C#.Кажется, что это должно сэкономить кучу сил, но мы теряем главное: одновременное сравнение двух алгоритмов. Если в версию на Matlab будут внесены изменения, мы можем не узнать об этом своевременно или не осознать, насколько эти изменения важны (сколько тестов они порушили). Билдить .NET сборки прямо из Matlab. К сожалению, нормальных (по производительноси и по надёжности) фреймворков для этого нет, и скорее всего никогда не будет. Матлаб – мощнейший инструмент, но создавался для других целей. Разработать на C# фреймворк, который позволит писать код в матлаб-стиле, с привычной обработкой матриц, индексов, условий и др. Такие разработки существуют: numerics.mathdotnet.com, ilnumerics.net, но несовершенны, и мы постепенно делаем свою. В итоге Вступая на этот путь, мы не ожидали, что верификация наших алгоритмов выльется в нетривиальный многоходовый процесс. В целом, нас устраивает качество и повторяемость результата, и нам интересно услышать мнение людей, столкнувшихся с похожими задачами.
