LISTENING TO MULTI-TALKER CONVERSATIONS: MODULAR AND END-TO-END PERSPECTIVES
by

Desh Raj
A dissertation submitted to Johns Hopkins University
in conformity with the requirements for the degree of
Doctor of Philosophy
Baltimore, Maryland

February, 2024

© 2024 Desh Raj
All rights reserved

## Abstract

Since the first speech recognition systems were built more than 30 years ago,
improvement in voice technology has enabled applications such as smart
assistants and automated customer support. Conversational intelligence of the
future is expected to move beyond single-user applications of voice
technologies to actively participate in human conversations, including in
scenarios such as note-taking, fact-checking, or collaborative learning in
peer groups. For such systems, recognizing free-flowing multi-party
conversations is a crucial and challenging component that still remains
unsolved. In this dissertation, we focus on this problem of speaker-attributed
multi-talker speech recognition for the meeting transcription task, and
propose two perspectives which result from its probabilistic formulation.

In the modular perspective, speaker-attributed transcription is performed
through a pipeline of sub-tasks involving speaker diarization, target speaker
extraction, and speech recognition. Our first contribution is a novel method
to perform overlap-aware speaker diarization by reformulating spectral
clustering as a constrained optimization problem. We also describe an
algorithm to ensemble diarization outputs, and show that it can be used to
either combine several overlap-aware systems, or to perform multi-channel
diarization by late fusion. Once speaker segments are identified, we robustly
extract single-speaker utterances from the mixture using a GPU-accelerated
implementation of guided source separation. This eventually allows us to use
an off-the-shelf ASR system to obtain speaker-attributed transcripts.

Since the modular approach suffers from error propagation, we propose an
alternate “end-to-end” perspective on the problem. For this, we describe the
Streaming Unmixing and Recognition Transducer (SURT) which extends neural
transducers for multi-talker ASR by incorporating an unmixing component. We
show how to train SURT models efficiently by carefully designing the network
architecture, objective functions, and mixture simulation techniques. Finally,
we add an auxiliary speaker branch to enable joint prediction of speaker
labels synchronized with the speech tokens, and propose a novel speaker
prefixing approach for ensuring label consistency through the recording. We
demonstrate that training on synthetic mixtures and adapting with real data
helps these models transfer well for streaming transcription of real meeting
sessions.

Primary reader: Sanjeev Khudanpur

#### Thesis Committee

Sanjeev Khudanpur
Daniel Povey (Xiaomi Inc., Beijing)
Jinyu Li (Microsoft Corp., Redmond)

## Acknowledgments

When I started on this Ph.D. journey in 2018, I had no inkling of how much of
a life-altering process it would turn out to be. These last five years have
been absolutely exceptional, and as with all things magical, I split my
acknowledgments for this dissertation into seven parts.

First, I am indebted to my parents for making immense sacrifices such that I
get the best education possible, which in turn enabled me to come further than
I had imagined. I thank my grand-parents for always pushing me to dream
bigger, even if it came at the cost of being away for years on end. I thank my
brother, Abhishek Raj, who has been an inspiration my whole life — if I have
been able to sail in high winds, it’s because I know I have a light to guide
me home. I thank my sister, Shanu Amit Srivastava, who was my first teacher
and instilled in me a love and thirst for learning.

Second, I am infinitely grateful to my supervisor, Sanjeev Khudanpur, for the
constant support and advice over the last several years. Besides teaching me
how to think critically about research questions, I have also learnt from you
the importance of going out of my comfort zone, making strong connections, and
enjoying the process of research. I thank my second advisor, Dan Povey, from
whom I learnt the importance of well-written, open-source code, and which has
since become a guiding principle of my research. I will also forever be
grateful to Dan for offering me a PhD position in his group at a time when I
had no background in speech research. I thank Jinyu Li for not just being a
great mentor, but also for taking out time from managing a large industry
group to be a part of my qualification and thesis committees.

I have been fortunate to have had several unofficial advisors during my time
at JHU, each of whom taught me several things. Shinji Watanabe showed me the
importance of asking big picture questions (in fact, my dissertation research
branched off of working with Shinji on the CHiME-6 project) and of staying
humble in success. From Paola Garcia, I learnt that caring about the
researcher is just as important as caring about their research. Paola also
taught me the fundamentals of speaker diarization, which forms several
chapters of this dissertation. I thank Jan “Yenda” Trmal for his expertise
with Kaldi, and Piotr Zelasko for helping me become a better Python developer.
During this Ph.D., I spent two summers at Microsoft and Meta, respectively. I
thank Jinyu Li, Liang Lu, Zhuo Chen, and Naoyuki Kanda at Microsoft for their
guidance in initiating me into the “end-to-end” multi-talker methods. At Meta,
I thank Ozlem Kalinli for hiring me into the amazing speech team, and Junteng
Jia, Chunyang Wu, and Jay Mahadeokar for giving me the freedom to try and
fail.

My fourth acknowledgment is reserved for friends, the ones I had coming in and
the ones I made along the way. I thank my “B3 family” for always having my
back — many a Sunday afternoon was spent Zoom-ing with this band of brothers
spread across 5 countries even before the pandemic made it cool. I thank my
labmates in the “Kaldi group” for the fruitful discussions and gossip we
shared in Hackerman 322. I had zero knowledge about speech processing when I
joined the program, and much of what I have learnt I owe to David Snyder,
Vimal Manohar, Matthew Wiesner, Matt Maciejewski, Yiming Wang, and Ke Li. I am
indebted to Hainan Xu and Xiaohui Zhang who were incredibly helpful this past
year as I was looking for full-time positions. I have also gained much from
the friendships of Ashish Arora, Dongji Gao, Zili Huang, Ruizhe Huang, Yiwen
Shao, Fei Wu, Amir Hussein, Jonathan Chang, Henry Li, and Cihan Xiao. For
Jinyi Ondel Yang, I reserve a special place in my heart — I cherish our long
walks that made the pandemic a little more sufferable, our expeditions for
Indian, Chinese, and Vietnamese food, and our mutual love for the French
language (and its speakers). Outside the Kaldi group, I thank Elias Stengel-
Eskin, David Mueller, Aaron Mueller, Kelly Marchisio, Suzanna Sia, Mitchell
Gordon, Jacob Buckman, and Craig Guo for (often beverage-infused)
conversations about big ideas in machine learning and beyond. I thank Samik
Sadhu for hosting a number of potluck parties, and Xuan Zhang for accompanying
me to them.

My fifth vote of thanks is owed to the CS and CLSP administrative staff who
ensured that all the technicalities were met so that I could focus on the
research. For this, I tip my hat to Ruth Scally, Lauren Meek, and Kim Franklin
for their continued support with all things admin. I also thank Joe McKnight
at the HLTCOE for always being proactive about resource allocation on that
cluster, without which these experiments could not have been performed.

This dissertation is the result of several publications which would not have
seen the light of day without the efforts of all my amazing co-authors. Beside
the individuals mentioned earlier, I thank Aswin Subramanian, Jesus Villalba,
Pavel Denisov, Hakan Erdogan, Mao-kui He, Takuya Yoshioka, Andreas Stolcke,
Katerina Zmolikova, Marc Delcroix, Yashesh Gaur, Samuele Cornell, Xuankai
Chang, and Niko Moritz. If I have seen further, it is by standing on the
shoulders of these giants.

Finally, I am grateful to Marie-Philippe Gill, whose love and support has
stayed strong through the hills and valleys of this journey. I will always
treasure these years at Johns Hopkins, not just because they made me a better
person and a better researcher, but also because it was here that I met the
love of my life. When I count my blessings, I count you twice.

###### Table of Contents

  1. Abstract
  2. Acknowledgments
  3. 1 The “Who Spoke What“ Problem
    1. 1.1 Motivation
    2. 1.2 Background
    3. 1.3 Problem definition
    4. 1.4 Data
    5. 1.5 Evaluation metrics
      1. 1.5.1 Diarization metrics
      2. 1.5.2 ASR metrics
      3. 1.5.3 Signal-level metrics
      4. 1.5.4 Multi-talker ASR metrics
    6. 1.6 Outline of the dissertation
    7. 1.7 Publications and Code
  4. 2 Overlap-aware Speaker Diarization using Spectral Clustering
    1. 2.1 A background in speaker diarization
    2. 2.2 The clustering paradigm
      1. 2.2.1 Speech activity detection
      2. 2.2.2 Embedding extraction
      3. 2.2.3 Scoring
      4. 2.2.4 Clustering
        1. 2.2.4.1 Agglomerative hierarchical clustering
        2. 2.2.4.2 Spectral clustering
    3. 2.3 Overlap-aware diarization
    4. 2.4 Methodology
      1. 2.4.1 Estimating number of speakers
      2. 2.4.2 Multi-class spectral clustering
      3. 2.4.3 Extension to overlap-aware clustering
    5. 2.5 Overlap detection
    6. 2.6 Experimental setup
      1. 2.6.1 Datasets
      2. 2.6.2 Baselines
      3. 2.6.3 Implementation details
    7. 2.7 Results and discussion
      1. 2.7.1 Overlap detection on AMI
      2. 2.7.2 Diarization results for AMI
      3. 2.7.3 Analysis on LibriCSS
    8. 2.8 Conclusion
  5. 3 Ensembles of Diarization Systems
    1. 3.1 Introduction
    2. 3.2 System combination with DOVER-Lap
      1. 3.2.1 Problem formulation
      2. 3.2.2 Preliminary: DOVER
        1. 3.2.2.1 Label mapping
        2. 3.2.2.2 Label voting
    3. 3.3 Label mapping as a graph partitioning problem
      1. 3.3.1 Some properties of graph $\mathcal{G}$
      2. 3.3.2 An exponential algorithm based on clique enumeration
      3. 3.3.3 Polynomial-time Hungarian method
        1. 3.3.3.1 Definitions and key concepts
        2. 3.3.3.2 The Hungarian method
        3. 3.3.3.3 Algorithm
    4. 3.4 Label voting in DOVER-Lap
    5. 3.5 System combination experiments
      1. 3.5.1 Setup
      2. 3.5.2 Diarization results on AMI
      3. 3.5.3 Diarization results on LibriCSS
    6. 3.6 Late fusion for multi-microphone diarization
    7. 3.7 Conclusion
  6. 4 Target Speaker Extraction with Guided Source Separation
    1. 4.1 Target speaker extraction
    2. 4.2 Guided source separation
      1. 4.2.1 De-reverberation using WPE
      2. 4.2.2 Mask estimation using CACGMMs
      3. 4.2.3 Mask-based MVDR beamforming
    3. 4.3 GPU-accelerated inference
      1. 4.3.1 Segment batching
      2. 4.3.2 CPU-based data-loaders
      3. 4.3.3 Frequency batching
      4. 4.3.4 Einsum path optimization
    4. 4.4 Implementation details
    5. 4.5 Experiments
      1. 4.5.1 Setup
      2. 4.5.2 Results
        1. 4.5.2.1 Signal-level enhancement
      3. 4.5.3 Improvement in target-speaker information
        1. 4.5.3.1 Far-field ASR performance
        2. 4.5.3.2 Which factors are most important for GSS?
        3. 4.5.3.3 Analysis of speed-up
    6. 4.6 Conclusion
  7. 5 A Modular Framework for Multi-talker Speech Recognition
    1. 5.1 Probabilistic formulation of multi-talker ASR
      1. 5.1.1 Overlap-aware diarization
      2. 5.1.2 Target-speaker extraction
      3. 5.1.3 Automatic speech recognition
    2. 5.2 Experimental setup
    3. 5.3 Results & Discussion
      1. 5.3.1 Results for different benchmarks
      2. 5.3.2 Effect of overlap-aware diarization
      3. 5.3.3 Effect of target-speaker extraction
      4. 5.3.4 Qualitative analysis
    4. 5.4 Limitations
  8. 6 Streaming Unmixing and Recognition Transducers
    1. 6.1 Introduction
    2. 6.2 Related Work
    3. 6.3 Multi-talker ASR with transducers
      1. 6.3.1 Channel assignment as graph coloring
      2. 6.3.2 Heuristic error assignment training (HEAT)
      3. 6.3.3 HEAT vs. PIT
    4. 6.4 The SURT model
      1. 6.4.1 Network architecture
        1. 6.4.1.1 Unmixing module
        2. 6.4.1.2 Chunk width randomization
        3. 6.4.1.3 Recognition module
      2. 6.4.2 Training objective
      3. 6.4.3 Mixture simulation
      4. 6.4.4 Pre-training & adaptation
    5. 6.5 Experimental Setup
      1. 6.5.1 Evaluation
      2. 6.5.2 Implementation details
    6. 6.6 Results & Discussion
      1. 6.6.1 Results on LibriCSS
      2. 6.6.2 Effect of network architecture
      3. 6.6.3 Effect of auxiliary objectives
      4. 6.6.4 Effect of pre-training
      5. 6.6.5 Measuring leakage and omission
      6. 6.6.6 Results on AMI and ICSI
    7. 6.7 Conclusion
  9. 7 Speaker Attribution in the SURT Framework
    1. 7.1 Introduction
    2. 7.2 Preliminary
      1. 7.2.1 Speech recognition with neural transducers
      2. 7.2.2 Multi-talker ASR with SURT
    3. 7.3 SURT for speaker-attributed transcription
      1. 7.3.1 Auxiliary speaker transducer
      2. 7.3.2 Synchronizing speaker labels with ASR tokens
      3. 7.3.3 Maintaining state across utterance groups
        1. 7.3.3.1 What does the auxiliary encoder encode?
        2. 7.3.3.2 The speaker prefixing method
    4. 7.4 Experimental Setup
      1. 7.4.1 Network architecture
      2. 7.4.2 Data
      3. 7.4.3 Training details
      4. 7.4.4 Evaluation
    5. 7.5 Results & Discussion
      1. 7.5.1 RNN-T vs. HAT for speaker-agnostic ASR
      2. 7.5.2 Sequential vs. joint training
      3. 7.5.3 Auxiliary encoder position
      4. 7.5.4 Effect of left context
      5. 7.5.5 Utterance-group evaluation on AMI
      6. 7.5.6 Full-session evaluation on AMI
    6. 7.6 Conclusion
  10. 8 Conclusion and Future Work
    1. 8.1 Summary of contributions
    2. 8.2 Other open-source work
  11. A Dataset Details
    1. A.1 LibriCSS
    2. A.2 AMI
    3. A.3 ICSI
    4. A.4 AliMeeting
  12. B Proofs for DOVER-Lap Label Mapping Algorithms
    1. B.1 Proof of Lemma 3.3.1
    2. B.2 Proof of Theorem 3.3.7
    3. B.3 Proof of Lemma B.4.2
    4. B.4 Label Mapping with Randomized Local Search
      1. B.4.1 Preliminary: deterministic local search
      2. B.4.2 Extension to randomized case

###### List of Tables

  1. 1.1 A summary of tasks related to the problem of speaker-attributed multi-talker speech recognition. The two sections denote a categorization of tasks into “front-end” and “back-end”.
  2. 1.2 Statistics of datasets used for evaluations. The $k$-speaker durations are in terms of fraction of total speaking time.
  3. 1.3 Summary of software contributions as a result of this dissertation.
  4. 2.1 Overlap detection results on AMI mix-headset data, in terms of Precision (%) and Recall (%).
  5. 2.2 Diarization results on AMI mixed-headset eval set.
  6. 2.3 Diarization performance on LibriCSS evaluation set (sessions 2-10), evaluated condition-wise, in terms of % DER. 0S and 0L refer to 0% overlap with short and long inter-utterance silences, respectively. Our overlap detector obtained 96.3% precision and 83.8% recall on this data. RPN does not use ground truth VAD.
  7. 3.1 Notations used in this chapter.
  8. 3.2 System combination experiments using DOVER-Lap on the AMI evaluation set, reported in terms of MS, FA, SE, and DER. We combined 3 overlap-aware hypotheses: overlap-aware SC, VB-based overlap assignment, and regional proposal networks.
  9. 3.3 Diarization performance on LibriCSS evaluation set (sessions 2-10), evaluated condition-wise, in terms of % DER. 0S and 0L refer to 0% overlap with short and long inter-utterance silences, respectively. The DL results are using rank-based weighting.
  10. 3.4 Diarization result break-down on LibriCSS evaluation set, in terms of % missed speech (MS), false alarm (FA), and speaker confusion (Conf.). The numbers in smaller font are the corresponding error rates computed on only the overlapping regions.
  11. 3.5 Diarization results for multichannel LibriCSS evaluation set. Late fusion using DL achieved better performance compared to early fusion based on dereverberation and beamforming.
  12. 3.6 Summary of DOVER-Lap usage in major speaker diarization and multi-talker ASR community challenges.
  13. 4.1 Signal-level enhacement performance of GSS in terms of PESQ, SI-SDR, and STOI metrics. For each metric, we report the measure on the input mixture (in), the enhanced signal (out), and the difference ($\Delta$).
  14. 4.2 Improvement in target-speaker information for enhanced signal compared to mixed signal, measured in terms of $\Delta_{\text{spk}}$. The columns denote the speaker embedding extractor used.
  15. 4.3 Comparison of close-talk and far-field ASR performance for meeting datasets. The GSS setting uses 7 channels for LibriCSS and 8 channels for AMI and AliMeeting. †LibriCSS IHM refers to the corresponding LibriSpeech utterances. #For AliMeeting, the numbers are CER.
  16. 4.4 Compute time for our GSS implementation compared with original on CHiME-6 dev set, using all available channels, 15s context, and 20 BSS iterations. “Time” is the actual wall clock time (in hours), while “cum. time” is the effective total time for all jobs. Speedup is the ratio of the cumulative times.
  17. 5.1 WER (or CER) results using an oracle diarization system and GSS. These represent the minimum achievable cpWER (or cpCER) under the modular framework using the same ASR.
  18. 5.2 Effect of diarization and GSS components on speaker-attributed ASR, as measured by cpWER (or cpCER).
  19. 5.3 Examples of speaker-attributed transcription for a short segment of the session ES2011a from AMI dev set, between 817s and 833s. The first block shows the reference transcript for this segment. Each line in the transcript denotes a different speaker. Different segments of the same speaker are separated with a pipe (“|”) character.
  20. 6.1 Performance of SURT on (a) “anechoic” and (b) “replayed” versions of LibriCSS test set. The SURT 2.0 models were decoded using beam search with a beam size of 4.
  21. (a) Anechoic
  22. (b) Replayed
  23. 6.2 Effect of architectural choices for various components, shown on “anechoic” LibriCSS test set. The last row denotes the final network architectures for SURT.
  24. 6.3 Effect of auxiliary objectives on “anechoic” LibriCSS test set. All models used the SURT-base architecture.
  25. 6.4 Comparison of leakage@4 and omission@4 with insertion and deletion errors on the “anechoic” LibriCSS dev set.
  26. 6.5 Results on the AMI and ICSI test sets, under different microphone settings, using SURT base and large models.
  27. 6.6 WER breakdown on the AMI test set for the SDM microphone condition, using SURT base and large models.
  28. 7.1 Statistics of datasets used for evaluations. The overlap durations are in terms of fraction of total speaking time.
  29. 7.2 Comparison of different training strategies for SURT with auxiliary speaker branch.
  30. 7.3 Speaker-attributed ASR performance on LSMix dev for different positions of the auxiliary encoder. $\mathbf{h}_{l}$ denotes the hidden representation at the $l^{\mathrm{th}}$ block of the main zipformer encoder, and $\mathbf{h}_{0}^{\mathrm{aux}}$ is the input to the auxiliary encoder.
  31. 7.4 Performance of SURT models (with and without speaker prefixing) for different conditions on AMI test set, evaluated on utterance groups. “ORC” denotes the ORC-WER metric, and is the same for all models.
  32. 7.5 Breakdown of model (A)’s performance on IHM-Mix test set by number of speakers in the utterance group.
  33. 7.6 Full-session evaluation cpWER (%) on AMI test set. We also report the ORC-WER for the same outputs (evaluated on utterance groups).

###### List of Figures

  1. 1.1 Toy examples to demonstrate differences of multi-talker WER definitions.
  2. (a)
  3. (b)
  4. 2.1 An illustration of the speaker diarization task. The system estimates $N=3$ speakers in the recording.
  5. 2.3 Architecture of the neural network used for frame-level classification for overlap detection.
  6. 2.5 T-SNE plots of x-vector embeddings for (a) non-overlapping, and (b) overlapping segments for the recording EN2002a in the AMI eval set (containing 4 speakers). Colors denote the speaker assigned to the segment. For (b), each color represents a distinct pair of speaker labels, resulting in 6 differently colored clusters.
  7. (a)
  8. (b)
  9. 3.1 An illustration of overlapping output produced by DOVER-Lap for overlapping hypotheses.
  10. 3.2 Illustration of the label mapping problem as a graph $\mathcal{G}$ for the case of $K=3$. $V_{1}$ denotes the clique formed by vertices $(u_{1}^{1},u_{2}^{2},u_{3}^{3})$. $\Delta(u)$ represents the segments where speaker $u$ is active in the recording.
  11. 3.3 Partition weight $w(\Phi)$ versus diarization error rate (DER) for three arbitrarily chosen recordings from the AMI evaluation set, showing that DER tends to improve with weight.
  12. 3.4 Computation of the cost tensor $\mathbf{C}$ for the DOVER-Lap label mapping algorithm.
  13. 3.5 Label mapping time (in ms) for combining different number of hypotheses on the AMI and LibriCSS data. The y-axis is logarithmic.
  14. 4.1 The target speaker extraction problem, and illustration of auxiliary cues. Adapted from [1].
  15. 4.2 An overview of the guided source separation (GSS) method for target-speaker extraction.
  16. 4.3 Overview of batch processing for GPU-accelerated GSS. Solid and dotted lines denote GPU-bound and CPU-bound operations, respectively. The WPE module is not shown.
  17. 4.4 Representative output of profiler during enhancement of a single recording. Full stats are available at this https url.
  18. 4.5 Average WER for different microphone settings and overlap ratios.
  19. 4.6 Impact of several factors on ASR performance. In each figure, the left and right y-axes denoten WERs for LibriCSS (test) and AMI (dev), respectively, with the axes scaled according to the range of corresponding WER values.
  20. 5.1 Flow diagram of the modular system for speaker-attributed transcription. The input is a multi-channel recording, and the output is speaker-wise transcripts.
  21. 5.2 Block diagram of the neural transducer.
  22. 6.1 Assigning 5 utterances to 2 output channels. The black dashed boxes represent different utterance groups. Figure based on [2].
  23. 6.2 Example of heuristic error assignment training (HEAT). Each color represent a different speaker. The utterances ($\mathbf{x}_{u}$,$\mathbf{y}_{u}$) are assigned, in order of start times, to the next available channel. Such an assignment avoids the exponential complexity associated with permutation invariant training (PIT).
  24. 6.3 Training dynamics for HEAT versus PIT based loss for different utterance delays: (a) 2.0 s, and (b) 0.0 s.
  25. (a) Delay = 2.0 s
  26. (b) Delay = 0.0 s
  27. 6.4 Block diagram of SURT. $\mathbf{X}$ denotes the input mixture. $\mathbf{X}_{1}$ and $\mathbf{Y}_{1}$ are concatenated sources and references for the first branch (only required during training). The “recognition” component is pre-trained on single-speaker data.
  28. 6.5 Overview of the streaming dual path LSTM model. The intra-chunk LSTM is bidirectional, whereas the inter-chunk LSTM is unidirectional.
  29. 6.6 Illustration of the zipformer encoder architecture. The encoder contains multiple “blocks” running at different frame rates (left). Each block contains several “layers” (middle), and each layer performs self-attention twice with shared attention weights (right).
  30. 6.7 Mixture simulation workflow for LibriSpeech-based training. Gray cylinders denote external data used during simulation: LibriSpeech utterances, statistics from LibriCSS, real RIRs, and MUSAN noises. The simulation workflow can be conceptually divided into three phases: (i) mixing, which creates anechoic meetings, (ii) reverberation, which convolves with RIRs, and (iii) augmentation, which perturbs the reverberant mixtures with various schemes. The dotted path is optional for anechoic training.
  31. 6.8 Occupation probabilities of nodes in the $T\times U$ lattice for both output channels, for models trained with and without auxiliary CTC loss ($\mathcal{L}_{\text{ctc}}$. $T$ and $U$ are on $x$ and $y$ axes, respectively. For this mixture, $T=395$, $U_{1}=79$, and $U_{2}=44$. The double arrows between the plots denote the reference segments: red for channel 1 and green for channel 2. Brighter colors denote higher occupation probabilities.
  32. 6.9 Effect of transducer pre-training with LibriSpeech. WERs are shown for the LibriCSS dev set after each training epoch. The dotted horizontal lines show the final WERs on test set with model averaging.
  33. 6.10 Effect of decoding beam size on insertion and deletion errors, versus effect on leakage and omission (for $n=4$), for SURT-base models with and without adaptation, for (a) “anechoic” and (b) “replayed” conditions, averaged across all overlap settings. The top row shows insertion and deletion errors, while the bottom row contains leakage@4 and omission@4.
  34. 7.1 Auxiliary speaker transducer (red box) with shared blank label. The auxiliary encoder takes as input a hidden layer representation $\mathbf{h}_{n}$ from the main encoder, and generates $\mathbf{f}_{1:T}^{\mathrm{aux}}$. The blank logit $\mathbf{z}[0]$ from the main joiner is shared with the speaker branch to compute the HAT loss.
  35. 7.2 Illustration of problem caused by relative speaker label within utterance groups. For each group, speakers are assigned labels in FIFO order, which may result in speaker permutation errors for the recording.
  36. 7.3 Projections of auxiliary encoder representations for a subset of LSMix dev. Each point denotes the representation of one speaker in a mixture, averaged over the frames on which the model emits a non-blank label. (a) and (b) denote UMAP projection, and (c) shows LDA projection using absolute speaker classes.
  37. (a)
  38. (b)
  39. (c)
  40. 7.4 Utterance group statistics of the AMI meeting corpus: (a) number of speakers in the group, and (b) number of speakers seen before the group.
  41. 7.5 Effect of auxiliary encoder left context on (a) WDER and (b) cpWER. Dotted lines show best performance using $\infty$ left context.
  42. 7.6 Average per-frame entropy for utterance groups with different number of speakers.

##  Chapter 1 The “Who Spoke What“ Problem

###  1.1 Motivation

Advances in artificial intelligence (AI) in the last several decades have been
limited to task-specific improvements that were strictly categorized into
different modalities. For instance, methods have been developed to detect and
segment objects in images and video (vision), to analyze sentiments present in
textual extracts (language), and to transcribe an audio recording in noisy
conditions (speech). With the rise of deep neural networks and the convergence
of modeling strategies used to address these diverse tasks and modalities, the
next version of AI is expected to comprise systems that can learn
simultaneously from several sensors, similar to how humans learn. Neuro-
symbolic learning methods are expected to be complemented by extensive
knowledge graphs to enable common sense reasoning in complex scenarios, such
as participating in human conversations.

Since the first speech recognition systems were built more than 50 years ago,
improvement in voice technology has enabled applications such as voice
assistants on smartphones, semi-automated customer support, and embedded
systems. Through years of research on speech enhancement and robust speech
processing, these systems are now deployed in diverse settings such as on
smart home speakers and vehicle controls. Nevertheless, present systems are
passive listeners which transcribe single-speaker utterances and feed into
downstream language understanding components. Conversational intelligence of
the future is expected to comprise systems that can actively participate in
human conversations, including scenarios such as note-taking or fact-checking
in meetings, collaborative learning in education, or simply recommending
grocery items in households. While such systems would require intelligence in
diverse modalities — dialog systems for context handling, emotion recognition
from speech and video, common sense reasoning, to name a few — their ability
to recognize free-flowing multi-party conversations is a crucial and complex
task that needs to be solved.

###  1.2 Background

Multi-talker speech recognition of free-flowing conversations is a well-known
problem. In the offline setting, a long-form audio recording (ranging between
several minutes up to a few hours) is provided, and the expected output is a
speaker-attributed transcription with time marks. When deployed online,
streaming audio is provided as input with the same transcription requirements.
In addition to their use in conversational agents, these systems have several
other applications — such as real-time meeting transcription for hearing-
impaired participants, and generating automatic subtitles for movies or video
streams, to name a few. When used in conjunction with language understanding
or dialog systems, they also enable real conversational AI. However, systems
for solving this problem are still far from human parity, often achieving
between 30% and 50% error rates on the task. As such, the problem is rewarding
both in its technical difficulty as well as its ramifications on real-world
applications.

In the 2000s, several advances were made as a result of NIST evaluations [3]
and the AMI project [4] that were aimed at tackling the multi-talker
recognition problem, primarily in the offline setting. More recently,
challenges such as DIHARD [5] and CHiME [6] have focused on diarization and
speech recognition tasks in very challenging scenarios. As a result, we are
closer today to solving the multi-talker conversation transcription problem
than we have ever been.

Nevertheless, there are several challenges yet to be addressed. While
recognition of clean, read speech is claimed to have surpassed human
parity111Such claims must always be taken with a grain of salt, for they are
made on specific data sets, and their generality is rarely (if ever) tested
[7, 8], the same cannot be said of conversations in the wild. A careful
selection of deep learning advances in acoustic modeling, language modeling,
and system combination was shown to reach professional transcription levels in
conversational speech [9], but this evaluation was limited to telephonic
conversations between two speakers. Although this is an important development,
real multi-talker conversations raise many additional challenges, most notably
the case of overlapping speech. Studies have shown that meetings can contain
up to 20% overlapping speech [4], which has implications for both diarization
and ASR — diarization systems which make single-speaker assumptions miss the
interfering speaker completely, and ASR systems trained on clean utterances
are more error-prone on these overlapped regions. Combined with the effect of
non-stationary noise and reverberation in real recordings, the error rates in
these settings may be degraded by up to 86% [10] in meetings, and 52% in
dinner-party settings [6]. Real-time recognition adds an extra layer of
difficulty to this problem.

In popular literature, the challenge posed by overlapped speech is often
referred to as the “cocktail party problem”, and is challenging enough that it
encompasses several modules that are entire fields in speech processing
research. The conventional approach for multi-talker ASR is through a cascade
of front-end and back-end components, where a separation module feeds into a
single-talker ASR. While this is an appealing solution, and several advances
have indeed been made in speech enhancement (including separation), most of
these techniques are designed for (and evaluated on) short, fully overlapping
(and often simulated) mixtures. In several cases, they also make unrealistic
assumptions, such as prior knowledge of the number of speakers in the mixture.
It may further be preferable from an application perspective to have fewer
independent components in the pipeline, since cascaded modules tend to
compound the overall latency in deployed systems. Recently, there have been
efforts towards “continuous speech separation,” which seeks to situate
separation techniques in more realistic settings of long-form conversations
containing partially overlapped speech [11], such as that found in multi-
talker conversations.

The diarization and ASR communities have independently sought to develop
methods that handle multi-talker overlapping speech. For diarization, existing
approaches to solve the overlap problem involve using externally trained
overlap detectors to identify frames in the recording which contain
overlapping speech. Once overlaps are detected, an “overlap assignment” stage
assigns additional speaker labels to the overlapping frames [12]. A second
class of methods uses end-to-end neural systems to perform overlapping
diarization in a supervised setting [13]. For multi-talker ASR, permutation-
invariant training (PIT), which was first proposed for speech separation, has
successfully been employed [14]; however, the transcriptions produced by such
a method are unordered across utterances, which makes them dependent on an
external speaker tracking or diarization module. A new framework called
serialized output training [15] aims to mitigate some of the issues with PIT,
and has been used to jointly perform ASR, speaker identification, and counting
[16, 17]. Similarly, noise robust ASR and diarization continues to be an
important direction of research [18]. In addition to improvements in speech
enhancement [19], existing research has explored noise-aware and multi-
condition training for ASR [20], and feature mapping for diarization [21].

With these advancements in diarization and ASR systems, there is increasing
interest in developing systems that perform multi-talker speech recognition
for unsegmented recordings. The latest edition of the CHiME challenge [6]
included a track for evaluating systems for dinner-party conversations. An
iterative training strategy combining clustering-based diarization with
target-speaker ASR has been proposed recently [22]. The need for controlled
but realistic data to investigate such systems has resulted in several new
datasets such as LibriCSS [11] and LibriMix [23]. The research agenda at the
JSALT 2020 workshop222https://www.clsp.jhu.edu/workshops/20-workshop/ included
a project aimed at “building fully contained multi-talker audio transcription
systems based on speech separation and extraction”.

Due to the amount of research conducted on the cocktail-party problem and its
various subproblems, it is near impossible to provide a comprehensive review
of past work. Instead, we will discuss the relevant background work for each
chapter as we proceed through the dissertation. In the remainder of this
chapter, we will define the core problem that is addressed in this
dissertation, along with the relevant datasets and evaluation metrics. We will
also provide a brief outline of the dissertation, including a summary of its
two parts.

###  1.3 Problem definition

Our objective in this work is to solve the problem of speaker-attributed
multi-talker speech recognition. Given a single or multi-channel recording
$\mathcal{R}$ (such as that from a meeting), the goal is to transcribe all the
speech in the recording and attribute the words to the corresponding speakers.
Formally, if the recording consists of $K$ speakers, and $\mathbf{w}_{k}$
denotes the sequence of words uttered by speaker $k$, we aim to find a mapping
$W$ such that

$W(R)=\\{\mathbf{w}_{1},\ldots,\mathbf{w}_{K}\\}.$ (1.1)

As we will see throughout this dissertation, it is possible to estimate $W$
indirectly by combining several components (which we call the “modular”
approach), or to estimate it directly in an “end-to-end” manner. The former
decomposition results in several problems which are related to the task of
speaker-attributed transcription, as summarized in Table 1.1. In the following
chapters, we will focus on the problems of speaker diarization and target-
speaker extraction as components for one such modular pipeline. Other
combinations of components can be used for different pipelines, as described
in [24]. In Chapter 5, we will show how our modular pipeline falls out from a
probabilistic formulation of the above problem.

Task Input Output Speech enhancement Mixed recording $\mathcal{R}$ Enhanced
recording $\mathcal{R}^{\ast}$ Speech separation Mixed recording $\mathcal{R}$
Separated audio signals $\mathcal{R}_{1},\ldots,\mathcal{R}_{K}$ Target-
speaker extraction Mixed recording $\mathcal{R}$ Speaker identity $k$ Speaker-
specific audio $\mathcal{R}_{k}$ Speaker diarization Mixed recording
$\mathcal{R}$ Homogeneous speaker segments $\\{(\Delta_{j},u_{j}):1\leq j\leq
N\\}$ Speech recognition Segmented utterance $\mathbf{X}_{j}$ Segment
transcript $\mathbf{y}_{j}$ Target-speaker ASR Mixed recording $\mathcal{R}$
Speaker identity $k$ Speaker-specific transcript $\mathbf{w}_{k}$

Table 1.1: A summary of tasks related to the problem of speaker-attributed
multi-talker speech recognition. The two sections denote a categorization of
tasks into “front-end” and “back-end”.

###  1.4 Data

We focus on meeting transcription as an application of multi-talker speaker-
attributed ASR. Throughout this dissertation, we will demonstrate the
performance of our methods on several publicly available meeting benchmarks:
LibriCSS, AMI, ICSI, and AliMeeting. These benchmarks are detailed in Appendix
A, and their summary statistics are shown in Table 1.2. We have selected these
corpora because they provide distant microphone recordings as well as close-
talk recordings for the meeting sessions, which makes it convenient to perform
controlled evaluations, as well as for training models. In this dissertation,
we will often refer to different microphone settings for these corpora:

  1. 1.

IHM: These are individual close-talk microphone recordings, one per
participant, recorded on either headset or lapel microphones.

  2. 2.

IHM-Mix: These are digitally summed versions of the IHM recordings, which
provides overlapped speech conditions without far-field and background noise
artifacts.

  3. 3.

SDM: This refers to single distant microphone, i.e., a recording taken from
one of the far-field microphones.

  4. 4.

MDM: This refers to multiple distant microphones, and the recordings may or
may not be beamformed.

Table 1.2: Statistics of datasets used for evaluations. The $k$-speaker
durations are in terms of fraction of total speaking time.

LibriCSS AMI ICSI AliMeeting Dev Test Train Dev Test Train Dev Test Train Dev
Test Duration (h:m) 1:00 9:05 79:23 9:40 9:03 66:38 2:16 2:45 111:21 4:12
10:46 Num. sessions 6 54 133 18 16 70 2 3 209 8 20 Silence (%) 6.2 6.7 18.1
21.5 19.6 55.2 25.9 25.9 7.11 7.7 8.0 1-speaker (%) 81.3 81.2 75.5 74.3 73.0
82.1 90.3 84.9 52.5 62.1 63.4 2-speaker (%) 18.6 18.5 21.1 22.2 21.0 15.7 9.0
13.6 32.8 27.6 24.9 >2-speaker (%) 0.1 0.4 3.4 3.5 6.0 2.2 0.7 1.4 14.7 10.2
11.7

###  1.5 Evaluation metrics

Our objective in this dissertation is to demonstrate the performance of
modular and end-to-end systems for speaker-attributed multi-talker ASR.
Modular systems comprise a pipeline of speaker diarization, target speaker
extraction, and ASR components, while end-to-end systems seek to directly
estimate speaker-labeled transcripts. In this section, we describe the metrics
that we will use to evaluate the individual components or the final system in
the subsequent chapters.

####  1.5.1 Diarization metrics

We use diarization error rate (DER), as described in [25], to evaluate the
speaker diarization systems proposed in this dissertation. DER comprises the
sum of three different kinds of error rates — missed speech (MS), false alarms
(FA), and speaker confusion (SC) — and is given as

$DER=MS+FA+SC.$ (1.2)

Since speaker diarization systems produce relative speaker labels (and not
absolute labels), we first find the optimal mapping of reference and
hypothesis speakers which would minimize the DER. This is usually done by
formulating the problem as a linear sum assignment problem, and solved using
the Hungarian algorithm [26].

####  1.5.2 ASR metrics

We use the word error rate (WER) metric to evaluate single-speaker ASR
systems. WER is computed as the Levenshtein distance [27] between the
reference $\mathbf{w}^{\ast}$ and hypothesis $\hat{\mathbf{w}}$, and is the
most popular metric for reporting ASR performance. Informally, the Levenshtein
distance between two strings is the minimum number of edits, (insertions,
deletions, and substitutions), needed to transform one string into the other.
The process of alignment can be described as the application of these edits to
$\hat{\mathbf{w}}$, and the best alignment is the one that uses the fewest
number of edits. Note that the Levenshtein distance considers only monotonic,
i.e. left-to-right, alignment of the hypothesis transcript $\hat{\mathbf{w}}$,
with reference transcript, $\mathbf{w}^{\ast}$, and is efficiently computed
via dynamic programming.

####  1.5.3 Signal-level metrics

In Chapter 4, we will describe target speaker extraction (TSE) using guided
source separation [28]. Since the objective of TSE is to estimate clean,
single-speaker signal, given a noisy multi-talker signal as input, we will
additionally use signal-level metrics as an intrinsic measure of system
performance. In particular, we will use the following metrics popular in
speech enhancement literature:

  * •

PESQ [29]: PESQ (Perceptual Evaluation of Speech Quality), originally
developed to assess the quality of speech codecs, measures the similarity
between a reference (original) and a processed (separated) audio signal in
terms of perceived quality. It takes into account various factors related to
human auditory perception, such as loudness, sharpness, and distortion. The
output of PESQ is a single value, typically ranging from -0.5 to 4.5, with
higher values indicating better perceived quality.

  * •

SI-SDR [30]: SI-SDR (Scale Invariant Signal-to-Distortion Ratio) measures the
quality of a separated audio signal by quantifying the ratio between the
target (clean) signal and the unwanted interference or distortion caused by
the separation process. The “scale-invariant” aspect of the metric means that
it is not sensitive to the scaling of the signals, making it more robust in
scenarios where the amplitude of the signals may vary. Mathematically, it is
defined as

$\text{SI-
SDR}=10\cdot\log_{10}\left(\frac{{\|s_{\text{target}}\|^{2}}}{{\|s_{\text{distortion}}\|^{2}}}\right),$
(1.3)

where $s_{\text{target}}$ is the clean signal and $s_{\text{distortion}}$ is
the distortion caused by the enhancement process.

  * •

STOI [31]: STOI (Short-Time Objective Intelligibility) specifically evaluates
the intelligibility of speech by measuring the similarity between a reference
and a processed audio signal in terms of how well the speech can be
understood. STOI takes into account factors related to human auditory
perception, such as the modulation spectrum and the presence of noise. It
operates on short-time frames, which allows it to capture variations in
intelligibility over time. The output of STOI is a value between 0 and 1,
where 1 indicates perfect intelligibility (i.e., the separated speech is
identical to the original), and 0 indicates no intelligibility (i.e., the
separated speech is completely unintelligible).

####  1.5.4 Multi-talker ASR metrics

Our primary metric for evaluating the final speaker-attributed transcription
systems is the concatenated minimum-permutation word error rate (cpWER) [6].
The key idea in cpWER is to find the best permutation between reference and
hypothesis speakers that minimizes the average WER between the speaker’s
concatenated transcripts. Given reference transcripts for a session and the
corresponding hypothesis, the computation follows three steps:

  * •

Concatenate all utterances of each speaker for both reference and hypothesis
files.

  * •

Compute the WER between the reference and all possible speaker permutations of
the hypothesis.

  * •

Pick the lowest WER among them.

In some cases, we may also want to evaluate multi-talker ASR systems without
speaker labels. For example, the SURT model that we describe in Chapter 6
transcribes all the speech in a mixture without attributing the words to
speakers. In this case, we will use the optimal reference combination word
error rate (ORC-WER) metric, proposed concurrently in [32] and [33]. ORC-WER
is used for evaluating systems where the reference contains a list of
(possibly overlapping) segments ordered by start time, and the hypothesis
contains multiple streams of output transcript. Since there is no obvious
mapping from reference segments to the output streams, we find the best
permutation of reference to stream that minimizes the overall word error rate.
[34] proposed a polynomial-time implementation of ORC-WER using multi-
dimensional Levenshtein distance, and released it through the
meeteval333https://github.com/fgnt/meeteval toolkit. They showed that ORC-WER
is a lower bound on cpWER and becomes equal to the cpWER when no speaker
errors are present. We used their open-source implementation for evaluating
our SURT models in this dissertation. The overall algorithm for ORC-WER
computation is given in Algorithm 1. We assume that the references
$\mathcal{R}_{n}$ are ordered according to the start times of utterances.

1

Input: Ref.: $\mathcal{R}_{1},\ldots,\mathcal{R}_{N}$; hyp.:
$\mathcal{H}_{1},\ldots,\mathcal{H}_{C}$

Output: $W_{\text{orc}}$

2

$\mathcal{R}\leftarrow\mathcal{R}_{1}\diamond\ldots\diamond\mathcal{R}_{N}$

// Insert channel change token

3

$\xi\leftarrow\\{\\}$

// Memoize costs to avoid recomputing

4

5 Function  _levenshtein(_$R$ , $H$, $i=\phi$_)_:

6 $K=(R,H,i)$

7 if  _$K$ in $\xi$_ then

8 return $\xi[K]$

9

10 if  _$i\neq\phi$ and $\mathcal{R}[R-1]==\diamond$_ then

// Reached a channel change token

11 $\xi[K]\leftarrow$ levenshtein(_$R-1$ ,$H$,$\phi$_)

12 return $\xi[K]$

13

14 if  _$i=\phi$_ then

$C\leftarrow\emptyset$

// Find minimum over all hypotheses

15 for  _$i$ in range($|\mathcal{H}|$)_ do

16 $C[i]\leftarrow$ levenshtein(_$R$ ,$H$,$i$_)

17

18 $\xi[K]\leftarrow\min(C)$

19 return $\xi[K]$

20

21 else

// Regular Levenshtein update

22 if  _$R=0$_ then

23 $c\leftarrow\sum_{h\in H}h$

24

25 else if  _$H[i]=0$_ then

26 $c\leftarrow 1$ \+ levenshtein(_$R-1$ ,$H$,$i$_)

27

28 else if  _$\mathcal{R}[R-1]=\mathcal{H}[i][H[i]-1]$_ then

29 $H[i]\leftarrow H[i]-1$

30 $c\leftarrow$ levenshtein(_$R-1$ ,$H$,$i$_)

31 $H[i]\leftarrow H[i]+1$

32

33 else

34 $ins\leftarrow$ levenshtein(_$R-1$ ,$H$,$i$_)

35 $H[i]\leftarrow H[i]-1$

36 $del\leftarrow$ levenshtein(_$R$ ,$H$,$i$_)

37 $sub\leftarrow$ levenshtein(_$R-1$ ,$H$,$i$_)

38 $H[i]\leftarrow H[i]+1$

39

40 $c\leftarrow 1+\min(ins,del,sub)$

41

42 $\xi[K]\leftarrow c$

43 return $\xi[K]$

44

45

46

47return levenshtein(_$|\mathcal{R}|$ ,$\\{|h|:h\in\mathcal{H}\\}$_)

48

Algorithm 1 ORC-WER computation

Fig. 1.1 shows the difference between cpWER and ORC-WER using some toy
examples. For the example shown in Fig. 1.1(a), the hypothesis assigns all
words to the same channel (or speaker). Since ORC-WER is speaker-agnostic, the
resulting error is 0, whereas for cpWER, there are 2 insertions and 2
deletions, resulting in 4 errors. In the example shown in Fig. 1.1(b), both
the metrics result in the same absolute error.

(a)

(b)

Figure 1.1: Toy examples to demonstrate differences of multi-talker WER
definitions, based on Figure 1 in [34]. Each solid box is a word, and grey
hatched box is an utterance. Error counts for ORC-WER and cpWER are shown in
the tables.

###  1.6 Outline of the dissertation

In the previous sections, we have described the problem of speaker-attributed
multi-talker ASR, and the corresponding datasets and evaluation criteria. We
tackle this problem from two perspectives, and this dissertation is also
organized along the same lines.

The first part (i.e., the modular approach) comprises chapters 2, 3, 4, and 5.
Since overlapping speech is a major challenge for multi-talker ASR, we begin
in Chapter 2 by proposing a new method for overlap-aware speaker diarization
using spectral clustering. We show that our method is easy to integrate into
existing clustering-based pipelines and provides significant DER improvements
compared to methods that ignore overlapping speech. In the last few years,
there have been tremendous advances in overlap-aware diarization, with
different approaches having their own advantages and limitations. In Chapter
3, we describe the DOVER-Lap algorithm to ensemble the outputs of these
systems, resulting in significant gains over single-best systems. In the
multi-channel setting, DOVER-Lap can also be used to combine the outputs from
different channels as a late fusion strategy. Once the homogeneous speaker
segments have been identified, we use the guided source separation (GSS)
method to extract speaker-specific signals from the mixture. In Chapter 4, we
describe a GPU-accelerated GSS implementation that provides close to 300x
speed-up for inference, thus providing large RTF improvements for the
pipeline. Finally, we present the full pipeline, along with its probabilistic
formulation, in Chapter 5. Qualitative and quantitative analyses of the
pipeline throws light on the limitations of the modular approach.

The second part of the dissertation describes an alternate end-to-end
perspective in Chapters 6 and 7. In Chapter 6, we first introduce the
Streaming Unmixing and Recognition Transducer (SURT), an extension of the
popular neural transducers for handling multi-talker overlapping speech. SURT
combines “unmixing” and “recognition” components trained end-to-end with an
ASR loss. By using a fixed ordering of references instead of permutation
invariant training, and through various choices in model design, architecture,
training mixture simulation, and objective functions, we show how to train the
SURT models efficiently for speaker-agnostic transcription of real meetings.
Once we have an efficient training pipeline, we extend SURT for speaker-
attributed transcription by adding an auxiliary speaker branch to the
recognition component. For this, we propose blank factorization to synchronize
the emission from the branches, and speaker prefixing to ensure speaker label
consistency through the recording. Our final SURT model shows promising
results on AMI, although there still exists a gap compared to offline, modular
systems.

###  1.7 Publications and Code

The work described in this dissertation has been published at the following
venues.

  * •

Chapter 2: [35]

  * •

Chapter 3: [36, 37]

  * •

Chapter 4: [38]

  * •

Chapter 5: [39]

  * •

Chapter 6: [33, 40]

  * •

Chapter 7: [41]

Additionally, this dissertation has also resulted in open-source software
contributions, as summarized in Table 1.3. In several cases such as Chapters 3
and 4, we implemented stand-alone Python packages which can be integrated into
existing frameworks or recipes. For example, our GSS implementation has
recently been used as part of the community baseline in the CHiME-7 DASR
challenge [42]. For others, such as the SURT model described in Chapters 6 and
7, the open-source implementation was done as part of a popular framework such
as icefall. In such cases, the recipe was also accompanied by development and
contributions in the k2 and Lhotse toolkits.444This dissertation was partially
supported by an NSF CIRC grant for the development of next-generation speech
tools (Lhotse, k2, and icefall.)

Chapter GitHub repositories Remarks 2 desh2608/diarizer desh2608/spyder
Recipes for clustering-based diarization Python package for fast DER
computation 3 desh2608/dover-lap Python implementation of DOVER-Lap 4
desh2608/gss CuPy-based fast GSS with recipes 5
desh2608/icefall/tree/multi_talker Icefall recipes for multi-talker ASR 6 & 7
k2-fsa/icefall LibriCSS and AMI SURT recipes

Table 1.3: Summary of software contributions as a result of this dissertation.

##  Chapter 2 Overlap-aware Speaker Diarization using Spectral Clustering

One of the challenges of multi-talker speaker-attributed ASR is to identify
and demarcate unique speakers in the recording. In this chapter, we will begin
by formalizing this “speaker diarization” problem, and then describe a popular
clustering-based paradigm to solve it. We will identify how the naive
clustering solution fails to address overlapping speech, resulting in high
error rates for meeting-like scenarios. Finally, we will show that an
alternative formulation of multi-class spectral clustering allows us to
incorporate an external overlap detection module into the process, effectively
reducing overlap related errors in the diarization output.

###  2.1 A background in speaker diarization

Speaker diarization (or “who spoke when”) is defined as the task of segmenting
speech into speaker-homogeneous regions [43, 44]. The input in this task is an
audio recording (single or multi-channel) which may extend from a few minutes
up to several hours (or days, such as in scenarios like child language
acquisition). The desired output is a set of (possibly overlapping) segments
with associated speaker labels. Formally, given an audio recording $R$, the
diarization system is a function $f$ that estimates a set of speaker-labeled
time segments, i.e.,

$f(R)=\\{(\Delta_{j},u_{j}):1\leq j\leq N\\},$ (2.1)

where $\Delta_{j}=(t_{j}^{\mathrm{st}},t_{j}^{\mathrm{en}})$ denotes the
segment boundaries and $u_{j}\in[K]$ denotes the speaker label. $K$ and $N$
are the estimated number of speakers and speaker-homogeneous segments in $R$,
respectively. Depending on the use-case, the true value of $K$ may or may not
be known beforehand.

Figure 2.1: An illustration of the speaker diarization task. The system
estimates $N=3$ speakers in the recording.

The speaker labels $u_{j}$ are relative labels, i.e., they are only consistent
within the recording. Fig. 2.1 illustrates an example of the diarization task
where the system predicts $N=4$ segments containing $K=3$ speakers. Note that
some parts of the audio may be “non-speech,” i.e., they do not have any
assigned speaker (e.g., the segment between $t_{2}^{\mathrm{en}}$ and
$t_{3}^{\mathrm{st}}$, whereas some other parts may have “overlapping speech”
and are assigned to multiple speakers (e.g., the segment between
$t_{2}^{\mathrm{st}}$ and $t_{1}^{\mathrm{en}}$).

###  2.2 The clustering paradigm

The conventional solution to speaker diarization is based on the “clustering”
principle. This is a pipeline consisting of four major components, as shown in
Fig. 2.2. These components are described in the following sections.

Figure 2.2: Components of the clustering-based diarization system (in dotted
box). Green arrows and boxes show the new components for overlap-aware
diarization (Section 2.4).

####  2.2.1 Speech activity detection

First, a speech activity detection (SAD) module is used to filter out the non-
speech regions of the recording. Traditional methods in SAD often rely on
signal processing techniques, such as energy-based thresholding [45], analysis
of the frequency modulation including harmonics [46] and formants [47], and
statistical modeling [48, 49]. These methods analyze the characteristics of
the audio signal to distinguish between speech and non-speech segments. While
effective in controlled environments, they may face challenges in noisy or
dynamic settings. Machine learning and deep learning techniques have
significantly advanced the field of SAD. Supervised learning approaches, using
annotated datasets, allow models to learn discriminative features for
differentiating speech from non-speech segments. Popular algorithms include
support vector machines (SVMs) [50], Gaussian mixture models (GMMs) [51],
hidden Markov models (HMMs) [52], and more recently, deep learning
architectures like convolutional [53, 54] and recurrent neural networks [55,
56]. Unsupervised and semi-supervised techniques have also emerged to address
scenarios where labeled data is scarce [57, 58]. Additionally, context-aware
approaches have gained prominence, leveraging additional information like
contextual cues, speaker characteristics, or linguistic features to enhance
SAD performance [59, 60].

In this chapter, since our objective is to improve the clustering stage using
external overlap information, we will use an oracle SAD to detect speech
segments. Later, in Chapter 5, we will replace this oracle with a neural
network based SAD to evaluate the full pipeline of speaker-attributed ASR.
Regardless of the SAD model used, we can mathematically formulate the problem
as

$\mathrm{SAD}(R)=\\{\Delta_{n}^{\mathrm{SAD}}:1\leq n\leq
N_{\mathrm{SAD}}\\},$ (2.2)

where $\Delta_{n}^{\mathrm{SAD}}$, as defined in (2.1), denotes a speech
segment in $R$, and $N_{\mathrm{SAD}}$ is the number of speech segments
identified. Note that each of these speech segments may contain multiple
speakers at this point.

####  2.2.2 Embedding extraction

Once the non-speech regions have been discarded, the speech regions of the
recording, i.e.,
$\\{\Delta_{1}^{\mathrm{SAD}},\ldots,\Delta_{N_{\mathrm{SAD}}}^{\mathrm{SAD}}\\}$,
are divided into small, overlapping subsegments (or window), under the
assumption that no speaker changes would happen within these subsegments.
Conventionally, a sliding window of size 1.5s and shift 0.75s is used to
obtain these subsegments. A pre-trained speaker embedding extractor is then
used to obtain fixed-dimensional embeddings, which we denote as
$\mathbf{s}_{1},\ldots,\mathbf{s}_{N}$, where
$\mathbf{s}_{n}\in\mathbb{R}^{d}$ is the embedding for one such window. The
diarization process assigns one or more speaker labels to each of these $N$
windows.

Originally, unsupervised GMM-based methods, such as i-vectors [61] were used
to obtain $\\{\mathbf{s}_{n}\\}$, the fixed-dimensional embeddings. However,
deep neural network (DNN) based techniques, such as d-vectors [62] and
x-vectors [63] have become more popular in the last few years due to their
better speaker discriminative capabilities. Researchers have also explored
using attention-based methods [64, 65], triplet loss [66], and domain
adaptation [67] to improve the speaker embeddings, which in turn improves
their applicability in diarization. In this chapter, we use the x-vector based
method to obtain embeddings.

The x-vector model [63] is based on time-delay neural networks (TDNNs) [68],
which model temporal dependencies in speech, usually better than RNNs or
multi-layer perceptrons (MLP) with context windows. The architecture consists
of TDNN layers operating at the frame level, followed by statistics pooling
layers operating at the segment level. These pooling layers mitigate the
dependency on the utterance length, and are especially advantageous for
speaker diarization since these systems process segments that are shorter than
the typical window length for speech recognition. The x-vector neural network
is trained in a supervised manner with a speaker classification objective. In
Chapter 5, we will replace the TDNN-based x-vector with a wide ResNet
architecture that has been shown to outperform the original model on speaker
recognition tasks [69].

####  2.2.3 Scoring

Once we have the embeddings $\mathbf{s}_{n}$, we score them pair-wise using
some distance metric. The simplest of such metrics is the cosine similarity
between two vectors, which is defined as

$\cos(\theta)=\frac{\mathbf{s}_{1}\cdot\mathbf{s}_{2}}{\lVert\mathbf{s}_{1}\rVert\lVert\mathbf{s}_{2}\rVert}.$
(2.3)

Cosine similarity is a popular metric in speaker diarization systems which use
spectral clustering or mean shift clustering algorithms. It does not require
any training or parameter tuning; however, it cannot project or weight the
embedding vectors to enhance the similarity measurement.

Another distance metric often used in speaker recognition literature is
probabilistic linear discriminant analysis (PLDA) [70]. PLDA produces a
comparison score, which is the log of the ratio of the probability that the
embeddings were produced by the same speaker, versus the probability that they
were produced by different speakers. If the comparison score is above a
decision threshold $\theta$, we posit that the embeddings belong to the same
speaker, otherwise, we declare that they belong to different speakers. Since
these PLDA scores may be negative and are asymmetric by definition, they
cannot directly be used for spectral clustering, since the method requires a
positive, symmetric affinity matrix. Although these limitations can be
bypassed using shifting and symmetrization steps, we just use cosine
similarity in this chapter as our distance metric. This results in an affinity
matrix, $\mathbf{A}\in\mathbb{R}^{N\times N}$, given as

$\mathbf{A}_{ij}=\frac{\mathbf{s}_{i}\cdot\mathbf{s}_{j}}{\lVert\mathbf{s}_{i}\rVert\lVert\mathbf{s}_{j}\rVert}.$
(2.4)

####  2.2.4 Clustering

The final step in the diarization process, and the one we are most interested
in, is clustering performed on the resulting affinity matrix. Among the most
widely used clustering methods in speaker diarization are agglomerative
hierarchical clustering (AHC) and spectral clustering [71].

#####  2.2.4.1 Agglomerative hierarchical clustering

AHC is based on an iterative process of merging the existing clusters of
speech segments until the distance of the closest cluster pair meets a
predetermined stopping criterion [72]. Given the affinity matrix $\mathbf{A}$,
which provides pair-wise similarity scores between the $N$ sub-segment
embeddings, an iterative process is followed until some stopping criterion is
reached. We start by assigning each of the $N$ embeddings to a unique cluster
(or speaker). At each step, the two closest clusters are merged based on a
linkage criterion, such as the distance between their closest (single
linkage), farthest (complete linkage), or average (average linkage) data
points. After merging the clusters, $\mathbf{A}$ is updated to reflect the
distances between the new clusters and the remaining clusters. This iterative
merging process is often visualized as a dendrogram.

For speaker diarization tasks, the merging process can be stopped using either
a threshold for similarity or a target number of speakers. Usually, the
stopping criterion is adjusted based on a development set to get an accurate
number of clusters. If the number of speakers is known or estimated in
advance, the AHC process can be stopped when the number of merged clusters
reaches the predetermined number of speakers.

#####  2.2.4.2 Spectral clustering

Spectral clustering was first applied to speaker diarization in [73] using the
Ng-Jordan-Weiss (NJW) algorithm [74]. [75] extended this to the case of an
unknown number of speakers by using the eigengap criterion. Agglomerative and
spectral clustering methods for meeting diarization were compared in [71].
After i-vectors were proposed for speaker recognition [61], they were combined
with cosine scoring and spectral clustering to perform diarization in [76]. It
was further observed that spectral clustering was more robust to non-
stationary environmental noise compared to other clustering methods [77]. More
recently, with the ubiquitousness of deep neural networks, several researchers
have proposed methods to incorporate DNNs with spectral clustering. [78]
proposed a supervised method to measure the similarity matrix between all
segments of an audio recording with BLSTMs, and applied spectral clustering on
top of the similarity matrix. Other approaches use DNN-based speaker
embeddings, such as x-vectors [63], to compute the similarty matrix between
segment pairs [79, 80]. Additionally, [79] introduced $p$-binarization and
normalized maximum eigengap (NME) techniques to automatically estimate the
number of speakers in the recording.

The traditional approach to spectral clustering is using the algorithm
presented in [74]. This algorithm consists of the following steps:

  1. 1.

The Laplacian, $\mathbf{L}$, of the affinity matrix $\mathbf{A}$ is computed
as $\mathbf{L}=\mathbf{D}-\mathbf{A}$ (for the case of unnormalized
Laplacian), where $\mathbf{D}$ is the degree matrix.

  2. 2.

Eigen-decomposition of $\mathbf{L}$ is used to obtain the eigenvectors and
eigenvalues as $\mathbf{L}=\mathbf{X}\Lambda\mathbf{X}^{T}$.

  3. 3.

The optimal number of clusters, $K$, is estimated by finding the maximum
eigengap in the eigengap vector, i.e.,

$\mathbf{e}_{\mathrm{gap}}=\\{\lambda_{2}-\lambda_{1},\lambda_{3}-\lambda_{2},\ldots,\lambda_{n}-\lambda_{n-1}\\}.$

  4. 4.

The eigenvectors $\mathbf{v}_{1},\ldots,\mathbf{v}_{K}$ corresponding to the
$K$ smallest eigenvalues are collected into a
$\mathbf{U}\in\mathbb{R}^{N\times K}$ matrix, and the rows $\mathbf{u}_{n}$ of
$\mathbf{U}$ are clustered into $K$ clusters using K-means clustering.

In Section 2.4, we will describe an alternative formulation of spectral
clustering based on solving a constrained optimization problem, which is more
amenable for overlap-aware speaker diarization.

###  2.3 Overlap-aware diarization

Although the clustering paradigm described above has proved to be effective
through the use of DNN-based speaker embeddings, it cannot handle overlapping
speech by design, since the clustering process assigns each segment to exactly
one speaker. Existing approaches to solve the overlap problem fall into two
categories. In the first category, an externally trained overlap detection
module identifies frames in the recording which contain overlapping speech.
This “overlap detection” may be performed using HMMs [81, 82, 83] or neural
networks [84, 85, 86, 87]. Once overlaps are detected, an “overlap assignment”
stage assigns additional speaker labels to the overlapping frames. [12]
proposed overlap-aware resegmentation, which leverages the variational Bayes
(VB)-HMM method used originally for diarization in [88], and applied to
resegmentation in [89]. In the second framework, end-to-end systems [13, 90]
are used to perform overlapping diarization in a supervised setting. While
speaker diarization in overlapping settings has been studied extensively,
there is no prior work, to the best of our knowledge, on incorporating overlap
awareness into spectral clustering based diarization.

In this chapter, we extend spectral clustering for overlap-aware speaker
diarization. Specifically, we train an external overlap detector, and use its
classification decision during clustering of the segment-level embeddings. Our
method relies on the two-step clustering formulation proposed in [91]. The
remainder of this chapter is organized as follows. We start by giving a
detailed description of our method in Section 2.4, where we discuss
$p$-binarization and NME for estimating the number of speakers, followed by
the mathematical formulation of multi-class spectral clustering. We then
introduce our modification of the method to perform overlap-aware diarization.
This is followed by a description of our experimental setup and results in
Sections 2.6 and 2.7, respectively. We present results on the AMI meeting
corpus and the LibriCSS dataset, with detailed analysis of the performance of
the method on different overlap conditions.

###  2.4 Methodology

Our diarization system follows the clustering paradigm outlined in Section
2.2. We focus on the final clustering stage, and specifically on how to make
the clustering process overlap-aware. In particular, given a sequence of
windowed embeddings $S=(\mathbf{s}_{1},\ldots,\mathbf{s}_{N})$, the objective
is to compute a label sequence
$L=(\boldsymbol{\ell}_{1},\ldots,\boldsymbol{\ell}_{N})$, where
$\boldsymbol{\ell}_{n}$ may be a single label or, in case of overlapping
segment, multiple labels. For convenience, we assume that overlaps can occur
between at most two speakers, so $\boldsymbol{\ell}_{n}$ will be a 2-tuple for
an overlapping segment.

In this section, we will assume that we have an overlap detector which
decides, for each window, whether or not it contains overlapping speech. We
denote the as

$\mathrm{OVL}(R)=\mathbf{v}_{OL},$ (2.5)

where $\mathbf{v}_{OL}\in\\{0,1\\}^{N}$, and $\mathbf{v}_{OL}^{t}=1$ indicates
that ${\ell}_{n}$ must be a 2-tuple. Later, in Section 2.5, we will describe
the formulation of one such method for computing $\mathrm{OVL}(R)$, using a
hybrid HMM-DNN approach.

Given $S$ and $\mathbf{v}_{OL}$, overlap-aware diarization seeks to compute an
optimal label sequence $L$ which minimizes the diarization error. Since we do
not additionally have information about the number of speakers $K$ in the
recording, we first estimate it using the heuristic described in [79].
Subsequently, we perform multi-class spectral clustering to group the $N$
windowed subsegments into the estimated $\widehat{K}$ clusters using the
optimal discretization procedure proposed in [91], where we make a key
modification to constrain the optimization process on the output
$\mathbf{v}_{OL}$ of our overlap detector.

####  2.4.1 Estimating number of speakers

Given $S$, we compute the affinity matrix $\mathbf{A}\in[-1,1]^{N\times N}$ of
raw cosine similarity values. Then, $p$-binarization is performed on this
matrix by replacing the $p$ highest similarity values in each row with 1, and
the rest with 0, followed by a symmetrization operation,

$\bar{\mathbf{A}}_{p}=\frac{1}{2}(\mathbf{A}_{p}+\mathbf{A}_{p}^{T}).$ (2.6)

We compute the unnormalized Laplacian for this matrix,

$\mathbf{L}_{p}=\mathbf{D}_{p}-\bar{\mathbf{A}}_{p},$ (2.7)

where $\mathbf{D}_{p}=\mathrm{diag}\\{d_{1},\ldots,d_{N}\\}$,
$d_{i}=\sum_{n=1}^{N}a_{i,n}$, also known as the “degree” of node $i$.

The properties of the unnormalized Laplacian of the affinity matrix have been
studied extensively [92], and it is known that $\mathbf{L}_{p}$ has $N$ non-
negative, real eigenvalues
$0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{N}$. Furthermore, an
implication of the Davis-Kahan perturbation theory [93] proposes an eigengap
heuristic for the optimal number of clusters. Specifically, let
$\mathbf{e}_{p}$ denote the vector of differences in consecutive eigenvalues
(in increasing order). We compute the quantities

$g_{p}=\frac{\max(\mathbf{e}_{p})}{\lambda_{p,N}+\epsilon},\quad\text{and}\quad
r(p)=\frac{p}{g_{p}}.$ (2.8)

Then, the optimal number of clusters is given as

$\widehat{K}=\arg\max(\mathbf{e}_{\hat{p}}),\quad\mathrm{where}~{}~{}\hat{p}=\mathrm{arg}\min_{p}r(p).$
(2.9)

In the multi-class spectral clustering procedure below, we will use this
estimate $\hat{K}$ for the number of clusters, and drop the subscript $p$ from
the matrices like $\mathbf{L}_{p}$, $\mathbf{D}_{p}$ and
$\bar{\mathbf{A}}_{p}$ for brevity.

####  2.4.2 Multi-class spectral clustering

Bipartite graph partitioning using the affinity matrix Laplacian $\mathbf{L}$
is solved by node assignment based on the underlying Fiedler vector
(eigenvector corresponding to the second smallest eigenvalue) [94]. The Ng-
Jordan-Weiss algorithm [74] is a popular extension of this principle for
multi-way partitioning of the graph. It applies K-means clustering on the
first $K$ eigenvectors of $L$, i.e., in the $K$-eigenspace of the Laplacian,
as described in Section 2.2.4.2. It is known that if the original samples are
separable into $K$ groups using some transformation, then their projection on
the $K$-eigenspace can be easily grouped using K-means clustering. Recent work
on speaker diarization through spectral clustering of x-vectors, as in [79]
and [80], has employed this algorithm. However, there are two major
limitations of this approach. First, the K-means clustering process may get
stuck in bad local optima, particularly when the affinity matrix is noisy.
Second, and particularly relevant for our case, it is difficult to extend this
method to handle overlaps. To remedy these issues, we use an alternative
formulation of spectral clustering, proposed in [91].

Given $\mathbf{A}$ and $\mathbf{D}$ as defined earlier, the clustering problem
requires estimating the assignment matrix $X$. In graph partitioning terms,
this can be represented as

$\displaystyle\mathrm{maximize}\quad\epsilon(X)$
$\displaystyle=\frac{1}{K}\sum_{k=1}^{K}\frac{X_{k}^{T}\mathbf{A}X_{k}}{X_{k}^{T}\mathbf{D}X_{k}}$
(2.10) $\displaystyle\mathrm{subject~{}to}\,\,\,\,\,\,\quad X$
$\displaystyle\in\\{0,1\\}^{N\times K},$ $\displaystyle X\boldsymbol{1}_{K}$
$\displaystyle=\boldsymbol{1}_{N}.$

Intuitively, the objective function $\epsilon(X)$ seeks to maximize the
average “link-ratio”, i.e., the fraction of all link weights in a group that
stay within the group. The constraint $X\boldsymbol{1}_{K}=\boldsymbol{1}_{N}$
enforces the condition that each sample can belong to exactly 1 cluster. We
will see later (cf. Section 2.4.3) how this constraint can be modified for our
overlap-aware scenario.

The optimization problem in (2.10) is NP-complete due to the discrete
constraints on $X$. Instead of solving this original problem, we solve a
relaxed version of this problem which ignores the constraints. Let

$Z=f(X)=X(X^{T}\mathbf{D}X)^{-\frac{1}{2}}.$ (2.11)

It is easy to verify that $Z^{T}\mathbf{D}Z=I_{K}$. We can rewrite the above
problem (2.10), by ignoring the constraints, as

$\displaystyle\mathrm{maximize}\,\,\,\,\,\,\,\quad\epsilon(Z)$
$\displaystyle=\text{tr}(Z^{T}\mathbf{A}Z)$ (2.12)
$\displaystyle\mathrm{subject~{}to}\quad Z^{T}\mathbf{D}Z$
$\displaystyle=I_{K}.$

Since $Z$ has been relaxed into the continuous domain, the new optimization
problem becomes tractable. Let

$P=\mathbf{D}^{-1}\mathbf{A},$ (2.13)

and suppose the eigen-decomposition of $P$ is given as $PV=VS$. Let
$\Lambda^{\ast}=\mathrm{diag}(s_{1},\ldots,s_{K})$ and $Z^{\ast}$ contain the
first $K$ columns of $V$. Then, the global optimum of the problem described in
(2.12) occurs at

$\\{Z^{\ast}R:R^{T}R=I_{K},PZ^{\ast}=Z^{\ast}\Lambda^{\ast}\\}.$ (2.14)

This implies that the global optimum is not unique; rather, it is a subspace
spanned by the first $K$ eigenvectors of $P$ through orthonormal matrices. The
matrix $Z$ is a continuous solution to our clustering problem. To obtain a
discrete solution, we solve for a discrete approximation for $Z$. First, we
note from (2.11) that

$X=f^{-1}(Z)=\operatorname{Diag}\left({\mathrm{diag}}^{-\frac{1}{2}}\left(ZZ^{T}\right)\right)Z.$
(2.15)

Using this transformation, we can characterize the solution obtained in (2.14)
as

$\\{\tilde{X}^{\ast}R:R^{T}R=I_{K},\tilde{X}^{\ast}=f^{-1}(Z^{\ast})\\}.$
(2.16)

Now, our discretization problem is to find an $X$ which approximates
$\tilde{X}^{\ast}R$ for some orthonormal $R$, such that $X$ obeys the discrete
constraints from problem (2.10). Mathematically, this is formulated as

$\displaystyle\mathrm{minimize}\quad\phi(X,R)$ $\displaystyle=\left\lVert
X-\tilde{X}^{\ast}R\right\rVert^{2}$ (2.17)
$\displaystyle\mathrm{subject~{}to}\,\quad\quad\quad X$
$\displaystyle\in\\{0,1\\}^{N\times K},$ $\displaystyle X\boldsymbol{1}_{K}$
$\displaystyle=\boldsymbol{1}_{N},$ $\displaystyle R^{T}R$
$\displaystyle=I_{K}.$

It is difficult to minimize $\phi(X,R)$ jointly in $X$ and $R$, so we optimize
it alternately in $X$ and $R$. Suppose we are given some $R^{\ast}$, then the
problem (2.17) reduces to

$\displaystyle\mathrm{minimize}\quad\phi(X)$ $\displaystyle=\left\lVert
X-\tilde{X}^{\ast}R^{\ast}\right\rVert^{2}$ (2.18)
$\displaystyle\mathrm{subject~{}to}\quad\quad X$
$\displaystyle\in\\{0,1\\}^{N\times K},$ $\displaystyle X\boldsymbol{1}_{K}$
$\displaystyle=\boldsymbol{1}_{N}.$

The solution to this problem is given by non-maximal suppression, i.e.,

$X^{{\ast}}(i,l)=\left\langle
l=\arg\max_{k\in[K]}\tilde{X}(i,k)\right\rangle,\quad i\in\\{1,\ldots,N\\}.$
(2.19)

Intuitively, we set the largest entry in each row as one and zero out all the
others. This ensures that each sample belongs to exactly 1 cluster. In the
next section, we will see how to reformulate problem (2.18) for the case when
some samples can belong to more than one clusters. Next, we fix $X^{\ast}$ and
solve the following problem for $R^{\ast}$:

$\displaystyle\mathrm{minimize}\quad\phi(R)$ $\displaystyle=\left\lVert
X^{\ast}-\tilde{X}^{\ast}R\right\rVert^{2}$ (2.20)
$\displaystyle\mathrm{subject~{}to}\quad R^{T}R$ $\displaystyle=I_{K}.$

The solution to this problem is given by

$R^{\ast}=\tilde{U}U^{T},$ (2.21)

where $(U,\Omega,\tilde{U})$ is a singular value decomposition of
$X^{{\ast}T}\tilde{X}^{\ast}$.

We solve the two problems (2.18) and (2.20) iteratively until convergence, and
finally return $X^{\ast}$ as the output of the clustering procedure.

####  2.4.3 Extension to overlap-aware clustering

From (2.5), suppose the output of our overlap detector is given by
$\mathbf{v}_{OL}\in\\{0,1\\}^{N}$, where $\mathbf{v}_{OL}^{t}=1$ indicates
that ${\ell}_{n}$ must be a 2-tuple. Then, we can reformulate problem (2.18)
to include the overlap constraint as

$\displaystyle\mathrm{minimize}\quad\phi(X)$ $\displaystyle=\left\lVert
X-\tilde{X}^{\ast}R^{\ast}\right\rVert^{2}$ (2.22)
$\displaystyle\mathrm{subject~{}to}\quad\quad X$
$\displaystyle\in\\{0,1\\}^{N\times K},$ $\displaystyle X\boldsymbol{1}_{K}$
$\displaystyle=\boldsymbol{1}_{N}+\mathbf{v}_{OL}.$

Intuitively, this solves the same optimum discretization problem, but the
cluster exclusivity constraint has been modified to represent the condition
that some samples may belong to more than one cluster. Similar to how we used
non-maximal suppression in (2.19) to solve the problem previously, the
solution to the modified problem is again given by non-maximal suppression,
with the exception that for samples belonging to more than one group, we set
the largest two entries to 1, while zeroing out the others. Mathematically,

$\displaystyle\hat{X}^{{\ast}}(i,l)=X^{{\ast}}(i,l)+\mathbf{v}_{OL}^{(i)}\times\left\langle
l=k^{\prime}_{i}\right\rangle,$ (2.23)

$~{}\forall i\in\\{1,\ldots,N\\}$, where $X^{{\ast}}(i,l)$ is defined in
(2.19), and $k^{\prime}_{i}$ is the index of the second largest element of
$\tilde{X}_{i}$. Although we only consider the case of 2-speaker overlaps
here, it is easy to extend this method to the case of an arbitrary number of
overlapping speakers.

###  2.5 Overlap detection

Our proposed overlap-aware diarization method relies heavily on the
performance of $\mathrm{OVL}(R)$, the overlap detector. In this section, we
detail an HMM-DNN based overlap detector. Our model is similar to the speech
activity detector previously used in the CHiME-6 baseline system [6].

We first trained a neural network classifier to assign each frame in an
utterance a label from $\cal C$ = {silence, single, overlap}, denoting
silence, single speaker, or overlapping regions, respectively. We used the
architecture shown in Figure 2.3, consisting of time-delay neural network
(TDNN) layers to capture long temporal contexts [68], interleaved with
bidirectional long short term memory (BLSTM) layers with projection, to
incorporate utterance-level statistics.

The posteriors obtained from the classifier were scaled with an external bias
parameter tuned on the development data to reduce the false alarm rate. We
then post-processed the per-frame classifier outputs to enforce minimum and
maximum silence/single/overlap durations, by constructing a simple HMM whose
state transition diagram encodes these constraints. Fig. 2.4 shows an example
of a simplified HMM where these durations are set to small quantities.
Treating the per-frame posteriors like emission probabilities, we performed
Viterbi decoding to obtain the most likely label-sequence. Furthermore, state
transitions between the silence and overlap states were prohibited, mimicking
real-world observations where it is highly unlikely for two speakers to start
or stop speaking simultaneously.

Figure 2.3: Architecture of the neural network used for frame-level
classification for overlap detection.

Figure 2.4: Simple HMM used for decoding graph construction. Here, we set the
minimum silence/speech/overlap duration as 0.0s/0.0s/0.1s, and maximum
speech/overlap duration as 0.03s/0.02s, respectively. Note that each
transition correspond to one frame in the input, which has a frame shift of
0.01s in this example.

###  2.6 Experimental setup

####  2.6.1 Datasets

We performed experiments on the AMI meeting corpus and the LibriCSS data.
Recall from Section 1.4 that AMI contains 4-speaker meetings, while LibriCSS
is a simulated corpus containing 8-speaker recordings. For our AMI
experiments, we used the mix-headset recordings, which are obtained by summing
the individual headset signals from the participants in the meeting. For our
LibriCSS experiments, we selected the recordings from the first channel of the
array. We used this dataset to conduct a performance analysis of our proposed
method on different overlap conditions.

####  2.6.2 Baselines

We first have single-speaker baselines: (i) agglomerative hierarchical
clustering (AHC) of x-vectors with probabilistic linear discriminant analysis
(PLDA) scoring [95], (ii) spectral clustering of x-vectors with cosine scoring
(using the Ng-Jordan-Weiss method) [79], and (iii) Bayesian HMM based x-vector
clustering (VBx) [96, 97]. We used the same x-vector extractor for all the
baselines (described in Section 2.6.3), so that the difference in their
performance was only due to the clustering process. Furthermore, we used the
same PLDA model (trained on a subset of the AMI training data) for the AHC and
VBx baselines111The VBx diarization system has been shown to obtain
significant gains with a PLDA interpolated between general data and in-domain
data, but we did not use this method in this chapter.. For both these
baselines, hyperparameters were tuned on the development set. No
hyperparameter selection is required for spectral clustering since it is auto-
tuned. We used a ground-truth VAD for these baselines as well as for our
proposed method.

We also compare our approach with diarization methods that do not ignore
overlaps. These include: (i) overlap-aware VB resegmentation [12] and (ii)
region proposal networks (RPNs) [90]. For the former, we report the results
from the paper, which uses a neural VAD. For RPNs, we filtered out non-speech
regions using the ground truth VAD. All results are reported in terms of
diarization error rate (DER), and we further break it down into missed speech
(MS), false alarms (FA), and speaker confusion (Conf.) errors.

####  2.6.3 Implementation details

X-vector extractor. We used an x-vector extractor similar to the ones
described in earlier studies [72, 79]. The model consists of TDNN layers with
statistics pooling, and we extracted 128-dim embeddings from the pre-final
layer. It was trained on VoxCeleb data [98] with simulated room impulse
responses [99] using the Kaldi toolkit [100], and released as part of the
CHiME-6 baseline [6].

Overlap detector. We trained an HMM-DNN overlap detector (described in Section
2.5) using Kaldi. We used 40-dim MFCCs features as input, and trained the
classifier on in-domain training data. For AMI, we used targets obtained from
annotations of the official training set. Since LibriCSS does not have
corresponding training data, we generated simulated mixtures with
reverberation using Librispeech training utterances [101] and used force-
aligned targets for training our overlap detector. The decoding graph was
created with additional constraints on the minimum and maximum durations:
0.03s and 10.0s for single speakers and 0.1s and 5.0s for overlapping regions,
respectively. Note that our clustering method itself is independent of the
overlap detector used.

Overlap-aware spectral clustering. We extended the spectral clustering
algorithm in scikit-learn [102] for our implementation. Since the overlap
detector provides frame-level classification decisions whereas x-vectors were
extracted for 1.5s segments, we assumed that a segment is “overlapping” if at
least half of it lies in overlapping regions. For estimating the number of
speakers $\widehat{K}$, we swept the binarization factor $p$ in the range from
2 to 20, similar to what was done in [79].

###  2.7 Results and discussion

####  2.7.1 Overlap detection on AMI

We present the results obtained by our overlap detector using 40-dim MFCC
features on AMI mix-headset data in Table 2.1. We can see that the performance
is comparable to previous studies on this dataset, without using waveform-
level learned features. Furthermore, the results are similar regardless of the
input features used for the overlap detection. In general, we prefer an
operating point with a relatively high precision, at the cost of low recall.
This is because if the overlap detector falsely identifies a sub-segment as an
overlapping one, the clustering process would assign 2 speakers to it,
resulting in increased false alarms. On the other hand, if we fail to detect
an overlapped sub-segment, it would not result in any extra errors compared
with a regular (non-overlapping) diarization system. For the experiments
reported in the subsequent sections, we used the output from the above overlap
detector using MFCC features.

Table 2.1: Overlap detection results on AMI mix-headset data, in terms of
Precision (%) and Recall (%).

Model (feature type) Dev Eval Precision Recall Precision Recall ConvNet
(Spectogram) [87] 80.5 50.2 75.8 44.6 E2E BLSTM (MFCC) [12] 90.0 52.5 91.9
48.4 E2E BLSTM (SincNet) [12] 90.0 63.8 86.8 65.8 Our method (FBank) 81.2 68.1
85.1 63.6 Our method (MFCC) 83.9 68.5 86.4 65.2 Our method (MFCC+pitch) 79.1
69.3 82.4 66.2

####  2.7.2 Diarization results for AMI

Table 2.2 shows our proposed overlap-aware spectral clustering method compared
with baselines, evaluated on the AMI mix-headset eval data. First, the simple
clustering-based baselines (AHC, spectral, and VBx) obtain a high MS error
rate, since they cannot assign more than one speaker to any sub-segment. Since
we used an oracle VAD, the corresponding FA rate is 0%, but this is likely to
increase when using automatic VADs. The speaker confusion varies depending on
the clustering method, and VBx is found to be the most accurate in this
setting.

Next, we see that the baselines with overlap assignment (such as VB
resegmentation [12] and RPN [90]) improve the overall DER, mainly due to
improvement in MS. Nevertheless, RPN was found to significantly increase FAs,
perhaps since it is trained on overlapping mixtures, and is prone to over-
assignment of speakers.

Using our overlap detector trained on the AMI train set, our overlap-aware
spectral clustering method was able to improve the DER from 28.3% for the
AHC/PLDA baseline, to 24.0%, which is a relative improvement of 15.2%. This
compares favorably with the performance of other diarization methods like
overlap-aware VB resegmentation and RPNs. Furthermore, it is possible to
reduce the DER to 21.5% using an oracle overlap detector. For all the
recordings in the test set, the NME-based speaker counting approach estimated
between 3 and 6 speakers, which is close to the oracle count of 4 speakers.

Table 2.2: Diarization results on AMI mixed-headset eval set.

Method MS FA Conf. DER AHC/PLDA 19.9 0.0 8.4 28.3 Spectral/cosine 19.9 0.0 7.0
26.9 VBx [96] 19.9 0.0 6.3 26.2 VB resegmentation [12] 13.0 3.6 7.2 23.8 RPN
[90] 9.5 7.7 8.3 25.5 Our method 11.3 2.2 10.5 24.0 Our method + oracle OD 7.4
1.8 12.3 21.5 Our method + noise aug. 11.3 2.2 10.1 23.6

A detailed analysis of the results reveals that although the missed speech
reduces substantially (from 19.9% to 11.3%) as a result of overlap detection,
there is also a significant increase in speaker confusion errors (from 8.4% to
10.5%). We conjecture that since the x-vector extractor was trained only on
single-speaker utterances, a mismatch in the overlap regions of the recording
results in noisy samples. The speaker confusion improved by 0.4% when we used
an x-vector extractor trained with noise augmentation, using noises from the
MUSAN corpus [103]. To verify our hypothesis further, we show the T-SNE plots
for the non-overlapping and overlapping segments in Fig. 2.5(a) and 2.5(b),
respectively. We can see that while the embeddings for the non-overlapping
segments are well separated, those for overlapping segments may often be
noisy, leading to clustering errors.

(a)

(b)

Figure 2.5: T-SNE plots of x-vector embeddings for (a) non-overlapping, and
(b) overlapping segments for the recording EN2002a in the AMI eval set
(containing 4 speakers). Colors denote the speaker assigned to the segment.
For (b), each color represents a distinct pair of speaker labels, resulting in
6 differently colored clusters. Table 2.3: Diarization performance on LibriCSS
evaluation set (sessions 2-10), evaluated condition-wise, in terms of % DER.
0S and 0L refer to 0% overlap with short and long inter-utterance silences,
respectively. Our overlap detector obtained 96.3% precision and 83.8% recall
on this data. RPN does not use ground truth VAD.

Method Overlap ratio in % Average 0L 0S 10 20 30 40 AHC/PLDA 5.1 2.7 11.5 19.3
22.7 28.8 16.3 Spectral/cosine 2.2 1.9 8.5 13.5 19.0 23.4 12.6 RPN 4.5 9.1 8.3
6.7 11.6 14.2 9.5 Our method 2.6 3.4 6.8 10.0 13.9 15.2 9.3 \+ oracle OD 2.2
3.3 6.7 9.6 12.9 14.4 8.8

####  2.7.3 Analysis on LibriCSS

Table 2.3 shows a breakdown of diarization errors obtained by our system,
compared with some of the baselines. It is evident that as the overlap ratio
increases from 0 to 40%, the difference in performance becomes more
significant. On average, our method provided a 42.9% relative DER improvement
compared to a baseline AHC system, and this increased to 46.0% relative on
using an oracle overlap detector. We note here that since LibriCSS does not
have a corresponding training set, the PLDA was trained on Librispeech
utterances. The mismatch between clean training data versus overlapping
mixtures at test time may be particularly detrimental to the performance of
the AHC system. As the overlap ratio increases, RPN performs better than our
method. We again attribute this to the fact that our RPN model is trained on
closely matched overlapping speech, whereas the x-vector extractor was trained
on single-speaker utterances, which results in a higher speaker confusion.
Nevertheless, in real meetings, it is relatively rare for overlap statistics
to be more than 30% (for example, AMI has 19.9% overlapping speech), and in
such conditions, our method obtains similar performance to the
discriminatively-trained RPN.

###  2.8 Conclusion

Speaker diarization is an important component of the multi-talker ASR problem,
since it performs speaker attribution for the transcriptions. In this chapter,
we showed that the traditional clustering-based diarization system is
inherently incapable of handling overlapping speech, which forms a significant
fraction of multi-talker recordings. We proposed a new method for overlap-
aware speaker diarization using spectral clustering by leveraging an external
overlap detector to identify the overlapping subsegments, and then assigning
these segments to multiple speakers during clustering. Our method provided
significant improvements over conventional single-speaker clustering models,
and was competitive with other overlap-aware diarization methods.

As described in Section 2.3, there are several newer approaches for overlap-
aware diarization, such as those which reformulate the problem as multi-label
classification. These methods, which are based on supervised training on
multi-speaker mixtures, are often more robust at handling overlapping speech.
Nevertheless, clustering-based approaches are still prominent because of their
robustness across acoustic domains and number of speakers. Given such
complementary systems, we ask the question: can we benefit by ensembling them
to benefit from their respective strengths? This question is addressed in the
next chapter.

##  Chapter 3 Ensembles of Diarization Systems

In the previous chapter, we described a method for overlap-aware speaker
diarization using spectral clustering. Considering the importance of
diarization as a pre-processing step, it is not surprising that there is a
large body of research tackling this problem with very different solutions.
These solutions have complementary strengths, such as performance on
overlapping speech, accurate estimation of number of speakers, or robustness
on out-of-domain acoustic environments. In this chapter, we propose DOVER-Lap,
an algorithm that can combine the outputs of these diverse systems, thereby
improving error rates across a range of conditions. In the context of our
over-arching multi-talker ASR pipeline, we expect such ensembling methods to
be fast and accurate for any number of diarization systems. We will show how
to adapt ideas from approximation algorithms to design a suite of such
ensembling algorithms with trade-offs between computational cost and
approximation ratios.

This chapter is organized as follows. Section 3.1 describes commonly used
approaches for speaker diarization in literature, along with their advantages
and disadvantages. In Section 3.2, we will formalize the system combination
problem and introduce DOVER-Lap, which decomposes the above problem into the
sub-problems of “label mapping” and “label voting.” Section 3.3 reformulates
label mapping as a graph partitioning problem, which allows us to describe a
fast and accurate approximation algorithm for the task. In Section 3.4, we
present the relatively easier problem of voting, and describe a simple maximal
voting strategy which solves it. Finally, we present results for system
combination in Section 3.5, where we perform DOVER-Lap based ensembling for
AMI and LibriCSS using a variety of speaker diarization systems. We also
experiment with multi-channel diarization through a late fusion of channel-
level diarization outputs in Section 3.6, and show that this simple strategy
is competitive with beamforming-based early fusion.

###  3.1 Introduction

In the 2000s, NIST and DARPA organized several challenges to advance the state
of speaker diarization research. Since statistical learning-based approaches
for diarization were still fairly new at the time, the evaluations were
suitably constrained — participants were often provided oracle speech
segmentation (i.e., non-speech regions were demarcated), the number of
speakers was known beforehand, and the audio recordings were assumed to have
zero overlapping speech. More recently, as the diarization task has matured,
we have moved towards unconstrained evaluations. The CHiME-6 [6] and DIHARD
[5, 104] challenges, for example, contain challenging recordings with high
noise and overlapping speech and a diverse number of speakers.

This shift in evaluation happened as a result of several advances in systems
that perform speaker diarization. The traditional approach for speaker
diarization, as described in Chapter 2, involved a clustering of segment-level
speaker embeddings, optionally followed by resegmentation [72, 79, 69]. This
approach requires separately optimized speech activity detection components,
and also assumes that the recording does not contain overlapping speech. To
alleviate the latter problem, several methods have been proposed which seek to
employ overlap detection modules and use some heuristics of the clustering
process to assign extraneous speakers to the overlapping segments [105, 106].

More recently, supervised diarization methods such as region proposal networks
(RPN), end-to-end neural diarization (EEND), and target-speaker voice activity
detection (TS-VAD) have been proposed which inherently perform overlapping
speaker assignment [90, 13, 80]. An alternate paradigm for overlap-aware
diarization involves using a continuous speech separation (CSS) module to
first split the recording into 2 or 3 streams, followed by clustering of
speakers across the streams [107, 108].

Machine learning tasks usually benefit from an ensemble of different systems
[109]. ROVER [110] is a popular post-processing method for combining the
outputs of speech recognition systems through weighted majority voting. This
method was generalized to be used with n-best lists or lattices, and called
confusion network combination (CNC) [111, 112]. Lattice combination has also
proved to be effective in systems developed for community challenges such as
the CHiME-6 challenge [113]. However, it has traditionally been difficult to
combine diarization systems at the output level due to the varying system-
dependent time-segmentations of the hypotheses.

DOVER [114] was the first algorithm proposed to perform such combination
through weighted majority voting (similar to ROVER for ASR) on homogeneous
single-speaker regions across a recording. Evaluation results showed that it
improved over random (or even oracle) channel selection, albeit with several
caveats. While DOVER provided a convenient method to combine diarization
outputs, it was limited since it could not handle outputs containing
overlapping segments. This limitation is of particular significance if we
consider the increasing application of diarization to real multi-talker
conversations containing high overlaps (such as the AMI [4] meeting corpus and
the CHiME challenges [115, 6]), and the availability of methods that can
perform diarization in such settings [12, 90, 13].

Our objective in this chapter is to devise an algorithm which can perform
hypotheses combination in overlap-aware settings. Towards this objective, we
propose DOVER-Lap (DOVER \+ Overlap), which generalizes and builds upon the
label mapping and label voting paradigms suggested in DOVER. We reformulate
the label mapping task as graph partitioning, and propose fast approximation
algorithms to solve it. We also modify the voting mechanism in DOVER such that
multiple speakers may be assigned to a region based on the voting decision.

We demonstrate through our experiments conducted on AMI and LibriCSS that
DOVER-Lap can efficiently combine hypotheses from very different systems,
ranging from conventional clustering-based to more recent end-to-end neural
methods, while improving the DER performance over the single best system. To
demonstrate the wide applicability of our technique, we also apply it to
multichannel diarization through late fusion of outputs from far-field array
microphones. We show that late fusion using DOVER-Lap is competitive with
early fusion using dereverberation and beamforming, without any need for
enhancement.

###  3.2 System combination with DOVER-Lap

####  3.2.1 Problem formulation

We assume that we are given the “hypotheses” $U_{k}$ from $K$ diarization
systems, i.e., $U_{1},\ldots,U_{K}$, where each system can perform overlapping
speaker assignment and may contain different number of speakers,
$c_{1},\ldots,c_{K}$. Mathematically, $U_{k}$ can be written as a set of
tuples containing time intervals and the corresponding speaker assignment. If
$U_{k}$ has $c_{k}$ speakers $\\{u_{k}^{1},\ldots,u_{k}^{c_{k}}\\}$ and
$N_{k}$ speaker-homogeneous segments, then

$U_{k}=\\{(\Delta_{k}^{n},u_{k}^{n}):n\in\\{1,\ldots,N_{k}\\}\\},$ (3.1)

where $\Delta_{k}^{n}$ is the time interval $n$ as defined in (2.1), and
$u_{k}^{n}\in\\{u_{k}^{1},\ldots,u_{k}^{c_{k}}\\}$ is the corresponding
speaker.

We define the problem of combining the hypothesis as finding a joint
diarization hypothesis $\hat{U}=\mathcal{D}(U_{1},\ldots,U_{K})$ such that
$\hat{U}$ minimizes the chosen diarization error metric with respect to an
unknown reference.

A straightforward approach for solving this problem involves dividing the
input hypotheses into small time durations, and performing majority voting
individually with each such region. However, there are two issues with this
solution. First, to perform any kind of voting (within a region), the system
outputs need to be in the same label space. Second, overlap-aware systems may
contain different number of speakers within any such region, and for overlap-
aware combination, the voting mechanism needs to account for this possibility.
In the next section, we describe how DOVER [114] solved this problem by
decomposing it into label mapping and label voting stages.

Table 3.1: Notations used in this chapter. Symbol | Definition
---|---
$U_{1},\ldots,U_{K}$ | Diarization hypotheses
$c_{k}$ | Number of speakers in hypotheses $k$
$C$ | Maximum number of speakers in any hypothesis
$u_{k}^{i}$ | Speaker $i$ in hypothesis $k$
$\Delta_{k}^{n}$ | Interval $n$ in hypotheses $k$
$V$ | Set of all hypotheses speakers
$E$ | Set of all edges $\\{(u_{k}^{i},u_{\ell}^{j})\\}$
$w_{e}$ | Weight on edge $e=\\{(u_{k}^{i},u_{\ell}^{j})\\}$
$(V_{1},\ldots,V_{C})$ | Clique set (output of label mapping)
$\mathcal{G}$ | Graph formed by vertex set $V$ and edge set $E$ with weights $w$

####  3.2.2 Preliminary: DOVER

DOVER (diarization output voting error reduction) was the first system
combination method proposed for combining diarization outputs using a weighted
majority voting technique [114]. It comprises two stages: label mapping, and
label voting, where each stage addresses one of the problems outlined in the
previous section.

#####  3.2.2.1 Label mapping

In the label mapping stage, the objective is to find a set of $C$ speaker
labels $\\{\hat{u}^{1},\ldots,\hat{u}^{C}\\}$ for our combined output
$\hat{U}$, and a mapping function $\mathcal{S}$ that takes as input one of the
speaker labels from the given hypotheses and maps it to a label in the
combined output, i.e., $\mathcal{S}(u_{k}^{i})=\hat{u}^{c}$, where $c\in[C]$.

In DOVER, this mapping is done incrementally by considering the hypotheses
pair-wise, with their order decided based on the average diarization error
rate (DER) to all other hypotheses. Suppose, for example, that the hypotheses
have been ordered as $U_{1},\ldots,U_{K}$. In this case, $U_{1}$ and $U_{2}$
are first mapped together using $U_{1}$ as reference to obtain $U_{1,2}$,
which is then mapped together with $U_{3}$ to obtain $U_{1,2,3}$, and so on,
until we have $U_{1,\ldots,K}$. At each iteration, the mapping is performed
using the Hungarian method [116], similar to how the reference and system
outputs are mapped to a common space for evaluating DER. This is an instance
of the weighted bipartite graph matching problem, and is poly-time solvable
using linear sum assignment on the weight matrix. This incremental approach
for label mapping treats it as an incremental assignment problem [117]. Due to
this treatment, it is unable to use the global pair-wise costs to map all the
hypotheses to a common space simultaneously. Furthermore, the method is
dependent on the order of hypotheses $H_{k}$, and choosing a bad initial pair
may be detrimental to the final mapping. In Section 3.3, we will reformulate
this label mapping problem in terms of graph partitioning, and propose fast
algorithms that seek to overcome these limitations with DOVER.

#####  3.2.2.2 Label voting

Figure 3.1: An illustration of overlapping output produced by DOVER-Lap for
overlapping hypotheses.

Once the hypotheses have been mapped to a common speaker label space, the
label voting stage is performed. In DOVER, weighted majority voting is done on
regions of input speech, where a region is defined as the maximal segment
delimited by any of the original speaker boundaries from the input hypotheses.
Given the speaker-homogeneous intervals $\Delta_{k}^{n}$ for the $K$
hypothesis, we pool the start and end time-stamps for all the intervals and
order them in monotonically increasing order. Let this new sequence be denoted
by $\\{\tau_{0},\ldots,\tau_{N-1}\\}$, where $N=\sum_{k=1}^{K}2N_{k}$; then,
each interval $[\tau_{n},\tau_{n+1}]$ is an example of a region defined above.
For all illustration, see the intervals
$[\tau_{0},\tau_{1}],\ldots,[\tau_{5},\tau_{6}]$ in Fig. 3.1.

Recall that overlap-aware diarization systems may contain multiple speakers in
each such region. However, DOVER makes the single-speaker assumption in
majority voting. Formally, if the audio is divided into $N$ regions, and
$L_{k}=(\ell_{k}^{1},\ldots,\ell_{k}^{T})$ denotes the region-wise labels
assigned by hypothesis $k\in K$, where
$\ell_{k}^{t}\in\\{\hat{u}^{1},\ldots,\hat{u}^{C}\\}$ (from label mapping),
and $C$ is the number of speakers in combined label space, then the DOVER
label voting stage computes, $\forall t\in T$,

$\ell_{t}=\arg\max_{\hat{u}^{c}\in\\{\hat{u}^{1},\ldots,\hat{u}^{C}\\}}\left(\sum_{k\in
K}w_{k}\mathbbm{1}(\ell_{k}^{t}=\hat{u}^{c})\right),$ (3.2)

where $w_{k}\in[0,1]$ denotes a confidence weight assigned to hypothesis $k$.
DOVER ranks the input hypotheses by their average DER to all other hypotheses,
and applies a weight that decays slowly with rank: $w_{k}=\frac{1}{k^{0.1}}$.
Since only a single speaker is assigned to every region, combination using
DOVER may lead to high missed speech in the overlap case, as shown in Fig.
3.1. We solve this problem through overlap-aware weighted majority voting,
described in Section 3.4.

###  3.3 Label mapping as a graph partitioning problem

Again, consider $K$ diarization hypotheses $U_{1},\ldots,U_{K}$, containing
$c_{1},\ldots,c_{k}$ speakers, respectively, such that
$C=\max\\{c_{k},k\in[K]\\}$. Let us denote each speaker as a node in a graph,
i.e., $u_{k}^{i}$ is the node corresponding to the $i^{th}$ speaker in the
$k^{th}$ hypothesis, and $V=\\{u_{k}^{i}\\}$ is the set of all speaker nodes.
Let $E=\\{(u_{k}^{i},u_{\ell}^{j}):\forall k,\ell\in[K],i\in U_{k},j\in
U_{\ell},k\neq\ell\\}$ denote the set of all edges. Informally, this means
that there is an edge between any two nodes if the nodes belong to different
hypotheses. Additionally, we have a weight function
$w:e\rightarrow\mathbb{R}^{+}$, where $e$ denotes an edge. In practice, these
edge weights are obtained by computing the relative overlap duration between
the speakers in the recordings, i.e.,

$w(u_{k}^{i},u_{\ell}^{j})=\frac{\Delta(u_{k}^{i})\cap\Delta(u_{\ell}^{j})}{\Delta(u_{k}^{i})\cup\Delta(u_{\ell}^{j})},$
(3.3)

where $\Delta(u)$ is the set of all segments where speaker $u$ is active in
the recording. Clearly, $w:E\rightarrow[0,1]$, and a higher $w$ means that the
corresponding speakers are more likely to occur in the same segments in the
recording (i.e., they are more likely to represent the same speaker).

We define the graph as $\mathcal{G}=(V,E,w)$. It is easy to see that
$\mathcal{G}$ is $K$-partite, and if $c_{k}=C,~{}\forall k\in[K]$, then it is
also complete. Fig. 3.2 illustrates this graphical formulation of the label
mapping problem.

Figure 3.2: Illustration of the label mapping problem as a graph $\mathcal{G}$
for the case of $K=3$. $V_{1}$ denotes the clique formed by vertices
$(u_{1}^{1},u_{2}^{2},u_{3}^{3})$. $\Delta(u)$ represents the segments where
speaker $u$ is active in the recording.

Each $U_{k}$ in the graph is an independent set (set of vertices with no edges
between any pair), and the label mapping problem can be defined as: partition
$V$ into $C$ vertex-disjoint cliques $\Phi=(V_{1},\ldots,V_{C})$, such that
the partition maximizes $w(\Phi)$, i.e.,

$\widehat{\Phi}=\text{arg}\max_{\Phi}w(\Phi),~{}~{}\text{where}~{}~{}w(\Phi)=\sum_{c\in
C}w(V_{c})=\sum_{c\in C}\sum_{e\in E(V_{c})}w(e),$ (3.4)

and $E(V_{c})$ represents edges in the sub-graph induced by $V_{c}$.
Intuitively, the objective maximizes the sum of all edge weights within the
cliques. The partition is orthogonal since it may contain at most one vertex
from every $U_{k}$.

It may not immediately be clear why maximizing the objective in (3.4) provides
an optimal label mapping. Since the partition is orthogonal, each $V_{c}$ may
represent a mapped speaker label. By maximizing the total edge weights within
cliques, we maximize the total relative overlap between speaker turns for
speakers that are mapped to the same label. It is hard to demonstrate a
theoretical correspondence between this objective and the DER metric that
would eventually be used to evaluate the results of the system combination.
However, we empirically demonstrate a correspondence using some recordings
from the AMI dataset in Fig. 3.3. We note from the figure that as the
objective (x-axis) improves, the DER decreases, suggesting that our proposed
objective is a good proxy for minimizing the final DER.

Figure 3.3: Partition weight $w(\Phi)$ versus diarization error rate (DER) for
three arbitrarily chosen recordings from the AMI evaluation set, showing that
DER tends to improve with weight.

####  3.3.1 Some properties of graph $\mathcal{G}$

######  Definition 3.3.1 (Turán graph).

The Turán graph $T(n,r)$ is a complete multi-partite graph formed by
partitioning a set of $n$ vertices into $r$ subsets, with sizes as equal as
possible, and connecting two vertices by an edge if and only if they belong to
different subsets.

######  Lemma 3.3.1.

$\mathcal{G}$ is equivalent to some $T(CK,K)$ Turán graph, i.e., it is
equivalent to a complete $K$-partite graph $K_{C,C,C,\ldots}$.

######  Lemma 3.3.2.

$\mathcal{G}$ has an exponential number of maximal cliques.

###### Proof.

The proof is through a simple combinatorial argument. Since $\mathcal{G}$ is a
complete $K$-partite graph, any maximal clique of $\mathcal{G}$ contains
exactly 1 vertex from all its $K$ independent sets. Since each independent set
has $C$ vertices, there are $C^{K}$ possibilities for a maximal clique. ∎

####  3.3.2 An exponential algorithm based on clique enumeration

In the previous section, we proved that $\mathcal{G}$ has an exponential
number of maximal cliques. Nevertheless, if $K$ is small, we can still
consider a brute-force solution for (3.4) by enumerating all the cliques in
the graph. Such an algorithm is presented in Algorithm 2, and it roughly
follows the following steps after the graph construction.

  1. 1.

Enumerate all the maximal cliques in $\mathcal{G}$. Let this set be denoted by
$S$.

  2. 2.

Find the clique $V_{c}$ with the maximum weight in $S$.

  3. 3.

Add $V_{c}$ to the partition $\Phi$. Remove the vertices in $V_{c}$ from
$\mathcal{G}$ and the associated edges.

  4. 4.

Repeat from Step 1 until no vertices remain in $\mathcal{G}$.

1

Input: Graph $\mathcal{G}=(V,E,w)$

Output: Partition $\Phi$ = $V_{1},\ldots,V_{C}$

2

3$\Phi=\\{\\}$

// Loop until no vertices remaining

4 while  _$V\neq\phi$_ do

$S$ = set of all maximal cliques in $V$

// Enumerate all maximal cliques

5

$V_{c}$ = max($S$, key=$\sum_{e\in S_{i}}w(e)$)

// Get maximum weighted clique

6

$\Phi=\Phi\cup\\{V_{c}\\}$

// Add clique to partition

7

$V=V\setminus\\{V_{c}\\}$

// Remove clique vertices from V

8

9

Algorithm 2 Exponential mapping based on clique enumeration

######  Theorem 3.3.3.

Algorithm 2 has time complexity $\mathcal{O}(C^{K})$, where $K$ is the number
of input hypotheses and $C$ is the maximum number of speakers in any
hypothesis.

###### Proof.

From Lemma 3.3.2, since $\mathcal{G}$ has $C^{K}$ maximal cliques, it takes at
least $\mathcal{O}(C^{K})$ time to simply enumerate all the cliques, as is
required in the first step of the algorithm. Hence, the mapping algorithm has
complexity exponential in the size of the input. ∎

In practice, we use tensor broadcasting operations to efficiently compute the
weights of all cliques in the graph. We build a cost tensor
$\mathbf{C}\in\mathbb{R}^{N_{1}\times\ldots\times N_{K}}$, where each element
of the tensor represents the weight of the clique corresponding to that
speaker group.

Figure 3.4: Computation of the cost tensor $\mathbf{C}$ for the DOVER-Lap
label mapping algorithm.

This computation is illustrated in Fig. 3.4 for $K=3$. Since the hypotheses
have 4, 3, and 4 speakers, respectively, $C\in\mathbb{R}^{4\times 3\times 4}$.
In the figure, we show the computation of the tensor index corresponding to
the tuple $(u_{1}^{4},u_{2}^{3},u_{3}^{1})$. For this, we first compute all 3
pair-wise costs; the cost of mapping $u_{1}^{4}$ and $u_{2}^{3}$ together, for
instance, is computed as the negative of the edge weight, which is the total
overlapping duration between $u_{1}^{4}$ and $u_{2}^{3}$, divided by the sum
of their speaking durations. Finally,
$C(u_{1}^{4},u_{2}^{3},u_{3}^{1})=-(M_{u_{1}^{4},u_{2}^{3}}+M_{u_{1}^{4},u_{3}^{1}}+M_{u_{2}^{3},u_{3}^{1}})$.
This sum can be efficiently computed by first computing all the pairwise sums
(i.e., the $K\choose{2}$ faces of the tensor, and then combining them using a
broadcasting operation.

Nevertheless, due to the exponential dependency, the algorithm quickly becomes
computationally intractable as $K$ increases. In Fig. 3.5, we computed the
label mapping time for an increasing number of input hypotheses for the AMI
and LibriCSS evaluation sets. For AMI (which contains 4 speakers; solid green
line), the algorithm became infeasible beyond $K=10$. For LibriCSS (which
contains 8 speakers; dotted green line), this limit was reached for an even
smaller value of $K$, making combination impossible beyond 7 hypotheses. As a
comparison, we also show (in blue) the mapping time for the poly-time
Hungarian algorithm we will describe in Section 3.3.3.

Figure 3.5: Label mapping time (in ms) for combining different number of
hypotheses on the AMI and LibriCSS data. The y-axis is logarithmic.

####  3.3.3 Polynomial-time Hungarian method

In this section, we propose a poly-time algorithm based on greedy pair-wise
combination of the hypotheses using the Hungarian method. Let use first define
some key concepts.

#####  3.3.3.1 Definitions and key concepts

Consider the subgraph $\mathcal{G}_{ij}$ induced by considering all the
vertices in sets $U_{i}$ and $U_{j}$, where $U_{i}$ and $U_{j}$ are two
independent sets in $\mathcal{G}$. By construction, such a subgraph
$\mathcal{G}_{ij}$ is a complete bipartite graph. For our graphical
formulation, we will first define a local and global mapping.

######  Definition 3.3.2.

A matching $M$ in $\mathcal{G}$ is a set of pairwise non-adjacent edges, none
of which are loops; that is, no two edges share common vertices. A perfect
matching is a matching which covers all vertices.

######  Definition 3.3.3.

A local label mapping $\psi$ is a matching on the bipartite graph
$\mathcal{G}_{ij}$.

######  Definition 3.3.4.

A global label mapping $\Psi$ is a function that assigns a vertex $u_{k}^{i}$
in the independent set $U_{k}$ to any one of the final cliques $V_{c}$.

Our algorithm works by incrementally constructing the global label mapping
using the local maps between pairs of independent sets. The local maps $\psi$
are computed using the Hungarian method as a subroutine, which is described
later. We develop the following terminology to describe this method. For the
sake of brevity, we drop the subscript $ij$ for the bipartite graph
$\mathcal{G}_{ij}$, and just refer to it as $\mathcal{G}$.

######  Definition 3.3.5.

A labeling of $\mathcal{G}$ is a function $l:V\rightarrow\mathbb{R}$ such that

$\forall\\{u,v\\}\in E,\quad l(u)+l(v)\geq w(u,v).$

######  Definition 3.3.6.

An equality subgraph is a subgraph
$\mathcal{G}_{l}=(V,E_{l})\subseteq\mathcal{G}=(V,E)$, fixed on labeling $l$,
such that

$E_{l}=\\{(u,v)\in E:l(u)+l(v)=w(u,v)\\}.$

This means that $\mathcal{G}_{l}$ only includes those edges from the bipartite
matching which allow the vertices to be perfectly feasible.

######  Lemma 3.3.4 (The Kuhn-Munkres theorem).

Given labeling $l$, if $\psi$ is a perfect matching on $\mathcal{G}_{l}$, then
$\psi$ is a maximum-weight matching on $\mathcal{G}$.

###### Proof.

Let $\psi^{\prime}$ be any perfect matching in $\mathcal{G}$. By definition of
a labeling function, and since $\psi^{\prime}$ is perfect,

$w(\psi^{\prime})=\sum_{(u,v)\in\psi^{\prime}}w(u,v)\leq\sum_{(u,v)\in\psi^{\prime}}l(u)+l(v)=\sum_{v\in
V}l(v).$

This means that $\sum_{v\in V}l(v)$ is an upper bound on the weight
$w(\psi^{\prime})$ of any perfect matching $\psi^{\prime}$ of $\mathcal{G}$.
Now, let us consider $\psi$.

$w(\psi)=\sum_{(u,v)\in\psi}w(u,v)=\sum_{(u,v)\in\psi}l(u)+l(v)=\sum_{v\in
V}l(v)\geq w(\psi^{\prime}).$

Thus, $\psi$ is a maximum-weight matching in $\mathcal{G}$. ∎

######  Definition 3.3.7.

Given a bipartite graph $\mathcal{G}$ and a matching $\psi$, the graph is said
to contain an alternating path if there exists a path in the graph which has
alternating edges in $\psi$.

######  Definition 3.3.8.

An augmenting path is a path in such a graph which has its endpoints (start
and end vertices) unmatched (i.e., not in the matching).

#####  3.3.3.2 The Hungarian method

An important component of our algorithm is the Hungarian method for computing
the maximum-weighted matching in bipartite graphs, due to Kuhn and Munkres
[116, 26]. In our algorithm, we use this as a subroutine to compute the local
label mapping $\psi$. In this section, we describe the algorithm and prove
that it returns a maximum bipartite matching in $\mathcal{O}(n^{3})$ time.

The idea behind the algorithm is to find a perfect matching on some labeling
$l$ on an equality subgraph, and use Lemma 3.3.4 to claim that it is a
maximum-weighted matching on $\mathcal{G}$. To achieve this, we start with an
empty matching $\psi=\phi$ and a valid $l$ given as

$l::=\forall x\in X,y\in Y:l(y)=0,l(x)=\max_{y^{\prime}\in Y}w(x,y^{\prime})$

We then repeat the steps of augmenting the matching and improving the
labeling, until we obtain a perfect matching. These two steps are outlined
below.

Step 1: Augmenting the matching

Given $\mathcal{G}_{l}$ and some matching $\psi$, we find unmatched vertices
$u,v\in V$ such that there is an augmenting path $\alpha$ from $u$ to $v$. If
such a pair of vertices exist, we create this augmenting path and flip the
edges in the matching, i.e., we replace the edges in $\psi$ with edges in the
augmenting path that are in $E_{l}\setminus\psi$. This process increases the
size of the matching, since we added previously unmatched vertices.

Step 2: Improving the labeling

Let $S\subseteq X$ and $T\subseteq Y$ represent the set of vertices on either
side of an “almost” augmenting path in $\psi$. Let $N_{l}(S)=\\{v:\forall u\in
S,(u,v)\in E_{l}\\}$. If $N_{l}(S)=T$, then we cannot increase the alternating
path and augment, so we must improve the labeling.

Let $\delta_{l}=\min_{u\in S,v\notin T}(l(u)+l(v)-w(u,v))$. We improve $l$ to
$l^{\prime}$ as

$l^{\prime}(r)=\begin{cases}l(r)-\delta_{l}&\text{if}~{}~{}r\in S,\\\
l(r)+\delta_{l}&\text{if}~{}~{}r\in T,\\\ l(r)&\text{otherwise}.\end{cases}$
(3.5)

It is easy to show that $l^{\prime}$ is a valid labeling by examining all
modified edges.

Using the two subroutines of augmenting and improving described above, the
Hungarian method iterates until $\psi$ is a perfect matching for
$\mathcal{G}_{l}$.

######  Lemma 3.3.5.

The Hungarian method runs in $\mathcal{O}(n^{3})$ time, where $n$ is the
number of vertices in $\mathcal{G}$.

###### Proof.

Each of the subroutines of augmenting the matching and improving the labeling
increases the size of the matching by 1 edge. Since there can be at most
$\frac{n}{2}$ edges in a matching, it takes $\mathcal{O}(n)$ rounds.
Augmenting the matching requires $\mathcal{O}(n)$ time to find the right
vertex, if one exists, and another $\mathcal{O}(n)$ to flip the matching.
Improving the labeling also requires $\mathcal{O}(n)$ to find $\delta_{l}$.
However, it can occur $\mathcal{O}(n)$ times if no augmenting path is found,
therefore it requires $\mathcal{O}(n^{2})$ steps in a single round. Hence, the
total running time is $\mathcal{O}(n^{3})$. ∎

#####  3.3.3.3 Algorithm

We now describe the whole algorithm for label mapping in Algorithm 3. The
algorithm starts with a pair of hypotheses (independent sets), and computes a
matching (local map) for them using the Hungarian method described in the
previous section. It then merges the pair w.r.t. the map $\psi$. This merge
operation is described next.

1

Input: Graph $\mathcal{G}=(V,E,w)$, $U=\\{U_{1},\ldots,U_{K}\\}$

Output: Partition $\Phi$ = $V_{1},\ldots,V_{C}$

2

3$\Psi=\\{\\}$

4$\upsilon=U_{1}$

5for  _$k$ in $[2,K]$_ do

6

$\psi$ = Hungarian($\upsilon$, $U_{k}$)

// Compute local map

7

$\upsilon$ = Merge($\upsilon,U_{k},\psi$)

// Merge pair w.r.t. local map

8

$\Psi$ = Update($\Psi,\psi$)

// Update global map

9

10

$\Phi$ = Partition($U$,$\Psi$)

// Compute partition using global map

11

Algorithm 3 Hungarian label mapping

Let $\mathcal{G}_{ij}$ be a bipartite graph induced from the graph
$\mathcal{G}$ by considering the independent sets $U_{i}$ and $U_{j}$, as
described earlier. Let $\psi$ be a matching on $\mathcal{G}_{ij}$, s.t.
$\psi=\\{u_{1}v_{1},u_{2},v_{2},\ldots,u_{C},v_{C}\\}$, where $u_{c}\in U_{i}$
and $v_{c}\in U_{j}$. We merge $U_{j}$ with $U_{i}$ by identifying the vertex
pairs $v_{c}$ with $u_{c}$. By Lemma 3.3.1, we can assume that we have
performed graph completion on $\mathcal{G}$ and so there are no unmatched
vertices. Let $U_{i(j)}$ denote the new vertex set. We remove the loops and
edges within $U_{i(j)}$, and replace multiple edges by a single edge with
weight equal to the sum of weights of the edges it is replacing. The new
weighted graph ($\mathcal{G}_{i(j)},w^{\prime}$) is called the merge of
$U_{j}$ to $U_{i}$ from $\mathcal{G}$ along $\psi$. Clearly,
$\mathcal{G}_{i(j)}$ is a ($k$-1)-partite graph.

In each iteration of the algorithm, we reduce the number of independent sets
by one because of this merge operation. Furthermore, after every merge, we
update the global mapping $\Psi$ using the local map $\psi$. This process
simply involves creating a transitive map of the form
$\psi_{K}(\ldots(\psi_{2}(\psi_{1}(\cdot))$ by composing the local label
mappings at each iteration.

######  Theorem 3.3.6.

Algorithm 3 runs in polynomial time.

###### Proof.

From Lemma 3.3.5, each iteration of the loop runs in $\mathcal{O}(C^{3})$
time, and there are a total of $K-1$ iterations. Hence, the algorithm finishes
in $\mathcal{O}(C^{3}K)$ time. ∎

######  Theorem 3.3.7.

Algorithm 3 is a $\frac{1}{C}$-approximation for the label mapping problem.

###### Proof Sketch.

The proof is obtained by induction on the number of hypotheses, $K$. The base
case holds trivially since the Hungarian algorithm returns a maximal matching.
The inductive case also holds by algebraic manipulation of the sum of weights
over the first matching and the remaining matching. For a detailed proof,
please refer to Appendix B.2. ∎

It can be shown through a reduction from the $c$-way $k$-coloring problem that
there is no efficient “deterministic” algorithm with a better approximation
ratio [118]. In Appendix B.4, we describe a label mapping algorithm based on
“randomized” local search, which obtains a close to optimal approximation
ratio in expectation.

###  3.4 Label voting in DOVER-Lap

Similar to DOVER, we perform weighted majority voting on “regions” of the
input. However, unlike the former, DOVER-Lap can assign multiple speakers to a
region. Consider a region $T$ (cf. intervals in Fig. 3.1), and suppose the
hypotheses $U_{1},\ldots,U_{K}$ contain $n_{1}^{T},\ldots,n_{K}^{T}$ speakers,
respectively, in this region. Then, we compute the weighted mean rounded to
the nearest integer as

$\hat{n}_{T}=\lfloor\sum_{k=1}^{K}w_{k}n_{k}^{T}\rceil,$ (3.6)

where $w_{k}$ are DOVER-like rank-based weights obtained by ranking the
hypotheses in increasing order of their total relative overlap duration with
all other hypotheses. The highest weighted $\hat{n}_{T}$ speakers are then
assigned to the region $T$. In case of ties, we assign all the tied speakers
to the regions. Since we use rank-based weighting of the hypotheses, such ties
only occur in very few regions. This assignment strategy allows multiple
overlapping speakers to be present in the combined diarization output.

###  3.5 System combination experiments

####  3.5.1 Setup

We performed experiments on two datasets: the AMI meeting corpus [4], and the
LibriCSS data [11] (Section 1.4). For AMI experiments, we used the mixed-
headset recordings, while for LibriCSS, we selected the the first channel of
the array in each recording.

We combine diarization results from the following systems.

  1. 1.

Overlap-aware spectral clustering (SC) [105]: This is our proposed method from
Chapter 2. It performs overlap-aware diarization by reformulating spectral
clustering as a constrained optimization problem, and then discretizing it
under the overlap constraints. An oracle SAD is used to remove non-speech
segments.

  2. 2.

VB-based overlap assignment (VB) [12]: This method leverages Variational Bayes
(VB)-HMM used originally for diarization in [88]. Using the output of an
externally trained overlap detector, overlapping frames are assigned the top
two speakers from the posterior matrix computed using VB inference. The same
SAD and overlap detector as in the system above were used.

  3. 3.

Region proposal networks (RPN) [90]: It combines segmentation and embedding
extraction into a single neural network, and jointly optimizes them using an
objective function that consists of boundary prediction and speaker
classification components. For AMI, we trained the RPN on force-aligned data
from the AMI training set; for LibriCSS, it was trained on simulated meeting-
style recordings with partial overlaps generated using utterances from the
LibriSpeech [101] training set. A post-processing step was applied using
oracle SAD segments to filter non-speech.

  4. 4.

Target-speaker voice activity detection (TS-VAD) [80]: It takes conventional
speech features (e.g., MFCC) along with i-vectors for each speaker as inputs
and produces frame-level activities for each speaker using a neural network
with a set of binary classification output layers. The initial estimates for
the speaker i-vectors were obtained using a spectral clustering system. For
training the model for LibriCSS, we created simulated meeting-style data
similar to that used for training the RPN model.

####  3.5.2 Diarization results on AMI

Table 3.2 shows the results on the AMI mix-headset data. We obtained
diarization outputs using the VB, SC, and RPN models, and then combined them
with our proposed DOVER-Lap method, using different label mapping algorithms.
The results are presented in terms of missed speech (MS), false alarm (FA),
speaker confusion error (SE), and total diarization error rate (DER). We used
spyder111https://github.com/desh2608/spyder for DER-based sorting in DOVER-
Lap, and also for evaluating the final performances.

All three methods resulted in combined diarization outputs that outperformed
the single best diarization system. Since we were only combining 3 systems, we
were able to use the exponential mapping algorithm, which resulted in the best
DER of 19.86% since it uses global clique weights to perform mapping. The
polynomial-time Hungarian mapping algorithm resulted in 20.46% DER, which is
still a 1% absolute improvement over the best system. Nevertheless, since it
performs pair-wise mapping, the resulting SE was 0.6% worse than that obtained
by the exponential method.