Nonlinear Weighted Finite Automata

Tianyu Li, Guillaume Rabusseau, Doina Precup
; Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:679-688, 2018.

Abstract

Weighted finite automata (WFA) can expressively model functions defined over strings but are inherently linear models.Given the recent successes of non-linear models in machine learning, it is natural to wonder whether extending WFA to the non-linearsetting would be beneficial.In this paper, we propose a novel model of neural network based nonlinear WFA model (NL-WFA) along with a learning algorithm. Our learning algorithm is inspired by the spectral learning algorithm for WFA and relies on a non-linear decomposition of the so-called Hankel matrix, by means of an auto-encoder network. The expressive power of NL-WFA and the proposed learning algorithm are assessed on both synthetic and real world data, showing that NL-WFA can infer complex grammatical structures from data.

Cite this Paper


BibTeX
@InProceedings{pmlr-v84-li18a, title = {Nonlinear Weighted Finite Automata}, author = {Tianyu Li and Guillaume Rabusseau and Doina Precup}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {679--688}, year = {2018}, editor = {Amos Storkey and Fernando Perez-Cruz}, volume = {84}, series = {Proceedings of Machine Learning Research}, address = {Playa Blanca, Lanzarote, Canary Islands}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/li18a/li18a.pdf}, url = {http://proceedings.mlr.press/v84/li18a.html}, abstract = {Weighted finite automata (WFA) can expressively model functions defined over strings but are inherently linear models.Given the recent successes of non-linear models in machine learning, it is natural to wonder whether extending WFA to the non-linearsetting would be beneficial.In this paper, we propose a novel model of neural network based nonlinear WFA model (NL-WFA) along with a learning algorithm. Our learning algorithm is inspired by the spectral learning algorithm for WFA and relies on a non-linear decomposition of the so-called Hankel matrix, by means of an auto-encoder network. The expressive power of NL-WFA and the proposed learning algorithm are assessed on both synthetic and real world data, showing that NL-WFA can infer complex grammatical structures from data.} }
Endnote
%0 Conference Paper %T Nonlinear Weighted Finite Automata %A Tianyu Li %A Guillaume Rabusseau %A Doina Precup %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-li18a %I PMLR %J Proceedings of Machine Learning Research %P 679--688 %U http://proceedings.mlr.press %V 84 %W PMLR %X Weighted finite automata (WFA) can expressively model functions defined over strings but are inherently linear models.Given the recent successes of non-linear models in machine learning, it is natural to wonder whether extending WFA to the non-linearsetting would be beneficial.In this paper, we propose a novel model of neural network based nonlinear WFA model (NL-WFA) along with a learning algorithm. Our learning algorithm is inspired by the spectral learning algorithm for WFA and relies on a non-linear decomposition of the so-called Hankel matrix, by means of an auto-encoder network. The expressive power of NL-WFA and the proposed learning algorithm are assessed on both synthetic and real world data, showing that NL-WFA can infer complex grammatical structures from data.
APA
Li, T., Rabusseau, G. & Precup, D.. (2018). Nonlinear Weighted Finite Automata. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in PMLR 84:679-688

Related Material