초록
그래프 비율 컷( ratio-cut) 최적화를 위한 새로운 접근법을 제안한다. 이 방법은 이진 할당을 확률변수로 모델링함으로써, 할당 변수의 파라미터를 온라인 환경에서 학습할 수 있도록, 기대 비율 컷에 대한 상한을 제시하고, 그 그래디언트에 대한 편향 없는 추정량을 제공한다. 제안하는 확률적 접근법(PRCut)을 통해 도출된 클러스터링은 조합 최적화 문제의 레이일리 몫( Rayleigh quotient) 근사화, 온라인 학습 확장 방식, 그리고 다양한 널리 사용되는 기법들을 모두 능가한다. 또한 PRCut 클러스터링이 유사도 측도와 매우 잘 일치하며, 레이블 기반 유사도가 제공되는 경우 지도 학습 분류기와 비슷한 성능을 달성할 수 있음을 입증한다. 본 연구에서 제안하는 이 새로운 접근법은 사전 학습된 자기지도 학습(self-supervised) 표현을 즉시 활용하여 경쟁력 있는 성능을 달성할 수 있으며, 이러한 표현의 품질을 평가하는 평가 방법으로도 활용될 수 있다.