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

New York University, New York NY

Investigators

Abstract

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.