Defying Boundaries - Diffusion Models in Combinatorial Optimization
- 2025년 1월 10일 오전 5:08
- 조회수: 72
REFERENCES
INFORMATION
- 2025년 1월 10일
- 오전 12시 ~
온라인 비디오 시청 (YouTube)
발표자:
차민성
차민성
TOPIC
Defying Boundaries - Diffusion Models in Combinatorial Optimization
On-Line Video
OVERVIEW
Diffusion Model은 Continuous Data에 기반하여 점진적으로 노이즈를 추가하고 이를 복원하는 과정을 통해 데이터 분포를 효과적으로 학습하며, 고품질 이미지 생성에서 독보적인 성과를 보여주고 있다. 이러한 모델의 가능성은 이미지 생성에만 국한되지 않으며, 최근에는 시계열 보간 및 예측 등의 분야에 대한 적용 가능성이 연구되고 있다. 특히, Diffusion Model은 조합 최적화(Combinatorial Optimization)와 같은 복잡한 문제에서도 새로운 해결 방안을 제시하고 있다.
조합 최적화 문제는 해 공간이 방대하고 연산량이 커 확장성의 한계가 명확하다. 이를 해결하기 위해 기존에는 다양한 휴리스틱 및 강화 학습 기반 기법이 연구되었지만, 다중 모드 분포 표현의 한계와 비효율적인 학습 구조로 인해 개선의 여지가 많았다.
Discrete Diffusion Model은 Continuous Diffusion Model의 개념을 확장하여, 이산적 데이터의 구조를 이해하고 활용함으로써 복잡한 문제를 점진적으로 정교화하며 높은 품질의 해를 생성한다. 본 세미나에서 소개하는 방법론, DIFUSCO는 이러한 Discrete Diffusion Model의 원리를 활용해 조합 최적화 문제를 효과적으로 해결할 수 있는 새로운 프레임워크를 제안하며, 특히 조합최적화 문제의 대표적인 예시인 외판원(Traveling Salesman Problem) 문제와 최대 독립 집합(Maximum Independent Set) 문제에서 유망한 결과를 보여주고 있다.
본 세미나에서는 DIFUSCO 방법론이 조합 최적화 문제를 해결하는 방식과 기존 기법에 대비하여 갖는 장점에 대해 논한다.
참고자료:
[1] Sun, Z., & Yang, Y. (2023). Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 3706-3731.
[2] Ho, J., Jain, A., & Abbeel, P. (2020). Denoising diffusion probabilistic models. Advances in neural information processing systems, 33, 6840-6851.
[3] Austin, J., Johnson, D. D., Ho, J., Tarlow, D., & Van Den Berg, R. (2021). Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34, 17981-17993.