This thesis considers two distance metric learning algorithms for a fingerprinting system, which identifies a query content by finding the fingerprint in the database (DB) that measures the shortest distance to the query fingerprint. The algorithms produce a metric which improves the identification performance of the fingerprinting system for a given fingerprint DB and a set of distortions which may not have been considered when initially designing the fingerprint. In the algorithms, with a given training data set consisting of the fingerprint of the distorted and the original contents, a distance metric is learned. The first distance metric learning algorithm learns a distance metric which is parameterized by a linear projection matrix. For a given training data set consisting of original and distorted fingerprints, a distance metric equivalent to the $\It{l_p}$ norm of the difference between two linearly projected fingerprints is learned by minimizing the false positive rate (probability of perceptually dissimilar content to be identified as being similar) for a given false negative rate (probability of perceptually similar content to be identified as being dissimilar).
The second distance metric learning algorithm learns a boosted distance metric which is obtained by combining various base distance metrics where the base distance metrics and the combining rule are determined by the distance metric learning algorithm. The boosted distance metric can obtain the trade-off relation between identification performance and execution time of fingerprinting system. In our experiment, the distance metric learning is applied to both audio and video fingerprinting systems. It is experimentally shown that the distance metrics learned by both distance metric learning algorithms can improve the identification performance of the fingerprinting system. It is also shown that the distance metric learned by the first distance metric learning algorithm performed better than that learned by well-known distance metric learning algorithms for classification and that the boosted metric can obtain a trade-off relation between the execution time and the identification performance.
본 학위논문에서는 핑거프린팅 시스템 (fingerprinting system) 의 성능 향상을 위한 두 가지의 거리 함수 학습 알고리즘 (distance metric learning algorithm) 을 제안한다. 핑거프린팅 시스템은 쿼리 (query) 로 입력된 콘텐츠 (content)의 핑거프린트 (fingerprint) 를 미리 구축한 데이터베이스 (database, DB) 상에서 검색함으로써 입력 콘텐츠를 식별하는 시스템이다. 제안하는 알고리즘은 핑거프린트와 핑거프린팅 시스템에 가해지는 왜곡이 주어졌을 경우에 핑거프린팅 시스템의 성능을 향상시킬 수 있는 거리 함수를 구한다. 이 때, 왜곡은 핑거프린팅 시스템을 개발할 당시에 고려되지 않는 것일 수도 있다. 제안하는 알고리즘에서는 원본 콘텐츠와 왜곡된 콘텐츠의 핑거프린트를 가지는 훈련 데이터로부터 거리 함수를 학습한다. 제안하는 첫 번째 거리 함수 학습 알고리즘은 선형 투영 (linear projection) 매트릭스를 파라미터로 가지는 거리 함수를 학습한다. 주어진 훈련 데이터에 대해서, 선형 투영된 두 핑거프린트 차의 $\It{l_p}$ 놈 ($\It{l_p}$ norm)의 형태를 가지는 거리 함수를 주어진 거짓 부정 (false negative)에 대해서 거짓 긍정 (false positive)을 최소화시키도록 학습한다. 이 때, 거짓 부정은 서로 비슷한 두 개의 콘텐츠가 다르다고 판단되는 확률, 거짓 긍정은 서로 다른 두 개의 콘텐츠가 같다고 판단되는 확률을 나타낸다. 제안하는 두 번째 거리 함수 학습 알고리즘은 여러 기본 거리 함수를 결합시켜서 하나의 부스티드 (boosted) 거리 함수를 학습한다. 기본 거리 함수와 결합 방법은 거리 함수 학습 알고리즘에 의해서 결정된다. 부스티드 거리 함수는 핑거프린팅 시스템의 식별 성능과 수행 시간 사이의 트레이트 오프 (trade-off) 관계를 조절할 수 있다. 두 가지 거리 함수 학습 알고리즘을 각각 오디오 핑거프린팅 시스템과 비디오 핑거프린팅 시스템에 적용하여 실험하였다. 실험을 통해서 두 거리 함수 학습 알고리즘을 통해서 얻어진 거리 함수가 주어진 시스템의 식별 성능을 향상시킬 수 있음을 보였다. 또한, 첫 번째 거리 함수 학습 알고리즘에 의해서 학습된 거리 함수는 기존에 분류를 위해 제안되었던 다른 거리 함수 학습 알고리즘에 의해서 학습된 거리 함수보다 나은 성능을 보여주였다. 두 번째 거리 함수 학습 알고리즘에 의해서 학습된 거리 함수는 식별 성능과 수행 시간 사이의 트레이드 오프 관계를 조절할 수 있음을 실험을 통해서 보였다.
