A Noise-tolerant Differentiable Learning Approach for Single Occurrence Regular Expression with Interleaving
This addresses a practical challenge in text processing for applications like data extraction, though it is incremental as it builds on prior work with improved robustness.
The paper tackles the problem of learning single occurrence regular expressions with interleaving (SOIRE) from noisy text strings, proposing a noise-tolerant differentiable learning approach called SOIREDL that outperforms state-of-the-art methods, particularly on noisy data.
We study the problem of learning a single occurrence regular expression with interleaving (SOIRE) from a set of text strings possibly with noise. SOIRE fully supports interleaving and covers a large portion of regular expressions used in practice. Learning SOIREs is challenging because it requires heavy computation and text strings usually contain noise in practice. Most of the previous studies only learn restricted SOIREs and are not robust on noisy data. To tackle these issues, we propose a noise-tolerant differentiable learning approach SOIREDL for SOIRE. We design a neural network to simulate SOIRE matching and theoretically prove that certain assignments of the set of parameters learnt by the neural network, called faithful encodings, are one-to-one corresponding to SOIREs for a bounded size. Based on this correspondence, we interpret the target SOIRE from an assignment of the set of parameters of the neural network by exploring the nearest faithful encodings. Experimental results show that SOIREDL outperforms the state-of-the-art approaches, especially on noisy data.