2019/12/31 by Thuan Nguyen, Thinh Nguyen, Nguyen, Thuan +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Electrical engineering #Information Retrieval (cs.IR) #Information Theory (cs.IT) #Signal Processing (eess.SP) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1912.13141
openalex publication_date 2019/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Set partitioning is a key component of many algorithms in machine learning, signal processing, and communications. In general, the problem of finding a partition that minimizes a given impurity (loss function) is NP-hard. As such, there exists a wealth of literature on approximate algorithms and theoretical analyses of the partitioning problem under different settings. In this paper, we formulate and solve a variant of the partition problem called the minimum impurity partition under constraint (MIPUC). MIPUC finds an optimal partition that minimizes a given loss function under a given concave constraint. MIPUC generalizes the recently proposed deterministic information bottleneck problem which finds an optimal partition that maximizes the mutual information between the input and partition output while minimizing the partition output entropy. Our proposed algorithm is developed based on a novel optimality condition, which allows us to find a locally optimal solution efficiently. Moreover, we show that the optimal partition produces a hard partition that is equivalent to the cuts by hyperplanes in the probability space of the posterior probability that finally yields a polynomial time complexity algorithm to find the globally optimal partition. Both theoretical and numerical results are provided to validate the proposed algorithm.