// doc/kws.dox
  
  
  // Copyright 2013  Johns Hopkins University (author: Guoguo Chen)
  
  // See ../../COPYING for clarification regarding multiple authors
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  
  //  http://www.apache.org/licenses/LICENSE-2.0
  
  // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
  // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
  // MERCHANTABLITY OR NON-INFRINGEMENT.
  // See the Apache 2 License for the specific language governing permissions and
  // limitations under the License.
  
  namespace kaldi {
  
  /**
    \page kws Keyword Search in Kaldi
  
    \section kws_intro Introduction
    This page describes the keyword search module in Kaldi. Our implementation
    includes the following features:
  
    - Lattice indexing for fast keyword retrieval.
    - Proxy keywords to handle out-of-vocabulary (OOV) problem.
  
    In the following document, we will focus on word level keyword search for
    simplicity purpose, but our implementation naturally supports word level as
    well as subword level keyword search -- both our LVCSR module and the KWS
    module are implemented using weighted finite state transducer (WFST), and the
    algorithm should work as long as the symbol table properly maps words/subwords
    to integers.
  
    The rest of this document is organized as follows: in section \ref kws_system
    "Typical Kaldi KWS system", we describe the basic components of a Kaldi KWS
    system; in section \ref kws_proxy "Proxy keywords", we explain how we use
    proxy keywords to handle the keywords that are not in the vocabulary; finally
    in section \ref kws_scripts "Babel scripts", we walk through the KWS related
    scripts we created for IARPA Babel project.
  
    \section kws_system Typical Kaldi KWS system
    An example of a Kaldi KWS system can be found in this paper <a href=
    http://www.clsp.jhu.edu/~guoguo/papers/icassp2013_lexicon_value.pdf> "Quantifying
    the Value of Pronunciation Lexicons for Keyword Search in Low Resource
    Languages", G. Chen, S. Khudanpur, D. Povey, J. Trmal, D. Yarowsky and
    O. Yilmaz</a>. Generally, a KWS system consists of two parts: a LVCSR module
    that decodes the search collection and generates corresponding lattices, and a
    KWS module that makes index for the lattices and searches the keywords from
    the generated index.
  
    Our basic LVCSR system is a SGMM + MMI system. We use standard PLP analysis to
    extract 13 dimensional acoustic features, and follow a typical maximum
    likelihood acoustic training recipe, beginning with a flat-start
    initialization of context-independent phonetic HMMs, and ending with speaker
    adaptive training (SAT) of state-clustered triphone HMMs with GMM output
    densities. This is followed by the training of a universal background model
    from speaker-transformed training data, which is then used to train a subspace
    Gaussian mixture model (SGMM) for the HMM emission probabilities. Finally, all
    the training speech is decoded using the SGMM system, and boosted maximum
    mutual information (BMMI) training of the SGMM parameters is performed. More
    details can be found in egs/babel/s5b/run-1-main.sh.
  
    We also build additional systems besides the basic SGMM + MMI system. For
    example, a hybrid deep neural network (DNN) system, details in
    egs/babel/s5b/run-2a-nnet-gpu.sh, a bottleneck feature system, details in
    egs/babel/s5b/run-8a-kaldi-bnf.sh, etc. All those systems decode and generate
    lattices for the same search collection, which will then be sent to the KWS
    module for indexing and searching. We do system combination on the retrieved
    results instend of lattices.
  
    Lattices generated by the above LVCSR systems are processed using the lattice
    indexing technique described in <a href=
    https://wiki.inf.ed.ac.uk/twiki/pub/CSTR/ListenSemester2201314/taslp_2011.pdf>
    "Lattice indexing for spoken term detection", D. Can, M. Saraclar, Audio,
    Speech, and Language Processing</a>. The lattices of all the utterances in the
    search collection are converted from individual weighted finite state
    transducers (WFST) to a single generalized factor transducer structure in
    which the start-time, end-time and lattice posterior probability of each word
    token is stored as a 3-dimensional cost. This factor transducer is actually an
    inverted index of all word sequences seen in the lattices. Given a keyword or
    phrase, we then create a simple finite state machine that accepts the
    keyword/phrase and composes it with the factor transducer to obtain all
    occurrences of the keyword/phrase in the search collection, along with the
    utterance ID, start-time and end-time and lattice posterior probability of
    each occurrence. All those occurrences are sorted according to their posterior
    probabilities and a YES/NO decision is assigned to each instance using the
    method proposed in the paper "Rapid and Accurate Spoken Term Detection".
    
    \section kws_proxy Proxy keywords
    Our proxy keyword generation process has been described in this paper <a href=
    http://www.clsp.jhu.edu/~guoguo/papers/asru2013_proxy_keyword.pdf> "Using Proxies
    for OOV Keywords in the Keyword Search Task", G. Chen, O. Yilmaz, J. Trmal,
    D. Povey, S. Khudanpur</a>. We originally proposed this method to solve the
    OOV problem of the word lattices -- if a keyword is not in the vocabulary of
    the LVCSR system, it will not appear in the search collection lattices, even
    though the keyword is actually spoken in the search collection. This is a
    known problem of LVCSR based keyword search systems, and there are ways to
    handle this, for example, building a subword system. Our approach is to find
    acoustically similar in-vocabulary (IV) words for the OOV keyword, and use
    them as proxy keywords instead of the original OOV keyword. The advantage is
    that we do not have to build additional subword systems. In a upcoming
    Interspeech paper "Low-Resource Open Vocabulary Keyword Search Using Point
    Process Models", C. Liu, A. Jansen, G. Chen, K. Kintzley, J. Trmal,
    S. Khudanpur, we show that this technique is comparable and complementary to a
    phonetic search method based on point process model. Proxy keyword is one of
    the fuzzy search methods, and it should also improve IV keyword performance,
    although we initially brought it up to handle OOV keywords.
  
    The general proxy keyword generation process can be formulized as follows:
    \f[
    K^\prime = \mathrm{Project} \left(
               \mathrm{ShortestPath} \left(
               \mathrm{Prune} \left(
               \mathrm{Prune} \left(K \circ L_2 \circ E^\prime \right)
               \circ L_1^{-1} \right) \right) \right)
    \f]
  
    where \f$K\f$ is the original keyword, \f$L_2\f$ is a lexicon that contains
    the pronunciation of \f$K\f$. If \f$K\f$ is out of vocabulary, this lexicon
    can be obtained by using G2P tools such as Sequitur. \f$E^\prime\f$ is the
    edit distance transducer that contains the phone confusions collectioned from
    training set, and \f$L_1\f$ is the original lexicon. \f$K^\prime\f$ is then a
    WFST that contains several IV words that are acoustically similar to the
    original keyword \f$K\f$. We plug it into the search pipeline "as if" it was
    the original keyword.
  
    Note that the two pruning stages are essential, especially when you have a
    very large vocabulary. We also implemented a lazy-composition algorithm that
    only generates composed states as needed (i.e., does not generate states that
    will be pruned away later). This avoids blowing up the memory when composing
    \f$K \circ L_2 \circ E^\prime\f$ with \f$L_1^{-1}\f$.
  
    \section kws_scripts Babel scripts
  
    \subsection kws_scripts_highlevel A highlevel look
    We have set up the "push-button" scripts for IARPA Babel project. If you are
    working on Babel and want to use our scripts, you can build a SGMM + MMI
    keyword search system in the following steps (assume you are in working
    directory egs/babel/s5b/):
    - Install F4DE and put it in your path.sh
    - Modify your cmd.sh so that it can run on your cluster
    - Link one of the config files in conf/languages to ./lang.conf, e.g., 
      "ln -s conf/languages/105-turkish-limitedLP.official.conf lang.conf"
    - Modify lang.conf to point to your files instead the ones on JHU cluster
    - Run run-1-main.sh, which builds the LVCSR system
    - Run run-2-segmentation.sh, which generates segmentation for eval data
    - Run run-4-anydecode.sh, which decodes the eval data, makes the index and
      searches the keywords
  
    Similarly, you can build DNN systems, BNF systems, Semi-supervised systems,
    etc. The KWS stuff happens in run-4-anydecode.sh. We will have a detailed look
    of how to do keyword search below, in case you want to do keyword search for
    some other resources. We assume that you have decoded your search collection
    and generated the corresponding lattices.
  
    \subsection kws_scripts_dataprep Prepare KWS data
    Typically, we generate KWS data directories under the search collection data
    directory. For example, if you have a search collection called dev10h.uem, you
    will have a data directory for it called data/dev10h.uem/. We create KWS data
    directories under this directory, e.g., data/dev10h.uem/kws/. Before creating
    KWS data directories, you have to get three files ready by hand: a ecf file
    that contains the search collection information, a kwlist file that lists all
    the keywords and a rttm file for scoring. Sometimes you may have to prepare
    those files by yourself, for example, you can generate the rttm file by force
    aligning the search collection with a trained model. Below we show the format
    of those files.
  
    Example ECF file:
    \verbatim
    <ecf source_signal_duration="483.825" language="" version="Excluded noscore regions">
      <excerpt audio_filename="YOUR_AUDIO_FILENAME" channel="1" tbeg="0.000" dur="483.825" source_type="splitcts"/>
    </ecf>
    \endverbatim
  
    Example KWLIST file:
    \verbatim
    <kwlist ecf_filename="ecf.xml" language="tamil" encoding="UTF-8" compareNormalize="" version="Example keywords">
      <kw kwid="KW204-00001">
        <kwtext>செய்றத</kwtext>
      </kw>
      <kw kwid="KW204-00002">
        <kwtext>சொல்லுவியா</kwtext>
      </kw>
    </kwlist>
    \endverbatim
  
    Example RTTM file:
    \verbatim
    SPEAKER YOUR_AUDIO_FILENAME 1 5.87 0.370 <NA> <NA> spkr1 <NA>
    LEXEME YOUR_AUDIO_FILENAME 1 5.87 0.370 ஹலோ lex spkr1 0.5
    SPEAKER YOUR_AUDIO_FILENAME 1 8.78 2.380 <NA> <NA> spkr1 <NA>
    LEXEME YOUR_AUDIO_FILENAME 1 8.78 0.300 உம்ம் lex spkr1 0.5
    LEXEME YOUR_AUDIO_FILENAME 1 9.08 0.480 அதான் lex spkr1 0.5
    LEXEME YOUR_AUDIO_FILENAME 1 9.56 0.510 சரியான lex spkr1 0.5
    LEXEME YOUR_AUDIO_FILENAME 1 10.07 0.560 மெசேஜ்டா lex spkr1 0.5
    LEXEME YOUR_AUDIO_FILENAME 1 10.63 0.350 சான்ஸே lex spkr1 0.5
    LEXEME YOUR_AUDIO_FILENAME 1 10.98 0.180 இல்லயே lex spkr1 0.5
    \endverbatim 
  
    With the above three files ready, you can start preparing KWS data directory.
    If you just want to do a basic keyword search, running the following should be
    enough:
    \verbatim
    local/kws_setup.sh \
      --case_insensitive $case_insensitive \
      --rttm-file $my_rttm_file \
      $my_ecf_file $my_kwlist_file data/lang $dataset_dir
    \endverbatim 
  
    If you want to do fuzzy search for your OOV keywords, you can run the
    following few commands, which first collects the phone confusions, and trains
    a G2P model, and then creates the KWS data directory:
    \verbatim
    #Generate the confusion matrix
    #NB, this has to be done only once, as it is training corpora dependent,
    #instead of search collection dependent
    if [ ! -f exp/conf_matrix/.done ] ; then
      local/generate_confusion_matrix.sh --cmd "$decode_cmd" --nj $my_nj  \
        exp/sgmm5/graph exp/sgmm5 exp/sgmm5_ali exp/sgmm5_denlats  exp/conf_matrix
      touch exp/conf_matrix/.done
    fi
    confusion=exp/conf_matrix/confusions.txt
  
    if [ ! -f exp/g2p/.done ] ; then
      local/train_g2p.sh  data/local exp/g2p
      touch exp/g2p/.done
    fi
    local/apply_g2p.sh --nj $my_nj --cmd "$decode_cmd" \
      --var-counts $g2p_nbest --var-mass $g2p_mass \
      $kwsdatadir/oov.txt exp/g2p $kwsdatadir/g2p
    L2_lex=$kwsdatadir/g2p/lexicon.lex
  
    L1_lex=data/local/lexiconp.txt
    local/kws_data_prep_proxy.sh \
      --cmd "$decode_cmd" --nj $my_nj \
      --case-insensitive true \
      --confusion-matrix $confusion \
      --phone-cutoff $phone_cutoff \
      --pron-probs true --beam $beam --nbest $nbest \
      --phone-beam $phone_beam --phone-nbest $phone_nbest \
      data/lang  $data_dir $L1_lex $L2_lex $kwsdatadir
    \endverbatim
  
    \subsection kws_scripts_index_and_search Indexing and searching
    At this stage we assume you have decoded your search collection and generated
    the corresponding lattices. Running the following script will take care of
    indexing and searching:
    \verbatim
    local/kws_search.sh --cmd "$cmd" \
      --max-states ${max_states} --min-lmwt ${min_lmwt} \
      --max-lmwt ${max_lmwt} --skip-scoring $skip_scoring \
      --indices-dir $decode_dir/kws_indices $lang_dir $data_dir $decode_dir
    \endverbatim
  
    If your KWS data directory has an extra ID, e.g., oov (this is useful when you
    have different KWS setups, in this case, your directory will look something
    like data/dev10h.uem/kws_oov), you have to run it with the extraid option:
    \verbatim
    local/kws_search.sh --cmd "$cmd" --extraid $extraid  \
      --max-states ${max_states} --min-lmwt ${min_lmwt} \
      --max-lmwt ${max_lmwt} --skip-scoring $skip_scoring \
      --indices-dir $decode_dir/kws_indices $lang_dir $data_dir $decode_dir
    \endverbatim
  */
  }