Kaldi学习笔记

1.2.1 timit_data_prepare.sh

1.2.2 timit_prepare_dict.sh

1.2.3 utils/prepare_lang.sh

参数:
1. --position-dependent-phones false, 音素是否设置为与在词中的位置相关
  (B)egin, (E)nd, (I)nternal and (S)ingleton，设置相关后，单个音素会扩展为4个。
a_B 6
a_E 7
a_I 8
a_S 9
2. "sil" "!SIL" "<UNK>" 写入到oov.txt

1.2.4 timit_format_data.sh

1.3.1 make_mfcc.sh

1.3.2 compute_cmvn_stats.sh

1.4.1 steps/train_mono.sh

1. TrainingGraphCompiler
   
   • CompileGraphFromText
   • MakeLinearAcceptor: 为每个语句生成一个acceptor，(ilabel, olabel, 1), 其中label为抄本当前音素
   • compose acceptor & lex_fst
   • make cfst ContextFst
   • ctx2word_fst
   • trans2word_fst

1.4.2 utils/mkgraph.sh

1. fst操作
   
   1. fsttablecompose: compose
   2. fstminmizeencode: min
   3. fstdeterminizestart: det
   4. fstcomposecontext: context expend
   5. fstisstochastic: ????
   6. make-h-transducer: 生成HMM的fst,Ha.fst
   7. 主要实现：H*det(C*det(L * G))
   8. add-self-loops: 可能是hmm自身跳转

1.4.3 steps/decode.sh

1.5.1 steps/align_si.sh

1.5.2 steps/train_deltas.sh

1.6.1 steps/train_lda_mllt.sh

silence_scale=0.0
void WeightSilencePost(const TransitionModel &trans_model,
                       const ConstIntegerSet<int32> &silence_set,
                       BaseFloat silence_scale,
                       Posterior *post) {
  for (size_t i = 0; i < post->size(); i++) {
    std::vector<std::pair<int32, BaseFloat> > this_post;
    this_post.reserve((*post)[i].size());
    for (size_t j = 0; j < (*post)[i].size(); j++) {
      int32 tid = (*post)[i][j].first,
          phone = trans_model.TransitionIdToPhone(tid);
      BaseFloat weight = (*post)[i][j].second;
      if (silence_set.count(phone) != 0) {  // is a silence.
        if (silence_scale != 0.0)
          this_post.push_back(std::make_pair(tid, weight*silence_scale));
      } else {
        this_post.push_back(std::make_pair(tid, weight));
      }
    }
    (*post)[i].swap(this_post);
  }
}

Posterior pdf_post;
ConvertPosteriorToPdfs(trans_model, post, &pdf_post);
for (int32 i = 0; i < feats.NumRows(); i++) {
  SubVector<BaseFloat> feat(feats, i);
  for (size_t j = 0; j < pdf_post[i].size(); j++) {
    int32 pdf_id = pdf_post[i][j].first;
    BaseFloat weight = RandPrune(pdf_post[i][j].second, rand_prune);
    if (weight != 0.0) {
      lda.Accumulate(feat, pdf_id, weight);
    }
  }
}

void LdaEstimate::Estimate(const LdaEstimateOptions &opts,
                           Matrix<BaseFloat> *m,
                           Matrix<BaseFloat> *mfull) const {
  int32 target_dim = opts.dim;
  KALDI_ASSERT(target_dim > 0);
  // between-class covar is of most rank C-1
  KALDI_ASSERT(target_dim <= Dim() && (target_dim < NumClasses() || opts.allow_large_dim));
  int32 dim = Dim();

  double count;
  SpMatrix<double> total_covar, bc_covar;
  Vector<double> total_mean;
  GetStats(&total_covar, &bc_covar, &total_mean, &count);

  // within-class covariance
  SpMatrix<double> wc_covar(total_covar);
  wc_covar.AddSp(-1.0, bc_covar);
  TpMatrix<double> wc_covar_sqrt(dim);
  try {
    wc_covar_sqrt.Cholesky(wc_covar);
  } catch (...) {
    BaseFloat smooth = 1.0e-03 * wc_covar.Trace() / wc_covar.NumRows();
    KALDI_LOG << "Cholesky failed (possibly not +ve definite), so adding " << smooth
              << " to diagonal and trying again.\n";
    for (int32 i = 0; i < wc_covar.NumRows(); i++)
      wc_covar(i, i) += smooth;
    wc_covar_sqrt.Cholesky(wc_covar);    
  }
  Matrix<double> wc_covar_sqrt_mat(wc_covar_sqrt);
  // copy wc_covar_sqrt to Matrix, because it facilitates further use
  wc_covar_sqrt_mat.Invert();

  SpMatrix<double> tmp_sp(dim);
  tmp_sp.AddMat2Sp(1.0, wc_covar_sqrt_mat, kNoTrans, bc_covar, 0.0);
  Matrix<double> tmp_mat(tmp_sp);

  Matrix<double> svd_u(dim, dim), svd_vt(dim, dim);
  Vector<double> svd_d(dim);
  tmp_mat.Svd(&svd_d, &svd_u, &svd_vt);
  SortSvd(&svd_d, &svd_u);

  KALDI_LOG << "Data count is " << count;
  KALDI_LOG << "LDA singular values are " << svd_d;

  KALDI_LOG << "Sum of all singular values is " << svd_d.Sum();
  KALDI_LOG << "Sum of selected singular values is " <<
      SubVector<double>(svd_d, 0, target_dim).Sum();

  Matrix<double> lda_mat(dim, dim);
  lda_mat.AddMatMat(1.0, svd_u, kTrans, wc_covar_sqrt_mat, kNoTrans, 0.0);

  // finally, copy first target_dim rows to m
  m->Resize(target_dim, dim);
  m->CopyFromMat(lda_mat.Range(0, target_dim, 0, dim));

  if (mfull != NULL) {
    mfull->Resize(dim, dim);
    mfull->CopyFromMat(lda_mat);
  }

  if (opts.within_class_factor != 1.0) { // This is not the normal code path;
    // it's intended for use in neural net inputs.
    for (int32 i = 0; i < svd_d.Dim(); i++) {
      BaseFloat old_var = 1.0 + svd_d(i), // the total variance of that dim..
          new_var = opts.within_class_factor + svd_d(i), // the variance we want..
          scale = sqrt(new_var / old_var);
      if (i < m->NumRows())
        m->Row(i).Scale(scale);
      if (mfull != NULL)
        mfull->Row(i).Scale(scale);
    }
  }

  if (opts.remove_offset) {
    AddMeanOffset(total_mean, m);
    if (mfull != NULL)
      AddMeanOffset(total_mean, mfull);
  }  
}

1.7.1 feature

#zss splice feature
feats_cv="ark,s,cs:utils/filter_scp.pl $dir/valid_uttlist $data/feats.scp | apply-cmvn --norm-vars=$norm_vars $data/norm_global_mv.ark scp:- ark:- | splice-feats ark:- ark:-|"
#dnn Generate the splice transform
echo "Using splice +/- $splice , step $splice_step"
feature_transform=$dir/tr_splice$splice-$splice_step.nnet
utils/nnet/gen_splice.py --fea-dim=$feat_dim --splice=$splice --splice-step=$splice_step > $feature_transform

1.8.1 网络结构(输入、输出、隐层）

1.8.2 get_lda.sh

1.8.3 get_egs.sh

awk '{print $1}' $data/utt2spk | utils/shuffle_list.pl | head -$num_utts_subset \
	> $dir/valid_uttlist || exit 1;

1.8.4 训练

1. 问题
   
   1. TODO shuffle是什么？
      
   2. TODO 如何利用hmm初始化,feature is not equal dimension
      
   3. TODO 如何使用nnet的priors_
      

      给网络加上先验，训练时并没有用，用于识别时。

   4. TODO dropout, bottleneck如何使用
      

      Dropout Component

2. 数据结构
   
   • Example

   struct NnetExample {
   /// The label(s) for this frame; in the normal case, this will be a vector of
   /// length one, containing (the pdf-id, 1.0)
   std::vector<std::pair<int32, BaseFloat> > labels;
   /// The input data-- typically with NumRows() more than
   /// labels.size(), it includes features to the left and
   /// right as needed for the temporal context of the network.
   /// (see the left_context variable).
   CompressedMatrix input_frames;
   /// The number of frames of left context (we can work out the #frames
   /// of right context from input_frames.NumRows(), labels.size(), and this).
   int32 left_context;
   /// The speaker-specific input, if any, or an empty vector if
   /// we're not using this features. We'll append this to each of the
   Vector<BaseFloat> spk_info; 
   /// Set the label of this example to the specified pdf_id 
   /// with the specified weight.
   void SetLabelSingle(int32 pdf_id, BaseFloat weight = 1.0);
   /// Get the maximum weight label (pdf_id and weight) of this example. 
   int32 GetLabelSingle(BaseFloat *weight = NULL);
   };
   

   • Component

   // nnet/nnet-activation.h
   class Softmax : public Component
   class BlockSoftmax : public Component
   class Sigmoid : public Component
   class Tanh : public Component 
   class Dropout : public Component
   

   • NnetSimpleTrainer

   //里面没有prior_的信息, 那么prior在那里用？
   void NnetSimpleTrainer::TrainOnExample(const NnetExample &value) {
   buffer_.push_back(value);
   if (static_cast<int32>(buffer_.size()) == config_.minibatch_size)
   TrainOneMinibatch();
   }
   void NnetSimpleTrainer::TrainOneMinibatch() {
   
   KALDI_ASSERT(!buffer_.empty());
   // The following function is declared in nnet-update.h.
   logprob_this_phase_ += DoBackprop(*nnet_,
   buffer_,
   nnet_);
   weight_this_phase_ += TotalNnetTrainingWeight(buffer_);
   buffer_.clear();
   minibatches_seen_this_phase_++;
   if (minibatches_seen_this_phase_ == config_.minibatches_per_phase) {
   bool first_time = false;
   BeginNewPhase(first_time);
   }
   }
   

   • AmNnet

   //Amnet
   class AmNnet {
     Nnet nnet_;
     Vector<BaseFloat> priors_; 
   };
   

3. 训练工具
   
   • nnet-init: Initialize the neural network from a config file with a line for each component
   • nnet-am-init: 好像只把nnet,tree, topo写到一个文件了
   • nnet-get-egs: 生成examples(准备网络输入格式的数据，上下文特征,pdf标签)

   ProcessFile(feats, pdf_post, key, left_context, right_context, const_feat_dim,
   keep_proportion, &num_frames_written, &example_writer)
   for (int32 i = 0; i < feats.NumRows(); i++) {
   int32 count = GetCount(keep_proportion); // number of times
   // we'll write this out (1 by default).
   if (count > 0) {
   // Set up "input_frames".
   for (int32 j = -left_context; j <= right_context; j++) {
   int32 j2 = j + i;
   if (j2 < 0) j2 = 0;
   if (j2 >= feats.NumRows()) j2 = feats.NumRows() - 1;
   SubVector<BaseFloat> src(feats.Row(j2), 0, basic_feat_dim),
   dest(input_frames, j + left_context);
   dest.CopyFromVec(src);
   }
   eg.labels = pdf_post[i];
   eg.input_frames = input_frames;
   if (const_feat_dim > 0) {
   // we'll normally reach here if we're using online-estimated iVectors.
   SubVector<BaseFloat> const_part(feats.Row(i),
   basic_feat_dim, const_feat_dim);
   eg.spk_info.CopyFromVec(const_part);
   }
   std::ostringstream os;
   os << utt_id << "-" << i;
   
   
   std::string key = os.str(); // key is <utt_id>-<frame_id>
   
   
   for (int32 c = 0; c < count; c++)
   example_writer->Write(key, eg);
   }
   }
   

   • nnet-shuffle-egs: from the input to output, but randomly shuffle the order
   • nnet-subset-egs: Creates a random subset of the input examples, of a specified size
   • nnet-train-transitions

   void SetPriors(const TransitionModel &tmodel,
                  const Vector<double> &transition_accs,
                  double prior_floor,
                  AmNnet *am_nnet) {
     KALDI_ASSERT(tmodel.NumPdfs() == am_nnet->NumPdfs());
     Vector<BaseFloat> pdf_counts(tmodel.NumPdfs());
     KALDI_ASSERT(transition_accs(0) == 0.0); // There is
     // no zero transition-id.
     for (int32 tid = 1; tid < transition_accs.Dim(); tid++) {
       int32 pdf = tmodel.TransitionIdToPdf(tid);
       pdf_counts(pdf) += transition_accs(tid);
     }
     BaseFloat sum = pdf_counts.Sum();
     KALDI_ASSERT(sum != 0.0);
     KALDI_ASSERT(prior_floor > 0.0 && prior_floor < 1.0);
     //归一化
     pdf_counts.Scale(1.0 / sum);
     pdf_counts.ApplyFloor(prior_floor);
     pdf_counts.Scale(1.0 / pdf_counts.Sum()); // normalize again.
     am_nnet->SetPriors(pdf_counts);
   }
   

   • nnet-train-simple

   //默认minibatch(1024)，达到minibatch-size时处理
   NnetSimpleTrainer trainer(train_config,&(am_nnet.GetNnet())); 
   SequentialNnetExampleReader example_reader(examples_rspecifier); 
   for (; !example_reader.Done(); example_reader.Next(), num_examples++) 
       trainer.TrainOnExample(example_reader.Value()); // It all happens here!
   

   • nnet-train-parallel
4. 解码
   
   1. nnet2/decode.sh
      
      • nnet-latgen-faste

2.1.1 Required(Must provide)

作用: 文件唯一标识符
格式: 
FAEM0_SI1392
FAEM0_SI2022

作用: 数据文件列表
格式: FBMJ0_SI815 /home/robin1001/kaldi/kaldi-trunk/egs/timit/s5/../../../tools/sph2pipe_v2.5/sph2pipe -f wav /home/robin1001/data/timit/TIMIT/TRAIN/DR4/FBMJ0/SI815.WAV |

作用: 抄本, 注意sil扩展
格式: FAEM0_SI1392 sil ax s uw m f ao r ix vcl z ae m cl p uh l ax s n vcl d f iy l vcl s sil

作用: 说话人信息到uttid
使用: 1. 计算cmvn时, compute-cmvn-stats使用spk2uut
格式: 
utt2spk: FAEM0 FAEM0_SI1392 FAEM0_SI2022 FAEM0_SI762 FAEM0_SX132 FAEM0_SX222 FAEM0_SX312 FAEM0_SX402 FAEM0_SX42
spk2utt: FAEM0_SI1392 FAEM0

2.1.2 Timit Required

作用: 说话人到性别信息
使用: 没有看到
格式: 
FAEM0 f
FAJW0 f

作用: 训练数据时长信息
使用: 没有看到
格式: 
FAEM0_SI1392 4.761625 
FAEM0_SI2022 2.252812

作用: 扩展形式的超本，加入说话人，性别，时长信息
使用: stm和gtm这玩意儿timit独有，和解码时还有关系
格式: 
;; LABEL "O" "Overall" "Overall"
;; LABEL "F" "Female" "Female speakers"
;; LABEL "M" "Male" "Male speakers"
FAEM0_SI1392 1 FAEM0 0.0 4.761625 <O,M>  sil ax s uw m f ae n vcl d f iy l vcl s sil

作用: 这是啥？
格式: 所有内容都在这儿
;; empty.glm
  [FAKE]     =>  %HESITATION     / [ ] __ [ ] ;; hesitation token

3.1.1 Reading and modifying the code

3.3.1 Matrix & Vector

Vector<float> v(10), w(9);
for(int i=0; i < 9; i++) {
   v(i) = i; 
   w(i) = i+1;
}
Matrix<float> M(10,9);
M.AddVecVec(1.0, v, w);
//A = beta * A + alpha * B * C; B,C是否转置由kNoTrans和kTrans决定
A.AddMatMat(alpha, B, kNoTrans, C, kTrans, beta);

3.3.2 Sub-vectors & Sub-matrices

Vector<float> v(10), w(10);
Matrix<float> M(10, 10);
SubVector<float> vs(v, 1, 9), ws(w, 1, 9);
SubMatrix<float> Ms(M, 1, 9, 1, 9);
// next line would be v(2:10) += M(2:10,2:10)*w(2:10) in some
// matrix multiply & add
vs.AddMatVec(1.0, Ms, kNoTrans, ws); vs = 1.0 * Ms * ws

//切片操作
SubVector row_of_m(M, 0); // M.Row(3), return SubVector
// get a sub-vector of length 5 starting from position 0; zero it.
v.Range(0, 5).SetZero();
// get a sub-matrix of size 2x2 starting from position (5,5); zero it.
M.Range(5, 2, 5, 2).SetZero();

3.3.3 Copy

3.4.1 kaldi.mk

3.4.2 Makefile

3.5.1 parse-option(util, ParseOption类)

3.7.1 HMM topology

<Topology>
<TopologyEntry>
<ForPhones> 1 2 3 4 5 6 7 8 </ForPhones>
<State> 0 <PdfClass> 0
<Transition> 0 0.5
<Transition> 1 0.5
</State> 
<State> 1 <PdfClass> 1 
<Transition> 1 0.5
<Transition> 2 0.5
</State>  
<State> 2 <PdfClass> 2
<Transition> 2 0.5
<Transition> 3 0.5
</State>   
<State> 3
</State>   
</TopologyEntry>
</Topology>

struct HmmState {
    int32 pdf_class;
    std::vector<std::pair<int32, BaseFloat> > transitions;
};
typedef std::vector<HmmState> TopologyEntry;
class HmmTopology{
  std::vector<int32> phones_;  // 排序的音素topo集合
  std::vector<int32> phone2idx_;  // 音素到hmm topo结构的映射
  std::vector<TopologyEntry> entries_; //topo
};

3.7.2 Pdf-classes

3.7.3 Transition models (the TransitionModel object)

//             (phone, HMM-state, pdf-id) -> transition-state
//   (transition-state, transition-index) -> transition-id
 The most "natural" FST-based setups would have what we call pdf-ids on
 the input labels. However, bearing in mind that given our tree-building
 algorithms it will not always be possible to map uniquely from a pdf-id
 to a phone, this would make it hard to map from an input-label sequence
 to a phone sequence, and this is inconvenient for a number of reasons;
 it would also make it hard in general to train the transition probabilities
 using the information in the FST alone. For this reason we put identifiers
 called transition-ids on the input labels of the FST, and these can be mapped
 to the pdf-id but also to the phone and to a particular transition in a
 prototype HMM (as given in the HmmTopology object).

1. Integer identifiers used by TransitionModel
   
   1. phone: 1-based
   2. hmm-state: 0-based
   3. transition-state: 1-based
   4. transition-index 0-based
   5. transition-id: 1-based
2. transition-id as input label
   
3. Alignments in Kaldi
   
   • vector<int32>, which contains a sequence of transition-ids

3.10.1 hash-list(util/hash-list.h)

3.10.2 kaldi-table(util/kaldi-table)

3.13.1 两种不同实现

5.1.1 DecodableInterface

5.1.2 SimpleDecoder

class Token {
   public:
    Arc arc_;
    Token *prev_;
    int32 ref_count_;
    Weight weight_;
    ...
};

bool LatticeFasterDecoder::Decode(DecodableInterface *decodable) {
    for(int32 frame = 0; !decodable.IsLastFrame(frame-1); frame++) {
        ClearToks(prev_toks_);
        std::swap(cur_toks_, prev_toks_);
        ProcessEmitting(decodable, frame);
        ProcessNonemitting();
        PruneToks(cur_toks_, beam_);
     }
}

// Outputs an FST corresponding to the raw, state-level
// tracebacks.
bool LatticeFasterDecoder::GetRawLattice(fst::MutableFst<LatticeArc> *ofst) const {
  typedef LatticeArc Arc;
  typedef Arc::StateId StateId;
  typedef Arc::Weight Weight;
  typedef Arc::Label Label;
  ofst->DeleteStates();
  // num-frames plus one (since frames are one-based, and we have
  // an extra frame for the start-state).
  int32 num_frames = active_toks_.size() - 1;
  KALDI_ASSERT(num_frames > 0);
  //生成token到id的映射， 每一帧上都有active token list，顺序访问编号
  unordered_map<Token*, StateId> tok_map(num_toks_/2 + 3); // bucket count
  // First create all states.
  for (int32 f = 0; f <= num_frames; f++) {
    if (active_toks_[f].toks == NULL) {
      KALDI_WARN << "GetRawLattice: no tokens active on frame " << f
                 << ": not producing lattice.\n";
      return false;
    }
    for (Token *tok = active_toks_[f].toks; tok != NULL; tok = tok->next)
      tok_map[tok] = ofst->AddState();
  }
  // Now create all arcs，按照token之间跳转关系加上弧Arc，有没有超级简单啊，fst就是好
  StateId cur_state = 0; // we rely on the fact that we numbered these
  // consecutively (AddState() returns the numbers in order..)
  for (int32 f = 0; f <= num_frames; f++) {
    for (Token *tok = active_toks_[f].toks; tok != NULL; tok = tok->next,
             cur_state++) {
      for (ForwardLink *l = tok->links;
           l != NULL;
           l = l->next) {
        unordered_map<Token*, StateId>::const_iterator iter =
            tok_map.find(l->next_tok);
        StateId nextstate = iter->second;
        KALDI_ASSERT(iter != tok_map.end());
        BaseFloat cost_offset = 0.0;
        if (l->ilabel != 0) { // emitting..
          KALDI_ASSERT(f >= 0 && f < cost_offsets_.size());
          cost_offset = cost_offsets_[f];
        }
        Arc arc(l->ilabel, l->olabel,
                Weight(l->graph_cost, l->acoustic_cost - cost_offset),
                nextstate);
        ofst->AddArc(cur_state, arc);
      }
      if (f == num_frames) {
        std::map<Token*, BaseFloat>::const_iterator iter =
            final_costs_.find(tok);
        if (iter != final_costs_.end())
          ofst->SetFinal(cur_state, LatticeWeight(iter->second, 0));
      }
    }
  }
  KALDI_ASSERT(cur_state == ofst->NumStates());
  return (cur_state != 0);
}

//先计算raw lattice，然后生成最短路径的lattice
bool LatticeFasterDecoder::GetBestPath(fst::MutableFst<LatticeArc> *ofst) const {
  fst::VectorFst<LatticeArc> fst;
  if (!GetRawLattice(&fst)) return false;
  // std::cout << "Raw lattice is:\n";
  // fst::FstPrinter<LatticeArc> fstprinter(fst, NULL, NULL, NULL, false, true);
  // fstprinter.Print(&std::cout, "standard output");
  ShortestPath(fst, ofst);
  return true;
}
//由最短路径得到的fst，其ilabel就是alignment， 其olabel就是words
bool GetLinearSymbolSequence(const Fst<Arc> &fst,
                             vector<I> *isymbols_out,
                             vector<I> *osymbols_out,
                             typename Arc::Weight *tot_weight_out) {
  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  Weight tot_weight = Weight::One();
  vector<I> ilabel_seq;
  vector<I> olabel_seq;

  StateId cur_state = fst.Start();
  if (cur_state == kNoStateId) {  // empty sequence.
    if (isymbols_out != NULL) isymbols_out->clear();
    if (osymbols_out != NULL) osymbols_out->clear();
    if (tot_weight_out != NULL) *tot_weight_out = Weight::Zero();
    return true;
  }
  while (1) {
    Weight w = fst.Final(cur_state);
    if (w != Weight::Zero()) {  // is final..
      tot_weight = Times(w, tot_weight);
      if (fst.NumArcs(cur_state) != 0) return false;
      if (isymbols_out != NULL) *isymbols_out = ilabel_seq;
      if (osymbols_out != NULL) *osymbols_out = olabel_seq;
      if (tot_weight_out != NULL) *tot_weight_out = tot_weight;
      return true;
    } else {
      if (fst.NumArcs(cur_state) != 1) return false; //什么意思，因为这是最短路径的lattice

      ArcIterator<Fst<Arc> > iter(fst, cur_state);  // get the only arc.
      const Arc &arc = iter.Value();
      tot_weight = Times(arc.weight, tot_weight);
      if (arc.ilabel != 0) ilabel_seq.push_back(arc.ilabel);
      if (arc.olabel != 0) olabel_seq.push_back(arc.olabel);
      cur_state = arc.nextstate;
    }
  }
}

5.2.1 数据结构

1. EventMap
   
   • EventKeyType: int
   • EventValueType: int
   • EventAnswerType: int
   • typedef std::vector<std::pair<EventKeyType,EventValueType> > EventType;
   • ConstantEventMap: 叶子节点

   answer_: 节点id，mono-tree中就是hmm-state的编号

   • TableEventMap:

   EventKeyType key_: key, -1时子树为叶节点， P时为hmm_sets
   std::vector<EventMap*> table_: 各个子树
   Lookup: 二分查找，event中查找key，返回id
   MultiMap: 空查找所有，否则查找ans
   MaxResult: 共多少个节点，返回最大节点编号
   

2. ContextDependency
   
   • gmm-init-mono中如何构建一颗树
   • GetPdfInfo: 返回每个pdf对应的音素状态
   • to_pdf_
3. TransitionModel
   
   • state2id_
   • id2state_
   • triples_
   • ComputeTriples: 计算triples_
   • ConputeDerived: 计算state2id_, id2state_
   • InitializeProbs: 计算trans_id的log prob
   • exp/mono/tree 格式： CE TE SE

5.2.2 Clusterable

class GaussClusterable: public Clusterable {
public:
virtual void Add(const Clusterable &other_in);
virtual void Sub(const Clusterable &other_in);
virtual BaseFloat Normalizer() const { return count_; }
virtual Clusterable *Copy() const;
double count_;
Matrix<double> stats_; // two rows: sum, then sum-squared.
double var_floor_; // should be common for all objects created.

5.2.3 计算似然和似然增益

5.2.4 tools & core code

1. acc-tree-stats
   

   for (int i = -N; i < static_cast<int>(split_alignment.size()); i++) {
     // consider window starting at i, only if i+P is within
     // list of phones.
     if (i + P >= 0 && i + P < static_cast<int>(split_alignment.size())) {
       int32 central_phone =
           MapPhone(phone_map,
                    trans_model.TransitionIdToPhone(split_alignment[i+P][0]));
       bool is_ctx_dep = ! std::binary_search(ci_phones.begin(),
                                              ci_phones.end(),
                                              central_phone);
       EventType evec;
       for (int j = 0; j < N; j++) {
         int phone;
         if (i + j >= 0 && i + j < static_cast<int>(split_alignment.size()))
           phone =
               MapPhone(phone_map,
                        trans_model.TransitionIdToPhone(split_alignment[i+j][0]));
         else
           phone = 0;  // ContextDependency class uses 0 to mean "out of window";
         // we also set the phone arbitrarily to 0
   
         // Don't add stuff to the event that we don't "allow" to be asked, due
         // to the central phone being context-independent: check "is_ctx_dep".
         // Why not just set the value to zero in this
         // case?  It's for safety.  By omitting the key from the event, we
         // ensure that there is no way a question can ever be asked that might
         // give an inconsistent answer in tree-training versus graph-building.
         // [setting it to zero would have the same effect given the "normal"
         // recipe but might be less robust to changes in tree-building recipe].
         if (is_ctx_dep || j == P)
           evec.push_back(std::make_pair(static_cast<EventKeyType>(j), static_cast<EventValueType>(phone)));
       }
       for (int j = 0; j < static_cast<int>(split_alignment[i+P].size());j++) {
         // for central phone of this window...
         EventType evec_more(evec);
         int32 pdf_class = trans_model.TransitionIdToPdfClass(split_alignment[i+P][j]);
         // pdf_class will normally by 0, 1 or 2 for 3-state HMM.
         std::pair<EventKeyType, EventValueType> pr(kPdfClass, pdf_class);
         evec_more.push_back(pr);
         std::sort(evec_more.begin(), evec_more.end());  // these must be sorted!
         if (stats->count(evec_more) == 0)
           (*stats)[evec_more] = new GaussClusterable(dim, var_floor);
   
         BaseFloat weight = 1.0;
         (*stats)[evec_more]->AddStats(features.Row(cur_pos), weight);
         cur_pos++;
       }
     }
   }
   

2. cluster-phones
   

     // split by phone,根据中间音素分类，并统计
     SplitStatsByKey(retained_stats, P, &split_stats);
     std::vector<Clusterable*> summed_stats;  // summed up by phone.
     SumStatsVec(split_stats, &summed_stats);
     // 树聚类
     std::vector<int32> assignments;  // assignment of phones to clusters. dim == summed_stats.size().
     std::vector<int32> clust_assignments;  // Parent of each cluster.  Dim == #clusters.
     int32 num_leaves;  // number of leaf-level clusters.
     TreeCluster(summed_stats_per_set,
                 summed_stats_per_set.size(),  // max-#clust is all of the points.
                 NULL,  // don't need the clusters out.
                 &assignments,
                 &clust_assignments,
                 &num_leaves,
                 topts);
     //调用
     TreeClusterer tc(points, max_clust, cfg);
     BaseFloat ans = tc.Cluster(clusters_out, assignments_out, clust_assignments_out, num_leaves_out);
     //类TreeCluster
   class TreeClusterer {
     //树聚类
     BaseFloat Cluster(std::vector<Clusterable*> *clusters_out,
                       std::vector<int32> *assignments_out,
                       std::vector<int32> *clust_assignments_out,
                       int32 *num_leaves_out) {
       while (static_cast<int32>(leaf_nodes_.size()) < max_clust_ && !queue_.empty()) {
         std::pair<BaseFloat, Node*> pr = queue_.top();
         queue_.pop();
         ans_ += pr.first;
         DoSplit(pr.second);
       }
       CreateOutput(clusters_out, assignments_out, clust_assignments_out,
                    num_leaves_out);
       return ans_;
     }
     //对一个节点进行分割
     void DoSplit(Node *node) {}
     //将一个节点进行kmeans聚类, 此处kmeans聚类比较特殊，为保证结果较优，进行了多次不同初始化，并选择效果好的。
     void FindBestSplit(Node *node) {
       // takes a leaf node that has just been set up, and does ClusterKMeans with k = cfg_branch_factor.
       KALDI_ASSERT(node->is_leaf);
       if (node->leaf.points.size() == 0) {
         KALDI_WARN << "Warning: tree clustering: leaf with no data\n";
         node->leaf.best_split = 0; return;
       }
       if (node->leaf.points.size()<=1) { node->leaf.best_split = 0; return; }
       else {
         // use kmeans.
         BaseFloat impr = ClusterKMeans(node->leaf.points,
                                        cfg_.branch_factor,
                                        &node->leaf.clusters,
                                        &node->leaf.assignments,
                                        cfg_.kmeans_cfg);
         node->leaf.best_split = impr;
         if (impr > cfg_.thresh)
           queue_.push(std::make_pair(impr, node));
       }
     }
   }
   

3. compile-questions
   

   Questions qo;
   QuestionsForKey phone_opts(num_iters_refine);
   // the questions-options corresponding to keys 0, 1, .. N-1 which
   // represent the phonetic context positions (including the central phone).
   phone_opts.initial_questions = questions;
   //对每个位置建立问题集
   for (int32 n = 0; n < N; n++) {
     KALDI_LOG << "Setting questions for phonetic-context position "<< n;
     qo.SetQuestionsOf(n, phone_opts);
   }
   QuestionsForKey pdfclass_opts(num_iters_refine);
   std::vector<std::vector<int32> > pdfclass_questions(max_num_pdfclasses-1);
   //对kPdfClass=-1问题集[ [0], [0, 1] ]
   for (int32 i = 0; i < max_num_pdfclasses - 1; i++)
     for (int32 j = 0; j <= i; j++)
       pdfclass_questions[i].push_back(j);
   // E.g. if max_num_pdfclasses == 3,  pdfclass_questions is now [ [0], [0, 1] ].
   pdfclass_opts.initial_questions = pdfclass_questions;
   KALDI_LOG << "Setting questions for hmm-position [hmm-position ranges from 0 to "<< (max_num_pdfclasses-1) <<"]";
   qo.SetQuestionsOf(kPdfClass, pdfclass_opts);
   

4. build-tree
   

   EventMap *SplitDecisionTree(const EventMap &input_map,
                               const BuildTreeStatsType &stats,
                               Questions &q_opts,
                               BaseFloat thresh,
                               int32 max_leaves,  // max_leaves<=0 -> no maximum.
                               int32 *num_leaves,
                               BaseFloat *obj_impr_out,
                               BaseFloat *smallest_split_change_out) {
     {  // Do the splitting.
       int32 count = 0;
       std::priority_queue<std::pair<BaseFloat, size_t> > queue;  // use size_t because logically these
       // are just indexes into the array, not leaf-ids (after splitting they are no longer leaf id's).
       // Initialize queue.
       for (size_t i = 0; i < builders.size(); i++)
         queue.push(std::make_pair(builders[i]->BestSplit(), i));
       // Note-- queue's size never changes from now.  All the alternatives leaves to split are
       // inside the "DecisionTreeSplitter*" objects, in a tree structure.
       //此处为重点，优先队列的使用，及决策树终止的两个条件
       while (queue.top().first > thresh
             && (max_leaves<=0 || *num_leaves < max_leaves)) {
         smallest_split_change = std::min(smallest_split_change, queue.top().first);
         size_t i = queue.top().second;
         like_impr += queue.top().first;
         builders[i]->DoSplit(num_leaves);
         queue.pop();
         queue.push(std::make_pair(builders[i]->BestSplit(), i));
         count++;
       }
       KALDI_LOG << "DoDecisionTreeSplit: split "<< count << " times, #leaves now " << (*num_leaves);
     }
     ...
   }
   寻找最优问题集类
   class DecisionTreeSplitter {
     //返回最优的一个分割增益
     BaseFloat BestSplit() { return best_split_impr_; } // returns objf improvement (>=0) of best possible split.
     //构造函数中即从问题集中寻找最优问题
     DecisionTreeSplitter(EventAnswerType leaf, const BuildTreeStatsType &stats,
                         const Questions &q_opts): q_opts_(q_opts), yes_(NULL), no_(NULL), leaf_(leaf), stats_(stats) {
       // not, this must work when stats is empty too. [just gives zero improvement, non-splittable].
       FindBestSplit();
     }
      //在all_keys中找最优
     void FindBestSplit() {}
   };
   
   BaseFloat ComputeInitialSplit(const std::vector<Clusterable*> &summed_stats,
                                 const Questions &q_opts, EventKeyType key,
                                 std::vector<EventValueType> *yes_set) {
     ...
     const std::vector<std::vector<EventValueType> > &questions_of_this_key = key_opts.initial_questions;
   
     int32 best_idx = -1;
     BaseFloat best_objf_change = 0;
     //在问题集中寻找似然增益最大的问题
     for (size_t i = 0; i < questions_of_this_key.size(); i++) {
       const std::vector<EventValueType> &yes_set = questions_of_this_key[i];
       std::vector<int32> assignments(summed_stats.size(), 0);  // 0 is index of "no".
       std::vector<Clusterable*> clusters(2);  // no and yes clusters.
       for (std::vector<EventValueType>::const_iterator iter = yes_set.begin(); iter != yes_set.end(); iter++) {
         KALDI_ASSERT(*iter>=0);
         if (*iter < (EventValueType)assignments.size()) assignments[*iter] = 1;
       }
       kaldi::AddToClustersOptimized(summed_stats, assignments, *total, &clusters);
       BaseFloat this_objf = SumClusterableObjf(clusters);
   
       if (this_objf < unsplit_objf- 0.001*std::abs(unsplit_objf)) {  // got worse; should never happen.
         // of course small differences can be caused by roundoff.
         KALDI_WARN << "Objective function got worse when building tree: "<< this_objf << " < " << unsplit_objf;
         KALDI_ASSERT(!(this_objf < unsplit_objf - 0.01*(200 + std::abs(unsplit_objf))));  // do assert on more stringent check.
       }
   
       BaseFloat this_objf_change = this_objf - unsplit_objf;
       if (this_objf_change > best_objf_change) {
         best_objf_change = this_objf_change;
         best_idx = i;
       }
       DeletePointers(&clusters);
     }
     delete total;
     if (best_idx != -1)
       *yes_set = questions_of_this_key[best_idx];
     return best_objf_change;
   }
   

5.3.1 component

//Componet子类需实现PropagateFnc和BackpropagateFnc接口
class Sigmoid : public Component {
 public:
  void PropagateFnc(const CuMatrixBase<BaseFloat> &in, CuMatrixBase<BaseFloat> *out) {
    // y = 1/(1+e^-x)
    out->Sigmoid(in);
  }
  void BackpropagateFnc(const CuMatrixBase<BaseFloat> &in, const CuMatrixBase<BaseFloat> &out,
                        const CuMatrixBase<BaseFloat> &out_diff, CuMatrixBase<BaseFloat> *in_diff) {
    // ey = y(1-y)ex
    in_diff->DiffSigmoid(out, out_diff);
  }
};
//UpdatableComponent还需实现Update()接口
class UpdatableComponent : public Component {
public:
  //updatable
  bool IsUpdatable() const {
    return true;
  }
  /// Compute gradient and update parameters
  virtual void Update(const CuMatrixBase<BaseFloat> &input,
                      const CuMatrixBase<BaseFloat> &diff) = 0;
 protected:
  /// Option-class with training hyper-parameters
  NnetTrainOptions opts_;
};
//UpdatableComponent参数初始化
void InitData(std::istream &is)

5.3.2 nnet

private:
  std::vector<Component*> components_; 
  std::vector<CuMatrix<BaseFloat> > propagate_buf_; ///< buffers for forward pass
  std::vector<CuMatrix<BaseFloat> > backpropagate_buf_; ///< buffers for backward pass

void Nnet::Propagate(const CuMatrixBase<BaseFloat> &in, CuMatrix<BaseFloat> *out) {
  propagate_buf_[0].Resize(in.NumRows(), in.NumCols());
  propagate_buf_[0].CopyFromMat(in);
  for(int32 i=0; i<(int32)components_.size(); i++) {
    components_[i]->Propagate(propagate_buf_[i], &propagate_buf_[i+1]);
  }
  (*out) = propagate_buf_[components_.size()];
}
void Nnet::Backpropagate(const CuMatrixBase<BaseFloat> &out_diff, CuMatrix<BaseFloat> *in_diff) {
  // copy out_diff to last buffer
  backpropagate_buf_[NumComponents()] = out_diff;
  // backpropagate using buffers
  for (int32 i = NumComponents()-1; i >= 0; i--) {
    components_[i]->Backpropagate(propagate_buf_[i], propagate_buf_[i+1],
                            backpropagate_buf_[i+1], &backpropagate_buf_[i]);
    if (components_[i]->IsUpdatable()) {
      UpdatableComponent *uc = dynamic_cast<UpdatableComponent*>(components_[i]);
      uc->Update(propagate_buf_[i], backpropagate_buf_[i+1]);
    }
  }
  // eventually export the derivative
  if (NULL != in_diff) (*in_diff) = backpropagate_buf_[0];
}

5.3.3 nnet-train-frmshuff

--cross-validate:  Perform cross-validation (don't backpropagate)
--objective-function: xent or mes
–feature-transform, this can be a Nnet which does on-the-fly feature transformation
--minibatch-size

//minibatch在这里面
NnetDataRandomizerOptions rnd_opts;
rnd_opts.Register(&po);

5.4.1 keypoint

5.4.2 代码解析

1. 卷积层 nnet-convolution-component.h
   

   void PropagateFnc(const CuMatrixBase<BaseFloat> &in, CuMatrixBase<BaseFloat> *out) {
     // useful dims
     int32 num_splice = input_dim_ / patch_stride_; //帧数
     int32 num_patches = 1 + (patch_stride_ - patch_dim_) / patch_step_; //patch num
     int32 num_filters = filters_.NumRows(); //filter数量，一行为一个filter
     int32 num_frames = in.NumRows(); //batch中的数据数
     int32 filter_dim = filters_.NumCols(); //filter的核大小
   
     // we will need the buffers 
     if (vectorized_feature_patches_.size() == 0) {
       vectorized_feature_patches_.resize(num_patches);
       feature_patch_diffs_.resize(num_patches);
     }
   
     /* Prepare feature patches, the layout is:
      * |----------|----------|----------|---------| (in = spliced frames)
      *   xxx        xxx        xxx        xxx       (x = selected elements)
      *
      *   xxx : patch dim
      *    xxx 
      *   ^---: patch step
      * |----------| : patch stride
      *
      *   xxx-xxx-xxx-xxx : filter dim
      *  
      */
     for (int32 p=0; p<num_patches; p++) {
       vectorized_feature_patches_[p].Resize(num_frames, filter_dim, kSetZero);
       // build-up a column selection mask:
       std::vector<int32> column_mask;
       /*
        *|-XXX---------|
        *|-XXX---------|
        *|-XXX---------|
        *|-XXX---------|
        column_mask的位置, p * patch_step + s * patch_stride_ + d
        */
       for (int32 s=0; s<num_splice; s++) {
         for (int32 d=0; d<patch_dim_; d++) {
           column_mask.push_back(p * patch_step_ + s * patch_stride_ + d);
         }
       }
       KALDI_ASSERT(column_mask.size() == filter_dim);
       // select the current patch columns, 一行为一个输入数据。
       vectorized_feature_patches_[p].CopyCols(in, column_mask);
     }
   
     // compute filter activations
     for (int32 p=0; p<num_patches; p++) {
       //patch p 在输出中的位置tgt
       CuSubMatrix<BaseFloat> tgt(out->ColRange(p * num_filters, num_filters));
       tgt.AddVecToRows(1.0, bias_, 0.0); // add bias
       // apply all filters
       tgt.AddMatMat(1.0, vectorized_feature_patches_[p], kNoTrans, filters_, kTrans, 1.0);
     }
   }
   //后向程序仅是对公式的翻译
   void BackpropagateFnc(const CuMatrixBase<BaseFloat> &in, const CuMatrixBase<BaseFloat> &out,
                         const CuMatrixBase<BaseFloat> &out_diff, CuMatrixBase<BaseFloat> *in_diff) {
   }
   void Update(const CuMatrixBase<BaseFloat> &input, const CuMatrixBase<BaseFloat> &diff) {
   }
   

2. pooling层 nnet-max-pooling-component.h
   

   void PropagateFnc(const CuMatrixBase<BaseFloat> &in, CuMatrixBase<BaseFloat> *out) {                                                                
     // useful dims                                                                                                                                    
     int32 num_patches = input_dim_ / pool_stride_;                                                                                                    
     int32 num_pools = 1 + (num_patches - pool_size_) / pool_step_;                                                                                    
     //pool_step_ pool步移， pool_size_，pool步长                                                                                                                                                  
     // do the max-pooling (pools indexed by q),为每个输出q选择max                                                                                                        
     for (int32 q = 0; q < num_pools; q++) {                                                                                                           
       // get output buffer of the pool                                                                                                                
       CuSubMatrix<BaseFloat> pool(out->ColRange(q*pool_stride_, pool_stride_));                                                                       
       pool.Set(-1e20); // reset (large negative value)                                                                                                
       for (int32 r = 0; r < pool_size_; r++) { // max                                                                                                 
         int32 p = r + q * pool_step_; // p = input patch                                                                                              
         pool.Max(in.ColRange(p*pool_stride_, pool_stride_)); //*this = max(*this, A)                                                                                      
       }                                                                                                                                               
     }                                                                                                                                                 
   } 
   //max-pool，若其为max，后向误差乘以1，否则0，这里有个scale的操作
   //因为中间部分可能多次计算，相对的边缘部分在shift中计算次数较少
   void BackpropagateFnc(const CuMatrixBase<BaseFloat> &in, const CuMatrixBase<BaseFloat> &out,
                         const CuMatrixBase<BaseFloat> &out_diff, CuMatrixBase<BaseFloat> *in_diff) {
     // useful dims
     int32 num_patches = input_dim_ / pool_stride_;
     int32 num_pools = 1 + (num_patches - pool_size_) / pool_step_;
     //scale 数组
     std::vector<int32> patch_summands(num_patches, 0);
     in_diff->SetZero(); // reset
     //遍历所有pool输出
     for(int32 q=0; q<num_pools; q++) { // sum
       for(int32 r=0; r<pool_size_; r++) {
         //对应q时的输入
         int32 p = r + q * pool_step_; // patch number
         CuSubMatrix<BaseFloat> in_p(in.ColRange(p*pool_stride_, pool_stride_));
         CuSubMatrix<BaseFloat> out_q(out.ColRange(q*pool_stride_, pool_stride_));
         CuSubMatrix<BaseFloat> tgt(in_diff->ColRange(p*pool_stride_, pool_stride_));
         CuMatrix<BaseFloat> src(out_diff.ColRange(q*pool_stride_, pool_stride_));
         //find max mask
         CuMatrix<BaseFloat> mask;
         in_p.EqualElementMask(out_q, &mask);
         src.MulElements(mask);
         tgt.AddMat(1.0, src);
         patch_summands[p] += 1;
       }
     }
     //scale操作
     for(int32 p=0; p<num_patches; p++) {
       CuSubMatrix<BaseFloat> tgt(in_diff->ColRange(p*pool_stride_, pool_stride_));
       KALDI_ASSERT(patch_summands[p] > 0); // patch at least in one pool
       tgt.Scale(1.0/patch_summands[p]);
     }
   }
   

5.5.1 ali-to-post: make_pair<alignment, 1.0>, Convert alignments to viterbi style posteriors

void AlignmentToPosterior(const std::vector<int32> &ali,
                          Posterior *post) {
  post->clear();
  post->resize(ali.size());
  for (size_t i = 0; i < ali.size(); i++) {
    (*post)[i].resize(1);
    (*post)[i][0].first = ali[i];
    (*post)[i][0].second = 1.0;
  }
}

5.5.2 kaldi log(base/kaldi-error.h)

class KaldiLogMessage {
 public:
  inline std::ostream &stream() { return ss; }
  KaldiLogMessage(const char *func, const char *file, int32 line);
  ~KaldiLogMessage() { fprintf(stderr, "%s\n", ss.str().c_str()); }
 private:
  std::ostringstream ss;
};

#define KALDI_LOG kaldi::KaldiLogMessage(__func__, __FILE__, __LINE__).stream()

KaldiLogMessage::KaldiLogMessage(const char *func, const char *file,
                                 int32 line) {
  this->stream() << "LOG (" << GetProgramName() << func << "():"
                 << GetShortFileName(file) << ':' << line << ") ";
}

5.5.3 kaldi中的并行run.pl

1. 主要特点
   
   1. 错误日志
   2. 计算时间
   3. 在log文件首行打印所执行命令的实际参数信息
   4. 因此在不并行的时候也能看到使用$cmd
2. 示例
   

   $cmd JOB=1:$nj $dir/log/acc_tree.JOB.log \
       acc-tree-stats  --ci-phones=$ciphonelist $alidir/final.mdl "$feats" \
        "ark:gunzip -c $alidir/ali.JOB.gz|" $dir/JOB.treeacc || exit 1;
   #等价于如下shell
   for ((i=1; i<=$JOB; i++));
   do
   {
      #my operate
   }& #并行
   done
   wait #等待所有子进程结束
   

3. run.pl源码
   

   #JOB
   if ($ARGV[0] =~ m/^([\w_][\w\d_]*)+=(\d+):(\d+)$/) { # e.g. JOB=1:10
       $jobname = $1;
       $jobstart = $2;
       $jobend = $3;
   }
   #创建子进程
   for ($jobid = $jobstart; $jobid <= $jobend; $jobid++) {
     $childpid = fork();
   }
   #等待子进程结束
   for ($jobid = $jobstart; $jobid <= $jobend; $jobid++) {
     $r = wait();
     if ($r == -1) { die "Error waiting for child process"; } # should never happen.
     if ($? != 0) { $numfail++; $ret = 1; } # The child process failed.
   }
   

8.5.1 何为确定化

8.5.2 确定化算法

8.10.1 StdArc

struct StdArc {
 typedef int Label;
 typedef TropicalWeight Weight;  // see "FST Weights" below 
 typedef int StateId; 

 Label ilabel;
 Label olabel;
 Weight weight;
 StateId nextstate;
};
for (ArcIterator<StdFst> aiter(fst, i); !aiter.Done(); aiter.Next())
  const StdArc &arc = aiter.Value();
Matcher<StdFst> matcher(fst, MATCH_INPUT);
matcher.SetState(i);
if (matcher.Find(l)) 
  for (; !matcher.Done(); matcher.Next())
     const StdArc &arc = matcher.Value();

8.10.2 fst

//抽象类
Fst<Arc>
ExpandedFst<Arc>: +NumStates();
MutableFst<Arc>: 可变的fst，如AddStates(), SetStart()

//实现
VectorFst<Arc>: mutable fst
ConstFst<Arc>:  immutable fst
ComposeFst<Arc>

//StdArc
ilabel, olabel, weight(Weight), nextstate

//Weight
TropicalWeight, LogWeight, ProductWeight

//Fst
Start(), Final(), Read(), etc ...

//Mutable Fst
SetStart(), SetFinal(), AddState(), AddArc()

//StateIterator
Done(), Value(), Next(), Reset()

//ArcIterator
Done(), Value(), Next(), Reset()

//FstImple: public Fst
type_, isymbols_, osymbols_, ref_count_

//SymbolTable Impl: 包装SymbolTable
map<int64, const char*> key_map_;
vector<const char *> symbols_;

//VectorState
final, Vector<A> arcs, niepsilon, noepsilon

//VectorFstBaseImpl: 这个类是VectorFst的一系列实现
state_;
vector<State *>states;
StateId AddState() { states.push_back(new State())
etc ...

8.11.1 幺半群

8.11.2 半环

8.11.3 Moore & Mealy