×

zbMATH — the first resource for mathematics

Question answering by humans and machines: a complexity-theoretic view. (English) Zbl 1423.68375
Summary: 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.
MSC:
68T01 General topics in artificial intelligence
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balcázar, J. L.; Diaz, J.; Gabarro, J., Structural Complexity I, (1995), Springer-Verlag: Springer-Verlag Berlin
[2] News, B. B.C., IBM’s Watson supercomputer crowned Jeopardy king, (February 17, 2011)
[3] Damm, C.; Holzer, M., Automata that take advice, (Wiedermann, J.; Hájek, P., Mathematical Foundations of Computer Science 1995, Proc. 20th International Symposium (MFCS’95). Mathematical Foundations of Computer Science 1995, Proc. 20th International Symposium (MFCS’95), Lecture Notes in Comput. Sci., vol. 969, (1995), Springer-Verlag: Springer-Verlag Berlin), 149-158 · Zbl 1193.68152
[4] Ferrucci, D., Building Watson: an overview of the DeepQA project, AI Mag., 59-79, (Fall 2010)
[5] Goldin, D.; Wegner, P., Persistence as a Form of Interaction, (1998), Dept. of Computer Science, Brown University: Dept. of Computer Science, Brown University Providence RI, Tech. Rep. CS-98-07
[6] Goldin, D. Q., Persistent Turing machines as a model of interactive computation, (Schewe, K.-D.; Thalheim, B., Foundations of Information and Knowledge Systems. Foundations of Information and Knowledge Systems, Lecture Notes in Comput. Sci., vol. 1762, (2000), Springer-Verlag), 116-135 · Zbl 0961.68048
[7] Goldin, D. Q.; Smolka, S. A.; Attie, P. C.; Sonderegger, E. L., Turing machines, transition systems, and interaction, Inform. and Comput., 194, 2, 101-128, (2004) · Zbl 1090.68040
[8] Hempel, H.; Kimmritz, M., Persistent computations of Turing machines, (Ibarra, O. H.; Ravikumar, B., Implementation and Application of Automata, 13th Int. Conference. Implementation and Application of Automata, 13th Int. Conference, CIAA 2008. Implementation and Application of Automata, 13th Int. Conference. Implementation and Application of Automata, 13th Int. Conference, CIAA 2008, Lecture Notes in Comput. Sci., vol. 5148, (2008), Springer-Verlag), 171-180 · Zbl 1172.68472
[9] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relation to Automata, (1969), Addison-Wesley Publ. Comp.: Addison-Wesley Publ. Comp. Reading MA · Zbl 0196.01701
[10] Karp, R. M.; Lipton, R. J., Turing machines that take advice, Enseign. Math., 28, 191-209, (1982) · Zbl 0529.68025
[11] Kosub, S., Persistent Computations, (1998), Institut für Informatik, Julius-Maximilians-Universität Würzburg: Institut für Informatik, Julius-Maximilians-Universität Würzburg Würzburg, Techn. Rep. 217
[12] Lehnert, W. G., Paradigmatic issues in cognitive science, (Kintsch, W.; Miller, J. R.; Polson, P. G., Methods and Tactics in Cognitive Science, (1984), Psychology Press: Psychology Press New York), 21-49, Ch. 2
[13] (Maybury, M. T., New Directions in Question Answering. New Directions in Question Answering, AAAI Ser., (2004), MIT Press: MIT Press Cambridge MA)
[14] Mishra, A.; Jain, S. K., A survey on question answering systems with classification, J. King Saud Univ. - Comput. Inf. Sci., 28, 345-361, (2016)
[15] Nelson, R. J., Machine models for cognitive science, Philos. Sci., 54, 391-408, (1987)
[16] Nivat, M., 40th anniversary of EATCS, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 108, 145-147, (October 2012)
[17] Pippenger, N., On simultaneous resource bounds, (20th Symp. Foundations of Computer Science, Proceedings, (1979), IEEE Press), 307-311
[18] Pylyshyn, Z. W., Computing in cognitive science, (I. Ṗosner, M., Foundations of Cognitive Science, (1989), MIT Press: MIT Press Cambridge, MA), 49-91
[19] van Leeuwen, J.; Wiedermann, J., Beyond the Turing limit: evolving interactive systems, (Pacholski, L.; Ružička, P., Theory and Practice of Informatics, Proc. 28th Conference. Theory and Practice of Informatics, Proc. 28th Conference, SOFSEM 2001. Theory and Practice of Informatics, Proc. 28th Conference. Theory and Practice of Informatics, Proc. 28th Conference, SOFSEM 2001, Lecture Notes in Comput. Sci., vol. 2234, (2001), Springer-Verlag: Springer-Verlag Berlin), 90-109 · Zbl 1052.68045
[20] Vollmer, H., Introduction to Circuit Complexity - A Uniform Approach, (1999), Springer-Verlag: Springer-Verlag Berlin
[21] Wiedermann, J., The computational limits to the cognitive power of the neuroidal tabula rasa, J. Exp. Theor. Artif. Intell., 15, 3, 267-279, (2003) · Zbl 1084.68112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.