Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 10 of 16
-
ItemAutomatic instant messaging dialogue using statistical models and dialogue acts( 2008)Instant messaging dialogue is used for communication by hundreds of millions of people worldwide, but has received relatively little attention in computational linguistics. We describe methods aimed at providing a shallow interpretation of messages sent via instant messaging. This is done by assigning labels known as dialogue acts to utterances within messages. Since messages may contain more than one utterance, we explore automatic message segmentation using combinations of parse trees and various statistical models to achieve high accuracy for both classification and segmentation tasks. Finally, we gauge the immediate usefulness of dialogue acts in conversation management by presenting a dialogue simulation program that uses dialogue acts to predict utterances during a conversation. The predictions are evaluated via qualitative means where we obtain very encouraging results.
-
ItemThe logic of bunched implications: a memoir( 2006)This is a study of the semantics and proof theory of the logic of bunched implications (BI), which is promoted as a logic of (computational) resources, and is a foundational component of separation logic, an approach to program analysis. BI combines an additive, or intuitionistic, fragment with a multiplicative fragment. The additive fragment has full use of the structural rules of weakening and contraction, and the multiplicative fragment has none. Thus it contains two conjunctive and two implicative connectives. At various points, we illustrate a resource view of BI based upon the Kripke resource semantics. Our first original contribution is the formulation of a proof system for BI in the newly developed proof-theoretical formalism of the calculus of structures. The calculus of structures is distinguished by its employment of deep inference, but we already see deep inference in a limited form in the established proof theory for BI. We show that our system is sound with respect to the elementary Kripke resource semantics for BI, and complete with respect to a formulation of the partially-defined Kripke resource semantics. Our second contribution is the development from a semantic standpoint of preliminary ideas for a hybrid logic of bunched implications (HBI). We give a Kripke semantics for HBI in which nominal propositional atoms can be seen as names for resources, rather than as names for locations, as is the case with related proposals for BI-Loc and for intuitionistic hybrid logic.
-
ItemLocal search methods for constraint problems( 2008-02)This thesis investigates the use of local search methods in solving constraint problems. Such problems are very hard in general and local search offers a useful and successful alternative to existing techniques. The focus of the thesis is to analyze the techniques of invariants used in local search. The use of invariants have recently become the cornerstone of local search technology as they provide a declarative way to specify incremental algorithms. We have produced a series of program libraries in C++ known as the One-Way-Solver. The One-Way-Solver includes the implementation of incremental data structures and is a useful tool for the implementation of local search. The One-Way-Solver is applied to two challenging constraint problems, the Boolean Satisfiability Testing (SAT) and university course timetabling problems.
-
ItemUsing minimal recursion semantics in Japanese question answering( 2006-09)Question answering is a research field with the aim of providing answers to a user’s question, phrased in natural language. In this thesis I explore some techniques used in question answering, working towards the twin goals of using deep linguistic knowledge robustly as well as using language-independent methods wherever possible. While the ultimate aim is cross-language question answering, in this research experiments are conducted over Japanese data, concentrating on factoid questions. The two main focus areas, identified as the two tasks most likely to benefit from linguistic knowledge, are question classification and answer extraction. In question classification, I investigate the issues involved in the two common methods used for this task—pattern matching and machine learning. I find that even with a small amount of training data (2000 questions), machine learning achieves better classification accuracy than pattern matching with much less effort. The other issue I explore in question classification is the classification accuracy possible with named entity taxonomies of different sizes and shapes. Results demonstrate that, although the accuracy decreases as the taxonomy size increases, the ability to use soft decision making techniques as well as high accuracies achieved in certain classes make larger, hierarchical taxonomies a viable option. For answer extraction, I use Robust Minimal Recursion Semantics (RMRS) as a sentence representation to determine similarity between questions and answers, and then use this similarity score, along with other information discovered during comparison, to score and rank answer candidates. Results were slightly disappointing, but close examination showed that 40% of errors were due to answer candidate extraction, and the scoring algorithm worked very well. Interestingly, despite the lower accuracy achieved during question classification, the larger named entity taxonomies allowed much better accuracy in answer extraction than the smaller taxonomies.
-
ItemImproving the efficiency and capabilities of document structuring( 2007)Natural language generation (NLG), the problem of creating human-readable documents by computer, is one of the major fields of research in computational linguistics The task of creating a document is extremely common in many fields of activity. Accordingly, there are many potential applications for NLG - almost any document creation task could potentially be automated by an NLG system. Advanced forms of NLG could also be used to generate a document in multiple languages, or as an output interface for other programs, which might ordinarily produce a less-manageable collection of data. They may also be able to create documents tailored to the needs of individual users. This thesis deals with document structure, a recent theory which describes those aspects of a document’s layout which affect its meaning. As well as its theoretical interest, it is a useful intermediate representation in the process of NLG. There is a well-defined process for generating a document structure using constraint programming. We show how this process can be made considerably more efficient. This in turn allows us to extend the document structuring task to allow for summarisation and finer control of the document layout. This thesis is organised as follows. Firstly, we review the necessary background material in both natural language processing and constraint programming.
-
ItemOn designing a mobile robot for RoboCup( 2006-03)The Roobots are a robot soccer team which participated in the RoboCup small-sized robot league competition in the years 2000, 2001 and 2002, when they finished in fourth place. This thesis describes the design of the robots in the 2002 team. Design issues for mobile robots in the RoboCup small-sized robot league are reviewed. The design decisions are presented. Finally, some lessons learnt for system design and project management from the three years of competition are presented.
-
ItemAgent-based approaches to pedestrian modelling( 2007-02)This thesis investigates the early stages of the software development process for agent-based models of pedestrian behaviour. Planning for pedestrians is becoming more important as planners and engineers become more aware of the sustainability and environmental aspects of transport and infrastructure. It is also necessary for the planning and management of pedestrian areas and events. Pedestrian behaviour is more difficult to model than other transport modes as it is not as constrained and operates at a finer scale. Many approaches have been developed for modelling pedestrian behaviour. The simplest involve a single mathematical equation taking into account area and attractiveness of an area to calculate the maximum capacity. More complicated mathematical models involving differential equations have also been used. Agent-based modelling is a recent development in modelling and simulation. These simulations contain agents who interact with each other and the environment in which they are situated. Their similarity to human societies has led to their use for many social applications. Many modellers are unsure of what agents are and how to develop models using them. In some cases, agents may be useful. In other cases, the model outputs and realism may not offset the learning curve, development time, and increased complexity of an agent-based model. (For complete abstract open document)
-
ItemShadowboard: an agent architecture for enacting a sophisticated digital self( 2001-09)In recent years many people have built Personal Assistant Agents, Information Agents and the like, and have simply added them to the operating system as auxiliary applications, without regard to architecture. This thesis argues that an agent architecture, one designed as a sophisticated representation of an individual user, should be embedded deep in the device system software, with at least equal status to the GUI – the graphical user interface. A sophisticated model of the user is then built, drawing upon contemporary Analytical Psychology – the Psychology of Subselves. The Shadowboard Agent architecture is then built upon that user model, drawing both structural and computational implications from the underlying psychology. An XML DTD file named Shadowboard.dtd is declared as a practical manifestation of the semantics of Shadowboard. An implementation of the Shadowboard system is mapped out, via a planned conversion of two existing integrated systems: SlimWinX, an event-driven GUI system; and XSpaces, an object-oriented tuplespace system with Blackboard-like features. The decision making mechanism passes logic terms and contraints between the various sub-agent components (some of which take on the role of Constraint Solvers), giving this agent system some characteristics of a Generalised Constraint Solver. A Shadowboard agent (built using the system) consists of a central controlling autonomous agent named the Aware Ego Agent, and any number of sub-agents, which collectively form an integrated but singular whole agent modelled on the user called the Digital Self. One such whole-agent is defined in a file named DigitalSelf.xml – which conforms to the schema in Shadowboard.dtd - which offers a comprehensive and generic representation of a user’s stance in a 24x7 network, in particular - the Internet. Numerous types of Shadowboard sub-agents are declared.
-
ItemLinguistic data models: presentation and representation( 2006-09)When field linguists describe undocumented languages, they produce written artefacts including word lists, interlinear texts, syntax trees and inflectional paradigms. Increasingly, linguists are digitising these artefacts and placing them in large data-stores to improve access. In contrast to the physical media that is stored in libraries, the techniques for archiving digital media are far less mature. The ad hoc nature of curation practices for digital resources is a significant concern for those involved in archiving language data. This concern led to the formation of EMELD to describe best practices for field linguists who are creating digital resources. Even field linguists who are aware of archival issues struggle with digitisation. In particular, poor digitisation of linguistic objects inhibits linguists who might wish to reuse these items.
-
ItemA formal framework for linguistic tree query( 2006-02)The analysis of human communication, in all its forms, increasingly depends on large collections of texts and transcribed recordings. These collections, or corpora, are often richly annotated with structural information. These datasets are extremely large so manual analysis is only successful up to a point. As such, significant effort has recently been invested in automatic techniques for extracting and analyzing these massive data sets. However, further progress on analytical tools is confronted by three major challenges. First, we need the right data model. Second, we need to understand the theoretical foundations of query languages on that data model. Finally, we need to know the expressive requirements for general purpose query language with respect to linguistics. This thesis has addressed all three of these issues. Specifically, this thesis studies formalisms used by linguists and database theorists to describe tree structured data. Specifically, Propositional dynamic logic and monadic second-order logic. These formalisms have been used to reason about a number of tree querying languages and their applicability to the linguistic tree query problem. We identify a comprehensive set of linguistic tree query requirements and the level of expressiveness needed to implement them. The main result of this study is that the required level of expressiveness of linguistic tree query is that of the first-order predicate calculus over trees. This formal approach has resulted in a convergence between two seemingly disparate fields of study. Further work in the intersection of linguistics and database theory should also pave the way for theoretically well-founded future work in this area. This, in turn, will lead to better tools for linguistic analysis and data management, and more comprehensive theories of human language.