SGER: Scaling up unsupervised grammar induction

这个SGER项目旨在确定计算密集型、迭代统计学习算法在MapReduce架构上的可扩展性。这些算法是自然语言处理研究的基础，但它们在中等规模的训练数据集（文本语料库）上的可扩展性尚未得到充分探索。从表面上看，扩展到更多的数据似乎很适合MapReduce范式，这个探索性项目旨在确定这些算法是否从更多的数据和更复杂的数据中受益，而不是在以前的工作中使用。特别强调了无监督学习算法，如期望最大化算法，这些算法在小问题上得到了广泛的研究，而在大问题上却很少得到研究。这项技术也适用于许多其他方法。与此同时，该项目寻求探索如何利用超级计算机和MapReduce使这些学习算法更快，从而加快研究周期。具体来说，“E步”（或类似步骤）是迭代中计算量要求最高的部分，但是训练数据是独立且相同分布的标准假设允许并行化。在这种并行化受到网络和输入输出开销影响的程度上，训练的每次迭代可能会更快，可能会将训练时间从几天或几周减少到几小时。本项目探讨了这种权衡和其他类似的权衡。这项工作利用了雅虎捐赠的资源，供PI的研究小组使用：一台运行Hadoop （MapReduce的开源实现）的4000节点超级计算机。

This SGER project seeks to determine the scalability of computationally intensive, iterative statistical learning algorithms on a MapReduce architecture. Such algorithms underlie much research in natural language processing, yet their scalability to even moderately large training datasets (text corpora) has been under-explored. On the surface, scaling to more data appears to be a good fit for the MapReduce paradigm, and this exploratory project aims to identify whether such algorithms benefit from more data and more complex data than used in prior work. A special emphasis is given to unsupervised learning algorithms, such as the Expectation-Maximization algorithm, which have been widely studied on small problems and rarely studied on large ones. The technique is applicable to many other methods, as well.At the same time, the project seeks to explore how to leverage supercomputers and MapReduce to make these learning algorithms faster, permitting a faster research cycle. Concretely, the "E step" (or itsanalogue) is the most computationally demanding part of an iteration, but the standard assumption that the training data are independently and identically distributed permits parallelization. To the extent that this parallelization is affected by network and input-output overhead, each iteration of training may be made faster, perhaps reducing training time from days or weeks to hours. This project explores this tradeoff and others like it.This work leverages a resource donated by Yahoo for use by the PI's research group: a 4,000-node supercomputer running Hadoop (an open-source implementation of MapReduce).