Black-box optimization using factorization and Ising machines

본 논문은 다양한 분야의 대규모 블랙박스 최적화 문제를 효율적으로 해결하기 위해 대리 모델로서 인수분해 머신을 그리고 이징 머신을 활용하는 인수분해 머신 양자 어닐링 (FMQA) 알고리즘을 검토하며, 동시에 즉각적인 도입을 촉진하기 위해 필요한 도구와 적용 사례를 제공합니다.

핵심

케이크를 위한 완벽한 레시피를 찾으려 한다고 상상해 보세요. 하지만 요리책도, 재료 목록도, 오븐이 어떻게 작동하는지에 대한 지식도 없습니다. 오직 케이크를 구워 보고 맛을 본 뒤 점수를 받는 것만 가능합니다. 케이크가 건조하면 낮은 점수를 받고, 맛있으면 높은 점수를 받습니다. 이것이 과학자들이 블랙박스 최적화라고 부르는 것입니다. 당신은 최고의 "입력"(재료) 을 찾아 최고의 "출력"(맛) 을 얻으려 하지만, 그 기계(오븐) 는 미스터리입니다.

문제는 가능한 재료 조합이 수십억 가지나 된다는 점입니다. 하나씩 모두 시도해 보는 것은 영원히 걸릴 것입니다. 다음으로 가장 좋은 배치를 추측하는 것도 어렵습니다. 규칙을 알 수 없기 때문입니다.

이 논문은 두 가지 주요 도구를 사용하여 이 미스터리를 해결하는 교묘한 새로운 방법을 소개합니다. 바로 스마트 추측 기계(팩터제이션 머신) 와 초고속 검색 엔진(이징 머신) 입니다.

다음은 단계별 작동 원리입니다:

1. 스마트 추측 기계 (대리 모델)

매번 레시피를 테스트할 때마다 실제 케이크를 구우는 대신, 오븐의 "디지털 트윈"을 구축합니다. 몇 개의 케이크를 구워 결과를 기록한 뒤, 컴퓨터 프로그램인 팩터제이션 머신에게 이전 레시피들을 바탕으로 새로운 레시피가 얼마나 좋을지 예측하도록 가르칩니다.

• 비유: 이는 100 개의 케이크를 맛본 음식 평론가와 같습니다. "계란 2 개와 설탕 3 컵을 사용한다"고 말하면, 실제로 구워 보지 않아도 점수를 추측할 수 있습니다.
• 한계: 비록 똑똑한 평론가가 있더라도, 수십억 가지 옵션 중에서 절대적으로 최고의 레시피를 찾는 것은 여전히 거대한 퍼즐입니다. 재료가 이산적(discrete) 인 경우 (예: "계란 1 개 추가" 또는 "계란 2 개 추가"이지 "계란 1.5 개 추가"가 아님) 가능성의 수가 폭발적으로 증가합니다.

2. 초고속 검색 엔진 (이징 머신)

이제 논문이 흥미로워집니다. 저자들은 "스마트 추측 기계"를 특수한 유형의 컴퓨터인 이징 머신이 완벽하게 이해하는 언어로 변환할 수 있음을 깨달았습니다.

• 비유: 이징 머신을 거대하고 초고속인 미로 해결사로 상상해 보세요. 보통 이러한 기계들은 배송 트럭의 최단 경로를 찾거나 자석을 배열하는 것과 같은 복잡한 퍼즐을 푸는 데 사용됩니다.
• 마법 같은 트릭: 저자들은 "스마트 추측 기계"의 예측 문제를 이징 머신이 순식간에 풀 수 있는 미로로 변환하는 방법을 발견했습니다. 컴퓨터가 천천히 추측하고 확인하는 대신, 이징 머신은 "스마트 평론가"가 가장 좋다고 생각하는 재료 조합을 즉시 찾아냅니다.

3. "FMQA" 알고리즘

논문은 이 전체 과정을 FMQA(2 차 최적화 어닐링을 갖춘 팩터제이션 머신) 라고 부릅니다.

• 흐름:
  1. 몇 개의 케이크를 구워 데이터를 수집합니다.
  2. 스마트 평론가 (팩터제이션 머신) 를 훈련시킵니다.
  3. 초고속 검색 엔진 (이징 머신) 에게 평론가가 상상할 수 있는 최고의 레시피를 찾도록 요청합니다.
  4. 그 특정 레시피를 구워 실제 점수를 얻습니다.
  5. 그 새로운 점수를 평론가에게 피드백하고 반복합니다.

이것이 왜 중요한가요?

보통 거대한 목록에서 최고의 레시피를 찾는 것은 극도로 느립니다. 이 논문은 "평론가"와 "초고속 검색 엔진"이라는 특정 조합을 사용하면 옵션 목록이 거대하더라도 이전보다 훨씬 빠르게 훌륭한 해결책을 찾을 수 있음을 보여줍니다.

논문에서 제시된 실제 사례

저자들은 이론만 이야기한 것이 아니라, 과학과 공학의 실제 "레시피"로 이를 테스트했습니다:

• 초재료 설계: 냉각을 위한 "메타물질"(특별한 성질을 가진 인공 재료) 을 설계했습니다. 서로 다른 재료로 만든 작은 막대들을 배열해야 했습니다. 알고리즘은 무작위 추측보다 더 잘 작동하는 패턴을 찾았습니다.
• 더 나은 층 구조 설계: 빛은 통과시키지만 열은 차단하는 창문용 필름 층을 설계했습니다. 알고리즘은 재료를 쌓는 완벽한 순서를 파악했습니다.
• 교통 신호등 개선: 교통 신호등을 퍼즐처럼 취급했습니다. 목표는 차량이 도시를 더 빠르게 이동하게 만드는 것이었습니다. 알고리즘은 빨간불과 초록불의 타이밍을 조정하여 표준 설정보다 훨씬 매끄러운 흐름을 찾았습니다.
• 비행기 날개 설계: 날개의 모양을 조정하여 더 효율적으로 비행하도록 했습니다 (양력 증가, 항력 감소).
• 신약 개발 (펩타이드): 박테리아는 죽이지만 인간 세포에는 해를 끼치지 않는 짧은 단백질 사슬 (펩타이드) 을 설계했습니다. 이는 건초더미에서 바늘을 찾는 것과 같지만, 알고리즘은 실험실에서 테스트했을 때 실제로 작동하는 몇 가지를 찾아냈습니다.

결론

이 논문은 특정 유형의 AI(팩터제이션 머신) 와 특수 하드웨어(이징 머신) 를 결합함으로써 과학자들이 "블랙박스" 문제를 훨씬 빠르게 해결할 수 있다고 주장합니다. 이는 탐정에게 가장 유망한 단서를 즉시 강조해 주는 초강력 확대경을 주는 것과 같습니다. 이를 통해 이전에는 너무 복잡해서 풀 수 없었던 범죄 (또는 재료 설계) 를 해결할 수 있게 됩니다.

저자들은 다른 과학자들이 자신의 어려운 퍼즐을 해결하기 위해 이 "스마트 평론가 + 초고속 검색 엔진" 조합을 사용할 수 있도록 무료 소프트웨어 도구를 공개하기도 했습니다.

기술 요약

Tamura 등 의 논문 "Black-box optimization using factorization and Ising machines"에 대한 상세한 기술적 요약입니다.

1. 문제 정의

**블랙박스 최적화 (BBO)**는 재료 설계 및 신약 개발부터 머신러닝 하이퍼파라미터 튜닝에 이르기까지 다양한 분야에서 중요한 과제입니다. BBO 에서 목적 함수 $y(x)$는 내부 함수 형태와 기울기가 알려지지 않은 "블랙박스"이며, 입력 - 출력 쌍만 이용 가능합니다.

• 과제: 베이지안 최적화 (BO) 와 같은 기존 BBO 방법은 가우시안 프로세스 (Gaussian Processes) 와 같은 대리 모델을 사용하여 최적 입력을 예측합니다. 그러나 입력 공간이 이산적, 고차원적, 또는 조합적일 때 획득 함수 (acquisition function) (다음 입력을 선택하는 기준) 를 최적화하는 것은 계산적으로 해결하기 어렵습니다.
• 병목 현상: 후보 입력의 수가 증가함에 따라 완전 탐색은 불가능 (NP-hard) 해지며, 기울기 기반 방법은 이산 변수에서 실패합니다. 기존 방법들은 전역 최적점을 찾기 위해 대규모 이산 탐색 공간을 효율적으로 탐색하는 데 어려움을 겪습니다.

2. 방법론: FMQA 알고리즘

이 논문은 FMQA (Factorization Machine with Quadratic-optimization Annealing) 알고리즘을 제안합니다. 이 접근법은 특정 머신러닝 대리 모델과 Ising 기계 (IMs) 를 결합하여 획득 함수 최적화를 효율적으로 해결합니다.

A. 대리 모델: 팩토라이제이션 머신 (FM)

FMQA 는 가우시안 프로세스 대신 **팩토라이제이션 머신 (FM)**을 대리 모델로 사용합니다.

• 구조: FM 은 출력 $\bar{y}(x)$를 선형 항과 쌍별 상호작용 항의 합으로 모델링합니다:
  $$\bar{y}(x) = w_0 + \sum w_i x_i + \sum \sum \langle v_i, v_j \rangle x_i x_j$$
• 장점: FM 은 **Quadratic Unconstrained Binary Optimization (QUBO)**모델 (또는 Ising Hamiltonian) 로 직접 변환될 수 있습니다. 이를 통해 대리 모델 자체를 IM 을 사용하여 최적화 문제로 풀 수 있습니다.
• 학습: FM 은 $N$을 특성 수, $K$를 잠재 차원이라고 할 때 선형 복잡도 $O(NK)$로 경사 하강법을 사용하여 효율적으로 학습됩니다.

B. 최적화 엔진: Ising 기계 (IMs)

핵심 혁신은 FM 의 획득 함수 (또는 음수 예측값) 를 최대화하는 입력 $x$를 찾기 위해 IM 을 사용하는 것입니다.

• 하드웨어/소프트웨어: 이 알고리즘은 특정 IM 에 구애받지 않습니다. 다음을 지원합니다:
  • 양자 어닐러: 예: D-Wave 시스템.
  • 디지털 어닐러: 예: Fujitsu Digital Annealer.
  • 시뮬레이션 어닐링 엔진: 예: Fixstars Amplify Annealing Engine (GPU 기반).
• 프로세스: FM 을 QUBO 로 변환 $\rightarrow$ IM 으로 최적 이진 벡터 탐색 $\rightarrow$ 원래 입력 공간으로 디코딩.

C. 비이진 입력 처리 (인코딩 전략)

IM 이 이진 변수로 작동하므로, 논문은 일반적인 최적화 문제를 위한 인코딩 방법을 상세히 설명합니다:

1. 이진 변수: 직접 매핑 (인코딩 불필요).
2. 정수 변수:
   • 이진 인코딩: 정수를 2 의 거듭제곱의 합으로 표현.
   • One-Hot 인코딩: 정수를 $N$비트 중 단일 '1'로 표현 (제약 조건 $\sum x_i = 1$ 필요).
   • Domain-Wall 인코딩: One-Hot 에 비해 비트 수를 줄이는 더 효율적인 정수 인코딩.
3. 복잡한 구조 (그래프, 문자열, 이미지):
   • **Binary Variational Autoencoder (bVAE)**를 사용합니다.
   • bVAE 는 분자 SMILES 문자열, 이미지와 같은 복잡한 입력을 이진 변수의 잠재 공간으로 인코딩합니다.
   • FM 은 이 잠재 공간에서 학습됩니다. IM 은 잠재 이진 벡터를 최적화한 후, 이를 원래 구조로 디코딩합니다.

3. 주요 기여

1. 알고리즘적 프레임워크: QUBO 호환성 있는 FM 대리 모델을 통해 BBO 와 조합 최적화 하드웨어 (IMs) 를 연결하는 FMQA 알고리즘을 공식화했습니다.
2. 확장성: 획득 함수 최적화의 어려움으로 인해 기존 BO 가 실패하는 대규모 이산 최적화 문제 (수천 비트까지) 를 FMQA 가 처리할 수 있음을 보였습니다.
3. 소프트웨어 생태계: 기술을 민주화하기 위한 오픈소스 도구를 도입했습니다:
   • Original FMQA Package: 기본 구현을 위한 Python 라이브러리.
   • Amplify-BBOpt: Fixstars Amplify SDK 와 통합된 전용 라이브러리로, 사용자가 수동 QUBO 공식화 없이 연속 변수와 제약 조건 (예: one-hot) 을 정의할 수 있게 합니다.
4. 종합적 벤치마킹: 단순 이진 문제를 넘어 다양한 분야에서 접근법의 타당성을 검증하여 그 다용도성을 입증했습니다.

4. 결과 및 적용 사례

이 논문은 물리학, 화학, 재료 과학, 사회 과학 전반에 걸친 성공적인 적용 사례를 검토합니다:

• 제약 조건이 없는 이진 최적화:

  • 메타물질 설계: D-Wave 2000Q 를 사용하여 복사 냉각 구조 (24-60 비트) 를 최적화하여 무작위 탐색보다 우수한 구조를 더 빠르게 발견했습니다.
  • 층상 재료: 고성능 투명 복사 냉각 필름 (최대 48 비트) 과 광각 스펙트럼 필터를 설계하여 기록적인 성능을 가진 10 층 재료를 성공적으로 제작했습니다.
  • 고분자 설계: 열전도도를 위한 3 블록 공중합체를 최적화했습니다.
  • 특성 선택: 고분자 기계적 특성 예측을 위한 최적 특성 부분집합을 선택하여 LASSO 보다 우수한 성능을 보였습니다.

• 제약 조건이 있는 이진 최적화:

  • 자기 터널 접합 (MTJ): QUBO 에 페널티 항을 사용하여 특정 이온 수에 대한 엄격한 제약 (예: 정확히 5 개의 Mg 과 5 개의 Ge) 하에 원자 배열을 최적화했습니다.
  • 분자 구성: 극성화도를 위한 페릴렌 분자의 원자 구성을 최적화했습니다.
  • 공명 회피: 회로 기판의 마운팅 홀 위치를 최적화하여 고유 진동수를 최대화했습니다.

• 정수 변수 문제:

  • 포토닉 크리스탈 레이저: 출력 전력 및 빔 품질을 위해 연속 구조 파라미터 (44 비트로 이산화) 를 최적화하여 입자 군집 최적화 (PSO) 와 유전 알고리즘 (GA) 보다 우수한 성능을 보였습니다.
  • 날개 모양 최적화: 양력 - 항력 비율을 최대화하기 위해 익형 모양 (100 비트) 을 최적화하여 무작위 탐색 대비 17% 개선 효과를 달성했습니다.
  • 교통 신호 제어: 도시 시뮬레이션에서 평균 차량 속도를 최대화하기 위해 960 개의 이진 변수 (16 개의 교차로 표현) 를 최적화했습니다.
  • 차체 설계: 18 개의 제약 조건이 있는 차량 구조에 대한 다목적 벤치마크를 해결하여 NSGA-II 보다 적은 함수 평가 (900 대 30,000) 로 더 나은 파레토 해를 달성했습니다.

• 복잡한 구조 (bVAE):

  • 열 방출기: 500 비트 잠재 공간을 사용하여 열광전지를 위한 2 차원 토폴로지 모양을 최적화했습니다.
  • 분자 설계: 300 비트 잠재 공간을 사용하여 약물 유사 분자 (SMILES 문자열) 의 여러 특성 (LogP, QED 등) 을 최적화했습니다.
  • 펩타이드 설계: 항균 및 비용혈성 펩타이드에 대한 다목적 최적화를 수행하여 두 가지 새로운 펩타이드를 성공적으로 합성 및 검증했습니다.

5. 중요성 및 전망

• IM 의 핵심 기술: 이 논문은 FMQA 를 Ising 기계의 "킬러 애플리케이션"으로 위치시켜, 이전에 해결하기 어려웠던 실제 BBO 문제를 해결하는 실용적인 엔드 - 투 - 엔드 워크플로우를 제공합니다.
• 속도 및 효율성: 획득 함수 최적화를 전용 하드웨어 (IMs) 에 위임함으로써, 이산 공간에서 전역 최적점을 찾는 데 필요한 계산 시간을 크게 단축합니다.
• 미래 방향:
  • 양자 우위: 현재는 양자 어닐러와 디지털 어닐러를 사용하지만, 큐비트 수가 증가함에 따라 게이트 기반 양자 컴퓨터 (QAOA 사용) 에도 프레임워크가 준비되어 있습니다.
  • 자율 실험실: 저자들은 FMQA 를 자동화된 실험 시스템과 통합하여 재료 발견 및 신약 개발을 가속화할 것을 제안합니다.
  • 확장성: 향후 연구는 더 큰 배치 크기를 처리하고 예측 정확도 및 IM 성능을 더욱 향상시키기 위해 고차 대리 모델 (HUBO) 을 개발하는 것을 목표로 합니다.

결론적으로, 이 논문은 머신러닝 대리 모델링과 조합 최적화 하드웨어 간의 간극을 효과적으로 연결하는 강력하고 다용도이며 매우 효율적인 블랙박스 최적화 프레임워크로 FMQA 를 확립합니다.