In this paper, we present the systems that the Natural Language Engineering and Pattern Recognition group (ELiRF) has submitted to the MediaEval 2015 Query by Example Search on Speech Task. All of them are based on a Subsequence Dynamic Time Warping algorithm. The systems use information from outside the task (low-resources systems).
In this paper, we present the two systems that we have submitted to the MediaEval 2015 Query by Example Search on Speech Task [7]. Both systems are based on a Subsequence Dynamic Time Warping (S-DTW) algorithm [2]. However, they di er in the way the minimization process is performed. In the rst system the minimization is computed directly on the accumulated distances, while in the second system the average distances are considered. In the following sections, we will explain how the feature vectors are computed for each system, the di erences in the search algorithm, the scoring system and the results obtained in this evaluation.
Both of our systems use the same philosophy. The rst step was to preprocess all the audio les, both spoken documents and queries, using a phoneme recognizer. This way a sequence of feature vectors based on posteriorgrams was obtained as a representation of each audio le [3, 5]. Then, we took each possible pair (document, query ) and run a SDTW algorithm on them. This provided the bounds of a possible detection of the query within the document, and a score for this detection. After that, a decision-making module established a threshold based on the scores of all the possible detections. This was necessary in order to only accept the detections with the highest con dences. Finally, a fusion module used the scores obtained from three systems based on three di erent languages and mixed them in order to achieve better results.
4.
The search algorithm we used is based on Dynamic Programming (DP). In particular, we used S-DTW, which is a DP technique for comparing two sequences of objects. In our case, one of the sequences corresponded to feature vectors of one of the audio documents, and the other one represented a query. The S-DTW method found multiple local alignments of the query within an audio document, by allowing it to start at any position of the audio document. Equation 1 shows the generic formulation of S-DTW:
M (i; j) = 8+1 > > >><+1
0 > >>> min :8(x;y)2S
M (i
x; j
y) + D(Ai; Bj ) j
1
(
In our systems the set of allowed movements S was f(
The second system (SDTW-avg) is based on a variation on the minimization process which takes into account the number of steps the S-DTW algorithm does [4]. This way, a local minimization is performed on the average distances, by keeping track of the total distance and the number of steps. This method was also run separately for each of the three languages.
Once the search algorithm had found the best alignment for each possible pair (document, query ), the distance values were used to determine the scores. The score must indicate how likely it is that a query appears in a document. For this reason, the minus distance was used as score (a smaller distance indicates then a better score). For each query a di erent threshold based on the n-best matches among all the documents is used. The selected pairs go then through a score normalization process, so the scores regarding each query have zero-mean and unit-variance. A default score is assigned to the pairs that are not selected.
Previous works such as [1] have shown that a proper combination of systems leads to better results. In our case a combination of the systems that used each of the three languages is performed. However, our combination is not as elaborated as the one from that work. Our combination system was to keep for each pair (document, query ) the maximum score among the three considered languages. Then, a threshold is calculated for the hard decision (YES/NO), used for the Term Weighted Value metric. This threshold was a close value to the one calculated by the scoring tool for the Maximum Term Weighted Value with the development set. This fusion by language was performed in both of our systems.
We performed several preliminary experiments in order to nd the best con guration for our systems. For example, we evaluated di erent distance functions for the search algorithm. One of them was the Kullback-Leibler divergence, since the audios were represented as sequences of probability vectors. We also tried the cosine distance. Finally, we used the dot product, since it provided the best results for the development set.
For this MediaEval 2015 Query by Example Search on Speech Evaluation, we submitted one run for each of the systems described above. The results we obtained are shown in Tables 1 and 2. The measure to be optimized for this Evaluation was the Normalized Cross Entropy Score (Cnxe). However, other measures such as the Maximum and the Actual Term Weighted Values (MTWV and ATWV, respectively) were considered as secondary metrics. In these tables SDTW stands for the system where the minimization was based on the distance, and SDTW-avg stands for the system where the minimization was based on the average distance. The gures that are shown in the tables reveal better results if the minimization is performed using the average distance rather than if the total distance is used.
The results shown in Tables 3 and 4 are separated by query type. Our approach obtains better results with query type T1 (exact match), since it does not naturally consider the word level reorderings or possible ller items from query types T2 (with small variations and word level reorderings) and T3 (split with llers).
These systems use our own multi-thread implementation of the S-DTW algorithm. We used a PC with an Intelr Xeonr @ 3.70 GHz with 12 threads and 64 GB of RAM on a Linux operating system. At the preprocessing stage, we achieved an indexing speed factor of 0:40, and our memory peak was lower than 0:1 GB. At the search stage, our searching speed factor was 3:11 and the memory peak was above 13 GB. Thus, our processing load for both systems was 37:29. 7.
In this paper, we have presented the systems we have submitted to the MediaEval 2015 Query by Example Search on Speech Evaluation, as well as the results obtained. This was a very challenging task in which not only exact occurrences of the queries, but also with lexical variations, word level reorderings or queries that were split and had llers in between had to be found. Our approach o ers better results where an exact match is searched, as they are more natural to our search algorithm. We have also tried a variation on the standard S-DTW algorithm which considers the average distance instead of the raw sum of distances. This variation led to better results on the test set.
As future work, we would like to improve our system in order to better handle the word reorderings, as well as queries that are not represented as a consecutive piece of audio.
This work is funded by the Spanish Government and the E.U. under contract TIN2014-54288-C4-3-R and FPU Grant AP2010-4193.