\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 %%