Question Answering by Humans and Machines: A Complexity-theoretic View

0505732 - ÚI 2020 RIV NL eng J - Článek v odborném periodiku
van Leeuwen, J. - Wiedermann, Jiří
Question Answering by Humans and Machines: A Complexity-theoretic View.
Theoretical Computer Science. Roč. 777, 19 July (2019), s. 464-473. ISSN 0304-3975. E-ISSN 1879-2294
Grant ostatní: AV ČR(CZ) StrategieAV21/1
Program: StrategieAV
Institucionální podpora: RVO:67985807
Klíčová slova: Question answering * Computational complexity * Human agents * Cognitive automata * Background intelligence * QA-machines * Advice * Learning space * Pippenger's theorem * Turing machines
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.747, rok: 2019
Způsob publikování: Open access
http://dx.doi.org/10.1016/j.tcs.2018.08.012

Question-answering systems like Watson beat humans when it comes to processing speed and memory. But what happens if we compensate for this? What are the fundamental differences in power between human and artificial agents in question answering? We explore this issue by defining new computational models for both agents and comparing their computational efficiency in interactive sessions. Concretely, human agents are modeled by means of cognitive automata, augmented with a form of background intelligence which gives the automata the possibility to query a given Turing machine and use the answers from one interaction to the next. On the other hand, artificial question-answering agents are modeled by QA-machines, which are Turing machines that can access a predefined, potentially infinite knowledge base (‘advice’) and have a bounded amount of learning space at their disposal. We show that cognitive automata and QA-machines have exactly the same potential in realizing question-answering sessions, provided the resource bounds in one model are sufficient to match the abilities of the other. In particular, polynomially bounded cognitive automata with background intelligence (i.e. human agents) prove to be equivalent to polynomially bounded QA-machines with logarithmic learning space. It generalizes Pippenger's theorem on the computational power of switching circuits (without background intelligence) to a foundational result for question answering in cognitive science. The framework reveals why QA-machines have a fundamental advantage.
Trvalý link: http://hdl.handle.net/11104/0297140