Inside-Outsideアルゴリズムを試す

自然言語処理 プログラミング

はじめに

確率文脈自由文法での生成規則の適用確率の推定アルゴリズムで紹介されている「Inside-Outsideアルゴリズム」について、Webで検索してみても、最尤導出の構文木や内側確率の計算例などはあっても、外側確率や生成確率の推定などまで計算例を書いてくれているのはなさそうだったので、手計算確認用にプログラムを書いた。

Inside-Outsideアルゴリズムとは

  • 内側・外側アルゴリズム
  • 確率文脈自由文法の生成規則(チョムスキー標準形)の確率値をコーパスを求める際に、内側確率βと外側確率αを導入することで効率よく求められる
    • 隠れマルコフモデルにおける前向き・後ろ向きアルゴリズムに似た感じ
    • 内側確率 : 非終端記号Aから終端記号列w_i^jが生成される確率
    • 外側確率 : 導出中に出現するAについて、Aが支配しているw_i^j以外の両側の終端記号列w_1^{i-1}とw_{j+1}^Nが現れる確率
  • 内側確率と外側確率を使って各生成規則の適用回数を推定でき、これを用いて生成規則の確率値を求める、ということを繰り返す

詳しくは「北, 言語と計算4 確率的言語モデル, 東京大学出版会」の第5章を参照。

コード

内側確率と外側確率、適用回数の推定が確認できればよいと思って書いたため、だいたい愚直。
最尤導出と内側確率が上の書籍と同じ値であるのと、繰り返し最適化で対数尤度が収束しているようなので、たぶん大丈夫。。。
(雑な確認しかしていないので、何かありましたら教えていただければと思います)

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cmath>

//乱数
// 注意: longではなくint(32bit)にすべき
unsigned long xor128(){
  static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
  unsigned long t;
  t=(x^(x<<11));
  x=y; y=z; z=w;
  return w=(w^(w>>19))^(t^(t>>8));
}
// 注意: int_maxぐらいで割るべき
double frand(){
  return xor128()%1000000/static_cast<double>(1000000); 
}

double logsumexp(const std::vector<double>& lps){
  if(lps.size() == 0) return -1e300;
  double mx = lps[0];
  for(size_t i=0; i<lps.size(); i++){
    if(lps[i] > mx) mx = lps[i];
  }
  double sum = 0;
  for(size_t i=0; i<lps.size(); i++){
    sum += exp(lps[i] - mx);
  }
  return mx + log(sum);
}

//計算用のdp[i][j][A]形式の3次元dpテーブル
template<class T>
class DPTable {
  int N;
  std::vector< std::vector< std::map<std::string,T> > > dp;
public:
  DPTable(int N):dp(N, std::vector< std::map<std::string,T> >(N)){}

  bool exists(size_t i, size_t j, const std::string& S){ return dp[i][j].count(S) > 0; }

  T get(size_t i, size_t j, const std::string& S){ return dp[i][j][S]; }

  void set(size_t i, size_t j, const std::string& S, const T& val){ dp[i][j][S] = val; }

  std::vector<std::string> get_str_list(size_t i, size_t j){
    std::vector<std::string> ret;
    for(typename std::map<std::string,T>::iterator itr = dp[i][j].begin();
        itr != dp[i][j].end();
        ++itr){
      ret.push_back(itr->first);
    }
    return ret;
  }
};

//文法< A -> B C, p >
struct Grammar {
  std::string lhs; // A
  std::pair<std::string,std::string> rhs; // B C (lexicalならCは空)
  double lp; //確率値の対数
  Grammar(const std::string lhs,
          const std::pair<std::string,std::string> rhs,
          double lp):
    lhs(lhs),rhs(rhs),lp(lp){}
};
bool operator==(const Grammar& a, const Grammar& b){
  return a.lhs == b.lhs && a.rhs == b.rhs;
}
bool operator<(const Grammar& a, const Grammar& b){
  if(a.lhs == b.lhs) return a.rhs < b.rhs;
  return a.lhs < b.lhs;
}

//文法の管理
class Grammars {
  std::string start;
  std::map< std::pair<std::string,std::string>, std::vector<Grammar> > grammars;
public:
  Grammars(std::string start = "S"):start(start){}

  void set_start(const std::string& st){
    start = st;
  }

  std::string get_start(){
    return start;
  }

  void add(const Grammar& grm){
    grammars[grm.rhs].push_back(grm);
  }

  std::vector<Grammar> search(const std::pair<std::string,std::string>& rhs){
    return grammars[rhs];
  }

  //確率値を適当な値で埋める
  void fill_random(){
    std::map< std::string,std::vector<double> > sum;
    for(std::map< std::pair<std::string,std::string>, std::vector<Grammar> >::iterator itr = grammars.begin();
        itr != grammars.end();
        ++itr){
      for(size_t i=0; i<(itr->second).size(); i++){
        (itr->second)[i].lp = log(frand() * 0.09 + 0.01);//0.01〜0.1で適当に与える(次の正規化でΣp(A->*)=1となるように調整する)
        sum[(itr->second)[i].lhs].push_back((itr->second)[i].lp);
      }
    }
    //正規化
    std::map<std::string,double> norm;
    for(std::map< std::string,std::vector<double> >::iterator itr = sum.begin();
        itr != sum.end();
        ++itr){
      norm[itr->first] = logsumexp(itr->second);
    }
    for(std::map< std::pair<std::string,std::string>, std::vector<Grammar> >::iterator itr = grammars.begin();
        itr != grammars.end();
        ++itr){
      for(size_t i=0; i<(itr->second).size(); i++){
        (itr->second)[i].lp -= norm[(itr->second)[i].lhs];
      }
    }
  }

  std::vector<Grammar> get_all_grammar(){
    std::vector<Grammar> ret;
    for(std::map< std::pair<std::string,std::string>, std::vector<Grammar> >::iterator itr = grammars.begin();
        itr != grammars.end();
        ++itr){
      for(size_t i=0; i<(itr->second).size(); i++){
        ret.push_back((itr->second)[i]);
      }
    }
    return ret;
  }  

  void dump(){
    for(std::map< std::pair<std::string,std::string>, std::vector<Grammar> >::iterator itr = grammars.begin();
        itr != grammars.end();
        ++itr){
      for(size_t i=0; i<(itr->second).size(); i++){
        Grammar grm = (itr->second)[i];
        std::cout << grm.lhs << " -> " << grm.rhs.first << " " << grm.rhs.second << "\t" << exp(grm.lp) << std::endl;
      }
    }
  }
};



class PCFG {
public:
  //最尤導出計算用
  struct Info {
    std::string lhs;
    std::pair<std::string,std::string> rhs;
    std::pair< std::pair<int,int>, std::pair<int,int> > idx;
    double delta;
    std::pair<int,int> ans; //結果パース用
    Info():delta(-INF){}
  };
  //Inside-Outside algorithm計算用
  struct BetaAlpha {
    double beta;
    double alpha;
    BetaAlpha():beta(-INF),alpha(-INF){}
    BetaAlpha(double beta, double alpha):beta(beta),alpha(alpha){}
  };
private:
  static const double INF;

  //文法の管理
  Grammars grammars;

  /* 最尤導出計算用 */
  //dpテーブルから最尤な導出を配列形式にして返す
  std::pair< double,std::vector<Info> > get_best_tree(size_t N, DPTable<Info>& dp){
    std::vector<Info> ret;

    if(N==0 || !dp.exists(0,N-1,grammars.get_start())) return std::make_pair(-1,ret);

    //開始記号から構文木をたどる
    size_t i = 0;
    Info tmp = dp.get(0,N-1,grammars.get_start());
    double p = tmp.delta;
    ret.push_back(tmp);
    ret[i].ans = std::make_pair(ret.size(), ret.size()+1);
    ret.push_back(dp.get(tmp.idx.first.first,tmp.idx.first.second,tmp.rhs.first));
    ret.push_back(dp.get(tmp.idx.second.first,tmp.idx.second.second,tmp.rhs.second));
    i++;
    while(i < ret.size()){
      tmp = ret[i];
      if(tmp.rhs.second != ""){ //A -> B C
        ret[i].ans = std::make_pair(ret.size(), ret.size()+1);
        ret.push_back(dp.get(tmp.idx.first.first,tmp.idx.first.second,tmp.rhs.first)); //B
        ret.push_back(dp.get(tmp.idx.second.first,tmp.idx.second.second,tmp.rhs.second));//C
      } else { //A -> a
        ret[i].ans = std::make_pair(-1, -1); //a
      }
      i++;
    }
    return std::make_pair(p, ret);
  }

  /* Inside-Outsideアルゴリズム用 */
  //DPテーブルを作成
  void make_dp_table(DPTable<BetaAlpha>& dp, const std::vector<std::string>& text){
    std::vector<Grammar> grms = grammars.get_all_grammar();
    size_t N = text.size();
    //内側確率betaの計算
    {//対角要素を更新
      for(size_t i=0; i<N; i++){
        std::vector<Grammar> v = grammars.search(std::make_pair(text[i],""));
        for(size_t j=0; j<v.size(); j++){
          dp.set(i, i, v[j].lhs, BetaAlpha(v[j].lp, -INF));
        }
      }
    }
    {//残りの部分を更新
      for(size_t n=1; n<N; n++){
        for(size_t i=0; i<N-n; i++){
          std::map< std::string, std::vector<double> > memo;
          for(size_t k=0; k<grms.size(); k++){
            std::vector<double> v;
            for(size_t j=1; j<=n; j++){
              bool ok = true; //A->B CでBとCが両方0以上の値が存在しているものだけ計算
              double lp = 0;
              if(dp.exists(i,i+j-1,grms[k].rhs.first)){
                lp += dp.get(i,i+j-1,grms[k].rhs.first).beta;
              }else{
                ok = false;
              }
              if(dp.exists(i+j,i+n,grms[k].rhs.second)){
                lp += dp.get(i+j,i+n,grms[k].rhs.second).beta;
              }else{
                ok = false;
              }
              if(ok) v.push_back(lp);
            }
            if(v.size() > 0) memo[grms[k].lhs].push_back(grms[k].lp + logsumexp(v));
          }
          for(std::map< std::string, std::vector<double> >::iterator itr = memo.begin();
              itr != memo.end();
              ++itr){
            if((itr->second).size() > 0) dp.set(i,i+n,itr->first,BetaAlpha(logsumexp(itr->second), -INF));
          }
        }
      }
    }

    if(!dp.exists(0,N-1,grammars.get_start())) return; //構築に失敗したら終了
    
    //外側確率alphaの計算
    {//一番右上の外側確率を設定
      BetaAlpha ba = dp.get(0,N-1,grammars.get_start());
      dp.set(0,N-1,grammars.get_start(),BetaAlpha(ba.beta,0));
    }
    {//A -> B Cの形の生成規則に対し、Aの外側確率からBとCの外側確率を更新
      for(size_t n=N-1; n>=1; n--){
        for(size_t i=0; i<N-n; i++){
          for(size_t j=0; j<grms.size(); j++){
            if(!dp.exists(i,i+n,grms[j].lhs)) continue;
          
            std::map< std::pair< std::pair<size_t,size_t>,std::string >, std::vector<double> > memo;
            for(size_t k=1; k<=n; k++){
              //alpha[i+k][i+n][C] += P(A->BC) * alpha[i][i+n][A] * beta[i][i-1+k][B]
              if(dp.exists(i+k,i+n,grms[j].rhs.second) && dp.exists(i,i-1+k,grms[j].rhs.first)){
                double lp = grms[j].lp + dp.get(i,i+n,grms[j].lhs).alpha + dp.get(i,i-1+k,grms[j].rhs.first).beta;
                memo[std::make_pair(std::make_pair(i+k,i+n),grms[j].rhs.second)].push_back(lp);
              }
              //alpha[i][i+n-k][B] += P(A->BC) * alpha[i][i+n][A] * beta[i+n+1-k][i+n][C]
              if(dp.exists(i,i+n-k,grms[j].rhs.first) && dp.exists(i+n+1-k,i+n,grms[j].rhs.second)){
                double lp = grms[j].lp + dp.get(i,i+n,grms[j].lhs).alpha + dp.get(i+n+1-k,i+n,grms[j].rhs.second).beta;
                memo[std::make_pair(std::make_pair(i,i+n-k),grms[j].rhs.first)].push_back(lp);
              }
            }
            for(std::map< std::pair< std::pair<size_t,size_t>,std::string >, std::vector<double> >::iterator itr = memo.begin();
                itr != memo.end();
                ++itr){
              size_t l = (itr->first).first.first;
              size_t r = (itr->first).first.second;
              std::string A = (itr->first).second;
              if(!dp.exists(l,r,A)) continue;
              std::vector<double> v = itr->second;
              BetaAlpha ba = dp.get(l,r,A);
              v.push_back(ba.alpha);
              ba.alpha = logsumexp(v);
              dp.set(l,r,A,ba);
            }
          }
        }
      }
    }
  }
  
  //テキストの確率値を取得
  double get_sentence_prob(DPTable<BetaAlpha>& dp, const std::vector<std::string>& text){
    size_t N = text.size();
    return dp.get(0,N-1,grammars.get_start()).beta;
  }
  
  //コーパスの尤度を計算
  double calc_log_likelihood(const std::vector< std::vector<std::string> >& corpus){
    double ret = 0.0;
    for(size_t i=0; i<corpus.size(); i++){
      DPTable<BetaAlpha> dp(corpus[i].size());
      make_dp_table(dp, corpus[i]);
      if(!dp.exists(0,corpus[i].size()-1,grammars.get_start())){ //構文木が作成できていない場合はスキップ
        //std::cerr << "text[" << i << "] skipped" << std::endl;
        continue;
      }
      double lp = get_sentence_prob(dp, corpus[i]);
      //std::cerr << "text[" << i << "] = " << lp << std::endl;
      ret += lp;
    }
    return ret;
  }
    
  //ルールの適用確率の推定
  void update_grammar_prob(const std::vector< std::vector<std::string> >& corpus){
    std::vector<Grammar> grms = grammars.get_all_grammar();
    std::map< Grammar,std::vector<double> > cnt;
    //適用された回数をカウント
    for(size_t t=0; t<corpus.size(); t++){
      size_t N = corpus[t].size();
      DPTable<BetaAlpha> dp(N);
      make_dp_table(dp, corpus[t]);
      if(!dp.exists(0,N-1,grammars.get_start())) continue; //構文木が作成できていない場合はスキップ
      double lp_sentence = get_sentence_prob(dp, corpus[t]);
      for(size_t g=0; g<grms.size(); g++){
        std::vector<double> v;
        if(grms[g].rhs.second == ""){ //A -> a
          for(size_t i=0; i<N; i++){
            if(dp.exists(i,i,grms[g].lhs)) v.push_back(grms[g].lp - lp_sentence + dp.get(i,i,grms[g].lhs).alpha);
          }
        }else{ //A -> B C
          for(size_t n=1; n<=N-1; n++){
            for(size_t i=0; i<N-n; i++){
              for(size_t j=1; j<=n; j++){
                if(!dp.exists(i,i+n,grms[g].lhs)) continue;
                if(!dp.exists(i,i+j-1,grms[g].rhs.first)) continue;
                if(!dp.exists(i+j,i+n,grms[g].rhs.second)) continue;
                
                double lp = grms[g].lp - lp_sentence + 
                  dp.get(i,i+n,grms[g].lhs).alpha + 
                  dp.get(i,i+j-1,grms[g].rhs.first).beta +
                  dp.get(i+j,i+n,grms[g].rhs.second).beta;
                v.push_back(lp);
              }
            }
          }
        }
        cnt[grms[g]].push_back(logsumexp(v));
      }
    }
    //適用回数から確率を計算し、grammarsを更新
    std::map< std::string,std::vector<double> > sum;
    for(std::map< Grammar,std::vector<double> >::iterator itr = cnt.begin();
        itr != cnt.end();
        ++itr){
      sum[(itr->first).lhs].push_back(logsumexp(itr->second));
    }
    Grammars new_grms;
    new_grms.set_start(grammars.get_start());
    for(size_t i=0; i<grms.size(); i++){
      double lp = logsumexp(cnt[grms[i]]) - logsumexp(sum[grms[i].lhs]);
      new_grms.add(Grammar(grms[i].lhs, grms[i].rhs, lp));
    }
    grammars = new_grms;
  }

public:
  //文法の開始記号を登録
  void set_start(const std::string& st){
    grammars.set_start(st);
  }

  //文法を登録
  void add_grammar(const std::string& lhs, const std::pair<std::string,std::string>& rhs, double lp){
    grammars.add(Grammar(lhs,rhs,lp));
  }

  //文に対して最尤な導出を計算
  std::pair< double, std::vector<Info> > calc_best_tree(const std::vector<std::string>& text){
    size_t N = text.size();
    DPTable<Info> dp(N);
    //対角要素を計算
    for(size_t i=0; i<N; i++){
      std::vector<Grammar> v = grammars.search(std::make_pair(text[i],""));
      for(size_t j=0; j<v.size(); j++){
        Info info;
        info.lhs = v[j].lhs;
        info.rhs = v[j].rhs;
        info.idx.first = std::make_pair(i,i);
        info.idx.second = std::make_pair(-1,-1);
        info.delta = v[j].lp;
        
        if(dp.get(i, i, v[j].lhs).delta < v[j].lp){
          dp.set(i, i, v[j].lhs, info);
        }
      }
    }
    //三角行列の2番目以降の対角線上の要素を計算
    for(size_t n=1; n<N; n++){
      for(size_t i=0; i<N-n; i++){
        for(size_t j=1; j<=n; j++){
          std::vector<std::string> v1 = dp.get_str_list(i, i+j-1);
          std::vector<std::string> v2 = dp.get_str_list(i+j, i+n);
          for(size_t v1i=0; v1i<v1.size(); v1i++){
            for(size_t v2i=0; v2i<v2.size(); v2i++){
              std::vector<Grammar> v = grammars.search(std::make_pair(v1[v1i],v2[v2i]));
              for(size_t k=0; k<v.size(); k++){
                if(dp.get(i, i+n, v[k].lhs).delta <
                   v[k].lp + dp.get(i,i+j-1,v1[v1i]).delta + dp.get(i+j,i+n,v2[v2i]).delta){
                  Info info;
                  info.lhs = v[k].lhs;
                  info.rhs = v[k].rhs;
                  info.idx.first = std::make_pair(i,i+j-1);
                  info.idx.second = std::make_pair(i+j,i+n);
                  info.delta = v[k].lp + dp.get(i,i+j-1,v1[v1i]).delta + dp.get(i+j,i+n,v2[v2i]).delta;
                  
                  dp.set(i,i+n,v[k].lhs,info);
                }
              }
            }
          }
        }
      }
    }
    return get_best_tree(N, dp);
  }

  //Inside-Outside algorithmで文法の確率値を推定
  void estimate(const std::vector< std::vector<std::string> >& corpus, size_t ITER = 100000, double EPS = 1e-6){
    std::cerr << "Start Training..." << std::endl;
    //文法の確率を適当な値で埋める
    grammars.fill_random();
    
    double LL_prev = -INF, LL_now;
    for(size_t iter=1; iter<=ITER; iter++){
      //確率値の更新
      update_grammar_prob(corpus);
      //尤度の計算
      LL_now = calc_log_likelihood(corpus);

      std::cerr << "ITER = " << iter << "\tLL : " << LL_now << std::endl;
      if(fabs(LL_now - LL_prev) < EPS) break;
      LL_prev = LL_now;
    }

    //推定後の文法情報をダンプ
    std::cout << "[New Grammar]" << std::endl;
    grammars.dump();
    std::cout << std::endl;
  }

  //文を解析し、結果を出力、文の確率を返す
  double dump(const std::vector<std::string>& text){
    size_t N = text.size();
    std::pair< double, std::vector<Info> > best_tree = calc_best_tree(text);
    std::vector<Info> ret = best_tree.second;

    DPTable<BetaAlpha> dp(N);
    make_dp_table(dp, text);
    double lp_sentence = 0.0;
    if(dp.exists(0,N-1,grammars.get_start())){
      lp_sentence = get_sentence_prob(dp, text);
    }
    
    std::cout << "Text : ";
    for(size_t i=0; i<text.size(); i++){
      if(i!=0) std::cout << " ";
      std::cout << text[i];
    }
    std::cout << std::endl;
    std::cout << "P(W,T_best) : " << exp(best_tree.first) << std::endl;
    std::cout << "P(W) : " << exp(lp_sentence) << std::endl;
    
    for(size_t i=0; i<best_tree.second.size(); i++){
      std::cout << i << "\t";
      std::cout << ret[i].ans.first << "\t" << ret[i].ans.second << "\t";
      std::cout << ret[i].lhs << " -> " << ret[i].rhs.first << " " << ret[i].rhs.second << std::endl;
    }
    std::cout << std::endl;
    return best_tree.first;
  }
  
};
const double PCFG::INF = 1e100;

int main(){
  PCFG pcfg;

  //文法の登録(書籍のp.128図5.1)
  pcfg.set_start("S"); //開始記号
  pcfg.add_grammar("S", std::make_pair("N","V"), log(0.4));
  pcfg.add_grammar("S", std::make_pair("S","PP"), log(0.5));
  pcfg.add_grammar("S", std::make_pair("V","N"), log(0.1));
  pcfg.add_grammar("V", std::make_pair("V","N"), log(0.4));
  pcfg.add_grammar("PP", std::make_pair("P","N"), log(1.0));
  pcfg.add_grammar("N", std::make_pair("N","PP"), log(0.1));
  pcfg.add_grammar("N", std::make_pair("I",""), log(0.4));
  pcfg.add_grammar("N", std::make_pair("Maria",""), log(0.3));
  pcfg.add_grammar("N", std::make_pair("pizza",""), log(0.2));
  pcfg.add_grammar("V", std::make_pair("eat",""), log(0.6));
  pcfg.add_grammar("P", std::make_pair("with",""), log(1.0));

  //コーパス
  std::vector< std::vector<std::string> > corpus;
  { //I eat pizza with Maria
    std::vector<std::string> text;
    text.push_back("I");
    text.push_back("eat");
    text.push_back("pizza");
    text.push_back("with");
    text.push_back("Maria");
    corpus.push_back(text);
  }
  { //Maria eats pizza
    std::vector<std::string> text;
    text.push_back("Maria");
    text.push_back("eat");
    text.push_back("pizza");
    corpus.push_back(text);
  }

  //コーパス全体の対数尤度の合計
  double ll_sum;
  
  //指定した確率値での解析結果
  ll_sum = 0;
  for(size_t i=0; i<corpus.size(); i++){
    ll_sum += pcfg.dump(corpus[i]);
  }
  std::cout << "LLsum = " << ll_sum << std::endl;
  std::cout << std::endl;
  
  //適用確率を推定
  pcfg.estimate(corpus);

  //推定後の確率値での解析結果
  ll_sum = 0;
  for(size_t i=0; i<corpus.size(); i++){
    ll_sum += pcfg.dump(corpus[i]);
  }
  std::cout << "LLsum = " << ll_sum << std::endl;
  std::cout << std::endl;
  
  return 0;
}

結果

実行結果。
導出木の配列の部分は、以下の形式。

木のノード番号(0は根ノード)　　　左の子ノードの番号　　　右の子ノードの番号　　適用規則
Text : I eat pizza with Maria
P(W,T_best) : 0.001152     //書籍のp.128 P(W,T_2)と同じ
P(W) : 0.0013824           //書籍のp.129 P(W)と同じ
0       1       2       S -> S PP
1       3       4       S -> N V
2       5       6       PP -> P N
3       -1      -1      N -> I
4       7       8       V -> V N
5       -1      -1      P -> with
6       -1      -1      N -> Maria
7       -1      -1      V -> eat
8       -1      -1      N -> pizza

Text : Maria eat pizza
P(W,T_best) : 0.00576
P(W) : 0.00576
0       1       2       S -> N V
1       -1      -1      N -> Maria
2       3       4       V -> V N
3       -1      -1      V -> eat
4       -1      -1      N -> pizza

LLsum = -11.9231

Start Training...
ITER = 1        LL : -11.9597
ITER = 2        LL : -11.7674
ITER = 3        LL : -11.7563
ITER = 4        LL : -11.7553
ITER = 5        LL : -11.7552
ITER = 6        LL : -11.7552
ITER = 7        LL : -11.7552
ITER = 8        LL : -11.7552
[New Grammar]
N -> I  0.532391
N -> Maria      0.355308
N -> N PP       1.2904e-08
S -> N V        0.666667
PP -> P N       1
S -> S PP       0.333333
S -> V N        0
V -> V N        0.5
V -> eat        0.5
N -> pizza      0.112301
P -> with       1

Text : I eat pizza with Maria
P(W,T_best) : 0.00118018
P(W) : 0.00118018
0       1       2       S -> S PP
1       3       4       S -> N V
2       5       6       PP -> P N
3       -1      -1      N -> I
4       7       8       V -> V N
5       -1      -1      P -> with
6       -1      -1      N -> Maria
7       -1      -1      V -> eat
8       -1      -1      N -> pizza

Text : Maria eat pizza
P(W,T_best) : 0.00665024
P(W) : 0.00665024
0       1       2       S -> N V
1       -1      -1      N -> Maria
2       3       4       V -> V N
3       -1      -1      V -> eat
4       -1      -1      N -> pizza

LLsum = -11.7552

ランダムな確率から(toy)コーパスを使って推定しなおしても構文木は同じ結果になっている。
1つ目の文の構文木は以下。

上記の推定では、コーパスに出現してない生成規則「N -> N PP」の確率値が小さくなって、推定規則を使ったコーパスの対数尤度が元の対数尤度より大きくすることができている模様(-11.9231→-11.7552)。
また、初期値に与える確率値を変えると結果も変わることも確認できる。(EMアルゴリズム的に)

参考