The NLP Engine: A Universal Turing Machine for NLP
This provides a foundational approach to systematically measure and compare NLP task complexities, though it is an initial and imperfect attempt.
The paper develops a universal framework to quantify the complexity of NLP tasks using Shannon Entropy, comparing simpler tasks like part-of-speech tagging to more complex ones like machine translation.
It is commonly accepted that machine translation is a more complex task than part of speech tagging. But how much more complex? In this paper we make an attempt to develop a general framework and methodology for computing the informational and/or processing complexity of NLP applications and tasks. We define a universal framework akin to a Turning Machine that attempts to fit (most) NLP tasks into one paradigm. We calculate the complexities of various NLP tasks using measures of Shannon Entropy, and compare `simple' ones such as part of speech tagging to `complex' ones such as machine translation. This paper provides a first, though far from perfect, attempt to quantify NLP tasks under a uniform paradigm. We point out current deficiencies and suggest some avenues for fruitful research.