English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Set partitioning is a key component of many algorithms in machine learning,signal processing, and communications. In general, the problem of finding apartition that minimizes a given impurity (loss function) is NP-hard. As such,there exists a wealth of literature on approximate algorithms and theoreticalanalyses of the partitioning problem under different settings. In this paper,we formulate and solve a variant of the partition problem called the minimumimpurity partition under constraint (MIPUC). MIPUC finds an optimal partitionthat minimizes a given loss function under a given concave constraint. MIPUCgeneralizes the recently proposed deterministic information bottleneck problemwhich finds an optimal partition that maximizes the mutual information betweenthe 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, weshow that the optimal partition produces a hard partition that is equivalent tothe cuts by hyperplanes in the probability space of the posterior probabilitythat finally yields a polynomial time complexity algorithm to find the globallyoptimal partition. Both theoretical and numerical results are provided tovalidate the proposed algorithm.

Minimizing Impurity Partition Under Constraints