Fetching the paper…

Reading the bibliography…

Minimizing Impurity Partition Under Constraints · Around

2019

Minimizing Impurity Partition Under Constraints

Nguyen, Thuan, Nguyen, Thinh

Original
PDF
Post on X

Understand

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).

Built on

On channel capacity per unit cost
Sergio Verdu · 1990
Earlier work this paper cites.
An iterative’flip-flop’approximation of the most informative split in the construction of decision trees
Arthur Nádas, David Nahamoo, Michael A Picheny, and Jeffrey Powell · 1991
Earlier work this paper cites.
Optimal partitioning for classification and regression trees
Philip A. Chou · 1991
Earlier work this paper cites.
Minimum impurity partitions
David Burshtein, Vincent Della Pietra, Dimitri Kanevsky, Arthur Nadas, et al · 1992
Earlier work this paper cites.
Partitioning nominal attributes in decision trees
Don Coppersmith, Se June Hong, and Jonathan RM Hosking · 1999
Earlier work this paper cites.

Similar

The information bottleneck method
Naftali Tishby, Fernando C Pereira, and William Bialek · 2000
Cited alongside, same era.
How to construct polar codes
Ido Tal and Alexander Vardy · 2013
Cited alongside, same era.
C4. 5: programs for machine learning
J Ross Quinlan · 2014
Cited alongside, same era.
Quantization of binary-input discrete memoryless channels
Brian M Kurkoski and Hideki Yagi · 2014
Cited alongside, same era.
Decoding ldpc codes with mutual information-maximizing lookup tables
Francisco Javier Cuadros Romero and Brian M Kurkoski · 2015
Cited alongside, same era.

Then

Classification and regression trees
Leo Breiman · 2017
Later among the works it cites.
The deterministic information bottleneck
DJ Strouse and David J Schwab · 2017
Later among the works it cites.
Binary partitions with approximate minimum impurity
Eduardo S Laber, Marco Molinaro, and Felipe A Mello Pereira · 2018
Later among the works it cites.
On the capacities of discrete memoryless thresholding channels
Thuan Nguyen, Yu-Jung Chu, and Thinh Nguyen · 2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…