• 목록

[일시] 2026.02.23.

[리뷰 논문] Bayesian Optimization over Permutation Spaces

[요약]
본 발표는 순열 공간 상에서의 Bayesian Optimization 을 활용하여 최적 해를 찾아내는 알고리즘인 BOPS 를 제안한다. 특히 근사 가능한 해를 구할 수 있는 Kendall kernel을 적용한 BOPS-T 알고리즘과 순열 공간에 대한 표현력을 극대화하는 Mallow kernel을 적용한 BOPS-H 알고리즘으로 제안하였다. 기존의 연구에서는 순열 공간 자체의 비가환적 특징을 반영할 수 없다는 문제점에 대해서 각 커널에 대한 적용 및 제약식의 적용을 통해서 해결하고자 하는 노력을 보였다. 특히 Kendall kernel을 적용한 BOPS-T 알고리즘에서는 acquisition function으로 Thompson sampling을 적용하여 가중치 공간에서의 표현을 가능하게 하였고, 이를 Clique 기반의 SDP 완화로 연산의 효율성을 개선하고자 하는 증명을 선보였다. 하지만 실제 실험 결과에서는 순열 공간의 특징을 잘 표현할 수 있는 Mallow Kernel을 적용했을 때에 실제로 거의 대부분의 경우에서 우수한 성능을 보이는 것을 확인할 수 있었다.

[Q&A]
- 각 알고리즘에서 적용된 Mallow kernel, Kendall kernel, 그리고 Diffusion kernel의 차이점이 궁금합니다.
: Kendall kernel의 경우 두 순열 간의 쌍에 대한 상대적 순서를 보기 위해 kendall tau 거리에 기반해 사용되었다. 그에 반해 Mallow kernel의 경우에는 중심 순열로부터의 거리를 기반으로 하는 확률 분포 모델을 커널화한다. 이는 Kendall kernel과 유사하지만,  mallow kernel은 distance measure가 다양하게 적용될 수 있다는 차이점을 갖는다. 마지막으로 Diffusion kernel의 경우 순열 공간을 하나의 그래프로 보는 관점에서의 그래프 이론에서의 확산 방정식을 적용하게 된다. 순열의 기하학적 구조를 반영할 수 있는 특징을 갖지만 계산 복잡도가 높다는 단점이 존재한다.

- Thompson Sampling이 본 연구의 문제 상황에서 적절한 sampling 기법인지, 문제 상황이 충분히 큰 상황에 적절한 sampling 기법이 무엇일지 궁금합니다.
: 일반적인 continuous 공간에 비해 순열 공간이 복잡한 특징에 대해서 적절히 동작할 수 있는 sampling 기법이라고 볼 수 있다. Thompson sampling을 사용하게 될 경우 모델의 불확실성이 높은 영역을 자연스럽게 탐색할 수 있기 때문에 최적화에 사용될 수 있다고 볼 수 있다. 거대한 순열 탐색 공간에서 발생하는 계산 복잡도를 제어하고 수렴을 보장할 수 있는 기법으로 활용되었다.


[녹화 영상 링크]
https://us06web.zoom.us/rec/share/y8jKM0x0cXl4v_yAS3HLDsqh34ywWt9HHShZ8Rn5m75HAmaWZ1Dqr7CrNPbND5BM.l2uZxV2_a7CMP69d