Chan, Shuk Fong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 114-122). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Thesis Contributions --- p.5 / Chapter 1.3 --- Thesis Outline --- p.9 / Chapter 2 --- Background --- p.10 / Chapter 2.1 --- Mixed-Initiative Interactions --- p.11 / Chapter 2.2 --- Mixed-Initiative Spoken Dialog Systems --- p.14 / Chapter 2.2.1 --- Finite-state Networks --- p.16 / Chapter 2.2.2 --- Form-based Approaches --- p.17 / Chapter 2.2.3 --- Sequential Decision Approaches --- p.18 / Chapter 2.2.4 --- Machine Learning Approaches --- p.20 / Chapter 2.3 --- Understanding Mixed-Initiative Dialogs --- p.24 / Chapter 2.4 --- Cooperative Response Generation --- p.26 / Chapter 2.4.1 --- Plan-based Approach --- p.27 / Chapter 2.4.2 --- Constraint-based Approach --- p.28 / Chapter 2.5 --- Chapter Summary --- p.29 / Chapter 3 --- Mixed-Initiative Dialog Management in the ISIS system --- p.30 / Chapter 3.1 --- The ISIS Domain --- p.31 / Chapter 3.1.1 --- System Overview --- p.31 / Chapter 3.1.2 --- Domain-Specific Constraints --- p.33 / Chapter 3.2 --- Discourse and Dialog --- p.34 / Chapter 3.2.1 --- Discourse Inheritance --- p.37 / Chapter 3.2.2 --- Mixed-Initiative Dialogs --- p.41 / Chapter 3.3 --- Challenges and New Directions --- p.45 / Chapter 3.3.1 --- A Learning System --- p.46 / Chapter 3.3.2 --- Combining Interaction and Delegation Subdialogs --- p.49 / Chapter 3.4 --- Chapter Summary --- p.57 / Chapter 4 --- Understanding Mixed-Initiative Human-Human Dialogs --- p.59 / Chapter 4.1 --- The CU Restaurants Domain --- p.60 / Chapter 4.2 --- "Task Goals, Dialog Acts, Categories and Annotation" --- p.61 / Chapter 4.2.1 --- Task Goals and Dialog Acts --- p.61 / Chapter 4.2.2 --- Semantic and Syntactic Categories --- p.64 / Chapter 4.2.3 --- Annotating the Training Sentences --- p.65 / Chapter 4.3 --- Selective Inheritance Strategy --- p.67 / Chapter 4.3.1 --- Category Inheritance Rules --- p.67 / Chapter 4.3.2 --- Category Refresh Rules --- p.73 / Chapter 4.4 --- Task Goal and Dialog Act Identification --- p.78 / Chapter 4.4.1 --- Belief Networks Development --- p.78 / Chapter 4.4.2 --- Varying the Input Dimensionality --- p.80 / Chapter 4.4.3 --- Evaluation --- p.80 / Chapter 4.5 --- Procedure for Discourse Inheritance --- p.83 / Chapter 4.6 --- Chapter Summary --- p.86 / Chapter 5 --- Cooperative Response Generation in Mixed-Initiative Dialog Modeling --- p.88 / Chapter 5.1 --- System Overview --- p.89 / Chapter 5.1.1 --- State Space Generation --- p.89 / Chapter 5.1.2 --- Task Goal and Dialog Act Generation for System Response --- p.92 / Chapter 5.1.3 --- Response Frame Generation --- p.93 / Chapter 5.1.4 --- Text Generation --- p.100 / Chapter 5.2 --- Experiments and Results --- p.100 / Chapter 5.2.1 --- Subjective Results --- p.103 / Chapter 5.2.2 --- Objective Results --- p.105 / Chapter 5.3 --- Chapter Summary --- p.105 / Chapter 6 --- Conclusions --- p.108 / Chapter 6.1 --- Summary --- p.108 / Chapter 6.2 --- Contributions --- p.110 / Chapter 6.3 --- Future Work --- p.111 / Bibliography --- p.113 / Chapter A --- Domain-Specific Task Goals in CU Restaurants Domain --- p.123 / Chapter B --- Full list of VERBMOBIL-2 Dialog Acts --- p.124 / Chapter C --- Dialog Acts for Customer Requests and Waiter Responses in CU Restaurants Domain --- p.125 / Chapter D --- The Two Grammers for Task Goal and Dialog Act Identifi- cation --- p.130 / Chapter E --- Category Inheritance Rules --- p.143 / Chapter F --- Category Refresh Rules --- p.149 / Chapter G --- Full list of Response Trigger Words --- p.154 / Chapter H --- Evaluation Test Questionnaire for Dialog System in CU Restaurants Domain --- p.159 / Chapter I --- Details of the statistical testing Regarding Grice's Maxims and User Satisfaction --- p.161

Skyline has been proposed as an important operator for many applications, such as multi-criteria decision making, data mining and visualization, and user-preference queries. Due to its importance, skyline and its computation have received considerable attention from database research community recently. All the existing techniques, however, focus on the conventional databases. They are not applicable to online computation environment, such as data stream. In addition, the existing studies consider efficiency of skyline computation only, while the fundamental problem on the semantics of skylines still remains open. In this thesis, we study three problems of skyline computation: (1) online computing skyline over data stream; (2) skyline cube computation and its analysis; and (3) top-k most representative skyline. To tackle the problem of online skyline computation, we develop a novel framework which converts more expensive multiple dimensional skyline computation to stabbing queries in 1-dimensional space. Based on this framework, a rigorous theoretical analysis of the time complexity of online skyline computation is provided. Then, efficient algorithms are proposed to support ad hoc and continuous skyline queries over data stream. Inspired by the idea of data cube, we propose a novel concept of skyline cube which consists of skylines of all possible non-empty subsets of a given full space. We identify the unique sharing strategies for skyline cube computation and develop two efficient algorithms which compute skyline cube in a bottom-up and top-down manner, respectively. Finally, a theoretical framework to answer the question about semantics of skyline and analysis of multidimensional subspace skyline are presented. Motived by the fact that the full skyline may be less informative because it generally consists of a large number of skyline points, we proposed a novel skyline operator -- top-k most representative skyline. The top-k most representative skyline operator selects the k skyline points so that the number of data points, which are dominated by at least one of these k skyline points, is maximized. To compute top-k most representative skyline, two efficient algorithms and their theoretical analysis are presented.

Skyline has been proposed as an important operator for many applications, such as multi-criteria decision making, data mining and visualization, and user-preference queries. Due to its importance, skyline and its computation have received considerable attention from database research community recently. All the existing techniques, however, focus on the conventional databases. They are not applicable to online computation environment, such as data stream. In addition, the existing studies consider efficiency of skyline computation only, while the fundamental problem on the semantics of skylines still remains open. In this thesis, we study three problems of skyline computation: (1) online computing skyline over data stream; (2) skyline cube computation and its analysis; and (3) top-k most representative skyline. To tackle the problem of online skyline computation, we develop a novel framework which converts more expensive multiple dimensional skyline computation to stabbing queries in 1-dimensional space. Based on this framework, a rigorous theoretical analysis of the time complexity of online skyline computation is provided. Then, efficient algorithms are proposed to support ad hoc and continuous skyline queries over data stream. Inspired by the idea of data cube, we propose a novel concept of skyline cube which consists of skylines of all possible non-empty subsets of a given full space. We identify the unique sharing strategies for skyline cube computation and develop two efficient algorithms which compute skyline cube in a bottom-up and top-down manner, respectively. Finally, a theoretical framework to answer the question about semantics of skyline and analysis of multidimensional subspace skyline are presented. Motived by the fact that the full skyline may be less informative because it generally consists of a large number of skyline points, we proposed a novel skyline operator -- top-k most representative skyline. The top-k most representative skyline operator selects the k skyline points so that the number of data points, which are dominated by at least one of these k skyline points, is maximized. To compute top-k most representative skyline, two efficient algorithms and their theoretical analysis are presented.

FrameNet is used to enhance the performance of semantic QA systems. FrameNet is a linguistic resource that encapsulates Frame Semantics and provides scenario-based generalizations over lexical items that share similar semantic backgrounds. / Doctor of Philosophy

Skyline has been proposed as an important operator for many applications, such as multi-criteria decision making, data mining and visualization, and user-preference queries. Due to its importance, skyline and its computation have received considerable attention from database research community recently. All the existing techniques, however, focus on the conventional databases. They are not applicable to online computation environment, such as data stream. In addition, the existing studies consider efficiency of skyline computation only, while the fundamental problem on the semantics of skylines still remains open. In this thesis, we study three problems of skyline computation: (1) online computing skyline over data stream; (2) skyline cube computation and its analysis; and (3) top-k most representative skyline. To tackle the problem of online skyline computation, we develop a novel framework which converts more expensive multiple dimensional skyline computation to stabbing queries in 1-dimensional space. Based on this framework, a rigorous theoretical analysis of the time complexity of online skyline computation is provided. Then, efficient algorithms are proposed to support ad hoc and continuous skyline queries over data stream. Inspired by the idea of data cube, we propose a novel concept of skyline cube which consists of skylines of all possible non-empty subsets of a given full space. We identify the unique sharing strategies for skyline cube computation and develop two efficient algorithms which compute skyline cube in a bottom-up and top-down manner, respectively. Finally, a theoretical framework to answer the question about semantics of skyline and analysis of multidimensional subspace skyline are presented. Motived by the fact that the full skyline may be less informative because it generally consists of a large number of skyline points, we proposed a novel skyline operator -- top-k most representative skyline. The top-k most representative skyline operator selects the k skyline points so that the number of data points, which are dominated by at least one of these k skyline points, is maximized. To compute top-k most representative skyline, two efficient algorithms and their theoretical analysis are presented.

Skyline has been proposed as an important operator for many applications, such as multi-criteria decision making, data mining and visualization, and user-preference queries. Due to its importance, skyline and its computation have received considerable attention from database research community recently. All the existing techniques, however, focus on the conventional databases. They are not applicable to online computation environment, such as data stream. In addition, the existing studies consider efficiency of skyline computation only, while the fundamental problem on the semantics of skylines still remains open. In this thesis, we study three problems of skyline computation: (1) online computing skyline over data stream; (2) skyline cube computation and its analysis; and (3) top-k most representative skyline. To tackle the problem of online skyline computation, we develop a novel framework which converts more expensive multiple dimensional skyline computation to stabbing queries in 1-dimensional space. Based on this framework, a rigorous theoretical analysis of the time complexity of online skyline computation is provided. Then, efficient algorithms are proposed to support ad hoc and continuous skyline queries over data stream. Inspired by the idea of data cube, we propose a novel concept of skyline cube which consists of skylines of all possible non-empty subsets of a given full space. We identify the unique sharing strategies for skyline cube computation and develop two efficient algorithms which compute skyline cube in a bottom-up and top-down manner, respectively. Finally, a theoretical framework to answer the question about semantics of skyline and analysis of multidimensional subspace skyline are presented. Motived by the fact that the full skyline may be less informative because it generally consists of a large number of skyline points, we proposed a novel skyline operator -- top-k most representative skyline. The top-k most representative skyline operator selects the k skyline points so that the number of data points, which are dominated by at least one of these k skyline points, is maximized. To compute top-k most representative skyline, two efficient algorithms and their theoretical analysis are presented.

Thesis (M.S.)--State University of New York at Binghamton, Department of Computer Science, Thomas J. Watson School of Engineering and Applied Science, 2006. / Includes bibliographical references.

Thesis (Ph.D.) - Carleton University, 2007. / Includes bibliographical references (p. 220-226). Also available in electronic format on the Internet.

Le volume et la complexité des données générées par les systèmes d’information croissent de façon singulière dans les entrepôts de données. Le domaine de l’informatique décisionnelle (aussi appelé BI) a pour objectif d’apporter des méthodes et des outils pour assister les utilisateurs dans leur tâche de recherche d’information. En effet, les sources de données ne sont en général pas centralisées, et il est souvent nécessaire d’interagir avec diverses applications. Accéder à l’information est alors une tâche ardue, alors que les employés d’une entreprise cherchent généralement à réduire leur charge de travail. Pour faire face à ce constat, le domaine « Enterprise Search » s’est développé récemment, et prend en compte les différentes sources de données appartenant aussi bien au réseau privé d’entreprise qu’au domaine public (telles que les pages Internet). Pourtant, les utilisateurs de moteurs de recherche actuels souffrent toujours de du volume trop important d’information à disposition. Nous pensons que de tels systèmes pourraient tirer parti des méthodes du traitement naturel des langues associées à celles des systèmes de questions/réponses. En effet, les interfaces en langue naturelle permettent aux utilisateurs de rechercher de l’information en utilisant leurs propres termes, et d’obtenir des réponses concises et non une liste de documents dans laquelle l’éventuelle bonne réponse doit être identifiée. De cette façon, les utilisateurs n’ont pas besoin d’employer une terminologie figée, ni de formuler des requêtes selon une syntaxe très précise, et peuvent de plus accéder plus rapidement à l’information désirée. Un challenge lors de la construction d’un tel système consiste à interagir avec les différentes applications, et donc avec les langages utilisés par ces applications d’une part, et d’être en mesure de s’adapter facilement à de nouveaux domaines d’application d’autre part. Notre rapport détaille un système de questions/réponses configurable pour des cas d’utilisation d’entreprise, et le décrit dans son intégralité. Dans les systèmes traditionnels de l’informatique décisionnelle, les préférences utilisateurs ne sont généralement pas prises en compte, ni d’ailleurs leurs situations ou leur contexte. Les systèmes état-de-l’art du domaine tels que Soda ou Safe ne génèrent pas de résultats calculés à partir de l’analyse de la situation des utilisateurs. Ce rapport introduit une approche plus personnalisée, qui convient mieux aux utilisateurs finaux. Notre expérimentation principale se traduit par une interface de type search qui affiche les résultats dans un dashboard sous la forme de graphes, de tables de faits ou encore de miniatures de pages Internet. En fonction des requêtes initiales des utilisateurs, des recommandations de requêtes sont aussi affichées en sus, et ce dans le but de réduire le temps de réponse global du système. En ce sens, ces recommandations sont comparables à des prédictions. Notre travail se traduit par les contributions suivantes : tout d’abord, une architecture implémentée via des algorithmes parallélisés et qui prend en compte la diversité des sources de données, à savoir des données structurées ou non structurées dans le cadre d’un framework de questions/réponses qui peut être facilement configuré dans des environnements différents. De plus, une approche de traduction basée sur la résolution de contrainte, qui remplace le traditionnel langage-pivot par un modèle conceptuel et qui conduit à des requêtes multidimensionnelles mieux personnalisées. En outre, en ensemble de patrons linguistiques utilisés pour traduire des questions BI en des requêtes pour bases de données, qui peuvent être facilement adaptés dans le cas de configurations différentes. / The amount and complexity of data generated by information systems keep increasing in Warehouses. The domain of Business Intelligence (BI) aims at providing methods and tools to better help users in retrieving those data. Data sources are distributed over distinct locations and are usually accessible through various applications. Looking for new information could be a tedious task, because business users try to reduce their work overload. To tackle this problem, Enterprise Search is a field that has emerged in the last few years, and that takes into consideration the different corporate data sources as well as sources available to the public (e.g. World Wide Web pages). However, corporate retrieval systems nowadays still suffer from information overload. We believe that such systems would benefit from Natural Language (NL) approaches combined with Q&A techniques. Indeed, NL interfaces allow users to search new information in their own terms, and thus obtain precise answers instead of turning to a plethora of documents. In this way, users do not have to employ exact keywords or appropriate syntax, and can have faster access to new information. Major challenges for designing such a system are to interface different applications and their underlying query languages on the one hand, and to support users’ vocabulary and to be easily configured for new application domains on the other hand. This thesis outlines an end-to-end Q&A framework for corporate use-cases that can be configured in different settings. In traditional BI systems, user-preferences are usually not taken into account, nor are their specific contextual situations. State-of-the art systems in this field, Soda and Safe do not compute search results on the basis of users’ situation. This thesis introduces a more personalized approach, which better speaks to end-users’ situations. Our main experimentation, in this case, works as a search interface, which displays search results on a dashboard that usually takes the form of charts, fact tables, and thumbnails of unstructured documents. Depending on users’ initial queries, recommendations for alternatives are also displayed, so as to reduce response time of the overall system. This process is often seen as a kind of prediction model. Our work contributes to the following: first, an architecture, implemented with parallel algorithms, that leverages different data sources, namely structured and unstructured document repositories through an extensible Q&A framework, and this framework can be easily configured for distinct corporate settings; secondly, a constraint-matching-based translation approach, which replaces a pivot language with a conceptual model and leads to more personalized multidimensional queries; thirdly, a set of NL patterns for translating BI questions in structured queries that can be easily configured in specific settings. In addition, we have implemented an iPhone/iPad™ application and an HTML front-end that demonstrate the feasibility of the various approaches developed through a series of evaluation metrics for the core component and scenario of the Q&A framework. To this end, we elaborate on a range of gold-standard queries that can be used as a basis for evaluating retrieval systems in this area, and show that our system behave similarly as the well-known WolframAlpha™ system, depending on the evaluation settings.

This thesis describes advancements in question answering along three general directions: model architecture extensions, explainable question answering, and data augmentation. Chapter 2 describes the first state-of-the-art model for the Natural Questions dataset based on pretrained transformers. Chapters 3 and 4 describe extensions to the model architecture designed to accommodate long textual inputs and multimodal text+image inputs, establishing new state-of-the-art results on the Natural Questions and on the VCR dataset. Chapter 5 shows that significant improvements can be obtained with data augmentation on the SQuAD and Natural Questions dataset, introducing roundtrip consistency as a simple heuristic to improve the quality of synthetic data. In Chapters 6 and 7 we explore explainable question answering, demonstrating the usefulness of a new concrete kind of structured explanations, QED, and proposing a semantic analysis of why-questions in the Natural Questions, as a way of better understanding the nature of real world explanations. Finally, in Chapters 8 and 9 we delve into more exploratory data augmentation techniques for question answering. We look respectively at how straight-through gradients can be utilized to optimize roundtrip consistency in a pipeline of models on the fly, and at how very recent large language models like PaLM can be used to generate synthetic question answering datasets for new languages given as few as five representative examples per language.