Stage-dependent integer-binary encoding in factorization-machine black-box optimization

기술 요약: 인자 분해 기반 블랙박스 최적화에서의 단계별 정수-이진 인코딩

문제 정의
블랙박스 최 optimization(BBO)은 목적 함수가 명시적인 해석적 형태를 갖지 않고 평가 비용이 많이 드는 문제를 다룹니다. Factorization Machine with Quadratic-optimization Annealing (FMQA)은 Factorization Machine (FM)을 사용하여 대리 모델(surrogate model)을 구축하고 이를 이징 머신(Ising machine)으로 최적화하는 저명한 BBO 접근 방식입니다. FMQA의 핵심 구성 요소는 정수 또는 연속 변수를 정수-이진 인코딩(예: 원-핫, 도메인 월, 또는 이진 인코딩)을 통해 이진 변수로 변환하여 문제를 이차 무제약 이진 최적화(QUBO) 모델로 정식화하는 것입니다.

기존의 FMQA는 머신 러닝 단계(대리 모델 구축)와 솔루션 탐색 단계(이징 머신 최적화) 모두에서 단일 정수-이진 인코딩 방법을 사용합니다. 그러나 이전 연구에 따르면 트레이드오프가 존재함을 시사합니다. 즉, 도메인 월(domain-wall) 인코딩은 이징 머신에서 우수한 솔루션 탐색 성능을 제공하는 경우가 많은 반면, 원-핫(one-hot) 인코딩은 전체 FMQA 최적화 과정에서 더 낮은 목적 함수 값을 생성하는 것으로 관찰되었습니다. 이러한 불일치는 학습에 최적인 인코딩이 지형(landscape)을 학습하는 데 적합한 인코딩과 탐색하는 데 적합한 인코딩과 다를 수 있음을 의미합니다. 단일 인코딩을 고정하는 기존 방식은 FM과 이징 머신의 서로 다른 능력을 완전히 활용하지 못할 수 있습니다.

방법론
저자들은 머신 러닝 단계와 솔루션 탐색 단계에 서로 다른 정수-이진 인코딩 방법을 사용하는 단계별 FMQA 프레임워크를 제안합니다. 이 접근 방식의 핵심은 다음과 같습니다.

1. 이중 인코딩 전략: 본 프레임워크는 학습에 적합한 인코딩(제안된 "OhDw" 변형에서는 원-핫 인코딩)을 사용하여 FM 대리 모델을 학습시킨 후, 이 결과물인 대리 모델을 이징 머신에 의한 최적화 전 탐색에 적합한 다른 인코딩(도메인 월 인코딩)으로 변환합니다.
2. QUBO 행렬 변환: 이러한 전환을 가능하게 하기 위해, 저자들은 원-핫 인코딩과 도메인 월 인코딩 사이의 QUBO 행렬 간 수학적 변환 공식을 유도했습니다. 이 공식들은 가능한 정수 상태에 대해 대리 목적 함수 지형을 (가산 상수 항을 제외하고) 보존합니다.
   • 원-핫에서 도메인 월로의 변환은 특정 합산 관계(식 18–20)를 사용하여 QUBO 행렬 $Q^{(oh)}$의 대각 및 비대각 항을 $Q^{(dw)}$로 변환하는 과정을 포함합니다.
   • 도메인 월에서 원-핫으로의 역변환 또한 유도되었습니다(식 22–24).
   • 이러한 상호 변환의 계산 복잡도는 $O(N^2q^2)$로 설정되었으며, 여기서 $N$은 입력 차원이고 $q$는 이산화 레벨입니다.
3. 알고리즘 워크플로우:
   • 학습 단계: 원-핫 인코딩을 사용하여 인코딩된 입출력 데이터에 대해 FM을 학습시킵니다.
   • 변환: 학습된 대리 모델(QUBO 행렬로 표현됨)을 원-핫에서 도메인 월 인코딩으로 변환합니다.
   • 탐색 단계: 변환된 QUBO에 도메인 월 인코딩 제약 조건을 추가하여 이징 머신(Fixstars Amplify Annealing Engine)을 통해 후보 솔루션을 최적화합니다.
   • 평가: 솔루션을 디코딩하여 실제 블랙박스 함수에 대해 평가하고, 다음 반복(iteration)을 위한 학습 데이터셋에 추가합니다.

주요 기여

1. 프레임워크 제안: 프로세스 전반에 걸쳐 단일 인코딩을 고정하는 대신, 학습 단계와 탐색 단계 사이의 인코딩 선택을 분리하는 FMQA 프레임워크를 도입했습니다.
2. 이론적 유도: 학습된 모델의 충실도(fidelity)를 잃지 않고 인코딩 전환을 가능하게 하는, 원-핫 및 도메인 월 QUBO 행렬 간의 상호 변환 공식을 유도했습니다.
3. 경험적 분해: 정수-이진 인코딩의 효과를 학습 단계와 솔루션 탐색 단계의 기여분으로 수치적으로 분해하여, 각각의 영향력을 별도로 평가함으로써 성능에 미치는 영향을 이해했습니다.

실험 결과
제안된 방법은 다봉형 벤치마크 문제인 Rastrigin 함수에 대해 입력 차원 $N \in \{2, 5\}$ 및 이산화 레벨 $q \in \{61, 301\}$ 조건에서 평가되었습니다. 제안된 "OhDw" 방식(학습에는 원-핫, 탐색에는 도메인 월 사용)의 성능을 기존의 단일 인코딩 변형들(Oh, Dw, Bi) 및 베이지안 최적화(BO)와 비교했습니다.

• 학습 단계 인코딩의 지배력: 모든 조건에서 학습 단계에 사용된 인코딩이 최적화 성능을 결정하는 지배적인 요인이었습니다. 학습 단계에서 원-핫 인코딩을 사용하는 방식(Oh 및 OhDw)이 도메인 월 또는 이진 인코딩을 사용하는 방식보다 일관되게 더 낮은 잔차 오차(residual error)를 달면했습니다.
• 단계별 이점: 솔루션 탐색 단계에서 도메인 월 인코딩으로 전환하는 이점은 조건에 따라 달랐습니다.
  • $N=5$ 및 $q=301$ (더 미세한 이산화, 더 큰 탐색 공간)의 경우, OhDw 방식은 Oh 방식(원-핫 전용)에 비해 더 낮은 잔차 오차와 전역 최적값에 더 가까운 솔루션을 달성했습니다.
  • $N=5$ 및 $q=61$의 경우, Oh 방식이 OhDw보다 약간 더 우수한 성능을 보였습니다.
  • $N=2$의 경우, Oh와 OhDw 사이에 유의미한 성능 차이가 관찰되지 않았습니다.
• 탐색 안정성: 솔루션 탐색 단계 분석 결과, 도메인 월 인코딩은 이징 머신 내에서 실행 가능한 상태 간의 더 안정적인 전이를 허용하는 반면, 원-핫 인코딩은 제약 조건을 위반하는 상태를 거쳐야 하므로 탐색 안정성을 저해할 가능성이 있는 것으로 나타났습니다.

의의 및 주장
본 논문은 정수-이진 인코딩의 선택이 단순한 표현 방식의 선택이 아니라, FMQA의 학습 및 솔루션 탐색 단계에서 서로 다른 역할을 수행하는 설계 요소라고 주장합니다. 주요 발견은 학습 단계에서의 원-핫 인코딩이 정확한 대리 모델을 구축하는 탁월한 능력 덕분에 최적화 성능을 주도하는 핵심 동력이라는 점입니다. 그러나 본 연구는 단계별 인코딩(특히 학습을 위한 원-핫과 탐색을 위한 도메인 월의 결로)을 사용하는 것이, 특히 입력 차원이 크고 이산화가 미세하여 탐색 공간이 복잡한 시나리오에서 추가적인 개선을 제공할 수 있음을 입증했습니다.

저자들은 OhDw 방식이 유망함을 보여주지만, 그 일반성을 확보하기 위해서는 더 다양한 벤치마크 함수와 실제 설계 최적화 문제에 대한 추가 검증이 필요하다고 결론지었습니다. 또한, 페널티 계수에 대한 민감도 및 QUBO 밀도 차이에 대한 체계적인 분석이 향후 연구 과제로 남아 있습니다.