- 최적의 sparse binary hash code 를 찾는 combinatorial optimization 문제와 minimum-cost flow 문제와의 동치관계 증명

- 정확도 손실없이 478배의 retrieval 검색 속도 향상

- 머신러닝 분야 최고 학회 ICML 논문 게재

송현오 교수 연구진은 빠르고 정확한 데이터 검색을 가능하게 하는 binary representation 을 딥러닝 네트워크를 이용해 얻는 최적화 알고리즘을 고안했다고 밝혔다. 실제 산업에서는 (예: 구글 이미지 검색) 데이터 검색을 위해 딥러닝 네트워크로 representation 을 먼저 얻은 다음 vector quantization 같은 미분 불가능한 이진화 (binarization) 후처리 과정을 통해 더 검색 속도 효율이 높은 binary representation 을 계산해 사용한다. 이 과정에서 딥러닝 네트워크로 얻은 representation 의 정확도 손실이 발생하게 된다.

이러한 문제를 해결하기 위해 송 교수 연구팀(정연우 석박통합과정)은 [그림1]에서의 수식처럼 데이터 유사도 정보를 잘 표현하며 동시에 sparse 한 binary hash code 를 학습할 수 있는 최적화 알고리즘을 고안했다. 이 알고리즘은 최적의 sparse binary hash code 를 찾는 단계와 그 코드를 바탕으로 딥러닝 기반 거리 학습을 통한 거리 학습 단계로 나누어 단계적으로 최적화 한다.

또한 최적의 sparse binary hash code 를 찾는 combinatorial optimization 문제는 [그림2] 에서처럼 그래프 문제 중 하나인 minimum-cost flow 문제와의 동치관계에 있고 polynomial time 내에 최적해를 찾을 수 있음을 증명했다 (논문의 정리1 참조).

연구진은 이러한 최적화된 sparse binary hash code 를 이용해 해시테이블을 생성할 수 있고 머신러닝 벤치마크 데이터셋인 Cifar-100 와 ImageNet 에서 각각 98 배와 478 배의 검색 속도의 향상이 있었으며 정확도 또한 상승함을 보였다.

송 교수 연구팀의 이번 연구(Efficient end-to-end learning for quantizable representation)는 머신러닝 분야 최고 학회 중 하나인 ICML18 에 7월에 게재되었고 selected long oral presentation paper 로 선정되었다.

그리고 송 교수의 머신러닝 연구실 (https://mllab.snu.ac.kr) 에서는 수학 및 알고리즘적 사고력이 우수하고 머신러닝 연구에 관심이 있는 학생들을 석박통합과정으로 모집 중이다.

논문 preprint 링크: https://arxiv.org/abs/1805.05809
Github source code 링크: https://github.com/maestrojeong/Deep-Hash-Table-ICML18

https://cse.snu.ac.kr/sites/default/files/node--notice/1.%EA%B7%B8%EB%A6%BC_1.png

▲ [그림1] 이미지 유사도 정보를 나타내며 동시에 sparse한 해시 코드를 학습할 수 있는 최적화 문제

https://cse.snu.ac.kr/sites/default/files/node--notice/2.%EA%B7%B8%EB%A6%BC_2.png

▲ [그림 2] 최적의 sparse한 이진 해시 코드 구하는 문제와 동치인 min-cost flow 문제의 그래프