Distributed randomized model structure selection for NARX models

The identification of polynomial Nonlinear AutoRegressive [Moving Average] with eXogenous input variables (NAR[MA]X) models is typically carried out with incremental model building techniques. Despite their popularity, model structure selection (MSS) algorithms based on incremental model building procedures are critically affected by their inherently local search mechanism, that estimates the importance of each regressor based on its marginal improvement on the predictive performance of the model composed of the terms already selected. As a result, incremental MSS methods often lead to suboptimal solutions because of their difficulty to assess the global importance of a single regressor. The recently developed Randomized MSS (RaMSS) algorithm overcomes this limitation by recasting the MSS problem into a probabilistic framework. An independent Bernoulli random variable is assigned to each regressor to represent its probability of belonging to the target model structure. The probability distribution induced by the Bernoulli variables over the space of model structures is then progressively updated according to the performance of a population of extracted models, obtained through random sampling, until the convergence to the target model is achieved. The RaMSS algorithm shows its limitations when the number of regressors increases, since the number of sampled models must be increased as well in order to accurately explore the search space. Increasing the size of the population of extracted models, however, causes also an increase in the computational effort and, therefore, in the time required by the algorithm to converge. In this thesis, a distributed version of the RaMSS algorithm (dRaMSS) is introduced to overcome this issue. The regressor set is split among a group of independent processors and each of them executes the RaMSS on its local subset. The selected models are then distributed among all the units. Each processor adds the regressors of the collected model structures to its own regressor set and repeats the procedure. With this mechanism, every processor progressively improves its local MSS solution based on the knowledge extracted by the other ones, until all of them finally converge to the same solution. The performance of the dRaMSS has been evaluated on several different systems taken from the literature, with regressor sets of different sizes, via Monte-Carlo simulations. The results show that the distributed approach outperforms the centralized algorithm in terms of computation time and explored models when the number of terms in the regressor set is sufficiently high. Additionally, in case of huge regressor spaces (> 18K terms), the dRaMSS procedure achieves better results also in terms of accuracy, thus demonstrating to be a very effective MSS solver when the number of regressors is prohibitively large to be addressed by centralized algorithms.

L'identificazione di modelli NAR[MA]X (Nonlinear AutoRegressive [Moving Average] with eXogenous input variables) polinomiali è condotta tipicamente attraverso algoritmi basati sulla costruzione incrementale del modello. Nonostante la loro popolarità, l'efficacia di queste tecniche è notevolmente limitata dal loro meccanismo di selezione intrinsecamente locale, che stima l'importanza di ciascun regressore basandosi sul miglioramento della capacità predittiva a seguito del suo eventuale inserimento nel modello finale. L'algoritmo RaMSS (Randomized Model Structure Selection) supera questo limite riformulando il problema in un quadro probabilistico. Ad ogni regressore è assegnata una variabile casuale Bernoulliana indipendente che rappresenta la probabilità del termine di fare parte della struttura di modello finale. La distribuzione di probabilità indotta dalle variabili Bernoulliane sullo spazio delle strutture di modello è quindi progressivamente aggiornata sulla base delle performance di una popolazione di modelli, ottenuta attraverso un campionamento randomizzato, fino al raggiungimento della convergenza su una distribuzione finale. Le limitazioni del RaMSS emergono quando il numero di regressori aumenta, dal momento che anche il numero dei modelli campionati deve essere incrementato per poter esplorare accuratamente lo spazio delle strutture di modello. Tuttavia, l'aumento della dimensione della popolazione di modelli estratti causa anche un incremento del carico computazionale e, conseguentemente, del tempo richiesto dall'algoritmo per raggiungere la convergenza. In questa tesi viene introdotta una versione distribuita del RaMSS (dRaMSS) allo scopo di superare questo problema. L'insieme dei regressori è suddiviso tra diversi processori indipendenti, ciascuno dei quali esegue l'algoritmo RaMSS sul proprio sottoinsieme locale. I modelli selezionati sono quindi distribuiti tra tutte le unità. Ogni processore aggiunge l'unione dei regressori raccolti al proprio insieme locale e ripete la procedura di selezione e distribuzione. Con questo procedimento ogni processore migliora progressivamente la propria soluzione basandosi sulle informazioni ricavate dagli altri, fino a quando tutti non convergono sulla stessa struttura di modello. Le performance del dRaMSS sono state testate su diversi sistemi tratti dalla letteratura, con insiemi di regressori di dimensioni variabili, attraverso metodi di simulazione Monte-Carlo. I risultati mostrano che l'approccio distribuito supera l'algoritmo centralizzato in termini di tempo di computazione e numero di modelli esplorati, nel caso in cui il numero di regressori sia sufficientemente elevato. Inoltre, in caso di insiemi di regressori di dimensione particolarmente grande (18K termini), il dRaMSS ottiene risultati superiori anche in termini di accuratezza, dimostrando così la sua efficacia nell'identificazione della struttura di modello quando il numero di termini è così elevato da risultare proibitivo per gli algoritmi centralizzati.