Teachability on Grammatical Inference and its Applications for Natural Language Processing

在这项研究中，我们为上下文无关语言的子类开发了一种新的学习算法。在支持项期间的主要结果是我们证明了简单确定性语言的一个子类的多项式时间可教性。这个语言类是多项式时间可教的，但很难在多项式时间内从基于实例的查询中学习。因此，我们的结果显示了通过提问进行教和学的区别。接下来，我们将该算法应用到自然语言处理中，开发了一个用于会话的文本分割算法，并展示了该算法的性能改进。此外，我们还将该算法应用于博弈树搜索。然后提出了一种改进的强化学习算法来构造评价函数。我们也证实了我们的算法提高了学习性能。

In this study, we developed a new learning algorithm for a subclass of context-free languages. The main result during the supported term is that we showed polynomial time teachability of a subclass of simple deterministic languages. This language class is polynomial time teachable but it would be hard to learn from example based queries in polynomial time. Thus, our result shows a difference between teaching and learning via queries. Next, we applied our algorithm to natural language processing, then we developed a text segmentation algorithm for conversations and showed the performance improvement. In addition, we applied our algorithm to game tree search. Then we showed an improvement of reinforcement learning algorithm for making the evaluation function. We also confirmed the learning performance is improved by our algorithm.