最小化约束下的杂质分区
- 2020 年 1 月 1 日
- 筆記
原文标题：Minimizing Impurity Partition Under Constraints
集划分是机器学习，信号处理和通信中许多算法的关键组成部分。通常，寻找使给定杂质（损失函数）最小的分区的问题是NP-hard。因此，存在大量关于不同设置下的分区问题的近似算法和理论分析的文献。在本文中，我们制定并解决了分配问题的一个变体，称为约束下的最小杂质分配（MIPUC）。 MIPUC找到在给定凹约束下使给定损失函数最小的最佳分区。 MIPUC概括了最近提出的确定性信息瓶颈问题，该问题找到了一个最佳分区，该分区使输入和分区输出之间的互信息最大化，同时使分区输出熵（一种测量在动力学方面不能做功的能量总数）最小。我们提出的算法是基于一种新的最优性条件而开发的，它使我们能够有效地找到局部最优解。此外，我们表明，最优分区会产生一个硬分区，该分区等同于后验概率的概率空间中超平面的割伤，最终产生多项式时间复杂度算法来找到全局最优分区。提供理论和数值结果以验证所提出的算法。
原文作者：Thuan Nguyen,Thinh Nguyen
原文链接：https://arxiv.org/abs/1912.13141
