-
Linear-time computation of generalized minimal absent words for multiple strings
Authors:
Kouta Okabe,
Takuya Mieno,
Yuto Nakashima,
Shunsuke Inenaga,
Hideo Bannai
Abstract:
A string $w$ is called a minimal absent word (MAW) for a string $S$ if $w$ does not occur as a substring in $S$ and all proper substrings of $w$ occur in $S$. MAWs are well-studied combinatorial string objects that have potential applications in areas including bioinformatics, musicology, and data compression. In this paper, we generalize the notion of MAWs to a set…
▽ More
A string $w$ is called a minimal absent word (MAW) for a string $S$ if $w$ does not occur as a substring in $S$ and all proper substrings of $w$ occur in $S$. MAWs are well-studied combinatorial string objects that have potential applications in areas including bioinformatics, musicology, and data compression. In this paper, we generalize the notion of MAWs to a set $\mathcal{S} = \{S_1, \ldots, S_k\}$ of multiple strings. We first describe our solution to the case of $k = 2$ strings, and show how to compute the set $\mathsf{M}$ of MAWs in optimal $O(n + |\mathsf{M}|)$ time and with $O(n)$ working space, where $n$ denotes the total length of the strings in $\mathcal{S}$. We then move on to the general case of $k > 2$ strings, and show how to compute the set $\mathsf{M}$ of MAWs in $O(n \lceil k / \log n \rceil + |\mathsf{M}|)$ time and with $O(n (k + \log n))$ bits of working space, in the word RAM model with machine word size $ω= \log n$. The latter algorithm runs in optimal $O(n + |\mathsf{M}|)$ time for $k = O(\log n)$.
△ Less
Submitted 28 July, 2023; v1 submitted 4 July, 2023;
originally announced July 2023.
-
I4U System Description for NIST SRE'20 CTS Challenge
Authors:
Kong Aik Lee,
Tomi Kinnunen,
Daniele Colibro,
Claudio Vair,
Andreas Nautsch,
Hanwu Sun,
Liang He,
Tianyu Liang,
Qiongqiong Wang,
Mickael Rouvier,
Pierre-Michel Bousquet,
Rohan Kumar Das,
Ignacio Viñals Bailo,
Meng Liu,
Héctor Deldago,
Xuechen Liu,
Md Sahidullah,
Sandro Cumani,
Boning Zhang,
Koji Okabe,
Hitoshi Yamamoto,
Ruijie Tao,
Haizhou Li,
Alfonso Ortega Giménez,
Longbiao Wang
, et al. (1 additional authors not shown)
Abstract:
This manuscript describes the I4U submission to the 2020 NIST Speaker Recognition Evaluation (SRE'20) Conversational Telephone Speech (CTS) Challenge. The I4U's submission was resulted from active collaboration among researchers across eight research teams - I$^2$R (Singapore), UEF (Finland), VALPT (Italy, Spain), NEC (Japan), THUEE (China), LIA (France), NUS (Singapore), INRIA (France) and TJU (C…
▽ More
This manuscript describes the I4U submission to the 2020 NIST Speaker Recognition Evaluation (SRE'20) Conversational Telephone Speech (CTS) Challenge. The I4U's submission was resulted from active collaboration among researchers across eight research teams - I$^2$R (Singapore), UEF (Finland), VALPT (Italy, Spain), NEC (Japan), THUEE (China), LIA (France), NUS (Singapore), INRIA (France) and TJU (China). The submission was based on the fusion of top performing sub-systems and sub-fusion systems contributed by individual teams. Efforts have been spent on the use of common development and validation sets, submission schedule and milestone, minimizing inconsistency in trial list and score file format across sites.
△ Less
Submitted 2 November, 2022;
originally announced November 2022.
-
Minimal Absent Words on Run-Length Encoded Strings
Authors:
Tooru Akagi,
Kouta Okabe,
Takuya Mieno,
Yuto Nakashima,
Shunsuke Inenaga
Abstract:
A string $w$ is called a minimal absent word (MAW) for another string $T$ if $w$ does not occur (as a substring) in $T$ and any proper substring of $w$ occurs in $T$. State-of-the-art data structures for reporting the set $\mathsf{MAW}(T)$ of MAWs from a given string $T$ of length $n$ require $O(n)$ space, can be built in $O(n)$ time, and can report all MAWs in $O(|\mathsf{MAW}(T)|)$ time upon a q…
▽ More
A string $w$ is called a minimal absent word (MAW) for another string $T$ if $w$ does not occur (as a substring) in $T$ and any proper substring of $w$ occurs in $T$. State-of-the-art data structures for reporting the set $\mathsf{MAW}(T)$ of MAWs from a given string $T$ of length $n$ require $O(n)$ space, can be built in $O(n)$ time, and can report all MAWs in $O(|\mathsf{MAW}(T)|)$ time upon a query. This paper initiates the problem of computing MAWs from a compressed representation of a string. In particular, we focus on the most basic compressed representation of a string, run-length encoding (RLE), which represents each maximal run of the same characters $a$ by $a^p$ where $p$ is the length of the run. Let $m$ be the RLE-size of string $T$. After categorizing the MAWs into five disjoint sets $\mathcal{M}_1$, $\mathcal{M}_2$, $\mathcal{M}_3$, $\mathcal{M}_4$, $\mathcal{M}_5$ using RLE, we present matching upper and lower bounds for the number of MAWs in $\mathcal{M}_i$ for $i = 1,2,4,5$ in terms of RLE-size $m$, except for $\mathcal{M}_3$ whose size is unbounded by $m$. We then present a compact $O(m)$-space data structure that can report all MAWs in optimal $O(|\mathsf{MAW}(T)|)$ time.
△ Less
Submitted 14 April, 2022; v1 submitted 28 February, 2022;
originally announced February 2022.
-
Task-aware Warping Factors in Mask-based Speech Enhancement
Authors:
Qiongqiong Wang,
Kong Aik Lee,
Takafumi Koshinaka,
Koji Okabe,
Hitoshi Yamamoto
Abstract:
This paper proposes the use of two task-aware warping factors in mask-based speech enhancement (SE). One controls the balance between speech-maintenance and noise-removal in training phases, while the other controls SE power applied to specific downstream tasks in testing phases. Our intention is to alleviate the problem that SE systems trained to improve speech quality often fail to improve other…
▽ More
This paper proposes the use of two task-aware warping factors in mask-based speech enhancement (SE). One controls the balance between speech-maintenance and noise-removal in training phases, while the other controls SE power applied to specific downstream tasks in testing phases. Our intention is to alleviate the problem that SE systems trained to improve speech quality often fail to improve other downstream tasks, such as automatic speaker verification (ASV) and automatic speech recognition (ASR), because they do not share the same objects. It is easy to apply the proposed dual-warping factors approach to any mask-based SE method, and it allows a single SE system to handle multiple tasks without task-dependent training. The effectiveness of our proposed approach has been confirmed on the SITW dataset for ASV evaluation and the LibriSpeech dataset for ASR and speech quality evaluations of 0-20dB. We show that different warping values are necessary for a single SE to achieve optimal performance w.r.t. the three tasks. With the use of task-dependent warping factors, speech quality was improved by an 84.7% PESQ increase, ASV had a 22.4% EER reduction, and ASR had a 52.2% WER reduction, on 0dB speech. The effectiveness of the task-dependent warping factors were also cross-validated on VoxCeleb-1 test set for ASV and LibriSpeech dev-clean set for ASV and quality evaluations. The proposed method is highly effective and easy to apply in practice.
△ Less
Submitted 27 August, 2021;
originally announced August 2021.
-
A Generalized Framework for Domain Adaptation of PLDA in Speaker Recognition
Authors:
Qiongqiong Wang,
Koji Okabe,
Kong Aik Lee,
Takafumi Koshinaka
Abstract:
This paper proposes a generalized framework for domain adaptation of Probabilistic Linear Discriminant Analysis (PLDA) in speaker recognition. It not only includes several existing supervised and unsupervised domain adaptation methods but also makes possible more flexible usage of available data in different domains. In particular, we introduce here the two new techniques described below. (1) Corr…
▽ More
This paper proposes a generalized framework for domain adaptation of Probabilistic Linear Discriminant Analysis (PLDA) in speaker recognition. It not only includes several existing supervised and unsupervised domain adaptation methods but also makes possible more flexible usage of available data in different domains. In particular, we introduce here the two new techniques described below. (1) Correlation-alignment-based interpolation and (2) covariance regularization. The proposed correlation-alignment-based interpolation method decreases minCprimary up to 30.5% as compared with that from an out-of-domain PLDA model before adaptation, and minCprimary is also 5.5% lower than with a conventional linear interpolation method with optimal interpolation weights. Further, the proposed regularization technique ensures robustness in interpolations w.r.t. varying interpolation weights, which in practice is essential.
△ Less
Submitted 20 August, 2020;
originally announced August 2020.
-
Speaker detection in the wild: Lessons learned from JSALT 2019
Authors:
Paola Garcia,
Jesus Villalba,
Herve Bredin,
Jun Du,
Diego Castan,
Alejandrina Cristia,
Latane Bullock,
Ling Guo,
Koji Okabe,
Phani Sankar Nidadavolu,
Saurabh Kataria,
Sizhu Chen,
Leo Galmant,
Marvin Lavechin,
Lei Sun,
Marie-Philippe Gill,
Bar Ben-Yair,
Sajjad Abdoli,
Xin Wang,
Wassim Bouaziz,
Hadrien Titeux,
Emmanuel Dupoux,
Kong Aik Lee,
Najim Dehak
Abstract:
This paper presents the problems and solutions addressed at the JSALT workshop when using a single microphone for speaker detection in adverse scenarios. The main focus was to tackle a wide range of conditions that go from meetings to wild speech. We describe the research threads we explored and a set of modules that was successful for these scenarios. The ultimate goal was to explore speaker dete…
▽ More
This paper presents the problems and solutions addressed at the JSALT workshop when using a single microphone for speaker detection in adverse scenarios. The main focus was to tackle a wide range of conditions that go from meetings to wild speech. We describe the research threads we explored and a set of modules that was successful for these scenarios. The ultimate goal was to explore speaker detection; but our first finding was that an effective diarization improves detection, and not having a diarization stage impoverishes the performance. All the different configurations of our research agree on this fact and follow a main backbone that includes diarization as a previous stage. With this backbone, we analyzed the following problems: voice activity detection, how to deal with noisy signals, domain mismatch, how to improve the clustering; and the overall impact of previous stages in the final speaker detection. In this paper, we show partial results for speaker diarizarion to have a better understanding of the problem and we present the final results for speaker detection.
△ Less
Submitted 2 December, 2019;
originally announced December 2019.
-
I4U Submission to NIST SRE 2018: Leveraging from a Decade of Shared Experiences
Authors:
Kong Aik Lee,
Ville Hautamaki,
Tomi Kinnunen,
Hitoshi Yamamoto,
Koji Okabe,
Ville Vestman,
Jing Huang,
Guohong Ding,
Hanwu Sun,
Anthony Larcher,
Rohan Kumar Das,
Haizhou Li,
Mickael Rouvier,
Pierre-Michel Bousquet,
Wei Rao,
Qing Wang,
Chunlei Zhang,
Fahimeh Bahmaninezhad,
Hector Delgado,
Jose Patino,
Qiongqiong Wang,
Ling Guo,
Takafumi Koshinaka,
Jiacen Zhang,
Koichi Shinoda
, et al. (21 additional authors not shown)
Abstract:
The I4U consortium was established to facilitate a joint entry to NIST speaker recognition evaluations (SRE). The latest edition of such joint submission was in SRE 2018, in which the I4U submission was among the best-performing systems. SRE'18 also marks the 10-year anniversary of I4U consortium into NIST SRE series of evaluation. The primary objective of the current paper is to summarize the res…
▽ More
The I4U consortium was established to facilitate a joint entry to NIST speaker recognition evaluations (SRE). The latest edition of such joint submission was in SRE 2018, in which the I4U submission was among the best-performing systems. SRE'18 also marks the 10-year anniversary of I4U consortium into NIST SRE series of evaluation. The primary objective of the current paper is to summarize the results and lessons learned based on the twelve sub-systems and their fusion submitted to SRE'18. It is also our intention to present a shared view on the advancements, progresses, and major paradigm shifts that we have witnessed as an SRE participant in the past decade from SRE'08 to SRE'18. In this regard, we have seen, among others, a paradigm shift from supervector representation to deep speaker embedding, and a switch of research challenge from channel compensation to domain adaptation.
△ Less
Submitted 15 April, 2019;
originally announced April 2019.
-
Attention Mechanism in Speaker Recognition: What Does It Learn in Deep Speaker Embedding?
Authors:
Qiongqiong Wang,
Koji Okabe,
Kong Aik Lee,
Hitoshi Yamamoto,
Takafumi Koshinaka
Abstract:
This paper presents an experimental study on deep speaker embedding with an attention mechanism that has been found to be a powerful representation learning technique in speaker recognition. In this framework, an attention model works as a frame selector that computes an attention weight for each frame-level feature vector, in accord with which an utterancelevel representation is produced at the p…
▽ More
This paper presents an experimental study on deep speaker embedding with an attention mechanism that has been found to be a powerful representation learning technique in speaker recognition. In this framework, an attention model works as a frame selector that computes an attention weight for each frame-level feature vector, in accord with which an utterancelevel representation is produced at the pooling layer in a speaker embedding network. In general, an attention model is trained together with the speaker embedding network on a single objective function, and thus those two components are tightly bound to one another. In this paper, we consider the possibility that the attention model might be decoupled from its parent network and assist other speaker embedding networks and even conventional i-vector extractors. This possibility is demonstrated through a series of experiments on a NIST Speaker Recognition Evaluation (SRE) task, with 9.0% EER reduction and 3.8% min_Cprimary reduction when the attention weights are applied to i-vector extraction. Another experiment shows that DNN-based soft voice activity detection (VAD) can be effectively combined with the attention mechanism to yield further reduction of minCprimary by 6.6% and 1.6% in deep speaker embedding and i-vector systems, respectively.
△ Less
Submitted 25 September, 2018;
originally announced September 2018.
-
Attentive Statistics Pooling for Deep Speaker Embedding
Authors:
Koji Okabe,
Takafumi Koshinaka,
Koichi Shinoda
Abstract:
This paper proposes attentive statistics pooling for deep speaker embedding in text-independent speaker verification. In conventional speaker embedding, frame-level features are averaged over all the frames of a single utterance to form an utterance-level feature. Our method utilizes an attention mechanism to give different weights to different frames and generates not only weighted means but also…
▽ More
This paper proposes attentive statistics pooling for deep speaker embedding in text-independent speaker verification. In conventional speaker embedding, frame-level features are averaged over all the frames of a single utterance to form an utterance-level feature. Our method utilizes an attention mechanism to give different weights to different frames and generates not only weighted means but also weighted standard deviations. In this way, it can capture long-term variations in speaker characteristics more effectively. An evaluation on the NIST SRE 2012 and the VoxCeleb data sets shows that it reduces equal error rates (EERs) from the conventional method by 7.5% and 8.1%, respectively.
△ Less
Submitted 24 February, 2019; v1 submitted 29 March, 2018;
originally announced March 2018.
-
Training a Fully Convolutional Neural Network to Route Integrated Circuits
Authors:
Sambhav R. Jain,
Kye Okabe
Abstract:
We present a deep, fully convolutional neural network that learns to route a circuit layout net with appropriate choice of metal tracks and wire class combinations. Inputs to the network are the encoded layouts containing spatial location of pins to be routed. After 15 fully convolutional stages followed by a score comparator, the network outputs 8 layout layers (corresponding to 4 route layers, 3…
▽ More
We present a deep, fully convolutional neural network that learns to route a circuit layout net with appropriate choice of metal tracks and wire class combinations. Inputs to the network are the encoded layouts containing spatial location of pins to be routed. After 15 fully convolutional stages followed by a score comparator, the network outputs 8 layout layers (corresponding to 4 route layers, 3 via layers and an identity-mapped pin layer) which are then decoded to obtain the routed layouts. We formulate this as a binary segmentation problem on a per-pixel per-layer basis, where the network is trained to correctly classify pixels in each layout layer to be 'on' or 'off'. To demonstrate learnability of layout design rules, we train the network on a dataset of 50,000 train and 10,000 validation samples that we generate based on certain pre-defined layout constraints. Precision, recall and $F_1$ score metrics are used to track the training progress. Our network achieves $F_1\approx97\%$ on the train set and $F_1\approx92\%$ on the validation set. We use PyTorch for implementing our model. Code is made publicly available at https://github.com/sjain-stanford/deep-route .
△ Less
Submitted 11 September, 2017; v1 submitted 27 June, 2017;
originally announced June 2017.