Ph.D. Thesis Proposal
Synchronous grammars are grammars that model two languages and their translational equivalence. They are rewriting systems extended to two dimensions. Synchronous grammars provide the formal language foundation of syntax-based machine translation. In recent years, statistical syntax-based machine translation is being actively researched. In the general framework of syntax-based or tree-based statistical machine translation, there are many variants of models with different assumptions and prerequisites. Although theoretically, syntax-based models imply polynomial algorithms for machine translation due to the independence assumptions associated with the context-freeness of the grammars, in practice the complexities of the algorithms are still much higher than the IBM models under simple restrictions.
In this proposal, we address the complexity of synchronous grammars arising from the branching factors and the lexicalization of productions. We reduce the factorization problem of synchronous grammar rules to the problem of permutation factorization. We handle the complexities of actual parsing by borrowing from the parsing community techniques for efficient parsing and extend these techniques to bitext space for both training using EM algorithm and decoding using Viterbi algorithm. Our goal is building an efficient fully syntax-based system, also making theoretical contributions on the link between machine translation and permutations.