An Algorithmic Approach to Establish a Lower Bound for the Size of Semiring Neural Networks
Martin Böhm, Thomas Schmid · ESANN 2021 proceedings · 2021
Semiring neural networks have been introduced as a recurrent neural network-type representation of weighted automata with the potential to learn a recognizable series.Whether a given semiring neural network actually can or cannot compute a recognizable series, however, depends on the size of the network.Therefore, it is desirable to determine whether a proposed size is too small before initiation of the training procedure.Here, we present an algorithm that achieves this in polynomial time.As there is a one-to-one correspondence between semiring neural networks and weighted automata, our algorithm can also be used to derive lower bounds for the size of a recognizing automaton.Our algorithm complements previous work in this area as it works over commutative zero-sum-free semirings.