Designing practical algorithms for learning formal languages based on distribution of strings in contexts

最近，通常被称为“分布式学习”的方法在学习与上下文无关的语言方面取得了巨大的成功。这个研究项目揭示了这两种分布式学习方法的精确数学对称性。在此基础上，我们对现有的分布式学习算法进行了统一的评价，并设计了一种集成现有分布式学习算法的算法。该算法对上下文无关语言的学习能力比其他分布式学习算法强。此外，我们还展示了这些技术可以以统一的方式应用于比上下文无关语法更强大的不同语法形式。我们还提出了一种算法，该算法仅以高概率和高准确性从正例中学习特定的上下文无关语言。

Recently the approaches generically called "distributional learning" have been making a great success in the learning of context-free languages. This research project revealed the exact mathematical symmetry of the two types of distributional learning approaches. Based on this observation, we gave a uniform view of the existing distributional learning algorithms and designed an algorithm which integrates existing distributional learning algorithms in it. The obtained algorithm is stronger than other distributional learners for context-free languages. Moreover, we showed that the techniques can be applied to different grammar formalisms that are more powerful than context-free grammars in a uniform way. We also proposed an algorithm that learns certain context-free languages from positive examples only with high probability and accuracy.