Выбор алгоритма

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

Определение

Учитывая портфолио ${\mathcal {P}}$ алгоритмов ${\mathcal {A}}\in {\mathcal {P}}$, набор экземпляров $i\in {\mathcal {I}}$ и показатель стоимости $m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R}$, задача выбора алгоритма состоит в нахождении отображения $s:{\mathcal {I}}\to {\mathcal {P}}$ из экземпляров ${\mathcal {I}}$ к алгоритмам ${\mathcal {P}}$ такой, что стоимость $\sum _{i\in {\mathcal {I}}}m(s(i),i)$ во всех экземплярах оптимизировано.

Примеры

Проблема булевой выполнимости (и другие сложные комбинаторные проблемы)

Хорошо известным применением выбора алгоритма является проблема булевой выполнимости . Здесь портфель алгоритмов представляет собой набор (дополнительных) решателей SAT , экземпляры — это логические формулы, показатель стоимости — это, например, среднее время выполнения или количество нерешенных экземпляров. Итак, цель состоит в том, чтобы выбрать хорошо работающий решатель SAT для каждого отдельного экземпляра. Таким же образом выбор алгоритма можно применить и ко многим другим ${\mathcal {NP}}$-сложные задачи (такие как смешанное целочисленное программирование , CSP , планирование AI , TSP , MAXSAT , QBF и программирование набора ответов ). Системы-победители конкурса SAT: SATzilla, 3С и CSHC

Машинное обучение

В машинном обучении выбор алгоритма более известен как метаобучение . Портфель алгоритмов состоит из алгоритмов машинного обучения (например, случайный лес, SVM, DNN), экземплярами являются наборы данных, а метрикой стоимости является, например, частота ошибок. Итак, цель состоит в том, чтобы предсказать, какой алгоритм машинного обучения будет иметь небольшую ошибку в каждом наборе данных.

Возможности экземпляра

Проблема выбора алгоритма в основном решается с помощью методов машинного обучения. Представляя экземпляры проблемы числовыми признаками $f$Выбор алгоритма можно рассматривать как задачу многоклассовой классификации , изучая отображение $f_{i}\mapsto {\mathcal {A}}$ для данного экземпляра $i$.

Объекты экземпляра — это числовые представления экземпляров. Например, мы можем подсчитать количество переменных, предложений, среднюю длину предложений для булевых формул, или количество образцов, функций, баланс классов для наборов данных ML, чтобы получить представление об их характеристиках.

Статические и зондирующие функции

Мы различаем два типа характеристик:

1. Статические функции в большинстве случаев представляют собой некоторые подсчеты и статистику (например, соотношение предложений и переменных в SAT). Эти функции варьируются от очень дешевых функций (например, количества переменных) до очень сложных функций (например, статистики графов переменных).
2. Зондирующие признаки (иногда также называемые признаками ориентиров) вычисляются путем проведения некоторого анализа поведения алгоритма на экземпляре (например, точности дешевого алгоритма дерева решений на наборе данных ML или запуска в течение короткого времени решателя стохастического локального поиска на наборе данных). Булева формула). Эти функции часто стоят дороже, чем простые статические функции.

Стоимость функций

В зависимости от используемой метрики производительности $m$, вычисление признаков может быть связано с затратами. Например, если мы используем время работы в качестве показателя производительности, мы включаем время на вычисление функций нашего экземпляра в производительность системы выбора алгоритма. Решение SAT является конкретным примером, когда такими затратами функций нельзя пренебрегать, поскольку экземпляры функций для формул CNF могут быть либо очень дешевыми (например, получение количества переменных может быть выполнено за постоянное время для CNF в формате DIMAC), либо очень дешевыми. дорогостоящие (например, графические функции, стоимость которых может составлять десятки или сотни секунд).

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

Подходы

Регрессионный подход

Один из первых успешных подходов к выбору алгоритмов предсказал производительность каждого алгоритма. ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ и выбрали алгоритм с наилучшей прогнозируемой производительностью $arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)$ для примера $i$.

Кластерный подход

Распространенным предположением является то, что данный набор экземпляров ${\mathcal {I}}$ могут быть сгруппированы в однородные подмножества и для каждого из этих подмножеств существует один хорошо работающий алгоритм для всех экземпляров. Итак, обучение состоит из выявления однородных кластеров с помощью подхода неконтролируемой кластеризации и связывания алгоритма с каждым кластером. Кластеру назначается новый экземпляр и выбирается соответствующий алгоритм.

Более современный подход — экономичная иерархическая кластеризация. использование контролируемого обучения для выявления однородных подмножеств экземпляров.

Парный подход к классификации с учетом затрат

Общий подход к многоклассовой классификации заключается в изучении парных моделей между каждой парой классов (здесь алгоритмы). и выберите класс, который чаще всего предсказывали парные модели. Мы можем взвесить экземпляры задачи парного прогнозирования по разнице в производительности между двумя алгоритмами. Это мотивировано тем, что мы больше всего заботимся о том, чтобы прогнозы с большими различиями были правильными, но штраф за неправильный прогноз невелик, если разницы в производительности почти нет. Поэтому каждый экземпляр $i$ для обучения модели классификации ${\mathcal {A}}_{1}$ против ${\mathcal {A}}_{2}$ связано с затратами $|m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|$.

Требования

Кластеризация решателей SAT из сценария SAT12-INDU ASlib согласно коэффициенту корреляции Спирмена.

Значения Шепли для дополнительного анализа в сценарии SAT12-INDU ASlib

Задача выбора алгоритма может эффективно применяться при следующих предположениях:

• Портфолио ${\mathcal {P}}$ алгоритмов является дополнительным по отношению к множеству экземпляров ${\mathcal {I}}$, т. е. не существует единого алгоритма ${\mathcal {A}}\in {\mathcal {P}}$ который доминирует по производительности всех других алгоритмов над ${\mathcal {I}}$ (примеры дополнительного анализа см. на рисунках справа).
• В некоторых приложениях вычисление функций экземпляра связано с затратами. Например, если метрикой стоимости является время работы, нам также необходимо учитывать время на вычисление функций экземпляра. В таких случаях затраты на вычисление функций не должны превышать прирост производительности за счет выбора алгоритма.

Домены приложений

Выбор алгоритма не ограничивается отдельными областями, но может быть применен к любому типу алгоритма, если вышеуказанные требования удовлетворены. Домены приложений включают в себя:

• сложные комбинаторные задачи: SAT , смешанное целочисленное программирование , CSP , планирование AI , TSP , MAXSAT , QBF и программирование набора ответов
• комбинаторные аукционы
• в машинном обучении эта проблема известна как метаобучение
• дизайн программного обеспечения
• оптимизация черного ящика
• многоагентные системы
• численная оптимизация
• линейная алгебра, дифференциальные уравнения
• эволюционные алгоритмы
• проблема с маршрутом транспортного средства
• энергетические системы

Обширный список литературы по выбору алгоритмов можно найти в обзоре литературы.

Варианты выбора алгоритма

Онлайн подбор

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

Расчет графиков

Расширением выбора алгоритма является задача планирования алгоритма для каждого экземпляра, в которой мы не выбираем только один решатель, а выбираем бюджет времени для каждого алгоритма на основе каждого экземпляра. Этот подход повышает производительность систем выбора, особенно если признаки экземпляра не очень информативны и вероятен неправильный выбор одного решателя.

Выбор параллельных портфелей

Учитывая растущую важность параллельных вычислений, расширением выбора алгоритма для параллельных вычислений является выбор параллельного портфеля, в котором мы выбираем подмножество алгоритмов для одновременного запуска в параллельном портфеле.

Внешние ссылки

• Библиотека выбора алгоритмов (ASlib)
• Литература по выбору алгоритмов