首个可全局最优最小化两层ReLU/Maxout网络误分类数的算法
Deep-ICE: the first globally optimal algorithm for minimizing 0-1 loss in two-layer ReLU and maxout networks
- 基于组合优化构造全局最优解，时间复杂度为O(N^(DK+1))
- 在小数据集上可获得精确解，在大数据集上通过核数据集降维保持高效
- 相比梯度下降和SVM，误分类率降低20%-30%，适合小规模精确学习场景
本文提出首个针对两层Maxout与ReLU网络经验风险最小化的全局最优算法，即最小化误分类数量。该算法最坏时间复杂度为O(N^(DK+1))，其中K为隐藏神经元数，D为特征数。算法可推广至任意可计算损失函数，且不影响复杂度。实验表明，该算法在小规模数据集上能提供严格精确解。为处理大规模数据，我们引入一种新型核数据集选择方法，将数据规模压缩至可处理水平。该扩展使算法能高效处理大规模数据，在相同模型（固定隐藏节点的两层网络及线性模型）下，相较于当前最优方法（梯度下降训练的神经网络与支持向量机），训练与预测阶段误分类率均降低20%-30%。
原文摘要 · Abstract (English)
This paper introduces the first globally optimal algorithm for the empirical risk minimization problem of two-layer maxout and ReLU networks, i.e., minimizing the number of misclassifications. The algorithm has a worst-case time complexity of $O\left(N^{DK+1}\right)$, where $K$ denotes the number of hidden neurons and $D$ represents the number of features. It can be can be generalized to accommodate arbitrary computable loss functions without affecting its computational complexity. Our experiments demonstrate that the proposed algorithm provides provably exact solutions for small-scale datasets. To handle larger datasets, we introduce a novel coreset selection method that reduces the data size to a manageable scale, making it feasible for our algorithm. This extension enables efficient processing of large-scale datasets and achieves significantly improved performance, with a 20-30\% reduction in misclassifications for both training and prediction, compared to state-of-the-art approaches (neural networks trained using gradient descent and support vector machines), when applied to the same models (two-layer networks with fixed hidden nodes and linear models). The artifacts of the Deep-ICE algorithm can be found in https://github.com/XiHegrt/DeepICE-algorithm-artifacts.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。