Počet záznamů: 1
Question Answering by Humans and Machines: A Complexity-theoretic View
- 1.
SYSNO ASEP 0505732 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Question Answering by Humans and Machines: A Complexity-theoretic View Tvůrce(i) van Leeuwen, J. (NL)
Wiedermann, Jiří (UIVT-O) RID, SAI, ORCIDZdroj.dok. Theoretical Computer Science. - : Elsevier - ISSN 0304-3975
Roč. 777, 19 July (2019), s. 464-473Poč.str. 10 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova Question answering ; Computational complexity ; Human agents ; Cognitive automata ; Background intelligence ; QA-machines ; Advice ; Learning space ; Pippenger's theorem ; Turing machines Vědní obor RIV IN - Informatika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) Způsob publikování Open access Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000473372800030 EID SCOPUS 85054352634 DOI 10.1016/j.tcs.2018.08.012 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2020 Elektronická adresa http://dx.doi.org/10.1016/j.tcs.2018.08.012
Počet záznamů: 1