Enhancements of viterbi search for fast unit selection synthesis

Daniel Tihelka, Jiří Kala, Jindřich MatoušekInterspeech 2010

TL;DR

This paper tackles the computational bottleneck in unit selection Text-to-Speech (TTS) systems by optimizing the Viterbi search algorithm. They introduce a flexible pruning strategy that significantly speeds up synthesis without a noticeable drop in speech quality, making natural-sounding TTS more accessible for real-time applications.

What Problem Does This Paper Address?

Unit selection TTS is known for producing highly natural-sounding speech by stitching together pre-recorded speech units. However, the process of finding the optimal sequence of these units from a massive database can be computationally very expensive, especially for large speech corpora. This slowness makes it challenging to deploy such systems in real-time applications that require fast responses, like interactive voice assistants or on-demand synthesis services. The core problem is balancing the desire for high-quality, natural speech with the need for efficient, fast synthesis.

Methods

The authors build upon existing Viterbi search optimizations for unit selection TTS. Their approach introduces several enhancements:

  • Baseline Search Algorithm: A basic Viterbi search is described, which involves computing target costs (TC) and join costs (JC) between candidate units. A simple heuristic is introduced to avoid computing join costs if a predecessor's cumulative cost is already worse than the best found so far for the current candidate. This is referred to as the "baseline algorithm."
  • Enhanced Search Algorithm: This section introduces two key admissible stopping criteria inspired by prior work:
  • Admissible stopping of candidates evaluation: This limits the number of candidates considered for each unit to a predefined beam width (Ke). Candidates beyond this beam are only evaluated if they have a chance to yield a better cumulative cost than the best ones within the beam.
  • Admissible stopping of JC computing: This criterion stops the computation of join costs if no predecessor unit can contribute to a better cumulative cost than the best one already found for the current candidate.
  • Pre-pruning after target cost evaluation: To further accelerate the search, especially when Ke is large, an additional pruning step is introduced. This "pre-pruning" limits the number of candidates considered before the admissible stopping criteria are applied. It's controlled by a constant KT and a percentage K%, effectively setting an upper bound on the number of candidates to examine at each step.

The core idea is to intelligently prune the search space by avoiding unnecessary computations of join costs and by limiting the number of candidate units considered, all while ensuring that the optimal path is not discarded.

Datasets

The experiments were conducted using a speech corpus consisting of 12,277 recorded sentences, totaling 17 hours and 49 minutes of speech (excluding pauses). This corpus was previously described in [6]. No new benchmarks were introduced; rather, the existing corpus was used to evaluate the proposed optimizations.

Key Insights and Ideas

  • The "sweet spot" of pruning: The paper demonstrates that aggressive pruning (low KT, K%, and Ke) can lead to dramatic speedups without significantly degrading speech quality. This suggests that for many applications, a slightly less than "perfect" search path is acceptable if it means much faster synthesis.
  • Flexibility is key: The introduced parameters (KT, K%, Ke) offer a high degree of flexibility, allowing users to tune the search based on available computational resources and desired speed-quality trade-offs. This makes the system adaptable to various deployment scenarios.
  • Listening tests are crucial: While speedup metrics are important, the paper emphasizes the necessity of subjective listening tests to confirm that performance gains don't come at the cost of perceptible quality degradation. Their methodology of focusing on the "worst-case" differing phrases provides a pessimistic but robust evaluation.

Key Results

  • Significant Speedups: The optimized Viterbi search achieved substantial speedups compared to the baseline. The most aggressive configuration (KT=100, K%=10, Ke=50) resulted in a speedup of 58.4 times in terms of join cost computations compared to the baseline, and 244.5 times compared to the basic Viterbi search.
  • Minimal Quality Impact: Listening tests, focusing on the most differing phrases between optimized and baseline searches, showed no significant negative impact on speech quality. The average CCR (Comparison Category Rating) scores were very close to zero, indicating no strong preference for either the baseline or the optimized variants.
  • High Percentage of Differing Phrases: Even with aggressive pruning, the number of phrases where the optimized search selected a different candidate sequence was relatively low (e.g., 4.8% for the conservative setting, up to 71.7% for the aggressive setting). This indicates that the optimizations often find the same or very similar sequences.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while their chosen test set for listening tests focuses on the "worst cases," it's still possible that other, less differing phrases might show more noticeable quality deterioration with aggressive pruning.
  • The speedup measurements are based on join cost computations, which is a good proxy but doesn't directly reflect real-world latency on specific hardware.
  • Future Work: The paper doesn't explicitly detail future work, but the flexibility of the proposed parameters suggests that further exploration of optimal parameter settings for different application domains and hardware constraints would be a natural next step. Investigating the impact of these optimizations on other aspects of TTS quality, such as prosody, could also be a direction.

Summary updated

BibTeX
@inproceedings{tihelka2010enhancements,
  author = {Daniel Tihelka and Jiří Kala and Jindřich Matoušek},
  title = {{Enhancements of viterbi search for fast unit selection synthesis}},
  booktitle = {Interspeech},
  year = {2010},
}
Figure