# A Noise-tolerant Differentiable Learning Approach for Single Occurrence Regular Expression with Interleaving

arXiv: https://arxiv.org/abs/2212.00373 · HTML: https://mlsanity.com/paper/2212.00373/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 39 references that are in the map.
- First posted on arXiv 1 Dec 2022.

## Builds on (most cited first, 11 of 11)

- [DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs](https://mlsanity.com/paper/1911.00055/) (2019)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [End-to-End Differentiable Proving](https://mlsanity.com/paper/1705.11040/) (2017)
- [Learning Reasoning Strategies in End-to-End Differentiable Proving](https://mlsanity.com/paper/2007.06477/) (2020)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [Learn to Explain Efficiently via Neural Logic Inductive Learning](https://mlsanity.com/paper/1910.02481/) (2019)
- [Differentiable Reasoning on Large Knowledge Bases and Natural Language](https://mlsanity.com/paper/1912.10824/) (2019)
- [TransRegex: Multi-modal Regular Expression Synthesis by Generate-and-Repair](https://mlsanity.com/paper/2012.15489/) (2020)
- [Learning First-Order Rules with Differentiable Logic Program Semantics](https://mlsanity.com/paper/2204.13570/) (2022)
- [Practical Study of Deterministic Regular Expressions from Large-scale XML and Schema Data](https://mlsanity.com/paper/1805.12503/) (2018)
- [An Effective Algorithm for Learning Single Occurrence Regular Expressions with Interleaving](https://mlsanity.com/paper/1906.02074/) (2019)

## Abstract (arXiv)

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.