16 lines
2.5 KiB
TeX
16 lines
2.5 KiB
TeX
\section{Introduzione}
|
|
|
|
Entropia e mutua infomazione hanno trovato numerose applicazioni in machine learning. Si studia quindi una generalizzazione: le funzioni submodulari. Questa classe di funzioni è speciale dato che la minimizzazione è nota essere risolubile in tempo polinomiale\cite{datastructuresandalg2012}, mentre la massimizzazione, per quanto NP-completa, ammette approssimazione a meno di un fattore costante. Lo studio è incentivato dal fatto che molti problemi pratici si esprimono in termini di funzioni submodulari; ad esempio min-cut è un esempio di minimizzazione di una funzione submodulare. Esempi di massimizzazione di funzione submodulare sono il ``set-covering problem''\cite{setcovering1970}, ``uncapacitated competitive facility location problem''\cite{benati2003}, ``quadratic cost partition problem''\cite{goldengoringhosh2005}, ``generalized transpotation problem''\cite{maximizingsubmodularsetfunctions1981}.
|
|
|
|
Nel capitolo\ \ref{matroidi} saranno quindi illustrate le basi della teoria dei matroidi.
|
|
Lo studio dei matroidi parte da Hassler Whitney che nel 1935\cite{whitney1935} pone le basi per lo studio dell'argomento. Applicazioni della materia coprono numerosi campi, studio di grafi\cite{tutte1971}\cite{iri1979}, network flow\cite{lawler2004}, network analysis e network synthesis\cite{Recski2011}, descrizione di sistemi dinamici\cite{murota2010} e come approccio a una possibile soluzione al problema dei 4 colori\cite{tutte196615}\cite{ams1996matroid}.
|
|
|
|
Nel capitolo\ \ref{politopiepoliedri} si daranno le definizioni di poliedri e politopi.
|
|
|
|
Nei capitoli\ \ref{polimatroidi} e\ \ref{funzionipolimatroidi} si definirà prima i polimatroidi seguito dalle funzioni submodulari e loro proprietà.
|
|
Lo studio dei polimatroidi, come i matroidi generalizzano l'organizzazione di iperpiani, tratta dell'organizzazione di sottospazi e ha numerose applicazioni in programmazione lineare\cite{edmonds2001}\cite{schrijver2003} e teoria dei codici\cite{rankmetricqpoly2019}.
|
|
|
|
Nel capitolo\ \ref{esempisubmodulari} vedremo alcuni esempi di funzioni submodulari: ``weighted set cover'', ``probabilistic set cover'', ``facility location'', ``generalized graph cut'' e ``saturated cover'' e alcune delle loro proprietà.
|
|
|
|
Infine nella sezione\ \ref{applicazioneprob} vedremo quindi alcune applicazioni delle funzioni submodulari precedentemente illustrate in problemi come ``sensor placement'', ``query based, privacy preserving summarization'' e ``clustering'' attraverso informazione mutua.
|