알고리즘 선택

알고리즘 선택(인스턴스별 알고리즘 선택 또는 오프라인 알고리즘 선택이라고도 함)은 인스턴스별로 포트폴리오에서 알고리즘을 선택하는 메타 알고리즘 기법입니다.이는 많은 실제 문제에서 서로 다른 알고리즘이 서로 다른 성능 특성을 갖는다는 관찰에 의해 동기 부여됩니다.즉, 어떤 알고리즘은 어떤 시나리오에서는 잘 동작하지만 다른 알고리즘에서는 그 반대로 동작하지 않습니다.어느 알고리즘을 사용할지를 특정할 수 있으면, 각 시나리오에 맞추어 최적화해, 전체적인 퍼포먼스를 향상시킬 수 있습니다.이것이 알고리즘 선택이 목표로 하는 것입니다.알고리즘 선택 기술을 적용하기 위한 유일한 전제조건은 일련의 보완 알고리즘이 존재하는 것(또는 구성 가능한 것)입니다.

정의.

${\mathcal {A}}\in {\mathcal {P}}$ ${\mathcal {A}}\in {\mathcal {P}}$ 의 ${\mathcal {P}}$ P $(\$ 가 ${\mathcal {P}}$ $주어지면 인스턴스$ i $(\displaystyle$ i\in $\$ mathcal { $I})$ 와 $i\in {\mathcal {I}}$ 비용 $m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R}$ m $:$ P × $m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R}$ $m:{\mathcal {P}}\times {\mathcal {I}}\to \mathbb {R}$ R(\ $displaystyle {P})$ 의 집합은 $i\in {\mathcal {I}}$ 과 같습니다 $i\in {\mathcal {I}}$ orithm 선택 문제는 I $\sum _{i\in {\mathcal {I}}}m(s(i),i)$ $(\$ 에서 ${\mathcal {I}}$ ${\mathcal {P}}$ P(\ $displaystyle$ $\$ displaystyle\ $mathcal {P})$ 에 ${\mathcal {P}}$ $\sum _{i\in {\mathcal {I}}}m(s(i),i)$ I $s:{\mathcal {I}}\to {\mathcal {P}}$ $\sum _{i\in {\mathcal {I}}}m(s(i),i)$ $displaystyle$ s $mathcal$ ${P})$ 의 $s:{\mathcal {I}}\to {\mathcal {P}}$ $s:{\mathcal {I}}\to {\mathcal {P}}$ 을 찾는 것으로 구성됩니다 $.$ 모든 $인스턴스에서 }}m(s($ i $\sum _{i\in {\mathcal {I}}}m(s(i),i)$ ),i)}이(가) 최적화되었습니다.^[1]^[2]

예

부울 만족도 문제(및 기타 하드 조합 문제)

알고리즘 선택의 잘 알려진 적용은 부울 만족도 문제입니다.여기서 알고리즘의 포트폴리오는 (보완적인) SAT 솔버 세트이며 인스턴스는 부울 공식이며 비용 메트릭은 예를 들어 평균 런타임 또는 미해결 인스턴스 수입니다.따라서 각 인스턴스의 성능이 뛰어난 SAT 솔버를 선택하는 것이 목표입니다.마찬가지로 알고리즘 선택은 다른 ${\mathcal {NP}}$ $(\$ - 혼합 정수 프로그래밍, CSP, AI 계획, TSP, MAXSAT, QBF 및 응답 집합 프로그래밍 등)에 ${\mathcal {NP}}$ 적용할 수 있습니다.SAT의 경쟁 우위 시스템은 SATzilla,^[3] 3S^[4] 및 CSHC입니다^[5].

기계 학습

기계학습에서 알고리즘 선택은 메타학습으로 더 잘 알려져 있다.알고리즘의 포트폴리오는 기계 학습 알고리즘(예: 랜덤 포레스트, SVM, DNN)으로 구성되며, 인스턴스는 데이터 세트이며 비용 메트릭은 오류율이다.따라서 목표는 각 데이터 세트에서 어떤 기계 학습 알고리즘이 작은 오류를 가질지 예측하는 것입니다.

인스턴스 기능

알고리즘 선택 문제는 주로 기계 학습 기술로 해결된다.문제 인스턴스를 수치 $특징$ f {\ $displaystyle$ f $f$ 로 표시함으로써 알고리즘 선택은 특정 $인스턴스$ i {\ $displaystyle$ $i$ $i$ 에 대한 $f_{i}\mapsto {\mathcal {A}}$ f $f_{i}\mapsto {\mathcal {A}}$ $f_{i}\mapsto {\mathcal {A}}$ A $f_{i}\mapsto {\mathcal {A}}$ 를 $f_{i}\mapsto {\mathcal {A}}$ 학습함으로써 다중 클래스 분류 문제로 볼 수 있습니다.

인스턴스 기능은 인스턴스를 숫자로 표현한 것입니다.예를 들어 변수, 구, 부울 ^[6]수식의 평균 구 길이 또는 ML 데이터 세트의 샘플, 피쳐, 클래스 밸런스 수를 세어 특성에 대한 인상을 얻을 수 있습니다.

정적 기능과 프로빙 기능 비교

다음 두 가지 기능을 구분합니다.

정적 기능은 대부분의 경우 일부 카운트와 통계(SAT의 절 대 변수 비율 등)입니다.이러한 특징은 매우 저렴한 특징(예: 변수 수)에서 매우 복잡한 특징(예: 변수 절 그래프에 대한 통계)까지 다양하다.
프로빙 기능(일명 랜드마크 기능이라고도 함)은 인스턴스에서 알고리즘 동작의 일부 분석(예를 들어 ML 데이터 세트에서 저렴한 의사결정 트리 알고리즘의 정확도 또는 부울 공식에서 확률적 로컬 검색 솔버를 단시간 실행)을 실행하여 계산됩니다.이러한 기능에는 단순한 정적 기능보다 비용이 많이 듭니다.

기능 비용

사용하는 퍼포먼스 $메트릭$ m {\ $display$ m $m$ 에 따라 피쳐 계산은 비용과 관련지을 수 있습니다.예를 들어 실행 시간을 성능 지표로 사용할 경우 인스턴스 기능을 계산하는 시간을 알고리즘 선택 시스템의 성능에 포함합니다.CNF 공식의 인스턴스 기능이 매우 저렴하거나(예: DIMAC 형식의 CNF에 대해 일정한 시간에 수행할 수 있음) 매우 고가(예: 수십 초 또는 수백 초가 소요될 수 있는 그래프 기능)이기 때문에 SAT 해결은 이러한 기능 비용을 무시할 수 없는 구체적인 사례이다.

이러한 시나리오에서는 실제로 기능 계산의 오버헤드를 고려하는 것이 중요합니다.그렇지 않으면 알고리즘 선택 접근법의 퍼포먼스에 대해 오해를 불러일으킬 수 있는 인상이 생깁니다.예를 들어, 어떤 알고리즘을 선택할지를 정확하게 결정할 수 있지만, 특징이 포트폴리오 알고리즘의 실행 시간인 경우에는 포트폴리오 접근법에 이점이 없습니다.기능 비용을 생략하면 이는 명확하지 않습니다.

접근

회귀적 접근법

가장 먼저 성공한 알고리즘 선택 방법 ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ 하나는 각 ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ m ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ A ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ : ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ ${\display$ { $hat {m}}$ {\ $mathcal {A}}$ {\ $mathbb {R}}}$ 의 ${\hat {m}}_{\mathcal {A}}:{\mathcal {I}}\to \mathbb {R}$ 성능을 예측하고 $arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)$ $arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)$ $arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)$ ^ }의 $arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)$ 을 가장 잘 예측한 알고리즘을 선택하였습니다( $표시$ Istyl $).$ $e$ arg $\min$ _ ${\$ $mathcal$ ${A}\in {\mathcal {P}}{\hat {m}}_{\mathcal$ { $A}}(i$ $i$ ^[3] 인스턴스 $arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)$ $i$ 의 $arg\min _{{\mathcal {A}}\in {\mathcal {P}}}{\hat {m}}_{\mathcal {A}}(i)$ 경우

클러스터링 어프로치

일반적인 가정은 주어진 ${\mathcal {I}}$ 세트 I $(\$ 를 ${\mathcal {I}}$ 균일한 서브셋으로 묶을 수 있으며, 각 서브셋에 대해 모든 인스턴스에 대해 하나의 고성능 알고리즘이 있다는 것입니다.따라서, 훈련은 비감독 클러스터링 접근방식을 통해 동종 클러스터를 식별하고 알고리즘을 각 클러스터에 연결하는 것으로 구성됩니다.새 인스턴스가 클러스터에 할당되고 관련 알고리즘이 ^[7]선택됩니다.

보다 현대적인 접근방식은 동종 인스턴스 서브셋을 식별하기 위해 감독 학습을 사용하는 비용에 민감한 계층형^[5] 클러스터링입니다.

비용에 민감한 쌍별 분류 방법

다중 클래스 분류의 일반적인 접근법은 모든 클래스 쌍(여기서 알고리즘) 간에 쌍별 모델을 학습하고 쌍별 모델에 의해 가장 자주 예측된 클래스를 선택하는 것이다.우리는 두 알고리즘 간의 성능 차이로 쌍별 예측 문제의 인스턴스를 가중치할 수 있다.이는 차이가 큰 예측을 맞히는 데 가장 신경을 쓰지만 성능 차이가 거의 없을 경우 잘못된 예측에 대한 벌칙은 작기 때문입니다.따라서 분류 ${\mathcal {A}}_{1}$ $($ $스타일$ ${A}_$ 과 $($ 스타일 { $A}$ $|m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|$ ${2})$ 의 ${\mathcal {A}}_{2}$ 각 $i$ 는 $i$ $|m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|$ m $|m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|$ 1, $|m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|$ - m $표시 스타일$ m $({\mathcal {A}})과 관련된다.$ $i)$ $|m({\mathcal {A}}_{1},i)-m({\mathcal {A}}_{2},i)|$ ^[8]

요구 사항들

SAT12-INDU ASlib 시나리오의 SAT 솔버 클러스터화는 스피어맨의 상관계수에 따른 것입니다.

SAT12-INDU ASlib^[9] 시나리오에 대한 보완 분석을 위한 Shapley 값

알고리즘 선택 문제는 다음 전제 조건 하에서 효과적으로 적용할 수 있습니다.

The portfolio ${\mathcal {P}}$ of algorithms is complementary with respect to the instance set ${\mathcal {I}}$ , i.e., there is no single algorithm ${\mathcal {A}}\in {\mathcal {P}}$ that dominates the performance of all other algorithms over ${\$ $displaystyle$ {\ $mathcal {I}}($ 보완 분석에 대한 예는 오른쪽 그림 참조).
일부 응용 프로그램에서는 인스턴스 기능의 계산이 비용과 관련되어 있습니다.예를 들어 비용 메트릭이 실행 중인 경우 인스턴스 기능을 계산하는 시간도 고려해야 합니다.이 경우 기능 계산 비용은 알고리즘 선택을 통한 성능 향상보다 커서는 안 됩니다.

응용 프로그램 도메인

알고리즘 선택은 단일 도메인으로 한정되지 않고 위의 요건을 충족하면 모든 종류의 알고리즘에 적용할 수 있습니다.응용 프로그램 도메인은 다음과 같습니다.

하드 조합 문제:^[10] SAT, 혼합 정수 프로그래밍, CSP, AI 계획, TSP, MAXSAT, QBF 및 앤서 세트 프로그래밍
조합 경매
기계 학습에서, 문제는 메타 학습으로 알려져 있다.
소프트웨어 설계
블랙박스 최적화
멀티 에이전트 시스템
수치 최적화
선형 대수, 미분 방정식
진화 알고리즘
차량 경로 문제
전원 시스템

알고리즘 선택에 관한 광범위한 문헌 목록은 문헌 개요를 참조한다.