В статье пойдет речь об удобном инструменте, который я и мои коллеги часто используем в своей практике. Инструмент этот называется NOMAD. Этот пакет предназначен для оптимизации функционалов разной сложности, главным образом — трудно вычислимых, функционалов с недоступным по каким-то причинам градиентом, зашумленных и т.д.
Оптимизируемый (минимизируемый) функционал рассматривается как «черный ящик», за его вычисление отвечает отдельно имплементированный скрипт или программа (при работе в batch-mode) или специально реализованный С++-класс (при работе в library-mode). Оптимизация ведется при помощи алгоритма MADS
Исходники поставляются под лицензией LGPL, доступны версии для Unix, Linux, Mac OS X и Windows, для скачивания не требуется регистрация, но нужно заполнить небольшую форму (имя, организация, город, страна).
NOMAD: A blackbox optimization software
Зачем это нужно
Базовый сценарий таков. Вы разрабатываете вундервафлю, которая делает свой посильный вклад во имя всеобщего блага. В процессе работы используются крутые супер-современные методы и алгоритмы, настраиваемые через числовые параметры, которые вынесены у вас в конфиги (если просто не светятся в коде в виде магических цифр). У системы есть некоторый показатель качества, вычисляемый неизвестно как, и сейчас он находится на отметке 98 %, а вам неймется достигнуть 99.5 %. Хочется инструмент, которому можно было бы выдать «крутилки», и пойти попить чайку, в то время, как он поднимет качество системы чуть-чуть повыше. Неплохим инструментом для решения такого класса задач является NOMAD.
Частный случай. Для решения одной и той же задачи вы используете два разных алгоритма. Задача подразумевает некоторую классификацию или оценку входного объекта (пример — распознавание), на выходе вы получаете вектор значений оценок (пример — выходной вектор альтернатив у нейронной сети). На одном типе исходных данных лучше работает первый алгоритм, на другом — второй алгоритм, а четко разграничить типы входных данных вы по каким-то причинам не можете. Возможным выходом из положения является использование обоих алгоритмов, и «усреднение» результатов а-постериори. Вопрос только в том, с какими коэффициентами (весами) проводить усреднение результатов. Для определения оптимальных коэффициентов усреднения можно использовать NOMAD, если назначить функционалом, скажем, суммарное количество ошибок или некоторый суммарный штраф на заданной выборке входных данных.
Как этим пользоваться
Рассмотрим несложный пример использования NOMAD в режиме batch mode. Задача такая: вы хотить построить простую функцию, разбивающую объекты из множества X на два класса: A и B. Проведя небольшое статистическое исследование, вы обнаружили, что существуют признаки f1, f2 и f3, свидетельствующие о принадлежности объекта x какому-то классу. f1, f2 и f3 — функции от объекта, значением которых является действительное число. Классифицирующую функцию будем искать в виде C(x) = a1*f1(x) + a2*f2(x) + a3*f3(x) + b, где a1, a2, a3 — действительные числа, а b — целое от -1 до 1. Если C(x) >= 0, то будем говорить, что x принадлежит A, иначе x принадлежит B. Загвоздка в том, что если мы ошиблись и определили объект x к множеству B, хотя он на самом деле из A, то это конечно неприятно, но не смертельно, а вот если мы определили x в A, а должны были в B, то это в 100 раз хуже.
Есть несколько остроумных способов решить эту задачу, мы же, для примера, построим оценочный функционал и найдем коэффициенты при помощи NOMAD.
Пусть есть обучающая база, содержащая такие данные: истинный класс (куда мы должны определить
x) и значения признаков f1(x), f2(x), f3(x). База представляет собой такой текстовый файл: (скажем, base.data)
A 1.0 3.0 4.5555
B 2.3 2.3 0.0
B 2.4 2.5 9.0
...
Функционал определяем таким образом: просматриваем базу, если произошла ошибка — то приибавляем к значению функционала стоимость этой ошибки. Стоимость ошибки «надо А, а мы сказали В» равна единице, стоимость ошибки «надо В, а мы сказали А» равна 100.
Пишем простую программку, принимающую в качестве единственного аргумента среды файл с коэффициентами a1, a2, a3, b и выводящую в стандартный поток вывода значение функционала.
#!/usr/bin/python
# файл evaluator.py
import sys
# вычисляет значение классифицирующей функции
def C(f, a):
return a[3] + sum([x * y for x, y in zip(f, a[:3])])
# вычисляет штраф для одного объекта
def penalty(correct, f, a):
answer = 'A' if C(f, a) >= 0.0 else 'B'
# если все верно - штраф нулевой
if answer == correct:
return 0.0
# надо было А, мы сказали В
elif correct == 'A':
return 1.0
# надо было В, мы сказали А
else:
return 100.0
if __name__ == '__main__':
F = 0.0
# считываем коэффициенты из sys.argv[1]
a = list(map(float, list(open(sys.argv[1], 'r'))[0].split()))
# вычисляем функционал по обучающей базе
with open('base.data', 'r') as base:
for line in base:
line = line.strip().split()
correct = line[0]
f = map(float, line[1:])
F += penalty(correct, f, a)
# выводим значение функционала
print(F)
Следующий шаг — конфигурационный файл NOMAD: (скажем, params.nomad)
# количество аргументов функционала
DIMENSION 4
# команда, запускающая блакбокс и
# вычисляющая значение функционала
BB_EXE "$python evaluator.py"
# формат ввода блакбокса:
# три вещественных числа и одно целое
BB_INPUT_TYPE ( R R R I )
# формат вывода блакбокса:
# только значение функционала (OBJ)
# может содержать также функции-условия
# (для задач условной оптимизации)
BB_OUTPUT_TYPE OBJ
# начальное приближение
X0 ( 0 0 0 0 )
# границы изменения параметров
LOWER_BOUND ( -10 -10 -10 -1 )
UPPER_BOUND ( 10 10 10 1 )
# максимальное количество запуска блакбокса
MAX_BB_EVAL 1000
# временная директория
TMP_DIR /tmp
Запускаем NOMAD:
kbulatov@node ~> ./NOMAD.3.6.0/bin/nomad params.nomad
NOMAD - version 3.6.0 - www.gerad.ca/nomad
Copyright (C) 2001-2013 {
Mark A. Abramson - The Boeing Company
Charles Audet - Ecole Polytechnique de Montreal
Gilles Couture - Ecole Polytechnique de Montreal
John E. Dennis, Jr. - Rice University
Sebastien Le Digabel - Ecole Polytechnique de Montreal
Christophe Tribes - Ecole Polytechnique de Montreal
}
Funded in part by AFOSR and Exxon Mobil.
License : '$NOMAD_HOME/src/lgpl.txt'
User guide: '$NOMAD_HOME/doc/user_guide.pdf'
Examples : '$NOMAD_HOME/examples'
Tools : '$NOMAD_HOME/tools'
Please report bugs to nomad@gerad.ca
MADS run {
BBE OBJ
1 41100.0000000000
5 27814.0000000000
12 22459.0000000000
14 5070.0000000000
36 4853.0000000000
44 4828.0000000000
49 4720.0000000000
58 4657.0000000000
78 4583.0000000000
93 4514.0000000000
106 4509.0000000000
115 4495.0000000000
117 4494.0000000000
118 4484.0000000000
119 4453.0000000000
133 4379.0000000000
145 4376.0000000000
153 4217.0000000000
156 4158.0000000000
177 4034.0000000000
181 3982.0000000000
184 3942.0000000000
216 3918.0000000000
237 3905.0000000000
262 3903.0000000000
458 3903.0000000000
} end of run (mesh size reached NOMAD precision)
blackbox evaluations : 458
best feasible solution : ( 1.300140381 0.6046962738 -0.9088993073 -1 ) h=0 f=3903
В последней строчке — искомые коэффициенты.
Дополнительные возможности
В конфигурационном файле есть возможность указать огромное количество дополнительных параметров алгоритма оптимизации, в данном обзоре описаны лишь основные.
Есть также возможность использовать NOMAD как статическую С++-библиотеку (режим library mode). В этом случае нужно написать класс, вычисляющий функционал, что то вроде:
class MyEvaluator: public NOMAD::Evaluator {
public:
MyEvaluator(NOMAD::Parameters const& p)
: NOMAD::Evaluator(p) {}
~MyEvaluator() {}
bool eval_x(NOMAD::Eval_Point& x,
NOMAD::Double const& h_max,
bool& count_eval) const {
/// вычисление функционала
/// возвращаем false, если что-то пошло не так
...
count_eval = true;
return true;
}
}
Послесловие
Пример получился слегка натянутым, для более эффективного поиска нужно было конечно использовать режим library mode. Кроме того, функционал в данном случае представляет собой сумму масштабированных сигнальных функций, можно было существенно облегчить работу алгоритму, если аппроксимировать эти сигнальные функции какими-нибудь сигмоидами. Функционал, по крайней мере, получился бы непрерывным. Но цель — проиллюстрировать — достигнута.
Буду рад услышать про другие инструменты, позволяющие выполнять что-то подобное, если кому-то таковые известны и есть опыт успешного применения.
Автор: kbulatov
