320 lines
22 KiB
TeX
320 lines
22 KiB
TeX
\section{Applicazione a problemi}\label{applicazioneprob}
|
|
|
|
\subsubsection{``Submodular Cover'', ``Submodular Knapsack Constraints'' e ``Submodular Welfare Problem''}
|
|
|
|
Fra i problemi più famosi dell'informatica ci sono il problema dello zaino e il ``minimum set cover''. Si vede ora come si può arrivare ai problemi più specifici che riguardano le funzioni submodulari affrontate in ``Generalized submodular information measures: Theoretical properties, examples, optimization algorithms, and applications''\cite{generalizedsubmodular2022}.
|
|
|
|
\paragraph{``Minimum Set Cover''\cite{gareyjohnson2003}}
|
|
Dato un insieme $S = \{ s_1, \ldots, s_t \}$ e un insieme $C = \{c_1, \ldots, c_k\} \subseteq \mathcal{P}(S)$ con $\forall s\in S, \exists c_j \in C $ tale che $ s \in c_j$,
|
|
sia una ``set cover'' dell'insieme $S$ un insieme $I \subseteq \{1, \ldots, j\}$ tale che $ \bigcup_{i \in I}c_i = S $.
|
|
La soluzione del problema è quindi l'insieme $I^*$ con cardinalità minima. Il problema è NP-hard dato che si riconduce a 3-dimensional matching\cite{gareyjohnson2003}.
|
|
|
|
\paragraph{``Submodular Set Cover''\cite{wolsey1982}}
|
|
Data una funzione $f: \mathcal{P}(S) \to \mathbb{R}$ submodulare non decrescente, il problema consiste nel trovare il sottoinsieme di peso minimo tale che ``copra'' tutti gli elementi dell'insieme $S$, cioè abbia lo stesso valore rispetto la funzione $f$.
|
|
\[ I^* = \min_{I \subset S}\{ \sum_{i \in I}c_i | f(I) = f(S) \} \]
|
|
Si osserva che ci si può ricondurre al ``minimum set cover'' prendendo $f(I) = \sum_{i=1}^t \min\{\sum_{j \in S}a_{ij},b_i\}$.
|
|
|
|
\paragraph{``SCSC (Submodular Cost Submodular Cover)''\cite{submodularoptimization2013}}
|
|
Il problema che viene affrontato è un'ulteriore generalizzazione che richiede che la funzione costo sia polimatroide invece di modulare come nel caso precedente.
|
|
$\min_{I \subseteq S}\{f(I)|g(I) \ge c\} \textnormal{ con } f,g $ funzioni submodulari, monotone non decrescenti e normalizzate, cioè $ f(\emptyset) = g(\emptyset) = 0$.
|
|
\begin{center}
|
|
{\color{black!30} \dotfill}
|
|
\end{center}
|
|
|
|
\paragraph{Problema dello Zaino\cite{gareyjohnson2003}}
|
|
Dato un insieme $S = \{ s_1, \ldots, s_t\}$ e una funzione $f: S \to \mathbb{Z}^+$, un valore $b$ che è la dimensione dello zaino e un intero positivo $K$,
|
|
sia $I$ una partizione dell'insieme $S$ tale che $\sum_{i \in I} f(i) \le b$.
|
|
La soluzione del problema è quindi l'insieme $I^*$ con $\sum_{i \in I^*} f(i)$ massimo.
|
|
|
|
\paragraph{``Submodular Knapsack Problem''\cite{submodularknapsackpolytope2009}}
|
|
Data una funzione $f$ submodulare, il problema consiste nel trovare l'insieme con peso dato da $f$ più vicino al limite $b$. In particolare trovare $I^*$ tale che $I^* = \max_{I \subset S}\{ \sum_{i \in I}f(i) \le b \} $ con $f$ una funzione submodulare.
|
|
|
|
Si osserva che per $f$ modulare ci si riconduce al problema dello zaino.
|
|
|
|
\paragraph{``SCSK (Submodular Cost Submodular Knapsack)''\cite{submodularoptimization2013}}
|
|
Simile al caso precedente, si generalizza il problema richiedendo che l'obbiettivo da massimizzare sia una funzione submodulare.
|
|
$\max_{I \subseteq S}\{g(I)|f(I) \le b\} $ con $ f,g $ funzioni submodulari, monotone non decrescenti e normalizzate, cioè $ f(\emptyset) = g(\emptyset) = 0$.
|
|
|
|
Sia SCSC che SCSK sono NP-hard, tuttavia sono notevolmente più difficili da affrontare rispetto a ``submodular set cover'' e ``submodular knapsack'' perchè le garanzie sui limiti e sulla complessità cambiano polinomialmente rispetto alla curvatura di $f$, mentre solo in modo costante rispetto alla curvatura di $g$.
|
|
I problemi SCSC e SCSK sono fortemente connessi fra loro, infatti in tempo polinomiale si può trasformare ogni istanza di un problema in un'istanza dell'altro\cite{submodularoptimization2013}.
|
|
Entrambi i problemi possono essere affrontati tramite un algoritmo ``greedy'', su cui si hanno limiti noti\cite{submodularoptimization2013}.
|
|
|
|
\paragraph{``Submodular Welfare Problem''}
|
|
Un altro problema NP-hard\cite{submodularwelfare2010} per le funzioni submodulari è il ``submodular welfare problem'':
|
|
\begin{definizione}
|
|
Dati $m$ oggetti, $n$ giocatori a cui è associata una funzione submodulare $\omega_i: \mathcal{P}(\{1,\ldots,m\})\to \mathbb{R}^{+}$, trovare una partizione di $ \{1,\ldots,m\} = S_1 \cup S_2 \cup \ldots \cup S_n$ tale che $ \sum_{i=1}^{n}\omega_i(S_i) $ sia massima.
|
|
\end{definizione}
|
|
Pure questo problema ha un'approssimazione di almeno $ 1 - \frac{1}{e}$\cite{combinatorialauctions2006} grazie a un rilassamento di programmazione lineare del problema e con ``randomized rounding''\cite{combinatorialauctions2006}.
|
|
|
|
|
|
\subsubsection{Algoritmo ``greedy'' e curvatura}
|
|
%% cite{sviridenkovondrakward2014} per tutta la roba sulla curvatura
|
|
Per risolvere problemi di massimizzazione di funzioni submodulari non decrescenti soggette a limiti di cardinalità si impiega spesso l'algoritmo ``greedy'', che ha come risultato classico l'approssimazione di $1-\frac{1}{e}$ rispetto alla soluzione ottima\cite{nemhauserwolseyfisher1978}. L'approssimazione è ottima se si suppone che la funzione submodulare possa essere valutata un numero polinomiale di volte.
|
|
|
|
Esistono versioni continue\cite{vondrakjan2014}\cite{vondrakjan2020} che migliorano sia la complessità che le garanzie sull'approssimazione.
|
|
|
|
L'algoritmo ``greedy'' costruisce la soluzione partendo dall'insieme vuoto, senza backtracking, aggiungendo ad ogni passaggio l'elemento con valore dato da $f$ più alto fra quelli non ancora scelti.
|
|
|
|
\begin{center}
|
|
{\linespread{1}
|
|
\begin{algorithm}[H]
|
|
\renewcommand{\thealgorithm}{``greedy''\cite{nemhauserwolseyfisher1978}}
|
|
\caption{}\label{alg:cap}
|
|
\begin{algorithmic}[1]
|
|
\State{$S^0 \gets \emptyset, V^0 \gets V, t \gets 1$}
|
|
\While{$ t \ne k $}
|
|
\State{$ i(t) \in V^{t-1} $ tale che $ f(S^{t-1}|\{i(t)\})=\max_{i \in V^{t-1}}(S^{t-1}) $}
|
|
|
|
\If{$ f(S^{t-1}|\{i(t)\}) \le 0$}
|
|
\State{$ k^* \gets t-1\qquad $}\Comment{$ k^* < k $}
|
|
\State{\textbf{return} {$ S^{k^*} $}}
|
|
\ElsIf{$ f(S^{t-1}|\{i(t)\}) > 0 $}
|
|
\State{$ S^t \gets S^{t-1} \cup \{ i(t) \} $}
|
|
\State{$ V^t \gets V^{t-1} \setminus \{i(t)\} $}
|
|
\State{$ t \gets t + 1$}
|
|
\EndIf % chktex 1
|
|
\EndWhile % chktex 1
|
|
|
|
\State{$ k^* \gets k\qquad $}\Comment{$ k^* == k $}
|
|
\State{\textbf{return} {$ S^{k^*} $}}
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
}
|
|
\end{center}
|
|
|
|
Accade molto spesso che si ottengano risultati molto più vicini all'ottimo rispetto al caso peggiore di $1-\frac{1}{e}$.
|
|
|
|
Per quantificare questo fenomeno si impiega la nozione di curvatura, cioè si stabilisce quanto la funzione sia distante dall'essere lineare.
|
|
\begin{definizione}
|
|
Una funzione submodulare $f: \mathcal{P}(V) \to \mathbb{R}^+$ ha curvatura $\kappa \in [0, 1]$ se $f(S+j) - f(S) \ge (1 - \kappa)f({j}), \forall S \subset E, \forall j \in V \setminus S$.
|
|
\end{definizione}
|
|
In particolare se $\kappa = 0$ allora la funzione è lineare.
|
|
|
|
\sloppy L'algoritmo ``greedy'' per funzioni submodulari non decrescenti produce un'ap\-pros\-si\-ma\-zio\-ne di almeno $\frac{1-e^{-\kappa}}{\kappa}$, che tende a $1$ per $ \kappa \to 0 $\cite{sviridenkovondrakward2014}.
|
|
%% NOTE forse scrivere anche che in \cite{sviridenkovondrakward2014} c'è un'approssimazione migliore di (1-\frac{c}{e}-O(\epsilon))
|
|
|
|
Si può anche definire la curvatura rispetto ad un insieme:
|
|
\begin{definizione}
|
|
Una funzione submodulare $f: \mathcal{P}(V) \to \mathbb{R}^+$ ha curvatura $\kappa_f(S) = 1 - \min_{j\in S} \frac{f(j|S \setminus j)}{f(j)}$ rispetto ad un insieme $S \subseteq V$.
|
|
\end{definizione}
|
|
|
|
|
|
\subsection{Submodular Mutual Information-Based Selection}
|
|
Il problema consiste nella massimizzazione della funzione d'informazione submodulare fra un sottoinsieme e il complementare, limitando la cardinalità dell'insieme, cioè massimizzare $\mathcal{I}_f(A;V \setminus A)$ con $\norm{A}=k$.
|
|
Rispetto ad ottimizzare soltanto $f(A)$ si ha stabilità migliore rispetto a ``outliers'' dato che si impone somiglianza fra $A$ e $V \setminus A$.
|
|
|
|
%% TODO vedere se includere questo passaggio pg 13 basso sinistra
|
|
% Per esempio nel caso in cui $\mathcal{I}_f(A;V \setminus A) = \omega(\gamma(A)\cap\gamma(V \setminus A))$ e $f(A = \omega(\gamma(A)))$, la presenza di ``outliers''
|
|
Si osserva che $\mathcal{I}_f(A;V \setminus A)$ è submodulare ma non monotona, quindi l'approssimazione garantita dall'argoritmo ``\textit{greedy}'' precedente di $(1- \frac{1}{e})$\cite{nemhauserwolseyfisher1978} non è garantita.
|
|
Tuttavia si può ottenere una garanzia di $\frac{1}{e}$ attraverso un algoritmo ``randomized greedy''\cite{feigemirroknivondrak2011} dato che la funzione è non monotona submodulare e si limita la cardinalità.
|
|
|
|
\begin{teorema}\cite{generalizedsubmodular2022} %% TODO dimostrazione
|
|
Sia $f(j)\le1, \forall j \in V$, allora $g(A) = \mathcal{I}_f(A;V \setminus A)$ è $\epsilon$-ap\-pros\-si\-ma\-ti\-va\-men\-te monotona per un $A$ con fattore $\kappa_f(A)$, cioè $g(j|A) \ge -\kappa_f(A), \forall j \in V, A \subseteq V$, con $\kappa_f(A) = \max_{j \in V \setminus A}\frac{f(j|V \setminus (A \cup j))}{f(j)}$.
|
|
\end{teorema}
|
|
|
|
\begin{definizione}[$\epsilon$-approssimativamente monotona\cite{maxmizingapproximation2019}]
|
|
Sia $\epsilon \ge 0$. $f: \mathcal{P}(V) \to \mathbb{R}$ è $\epsilon$-approssimativamente monotona se $ \forall S \subseteq V, \forall s \notin S$ si ha $ f(S \cup \{s\}) \ge f(S) - \epsilon $, o in modo equivalente $f(\{s\}|S) \ge - \epsilon$.
|
|
\end{definizione}
|
|
|
|
\begin{dimostrazione}
|
|
Sia $g(A) = \mathcal{I}_f(A;V \setminus A) = f(A) + f(V \setminus A) - f(V)$. Per studiare la monotonicità di $g(A)$ si considera il guadagno aggiungendo un elemento $j \notin A$ ad $A$: $g(j|A) = g(A \cup \{j\}) - g(A) = f(A \cup \{j\}) + f(V \setminus (A \cup {j})) - f(V \setminus A)$. Quindi $ g(j|A) = f(j|A) - f(j|V \setminus (A \cup \{j\}))$.
|
|
La differenza può essere sia negativa che positiva, quindi in generale è soltanto $\epsilon$-approssimativamente monotona:
|
|
sia $\kappa_f(A) = \max_{j\in V \setminus A} (\frac{f(j|V\setminus (A \cup \{j\}))}{f(j)})$ la curvatura di $f$ per l'insieme $A$. Si ha quindi che $g(j|A) \ge f(j|A) - \kappa_f(A)\cdot f(j)$.
|
|
Dato che $f$ è monotona, $f(j|A)\ge0 \implies g(j|A) \ge - \kappa_f(A) \cdot f(j)$.
|
|
Se si assume che $\forall j \in V, f(j)\le 1$ allora $g(j|A)\ge - \kappa_f(A)$.
|
|
\end{dimostrazione}
|
|
|
|
L'algoritmo ``greedy'' garantisce di fornire una soluzione $\hat{A}$ con $\bigl|\hat{A}\bigr|=k$ e tale che $ \mathcal{I}_f(\hat{A};V \setminus \hat{A}) \ge (1-\frac{1}{e})\cdot(g(A^*) - k \cdot \kappa_f(A^*))$, dove $A^*$ è la soluzione ottima. %% usin \bigl and \bigr because \left and \right use the hat bounding box
|
|
|
|
\subsection{Query-Based and Privacy Preserving Summarization}
|
|
Si consideri il problema di massimizzazione dell'informazione mutua rispetto a un ``query set'' $Q$ e/o un ``private set'' $P$.
|
|
|
|
\subsubsection{Query-Based Summarization}
|
|
Si considera il problema quando $P=\emptyset$. Si ottengono due formulazioni del problema: ``direct optimization'' massimizzando l'informazione mutua e ``constrained formulation using conditional gain''.
|
|
|
|
\textit{Ottimizzazione diretta massimizzando l'informazione mutua}
|
|
|
|
Il problema può essere formulato come la massimizzazione dell'informazione mutua fra il ``query set'' $Q$ e l'insieme $A$, più un termine di correzione per diversità/rappresentazione.
|
|
\[ \max_{A \subseteq V, \norm{A} \le j} \mathcal{I}_f(A;Q) + \lambda \cdot g(A) \]
|
|
dove $g$ è una funzione submodulare e $\lambda \in \mathbb{R}$.
|
|
|
|
Si ha quindi un compromesso fra la massimizzazione della rilevanza rispetto alla ``query'' e rappresentazione/diversificazione tramite $g(A)$ con un parametro $\lambda$ come peso.
|
|
|
|
Si osserva che $ \mathcal{I}_f(A;Q) $ non è in generale submodulare in $A$ rispetto a $Q$.
|
|
|
|
\begin{teorema}\cite{generalizedsubmodular2022}
|
|
Se $f^{(3)}(i,j,k;A) \ge 0$ e $g$ è monotona submodulare, allora l'algoritmo ``greedy'' ottiene un'approssimazione di almeno $1-\frac{1}{e}$.
|
|
\end{teorema}
|
|
|
|
In particolare i problemi di ``set cover'' e ``facility location'' soddisfano queste ipotesi.
|
|
|
|
Si osserva che non avere una ``query'' vuol dire che $Q=V$, che implica $\mathcal{I}_f(A;Q) = f(A)$.
|
|
|
|
\textit{``Constrained formulation'' usando guadagno condizionale}
|
|
|
|
Una formulazione equivalente del problema è la seguente:
|
|
\begin{equation*}
|
|
\begin{dcases}
|
|
\max_{A \subseteq V}g(A) \\
|
|
f(A|Q) \le \epsilon \\
|
|
\norm{A} \le k
|
|
\end{dcases}
|
|
\end{equation*}
|
|
|
|
Siccome $\mathcal{I}_f(A;Q) = f(A) - f(A|Q)$, massimizzare $\mathcal{I}_f(A;Q)$ è equivalente a minimizzare $f(A|Q)$.
|
|
|
|
Dato che sia $f(A|B)$ e $g(A)$ sono funzioni submodulari in $A$, il problema si riduce alla massimizzazione submodulare con molteplici vincoli sulla cardinalità.
|
|
|
|
In particolare la seconda formulazione del problema ammette nel peggiore dei casi un'approssimazione di $ \left[ 1-\frac{1}{e}, \frac{n}{1+(n-1)(1-\kappa_f)} \right] $, dove $\kappa_f = 1-\min_{j \in V}\frac{f(j|V \setminus j)}{f(j)}$ è la curvatura.
|
|
\begin{definizione}\cite{submodularoptimization2013}
|
|
Un algoritmo è un algoritmo $[\alpha,\beta]$ bi-criterio se è garantito di ottenere l'insieme soluzione $S$ tale che $f(S) \ge \alpha f(S^*)$ e $g(S) \le k' = \beta k$, dove $S^*$ è la soluzione ottima.
|
|
\end{definizione}
|
|
|
|
Per il problema precedente quindi il fattore di approssimazione su $g(A)$ è $\alpha$, tuttavia $f(A|Q) \le \beta \epsilon$ e $ \norm{A} \le \beta k$ per $\beta>1$.
|
|
|
|
%% TODO aggiungere forse una riga su quale algoritmo è migliore pag 14
|
|
\par
|
|
Si osserva che però la seconda formulazione del problema richiede meno ipotesi per ammettere garanzie sul limite; se verificate le garanzie sono costanti nel primo caso, mentre nel secondo hanno un fattore polinomiale; infine il parametro $\epsilon$ è simile al parametro $\lambda$, ma è meno indiretto nell'effetto sulla somiglianza della ``query''.
|
|
|
|
|
|
\subsubsection{Privacy Preserving Summarization}
|
|
|
|
Rispetto al ``query based summarization'', l'obiettivo è quello di ottenere un ``riassunto'' $A$ che ha poca informazione mutua rispetto l'insieme $P$, che contiene quindi informazioni che non vogliono essere contenute in $A$.
|
|
|
|
\textit{Ottimizzazione diretta minimizzando l'informazione mutua}
|
|
|
|
In modo simile al \textit{Ottimizzazione diretta massimizzando l'informazione mutua} del problema con ``query'', si può ottenere la formulazione seguente\label{NSMImax}:
|
|
\[ \max_{A \subseteq V, \norm{A}\le k}\lambda g(A) - \mathcal{I}_f(A;P) = \max_{A \subseteq V, \norm{A}\le k} \lambda g(A) +f(P|A) \]
|
|
|
|
$f(P|A)$ è submodulare in $A$ soltanto se $f^{(3)}(i,j,k;A)\le 0$, quindi la massimizzazione non è trattabile nella maggior parte dei casi.
|
|
|
|
Inoltre nel caso in cui $P=\emptyset$, cioè non ci sono limiti per l'insieme di ``privacy'', $\mathcal{I}_f(A;P) = \mathcal{I}_f(A;\emptyset) = 0$, quindi non si riottiene il caso della semplice massimizzazione di $f(A)$.
|
|
|
|
\textit{Ottimizzazione diretta massimizzando il guadagno condizionale}
|
|
|
|
Invece di massimizzare $f(P|A)$ viene massimizzato $f(A|P)$. Anche se risulta un problema differente, l'obiettivo che cerca di raggiungere è simile, cioè ottenere l'insieme $A$ più distante da $P$.
|
|
\[ \max_{A\subseteq V, \norm{A}\le k} \lambda g(A) + f(A|P) \]
|
|
|
|
Il problema è quindi un'istanza della massimizzazione di una funzione monotona submodulare, quindi l'algoritmo ``greedy'' ammette approssimazione di $1 - \frac{1}{e}$.
|
|
|
|
Si osserva che avere un insieme di ``privacy'' vuoto risulta nella massimizzazione della funzione $f(A)$.
|
|
|
|
\textit{``Constrained formulation'' usando l'informazione mutua}
|
|
|
|
Si vuole di nuovo ottenere un parametro per manipolare meglio la differenza richiesta fra $A$ e $P$.
|
|
|
|
\begin{equation*}
|
|
\begin{dcases}
|
|
\max_{A\subseteq V}g(A)\\
|
|
\mathcal{I}_f(A;P)\le\epsilon\\
|
|
\norm{A} \le k
|
|
\end{dcases}
|
|
\end{equation*}
|
|
|
|
Invece di minimizzare $\mathcal{I}_f(A;P)$, viene aggiunto ai limiti. Si osserva inoltre che $\mathcal{I}_f(A;P)$ è submodulare se la terza derivata parziale di $f$ è non negativa, come nei problemi di ``facility location'' o ``set cover''.
|
|
Quindi questa formulazione è più facilmente trattabile rispetto alle altre, oltre ad avere controllo esplicito della privacy attraverso $\epsilon$.
|
|
Infine se $P=\emptyset$ si ottiene $\mathcal{I}_f(A;P) = \mathcal{I}_f(A;\emptyset) = 0$, e il problema si riconduce alla massimizzazione di $f(A)$.
|
|
|
|
|
|
\subsubsection{Joint Query e Privacy Preserving Summarization}
|
|
|
|
Si consideri quindi il problema di ottenere simultaneamente un riassunto $A$ rispetto a una ``query'' $Q$, rispettando un insieme di ``privacy'' $P$.
|
|
Come per i casi precedenti si possono individuare diverse formulazioni del problema.
|
|
|
|
|
|
\textit{Ottimizzazione diretta utilizzando l'informazione mutua}
|
|
\[ \max_{A\subseteq V, \norm{A}\le k} \mathcal{I}_f(A;Q) - \mathcal{I}_f(A;P) + \lambda g(A) \]
|
|
|
|
Tuttavia questa formulazione non è adeguata quando si pone $Q=V$ o $Q=\emptyset$. Infatti per $Q=V$ si ottiene $f(A)-\lambda g(A) - \mathcal{I}_f(A;P)$, simile ad una formulazione precedente inapprossimabile (\ref{NSMImax}), mentre per $Q=\emptyset$ si ottiene $ \lambda g(A) - \mathcal{I}_f(A;P)$, che è esattamente una formulazione precedente inapprossimabile (\ref{NSMImax}).
|
|
|
|
|
|
\textit{Ottimizzazione diretta sommando i termini ``query'' e ``privacy''}
|
|
|
|
\sloppy In\-ve\-ce di usare un solo iperparametro, si parametrizza sia $\mathcal{I}_f(A;Q)$ che $f(A|P)$:
|
|
\begin{equation*}
|
|
\max_{A\subseteq V, \norm{A}\le k} \lambda_1 \mathcal{I}_f(A;Q) + \lambda_2 f(A|P) + g(A)
|
|
\end{equation*}
|
|
|
|
Questa formulazione permette un'approssimazione di $1 - \frac{1}{e}$ della soluzione ottima\cite{generalizedsubmodular2022}.
|
|
Inoltre per $ P=\emptyset $ e $ Q=V $ si ottengono rispettivamente ``query based summarization'' e ``privacy preserving summarization''.
|
|
|
|
|
|
\textit{``Constrained formulation by combining the query and privacy constraints''}
|
|
|
|
In modo simile ai problemi separati precedenti, si possono usare vincoli invece che sommare i termini:
|
|
\begin{equation*}
|
|
\begin{cases}
|
|
\max\limits_{A\subseteq V} g(A) \\
|
|
f(A|Q) \le \epsilon_1 \\
|
|
\mathcal{I}_f(A;P) \le \epsilon_2 \\
|
|
\norm{A} \le k \\
|
|
\end{cases}
|
|
\end{equation*}
|
|
|
|
\sloppy Tut\-ta\-vi\-a, come per ``privicy preserving summarization'', è necessario che $\mathcal{I}_f(A;P)$ sia submodulare, che quindi richiede che $f^{(3)}$ sia non negativa.
|
|
|
|
Nei casi in cui la derivata terza potrebbe non essere non negativa si può riformulare il problema usando $f(A|Q)$:
|
|
\begin{equation*}
|
|
\begin{cases}
|
|
\max_{A\subseteq V}g(A) + \lambda_2 f(A|P)\\
|
|
f(A|Q) \le \epsilon_1 \\
|
|
\norm{A} \le k \\
|
|
\end{cases}
|
|
\end{equation*}
|
|
|
|
Sia la funzione da massimizzare che la funzione ``constraint'' sono submodulari, quindi è un istanza del problema \textnormal{SCSK}.
|
|
|
|
|
|
\textit{Ottimizzazione diretta con una funzione obbiettivo comune per i termini ``privacy'' e ``query''}
|
|
|
|
Si può semplificare la formulazione del problema combinando le due funzioni obiettivo in un'unica funzione, rimuovendo quindi un iperparametro.
|
|
\begin{equation*}
|
|
\max_{A\subseteq V, \norm{A}\le k} \mathcal{I}_f(A;Q|P) + \lambda g(A)
|
|
\end{equation*}
|
|
|
|
Dato che $\mathcal{I}_f(A;Q|P) = \mathcal{I}_f(A;Q) - \mathcal{I}_f(A;Q;P)$, per massimizzare la funzione contemporaneamente si massimizza l'informazione mutua fra $A$ e $Q$, cioè si trova un insieme $A$ simile a $Q$, e si minimizza l'informazione mutua fra $A$ e $P$ attraverso $\mathcal{I}_f(A;Q;P)$, dato che $A$ e $Q$ saranno già simili dato il primo termine.
|
|
|
|
Si osserva che nel caso $Q = V$ si massimizza $f(A|P) + \lambda g(A)$, nel caso $P = \emptyset$ si massimizza $ \mathcal{I}_f(A;Q) +\lambda g(A) $, nel caso $Q = V, P = \emptyset$ si massimizza $f(A) + \lambda g(A)$.
|
|
|
|
Questa formulazione del problema ammette una approssimazione di $1-\frac{1}{e}$ per tutte le funzioni monotone submodulari con terza derivata parziale non negativa, cioè $f^{(3)}(i,j,k;A) = f^{(2)}(j,k;A \cup i) - f^{(2)}(j,k;A) \ge 0 $.
|
|
|
|
|
|
\subsection{Clustering and Partitioning using the Multi-Set Mutual Information}
|
|
|
|
Attraverso l'informazione mutua si possono risolvere sia problemi di ``clustering'' che di partizionamento.
|
|
|
|
\textit{``Clustering''}
|
|
|
|
Usando la correlazione totale si ottiene un problema di partizionamento submodulare noto:
|
|
\[ \min\limits_{A_1, \ldots,A_k \textnormal{ tali che } \cup_{i=1}^{k} A_i=V \wedge (\forall i,j: A_i \cap A_j = \emptyset)}C_f(A_1,\ldots, A_k) \]
|
|
Infatti è equivalente a minimizzare $\sum_{i=1}^{k}f(A_i) - f(\bigcup_{i=1}^{k} A_i)= \sum_{i=1}^{k}f(A_i) - f(V)$. Dato che $f(V)$ è costante, il problema risulta un ``submodular multiway partition problem''.
|
|
|
|
\begin{definizione}[``submodular multiway partition problem'']\cite{submultiwaypartition2011}
|
|
Dato un inisieme $V$, un insieme $S = {s_1,\ldots, s_k} \subset V$ di cardinalità $k$ e una funzione $f: \mathcal{P}(V) \to \mathbb{R}^+$ submodulare non negativa, si suddivida $V$ in $k$ insiemi $A_1, \ldots, A_k$ tali che per $1 \le i \le k, s_i \in A_i$ e $\sum_{i=1}^k f(A_i)$ è minima.
|
|
\end{definizione}
|
|
|
|
\textit{``Diverse partitioning''}
|
|
|
|
Partendo dalla correlazione totale:
|
|
\begin{equation*}
|
|
\min\limits_{A_1, \ldots,A_k \textnormal{ tali che } \cup_{i=1}^{k} A_i=V \wedge (\forall i,j: A_i \cap A_j = \emptyset)}C_f(A_1,\ldots, A_k)
|
|
\end{equation*}
|
|
Risulta equivalente a:
|
|
\begin{equation*}
|
|
\begin{aligned}
|
|
&\max\sum_{i=1}^{k}f(A_i)-f(\bigcup_{i=1}^{k}A_i)\\
|
|
= &\max\sum_{i=1}^{k}f(A_i)-f(V)\\
|
|
\end{aligned}
|
|
\end{equation*}
|
|
|
|
Il problema quindi è equivalente al ``submodular welfare problem'', in cui le funzioni obiettivo però differiscono di una costante uguale a $f(V)$.
|
|
|
|
|
|
\subsection{Minimization of Submodular Information Metric}
|
|
Si vuole trovare il sottoinsieme $A\in \mathcal{P}(V)$ in modo che abbia distanza minima da $S_1, S_2, \ldots, S_m$:
|
|
\[ \min\limits_{A \subseteq V} \sum_{i=1}^m D_f(A,S_i) \]
|
|
Il problema è molto simile a trovare un insieme rappresentativo con una metrica submodulare di hamming dato che è un'approssimazione valida di $D_f(A,S)$.
|
|
In particolare la metrica submodulare di hamming è $D^{\textnormal{SHA}}(A,S)=f(A\setminus S) + f(S\setminus A)$ che è submodulare in $A$ per $S$ fissato.
|
|
Quindi è possibile ottenere una soluzione esatta in tempo polinomiale\cite{generalizedsubmodular2022}.
|
|
Inoltre si ha una garanzia di $1-\kappa_f$ sulla soluzione trovata, dove $\kappa_f$ è la curvatura di $f$.
|