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.