A comparison between CNN s and WFA s for Sequence Classification (2020)

Abstract: We compare a classical CNN architecture for sequence classification involving several convolutional and max-pooling layers against a simple model based on weighted finite state automata (WFA). Each model has its advantages and disadvantages and it is possible that they could be combined. However, we believe that the first research goal should be to investigate and understand how do these two apparently dissimilar models compare in the context of specific natural language processing tasks. This paper is the first step towards that goal. Our experiments with five sequence classification datasets suggest that, despite the apparent simplicity of WFA models and training algorithms, the performance of WFAs is comparable to that of the CNNs.

## introduction in the latter years cnns have been proposed as models for sequence classification and it has been shown that they can give competitive results, even when compared to more complex models @xcite @xcite @xcite . they typically combine various convolutional filters with max-pooling layers. because they have several interacting layers, it is in general is hard to interpret exactly what is it that they are learning. but most likely their success relies on the fact that their convolutional filters have the ability to capture arbitrary features of the input sequence. on the other hand, non-deterministic weighted automata (wfas) are recurrent models that only use linear activation functions.essentially, wfas can be regarded as recurrent neural networks where the function that predicts the dynamic state representation from previous states is linear. for more details about the relations between linear activation rnns and wfas, we refer the reader to @xcite . several algorithms based on low rank matrix decompositions have been proposed @xcite @xcite @xcite . in addition to being easily trainable, wfas offer other advantages. the main advantage is that they are classical computer science models that have been intensively researched in the theoretical community. because of this they are relatively well understood and we know how to efficiently perform important computations. for example, consider a wfa computing a distribution over strings, there are simple and efficient algorithms to compute marginal probabilities for prefixes, infixes and suffixes. furthermore another advantage of these models is that there are well known and understood algorithms for transforming them into deterministic automata. the resulting deterministic automata can be used to interpret the computation performed by wfas. both cnns and wfas are general models, and the exact architecture can be specified to solve different tasks such as language modeling, or sequence classification which is the focus of this paper. each model has its advantages and disadvantages and it is possible that they could be combined. however, we believe that the first research goal should be to investigate and understand how do these two apparently dissimilar models compare in the context of specific natural language processing tasks. this paper is the first step towards that goal. we focus on the task of sequence classification and compare the performance of wfas and cnns trained under the same initial conditions, over five different data sets. to a certain extent a similar comparison between wfas and neural models was made by @xcite in the context of language modeling. but to our knowledge this is the first empirical comparison of cnns and wfas for sequence classification. ## experiments we conducted experiments on five sequence classification data sets: the wfa models have two parameters: the number of states k and the maximum window size t, both parameters were validated using a validation set. for k we tried @xcite @xcite when a standard train-development-test partition was not provided in the original data set we performed 10 fold cross validation and report mean performance. we will compare the performance of the ensemble wfa with a classical cnn architecture for sequence classification. more specifically, we compare against the model described in @xcite . the model has 100 convolutional filters run over ngrams of size: [3, 4, 5], a max-pooling layer and a fully connected softmax layer. the word embeddings are randomly initialized and then modified during training. the model was trained using 0.5 drop-out and l2 regularization. we performed experiments on the 5 sequence classification datasets and report the results on ## discussion in the surface cnns and wfas for sequence classification might seem quite dissimilar. the performance of the cnns relies on learning good discriminative ngram features via their convolutional filters. in contrast the wfa ensemble focuses on learning good estimates of the moments distributions of each class. however, if we look closer into the wfas we realize that implicitly the wfa can also capture arbitrary features of the input sequences via its latent states (i.e. the latent states can remember any regular pattern of the input sequence). the ability to induce patterns seems to be confirmed by our experiments. our results show that by simply making a discriminative prediction out of the outputs of the class specific wfas we can get very close to matching the performance of the cnns. both cnns and wfas have their advantages and disadvantages. the main advantage of the cnns is that they are very flexible and can induce arbitrary patterns. however, training them can be computationally expensive and the resulting model might be hard to interpret. on the other hand wfas can be easily trained with the classical spectral method. most of the models reported in these experiments were trained in less than five minutes in a regular machine with four cpus. in addition, because the relation between inputs and latent-state is more transparent (i.e. just a linear function) they might be interpreted more easily. the main disadvantage of wfas is that they lack the modeling flexibility of cnns. this is because it is harder to incorporate arbitrary loss functions. while there have been extensions of spectral methods that can exploit any convex loss function @xcite this usually results in optimizations that are significantly more costly. and therefore the resulting training algorithms loose part of the practical appeal of the classical spectral method. finally, another potential limitation of wfas is that because the latent state dynamics is linear, they might need more states than models that can make use on non-linear dynamics. most likely the best model would combine the best of both worlds. but the first step is to understand their similarities and differences in the context of concrete nlp tasks. we believe our results are a first tiny step towards that goal. ## future work in many ways our experiments are crippled. the most evident limitation is that none of the models exploit external features such as pre-trained word embeddings, as it is well known that such features are essential to improve the performance of sequence prediction models. as we already said this is just a first comparison, and we focused on the simplest possible configuration of both models. in the future, we plan to make comparisons of models that incorporate word embeddings. notice that wfas have also been defined for real valued inputs @xcite and therefore they can also incorporate pre-trained word embedding vectors. furthermore, the comparison is relatively unfair in the sense that the wfas are trained in a generative fashion. there have been proposals for discriminative training or discriminative refinements that we plan to explore in the future @xcite . finally, in this paper we focus on comparisons against cnns. but it would be interesting to expand the study to other models such as rnns and lstms.