Morisi, Rita (2016) Graph–based techniques and spectral graph theory in control and machine learning. Advisor: Gnecco, Prof. Stefano. pp. 215. [IMT PhD Thesis]

Text
Morisi_phdthesis.pdf  Published Version Available under License Creative Commons Attribution No Derivatives. Download (4MB)  Preview 
Abstract
Graphs are powerful data structure for representing objects and their relationships. They are extremely useful in the study of dynamical systems, evaluating how different agents interact among each other and behave. An example is represented by the consensus problem where a graph models a set of agents that locally interact and exchange their opinions with the aim of reaching a common opinion (consensus state). At the same time, many learning techniques rely on graphs exploiting their potentialities in modeling the relationships between data and determining additional features related to the data similarities. To study both the consensus problem and specific machine learning applications based on graphs, the study of the spectral properties of graphs reveals fundamental. In the consensus problem, the convergence rate to the consensus state strictly depends on the spectral properties of the transition probability matrix associated to the agents network. Whereas graphs and their spectral properties are fundamental in determining learning algorithms able to capture the structure of a dataset. We propose a theoretical and numerical study of the spectral properties of a network of agents that interact with the aim of increasing the rate of convergence to the consensus state keeping as sparse as possible the graph involved. Experimental results demonstrate the capability of the proposed approach in reaching the consensus state faster than a classical approach. We then investigate the potentialities of graphs when applied in classification problems. The results achieved highlight the importance of graphs and their spectral properties handling with both semi–supervised and supervised learning problems.
Item Type:  IMT PhD Thesis 

Subjects:  Q Science > QA Mathematics > QA75 Electronic computers. Computer science 
PhD Course:  Computer Decision and System Science 
Identification Number:  10.6092/imtlucca/etheses/188 
Date Deposited:  27 Jul 2016 08:57 
URI:  http://etheses.imtlucca.it/id/eprint/188 
Actions (login required, only for staff repository)
View Item 