A rank-determination method for the spectral learning of stochastic weighted automata

In this work, a rank-determination method for the spectral learning algorithms of stochastic weighted finite automata (WFA) is proposed.In the spectral learning of stochastic WFA, a hyper-parameter which is the rank of the model needs to be specified by a user.However, the user usually does not know the true rank in advance.Therefore, some cross-validation process is employed for choosing the rank.This method is inefficient since it requires to learn multiple models.Our method can estimate the rank of the model during a single spectral learning process, and hence it eliminates the need for the cross-validation process.The idea is that when the noise level in data is low, analyzing the noise level and comparing it with the singular values of the sub-Hankel matrix might give us some insight into the number of effective singular values.Because the rank of any complete sub-Hankel matrix is equal to the number of state in a stochastic WFA, we can approximately estimate the number of state in a stochastic WFA by estimating the rank of a complete sub-Hankel matrix.To achieve this, we replace the deterministic singular value decomposition (SVD) with the fixed-precision randomized singular value decomposition (RSVD) in the spectral learning algorithm and propose two methods to estimate the noise level in data.By combining the noise-estimation method and the modified spectral learning algorithm, we obtain the new method, noise estimation based rank revealing method (NERR).Experimental results on datasets of the probabilistic automata learning competition (Pautomac) and the sequence prediction challenge (SPiCe) demonstrate the utility of this method.v Résumé Dans ce travail, une méthode de détermination de rang pour les algorithmes d'apprentissage spectral des automates finis pondérés (WFA) stochastiques est proposée.Pour l'apprentissage spectral des automates finis pondérés stochastiques, un hyperparamètre, qui correspond au rang du modèle, doit être spécifié par l'utilisateur.Cependant, l'utilisateur ne connaît généralement pas le rang réel à l'avance.Par conséquent, un processus de validation croisée est utilisé pour choisir le rang.Cette méthode est inefficace car elle nécessite l'apprentissage de plusieurs modèles.Notre méthode permet d'estimer le rang du modèle au cours d'un processus d'apprentissage spectral unique, éliminant ainsi la nécessité du processus de validation croisée.L'idée est que, lorsque le niveau de bruit dans les données est faible, l'analyse du niveau de bruit et sa comparaison avec les valeurs singulières de la matrice sous-Hankel pourraient nous donner une idée du nombre de valeurs singulières effectives.Étant donné que le rang de toute matrice sous-Hankel complète est égal au nombre d'états dans un automate fini pondéré stochastique, nous pouvons estimer approximativement le nombre d'états dans un automate fini pondéré stochastique en estimant le rang d'une matrice sous-Hankel complète.Pour ce faire, nous remplaçons la décomposition en valeurs singulières (SVD) d'ordre déterministe par la décomposition en valeurs singulières d'ordre aléatoire (RSVD) à précision fixe dans l'algorithme d'apprentissage spectral et proposons deux méthodes d'estimation du niveau de bruit dans les données.En combinant la méthode d'estimation du bruit et l'algorithme d'apprentissage spectral modifié, nous obtenons la nouvelle méthode, la méthode de révélation de rang basée sur l'estimation du bruit (NERR).Les résultats expérimentaux sur les jeux de données du concours d'apprentissage des automates probabilistes (Pautomac) et du défi de prédiction de séquence (SPiCe) démontrent l'utilité de cette méthode.vii Acknowledgements Foremost, I would like to express my sincere gratitude to my thesis advisors Prof. Xiao-Wen Chang and Prof. Doina Precup for the financial support of my master study and research, for their patience, motivation, enthusiasm, and immense knowledge.Their guidance helped me in all the time of research and writing of this thesis.I could not have imagined having better

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.