RI: Small: Collaborative Research: On-Line Learning Algorithms for Path Experts with Non-Additive Losses

在线学习算法越来越多地被采用为具有数亿或数十亿点的非常大的数据集的现代学习应用的关键解决方案。这些算法一次处理一个样本，每次迭代更新，通常计算成本低且易于实现。此外，这些算法还具有丰富的理论基础。这项研究的目的是通过扩大在线学习的应用范围，包括机器翻译、语音识别、其他自然语言处理应用、手写识别、计算机视觉、生物信息学和许多其他可以造福社会的领域，来推动在线学习的发展。专家技能和学生才能将结合起来，创造出有效的理论和算法解决方案，以及经过实验测试的开源软件工具，这些工具可以使广泛的社区受益。大多数学习问题都有一定的结构。在这样的问题中，专家可以被看作是有向图中的路径，每条边对应于一个子结构，对应于一个单词、音素、字符或图像补丁。目前具有路径专家的在线算法仅限于可加性损失，因此不适用于许多非可加性损失的重要应用。我们将为设计具有非加性损失的路径专家的有效在线学习算法创造理论基础。这种非加性损失是机器翻译、语音识别、发音建模、解析、图像处理等许多重要应用中的相关损失函数。精心设计的加权自动机和半环工具将用于设计具有非加性损失的路径专家的在线算法。算法的理论分析将辅以在各种应用中进行彻底的实验评估。

On-line learning algorithms are increasingly adopted as the key solution to modern learning applications with very large data sets of several hundred million or billion points. These algorithms process one sample at a time with an update per iteration that is typically computationally cheap and easy to implement. Additionally, these algorithms benefit from a rich theoretical foundation. The objective of this research is to advance on-line learning by broadening its applicability to a variety of applications including machine translation, speech recognition, other natural language processing applications, handwriting recognition, computer vision, bioinformatics, and many other areas which can benefit the society. Expert skills and student talent will be combined to create effective theoretical and algorithmic solutions and open-source software tools tested experimentally that can benefit a wide community.Most learning problems admit some structure. In such problems, experts can be viewed as paths in a directed graph with each edge corresponding to a sub-structure corresponding to a word, phoneme, character, or image patch. Current on-line algorithms with path experts are limited to additive losses and therefore are not applicable in many important applications where the loss is non-additive. We will create the theoretical foundation for designing efficient on-line algorithms for learning with path experts with non-additive losses. Such non-additive losses are the relevant loss functions in most important applications such as machine translation, speech recognition, pronunciation modeling, parsing, image processing and other areas. Carefully designed weighted automata and semiring tools will be used to devise on-line algorithms for path experts with non-additive losses. The theoretical analysis of the algorithms will be complemented by a thorough experimental evaluation in a variety of applications.