Regolarizzazione e Semi-supervised Learning su grafi di grandi dimensioni

La seguente trattazione si occupa di prevedere l'etichettatura di un grafo parzialmente etichettato e di conseguenza di ricostruire una funzione sul grafo da un insieme di campionamenti. Sono stati analizzati due algoritmi in particolare: la regolarizzazione di Tikhonov e l'interpolazione basate su un metodo kernel. Sono poi state analizzate due stime dell'errore di generalizzazione sui dati confrontandole grazie ad alcune proprietà del kernel. Gli algoritmi sono stati applicati a diversi dataset con lo scopo di esaminare l'errore compiuto. Si è giunti infine alla seguente conclusione: per pochi nodi etichettati l'interpolazione risulta molto valida. Al crescere dei nodi etichettati, per scelte accurate del paramentro di regolarizzazione, l'algoritmo di Tikhonov risulta però più efficace.