612 lines
36 KiB
TeX
612 lines
36 KiB
TeX
\section{Verso la definizione sublineare dell'entropia}
|
|
\subsection{Matroidi}\label{matroidi}
|
|
|
|
La teoria dei matroidi\cite{lawler2004} fu fondata da Hassler Whitney nel 1935 nella pubblicazione ``\textsc{On the Abstract Properties of Linear Dependence}''\cite{whitney1935} grazie ad uno studio sulla teoria algebrica della dipendenza lineare.
|
|
|
|
|
|
Data una matrice le colonne sono o linearmente dipendenti fra loro oppure linearmente indipendenti.
|
|
Whitney fa notare che esistono solo queste due classi, ma che non sono arbitrarie. Per esempio un sottoinsieme di colonne linearmente indipendenti è indipendente. Oppure se $I_p$ e $I_{p+1}$ sono insiemi di colonne linearmente indipendenti con rispettivamente $p$ e $p+1$ elementi allora, esiste una colonna $i\in I_{p+1}$ tale che $i\cup I_{p}$ è indipendente.\medskip
|
|
|
|
\begin{definizione}\cite{lawler2004} Un \textsc{matroide} $M = (E, \mathscr{I})$ è una struttura in cui $E$ è un insieme finito di elementi e $\mathscr{I}\subset \mathcal{P}(E)$, tale che:
|
|
|
|
\begin{itemize}
|
|
\item $\emptyset \in \mathscr{I}$ e $\forall i\subset I \in \mathscr{I}$, $i \in \mathscr{I}$
|
|
\item se $ I_p $ e $ I_{p+1} $ sottoinsiemi di $\mathscr{I}$, che contengono rispettivamente $p$ e $p+1$ elementi, allora $\exists i\in I_{p+1} - I_{p}$ tale che $ I_p \cup i \in \mathscr{I} $
|
|
\end{itemize}
|
|
\end{definizione}
|
|
|
|
|
|
$\mathcal{P}(E)$ si riferisce all'insieme delle parti di $E$.
|
|
|
|
Si consideri la matrice $A$:
|
|
\begin{equation*}
|
|
A =
|
|
\begin{+bmatrix}
|
|
a_{11} & \cdots & a_{1n}\\
|
|
\vdots & \ddots & \vdots\\
|
|
a_{m1} & \cdots & a_{mn}
|
|
\end{+bmatrix}
|
|
\end{equation*}
|
|
|
|
e siano le sue colonne $C_1, \ldots, C_n$. Ogni sottoinsieme $N$ di queste colonne è una matrice; se si considerano le colonne come elementi astratti si ottiene un matroide $M$.
|
|
|
|
Tuttavia non tutti i matroidi si possono esprimere come matrici\cite{whitney1935}.
|
|
|
|
La definizione di indipendenza è quindi relativa all'appartenenza all'insieme $\mathscr{I}$, non ad una proprietà intrinseca degli elementi.
|
|
|
|
\subsection{Politopi e Poliedri}\label{politopiepoliedri}
|
|
\begin{small}
|
|
\vspace{-0.8em}
|
|
\hspace{5em}\textit{tratto da }\cite{ziegler2007}
|
|
\end{small}
|
|
|
|
\begin{definizione}
|
|
Un $\mathcal{V}$-\textsc{politopo} è l'inviluppo convesso di un insieme finito di punti in $\mathbb{R}^d$.
|
|
\end{definizione}
|
|
|
|
L'inviluppo convesso di un insieme $K$ di punti è definito come:
|
|
\[ \text{conv}(K) = \{\lambda_1 \textbf{x}_1 + \ldots + \lambda_k \textbf{x}_k : \{\textbf{x}_1,\ldots,\textbf{x}_k \}\subseteq K, \lambda_i\geq0, \sum_{i=1}^k \lambda_i = 1 \} \]% chktex 11
|
|
|
|
\begin{definizione}
|
|
Un $\mathcal{H}$-poliedro è l'intersezione di un numero finito di semispazi chiusi in $\mathbb{R}^d$.
|
|
\end{definizione}
|
|
|
|
A differenza di un politopo, un $\mathcal{H}$-\textsc{poliedro} non è limitato nel piano.
|
|
|
|
Un $\mathcal{H}$-\textsc{politopo} è un $\mathcal{H}$-poliedro ``finito'', in particolare che non contiene semirette $\{\textbf{x}+t \textbf{y}:t>0\}$ per ogni $\textbf{y}\ne \textbf{0}$.
|
|
|
|
Un \textsc{politopo} è un insieme di punti $P\subseteq\mathbb{R}^d$ che può essere sia un $\mathcal{V}$-politopo o un $\mathcal{H}$-politopo.
|
|
|
|
\begin{figure}[htbp]
|
|
\centering\label{points}
|
|
\def\svgwidth{.6\textwidth}
|
|
\subimport{figures}{politopi.pdf_tex}
|
|
\caption{$\mathcal{V}$-politopo e $\mathcal{H}$-politopo}
|
|
\end{figure}
|
|
|
|
|
|
La dimensione di un politopo è la dimensione del suo inviluppo affine.
|
|
|
|
In particolare i politopi che hanno dimensione 0 sono i punti, quelli che hanno dimensione 1 sono i segmenti di linea.
|
|
|
|
\begin{definizione}
|
|
Un $\mathcal{H}$-\textsc{poliedro} $P\subseteq\mathbb{R}^d$ è definito come l'intersezione di semispazi:
|
|
\[ P = P(A, \textbf{z}) = \{ \textbf{x}\in\mathbb{R}^d : A \textbf{x} \le \textbf{z} \}\quad \text{ per qualche } A\in\mathbb{R}^{m\times d}, \textbf{z}\in\mathbb{R}^m \]
|
|
\end{definizione}
|
|
|
|
Si definisce quindi il cono di un insieme di punti $Y$ come:
|
|
\[ \text{cono}(Y) = \{ \lambda_1 \textbf{y}_1 + \ldots + \lambda_k \textbf{y}_k : \{\textbf{y}_1,\ldots,\textbf{y}_k\}\subseteq Y, \lambda_i \ge 0\} \]% chktex 11
|
|
Nel caso in cui $Y\subseteq\mathbb{R}^d$ si riduce a:
|
|
\[ \text{cono}(Y) \coloneq \{Y \textbf{t} : \textbf{t}\ge0\} \]
|
|
|
|
Se $Y = \emptyset$ allora $\text{cono}(Y)=\{\textbf{0}\}$
|
|
|
|
Si definisce la somma di Minkowski di due insiemi $P, Q \subseteq \mathbb{R}^d$ come:
|
|
\[ P + Q \coloneq \{ \textbf{x}+\textbf{y}:\textbf{x}\in P, \textbf{y}\in Q \} \]
|
|
|
|
\begin{definizione}
|
|
Un $\mathcal{V}$-\textsc{poliedro} $P$:
|
|
\[ P = \text{conv}(V) + \text{cono}(Y)\hspace{2em}\text{ per qualche } V\in \mathbb{R}^{d\times n}, Y\in \mathbb{R}^{d\times n'} \]
|
|
\end{definizione}
|
|
|
|
\begin{teorema}
|
|
Un insieme $P\in\mathbb{R}^d$ è un $\mathcal{V}$-poliedro:
|
|
\begin{align}
|
|
P = \text{conv}(V) + \text{cono}(Y)\hspace{2em}&\text{per qualche } V\in \mathbb{R}^{d\times n}, Y\in \mathbb{R}^{d\times n'} \notag
|
|
\shortintertext{se e solo se è un $\mathcal{H}$-poliedro:}
|
|
P=P(A, \textbf{z})\hspace{2em}&\text{per qualche } A\in \mathbb{R}^{m\times d}, \textbf{z}\in \mathbb{R}^{m} \notag
|
|
\end{align}
|
|
\end{teorema}
|
|
|
|
\subsection{Funzioni Submodulari e Polimatroidi}\label{polimatroidi}
|
|
Dato un insieme S, sia $f$ una funzione definita su $\mathcal{P}(S)$. $f$ è chiamata submodulare se\cite{schrijver2003}:
|
|
\[ f(T) + f(U) \ge f(T \cap U) + f(T \cup U) \quad \text{ per ogni } T,U \subset S \]
|
|
|
|
$f$ è chiamata supermodulare se $-f$ è submodulare. $f$ è modulare se $f$ è sia submodulare che supermodulare.
|
|
|
|
Una funzione $f$ su $\mathcal{P}(S)$ è chiamata non decrescente se $f(T) \le f(U)$ per qualsiasi $T \subseteq U \subseteq S$, e non crescente se $f(T) \ge f(U)$ per qualsiasi $T \subseteq U \subseteq S$. Se $f(\emptyset)=0$ allora $f$ si chiama normalizzata.
|
|
|
|
Ogni funzione modulare $f$ su $\mathcal{P}(S)$ soddisfa $f(U) = \omega(U) + \gamma$ per $U \subseteq S$, per $\gamma \in \mathbb{R}$ unico e per una funzione $\omega: S \to \mathbb{R} $ univoca tale che $\omega(U) \coloneq \sum\nolimits_{s \in U} \omega(s)$.
|
|
|
|
La submodularità è quindi l'analogo discreto della convessità.
|
|
|
|
\begin{definizione}\cite{schrijver2003} Si definiscono due poliedri associati ad una funzione $f$ su $\mathcal{P}(S)$:
|
|
\begin{equation*}
|
|
\label{Poliedri associati a $f$}
|
|
\begin{aligned}
|
|
P_f &\coloneq \{x \in \mathbb{R}^S : x \ge \textbf{0},&x(U) \le f(U), \forall U \subseteq S \}\\
|
|
EP_f &\coloneq \{x \in \mathbb{R}^S :&x(U) \le f(U), \forall U \subseteq S \}
|
|
\end{aligned}
|
|
\end{equation*}
|
|
|
|
$P_f$ è chiamato il polimatroide associato a $f$, $EP_f$ è chiamato il polimatroide esteso associato a $f$.
|
|
\end{definizione}
|
|
|
|
Si osserva che $P_f \ne \emptyset \Leftrightarrow f \ge \textbf{0}$ e che $ EP_f \ne \emptyset \Leftrightarrow f(\emptyset) \ge 0$. Un poliedro è chiamato polimatroide (esteso) se è il polimatroide (esteso) associato ad una funzione submodulare. Un polimatroide è limitato dato che $ \forall s \in S, 0 \le x_s \le f(\{s\})$ e quindi è un politopo.
|
|
|
|
Un'altra caratterizzazione delle funzioni submodulari è attraverso la definizione di derivata parziale di primo ordine\cite{generalizedsubmodular2022} o \textit{diminishing marginal returns}\cite{fujishige2005}:
|
|
\[ \forall T \subseteq V, j \notin V f(j|T) \ge f(j|V) \]
|
|
|
|
Se si definisce anche la derivata parziale di secondo ordine, si può avere un'altra caratterizzazione delle funzioni submodulari\cite{generalizedsubmodular2022}:
|
|
\begin{equation*}
|
|
\begin{aligned}
|
|
f^{(2)}(j,k;T) \coloneq &f(j|T \cup \{k\}) - f(j|T)\\
|
|
= &f(T \cup \{k\} \cup \{j\}) + f(T) - f(T \cup \{k\}) - f(T \cup \{j\})
|
|
\end{aligned}
|
|
\end{equation*}
|
|
con $T \subseteq V \setminus \{j,k\}$.
|
|
Una funzione $f$ è submodulare se le derivate parziali di secondo ordine rispetto a un insieme $T$ sono sempre negative, cioè:
|
|
\[ \forall\ T, \forall j,k \notin T \text{ si ha che } f^{(2)}(j, k; T) \le 0 \]
|
|
|
|
Si può anche definire la derivata parziale di terzo ordine:
|
|
\begin{center}
|
|
\begin{tblr}{colspec={Q[l,m]Q[r,m]Q[l,m]}}
|
|
$f^{(3)}(i,j,k;A) $ & $\coloneq$ &$f^{(2)}(j,k;A\cup \{i\})-f^{(2)}(j,k;A)$\\
|
|
& $=$ &$f(A\cup\{i\}\cup\{j\}\cup\{k\})-f(A\cup\{i\}\cup\{j\}) +$\\
|
|
& \SetCell[c=2]{r} $-f(A\cup\{i\}\cup\{k\})-f(A\cup\{i\}\cup\{j\})+$ \\
|
|
& \SetCell[c=2]{r} $+f(A\cup\{i\})+f(A\cup\{j\})+f(A\cup\{k\})+$\\
|
|
& \SetCell[c=2]{r} $-f(A)$
|
|
\end{tblr}
|
|
\end{center}
|
|
Sarà necessaria per definire quando l'informazione mutua sia submodulare.
|
|
|
|
\subsection{Entropia e Funzioni polimatroidi}\label{funzionipolimatroidi}
|
|
\begin{small}
|
|
\vspace{-0.8em}
|
|
\hspace{5em}\textit{tratto da }\cite{generalizedsubmodular2022}
|
|
\end{small}
|
|
|
|
\begin{definizione}
|
|
Una funzione $f$ si chiama funzione polimatroide se è monotona, non negativa, non decrescente e submodulare.
|
|
\end{definizione}
|
|
In generale funzioni polimatroidi possono essere viste come funzioni d'informazione $ \mathcal{I}_f(A) = f(A) $ dato che soddisfano tutte le disuguaglianze di Shannon\cite{shannon1948}:
|
|
|
|
\begin{itemize}
|
|
\item $f(A)$ è normalizzata, cioè $f(\emptyset) = 0$
|
|
\item $f(A)$ è monotona non decrescente, cioè per $A \subseteq B \subseteq S$ allora $f(B) \ge f(A)$
|
|
\item $f(A)$ è submodulare, cioè $f(A) + f(B) \geq f(A \cup B) + f(A \cap B), \forall A, B \subset V$
|
|
\end{itemize}
|
|
|
|
L'insieme di funzioni che soddifano queste tre proprietà vengono chiamate funzioni polimatroidi dato che esiste un isomorfismo tra questa classe di funzioni e la classe dei polimatroidi prima definiti.
|
|
|
|
\begin{teorema}
|
|
La classe delle funzioni polimatroidi è strettamente più generale della classe delle funzioni entropiche.
|
|
\end{teorema}
|
|
|
|
Sia $\Gamma^S_n$ la classe di tutte le funzioni sull'insieme V, con $|V| = n$, che soddisfano le disuguaglianze di Shannon.
|
|
Una funzione $f$ è costruibile se esiste un insieme di $n$ variabili aleatorie indicizzate su $V$, tali che l'entropia di ogni sottoinsieme di queste variabili sia uguale a $f$ applicato al corrispondente sottoinsieme di $V$.
|
|
Sia $\Gamma^H_n$ la classe di funzioni \textit{costruibili} sull'insieme $|V| = n$, cioè tutte le funzioni entropiche su sottoinsiemi di $n$ variabili aleatorie.
|
|
Sia $cl(\Gamma^H_n)$ la chiusura di $\Gamma^H_n$; in particolare $\Gamma^H_n \ne cl(\Gamma^H_n)$ per $n \ge 3$.
|
|
|
|
Il teorema può essere espresso quindi come $\Gamma^S_n \supset cl(\Gamma^H_n)$ e $\Gamma^S_n \supset \Gamma^H_n$ per $n\geq4$.
|
|
In particolare si ha $\Gamma^H_2 = \Gamma^S_2$ e $\Gamma^H_3 \ne cl(\Gamma^H_3) = \Gamma^S_3$.
|
|
|
|
Si osserva che $\Gamma^S_n$ è un cono convesso, dato che se $f_1$ e $f_2$ sono funzioni polimatroidi allora $\lambda_1 f_1 + \lambda_2 f_2$ è una funzione polimatroide se $\lambda_1,\lambda_2\ge0$ e dato che la funzione costante $f(A) = 0, \forall A$ appartiene a $\Gamma^S_n$.
|
|
|
|
In modo simile all'entropia, si vuole quindi caratterizzare la quantità di informazione che si aggiunge dall'insieme $A$ dato l'insieme $B$:
|
|
\begin{definizione}
|
|
Data una funzione $f: \mathcal{P}(V) \to \mathbb{R}$ sia $ f(A|B) \coloneq f(A\cup B) - f(B) $ il ``conditional gain''.
|
|
\end{definizione}
|
|
|
|
Si osserva che:
|
|
|
|
\begin{tblr}{colspec={Q[l,m]Q[l,m]}, column{2} = {leftsep = 0em, wd=15em}}
|
|
$f(A|B) \ge 0 $ & se $f$ è monotona \\
|
|
$f(A|B) \le f(A) $ & se $ f $ è subadditiva \\
|
|
\SetCell[c=2]{r} {\small \textit{(``conditioning reduces valuation'')}} \\
|
|
$ f(A|B\cup C) \le f(A|B) $ con $ C\neq \emptyset $ & se $ f $ è submodulare \\
|
|
\SetCell[c=2]{r} {\small \textit{(``further conditioning reduces valuation'')}}\\
|
|
$f(A|B)$ è submodulare in $A$ dato $B$ & se $ f $ è submodulare
|
|
\end{tblr}
|
|
|
|
Inoltre:
|
|
\[ f(A|B)=0 \Longleftrightarrow f(j|B)=0, \forall j \in A \]
|
|
cioè ogni elemento di $A$ non ha informazione aggiuntiva rispetto a $B$.
|
|
Data una funzione submodulare $g(A) = \lambda_1 f_1(A)+ \lambda_2 f_2(A)$, allora $ g(A|B) = \lambda_1 f_1(A|B) + \lambda_2 f_2(A|B) $.
|
|
|
|
Un limite rilevante per qualsiasi funzione $f$ polimatroide è il seguente:
|
|
\[ f(\cup_i A_i) = \mathcal{I}_f(\cup_i A_i) \le \sum_i f(A_i) = \sum_i \mathcal{I}_f(A_i) \]
|
|
|
|
In particolare si ha uguaglianza quando tutti gli insiemi $A_i$ sono indipendenti.
|
|
|
|
Un'altra proprietà rilevante è la seguente:
|
|
$\mathcal{I}_f(A) = 0 \Leftrightarrow f(j)=0, \forall j \in A$, cioè che si ha informazione nulla soltanto se ogni elemento dell'insieme ha informazione nulla.
|
|
|
|
Nel caso dell'entropia la formula è equivalente a: $H(X) = 0 \Leftrightarrow X$ è costante.
|
|
In generale quando $\mathcal{I}_f(A)=0$ vuole dire che ogni variabile $j\in A$ può essere ignorata, dato che non ha informazione.
|
|
|
|
\begin{definizione}
|
|
Dati due insiemi $A$ e $B$, l'informazione mutua fra i due insiemi è:
|
|
$\mathcal{I}_f(A;B) \coloneq f(A) + f(B) - f(A \cup B)$
|
|
\end{definizione}
|
|
|
|
Come per l'entropia di Shannon si ha simmetria rispetto agli insiemi:
|
|
\begin{equation*}
|
|
\mathcal{I}_f(A;B) = f(A) - f(A|B) = f(B) - f(B|A)
|
|
\end{equation*}
|
|
|
|
Dalla definizione di $\mathcal{I}_f(A;B)$ seguono le proprietà:
|
|
|
|
\begin{center}
|
|
\begin{tblr}{Q[r,m]Q[l,m]X[1,l]}
|
|
$\bullet$& $ \mathcal{I}_f(A;B) = \mathcal{I}_f(B;A) $ & \\
|
|
$\bullet$& $ \mathcal{I}_f(A;A) = f(A) $ & \\
|
|
$\bullet$& $ \mathcal{I}_g(A;B) = \lambda_1 \mathcal{I}_{f_1}(A;B) + \lambda_2 \mathcal{I}_{f_2}(A;B) $ &se $g(A) = \lambda_1 f_1(A) + \lambda_2 f_2(A)$ \\
|
|
$\bullet$& $ \mathcal{I}_f(A;B) = c $ &se $\forall A, f(A) = c $ \\
|
|
$\bullet$& $ \mathcal{I}_f(A;\emptyset) = 0 $ \\
|
|
$\bullet$& $ \mathcal{I}_f(A;V) = f(A) $ \\
|
|
$\bullet$& $ \mathcal{I}_f(A;B) \ge 0 $ &se $f$ è submodulare \\
|
|
$\bullet$& \SetCell[c=2]{l}
|
|
\begin{tblr}{colspec={Q[l,m]Q[l,m]}, column{1} = {leftsep = 0em}}
|
|
$\min(f(A),f(B)) \ge \mathcal{I}_f(A;B) \ge f(A \cap B) $ & {se $f$ è non \\ negativa \\ submodulare}
|
|
\end{tblr} \\
|
|
$\bullet$& $\mathcal{I}_f(A;B) $ è monotona in $A$ & per $B$ fisso \\
|
|
$\bullet$& \SetCell[c=2]{l}
|
|
\begin{tblr}{colspec={Q[l,m]Q[c,m]Q[r,m]}, column{1} = {leftsep = 0em}}
|
|
{$ \mathcal{I}_f(A;B) $ è submodulare in $A$ \\con $B$ fisso } &$\iff$ &{$f^{(2)}(j,k;A)$ è monotona non\\ decrescente in $A \subseteq V \setminus \{j,k\}$}
|
|
\end{tblr} \\
|
|
$\bullet$& \SetCell[c=2]{l}
|
|
\begin{tblr}{colspec={Q[l,m]Q[c,m]Q[c,m]}, column{1} = {leftsep = 0em}}
|
|
{$ \mathcal{I}_f(A;B) $ è submodulare in $A$ \\con $B$ fisso} &$\iff$ &$f^{(3)}(i,j,k;A) \geq 0$
|
|
\end{tblr}
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
Si può definire anche la ``submodular conditional mutual information'' degli insiemi $A$ e $B$ dato l'insieme $C$:
|
|
\begin{definizione}
|
|
Dati tre insiemi $A, B$ e $C$, sia:
|
|
\begin{align*}
|
|
\mathcal{I}_f(A;B|C)\coloneq &f(A|C)+f(B|C)-f(A \cup B|C) \\
|
|
= &f(A\cup C) + f(B \cup C) -f(A \cup B \cup C)- f(C)
|
|
\end{align*}
|
|
la ``submodular conditional mutual information''.
|
|
\end{definizione}
|
|
|
|
Seguono alcune proprietà:
|
|
\begin{center}
|
|
\begin{tblr}{Q[l,m]Q[l,m]X[1,l]}
|
|
$\bullet$& $ \mathcal{I}_f(A;B|C) = f(A|C) $ &se $ A \subseteq B $ \\
|
|
$\bullet$& $ \mathcal{I}_f(A;\emptyset|C) = 0 $ & \\
|
|
$\bullet$& $ \mathcal{I}_f(A;B|C) \ge 0 $ &se $f$ è non negativa submodulare \\
|
|
$\bullet$& \SetCell[c=2]{l} $ \min(f(A|C),f(B|C)) \ge \mathcal{I}_f(A;B|C) \ge f(A \cap B|C) $ \\
|
|
& & se $f$ è non negativa submodulare \\
|
|
$\bullet$& $ \mathcal{I}_f(A;B|C) $ è monotona in A &per $B$ e $C$ fissi \\
|
|
$\bullet$& \SetCell[c=2]{l}
|
|
\begin{tblr}{colspec={Q[l,m]Q[c,m]Q[r,m]}, column{1} = {leftsep = 0em}}
|
|
{$ \mathcal{I}_f(A;B|C) $ è submodulare in $A$ \\con $B$ e $C$ fissi} &$\iff$ &{$f^{(2)}(j,k;A)$ è monotona non\\ decrescente in $A \subseteq V \setminus \{j,k\}$}
|
|
\end{tblr} \\
|
|
$\bullet$& \SetCell[c=2]{l}
|
|
\begin{tblr}{colspec={Q[l,m]Q[c,m]Q[c,m]}, column{1} = {leftsep = 0em}}
|
|
{$ \mathcal{I}_f(A;B|C) $ è submodulare in $A$ \\con $B$ e $C$ fissi} &$\iff$ &$f^{(3)}(i,j,k;A) \geq 0$
|
|
\end{tblr}
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
Di particolare importanza è la submodularità di $ \mathcal{I}_f(A;B) $ e $ \mathcal{I}_f(A;B|C) $ rispetto a $f$.
|
|
Segue quindi la dimostrazione della monotonicità di $\mathcal{I}_f(A;B)$ per $B$ fisso, poi l'equivalenza della monotonia di $f^{(2)}$ alla positività di $f^{(3)}$ e infine l'equivalenza fra la submodularità di $\mathcal{I}_f(A;B)$ e la monotonia di $f^{(2)}$.
|
|
Si osserva infine che le dimostrazioni valgono anche per $ \mathcal{I}_f(A;B|C) $.
|
|
\begin{dimostrazione}[$\mathcal{I}_f(A;B)$ è monotona per $B$ fisso]
|
|
Sia $g(A) = \mathcal{I}_f(A;B)$ con $B$ fisso e $f$ submodulare. Si consideri quindi il guadagno dall'aggiungere un elemento $j\notin A\cup B$ ad $A$: $g(j|A) = g(\{j\}\cup A)-g(A) = f(\{j\}\cup A)+f(B)-f(\{j\}\cup A \cup B) -\left(f(A)+f(B)-f(A \cup B)\right) = f(\{j\}\cup A) - f(A) - \left( f(\{j\}\cup A \cup B) -f(A \cup B) \right) = f(j|A)-f(j|A\cup B)$.
|
|
Dato che $f$ è submodulare si ha $f(j|A)\ge f(j|A \cup B) \implies g(j|A) \ge 0$.
|
|
\end{dimostrazione}
|
|
\begin{dimostrazione}[$f^{(2)}$ è monotona non decrescente se e solo se $f^{(3)}$ è sempre positiva]
|
|
Dalla definizione di $f^{(3)}(i,j,k;A) = f^{(2)}(j,k;A \cup i) - f^{(2)}(j,k;A)$ segue che $ f^{(3)}(i,j,k;A)\ge 0 \implies f^{(2)}(j,k;A \cup i) \ge f^{(2)}(j,k;A) $.
|
|
Per induzione si ha $\forall A,C \subseteq V, f^{(2)}(j,k;A\cup C) \ge f^{(2)}(j,k;A)$.
|
|
Cioè $\forall A,B \subseteq V, A \subseteq B, f^{(2)}(j,k;B) \ge f^{(2)}(j,k;A)$.
|
|
\end{dimostrazione}
|
|
\begin{dimostrazione}[$\mathcal{I}_f(A;B)$ è submodulare se e solo se $f^{(2)}$ è monotona non decrescente]
|
|
Sia $g(A) = \mathcal{I}_f(A;B)$ con $B$ fisso. In particolare $g(j|A) = f(j|A) - f(j| A \cup B)$ dalla dimostrazione precedente. Per monotonicità di $f^{(2)}$ si ha $\forall j,k \notin A$:
|
|
\begin{center}
|
|
\begin{tblr}{colspec={Q[l,m]Q[r,m]X[1,l]},rows = {abovesep=0pt,belowsep=0pt}}
|
|
& $ f^{(2)}(j,k;A) $ &$\le f^{(2)}(j,k;A \cup B)$ \\
|
|
$\implies$ & $ f(j|A \cup \{k\}) - f(j|A) $ &$\le f(j|A\cup B \cup \{k\}) - f(j|A \cup B)$ \\
|
|
$\implies$ & $f(j|A \cup k) - f(j|A\cup B\cup \{k\})$ &$\le f(j|A) - f(j|A \cup B)$ \\
|
|
$\implies$ & $g(j|A \cup \{k\})$ &$\le g(j|A)$ \\
|
|
\end{tblr}
|
|
\end{center}
|
|
Per induzione si ha che $g(j|C) \le g(j|A)$ per $\forall C \supseteq A$, cioè $g$ è submodulare.
|
|
Per dimostrare l'inverso si assume che $\mathcal{I}_f(A;B)$ sia submodulare in $A$, ma che $f^{(2)}(j,k;A)$ non sia necessariamente monotona.
|
|
Cioè $\exists A,C$ con $A \cap C = \emptyset$ tali che $f^{(2)}(j,k;A)\ge f^{(2)}(j,k;A\cup C)$.
|
|
Sia $h(A) = \mathcal{I}_f(A;C)$. Seguendo la catena di disuguaglianze precedente si ottiene che $h(j|A\cup \{k\})\ge h(j|A)$, che contraddice la submodularità di $\mathcal{I}_f(A;C)$ per qualsiasi insieme $C$ fisso.
|
|
\end{dimostrazione}
|
|
Dato che $\mathcal{I}_f(A;B|C) = f(A|C) + f(B|C) - f(A\cup B|C) = g(A)+g(B)-g(A\cup B) = \mathcal{I}_g(A;B)$, allora le dimostrazioni sopra valgono anche per il caso della ``submodular conditional mutual information'', poichè $f^{(3)}(i,j,k;A)\ge0, \forall A \subseteq V \implies f^{(3)}(i,j,k;A\cup C)\ge 0,\forall A \subseteq V \implies g^{(3)}(i,j,k;A) \ge 0$.
|
|
|
|
|
|
La definizione dell'informazione mutua si può estendere anche a più di due insiemi:
|
|
\begin{definizione}[``submodular multi-set mutual information'']
|
|
\[ \mathcal{I}_f(A_1;A_2;\ldots;A_k) \coloneq - \sum_{T \subseteq \{1,\ldots,k\}}{(-1)}^{\norm{T}}f(\bigcup\limits_{i \in T}A_i) \]
|
|
\end{definizione}
|
|
Nello stesso modo si può estendere ``submodular conditional mutual information'':
|
|
\begin{definizione}[``submodular conditional k-set mutual information'']
|
|
\[ \mathcal{I}_f(A_1;A_2;\ldots;A_k|C) \coloneq - \sum_{T\subseteq \{1,\ldots,k\}}{(-1)}^{\norm{T}}f(\bigcup\limits_{i\in T}A_i|C) \]
|
|
\end{definizione}
|
|
|
|
Si osserva che nel caso in cui $k=2$ le definizioni coincidono con quelle prima presentate.
|
|
|
|
|
|
\begin{definizione}[``Submodular total correlation'']
|
|
\begin{equation*}
|
|
C_f(A_1;A_2; \ldots; A_k) \coloneq \left( \sum_{i=1}^{k}f(A_i) \right) - f(\cup_{i=1}^k A_i)
|
|
\end{equation*}
|
|
\end{definizione}
|
|
|
|
\begin{definizione}[``Submodular conditional total correlation'']
|
|
\begin{equation*}
|
|
C_f(A_1; A_2;\ldots; A_k|C) \coloneq \left( \sum_{i=1}^{k}f(A_i|C) \right) - f(\cup_{i=1}^k A_i | C)
|
|
\end{equation*}
|
|
\end{definizione}
|
|
|
|
Si osserva che per $k=2$ le definizioni corrispondono a quelle della ``submodular mutual information'' e ``submodular conditional mutual information'' rispettivamente.
|
|
|
|
|
|
Seguono alcune proprietà di $\mathcal{I}_f(A_1;A_2;\ldots;A_k)$ e di $C_f(A_1;A_2; \ldots; A_k)$:
|
|
|
|
\begin{center}
|
|
\begin{tblr}{Q[l,m]Q[l,m]Q[l,m]}
|
|
$\bullet$&\SetCell[c=2]{l} $ \mathcal{I}_g(A_1;A_2; \ldots; A_k) = \lambda_1 \mathcal{I}_{f_1}(A_1;A_2; \ldots; A_k) + \lambda_2 \mathcal{I}_{f_2}(A_1;A_2; \ldots; A_k) $ \\
|
|
\SetCell[c=3]{r} se $g(A) = \lambda_1 f_1(A) + \lambda_2 f_2(A)$ \\
|
|
|
|
$\bullet$&\SetCell[c=2]{l} $ C_g(A_1;A_2; \ldots; A_k) = \lambda_1 C_{f_1}(A_1;A_2; \ldots; A_k) + \lambda_2 C_{f_2}(A_1;A_2; \ldots; A_k) $ \\
|
|
\SetCell[c=3]{r} se $g(A) = \lambda_1 f_1(A) + \lambda_2 f_2(A)$ \\
|
|
|
|
$\bullet$& $ \mathcal{I}_g(A_1;A_2; \ldots; A_k) = c $ &se $g(A) = c, \forall A \neq \emptyset$ e $g(\emptyset) = 0$ \\
|
|
$\bullet$& $ C_g(A_1;A_2; \ldots; A_k) = (k-1)\cdot c $ &se $g(A) = c, \forall A \neq \emptyset$ e $g(\emptyset) = 0$ \\
|
|
$\bullet$&\SetCell[c=2]{l} $ \mathcal{I}_f(A_1;\ldots;A_k;A_{k+1}) = \mathcal{I}_f(A_1; \ldots; A_k) - \mathcal{I}_f(A_1; \ldots;A_k| A_{k+1}) $ \\
|
|
$\bullet$&\SetCell[c=2]{l} $ \mathcal{I}_f(A_1;\ldots;A_k|A_{k+1}) = \mathcal{I}_f(A_1 \cup A_{k+1};\ldots;A_k \cup A_{k+1}) - f(A_{k+1}) $ \\
|
|
|
|
$\bullet$& $ C_f(A_1;A_2; \ldots; A_k) \le \sum_{i=1}^{k}f(A_i) $ &se $f$ e una funzione polimatroide \\
|
|
$\bullet$& \SetCell[c=2]{l} $ \mathcal{I}_f(A_1;A_2; \ldots; A_k) \le \min(f(A_1), \ldots, f(A_k)) $ \\
|
|
\SetCell[c=3]{r} se $f$ appratiene alla classe delle funzioni ``facility location'' o ``set cover'' \\
|
|
|
|
$\bullet$& $ \mathcal{I}_f(A_1; \ldots; A_k;\emptyset) = 0 $ &se $f$ è una funzione normalizzata e \\
|
|
\SetCell[c=3]{r} submodulare \\
|
|
$\bullet$& $ C_f(A_1; \ldots; A_k;\emptyset) = C_f(A_1; \ldots; A_k) $ &se $f$ è una funzione normalizzata e \\
|
|
\SetCell[c=3]{r} submodulare \\
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
|
|
|
|
Per esprimere la ``distanza'' fra due insiemi $A$ e $B$ si definisce la ``submodular variation of information'':
|
|
\begin{definizione}
|
|
Dati gli insiemi $A$ e $B$ sia
|
|
\begin{align*}
|
|
D_f(A;B) \coloneq &f(A\cup B) - \mathcal{I}_f(A;B) \\
|
|
= &f(A|B) - f(B|A)
|
|
\end{align*}
|
|
la ``submodular variation of information''.
|
|
\end{definizione}
|
|
Si nota che non è una metrica in generale, ma solo una pseudo-metrica.
|
|
\begin{definizione}\cite{steenseebach1979}
|
|
Data una funzione $d: X \times X \to \mathbb{R}$ è una metrica se:
|
|
\begin{align*}
|
|
&d(x_1, x_2) \ge 0 \\
|
|
&d(x_1,x_2) = 0 \iff x_1 = x_2 \\
|
|
&d(x_1, x_2) = d(x_2, x_1) \\
|
|
&d(x_1, x_2) \le d(x_1, x_3) + d(x_3, x_2) \\
|
|
\intertext{Invece è una pseudo-metrica se:}
|
|
&d(x_1, x_2) \ge 0 \\
|
|
&d(x_1, x_2) = d(x_2, x_1) \\
|
|
&d(x_1, x_2) \le d(x_1, x_3) + d(x_3, x_2) \\
|
|
\end{align*}
|
|
\end{definizione}
|
|
|
|
$D_f(A,B)$ è una metrica se $f$ ha curvatura $\kappa_f < 1$. Se $\kappa_f = 0$ allora $D_f(A,B) = \sum_{v \in A \setminus B}f(v) + \sum_{v \in B \setminus A}f(v)$, che è la distanza di Hamming.
|
|
\begin{definizione}
|
|
Data una funzione $f$ submodulare, la metrica submodulare di Hamming $D_{f}^{\textnormal{SH}}(A,B)$ è definita come:
|
|
\begin{equation*}
|
|
D_{f}^{\textnormal{SH}}(A,B) = f\left( (A \setminus B) \cup (B \setminus A) \right)
|
|
\end{equation*}
|
|
\end{definizione}
|
|
|
|
Più utile è la sua approssimazione additiva chiamata $D_{f}^{\textnormal{SHA}}(A,B)$:
|
|
\[ D_{f}^{\textnormal{SHA}}(A,B) = f(A \setminus B) + f(B \setminus A) \]
|
|
|
|
Si ha quindi la seguente catena di disuguaglianze\cite{submodularcombinatorialinformation2021}:
|
|
\begin{center}
|
|
\begin{tblr}{X[1,l]X[1,l]X[1,l]X[1,l]X[2,l]}
|
|
\SetCell[c=5]{l} $ (1-\kappa_f(A \cup B))\cdot D^{\text{SH}}(A,B) \le $ \\
|
|
& \SetCell[c=4]{l} $ \le (1-\kappa_f(A \cup B)) \cdot D^{\text{SHA}}(A,B) \le $ \\
|
|
& & \SetCell[c=3]{l} $ \le D_f(A,B) \le $ \\
|
|
& & & \SetCell[c=2]{l} $ \le D^{\text{SH}}(A,B) \le $ \\
|
|
& & & & \SetCell[c=1]{l} $ \le D^{\text{SHA}}(A,B) $ \\
|
|
\end{tblr}
|
|
\end{center}
|
|
per $f$ monotona submodulare e $A, B$ qualsiasi. $\kappa_f(A)$ è la curvatura della funzione $f$ rispetto a un insieme $A$: $\kappa_f(A) = 1 - \min_{j\in A} \frac{f(j|A \setminus j)}{f(j)} $.
|
|
|
|
|
|
Due variabili aleatorie $X$ e $Y$ sono indipendenti quando l'informazione mutua $ \mathcal{I}(X;Y) = H(X,Y) = -\sum_{x \in X} \sum_{y \in Y}P(x,y) \log_2(P(x,y)) = 0 $, cioè per qualsiasi valore $x$ e $y$ che possono assumere $P(x,y) \log_2(P(x,y))$ risulti sempre uguale a 0.
|
|
Tuttavia la definizione per funzioni su insiemi diventa più intricata. Seguono alcune delle definizioni:
|
|
|
|
\begin{center}
|
|
\begin{tblr}{
|
|
colspec={Q[c,m]Q[co=1,c,m]Q[c,m]Q[co=2,l,m]},
|
|
column{1}= {leftsep = 0em},
|
|
hlines = {dash=dashed,fg=black!30}}
|
|
$\bullet$& Joint Independence (\textbf{J}) & $A \perp_f^{\text{J}} B $ se& $ \mathcal{I}_f(A;B) = 0 $ \\
|
|
$\bullet$& Marginal Independence (\textbf{M}) & $A \perp_f^{\text{M}} B $ se& {$ \forall a \in A, f(\{a\}|B) = f(\{a\}) $ e \\ $ \forall b \in B, f(\{b\}|A) = f(\{b\}) $} \\
|
|
$\bullet$& Pairwise Independence (\textbf{P}) & $A \perp_f^{\text{P}} B $ se& {$\forall a \in A, b \in B, f(\{a\}|\{b\}) = f(\{a\}) \land$ \\ $f(\{b\}|\{a\}) = f(\{b\}) $} \\
|
|
$\bullet$& Subset Marginal Independence (\textbf{SM}) & $A \perp_f^{\text{SM}} B $ se& {$\forall a \in A, X \subseteq B, f(\{a\}|X) = f(\{a\}) $ e\\ $\forall b \in B, X \subseteq A, f(\{b\}|X) = f(\{b\}) $} \\
|
|
$\bullet$& Modular Independence (\textbf{Mod}) & $A \perp_f^{\text{Mod}} B $ se& {$ \forall X \subseteq A \cup B, j \in A \cup B \setminus X, $ \\ $ f(\{j\}|X) = f(\{j\}) $} \\
|
|
$\bullet$& Subset Modular Independence (\textbf{SMod}) & $A \perp_f^{\text{SMod}} B $ se& {$\forall X \subseteq A \lor X \subseteq B, j \in A \cup B \setminus X, $ \\ $ f(\{j\}|X) = f(\{j\}) $} \\
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
Quando si riferirà all'indipendenza fra due insiemi si userà ``joint independence'' quando non specificato.
|
|
|
|
Esiste anche la nozione di indipendenza fra due insiemi $A$ e $B$ dato un insieme $C$: $A \perp^{\text{J}}_f B | C $ se $ \mathcal{I}_f(A;B|C) = 0 $, cioè se $ \mathcal{I}_f(A;B \cup C) = \mathcal{I}_f(A;C) \land \mathcal{I}_f(B;A \cup C) = \mathcal{I}_f(B;C)$. Si possono dare definizioni corrispondenti per \textbf{M}, \textbf{P}, \textbf{SM}, \textbf{Mod} e \textbf{SMod}.
|
|
|
|
\begin{teorema}
|
|
Sia $f$ una funzione prolimatroide, $A \perp_{f}^{\text{J}} B \Rightarrow A \cap B = \emptyset$.
|
|
\end{teorema}
|
|
|
|
\begin{dimostrazione}
|
|
$A \perp_{f}^{\text{J}} B $ implica $ \mathcal{I}_f(A;B) = 0 $, cioè $f(A) + f(B) = f(A \cup B)$.
|
|
Per submodularità di $f$ si ha che $ f(A) + f(B) \ge f(A \cup B) + f(A \cap B) \implies f(A) + f(B) - f(A \cup B) \ge f(A \cap B) \implies f(A \cap B) \le 0$.
|
|
Dato che $f$ è monotona e normalizzata, $f(A \cap B)$ non può essere negativa, quindi $ f(A \cap B) = 0 $.
|
|
Dato che $\forall a \in V, f(a) > 0$, allora $A \cap B$ deve essere uguale a $\emptyset$, cioè $A$ e $B$ sono disgiunti.
|
|
\end{dimostrazione}
|
|
|
|
|
|
\begin{teorema}
|
|
Per qualsiasi $f$ submodulare sono valide le seguenti relazioni:
|
|
\begin{center}
|
|
\begin{tblr}{colspec={ccccccccc}, rows = {abovesep=0pt,belowsep=0pt}}
|
|
\textbf{Mod}& $\Rightarrow$& \textbf{J}& $\Rightarrow$& \textbf{M}& $\Leftrightarrow$& \textbf{SM}& $\Rightarrow$& \textbf{P} \\
|
|
e \\
|
|
\textbf{Mod}& $\Rightarrow$& \textbf{SMod}& $\Rightarrow$& \textbf{M}&. & & & & \\
|
|
\end{tblr}
|
|
\end{center}
|
|
Esistono $f$ submodulari per cui l'inverso delle implicazioni non sono vere.
|
|
\end{teorema}
|
|
|
|
Si osserva che per $f$ submodulare si ha sempre $A \perp_f \emptyset$ e $A \perp_f C | B$ per $A \subseteq B$ e $C$ qualsiasi.
|
|
|
|
Se $f$ modulare allora tutte le definizioni di indipendenza sono equivalenti.
|
|
Se $f$ è una ``set cover function'' allora \textbf{J} $\Leftrightarrow$ \textbf{M} $\Leftrightarrow$ \textbf{SM} $\Leftrightarrow$ \textbf{P} e \textbf{Mod} $\Leftrightarrow$ \textbf{SMod}.
|
|
Se $f$ è la funzione entropia $H$ allora \textbf{Mod} $\Rightarrow$ \textbf{J} $\Rightarrow$ \textbf{M} $\Leftrightarrow$ \textbf{SM} $\Rightarrow$ \textbf{P}.
|
|
|
|
|
|
\subsection{Esempi di funzioni submodulari}\label{esempisubmodulari}
|
|
\begin{small}
|
|
\vspace{-0.6em}
|
|
\hspace{5em}\textit{tratto da }\cite{generalizedsubmodular2022}
|
|
\end{small}
|
|
|
|
|
|
\subsubsection{Weighted Set Cover}
|
|
Sia $f$ una ``weighted set cover function'', $f(A) = \omega(\bigcup\nolimits_{a\in A} \gamma(a)) = \omega(\gamma(A))$ con $\omega$ un vettore di pesi su $\mathbb{R}^{\gamma(V)}$ e senza perdita di generalità sempre positivo, $\omega(a) > 0, \forall a \in \gamma(V)$ dato che se esiste $b$ tale che $\omega(b) = 0$ si può semplicemente togliere $b$ da $\gamma(V)$.
|
|
|
|
$\gamma$ associa ogni sottoinsieme ad un altro sottoinsieme dei ``concetti''\cite{generalizedsubmodular2022} in $U = \gamma(V) \subseteq V$, $\omega(\gamma(A))$ è il peso dei ``concetti'' coperti dagli elementi in $A$.
|
|
|
|
Si osserva che $\gamma(A \cup B) = \gamma(A) \cup \gamma(B)$, da cui segue $f(A \cup B) = \omega(\gamma(A \cup B)) = \omega(\gamma(A) \cup \gamma(B))$.
|
|
|
|
Si può anche definire il problema in modo equivalente: sia $U$ l'insieme di tutti i ``concetti'', $U = \gamma(V)$, e sia
|
|
|
|
\begin{equation*}
|
|
c_u(i) =
|
|
\begin{cases}
|
|
1 & \text{se } u \in \gamma(\{i\})\\
|
|
0 & \text{altrimenti}
|
|
\end{cases}
|
|
\end{equation*}
|
|
|
|
cioè se $u$ è coperto dall'elemento $i$.
|
|
In modo analogo sia $c_u(A) = \sum_{a \in A}c_u(a) $ il numero di ``concetti'' nell'insieme $A$.
|
|
|
|
Si ottiene quindi $f(A) = \sum_{u \in U}\omega_u \min(c_u(A),1)$.
|
|
|
|
\begin{center}
|
|
\begin{tblr}{colspec={X[1,c]|X[1,c]|X[3,c]},
|
|
rowspec={Q[m]|Q[m]|Q[m]|Q[m]|Q[m]}
|
|
}
|
|
funzione & $f(A)$ & $\omega(\gamma(A))$ \\
|
|
submodular mutual information & $\mathcal{I}_f(A;B)$ & $\sum\limits_{u \in U} \omega_u \cdot \min(c_u(A),c_u(B),1) $ \\
|
|
submodular conditional gain & $f(A|B)$ & $\sum\limits_{u\in U} \omega_u \cdot (1-\min(c_u(B),1)) \cdot \min(c_u(A),1) $ \\
|
|
submodular information metric & $D_f(A,B)$ & $\omega(\gamma(A)\setminus \gamma(B)) + \omega(\gamma(B)\setminus \gamma(A))$ \\
|
|
submodular multi-set mutual information & $\mathcal{I}_f(A_1;\ldots;A_k) $ & $\sum\limits_{u \in U} \omega_u \cdot \min(c_u(A_1),\ldots,c_u(A_k),1)$ \\
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
Inoltre si ha che $A\perp_{f}B$ se e solo se $\gamma(A)\cap\gamma(B) = \emptyset$, quindi $A\perp_{f}C|B$ se e solo se $\gamma(A)\cap \gamma(C)\subseteq\gamma(B)$.
|
|
|
|
\subsubsection{Probabilistic Set Cover}
|
|
Sia $f$ una ``probabilistic set cover function'',
|
|
cioè $f(A) = \sum\nolimits_{i \in U}\omega_i \cdot (1-\prod\nolimits_{a\in A}(1-p_{ia}))$, dove $p_{ia}$ rappresenta la probabilità che l'elemento $a \in A$ ricopra l'elemento $i \in U = \gamma(V)$ e $\omega_i > 0$.
|
|
Nel caso $p_{ia} \in \{0,1\}$ si considera l'equivalente problema non probabilistico; per altri valori di $p$ si ha invece una generalizzazione del problema precedente.
|
|
Sia $P_i(A) = \prod_{a \in A}(1-p_{ia})$, cioè la probabilità che nessuno degli elementi di $A$ copra l'elemento $i$.
|
|
|
|
\begin{center}
|
|
\begin{tblr}{width=\linewidth,
|
|
colspec={X[1,c]|X[1,c]|X[3,c]},
|
|
rowspec={Q[m]|Q[m]|Q[m]|Q[m]|Q[m]}
|
|
}
|
|
funzione & $f(A)$ & $ \sum\limits_{i \in U}(1-P_i(A)) $ \\
|
|
submodular mutual information & $\mathcal{I}_f(A;B)$ & $ \sum\limits_{i \in U}\omega_i \cdot (1-(P_i(A) + P_i(B) - P_i(A \cup B))) $ \\
|
|
submodular conditional gain & $f(A|B)$ & $ \sum\limits_{i \in U} \omega_i \cdot P_i(B) \cdot (1-P_i(A \setminus B)) $ \\
|
|
submodular information metric & $D_f(A,B)$ & $ \sum\limits_{i \in U} \omega_i \cdot (P_i(B)\cdot(1-P_i(A \setminus B)) + P_i(A)(1-P_i(B \setminus A))) $ \\
|
|
submodular multi-set mutual information & $\mathcal{I}_f(A_1;\ldots;A_k) $ & $ \sum\limits_{i \in U} \omega \cdot \prod\limits_{j=1}^k(1-P_i(A_j)) $ \\
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
Sia ha che $A \perp_f B$ se e solo se $ \forall i \in U = \gamma(V), P_i(A) = 1 \vee P_i(B) = 1 $, cioè ogni elemento $i \in U$ non è coperto da $A$ né da $B$. In modo simile $ A \perp_f B|C $ se e solo se $P_i(A)=1 \vee P_i(B)=1$ quando $P_i(C) > 0$.
|
|
|
|
% Per definizione si può anche semplificare $D_f(A;B) = f(A|B)+f(B|A)$.
|
|
Si può osservare che $\mathcal{I}_f(A;B)$ è submodulare per $A$ con $B$ fisso. $\mathcal{I}_f(A;B)$ è quindi espresso equivalentemente come un'istanza di una ``probabilistic set cover function'' con i pesi per ogni elemento $i \in U$ uguali a $\omega_i(1-P_i(B))$ invece che $\omega_i$.
|
|
|
|
|
|
\subsubsection{Facility Location}
|
|
Sia $f(A) = \sum\nolimits_{i\in V}\max_{a\in A}s_{ia}$, dove $s$ è la matrice di similitudine fra gli elementi in $V$. In particolare $s$ per punti identici vale $1$, altrimenti ha valori inferiori a $1$.
|
|
|
|
\begin{center}
|
|
\begin{tblr}{width=\linewidth,
|
|
colspec={X[1,c]|X[1,c]|X[3,c]},
|
|
rowspec={Q[m]|Q[m]|Q[m]|Q[m]|Q[m]}
|
|
}
|
|
funzione & $f(A)$ & $ \sum\limits_{i \in V}\max\limits_{a \in A}s_{ia} $ \\
|
|
submodular mutual information & $\mathcal{I}_f(A;B)$ & $ \sum\limits_{i\in V}\min(\max\limits_{a\in A}s_{ia}, \max\limits_{b \in B}s_{ib}) $ \\
|
|
submodular conditional gain & $f(A|B)$ & $ \sum\limits_{i\in V}\max(0,\max\limits_{a\in A}s_{ia} - \max\limits_{b\in B} s_{ib}) $ \\
|
|
submodular information metric & $D_f(A,B)$ & $ \sum\limits_{i\in V}\lvert \max\limits_{a\in A}s_{ia} - \max\limits_{b\in B} s_{ib} \rvert $ \\
|
|
submodular multi-set mutual information & $\mathcal{I}_f(A_1;\ldots;A_k) $ & $ \sum\limits_{i\in V} \min(\max\limits_{a_1 \in A_1}s_{ia_1},\ldots,\max\limits_{a_k \in A_k}s_{ia_k}) $ \\
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
Inoltre $A \perp_f B$ se $\forall i \in V, (\forall j \in A, s_{ij}=0) \lor (\forall j \in B, s_{i,j}=0)$.
|
|
Si ha quindi $A \perp_f C|B$ se $ \forall i \in V, (\max_{j\in B}s_{ij}\ge \max_{j\in A}s_{ij}) \lor (\max_{j\in B}s_{ij}\ge \max_{j\in C}s_{ij}) $.
|
|
|
|
%% TODO espandere la descrizione delle formule
|
|
|
|
\subsubsection{Generalized Graph Cut}
|
|
|
|
Sia $f(A) = \lambda (\sum_{i\in V} \sum_{a\in A} s_{ia}) - \sum_{a_1,a_2 \in A} s_{a_1,a_2}$, con $s$ una matrice di similitudine, la funzione che generalizza il taglio di un grafo. Per garantire che $f$ sia una funzione monotona submodulare si richiede $\lambda \ge 2$.
|
|
|
|
\begin{center}
|
|
\begin{tblr}{width=\linewidth,
|
|
colspec={X[1,c]|X[1,c]|X[3,c]},
|
|
rowspec={Q[m]|Q[m]|Q[m]Q[m]}
|
|
}
|
|
funzione & $f(A)$ & $ \lambda (\sum\limits_{i\in V} \sum\limits_{a\in A} s_{ia}) - \sum\limits_{a_1,a_2 \in A} s_{a_1,a_2} $ \\
|
|
submodular mutual information & $\mathcal{I}_f(A;B)$ & $ f(A \cap B) + 2\sum\limits_{a \in A, b \in B}s_{ab}-2\sum\limits_{c\in A \cup B, d \in A \cap B}s_{cd} $ \\
|
|
submodular conditional gain & $f(A|B)$ & $ f(A \setminus B) - 2 \sum\limits_{a' \in A \setminus B} \sum\limits_{b\in B}s_{a'b} $ \\
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
In particolare se $A \cap B=\emptyset$ allora $ \mathcal{I}_f(A;B) = 2\sum\limits_{a \in A}\sum\limits_{b \in B}s_{ab} $, cioè la somiglianza fra gli insiemi $A$ e $B$. Inoltre $f(A|B) = f(A) - 2 \sum\limits_{a \in A}\sum\limits_{b \in B}s_{ab}$.
|
|
|
|
Si nota inoltre che $A \perp_f B$ se e solo se $ \mathcal{I}_f(A;B)=0 $ se e solo se $ s_{ab}=0, \forall a \in A, b \in B $.
|
|
|
|
Se si pone $B = V \setminus A$ si ottiene proprio la ``graph cut function'': $ \mathcal{I}_f(A;V \setminus A) = 2\sum\limits_{a\in A}\sum\limits_{b \in V \setminus A}s_{ab} $.
|
|
|
|
\subsubsection{Saturated Cover}
|
|
Sia $f(A) = \sum_{i\in V}\min(\alpha_i,\sum_{a\in A}s(i,a))$, con $s$ un kernel di similitudine come nel problema del ``facility location'' e $V = \{1,\ldots,n\}$.
|
|
Sia $m_i(A) = \sum_{a\in A} s(i,a)$, cioè un ``punteggio'' di $A$ per l'elemento $i$.
|
|
|
|
Per modularità si ha che $m_i(A\cup B) = m_i(A) + m_i(B) - m_i(A\cap B)$.
|
|
|
|
\begin{center}
|
|
\begin{tblr}{width=\linewidth,
|
|
colspec={X[1,c]|X[1,c]|X[3,c]},
|
|
rowspec={Q[m]|Q[m]|Q[m]}
|
|
}
|
|
funzione & $f(A)$ & $ \sum\limits_{i\in V}\min(\alpha_i,m_i(A)) $ \\
|
|
submodular mutual information & $\mathcal{I}_f(A;B)$ & $ \sum\limits_{i\in V}(\min(\alpha_i,m_i(A)) + \min(\alpha_i,m_i(B)) - \min(\alpha_i,m_i(A \cup B))) $ \\
|
|
submodular conditional gain & $f(A|B)$ & $ \sum\limits_{i \in V}\min(\alpha_i,m_i(A \cup B)) - \min(\alpha_i,m_i(B)) $ \\
|
|
\end{tblr}
|
|
\end{center}
|
|
|
|
Si può semplificare l'espressione di $\mathcal{I}_f(A;B)$ differenziando i casi rispetto a $i$ nella sommatoria:
|
|
|
|
\begin{tblr}{width=\linewidth,
|
|
colspec={Q[c,l]Q[c,l]Q[c,l]}}
|
|
$\bullet$& se $m_i(A) \ge \alpha_i, m_i(B) \le \alpha_i$ & allora si ottiene \ $m_i(B)$ \\
|
|
$\bullet$& se $m_i(A) \le \alpha_i, m_i(B) \ge \alpha_i$ & allora si ottiene \ $m_i(A)$ \\
|
|
$\bullet$& se $m_i(A) \ge \alpha_i, m_i(B) \ge \alpha_i$ & allora si ottiene \ $\alpha_i$ \\
|
|
$\bullet$& se $m_i(A \cup B) \le \alpha_i$ & allora si ottiene \ $m_i(A \cap B)$ \\
|
|
$\bullet$& \SetCell[c=1]{l,m} {se $m_i(A) \le \alpha_i, m_i(B) \le \alpha_i$, \\ $ m_i(A \cup B) \ge \alpha_i$} & allora si ottiene \ $m_i(A) + m_i(B) - \alpha_i$ \\
|
|
\end{tblr}
|
|
|
|
Si ottiene quindi: $\mathcal{I}_f(A;B) = \sum_{i \in V}\min(\alpha_i,m_i(A),m_i(B),m_i(A)+m_i(B)-\alpha_i)-\min(0,m_i(A \cup B)-\alpha_i)$.
|
|
|
|
|
|
%% \subsubsection{Log-Determinant} forse %%
|