NOMAD: Оптимизация «черных ящиков» в домашних условиях

в 12:21, , рубрики: Алгоритмы, оптимизация, Песочница, Программное обеспечение, разработка, Софт, метки: , ,

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

Оптимизируемый (минимизируемый) функционал рассматривается как «черный ящик», за его вычисление отвечает отдельно имплементированный скрипт или программа (при работе в batch-mode) или специально реализованный С++-класс (при работе в library-mode). Оптимизация ведется при помощи алгоритма MADS

Исходники поставляются под лицензией LGPL, доступны версии для Unix, Linux, Mac OS X и Windows, для скачивания не требуется регистрация, но нужно заполнить небольшую форму (имя, организация, город, страна).

NOMAD: A blackbox optimization software
image

Зачем это нужно

Базовый сценарий таков. Вы разрабатываете вундервафлю, которая делает свой посильный вклад во имя всеобщего блага. В процессе работы используются крутые супер-современные методы и алгоритмы, настраиваемые через числовые параметры, которые вынесены у вас в конфиги (если просто не светятся в коде в виде магических цифр). У системы есть некоторый показатель качества, вычисляемый неизвестно как, и сейчас он находится на отметке 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

Источник

Поделиться

* - обязательные к заполнению поля