초록
커널 방법의 성공은 특히 구조화된 데이터를 위한 새로운 양의 반정부호 함수(positive semidefinite functions) 설계를 촉진시켰습니다. 이에 대한 선도적인 설계 패러다임은 컨볼루션 커널(convolution kernel)입니다. 컨볼루션 커널은 구조화된 객체를 그 부분들로 분해하고 모든 부분 쌍에 대해 합을 구합니다. 반면, 할당 커널(assignment kernels)은 부분들 사이의 최적 일대일 대응(optimal bijection)에서 얻어지며, 이는 유사성의 더 유효한 개념을 제공할 수 있습니다. 그러나 일반적으로 최적 할당은 부정부호 함수(indefinite functions)를 생성하여 커널 방법에서의 사용을 복잡하게 만듭니다. 우리는 부분들을 비교하기 위해 사용되는 기저 커널(base kernels)의 클래스를 특징화하여 양의 반정부호 최적 할당 커널을 보장합니다. 이러한 기저 커널들은 히스토그램 교차(histogram intersection)를 통해 선형 시간 내에 계산되는 계층구조(hierarchies)를 형성합니다. 우리는 이러한 결과를 그래프용 Weisfeiler-Lehman 최적 할당 커널(Weisfeiler-Lehman optimal assignment kernel) 개발에 적용하였습니다. 이 커널은 널리 사용되는 벤치마크 데이터 세트에서 높은 분류 정확도를 제공하며, 원래의 Weisfeiler-Lehman 커널보다 개선되었습니다.