A Submodularity-based Clustering Algorithm for the Information Bottleneck and Privacy Funnel
Ni Ding, Parastoo Sadeghi · 2019
For the relevant data S that nests in the observation X, the information bottleneck (IB) aims to encode X into X̂ in X, with order to maximize the extracted useful information I(S; X̂) with the minimum coding rate I(X; X). For the dual privacy funnel (PF) problem where S denotes the sensitive/private data, the goal is to minimize the privacy leakage I(S; X̂) while maintain a certain level of utility I(X; X̂). For both problems, we propose an efficient iterative agglomerative clustering algorithm based on the minimization of the difference of submodular functions (IAC-MDSF). It starts with the original alphabet X̂ := X and iteratively merges the elements in the current alphabet X̂ that optimizes the Lagrangian function I(S; X̂)-λI(X; X̂). We prove that the best merge in each iteration of IAC-MDSF can be searched efficiently over all subsets of X̂ by the existing MDSF algorithms. By varying the value of the Lagrangian multiplier λ, we obtain the experimental results on a heart disease data set in terms of the Pareto frontier: I(S; X̂) vs. -I(X; X̂). We show that our IAC-MDSF algorithm outperforms the existing iterative pairwise merge approaches for both PF and IB and is computationally much less complex.