A Submodularity-based Clustering Algorithm for the Information Bottleneck and Privacy Funnel
A Submodularity-based Clustering Algorithm for the Information Bottleneck and Privacy Funnel
复制标题
针对信息瓶颈和隐私漏斗的基于子模的聚类算法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
P. Sadeghi
中科院分区：
文献类型：
--
作者：
Ni Ding;P. Sadeghi
For the relevant data $S$ that nests in the observation $X$, the information bottleneck (IB) aims to encode $X$ into $hat {X}$ in order to maximize the extracted useful information $I(S;hat {X})$ with the minimum coding rate $I(X;hat {X})$. For the dual privacy tunnel (PF) problem where $S$ denotes the sensitive$/mathrm {p}mathrm {r}mathrm {i}mathrm {v}mathrm {a}mathrm {t}mathrm {e}wedge $ data, the goal is to minimize the privacy leakage $I(S;X)$ while maintain a certain level of utility $I(X;hat {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 $hat {mathcal {X}}:= mathcal {X}$ and iteratively merges the elements in the current alphabet $ hat {mathcal {X}}$ that optimizes the Lagrangian function $I(S;hat {X})-lambda I(X;X)$. We prove that the best merge in each iteration of IAC-MDSF can be searched efficiently over all subsets of $hat {mathcal {X}}$ by the existing MDSF algorithms. By varying the value of the Lagrangian multiplier $lambda $, we obtain the experimental results on a heart disease data set in terms of the Pareto frontier: $I(S;hat {X}) mathrm {v}mathrm {s}. -I(X;hat {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.
For the relevant data $S$ that nests in the observation $X$, the information bottleneck (IB) aims to encode $X$ into $hat {X}$ in order to maximize the extracted useful information $I(S;hat {X})$ with the minimum coding rate $I(X;hat {X})$. For the dual privacy tunnel (PF) problem where $S$ denotes the sensitive$/mathrm {p}mathrm {r}mathrm {i}mathrm {v}mathrm {a}mathrm {t}mathrm {e}wedge $ data, the goal is to minimize the privacy leakage $I(S;X)$ while maintain a certain level of utility $I(X;hat {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 $hat {mathcal {X}}:= mathcal {X}$ and iteratively merges the elements in the current alphabet $ hat {mathcal {X}}$ that optimizes the Lagrangian function $I(S;hat {X})-lambda I(X;X)$. We prove that the best merge in each iteration of IAC-MDSF can be searched efficiently over all subsets of $hat {mathcal {X}}$ by the existing MDSF algorithms. By varying the value of the Lagrangian multiplier $lambda $, we obtain the experimental results on a heart disease data set in terms of the Pareto frontier: $I(S;hat {X}) mathrm {v}mathrm {s}. -I(X;hat {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.