QUESTION ANSWERING FROM PROCEDURAL SEMANTICS TO MODEL DISCOVERY

QUESTION ANSWERING FROM PROCEDURAL SEMANTICS TO MODEL DISCOVERY

Prof. John Kontos and Dr. Ioanna Malagardi

Encyclopedia of Human Computer Interaction, Edited by Dr. Claude Ghaoui. Idea Group Inc.Hershey, USA (2005)

(abridged)

ABSTRACT
A series of systems that can answer questions from various data or knowledge sources are briefly described and future developments are proposed. The line of development of ideas starts with procedural semantics and leads to human-computer interfaces that support researchers for the study of causal models of systems. The early implementation of question answering systems was based on procedural semantics. Deductive systems appeared later that produce answers implicit in the original database used for answering. Some systems were developed that instead of databases they used collections of texts for extracting the answers. Finally it is described how the information extracted from scientific and technical texts is used by modern systems for the answering of questions concerning the behaviour of causal models using appropriate linguistic and deduction mechanisms. It is predicted that the perfection of such systems will revolutionize the discovery practice of scientists and engineers.

HISTORICAL INTRODUCTION
Question Answering (QA) is one of the branches of Artificial Intelligence (AI) that involves the processing of human language by computer. QA systems accept questions in natural language and generate answers often also in natural language. The answers are derived from databases, text collectons or knowledge bases. The main aim of QA systems is to generate a short answer to a question rather than a list of possibly relevant documents. As it becomes more and more difficult to find answers on the WWW using standard search engines, the technology of QA systems will become increasingly important. A series of systems that can answer questions from various data or knowledge sources are briefly described below. These systems provide a friendly interface to the user of information systems that is particularly important for users who are not computer experts. The line of development of ideas starts with procedural semantics and leads to interfaces that support researchers for the discovery of parameter values of causal models of systems under scientific study. QA systems historically developed roughly during the 1960-1970 decade (Simmons, 1970). A few of the QA systems that were implemented during this decade are:

The BASEBALL System (Green et al, 1961)
The FACT RETRIEVAL System (Cooper, 1964)
The DELFI Systems (Kontos and Papakontantinou, 1970; Kontos and Kossidas, 1971)

The BASEBALL System
This system was implemented in the Lincoln Laboratory and it was the first QA system reported in the literature according to the references cited in the first book with a collection of AI papers (Feigenbaum and Feldman, 1963). The inputs were questions in English about games played by baseball teams. The system transformed the sentences to a form that permits search of a systematically organized memory store for the answers.Both the data and the dictionary were list structures and questions were limited to a single clause.

The FACT RETRIEVAL System
The system was implemented using the COMIT compiler-interpreter system as programming language. A translation algorithm was incorporated into the input routines. This algorithm generates the translation of all information sentences and all question sentences into their logical equivalents.

The DELFI System
The DELFI system answers natural language questions about the space relations between a set of objects. These are questions with unlimited nesting of relative clauses that were automatically translated into retrieval procedures consisting of general purpose procedural components that retrieved information from the database that contained data about the properties of the objects and their space relations.

The DELFI II System
The DELFI II system (Kontos and Kossidas, 1971) was an implementation of the second edition of the system DELFI augmented by deductive capabilities. In this system the procedural semantics of the questions are expressed using macro-instructions that are submitted to a macro-processor that expands them with a set of macro-definitions into full programs. Every macro-instruction corresponded to a procedural semantic component. In this way a program was generated that corresponded to the question and could be compiled and executed in order to generate the answer. DELFI II was used in two new applications. These applications concerned the processing of the database of the personnel of an organization and the answering of questions by deduction from a database with airline flight schedules using the rules:

If flight F1 flies to city C1 and flight F2 departs from city C1 then F2 follows F1.
If flight F1 follows flight F2 and the time of departure of F1 is at least two hours later than the time of arrival of F2 then F1 connects with F2.
If flight F1 connects with flight F2 and F2 departs from city C1 and F1 flies to city C2 then C2 is reachable from C1.

Given a database that contains the data:

F1 departs from Athens at 9 and arrives at Rome at 11
F2 departs from Rome at 14 and arrives at Paris at 15
F3 departs from Rome at 10 and arrives at London at 12

If the question “Is Paris reachable from Athens?” is submitted to the system then the answer it gives is “yes”, because F2 follows F1 and the time of departure of F2 is three hours later than the time of arrival of F1. It should be noted also that F1 departs from Athens and F2 flies to Paris.

If the question “Is London reachable from Athens?” is submitted to the system then the answer it gives is “no”, because F3 follows F1 but the time of departure of F3 is one hour earlier than the time of arrival of F1. It should be noted here that F1 departs from Athens and F3 flies to London.

BACKGROUND

The SQL QA Systems
In order to facilitate the commercial application of the results of research work like the one described so far it was necessary to adapt the methods used to the industrial data base environment. One important adaptation was the implementation of the procedural semantics interpretation of natural language questions using a commercially available database retrieval language. The SQL QA systems implemented by different groups including the author’s followed this direction by using SQL (Structured Query Language) so that the questions can be answered from any commercial database system.
The domain of an illustrative application of our SQL QA system involves information about different countries. The representation of the knowledge of the domain of application connected a verb phrase like “exports” or “has capital” to the corresponding table of the database that the verb is related to. This connection between the verbs and the tables provided the facility of the system to locate the table a question refers to using the verbs of the question. During the analysis of questions by the system an ontology related to the domain of application may be used for the correct translation of ambiguous questions to appropriate SQL queries. Some theoretical analysis of SQL QA systems has appeared recently (Popescu et al, 2003) and a recent system with a relational database is described in Samsonova et al [2003].

QA from Texts Systems
Some QA systems use collections of texts instead of databases for extracting answers. Most such systems are able to answer simple “factoid” questions only. Factoid questions seek an entity involved in a single fact. Some recent publications on QA from texts are Diekema [2003], Doan-Nguyen and Kosseim [2004], Harabagiu et al [2003], Kosseim et al [2003], Nyberg et al [2002], Plamondon and Kosseim [2002], Ramakrishnan [2004], Roussinof and Robles-Flores [2004] and Waldinger et al [2003]. Some future directions of QA from texts are proposed in Maybury [2003]. An international competition between question answering systems from texts has been organized by NIST (National Institute of Standards and Technology (Voorhees, 2001).
In what follows it is described how the information extracted from scientific and technical texts may be used by future systems for the answering of complex questions concerning the behaviour of causal models using appropriate linguistic and deduction mechanisms. An important function of such systems is the automatic generation of a justification or explanation of the answer provided.

The ARISTA System
The implementation of the ARISTA system is a QA system that answers questions by knowledge acquisition from natural language texts and it was first presented in Kontos [1992]. The ARISTA system was based on the representation independent method also called ARISTA for finding the appropriate causal sentences from a text and chaining them by the operation of the system for the discovery of causal chains.
This method achieves causal knowledge extraction through deductive reasoning performed in response to a user's question. This method is an alternative to the traditional method of translating texts into a formal representation before using their content for deductive question answering from texts. The main advantage of the ARISTA method is that since texts are not translated into any representation formalism retranslation is avoided whenever new linguistic or extra linguistic prerequisite knowledge has to be used for improving the text processing required for question answering.
An example text that is an extract from a medical physiology book in the domain of pneumonology and in particular of lung mechanics enhanced by a few general knowledge sentences was used as a first illustrative example of primitive knowledge discovery from texts (Kontos, 1992). The ARISTA system was able to answer questions from that text that require the chaining of causal knowledge acquired from the text and produced answers that were not explicitly stated in the input texts.

The use of Information Extraction
A system using information extraction from texts for QA was presented in Kontos and Malagardi [1999]. The system described had as ultimate aim the creation of flexible information extraction tools capable of accepting natural language questions and generating answers that contained information either directly extracted from the text or extracted after applying deductive inference. The domains examined were oceanography, medical physiology and ancient Greek law (Kontos and Malagardi, 1999). The system consisted of two main subsystems. The first subsystem achieved the extraction of knowledge from individual sentences that was similar to traditional information extraction from texts (Cowie and Lehnert, 1996; Grishman, 1997) while the second subsystem was based on a reasoning process that combines knowledge extracted by the first subsystem for answering questions without the use of a template representation.

QUESTION ANSWERING FOR MODEL DISCOVERY

The AROMA System
A modern development in the area of QA that points to the future is our implementation of the AROMA (ARISTA Oriented Model Adaptation) system. This system is a model-based QA system that may support researchers for the discovery of parameter values of procedural models of systems by answering “What if” questions. (Kontos et al, 2002). The concept of “What if” questions are considered here to involve the computation data of describing the behaviour of a simulated model of a system.
The knowledge discovery process relies on the search for causal chains that in turn relies on the search for sentences containing appropriate natural language phrases. In order to speed up the whole knowledge acquisition process the search algorithm described in Kontos and Malagardi [2001] was used for finding the appropriate sentences for chaining. The increase in speed results because the repeated sentence search is made a function of the number of words in the connecting phrases. This number is usually smaller than the number of sentences of the text that may be arbitrarily large.

The Knowledge Extraction Subsystem
This subsystem integrates partial causal knowledge extracted from a number of different texts. This knowledge is expressed in natural language using causal verbs such as “regulate”, “enhance” and “inhibit”. These verbs usually take as arguments entities such as entity names and process names that occur in the texts that we use for the applications. In this way causal relations are expressed between the entities, processes or entity-process pairs.
The input texts are submitted first to a preprocessing module of the subsystem that converts automatically each sentence into a form that shows word data with numerical information concerning the identification of the sentence that contains the word and its position in that sentence. This conversion has nothing to do with logical representation of the content of the sentences. It should be emphasized that we do not deviate from our ARISTA method with this conversion. We simply annotate each word with information concerning its position within the text. This form of sentences is then parsed and partial texts with causal knowledge are generated.

The Causal Reasoning Subsystem
The output of the first subsystem is used as input to the second subsystem that combines causal knowledge in natural language form to produce answers and model data by deduction not mentioned explicitly in the input text. The operation of this subsystem is based on the ARISTA method. The sentence fragments containing causal knowledge are parsed and the entity-process pairs are recognized. The user questions are processed and reasoning goals are extracted from them. The answers to the user questions that are generated automatically by the reasoning process contain explanations in natural language form. All this is accomplished by the chaining of causal statements using prerequisite knowledge such as ontology to support the reasoning process.

The Simulation Subsystem
The third subsystem is used for modelling the dynamics of a system specified on the basis of the texts processed by the first and second subsystem. The data of the model such as structure and parameter values are extracted from the input texts combined with prerequisite knowledge such as ontology and default process and entity knowledge. The solution of the equations describing the system is accomplished with a program that provides an interface with which the user may test the simulation outputs and manipulate the structure and the parameters of the model.

FUTURE TRENDS
The architecture of the AROMA system is pointing to future trends in the field of QA by serving among other things the processing of “What if” questions. These are questions about what will happen to a system under certain conditions. Implementing systems for the answering “What if” questions will be an important research goal in the future (Maybury 2003) .
Another future trend is the development of systems that may conduct an explanatory dialog with their human user by answering “Why” questions using the simulated behaviour of system models. A “Why question” seeks the reason for the occurrence of certain system behavior.
The work on model discovery QA systems paves the way towards important developments and justifies effort leading to the development of tools and resources aiming at the solution of the problems of model discovery based on larger and more complex texts. These texts may report experimental data that may be used to support the discovery and adaptation of models with computer systems.

CONCLUSION
A series of systems that can answer questions from various data or knowledge sources were briefly described. These systems provide a friendly interface to the user of information systems that is particularly important for users that are not computer experts. The line of development of systems starts with procedural semantics systems and leads to interfaces that support researchers for the discovery of model parameter values of simulated systems. If these efforts for more sophisticated human-computer interfaces succeed then a revolution may take place in the way research and development is conducted in many scientific fields. This revolution will make computer systems even more useful for research and development.

REFERENCES
Cooper, W. S. (1964). Fact Retrieval and Deductive Question–Answering Information Retrieval Systems. Journal of the ACM, Vol. 11, No. 2, pp. 117-137.
Cowie J., and Lehnert, W., (1996). Information Extraction. Communications of the ACM. Vol. 39, No. 1, pp. 80-91.
Diekema, A., R. (2003). What do You Mean? Finding Answers to Complex Questions. New Directions on Question Answering. Papers from 2003 AAAI Spring Symposium. The AAAI Press. USA, pp. 87-93.
Doan-Nguyen, H. and Kosseim, L. (2004). Improving the Precision of a Closed-Domain Question Answering System with Semantic Information. Proceedings of Researche d’ Information Assistee Ordinateur (RIAO-2004). pp. 850-859. Avignon, France. April 2004.
Feigenbaum, E., A. and Feldman, J. (1963). Computers and Thought. McGraw Hill. New York.
Green B. F. et al. (1961). BASEBALL: An Automatic Question Answerer. Proceedings of the Western Joint Computer Conference 19, pp. 219-224.
Grishman R., (1997). Information Extraction: Techniques and Challenges. In Pazienza, M. T. Information Extraction. LNAI Tutorial. Springer, pp. 10-27.
Harabagiu, S., M., Maiorano, S., J. and Pasca, M., A. (2003). Open-domain textual question answering techniques. Natural Language Engineering, Vol. 9 (3). Pp. 231-267.
Kontos J. and Papakonstantinou G., (1970). A question-answering system using program generation. In Proceedings of the ACM International Computing Symposium, Bonn, Germany, pp. 737-750.
Kontos J. and Kossidas A., (1971). On the Question-Answering System DELFI and its Application. Proceedings of the Symposium on Artificial Intelligence, Rome, Italy, pp. 31-36.
Kontos J. (1992) ARISTA: Knowledge Engineering with Scientific Texts. Information and Software Technology, Vol. 34, No 9, pp. 611-616.
Kontos J. and Malagardi I. (1999). Information Extraction and Knowledge Acquisition from Texts using Bilingual Question-Answering. Journal of Intelligent and Robotic Systems, Vol 26, No. 2, pp. 103-122, October.
Kontos J. and Malagardi I. (2001) A Search Algorithm for Knowledge Acquisition from Texts. HERCMA 2001, 5th Hellenic European Research on Computer Mathematics & its Applications Conference, Athens, Greece, pp. 226-230.
Kontos J., Elmaoglou A. and Malagardi I. (2002). ARISTA Causal Knowledge Discovery from Texts. Proceedings of the 5th International Conference on Discovery Science DS 2002, Luebeck, Germany, pp. 348-355.
Kontos, J., Malagardi, I., Peros, J. (2003). “The AROMA System for Intelligent Text Mining” HERMIS International Journal of Computers mathematics and its Applications. Vol. 4. pp.163-173. LEA.
Kontos, J. (2004). Artificial Intelligence. Chapter in Book “Cognitive Science: The New Science of the Mind”. Gutenbeng. Athens 2004. pp. 43-153 (in Greek).
Kosseim, L., Plamondon, L. and Guillemette, L., J. (2003). Answer Formulation for Question-Answering. Proceedings of the Sixteenth Conference of the Canadian Society for Computational Studies of Intelligence. (AI’2003). Lecture Notes in Artificial Intelligence no 2671, pp. 24-34. Springer Verlag. June 2003. Halifax Canada.
Maybury, M., T. (2003). Toward a Question answering Roadmap. New Directions on Question Answering. Papers from 2003 AAAI Spring Symposium. The AAAI Press. USA, pp. 8-11.
Nyberg, E. et al. (2002). The JAVELIN Question-Answering System at TREC 2002. NIST Special Publication:11th Text Retrieval Conference (TREC), 2002.
Plamondon, L. and Kosseim, L. (2002). QUANTUM: A Function-Based Question Answering System. Proceedings of The Fifteenth Canadian Conference on artificial Intelligence (AI’2002). Lecture Notes in artificial Intelligence no. 2338, pp.281-292. Springer Verlag. Berlin . May 2002. Calgary, Canada.
Popescu, A., Etzioni, O. and Kautz, H. (2003). Towards a Theory of Natural Language Interfaces to Databases. Proceedings of IUI’03, Miami, Florida, USA, pp. 149-157.
Ramakrishnan, G. et al. (2004). Is Question Answering an Acquired Skill? (2004). WWW2004. May 2004, New York, USA.
Roussinof, D., Robles-Flores, J., A. (2004). Web Question Answering: Technology and Business Applications. Proceedings of the Tenth Americas Conference on Information Systems. New York. August 2004.
Samsonova, M., Pisarev, A. and Blagov M. (2003). Processing of natural language queries to a relational database. Bioinformatics. Vol. 19 Suppl. 1. pp. i241-i249
Simmons R., F. (1970). Natural Language Question-Answering Systems: 1969. Computational Linguistics, Vol. 13, No 1, January, pp. 15-30.
Voorhees E., M. (2001). The Trec Question answering Track. Natural Language Engineering, Vol. 7, Issue 4.pp.361-378.
Waldinger, R. et al. (2003). Deductive Question Answering from Multiple Resources. New Directions in Question Answering, AAAI 2003.

Terms and Definitions

Ontology: A structure that represents taxonomic or meronomic relations between entities.
Question Answering System: A computer system that can answer a question posed to it by a human being using pre-stored information from a database, a text collection or a knowledge base.
Procedural Semantics: A method for the translation of a question by a computer program into a sequence of actions that retrieve or combine parts of information necessary for answering the question.
Causal Relation: A relation between the members of an entity-process pair where the first member is the cause of the second member that is the effect of the first member.
Causal Chain: A sequence of instances of causal relations such that the effect of each instance but the last one is the cause of the next one in sequence.
Model: A set of causal relations that specify the dynamic behavior of a system.
Explanation: A sequence of statements of the reasons for the behavior of the model of a system.
Model Discovery: The discovery of a set of causal relations that predict the behavior of a system.
“What if” question: A question about what will happen to a system under given conditions or inputs.
“Why” question: A question about the reason for the occurrence of certain system behavior.