Výběr algoritmu - Algorithm selection

Výběr algoritmu (někdy také nazývaný výběr algoritmu na instanci nebo výběr offline algoritmu ) je meta- algoritmická technika pro výběr algoritmu z portfolia na základě instance. Je to motivováno pozorováním, že na mnoha praktických problémech mají různé algoritmy různé výkonnostní charakteristiky. To znamená, že zatímco jeden algoritmus funguje v některých scénářích dobře, v jiných funguje špatně a naopak pro jiný algoritmus. Pokud dokážeme určit, kdy použít který algoritmus, můžeme optimalizovat pro každý scénář a zlepšit celkový výkon. K tomu slouží výběr algoritmu. Jediným předpokladem pro použití technik výběru algoritmů je, že existuje (nebo že může být konstruována) sada komplementárních algoritmů.

Definice

Vzhledem k portfoliu algoritmů , sadě instancí a nákladové metrice problém výběru algoritmu spočívá v nalezení mapování od instancí k algoritmům tak, aby byly optimalizovány náklady ve všech instancích. ${\ displaystyle {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {A}} \ in {\ mathcal {P}}}$ ${\ displaystyle i \ in {\ mathcal {I}}}$ ${\ displaystyle m: {\ mathcal {P}} \ times {\ mathcal {I}} \ to \ mathbb {R}}$ ${\ displaystyle s: {\ mathcal {I}} \ to {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {I}}}$ ${\ displaystyle {\ mathcal {P}}}$ ${\ Displaystyle \ sum _ {i \ in {\ mathcal {I}}} m (s (i), i)}$

Příklady

Booleovský problém uspokojivosti (a další tvrdé kombinatorické problémy)

Dobře známá aplikace výběru algoritmů je problém booleovské uspokojivosti . Zde je portfolio algoritmů sada (doplňkových) SAT řešičů , instance jsou booleovské vzorce, nákladová metrika je například průměrná doba běhu nebo počet nevyřešených instancí. Cílem je tedy vybrat dobře fungující SAT řešič pro každou jednotlivou instanci. Stejným způsobem lze výběr algoritmu aplikovat na mnoho dalších tvrdých problémů (jako je programování celých čísel , CSP , plánování AI , TSP , MAXSAT , QBF a programování sady odpovědí ). Konkurenčními systémy v SAT jsou SATzilla, 3S a CSHC ${\ displaystyle {\ mathcal {NP}}}$

Strojové učení

Ve strojovém učení je výběr algoritmu známější jako meta-learning . Portfolio algoritmů se skládá z algoritmů strojového učení (např. Random Forest, SVM, DNN), instance jsou soubory dat a nákladovou metrikou je například chybovost. Cílem je tedy předpovědět, který algoritmus strojového učení bude mít malou chybu v každé sadě dat.

Funkce instance

Problém s výběrem algoritmu je řešen hlavně technikami strojového učení. Reprezentací problémových instancí pomocí numerických funkcí lze výběr algoritmu vnímat jako problém klasifikace více tříd učením mapování pro danou instanci . ${\ displaystyle f}$ ${\ displaystyle f_ {i} \ mapsto {\ mathcal {A}}}$ ${\ displaystyle i}$

Funkce instance jsou numerické reprezentace instancí. Například můžeme spočítat počet proměnných, klauzulí, průměrnou délku klauzule pro booleovské vzorce nebo počet vzorků, funkcí, vyvážení tříd pro datové sady ML, abychom získali představu o jejich charakteristikách.

Statické vs. sondovací funkce

Rozlišujeme dva druhy funkcí:

Statické funkce jsou ve většině případů některé počty a statistiky (např. Poměr klauzulí k proměnným v SAT). Tyto funkce sahají od velmi levných funkcí (např. Počet proměnných) po velmi složité funkce (např. Statistiky o grafech s proměnnými klauzulemi).
Funkce sondování (někdy také nazývané funkce orientačních bodů) se vypočítávají spuštěním určité analýzy chování algoritmu na instanci (např. Přesnost algoritmu levného rozhodovacího stromu v datové sadě ML nebo krátkodobé spuštění stochastického lokálního vyhledávacího řešení na Booleovský vzorec). Tyto funkce často stojí více než jednoduché statické funkce.

Náklady na funkce

V závislosti na použité metrice výkonu může být výpočet funkcí spojen s náklady. Pokud například jako výkonovou metriku použijeme čas běhu, zahrneme čas do výpočtu funkcí naší instance do výkonu systému výběru algoritmů. Řešení SAT je konkrétním příkladem, kde nelze opomíjet takové náklady na funkce, protože instanční funkce pro vzorce CNF mohou být buď velmi levné (např. Pro získání počtu proměnných lze provádět CNF ve stálém čase ve formátu DIMAC) nebo velmi drahé (např. funkce grafu, které mohou stát desítky nebo stovky sekund). ${\ displaystyle m}$

V takových scénářích je důležité v praxi vzít v úvahu režii výpočtu funkcí; jinak se vytvoří zavádějící dojem z výkonu přístupu výběru algoritmu. Pokud například lze rozhodnout, který algoritmus zvolit, s dokonalou přesností, ale funkcemi je doba běhu algoritmů portfolia, není pro přístup portfolia žádný přínos. To by nebylo zřejmé, kdyby byly vynechány náklady na funkce.

Přístupy

Regresní přístup

Jeden z prvních úspěšných přístupů k výběru algoritmu předpovídal výkon každého algoritmu a vybral algoritmus s nejlepším předpokládaným výkonem pro instanci . ${\ displaystyle {\ hat {m}} _ {\ mathcal {A}}: {\ mathcal {I}} \ to \ mathbb {R}}$ ${\ displaystyle arg \ min _ {{\ mathcal {A}} \ in {\ mathcal {P}}} {\ hat {m}} _ {\ mathcal {A}} (i)}$ ${\ displaystyle i}$

Shlukování

Běžným předpokladem je, že danou sadu instancí lze seskupit do homogenních podmnožin a pro každou z těchto podmnožin existuje jeden dobře fungující algoritmus pro všechny instance. Trénink tedy spočívá v identifikaci homogenních klastrů pomocí přístupu klastrování bez dohledu a přidružení algoritmu ke každému klastru. Klastru je přiřazena nová instance a je vybrán přidružený algoritmus. ${\ displaystyle {\ mathcal {I}}}$

Modernějším přístupem je nákladově citlivé hierarchické klastrování pomocí supervizovaného učení k identifikaci homogenních podskupin instancí.

Párově nákladově citlivý přístup ke klasifikaci

Běžným přístupem pro klasifikaci více tříd je naučit se párové modely mezi každou dvojicí tříd (zde algoritmy) a vybrat třídu, která byla párovými modely předpovídána nejčastěji. Instance problému párových predikcí můžeme zvážit pomocí rozdílu výkonu mezi těmito dvěma algoritmy. To je motivováno skutečností, že nám nejvíce záleží na správnosti predikcí s velkými rozdíly, ale penalizace za nesprávnou předpověď je malá, pokud není téměř žádný výkonnostní rozdíl. Každá instance pro školení klasifikačního modelu vs je proto spojena s cenou . ${\ displaystyle i}$ ${\ displaystyle {\ mathcal {A}} _ {1}}$ ${\ displaystyle {\ mathcal {A}} _ {2}}$ ${\ displaystyle | m ({\ mathcal {A}} _ {1}, i) -m ({\ mathcal {A}} _ {2}, i) |}$

Požadavky

Klastrování SAT řešičů ze scénáře SAT12-INDU ASlib podle korelačního koeficientu spearmana.

Shapleyovy hodnoty pro doplňkovou analýzu ve scénáři SAT12-INDU ASlib

Problém s výběrem algoritmu lze efektivně aplikovat za následujících předpokladů:

Portfolio algoritmů je komplementární s ohledem na sadu instancí , tj. Neexistuje jediný algoritmus, který by dominoval výkonu všech ostatních algoritmů (viz obrázky vpravo na příkladech komplementární analýzy). ${\ displaystyle {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {I}}}$ ${\ displaystyle {\ mathcal {A}} \ in {\ mathcal {P}}}$ ${\ displaystyle {\ mathcal {I}}}$
V některých aplikacích je výpočet funkcí instance spojen s cenou. Pokud je například metrikou nákladů doba běhu, musíme také vzít v úvahu čas pro výpočet funkcí instance. V takových případech by náklady na výpočet funkcí neměly být vyšší než zisk z výkonu výběrem algoritmu.

Aplikační domény

Výběr algoritmu není omezen na jednotlivé domény, ale lze jej použít na jakýkoli druh algoritmu, pokud jsou splněny výše uvedené požadavky. Mezi aplikační domény patří:

těžké kombinatorické problémy: SAT , smíšené celočíselné programování , CSP , AI plánování , TSP , MAXSAT , QBF a programování sad odpovědí
kombinatorické aukce
ve strojovém učení je tento problém známý jako meta-učení
softwarový design
optimalizace černé skříňky
systémy s více agenty
numerická optimalizace
lineární algebra, diferenciální rovnice
evoluční algoritmy
problém se směrováním vozidla
energetické systémy

Rozsáhlý seznam literatury o výběru algoritmů odkazujeme na přehled literatury.

Varianty výběru algoritmu

Online výběr

Online výběr algoritmu se týká přepínání mezi různými algoritmy během procesu řešení. To je užitečné jako hyperheuristika . Naproti tomu výběr offline algoritmu vybere algoritmus pro danou instanci pouze jednou a před procesem řešení.

Výpočet plánů

Rozšířením výběru algoritmu je problém s plánováním algoritmu pro každou instanci, ve kterém nevybíráme pouze jednoho řešitele, ale vybíráme časový rozpočet pro každý algoritmus na základě jednotlivých instancí. Tento přístup zlepšuje výkon selekčních systémů, zejména pokud funkce instance nejsou příliš informativní a je pravděpodobný špatný výběr jediného řešitele.

Výběr paralelních portfolií

Vzhledem k rostoucímu významu paralelních výpočtů je rozšířením výběru algoritmů pro paralelní výpočet výběr paralelního portfolia, ve kterém vybereme podmnožinu algoritmů, které mají současně běžet v paralelním portfoliu.

Languages

In other projects