Answer typing is an important aspect of the question answering process. Most commonly addressed with the use of a fixed set of possible answer classes via question classification, answer typing influences which answers will ultimately be selected as correct. Answer typing introduces the concept of type-appropriate responses. Such responses are plausible in the context of question answering when they are believable as answers to a given question. This notion of type-appropriateness is distinct from correctness, as there may exist many type-appropriate responses that are not correct answers. Type-appropriate responses can even exist for other kinds of queries that are not strictly questions. This work introduces class-free models of answer type for certain kinds of questions as well as models of type-appropriateness useful to the domain of information retrieval. Models built for both open-ended noun phrase questions and how-adjective questions are designed to evaluate the type-appropriateness of a candidate answer directly rather than via the use of an intermediary question class (as is done with question classification). Experiments show a meaningful improvement over alternative typing strategies for these kinds of questions. Ideas from these models are then applied outside of the domain of question answering in an effort to improve traditional information retrieval results. Experiments comparing reranked results with those of the Google search engine show improvements are made in those rare situations for which Google provides less than ideal results.

One way that examinees can gain an unfair advantage on a test is by having prior access to the test questions and their answers, known as preknowledge. Determining which examinees had preknowledge can be a difficult task. Sometimes, the compromised test content that examinees use to get preknowledge has mistakes in the answer key. Examinees who had preknowledge can be identified by determining whether they used this flawed answer key. This research consisted of three papers aimed at helping testing programs detect examinees who used a flawed answer key. The first paper developed three methods for detecting examinees who used a flawed answer key. These methods were applied to a real data set with a flawed answer key for which 37 of the 65 answers were incorrect. One requirement for these three methods was that the flawed answer key had to be known. The second paper studied the problem of estimating an unknown flawed answer key. Four methods of estimating the unknown flawed key were developed and applied to real and simulated data. Two of the methods had promising results. The methods of estimating an unknown flawed answer key required comparing examinees’ response patterns, which was a time-consuming process. In the third paper, OpenMP and OpenACC were used to parallelize this process, which allowed for larger data sets to be analyzed in less time.

This experimental research study examined the effects of the Question-Answer Relationships (QAR) taxonomy on ninth-grade students’ ability to answer comprehension questions. Participants included 32 incoming ninth-grade students who were required to attend summer school due to poor attendance, grades, and/or standardized test scores. Participants were randomly assigned to experimental and control groups. Experimental group participants received one week of initial strategy instruction followed by three weeks of maintenance activities. Results indicated that the strategy had a negative effect on students’ question-answering ability and raised questions regarding comprehension instruction, length of interventions, and the role of scaffolded support for a target population of adolescent readers. Discussion of the results revolves around interventions, QAR instruction, reading ability, and motivation of the participants.

No description available.

Answer set programming (ASP) is a declarative approach to solving search problems. Logic programming constitutes the foundation of ASP. ASP is not a proof-theoretical approach where you get solutions by answer substitutions. Instead, the problem is represented by a logic program in such a way that models of the program according to the answer set semantics correspond to solutions of the problem. Answer set solvers (Smodels, Cmodels, Clasp, and Dlv) are used for finding answer sets of a given program. Although users can write programs with variables for convenience, current answer set solvers work on ground logic programs where there are no variables. The grounding step of ASP generates a propositional instance of a logic program with variables. It may generate a huge propositional instance and make the search process of answer set solvers more difficult. Model generation theorem provers (Paradox, Darwin, and FM-Darwin) have the capability of producing a model when the first-order input theory is satisfiable. This work proposes the use of model generation theorem provers as computational engines for ASP. The main motivation is to eliminate the grounding step of ASP completely or to perform it more intelligently using the model generation system. Additionally, regardless of grounding, model generation systems may display better performance than the current solvers. The proposed method can be seen as lifting SAT-based ASP, where SAT solvers are used to compute answer sets, to the first-order level for tight programs. A completion procedure which transforms a logic program to formulas of first-order logic is utilized. Besides completion, other transformations which are necessary for forming a firstorder theory suitable for model generation theorem provers are investigated. A system called Completor is implemented for handling all the necessary transformations. The empirical results demonstrate that the use of Completor and the theorem provers together can be an eective way of computing answer sets. Especially, the run time results of Paradox in the experiments has showed that using Completor and Paradox together is favorable compared to answer set solvers. This advantage has been more clearly observed for programs with large propositional instances, since grounding can be a bottleneck for such programs.

Data Quality (DQ) has been a long-standing concern for a number of stakeholders in a variety of domains. It has become a critically important factor for the effectiveness of organisations and individuals. Previous work on DQ methodologies have mainly focused on either the analysis of structured data or the business-process level rather than analysing the data itself. Question and Answer Reports (QAR) are gaining momentum as a way to collect responses that can be used by data analysts, for instance, in business, education or healthcare. Various stakeholders benefit from QAR such as data brokers and data providers, and in order to effectively analyse and identify the common DQ problems in these reports, the various stakeholders' perspectives should be taken into account which adds another complexity for the analysis. This thesis investigates DQ in QAR through an in-depth DQ analysis and provide solutions that can highlight potential sources and causes of problems that result in "low-quality" collected data. The thesis proposes a DQ methodology that is appropriate for the context of QAR. The methodology consists of three modules: question analysis, medium analysis and answer analysis. In addition, a Question Design Support (QuDeS) framework is introduced to operationalise the proposed methodology through the automatic identification of DQ problems. The framework includes three components: question domain-independent profiling, question domain-dependent profiling and answers profiling. The proposed framework has been instantiated to address one example of DQ issues, namely Multi-Focal Question (MFQ). We introduce MFQ as a question with multiple requirements; it asks for multiple answers. QuDeS-MFQ (the implemented instance of QuDeS framework) has implemented two components of QuDeS for MFQ identification, these are question domain-independent profiling and question domain-dependent profiling. The proposed methodology and the framework are designed, implemented and evaluated in the context of the Carbon Disclosure Project (CDP) case study. The experiments show that we can identify MFQs with 90% accuracy. This thesis also demonstrates the challenges including the lack of domain resources for domain knowledge representation, such as domain ontology, the complexity and variability of the structure of QAR, as well as the variability and ambiguity of terminology and language expressions and understanding stakeholders or users need.

Preferences are fundamental to decision making and play an important role in artificial intelligence. Our research focuses on three group of problems based on the preference formalism Answer Set Optimization (ASO): preference aggregation problems such as computing optimal (near optimal) solutions, strategic behaviors in preference representation, and learning ranks (weights) for preferences. In the first group of problems, of interest are optimal outcomes, that is, outcomes that are optimal with respect to the preorder defined by the preference rules. In this work, we consider computational problems concerning optimal outcomes. We propose, implement and study methods to compute an optimal outcome; to compute another optimal outcome once the first one is found; to compute an optimal outcome that is similar to (or, dissimilar from) a given candidate outcome; and to compute a set of optimal answer sets each significantly different from the others. For the decision version of several of these problems we establish their computational complexity. For the second topic, the strategic behaviors such as manipulation and bribery have received much attention from the social choice community. We study these concepts for preference formalisms that identify a set of optimal outcomes rather than a single winning outcome, the case common to social choice. Such preference formalisms are of interest in the context of combinatorial domains, where preference representations are only approximations to true preferences, and seeking a single optimal outcome runs a risk of missing the one which is optimal with respect to the actual preferences. In this work, we assume that preferences may be ranked (differ in importance), and we use the Pareto principle adjusted to the case of ranked preferences as the preference aggregation rule. For two important classes of preferences, representing the extreme ends of the spectrum, we provide characterizations of situations when manipulation and bribery is possible, and establish the complexity of the problem to decide that. Finally, we study the problem of learning the importance of individual preferences in preference profiles aggregated by the ranked Pareto rule or positional scoring rules. We provide a polynomial-time algorithm that finds a ranking of preferences such that the ranked profile correctly decided all the examples, whenever such a ranking exists. We also show that the problem to learn a ranking maximizing the number of correctly decided examples is NP-hard. We obtain similar results for the case of weighted profiles.

Knowledge representation and search are two fundamental areas of artificial intelligence. Knowledge representation is the area of artificial intelligence which deals with capturing, in a formal language, the properties of objects and the relationships between objects. Search is a systematic examination of all possible candidate solutions to a problem that is described as a theory in some knowledge representation formalism. We compare traditional declarative programming formalisms such as PROLOG and DATALOG with answer-set programming formalisms such as logic programming with stable model semantic. In this thesis we develop an answer-set formalism we can DC. The logic of DC is based on the logic of prepositional schemata and a version of Closed World Assumption. Two important features of the DC logic is that it supports modeling of the cardinalities of sets and Horn clauses. These two features facilitate modeling of search problems. The DC system includes and implementation of a grounder and a solver. The grounder for the DC system grounds instances of problems retaining the structure of the cardinality of sets. The resulting theories are thus more concise. In addition, the solver for the DC system utilizes the structure of cardinality of sets to perform more efficient search. The second feature, Horn clauses, are used when transitive closure will eliminate the need for additional variables. The semantics of the Horn clauses are retained in the grounded theories. This also results in more concise theories. Our goal in developing DC is to provide the computer science community with a system which facilitates modeling of problems, is easy to use, is efficient and captures the class of problems in NP-search. We show experimental results comparing DC to other systems. These results show that DC is always competitive with state-of-the-art answer-set programming systems and for many problems DC is more efficient.

Décrypter le fonctionnement des réseaux biologiques est une des missions centrales de la biologie des systèmes. En particulier, les réseaux de transduction du signal sont essentiels pour la compréhension de la réponse cellulaire à des perturbations externes ou internes. Pour faire face à la complexité de ces réseaux, des modélisations aussi bien numériques que formelles sont nécessaires. Nous proposons un cadre de modélisation formelle, dans le cadre de réseaux logiques, afin d'obtenir des prédictions robustes sur le comportement et le contrôle des voies de signalisation. Nous modélisons la réponse des réseaux logiques de signalisation par du raisonnement automatique à l'aide de Programmation par Ensembles-Réponses (Answer Set Programming, ASP). ASP fournit un langage déclaratif pour la modélisation de divers problèmes de représentation des connaissances et de raisonnement. Des solveurs permettent plusieurs modes de raisonnement pour étudier la multitude d'ensembles réponses. En s'appuyant sur la richesse du langage de modélisation et ses capacités de résolution très efficaces, nous utilisons ASP pour modéliser et résoudre trois problèmes dans le contexte des réseaux logiques de signalisation: apprentissage de réseaux booléens, calculs de plan d'expériences, et l'identification des contrôleurs. Globalement, la contribution de cette thèse est de trois ordres. Premièrement, nous introduisons un cadre formel pour la caractérisation et le raisonnement sur la réponse des réseaux logiques de signalisation. Deuxièmement, nous contribuons à une liste croissante d'applications réussies d'ASP en biologie des systèmes. Troisièmement, nous présentons un logiciel fournissant un pipeline complet de raisonnement automatisé sur la réponse des réseaux logiques de signalisation. / Deciphering the functioning of biological networks is one of the central tasks in systems biology. In particular, signal transduction networks are crucial for the understanding of the cellular response to external and internal perturbations. Importantly, in order to cope with the complexity of these networks, mathematical and computational modeling is required. We propose a computational modeling framework in order to achieve more robust discoveries in the context of logical signaling networks. More precisely, we focus on modeling the response of logical signaling networks by means of automated reasoning using Answer Set Programming (ASP). ASP provides a declarative language for modeling various knowledge representation and reasoning problems. Moreover, available ASP solvers provide several reasoning modes for assessing the multitude of answer sets. Therefore, leveraging its rich modeling language and its highly efficient solving capacities, we use ASP to address three challenging problems in the context of logical signaling networks: learning of (Boolean) logical networks, experimental design, and identification of intervention strategies. Overall, the contribution of this thesis is three-fold. Firstly, we introduce a mathematical framework for characterizing and reasoning on the response of logical signaling networks. Secondly, we contribute to a growing list of successful applications of ASP in systems biology. Thirdly, we present a software providing a complete pipeline for automated reasoning on the response of logical signaling networks.

Avec l'augmentation des connaissances disponibles sur Internet est apparue la difficulté d'obtenir une information. Les moteurs de recherche permettent de retourner des pages Web censés contenir l'information désirée à partir de mots clés. Toutefois il est encore nécessaire de trouver la bonne requête et d'examiner les documents retournés. Les systèmes de questions réponses ont pour but de renvoyer directement une réponse concise à partir d'une question posée en langue naturelle. La réponse est généralement accompagnée d'un passage de texte censé la justifier. Par exemple, pour la question « Quel est le réalisateur d'Avatar ? » la réponse « James Cameron » peut être renvoyée accompagnée de « James Cameron a réalisé Avatar. ». Cette thèse se focalise sur la validation de réponses qui permet de déterminer automatiquement si la réponse est valide. Une réponse est valide si elle est correcte (répond bien à la question) et justifiée par le passage textuel. Cette validation permet d'améliorer les systèmes de questions réponses en ne renvoyant à l'utilisateur que les réponses valides. Les approches permettant de reconnaître les réponses valides peuvent se décomposer en deux grandes catégories : -les approches utilisant un formalisme de représentation particulier de la question et du passage dans lequel les structures sont comparées ;-les approches suivant une approche par apprentissage qui combinent différents critères d'ordres lexicaux ou syntaxiques. Dans le but d'identifier les différents phénomènes sous tendant la validation de réponses, nous avons participé à la création d'un corpus annoté manuellement. Ces phénomènes sont de différentes natures telle que la paraphrase ou la coréférence. On peut aussi remarquer que les différentes informations sont réparties sur plusieurs phrases, voire sont manquantes dans les passages contenant la réponse. Une deuxième étude de corpus de questions a porté sur les différentes informations à vérifier afin de détecter qu'une réponse est valide. Cette étude a montré que les trois phénomènes les plus fréquents sont la vérification du type de la réponse, la date et le lieu contenus dans la question. Ces différentes études ont permis de mettre au point notre système de validation de réponses qui s'appuie sur une combinaison de critères. Certains critères traitent de la présence dans le passage des mots de la question ce qui permet de pointer la présence des informations de la question. Un traitement particulier a été effectué pour les informations de date en détectant une réponse comme n'étant pas valide si le passage ne contient pas la date contenue dans la question. D'autres critères, dont la proximité dans le passage des mots de la question et de la réponse, portent sur le lien entre les différents mots de la question dans le passage. Le second grand type de vérification permet de mesurer la compatibilité entre la réponse et la question. Un certain nombre de questions attendent une réponse étant d'un type particulier. La question de l'exemple précédent attend ainsi un réalisateur en réponse. Si la réponse n'est pas de ce type alors elle est incorrecte. Comme cette information peut ne pas se trouver dans le passage justificatif, elle est recherchée dans des documents autres à l'aide de la structure des pages Wikipédia, en utilisant des patrons syntaxiques ou grâce à des fréquences d'apparitions du type et de la réponse dans des documents. La vérification du type est particulièrement efficace puisqu'elle effectue 80 % de bonnes détections. La vérification de la validité des réponses est également pertinente puisque lors de la participation à une campagne d'évaluation, AVE 2008, le système s'est placé parmi les meilleurs toutes langues confondues. La dernière contribution a consisté à intégrer le module de validation dans un système de questions réponses, QAVAL. Dans ce cadre de nombreuses réponses sont extraites par QAVAL et ordonnées grâce au module de validation de réponses. Le système n'est plus utilisé afin de détecter les réponses valides mais pour fournir un score de confiance à chaque réponse. Le système QAVAL peut ainsi aussi bien être utilisé en effectuant des recherches dans des articles de journaux que dans des articles issus du Web. Les résultats sont assez bons puisqu'ils dépassent ceux obtenus par un simple ordonnancement des réponses de près de 50 %. / Question answering systems extract precise answers from a set of documents, and return the answers along with text snippets which justify them. For example, to the question "Who is the director of Avatar?" The answer "James Cameron" may be returned with "Avatar by James Cameron.".The answer validation detect automatically if the answer is valid ie. if it is correct (responds to the question) and justified by the text passage. This validation allows to improve the question answering systems by producing only valid answers.Two kind of methods can be used to detect right answers : -approaches using specific representation formalism of the question and the passage in which the structures are compared;-learning approaches that combines lexical and syntactic features.To identify the phenomena that characterize the answer validation, we built a manually annotated corpus. Differents phenomena can be seen like paraphrasing, coreference or that the information is spread in different sentences or documents. A second corpus aims to identify the different informations to be checked to valid an answer. This study showed that the three mains phenomena are the answer type, the date and place of the question.These studies have helped to develop our answer validation system which is based on a combination of features. The first one estimates the proportion of common terms in the snippet and the question, the second one measures the proximity of these terms and the answer. The second kind of features measure the compatibility between the answer and the question. Numerous questions wait for answers of an explicit type. For example, the question “Which president succeeded to Jacques Chirac?” requires an instance of president as answer.If the answer is not of this type then it is incorrect. The method aims at verifying that an answer given by a system corresponds to the given type. This verification is done by combining features provided by different methods. The first types of feature are statistical and compute the presence rate of both the answer and the type in documents, other features rely on named entity recognizers and the last criteria are based on the use of Wikipedia. Type checking is particularly effective because it makes 80 % correct detections. The final contribution was to integrate the validation module in a question answering system, QAVAL. Many answers are retrieved by QAVAL and ordered through the answers validation module. The module provide a confidence score to each response. QAVAL can be used both by researching the information in newspaper articles and in articles from the Web. The results are good, exceeding those obtained by a simple answer ranking from nearly 50%.