Wybór algorytmu - Algorithm selection

Wybór algorytmu (czasami nazywany również wyborem algorytmu na instancję lub wyborem algorytmu offline ) to technika metaalgorytmiczna służąca do wybierania algorytmu z portfela na zasadzie instancja po instancji. Jest to motywowane obserwacją, że w wielu praktycznych problemach różne algorytmy mają różne charakterystyki wydajnościowe. Oznacza to, że chociaż jeden algorytm działa dobrze w niektórych scenariuszach, w innych działa słabo i na odwrót w przypadku innego algorytmu. Jeśli możemy określić, kiedy użyć którego algorytmu, możemy zoptymalizować dla każdego scenariusza i poprawić ogólną wydajność. To właśnie ma na celu wybór algorytmu. Jedynym warunkiem zastosowania technik wyboru algorytmów jest istnienie (lub możliwość skonstruowania) zestawu algorytmów komplementarnych.

Definicja

Biorąc pod uwagę portfolio algorytmów , zestaw instancji i metrykę kosztu , problem wyboru algorytmu polega na znalezieniu mapowania z instancji na algorytmy, tak aby zoptymalizować koszt we wszystkich instancjach. ${\mathcal {P}}$ ${\ Displaystyle {\ mathcal {A}} \ w {\ mathcal {P}}}$ $i\in {\mathcal {I}}$ ${\ Displaystyle m: {\ mathcal {P}} \ razy {\ mathcal {I}} \ do \ mathbb {R}}$ $s:{\mathcal {I}}\do {\mathcal {P}}$ ${\mathcal {I}}$ ${\mathcal {P}}$ ${\ Displaystyle \ suma _ {i \ w {\ matematyczne {I}}} m (s (i), ja)}$

Przykłady

Problem spełnialności logicznej (i inne trudne problemy kombinatoryczne)

Dobrze znanym zastosowaniem doboru algorytmów jest problem spełnialności Boole'a . W tym przypadku portfolio algorytmów to zestaw (komplementarnych) solwerów SAT , instancje to formuły logiczne, metryka kosztu to na przykład średni czas działania lub liczba nierozwiązanych instancji. Tak więc celem jest wybranie dobrze działającego solvera SAT dla każdej indywidualnej instancji. W ten sam sposób wybór algorytmu może być zastosowany do wielu innych trudnych problemów (takich jak programowanie mieszanych liczb całkowitych , CSP , planowanie AI , TSP , MAXSAT , QBF i programowanie zbioru odpowiedzi ). Zwycięskie systemy w SAT to SATzilla, 3S i CSHC ${\mathcal {NP}}$

Nauczanie maszynowe

W uczeniu maszynowym wybór algorytmu jest lepiej znany jako metauczenie . Portfel algorytmów składa się z algorytmów uczenia maszynowego (np. Random Forest, SVM, DNN), instancje to zestawy danych, a metryka kosztu to np. stopa błędów. Celem jest więc przewidzenie, który algorytm uczenia maszynowego będzie miał mały błąd w każdym zestawie danych.

Funkcje instancji

Problem wyboru algorytmu rozwiązywany jest głównie za pomocą technik uczenia maszynowego. Reprezentując instancje problemu za pomocą cech liczbowych , wybór algorytmu może być postrzegany jako problem klasyfikacji wieloklasowej poprzez uczenie się mapowania dla danej instancji . $f$ ${\ Displaystyle f_ {i} \ mapsto {\ mathcal {A}}}$ $i$

Elementy instancji są numerycznymi reprezentacjami instancji. Na przykład możemy policzyć liczbę zmiennych, klauzul, średnią długość klauzuli dla formuł logicznych lub liczbę próbek, cech, balans klas dla zestawów danych ML, aby uzyskać wrażenie na temat ich cech.

Funkcje statyczne a funkcje sondowania

Rozróżniamy dwa rodzaje cech:

Cechy statyczne to w większości przypadków pewne liczebności i statystyki (np. stosunek klauzul do zmiennych w SAT). Cechy te wahają się od bardzo tanich cech (np. liczba zmiennych) do bardzo złożonych cech (np. statystyki dotyczące wykresów z klauzulami zmiennymi).
Funkcje sondujące (czasami nazywane również cechami charakterystycznymi) są obliczane poprzez przeprowadzenie analizy zachowania algorytmu na instancji (np. dokładność taniego algorytmu drzewa decyzyjnego w zestawie danych ML lub uruchomienie przez krótki czas stochastycznego lokalnego solwera wyszukiwania na formuła logiczna). Te funkcje często kosztują więcej niż proste funkcje statyczne.

Koszty funkcji

W zależności od użytej metryki wydajności obliczenia funkcji mogą być powiązane z kosztami. Na przykład, jeśli używamy czasu działania jako miernika wydajności, uwzględniamy czas na obliczenie funkcji naszej instancji w wydajności systemu wyboru algorytmu. Rozwiązywanie SAT jest konkretnym przykładem, w którym nie można pominąć takich kosztów funkcji, ponieważ funkcje instancji dla formuł CNF mogą być albo bardzo tanie (np. aby uzyskać liczbę zmiennych można wykonać w stałym czasie dla CNF w formacie DIMACs) lub bardzo drogie (np. funkcje wykresów, które mogą kosztować dziesiątki lub setki sekund). ${\ Displaystyle m}$

W takich scenariuszach ważne jest, aby wziąć pod uwagę narzut związany z obliczaniem cech w praktyce; w przeciwnym razie powstaje mylące wrażenie wydajności podejścia do wyboru algorytmu. Na przykład, jeśli decyzja, który algorytm wybrać, może być podjęta z idealną dokładnością, ale cechami są czas działania algorytmów portfela, podejście portfelowe nie przynosi żadnych korzyści. Nie byłoby to oczywiste, gdyby pominięto koszty funkcji.

Podchodzi do

Podejście regresji

Jedno z pierwszych udanych podejść do wyboru algorytmów przewidywało wydajność każdego algorytmu i wybierało algorytm o najlepszej przewidywanej wydajności dla instancji . ${\ Displaystyle {\ kapelusz {m}} _ {\ mathcal {A}}: {\ mathcal {I}} \ do \ mathbb {R}}$ ${\ Displaystyle arg \ min _ {{\ mathcal {A}} \ w {\ mathcal {P}}} {\ kapelusz {m}} _ {\ mathcal {A}} (i)}$ $i$

Podejście klastrowe

Powszechnie przyjmuje się, że dany zbiór instancji można pogrupować w jednorodne podzbiory, a dla każdego z tych podzbiorów istnieje jeden dobrze działający algorytm dla wszystkich znajdujących się tam instancji. Tak więc szkolenie polega na identyfikacji jednorodnych klastrów za pomocą nienadzorowanego podejścia do grupowania i powiązaniu algorytmu z każdym klastrem. Nowa instancja jest przypisywana do klastra i wybierany powiązany algorytm. ${\mathcal {I}}$

Bardziej nowoczesnym podejściem jest hierarchiczne grupowanie uwzględniające koszty, wykorzystujące nadzorowane uczenie do identyfikacji jednorodnych podzbiorów instancji.

Podejście do klasyfikacji uwzględniające koszty w parach

Powszechnym podejściem do klasyfikacji wieloklasowej jest uczenie się modeli parami pomiędzy każdą parą klas (tu algorytmów) i wybranie klasy, która była najczęściej przewidywana przez modele parami. Możemy zważyć wystąpienia problemu przewidywania parami przez różnicę wydajności między dwoma algorytmami. Wynika to z faktu, że najbardziej zależy nam na tym, aby prognozy z dużymi różnicami były poprawne, ale kara za niepoprawną prognozę jest niewielka, jeśli prawie nie ma różnicy w wydajności. Dlatego każde wystąpienie do uczenia modelu klasyfikacji vs jest skojarzone z kosztem . $i$ ${\mathcal {A}}_{1}$ ${\ Displaystyle {\ Mathcal {A}} _ {2}}$ ${\ Displaystyle | m ({\ matematyka {A}} _ {1}, ja) - m ({\ matematyka {A}} _ {2}, ja) |}$

Wymagania

Grupowanie solwerów SAT ze scenariusza SAT12-INDU ASlib według współczynnika korelacji Spearmana.

Wartości Shapleya do analizy uzupełniającej w scenariuszu SAT12-INDU ASlib

Problem wyboru algorytmu można skutecznie zastosować przy następujących założeniach:

Portfel algorytmów jest komplementarny w stosunku do zbioru instancji , tj. nie ma jednego algorytmu, który dominuje nad wydajnością wszystkich innych algorytmów (patrz rysunki po prawej dla przykładów analizy komplementarnej). ${\mathcal {P}}$ ${\mathcal {I}}$ ${\ Displaystyle {\ mathcal {A}} \ w {\ mathcal {P}}}$ ${\mathcal {I}}$
W niektórych aplikacjach obliczanie cech instancji wiąże się z kosztem. Na przykład, jeśli metryką kosztu jest czas działania, musimy również wziąć pod uwagę czas na obliczenie funkcji instancji. W takich przypadkach koszt obliczeń funkcji nie powinien być większy niż wzrost wydajności wynikający z wyboru algorytmu.

Domeny aplikacji

Wybór algorytmu nie ogranicza się do pojedynczych dziedzin, ale można go zastosować do dowolnego algorytmu, jeśli spełnione są powyższe wymagania. Domeny aplikacji obejmują:

trudne problemy kombinatoryczne: SAT , mieszane programowanie liczb całkowitych , CSP , planowanie AI , TSP , MAXSAT , QBF i programowanie zestawów odpowiedzi
aukcje kombinatoryczne
w uczeniu maszynowym problem znany jest jako meta-learning
projektowanie Oprogramowania
optymalizacja czarnoskrzynkowa
systemy wieloagentowe
optymalizacja numeryczna
algebra liniowa, równania różniczkowe
algorytmy ewolucyjne
problem z wyznaczaniem trasy pojazdu
systemy zasilania

Obszerną listę literatury na temat doboru algorytmów można znaleźć w przeglądzie literatury.

Warianty doboru algorytmu

Wybór online

Wybór algorytmu online odnosi się do przełączania pomiędzy różnymi algorytmami podczas procesu rozwiązywania. Jest to przydatne jako hiperheurystyka . Natomiast wybór algorytmu offline wybiera algorytm dla danej instancji tylko raz i przed procesem rozwiązywania.

Obliczanie harmonogramów

Rozszerzeniem doboru algorytmu jest problem szeregowania algorytmów na instancję, w którym nie wybieramy tylko jednego solvera, ale dobieramy budżet czasowy dla każdego algorytmu w oparciu o instancję. Takie podejście poprawia wydajność systemów selekcji, w szczególności jeśli cechy instancji nie są zbyt pouczające i istnieje prawdopodobieństwo błędnego wyboru pojedynczego solvera.

Wybór portfeli równoległych

Biorąc pod uwagę rosnące znaczenie obliczeń równoległych, rozszerzeniem wyboru algorytmów do obliczeń równoległych jest wybór portfela równoległego, w którym wybieramy podzbiór algorytmów do jednoczesnego działania w portfelu równoległym.

Languages

In other projects