Learning Moderately Input-Sensitive Functions: A Case Study in QR Code Decoding
This work addresses the challenge of learning functions with medium input-sensitivity, such as QR code decoding, for applications in symbolic computation and AI, representing a novel domain application rather than an incremental improvement.
The study tackled the problem of learning moderately input-sensitive functions by developing the first learning-based QR code decoder using Transformers, which successfully decoded QR codes beyond the theoretical error-correction limit and generalized to different languages and random strings.
The hardness of learning a function that attains a target task relates to its input-sensitivity. For example, image classification tasks are input-insensitive as minor corruptions should not affect the classification results, whereas arithmetic and symbolic computation, which have been recently attracting interest, are highly input-sensitive as each input variable connects to the computation results. This study presents the first learning-based Quick Response (QR) code decoding and investigates learning functions of medium sensitivity. Our experiments reveal that Transformers can successfully decode QR codes, even beyond the theoretical error-correction limit, by learning the structure of embedded texts. They generalize from English-rich training data to other languages and even random strings. Moreover, we observe that the Transformer-based QR decoder focuses on data bits while ignoring error-correction bits, suggesting a decoding mechanism distinct from standard QR code readers.