cdec中的cube pruning

cdec的cube pruning代码对应于apple_models.cc的CubePruningRescorer类.


在传统的cky解码过程中, 我们会为每一个chart定义一个heap, 如heap[i, j]用来存放所以souce side span为[i, j]的hypothese. 该heap的大小通常限置为某个常数(如200). 并且要求每个hypothesis的概率不能小于heap[i,j][0]的某个倍数(如0.05).
在cube pruning的时候, 通过设置pop_limit来限制最多生成多少个hypotheses. 
heap中各项的排列通常是按照score + heuristic_lm_score (即未计算在score中的前面几个单词的lm值)

在cdec的void KBestFast(const int vert_index, const bool is_goal) 方法中, 并没有为每个span[i, j]设置一个heap. 在cube pruning的时候, 设置pop_limit来限制最多生成多少个hypotheses. 虽然没有为每个span[i, j]设置一个heap,  cdec用candidate heap(没有大小限制)来保存:

      D_v.resize(state2node.size());
      int c = 0;
      for (State2Node::iterator i = state2node.begin(); i != state2node.end(); ++i){
          D_v[c++] = i->second;
          // cerr << "MERGED: " << *i->second << endl;
      }
      //cerr <<"Node id: "<< vert_index<< endl;
      //#ifdef MEASURE_CA
      // cerr << "countInProcess (pop/tot): node id: " << vert_index << " (" << count_in_process_pop << "/" << count_in_process_tot << ")"<      // cerr << "countAtEnd (pop/tot): node id: " << vert_index << " (" << count_at_end_pop << "/" << count_at_end_tot << ")"<      //#endif
      sort(D_v.begin(), D_v.end(), EstProbSorter());

cdec默认设置pop_limit为200, 为了增加搜索空间, 似乎只能放大pop_limit的值.

cdec是这样做cube pruning,

假设source side span为[i, j], 其source端看以表达为  a X1 b X2 c, ..., a X1 c,..., 各个source端对应的目标端翻译, 加起来共有m种, t1, t2, ..., tm; X1可能的hypotheses有n种, X11, ..., X1n; X2可能的hypotheses有k种, X21, ..., X2k.

1:  生成一个candidate list = {(0, 0, 0), (1, 0, 0), ..., (m, 0, 0)}. 第1/2/3维分别为上面三个变量的下标. 
2:  pop = 0;
3:  while (pop < pop_limit && candidate_list not empty) do
4:     对candidate list排序;
5:     从candidate_list中取出最大项(i, j, k);
6      生成新的hypothesis;
7      对(i, j, k)扩展, 往candidate_list中添加(i, j+1, k)和(i, j, k+1);
8      pop ++; 


X11, ..., X1n和X21, ..., X2k是按大小排序的. 不确定t1, t2, ..., tm是否也是按大小排序, 但这应该没有关系.