Analisi di equazioni iterative per l'ottimizzazione combinatoria.

This work concerns the application of belief propagation, a computational technique which arose in the fields of statistical physics and statistics, to an important combinatorial problem, the maximum weight matching on a bipartite graph. Belief propagation, otherwise known as the cavity method in theoretical physics, message passing algorithms in artificial intelligence, is an iterative procedure that allows to compute the marginal distributions of a set of variables in an efficient way, when the direct, "brute force' approach of summing over all the configurations would take too much time. In doing that, it exploits the structure of the probability measure associating to it a graph, the factor graph. In alternative formulations, it can be adapted to efficiently sample from a distribution or maximize a function, and I will focus on the latter aspect in particular. The cases in which this technique yields exact results in the rigorous mathematical sense are few, and the matching is one of them, but it performs impressively well as an approximation technique in a wide variety of cases; as a result, it is widely studied, both theoretically and practically, and applied in many disparate fields as computer vision, expert systems, coding theory, computational biology. I present some proofs of convergence and correctness and for the matching some simulations in which I compare the performance of BP and some variants with another widely used algorithm, the auction algorithm.

La mia tesi riguarda l'applicazione della Belief Propagation, una tecnica computazionale nata nell'ambito della fisica statistica e della statistica, a un importante problema combinatoriale: il problema del matching pesato ottimale su un grafo bipartito. La belief propagation, nota anche come metodo della cavità in fisica statistica, è una procedura iterativa che permette di calcolare la distribuzione marginale di un insieme di variabili in modo efficiente, quando l'approccio diretto impiegherebbe troppo tempo, e per fare questo sfrutta la particolare struttura della distribuzione di probabilità congiunta associandovi un grafo, il factor graph; in una formulazione alternativa, può essere usata per ottimizzare una funzione. I casi in cui questa tecnica dà risultati esatti in un senso matematicamente rigoroso sono pochi, e il matching è uno di questi, ma funziona straordinariamente e sorprendentemente bene come tecnica di approssimazione in una grande varietà di problemi, e infatti è stata largamente studiata ed è molto impiegata nei campi più disparati come computer vision, biologia computazionale, teoria dei codici. Presento alcune dimostrazioni della sua correttezza nei casi in cui è possibile, e per il matching alcune simulazioni per confrontare la sua performance di alcune sue varianti con un altro algoritmo (auction algorithm).