Year: 2021

Abstract:
Search over sequences is a fundamental problem. Very efficient solutions exist for text sequences, which are made up of discrete tokens chosen from a finite alphabet. Sequences, such as audio, video or sensor readings, are made up of continuous-valued samples with a large sampling rate, making similarity search inefficient. This paper proposes Wav2Tok, a deep sequence tokenizer that converts continuous-valued sequences to discrete tokens that are easier to retrieve via sequence queries. The only information available for training Wav2Tok is pairs of similar sequences, i.e., depending on how we form the pairs, the similarity semantics are learnt. Wav2Tok compresses the query and target sequences into short sequences of tokens that are faster to match. Experiments show consistent performance of Wav2Tok across various audio retrieval tasks, namely, music search (query by humming) and speech keyword search via audio query.

heading: 1 INTRODUCTION
text: Sequence Retrieval aims at retrieving sequences similar to a query sequence, with the constraint that an ordered alignment exists between the query and the target sequence. The examples include speech search, where the order of constituent units, such as phonemes, syllables or words, remains same; and music search – query by humming or query by example – where the order of constituent units, such as relative notes or phrases, remains same. Apart from audio, the problem also extends to tasks such as handwritten word search and gesture search. One can define similarity metrics over the sequences using Dynamic Time Warping (DTW) . But those can be very inefficient if the sequences are continuous valued and have high sampling rates, as in audio. Also, the high variability of query sequences makes the hand-made metrics cumbersome and ineffective . A more effective way of sequence retrieval is by mapping them to discrete tokens. For instance, for linguistic content based speech retrieval, audio is mapped to discrete linguistic tokens, such as phonemes, syllables or words, and search is performed over these tokens. For query-by-humming based music search, audio is mapped to discrete melody-related tokens, such as notes. For query-by-example based music search, audio is mapped to rule-based landmarks in spectrograms [Wang (2003)]. Hence, each problem uses a domain-specific hand-made mapping to tokens defined by a domain expert.
In this paper, we propose an audio tokenizer which maps the raw audio feature sequence to a sequence of tokens. The tokenizer is trained from pairs of query and target sequences, without any expert-defined tokens. The proposed algorithm makes use of the fact that relevant landmarks appear in the same order in both the query and the target sequences. This reduces the dimensionality of data and preserves the information relevant for effective retrieval. Existing text search methods, namely, locally sensitive hashing, edit distance, etc., can then be used to query over these tokens.

heading: 2 RELATED WORK
text: Sequence Labelling. With expert-defined tokens, various methods are popularly used for mapping sequences to tokens. In conventional methods, Hidden Markov Models [Rabiner & Juang (1986)] and Conditional Random Fields [Lafferty et al. (2001)] have been popularly used for sequence labelling. These methods involve a significant amount of domain knowledge and many assumptions to make tractable models, which are avoided by End-to-End learning models such as Recurrent Neural Networks (RNNs) using Connectionist Temporal Classification framework [Graves et al. (2006)].
Sequence labeling can be used for sequence retrieval by converting the sequences to tokens, which are easy to search over. But this approach inevitably depends upon expert-defined tokens.
Unsupervised Speech Recognition. Modern Representation learning techniques such as Contrastive Predictive Coding (CPC) [van den Oord et al. (2018)] and Autoregressive Predictive Coding (APC) [Chung & Glass (2020)] are able to generate state-of-the-art continuous representations which encode the slowly varying phoneme features in raw speech. Wav2Vec [Schneider et al. (2019)] generated continuous representations with an encoder pretrained to distinguish future timesteps from a set of distractors sampled from a proposal distribution by optimizing a CPC-based contrastive loss. After pretraining the models, the representations are mapped to phoneme tokens via minimization of the Connectionist Temporal Classification (CTC) Loss [Graves et al. (2006)]. With inspiration from VQ-VAE [van den Oord et al. (2017)] which marked the beginning of generation of discrete representations, VQ-Wav2Vec [Baevski et al. (2019)] discretized the representations generated by Wav2Vec [Schneider et al. (2019)] with either a K-Means Vector Quantizer [Baevski et al. (2019)] or a Gumble-Softmax based Vector Quantizer [Baevski et al. (2019)] to generate quantized speech representation used to pretrain a BERT [Devlin et al. (2018)]. Wav2Vec 2.0 [Baevski et al. (2020)] discretized and masked the representations to solve a CPC-based contrastive task over the quantized representations which are learned jointly. VQ-APC [Chung et al. (2020)] discretized the representations to solve APC task over the quantized representations which are learned jointly. Note, the main motivation to discretize raw audio in a latent space for all aforementioned works are to explicitly control information content encoded in the representations rather than achieve sequence tokenization. The codes or tokens generated by the models aren’t constrained to be interpretable and hence initialised in large numbers. Performing CTC fine-tuning in essence groups codes in the vector quantizer module of each model together and achieves codebook compression to the number of phonemes or linguistic units. The discretization of representations do result in performance increase on various downstream tasks, with a pretrained Wav2Vec 2.0 [Baevski et al. (2020)] achieving state of the art results on speech recognition by being fine-tuned on only 10 minutes of transcribed audio. SeqRQ-AE [Liu et al. (2019)] is the closest to our work which uses a VQ-VAE [van den Oord et al. (2017)] to estimate representations for each phoneme in speech. The VQ-VAE has a codebook containing the same number of members as the number of phonemes. The codebook is trained via phonetic clustering, temporal segmentation and CTC finetuning on a small amount of transcribed audio.
Neural Audio Fingerprinting. Now Playing [Arcas et al. (2017)] and [Chang et al. (2020)] use a Neural Network Fingerprinter (NNFP) module outputting representations which are efficient for search in query-by-example tasks where the difference between query and actual song is pretty minute in comparison to humming where only the melody is sung. Now Playing[Arcas et al. (2017)] trains representations by optimizing the Triplet loss [Schroff et al. (2015)] and [Chang et al. (2020)] trains representations by simulating the Maximum Inner Product Search on mini-batches of representations.
Cross Domain Alignment. Given a pair of semantically similar inputs for training, tasks such as visual question answering (text and image) and machine translation (text) involve learning of an alignment. The alignment here is not ordered and the inputs may be from different modalities. Attention models have been used to find alignment between output entities and input regions [Yao et al. (2018)]. [Chen et al. (2020)] use Gromov-Wasserstein distance between output and input entities to match them. However, there is no notion of tokens there, rather the salient entities in the input are represented as vectors in a graph.
Graph Matching. Generation of representations for graphs can be done by Graph Neural Networks [Gori et al. (2005)]. Graph matching is used to find similarity of structured graphs [Li et al. (2019)]. However, they perform the matching jointly on the pair of inputs, rather than representing each input independently. This makes them unsuitable for the search problem at hand due to large runtime complexity. The distance metrics used for graph matching are based on edit distance [Li et al. (2019)] and Wasserstein distance [Chen et al. (2020)].

heading: 3 METHODOLOGY

heading: 3.1 PROBLEM STATEMENT
text: Given a pair of semantically similar feature sequences (Xi,Xj) of length Ti and Tj respectively and feature sequence Xk of length Tk with no similarity to either of the feature sequences Xi or Xj , we aim to map sequence Xi to sequence of tokens Ti of length T ′i ≤ Ti, sequence Xj to sequence of tokens Tj of length T ′j ≤ Tj , and sequence Xk to sequence of tokens Tk of length T ′k ≤ Tk where all the tokens belong to a finite alphabet A such that, the edit distance between Ti and Tj is minimum while that between Tk and Ti as well as Tk and Tj is maximum.

heading: 3.2 MODEL ARCHITECTURE
text: Wav2Tok is comprised of an encoder, which, given input x ∈ Rn, outputs a representation z ∈ Rm, and a tokenizer, which, given the encoder output z, outputs a token τ which belongs to a finite K-element alphabet A = {1, ...,K}. Given, a temporal sequence X = [x1, ..., xT ] of length T where xt is the feature vector at time t. Our model performs frame-wise labelling of X to output a sequence of tokens T = [τ1, ..., τT ] where τt ∈ A is the token assigned to input xt. The encoder f : X 7→ Z encodes xt in a hyper-spherical space Z using a BiLSTM network [Schuster & Paliwal (1997)] followed by an L-2 normalization layer. The BiLSTM allows zt to summarise information in both directions, and hence, encode surrounding context. The tokenizer g : Z 7→ T is a K-means vector quantizer which vector quantizes encoder output zt with K quantizers or cluster centroids wtokk ∈ Z; k = 1, ...,K and outputs token τt as, τt = argmaxk{zt · wtokk }. The centroids are estimated prior to training via spherical K-means clustering in the spherical space Z generated by the freshly initialised encoder. The centroids are further tuned with training iterations.

heading: 3.3 MODEL TRAINING
text: Given a batch of tuples of similar sequences (Xi,Xi′) where Xi = [xit ∈ Rn; t = 1, ..., Ti] and Xi′ = [xi ′
t′ ∈ Rn; t′ = 1, ..., Ti′ ]. The encoder f maps these sequences to representations Zi = f(Xi) and Zi′ = f(Xi′). The tokenizer g then labels Zi framewise to token sequence Ti and Zi′ framewise to token sequence Ti′ . For training, the tuple (Zi,Zi′) are concatenated to form the composed sequence Zii′ = [Zi;Zi′ ] of length Tii′ = Ti + Ti′ . The tuple (Ti, Ti′) are also concatenated to form the token sequence Tii′ = [Ti; Ti′ ] of length Tii′ = Ti+Ti′ corresponding to sequenceZii′ . Given Tii′ = [τ ii ′ 1 , ..., τ ii′
Tii′ ]
and Zii′ = [zii ′ 1 , ..., zii ′ Tii′ ], we form aK ′ ≤ K length list of prototypes Pii′ = {pτ1ii′ , ...,p τK′ ii′ } where {τ1, ..., τK′} ∈ A are allK ′ unique tokens that occur in Tii′ and pτk′ii′ is a prototype for token τk′ ∈ A generated from all vectors in Zii′ mapping to τk′ as,
p̃τk′ii′ = 1∑Tii′
t=1 1τ ii′t =τk′
Tii′∑ t=1 zii ′ t 1τ ii′t =τk′ (1)
pτk′ii′ = p̃τk′ii′ ||p̃τk′ii′ ||
(2)
Let Pii′ and Pjj′ be lists of prototypes generated given tuples (Xi,Xi′) and (Xj ,Xj′), respectively. We sample tuples of prototypes (pτii′ ,pτ ′ jj′) where pτii′ is sampled from Pii′ and pτ ′
jj′ is sampled from Pjj′ .
Approach A. Given (pτii′ ,pτ ′
jj′), we optimize the following loss function L11 to increase the cosine similarity between pτii′ and pτ ′ jj′ to 1 if τ = τ ′ and to decrease the cosine similarity to 0 if τ 6= τ ′,
L11(pτii′ ,pτ ′ jj′ , t1) = BinXEnt(p τ ii′ · pτ ′ jj′ , t1) (3)
BinXEnt(pτii′ · pτ ′ jj′ , t1) = t1 · log(pτii′ · pτ ′ jj′) + (1− t1) · log(1− pτii′ · pτ ′ jj′) (4)
where BinXEnt(.) is the binary cross-entropy function, pτii′ · pτ ′
jj′ gives a cosine similarity score as both the vectors are L-2 normalized, and target t1 is 0 if τ 6= τ ′ else 1. We also optimize the following loss function L12 to increase the cosine similarity of pτii′ or pτ ′ jj′ with respect to the k th quantizer wtokk in our tokenizer g : Z 7→ T to 1 if τ or τ ′ = k repectively and to decrease the same to 0 if τ or τ ′ 6= k ,
L12(pτii′ ,pτ ′ jj′) = K∑ k=1 (BinXEnt(pτii′ · wtokk , t1k) +BinXEnt(pτ ′ jj′ · wtokk , t2k)) (5)
where target t1k is 0 if τ 6= k else 1 and target t2k is 0 if τ ′ 6= k else 1. The constrastive loss function L1 for Approach A thus formed with the union of the above two loss functions is given as,
L1(pτii′ ,pτ ′ jj′ , t1) = L11(pτii′ ,pτ ′ jj′ , t1) + L12(pτii′ ,pτ ′ jj′) (6)
Approach B. Given (pτii′ ,pτ ′
jj′), a relation network R : Rm 7→ R generates relation score R(pτii′ ,pτ ′
jj′) in the range [0, 1] which is closer to 0 if τ 6= τ ′ and closer to 1 if τ = τ ′. The relation score acts as a non-linear similarity metric and is given as,
R(pτii′ ,pτ ′ jj′) = σ(WTr |pτii′ − pτ ′
jj′ |) (7) where σ(.) is the sigmoid function, |.| is the element-wise absolute value function, andWr ∈ Rm is the weight matrix of the relation network R : Rm 7→ R. Given R(pτii′ ,pτ ′
jj′), we optimize the following loss function L21 to increase the relation score between pτii′ and pτ ′ jj′ to 1 if τ = τ ′ and to decrease the relation score to 0 if τ 6= τ ′,
L21(pτii′ ,pτ ′ jj′ , t2) = BinXEnt(R(pτii′ ,pτ ′ jj′), t2) (8)
where target t2 is 0 if τ 6= τ ′ else 1. We also optimize the following loss function L22 to increase the relation score of pτii′ or pτ ′ jj′ with respect to the k th quantizer wtokk in our tokenizer g : Z 7→ T to 1 if τ or τ ′ = k respectively and to decrease the same to 0 if τ or τ ′ 6= k ,
L22(pτii′ ,pτ ′ jj′) = K∑ k=1 (BinXEnt(R(pτii′ ,wtokk ), t1k) +BinXEnt(R(pτ ′ jj′ ,w tok k ), t2k)) (9) where target t3k is 0 if τ 6= k else 1 and target t4k is 0 if τ ′ 6= k else 1. The contrastive loss function L2 for Approach B thus formed with the union of the above two loss functions is given as,
L2(pτii′ ,pτ ′ jj′ , t2) = L22(pτii′ ,pτ ′ jj′ , t2) + L22(pτii′ ,pτ ′ jj′) (10)
A spherical K-means vector quantization loss as inspired from the K-means vector quantization loss in VQ-Wav2Vec [Baevski et al. (2019)] may be iterated to add more movement to the centroids and the representations. Given prototype pτii′ for token τ ∈ A generated from sequence of representations Zii′ = [zii ′ 1 , ..., zii ′ Tii′ ] and sequence of tokens Tii′ = [τ ii ′ 1 , ..., τ ii′ Tii′ ], our vector quantization loss is given as,
LSK(pτii′) = 1∑Tii′
t=1 1τ ii′t =τ
Tii′∑ t=1 (2− (sg(zii ′ t ) · wtokτ + γ · zii ′ t · sg(wtokτ )))1τ ii′t =τ (11)
where γ is a positive constant, and sg(.) is the stop-gradient operator. The stop-gradient operator converts the parameter input to a constant during gradient computation. Increasing sg(zii ′
t ) · wtokτ pushes wtokτ towards zii ′ t keeping zii ′ t static and increasing zii ′ t · sg(wtokτ ) pushes zii ′
t towards wtokτ keeping wtokτ static. With γ set to 0, iterating the loss only affects wtokτ .
Given (pτii′ ,pτjj′), the final loss function L which we minimize to optimize our model parameters is given as,
L(pτii′ ,pτ ′ jj′ , ta) = La(pτii′ ,pτ ′ jj′ , ta) + α · (LSK(pτii′) + LSK(pτ ′ jj′)) (12)
where α is a positive constant, ta is the target, and a = 1 corresponds to Approach A while a = 2 corresponds to Approach B.

heading: 3.4 SEQUENCE SEGMENTATION AND COMPRESSION
text: Given a sequence of features X = [x1, ...., xT ] where T is the sequence length, the encoder f outputs a sequence of L-2 normalised representations Z = [z1, ...., zT ] and the tokenizer g outputs a sequence of tokens T = [τ1, ...., τT ]. The consecutive repetition of tokens in T highlights a subsequence in Z whose constituent vectors are similar. Given T , we delete all consecutive token repetitions to form compressed token sequence T̃ = [τts1 :te1 , ..., τtsT ′ :teT ′ ] of length T
′ ≤ T where ts1 = 1, teT ′ = T , and τtsi :tei is the token which occurs in the interval [tsi : tei ] of sequence T . Given the set of token onset and offset times {(tsi , tei)|i ∈ {1, ..., T ′}} generated via compression of T to T̃ with tsi and tei denoting the onset and offset time of the i-th token τtsi :tei in T̃ , we generate compressed sequence Z̃ = [z̃ts1 :te1 , ..., z̃tsT ′ :teT ′ ] of length T
′ ≤ T from Z where z̃tsi :tei is a representation for all consecutive vectors zt in the interval [tsi , tei ] of sequence Z mapping to the same token τtsi :tei and is given as,
z̃′tsi :tei = 1
tei − tsi tei∑ t=tsi zt (13)
z̃tsi :tei = z̃′tsi :tei ||z̃′tsi :tei ||
(14)
A compressor network C performs the aforementioned compression on sequencesZ and T of length T to output sequences Z̃ and T̃ of length T ′ ≤ T respectively.

heading: 4 EXPERIMENTS
text: We test the performance of Wav2Tok for three tasks, viz., Query by Humming, Speech Search and Keyword Spotting.

heading: 4.1 DATASETS
text: We employ the MIR-QBSH dataset for query by humming tasks and TIMIT [Garofolo et al. (1993)] dataset for speech search and keyword spotting tasks. MIR-QBSH is composed of 4431 singing or humming recordings (8KHz, 8-bit, monophonic) submitted by 195 subjects. The dataset is further partitioned into 48 partitions, each composed of recordings corresponding to one of the 48 ground truth songs. TIMIT is composed of spoken text audio (16KHz, 16-bit, monophonic). We choose 59 words with reasonable number of occurrences as keywords and all other words as non-keywords, resulting in a dataset of 2169 keyword recordings.

heading: 4.2 BASELINES
text: STFT. This method performs DTW over raw STFT features.
Triplet. Representations generated by a BiLSTM encoder [Schuster & Paliwal (1997)] are tuned via optimizing the Triplet Loss [Schroff et al. (2015)] as done in optimizing neural audio fingerprints in Now Playing [Arcas et al. (2017)]. Let a be the reference or anchor sample, p be a positive sample (same sample but augmented), and n be a negative sample (sample with no similarity to a). Constraining all vectors in the triplet (a, p,n) to be L-2 normalized, the loss function for each triplet of is given as,
LTriplet(a, p,n) = max{d(a,p)− d(a,n) +m, 0} (15) d(x, y) = ||x− y|| (16)
where max{.} represents the maximum operator,x and y are vectors with same dimension, and m is the margin which adds the meaning of similarity to the function. The representations were not constrained to be L-2 normalized.
MIPS. Representations generated by a BiLSTM encoder [Schuster & Paliwal (1997)] are constrained to be L-2 normalized and are trained with divergences taken via simulation of Maximum
Inner Product Search [Mussmann & Ermon (2016)] on mini-batches of representation vectors as proposed by [Chang et al. (2020)]. A minibatch {zi|i ∈ {1, ..., N}} of size N is composed of N2 pairs {zorg, zrep} where representation vector zrep is an augmented replica of the representation vector zorg. With zj as the augmented replica of zi in a minibatch of representation vectors, the loss function to be minimized is given as,
LMIPS(zi, zj) = − log exp(Sim(zi, zj))∑ k 6=i exp(Sim(zi, zk))
(17)
Wav2Vec 2.0. A scaled down and modified Wav2Vec 2.0 [Baevski et al. (2020)] model where the latent Representations generated by a BiLSTM encoder [Schuster & Paliwal (1997)] are masked and Product Quantized (PQ) with a Gumble Softmax based Vector Quantizer [Baevski et al. (2019)] (see Appendix B). For a masked time step t, the latent representation zt is fed to a Transformer encoder [Vaswani et al. (2017)] which outputs a contextualised representation ct used to distinguish the true quantized representation qt output by the vector quantizer given zt from a set of D + 1 candidate quantized representations q̃ ∈ Qt containing qt and D distractors. The loss function iterated to train the model is given as,
LWav2V ec2 = − log exp(sim(ct,qt)/κ)∑
q̃∼Qt exp(sim(ct, q̃)/κ) + β · Ld (18)
where sim(a, b) = a T b
||a||||b|| gives cosine similarity score, β is a positive constant, and Ld is a codebook diversity loss for the Gumble Softmax based Vector Quantizer module encouraging equal use of the codebook entries (see Appendix B).
Wav2Vec Tok. The same architecture as Wav2Vec 2.0 but here the Gumble Softmax Based Vector Quantizer is used as a Tokenizer which labels the latent representations with K tokens forming alphabet A = {1, ...,K}. The representations are also trained optimizing loss function [18]. MIPS and Triplet use a 2-layer BiLSTM as encoder with 3.6 million trainable parameters. We use the LAMB optimizer [You et al. (2020)] and a Cosine Annealing Learning Schedule [Loshchilov & Hutter (2017)] with a learning rate restart of 0.0001 to train them. Wav2Vec 2.0 and Wav2Vec Tok use a 2-layer BiLSTM encoder with 3.6 million trainable parameters to generate latent space and a 2-layer Transformer with 3 attention heads with 8.5 million trainable parameters to generate context space amounting to models with 12.1 million trainable parameters. Both are trained using the ADAM [Kingma & Ba (2017)] optimizer and a linear learning schedule warming-up a learning rate of 0.001 in the first 8% of the training steps.

heading: 4.3 OUR MODELS
text: TokA. Model trained in accordance to Approach A. We do not iterate over the quantization loss LSK by setting positive constant α in final loss function L to 0 since we are calculating the contrastive loss L1 with cosine similarity allowing it to give the same regularisation as LSK . TokB. Model trained in accordance to Approach B.
TokB+Trans. Model trained in accordance to Approach B but with a Transformer encoder [Vaswani et al. (2017)] as encoder network instead of an BiLSTM and α = 0.
TokB+NoSim. Model trained in accordance to Approach B but with batches of tuples of sequences which need not be semantically similar and α = 0.
TokA, TokB, and TokB+NoSim use a 2-layer BiLSTM as encoder with 3.6 million trainable parameters. TokB+Trans uses a 2-layer Transformer with 3 attention heads as encoder with 8.5 million trainable parameters. We train then using the ADAM [Kingma & Ba (2017)] optimizer and a linear learning schedule, warming-up a learning rate of 0.001 in the first 8% of the training steps.

heading: 4.4 MUSIC MELODY SEARCH: QUERY BY HUMMING
text: Task. Given a test query audio, we are to find in the search audio database the most similar melody.
Experiment Details. We divide the MIR-QBSH dataset into 3 splits of training, validation and test with split sizes in the ratio 2462 : 844 : 1125. The recordings are all converted to Short Time Fourier Transform matrices with 513 frequency bins, a window length of 1024 samples (128 ms), and hop length of 512 samples. The training and the validation split consists of pairs of similar audio. The test set consists of a search database (with audio from validation split) and a set of queries (disjoint from both training and validation splits). All the audio in the search dataset are converted to sequences of representations or tokens, using the same tokenizer as used over the search database. Given a query sampled from the test split, we perform DTW based search (if representations) or Edit Distance based search (if tokens) over the search database.
Results. The proposed TokB representation with DTW search performs the best in terms of Mean Reciprocal Rank (MRR) scores (see Appendix D) as compared to other baselines and proposed methods, as shown in Table 1. Larger the MRR score, better is the method. Quantization of the representations to tokens (see TokB ED) makes the search faster, while slightly degrading the performance. To check the robustness of the representation or tokens, we also apply a series of transformations on the queries in the form of time stretch and pitch shift. Melodic semantics are not altered by these transformations. Along with the original query (V or vanilla) Table 1 also shows the results for Time Stretched (TS) query, Pitch Shifted (PS) query, and Time Stretched + Pitch Shifted (TS + PS) query. Sequence compression further speeds up the search while lowering the performance metrics (see Compressed columns in Table 1). ED is faster than DTW and compressed sequences are faster to search. So, ED based search over compressed tokens is the fastest.
Model SearchTime Normal
Wav2Vec Tok DTW 3.48 Wav2Vec Tok ED 0.2
TokB DTW 3.5 TokB ED 0.32
Compressed Wav2Vec Tok DTW 0.4 Wav2Vec Tok ED 0.02
TokB DTW 0.6 TokB ED 0.04
Table 2: Average Search Time (in s) per query
Effect of LSK . We study the effect of including LSK to the loss function by setting different values of α and γ in Eq. 12. We observe an overall performance drop with inclusion of LSK , as shown in Table 3.
Variation in number of Tokens. The effect of varying the size of alphabet A is shown in Table 4. K = 25 gives the best performance for all models. Although K = 15 and K = 40 gives a small performance drop in MRR for vanilla queries, the robustness of the tokens to transformed queries degrades a lot. TokB gave the best performance for almost all the settings of K while Wav2Vec Tok suffers a large drop in performance for K = 40.
Token Semantics. Query by humming involves similarity based on melody information, which is carried by the semantic pairing of the audio in training data. As an ablation study, we randomize this pairing; we call this model TokB+NoSim. The results are presented in Table 5. There is a drop in performance with TokB+NoSim as compared to TokB, which is more severe for transformed queries. These results support that the model TokB is learning the semantic information from the pairs.
Transformer as Encoder. We use a Transformer with 8.5 million parameters instead of a 3.6 million parameter BiLSTM as our encoder. We call this model as TokB+Trans. There is an overall drop in performance and robustness of the tokens generated by TokB+Trans incomparison to TokB (Table 5). Possible causes for such drop could be overfitting by the larger transformer encoder or the number of attention heads (3, here). Decreasing the number of layers and increasing the number of attention heads might bring in some improvement in performance.

heading: 4.5 SPEECH SEARCH
text: Task. Given a query speech audio, we are to find in the search database the audio with similar speech content.
Experiment Details. We divide the keyword dataset, extracted from TIMIT, into three splits, viz., training, validation and test with split sizes corresponding to each keyword in the ratio 1414 : 188 : 567. All audio are converted to spectrograms using Short Time Fourier Transform with 185 frequency bins, a window length of 368 samples (23 ms), and hop length of 92 samples. We train and test our models in the same fashion as done for query by humming experiments (Sec. 4.4).
Results. The representations generated by TokB and MIPS perform the best as shown in Table 6. There is only a slight drop of 0.02 MRR when sequence compression is applied to the representations generated by TokB (see Compressed columns in Table 6), implying a faster search with high MRR performance.
Models Normal Compressed
STFT DTW 0.49 - Triplet DTW 0.5 - MIPS DTW 0.737 -
Wav2Vec Tok DTW 0.64 0.5 TokA DTW 0.622 0.624 TokB DTW 0.735 0.71
Wav2Vec Tok ED 0.4 0.175 TokA ED 0.443 0.364 TokB ED 0.61 0.54
Table 6: TIMIT Similarity Search Results (MRR Scores)

heading: 4.6 KEYWORD SPOTTING
text: Task. Given a query audio containing an uttered keyword, spot the location of the keyword in a dataset of long speech recordings. It is considered a hit if the spotted segment in a long audio has a non-zero overlap with the ground truth segment of the keyword.
Experiment Details. All models are trained on the keyword dataset as done for speech search. We synthetically generate 564 long utterances each composed of either 60 or 80 non-keywords sampled randomly from TIMIT and 6 to 10 occurrences of keywords sampled from the keyword dataset extracted from TIMIT. The training set comprises 273 long utterances which are used to set the detection threshold for the keyword spotters. The test set consists of a query database (with audio from the validation split we generated from the keyword dataset) and a search database formed with the remaining 291 long utterances. The recordings are all converted to spectrograms using Short Time Fourier Transform with 185 frequency bins, a window length of 368 samples (23 ms), and hop length of 92 samples. We convert the search dataset as well as the query audio into representation or tokens using a tokenizer. For search, we chunk the long audio into smaller segments. Let U1 = [u11, ..., u1T ] of length T represent the query keyword to be spotted. Here, ut may either be a representation zt or a token τt or raw STFT feature xt. Let U2 = [u21, ..., u2T ′ ] represent the long query of length T ′ T . For any time step t in U2, a detection score st is generated as follows,
st = min l∈{0.5·T,T,2·T}
Dist(U1,U2t:t+l) (19)
where U2t:t+l is the segment of U2 in the time interval (t, t + l) of length l ∈ {0.5 · T, T, 2 · T}, and Dist(.) generates DTW distance when ut = zt or xt, and Edit Distance when ut = τt. We set detection threshold θ by training our keyword spotter with some training utterances (see Appendix C). A keyword is detected at time step t in given query iff st ≤ θ. We evaluate performance of all our keyword spotters based on Accuracy, Precision, Recall, F1 score and Search Time. Many efficient and faster algorithms exist for text search or genome sequence search but we chose to use aforementioned approach to test the tokenizer efficacy.
Results. Tokens and representations generated by TokB give the best results in terms of F1 Score, as shown in Table 7. The tokenization performed by TokB also results in the best search time since TokB performs the best segmentation of the input utterances. DTW over raw STFT features is fast because of low dimensionality of the features.

heading: 5 CONCLUSION AND FUTURE WORK
text: In this paper, we present a audio sequence tokenizer Wav2Tok that generates semantically meaningful ordered representations (or tokens) that can be used for efficient retrieval by query sequences. The tokens are learnt from pairs of semantically similar sequences, without any expert generated annotations. The tokenizer is tested for audio retrieval tasks involving a variety of semantics - melodic as well as phonetic. The performance is found to be consistent and better than state of the art models adapted for retrieval. We would like to apply more efficient search algorithms such as locally sensitive hashing and longest common subsequence search on the generated tokens to further speed up the search. Also, we are working towards extending the proposed framework to 2D data retrieval.

heading: 6 REPRODUCIBILITY
text: The codes required to reproduce the results of this paper will be made available after the review. The experiments are performed using standard datasets.

heading: B GUMBLE SOFTMAX BASED VECTOR QUANTIZER
text: The Gumble Softmax based Vector Quantizer product quantizes input latent representation zt ∈ Rm with C codebooks each containing K quantizers e ∈ RK×mC . Given zt, one of the K quantizers from each of the C codebooks are chosen resulting in vectors e1, ..., eC which are concatenated and linearly transformed from Rm to Rd to output qt ∈ Rd. zt is mapped to l ∈ RC×K logits to give probability scores for the choice of codeword. The probability pc,k of choosing kth quantizer in cth codebook is given as,
pc,k = exp (lc,k + nk)/τ∑K i=1 exp (lc,i + ni)/τ
(20)
where τ is a non-negative temperature, n = −log(−log(u)) and u are samples from the uniform distribution Unif(0, 1). During forward pass, the codeword is chosen as κ = argmaxj pc,j . The straight-through gradient estimator [Yin et al. (2019)] is utilized to estimate the gradient during backward pass.
Codebook Diversity Loss Ld. This loss promotes equal use of all the entries in each of the C codebooks by maximizing the entropy of the averaged softmax distribution l over the K entries for
each codebook p̃c across a batch of utterances.
Ld = 1
CK C∑ c=1 K∑ k=1 p̃c,k log p̃c,k (21)

heading: C SETTING OF DETECTION THRESHOLD FOR KEYWORD SPOTTING
text: Given the utterances are converted to sequences of tokens, we use Edit distance as detection score. The Edit distance being an integer, we find the mode mhit of the set of detection scores st generated at time steps t when a keyword is present. We also find the mode mno−hit of the set of detection scores st generated at time steps t when no keyword is present. The detection threshold is then set as th = 12 (mno−hit +mhit). If st ≤ th, keyword is spotted else non-keyword. Given the utterances are converted to sequences of representations, we use DTW distance as detection score. We find the average savghit of the set of detection scores st generated at time steps t when a keyword is present. We also find the average savgno−hit of the set of detection scores st generated at time steps t when no keyword is present. The detection threshold is then set as th = 12 (s avg no−hit + s avg hit ). If st ≤ th, keyword is spotted else non-keyword.

heading: D MEAN RECIPROCAL RANK
text: Mean Reciprocal Rank (MRR) is a metric used to evaluate search performances. Given a query, a search over the database outputs a ranking on the documents in a descending order of some similarity metric calculated with the query. Let ranki be the rank of the first relevant document for the ith query sampled from a set of N queries. The MRR score is given as,
MRR = 1
N N∑ i=1 1 ranki (22)

Review summaries:
The paper presents an algorithm to do sequence matching using a tokenizations of the original sequences, and evaluates it in three different settings. The test environments are non-standard setups of public databases, with a closed vocabulary of sequences, i.e. training, validation, and testing sets contain the same sequences.

This paper proposes to speed up search for similar sequences in cases where data is continuous valued and similar sequence search is computationally expensive.  It proposes to convert continuous valued sequence to a sequence of discrete tokens.  The token vocabulary and assignment of features to tokens is constructed via k-means clustering and evolves during the model training process.   Results are presented on two tasks: QBSH (query by singing/humming) and TIMIT speech search and keyword spotting, demonstrating that the proposed approach yields better results as compared to baseline DTW methods, and is also more robust to input distortions.  However a comparison with previously published results is missing.

This paper studies the problem of information retrieval that searches similar items to a given query. The paper introduces a new tokenizer and claims that Seq2Tok can convert a continuous sequence (e.g. audio) to discrete tokens. The purpose of the conversion is to enable easier retrieval. The paper conducts extensive experiments and claims that Seq2Tok achieves consistent performance on audio retrieval tasks.