关键词: 可微组合损失, 广义梯度, 线性规划, 神经网络

Abstract: Combinatorial problems with linear objective functions have a wide range of applications in real life, and there are many highly efficient algorithms for finding the optimal solutions to these combinatorial optimization problems. With the continuous development of artificial intelligence technology, people can make full use of the characteristics of powerful function approximators such as neural networks and combine rich feature extraction with efficient combinatorial solvers to achieve efficient approximate solution of high complexity combinatorial problems in an end-to-end, without any compromise. However, the solutions to the above combinatorial problems are similar with respect to the parameters in the problem instance, therefore, it is difficult for us to use gradient-based methods to optimize the model when the solution to the combinatorial problem is used as the criterion for model training. Many authors have attempted to apply combinatorial optimization and more broad convex optimization solvers to gradient-trained models. Several methods have been developed to differentiate the solution vectors of optimization problems. In most cases, we only need to differentiate the objective value (not the solution vector), but current existing methods can introduce unnecessary extra computations.
Here, we show how to perform gradient descents directly over the objective value of the solution to the combinatorial problems. Specifically, for efficiently solvable combinatorial problems that can be efficiently expressed as integer linear programs, the generalized gradients of objective values with respect to the real-valued parameters in the problem exist and can be efficiently computed by a black-box combinatorial algorithm in a single-run. This way of turning combinatorial solvers into differentiable building blocks in deep learning models enables us to execute their internal algorithms more efficiently. While ensuring the generalization of combinatorial deep learning models, it solves the problems: combinatorial solvers are difficult to be directly invoked and their applicability under specific problem structures is difficult to guarantee.
Moreover, we conduct two experiments: (1)weakly supervised image classification and (2)global sequence alignment problems with differentiable encoder-decoder architectures using Softmax or Gumbel-Softmax. The experimental results show that our proposed method can provide differentiable combinatorial losses for the above problems. Compared with other existing methods, our proposed method has the advantages of being more stable in training processes and more accurate and efficient in prediction. Specifically, in experiment (1), we use the information from the model about the class probability distribution output by each feature vector, match the model’s output about the feature vectors in the bag to the class label, and use the Hungarian algorithm as a combinatorial solver to find the permutation order in this problem. Compared with the existing gradient-based methods, the proposed method using generalized gradient to solve combinatorial optimization problems can provide training signals for large neural networks very effectively and is much faster than the current state-of-art methods in training speed. In experiment (2), we use Global Sequence Alignment (GSA) as loss. Compared to training using baseline loss, the proposed method achieves the best text summarization results of all three ROUGE evaluation metrics, and is more accurate and effective.
In the future, we will do further research on how to apply the proposed method in this paper. For example, DEtection TRansformer (DETR) was the first algorithm to apply the Transformer encoder-decoder architecture to object detection, and its architecture has become a building block in many transformer-based applications. However, DETR usually is set-based on the global loss function, which leads to inconsistent allocation cost and global loss. How to use the generalized gradient-based method proposed in this paper to improve the convergence speed and performance of DETR is a very valuable research direction.

Key words: differentiable combinatorial losses, generalized gradients, linear programs, neural networks