Efficient Gradient Computation for Structured Output Learning with Rational and Tropical Losses
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 na\"{i}ve 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Structured PredictionSimilar Papers 제목 키워드 기반
Tropical Geometry of Deep Neural Networks
We establish, for the first time, connections between feedforward neural networks with ReLU activation and tropical geometry --- we show that the family of such neural networks is equivalent to the family of tropical rat…
Alternating Minimization for Regression with Tropical Rational Functions
We propose an alternating minimization heuristic for regression over the space of tropical rational functions with fixed exponents. The method alternates between fitting the numerator and denominator terms via tropical p…
regressionTropical Expressivity of Neural Networks
We propose an algebraic geometric framework to study the expressivity of linear activation neural networks. A particular quantity of neural networks that has been actively studied is the number of linear regions, which g…
The Real Tropical Geometry of Neural Networks
We consider a binary classifier defined as the sign of a tropical rational function, that is, as the difference of two convex piecewise linear functions. The parameter space of ReLU neural networks is contained as a semi…
Hurricane Forecasting: A Novel Multimodal Machine Learning Framework
This paper describes a novel machine learning (ML) framework for tropical cyclone intensity and track forecasting, combining multiple ML techniques and utilizing diverse data sources. Our multimodal framework, called Hur…
BIG-bench Machine LearningDecoderHurricane ForecastingTropical Cyclone Intensity Forecasting+1