Performance-Driven QUBO for Recommender Systems on Quantum Annealers

"양자 어닐러를 위한 추천 시스템용 성능 주도 QUBO" 논문에 대한 상세한 기술 요약은 다음과 같습니다.

1. 문제 제기

추천 시스템은 방대한 수의 아이템 특성으로 인해 차원의 저주에 시달리는 경우가 많아, 중복성 증가, 저장 비용 상승, 검색 효율성 저하를 초래합니다. 특성 선택은 중요하지만, 기존 방법들은 최종 추천 성능 (예: nDCG 와 같은 순위 지표) 을 명시적으로 최적화하지 못하는 경우가 많습니다.

특성 선택을 위한 기존 양자 어닐링 (QA) 접근 방식은 문제를 2 차 무제약 이진 최적화 (QUBO) 로 공식화하지만, 두 가지 주요 한계에 직면해 있습니다:

1. 정렬되지 않은 목적 함수: 현재 QUBO 기반 방법들 (예: MIQUBO, CoQUBO) 은 통계적 의존성 (상호 정보, 상관관계) 이나 모델 출력에 기반하여 계수 행렬 $Q$를 구성할 뿐, 추천 성능 지표에 대한 직접적인 영향을 고려하지 않습니다.
2. 불안정성: 실제 하드웨어 (NISQ 시대) 에서의 양자 어닐러 성능은 문제 크기, 샘플 수, 문제 난이도에 민감하여 일관되지 않은 결과를 초래합니다.

저자들은 다음과 같은 세 가지 핵심 연구 질문을 제기합니다:

• 양자 어닐러의 불안정성이 추천 시스템 성능에 어떤 영향을 미치는가?
• 이 분야에서 특성 선택을 위한 양자 어닐러의 효과는 어떠한가?
• 양자 하드웨어 기반의 QUBO 기반 방법이 기존 클래식 특성 선택 기준을 능가하거나 맞먹을 수 있는가?

2. 방법론: PDQUBO

저자들은 PDQUBO(성능 주도 2 차 무제약 이진 최적화) 를 제안합니다. 이는 반사실적 분석을 통해 QUBO 최적화 목적 함수를 하류 추천 성능과 직접적으로 정렬시키는 새로운 프레임워크입니다.

핵심 워크플로우

1. 기본 모델 학습: 추천 모델 ($G_\Theta$) 을 전체 특성 집합 $F$로 학습합니다.
2. 반사실적 분석: 이 방법은 "반사실적 인스턴스"를 생성하여 특성의 영향을 평가합니다. 입력에서 개별 특성 ($f_i$) 과 특성 쌍 ($f_i, f_j$) 을 체계적으로 마스킹 (제거) 하고 평가 지표 (예: nDCG) 의 변화를 측정합니다.
   • $E_i$: $f_i$가 제거되었을 때의 성능 하락.
   • $E_{ij}$: $f_i$와 $f_j$가 모두 제거되었을 때의 성능 하락.
   • 참고: 양의 $E$는 해당 특성이 중요함 (제거 시 성능 하락) 을 나타내며, 음의 $E$는 해당 특성이 중복되거나 해롭음을 시사합니다.
3. QUBO 공식화: 반사실적 값을 사용하여 QUBO 계수 행렬 $Q$를 구성합니다:
   • 대각선 요소 ($Q_{ii}$): $-E_i$로 설정 (개별 특성 중요도 표현).
   • 비대각선 요소 ($Q_{ij}$): $-E_{ij}$로 설정 (특성 쌍 상호작용 표현).
   • 목적 함수는 $Y = x^T Q x$ 에 해당하는 에너지를 최소화하며, 여기서 $x$는 특성 선택을 나타내는 이진 벡터입니다. $Y$를 최소화하는 것은 추천 성능을 극대화하는 특성을 선택하는 것과 동일합니다.
4. 최적화: 구성된 QUBO 문제는 클래식 솔버 (시뮬레이션 어닐링, 탭루 검색) 또는 양자 어닐러 (D-Wave) 를 사용하여 해결합니다.
5. 재학습: 선택된 특성 부분 집합을 사용하여 기본 모델을 재학습하여 최종 평가를 수행합니다.

주요 차이점

• 모델 무관성: PDQUBO 는 KNN, MLP, NCF 등 어떤 기본 모델이든 그리고 어떤 지표든 작동합니다.
• 상호작용 인식: 특성을 독립적으로 취급하는 "필터" 방법과 달리, PDQUBO 는 $Q$의 2 차 항을 통해 명시적으로 쌍별 상호작용을 모델링합니다.

3. 주요 기여

1. PDQUBO 프레임워크: 반사실적 분석을 통해 특성 선택과 추천 성능을 명시적으로 연결하는 새로운 QUBO 공식화로, 최적화 방향이 통계적 기반이 아닌 성능 주도임을 보장합니다.
2. 포괄적 안정성 분석: 실제 양자 어닐러의 불안정성에 대한 상세한 조사로, 다음에 따라 솔루션 품질이 어떻게 변하는지 분석합니다:
   • 문제 크기 (특성 수).
   • 샘플 크기 (어닐링 실행 수).
   • 문제 난이도 (데이터 희소성).
3. 실증적 검증: CLEF 2024 QuantumCLEF 데이터셋, KuaiRec, KuaiRand, Avazu, Criteo 등 실제 데이터셋을 통한 광범위한 실험으로, PDQUBO 가 기존 QUBO 기준을 능가하고 최첨단 클래식 특성 선택 방법과 경쟁함을 입증했습니다.
4. 확장성 통찰: 계산 비용에 대한 분석과 전체 QUBO 행렬 구성의 $O(|F|^2)$ 복잡도를 완화하기 위한 제안된 2 단계 가지치기 전략을 제시했으나, 논문은 최적 성능을 위해서는 완전한 2 차 공식화가 필요하다고 결론 내립니다.

4. 실험 결과

저자들은 다양한 데이터셋과 모델에 대해 PDQUBO 를 기준 (CQFS, MIQUBO, CoQUBO, QUBO-Boosting) 과 클래식 방법 (Lasso, GBDT, 순열 중요도) 과 비교 평가했습니다.

• 기준 대비 성능:

  • PDQUBO 는 150_ICM 및 500_ICM 데이터셋의 대부분의 구성에서 최고 또는 2 위 nDCG@10 점수를 일관되게 달성했습니다.
  • CTR 예측 작업 (Avazu, Criteo) 에서 PDQUBO-Hybrid(하이브리드 양자 - 클래식 솔버 사용) 는 클래식 기준 및 기타 QUBO 변형보다 높은 AUC 점수를 기록했습니다.
  • PDQUBO 는 MIQUBO 와 같은 기타 QUBO 방법보다 현저히 우수한 성과를 보였으며, 이는 통계적 의존성 구성보다 성능 주도 구성이 우월함을 입증했습니다.

• 안정성 발견:

  • 문제 크기: 하드웨어의 논리적 큐비트 용량을 초과하는 특성 수가 증가함에 따라 양자 어닐링 (QA) 결과는 불안정해지는 반면, 클래식 솔버 (SA, TS) 는 안정적으로 유지됩니다.
  • 샘플 크기: QA 샘플 수를 늘리면 에너지 분산이 크게 줄어들고 하류 성능이 향상되어, NISQ 장치에서 충분한 샘플링의 필요성을 강조합니다.
  • 난이도: QA 는 희소 (어려운) 데이터셋에서 더 크지만 변동성이 큰 성능 향상을 보이는 경향이 있습니다.

• 2 차 항의 필요성:

  • "Indiv"(대각선만) 와 "All"(전체 행렬) 을 비교한 실험 결과, 쌍별 상호작용 ($Q_{ij}$) 을 포함하는 것이 중요함이 확인되었습니다. "All" 접근 방식이 훨씬 더 나은 결과를 제공하여, 이 맥락에서 효과적인 선택을 위해 특성 상호작용이 필수적임을 입증했습니다.

• 효율성:

  • 클래식 솔버의 시간 복잡도는 문제 크기에 따라 기하급수적으로 증가하는 반면, 양자 어닐링 시간은 하드웨어 접근 및 샘플링 시간에 제한되어 상대적으로 일정하게 유지되므로, 하드웨어 제약이 극복되면 대규모 문제에 대해 잠재적인 속도 우위를 제공합니다.

5. 의의 및 향후 방향

• 격차 해소: 이 연구는 최적화 목적 함수가 비즈니스 지표 (추천 품질) 를 직접 목표로 함으로써 이론적 양자 최적화와 실제 추천 시스템 배포 간의 격차를 성공적으로 해소했습니다.
• 실용적 타당성: 결과는 현재의 NISQ 하드웨어 제한에도 불구하고, 하이브리드 양자 - 클래식 접근 방식이 성숙된 클래식 방법과 비교하여 경쟁력 있거나 우수한 특성 선택을 제공할 수 있음을 시사합니다.
• 향후 작업: 저자들은 PDQUBO 를 고차 특성 상호작용(쌍 이상) 으로 확장하고, 더 대규모이고 복잡한 특성 구조를 처리하기 위해 게이트 기반 양자 컴퓨터에서 변분 양자 알고리즘을 탐구할 것을 제안합니다.

결론적으로, PDQUBO 는 양자 컴퓨팅을 실제 세계 추천 과제에 적용하는 데 있어 중요한 진전을 나타내며, 성능 주도적이고 반사실적 기반의 QUBO 공식화가 고품질 특성 선택을 위해 양자 어닐러를 효과적으로 활용할 수 있음을 입증했습니다.