Paper Info
Title
Efficient Gradient Computation for Structured Output Learning with Rational and Tropical Losses.
Abstract
Many structured prediction problems admit a natural loss function for evaluation such as the edit-distance or n-gram loss. However, existing learning algorithms are typically designed to optimize alternative objectives such as the cross-entropy. This is because a naive implementation of the natural loss functions often results in intractable gradient computations. In this paper, we design efficient gradient computation algorithms for two broad families of structured prediction loss functions: rational and tropical losses. These families include as special cases the n-gram loss, the edit-distance loss, and many other loss functions commonly used in natural language processing and computational biology tasks that are based on sequence similarity measures. Our algorithms make use of weighted automata and graph operations over appropriate semirings to design efficient solutions. They facilitate efficient gradient computation and hence enable one to train learning models such as neural networks with complex structured losses.
Year
Venue
Field
2018
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 31 (NIPS 2018)
Mathematical optimization,Shortest path problem,Computer science,Structured prediction,Algorithm,Artificial intelligence,Deep learning,Backpropagation,String metric,Artificial neural network,Computation,Scalability
DocType
Volume
ISSN
Conference
31
1049-5258
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Corinna Cortes165741120.50
Vitaly Kuznetsov2689.33
Mehryar Mohri34502448.21
Storcheus, Dmitry400.68
Yang, Scott5336.24