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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F19%3A00505732" target="_blank" >RIV/67985807:_____/19:00505732 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.tcs.2018.08.012" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2018.08.012</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2018.08.012" target="_blank" >10.1016/j.tcs.2018.08.012</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

777

Číslo periodika v rámci svazku

19 July

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

10

Strana od-do

464-473

Kód UT WoS článku

000473372800030

EID výsledku v databázi Scopus

2-s2.0-85054352634