페이스북에서 대용량 벡터의 유사도 검색을 위한 오픈소스 faiss를 깃허브에 공개했습니다. faiss 는 일종의 성분 분해 알고리즘인 Product Quantization(PQ) 알고리즘을 GPU를 대상으로 구현하였고 ‘Optimized Product Quantization for Approximate Nearest Neighbor Search‘ 페이퍼를 바탕으로 하고 있습니다. SIFT 데이터셋을 사용하여 데이터가 10만개일 때는 쿼리 속도가 20µs로 종전의 최고 성능과 유사하지만 데이터가 10억개일 때는 17.7µs로 종전 최고 성능보다 8배 정도 빠르다고 합니다. 이 프레임워크는 C++로 작성되었으며 파이썬 인터페이스를 가지고 있습니다. 벡터로 표현된 어떤 대상에 대해서도 GPU를 사용한 빠른 검색이 가능합니다. faiss 코드 구현을 자세히 설명한 페이퍼는 ‘Billion-scale similarity search with GPUs‘(1702.08734)입니다. 이러다 GPU를 사용하는 데이터베이스도 나올지 모르겠네요.

공교롭게도 이와 거의 동시에 딥마인드(DeepMind)팀에서 또 다른 k-NN 알고리즘에 대한 페이퍼 ‘Learning Deep Nearest Neighbor Representations Using Differentiable Boundary Trees‘(1702.08833) 공개했습니다. 최근에 발표된 boundary forest 알고리즘을 응용하여 트리 노드의 판단을 위해 뉴럴 네트워크를 이용합니다. 바운더리 트리 각 노드에서 데이터를 새로운 표현으로 변환하여 예측에 활용하는데 이 변환함수를 뉴럴 네트워크를 사용하여 학습시킵니다. MNIST 데이터로 1.85% 에러율을 얻었습니다.

그리고 난징 대학교에서 공개한 다른 페이퍼 ‘Deep Forest: Towards An Alternative to Deep Neural Networks‘(1702.08835)도 트리 모델에 관한 것으로 많은 관심을 받고 있습니다. 이 페이퍼에서는 gcForest 라는 새로운 앙상블 방법을 뉴럴 네트워크 대안으로 제시하고 있습니다. 아마도 이렇게 트리 관련 이슈가 동시에 나오는 것이 우연은 아닐거라고 생각됩니다. 트리모델은 분석하기도 좋고 비교적 직관적이므로 앞으로도 뉴럴 네트워크 등과 혼합된 형태가 많이 연구될 것 같습니다.

(업데이트) 난징 대학의 페이퍼에 대해 논란이 많네요. 실험결과가 의심스럽다, 코드가 공개되어 있지 않다, 그리고 뉴럴 네트워크와 트리모델 중 어떤게 더 나은지 실랑이도 생기네요. 레딧과 해커뉴스 포스트를 참고하세요.