A Submodularity-based Clustering Algorithm for the Information Bottleneck and Privacy Funnel

Abstract

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