Conditional Mutual Information¶
Denote \(\mathcal{V}\) as the ground-set of items to be summarized. We denote by \(\mathcal{V}^{\prime}\) an auxiliary set that contains user-provided information such as a query (for query-focused summarization) or a private set (for privacy-preserving summarization) or both in the case of joint query and privacy-preserving summarization. The auxilliary information provided by the user may not be in the same space as the items in \(\mathcal{V}\) – for example, if the items in \(\mathcal{V}\) are images, the query could be text queries. In such a case, we assume we have a joint embedding that can represent both the query and the image items, and correspondingly, we can define similarity between the items in \(\mathcal{V}\) and \(\mathcal{V}^{\prime}\). Next, let \(\Omega = \mathcal{V} \cup \mathcal{V}^{\prime}\) and define a set function \(f: 2^{\Omega} \rightarrow \Re\). Although \(f\) is defined on \(\Omega\), summarization is on the items in \(\mathcal{V}\), i.e., the discrete optimization problem will be only on subsets of \(\mathcal{V}\).
We define the submodular conditional mutual information of sets \(A,B\) given set \(C\) as
Intuitively CMI jointly models the mutual similarity between \(A\) and \(B\) and their collective dissimilarity from \(C\).
One possible application of CMI is joint query-focused and privacy preserving summarization. Given a query set \(Q\) and a private set \(P\), we would like to select a subset \(A \subseteq \mathcal{V}\) which has a high similarity with respect to a query set \(Q\), while simultaneously being different from the private set \(P\). A natural way to do this is by maximizing the above conditional submodular mutual information such that \(B=Q\) and \(C=P\).
Properties of conditional mutual information are studied at length in [IKBA21]. In particular, CMI is non-negative and monotone in one argument with the other fixed [GL20, IKBA21]. CMI however is not necessarily submodular in one argument (with the others fixed) [IKBA21, KSG08]. However, certain instantiations of CMI may turn out to be submodular.
Note
Given a submodular function \(f\), the CMI can either be viewed as the mutual information of the conditional gain function, or the conditional gain of the submodular mutual information [KKR+20].
Examples of Conditional Mutual Information functions:
ProbabilisticSetCoverConditionaMutualInformationFunction