Kaito Suzuki, Diptarama Hendrian, Ryo Yoshinaka and Ayumi Shinohara
Video:
Link to the paper: here
Abstract: We propose a query learning algorithm for an extension of weighted finite automata (WFAs), named symbolic weighted finite automata (SWFAs), which can handle strings over infinite alphabets more efficiently. Based on the idea of symbolic finite automata, SWFAs generalize WFAs by allowing transitions to be functions from a possibly infinite alphabet to weights. Our algorithm can learn SWFAs if functions in transitions are also learnable by queries. We also investigate minimization and equivalence checking for SWFAs
Any question or comment can be made using the comment section of the page below.
Thank you for the talk – it was very clear! I was wondering what kind of domains or applications are best suited to SWFAs. Are there examples in which another representation is possible, but the SWFA representation is more efficient?
Thank you for your question. In principle, SWFAs can be used for any applications of WFAs, such as extraction from RNN, data compression, NLP, etc. If the alphabet size is huge or infinite, SWFAs have the advantage in the sense of representation size. I think the example of extraction from RNN is particularly interesting since many RNNs have huge discrete (because of multi-dimensional) or continuous input.
However, our algorithm requires some additional assumptions for polynomial-time learning, including the existence of MAT-learner for the function class G and linear-closedness of G. This limits the range of applications. Our paper includes some discussions to show examples of G, but the applicable example of applications is still unclear.