Search

Imagine a machine, equipped with sensors, receiving a stream of sensory information. It must, somehow, make sense of this stream of sensory data. But what, exactly, does this involve? We have an intuitive understanding of what is involved in “making sense” of sensory data – but can we specify precisely what is involved? Can this intuitive notion be formalized? In this thesis, we make three contributions. First, we provide a precise formalization of what it means to “make sense” of a sensory sequence. According to our definition, making sense means constructing a symbolic causal theory that explains the sensory sequence and satisfies a set of unity conditions that were inspired by Kant’s discussion in the first half of the Critique of Pure Reason. According to our interpretation, making sense of sensory input is a type of program synthesis, but it is unsupervised program synthesis. Our second contribution is a computer implementation, the Apperception Engine, that was designed to satisfy our requirements for making sense of a sensory sequence. Our system is able to produce interpretable human-readable causal theories from very small amounts of data, because of the strong inductive bias provided by the Kantian unity constraints. A causal theory produced by our system is able to predict future sensor readings, as well as retrodict earlier readings, and impute missing sensory readings. In fact, it is able to do all three tasks simultaneously. The engine is implemented in Answer Set Programming (ASP) and induces theories expressed in an extension of Datalog that includes causal rules and constraints. We test the engine in a diverse variety of domains, including cellular automata, rhythms and simple nursery tunes, multi-modal binding problems, occlusion tasks, and sequence induction IQ tests. In each domain, we test our engine’s ability to predict future sensor values, retrodict earlier sensor values, and impute missing sensory data. The Apperception Engine performs well in all these domains, significantly out-performing neural net baselines. These results are significant because neural nets typically struggle to solve the binding problem (where information from different modalities must somehow be combined together into different aspects of one unified object) and fail to solve occlusion tasks (in which objects are sometimes visible and sometimes obscured from view). We note in particular that in the sequence induction IQ tasks, our system achieves human-level performance. This is notable because the Apperception Engine was not designed to solve these IQ tasks; it is not a bespoke hand-engineered solution to this particular domain. – Rather, it is a general purpose system that attempts to make sense of any sensory sequence, that just happens to be able to solve these IQ tasks “out of the box”. Our third contribution is a major extension of the engine to handle noisy and ambiguous data. While the initial implementation assumes the sensory input has already been preprocessed into ground atoms of first-order logic, our extension makes sense of raw unprocessed input – a sequence of pixel images from a video camera, for example. The resulting system is a neuro-symbolic framework for distilling interpretable theories out of streams of raw, unprocessed sensory experience.

Logic Programming (LP) and Argumentation are two paradigms for knowledge representation and reasoning under incomplete information. Even though the two paradigms share common features, they constitute mostly separate areas of research. In this thesis, we present novel developments in Argumentation, in particular in Assumption-Based Argumentation (ABA) and Abstract Argumentation (AA), and show how they can 1) extend the understanding of the relationship between the two paradigms and 2) provide solutions to problematic reasoning outcomes in LP. More precisely, we introduce assumption labellings as a novel way to express the semantics of ABA and prove a more straightforward relationship with LP semantics than found in previous work. Building upon these correspondence results, we apply methods for argument construction and conflict detection from ABA, and for conflict resolution from AA, to construct justifications of unexpected or unexplained LP solutions under the answer set semantics. We furthermore characterise reasons for the non-existence of stable semantics in AA and apply these findings to characterise different scenarios in which the computation of meaningful solutions in LP under the answer set semantics fails.

We propose methods on two fundamental graph theoretic problems: (1) network comparison, and (2) network modelling. Our methods are applied to five real-world network types, with an emphasis on world trade networks (WTNs), which we choose due to the world's current economic crisis. Finding topological similarities of complex networks is computationally intractable due to NP-Completeness of the subgraph isomorphism problem. Hence, simple heuristics have been used for this purpose. The most sophisticated heuristics are based on graph spectra and small subnetworks including graphlets. Among these, graphlets are preferred since spectra do not provide a direct real-world interpretation of network structure. However, current graphlet-based techniques can be improved. We improve graphlet-based heuristics by defining a new network topology descriptor, Graphlet Correlation Matrix (GCM), which eliminates all redundancies and quantifies the dependencies in graphlet properties. Then, we introduce a new network distance measure, Graphlet Correlation Distance (GCD), that compares GCMs of two networks. We show that GCD has the best network classification performance, is highly noise-tolerant, and is computationally efficient. Using this methodology, we highlight a three-layer organization in the WTNs: core, broker, and periphery. Furthermore, we uncover the link between the dynamic changes in oil price and trade network topology. Network models should shed light on the rules governing the formation of real networks. Using GCD, we identify models that fit five real-world network types. However, none of these standard network models fit WTNs. Hence, we introduce two new network models: one that mimics the Gravity Model of Trade, and the other that mimics brokerage / peripheral positioning of a country in WTN. Also, we show that economic wealth indicators of a country are predictive of its future brokerage position. Finally, we use exponential-family random graph modelling approach to build a generic framework that enables modelling based on any graphlet property.

This thesis examines the productive application of networks towards proteomics, with a specific biological focus on liver cancer. Contempory proteomics (shot- gun) is plagued by coverage and consistency issues. These can be resolved via network-based approaches. The application of 3 classes of network-based approaches are examined: A traditional cluster based approach termed Proteomics Expansion Pipeline), a generalization of PEP termed Maxlink and a feature-based approach termed Proteomics Signature Profiling. PEP is an improvement on prevailing cluster-based approaches. It uses a state- of-the-art cluster identification algorithm as well as network-cleaning approaches to identify the critical network regions indicated by the liver cancer data set. The top PARP1 associated-cluster was identified and independently validated. Maxlink allows identification of undetected proteins based on the number of links to identified differential proteins. It is more sensitive than PEP due to more relaxed requirements. Here, the novel roles of ARRB1/2 and ACTB are identified and discussed in the context of liver cancer. Both PEP and Maxlink are unable to deal with consistency issues, PSP is the first method able to deal with both, and is termed feature-based since the network- based clusters it uses are predicted independently of the data. It is also capable of using real complexes or predicted pathway subnets. By combining pathways and complexes, a novel basis of liver cancer progression implicating nucleotide pool imbalance aggravated by mutations of key DNA repair complexes was identified. Finally, comparative evaluations suggested that pure network-based methods are vastly outperformed by feature-based network methods utilizing real complexes. This is indicative that the quality of current networks are insufficient to provide strong biological rigor for data analysis, and should be carefully evaluated before further validations.

The actions and interactions of independently acting agents in a multi-agent system must be managed if the agents are to function effectively in their shared environment. Norms, which define the obligatory, prohibited and permitted actions for an agent to perform, have been suggested as a possible method for regulating the actions of agents. Norms are local rules designed to govern the actions of individual agents whilst also allowing the agents to achieve a coherent global behaviour. However, there appear to be very few instances of norm-governed multi-agent systems beyond theoretical examples. We describe an implementation strategy for allowing autonomous agents to take a set of norms into account when determining their actions. These norms are implemented using directives, which are local rules specifying actions for an agent to perform depending on its current state. Agents using directives are implemented in a simulation test bed, called Sinatra. Using Sinatra, we investigate the ability of directives to manage agent actions. We begin with directives to manage agent interactions. We find that when agents rely on only local rules they will encounter situations where the local rules are unable to achieve the desired global behaviour. We show how a centralised control mechanism can be used to manage agent interactions that are not successfully handled by directives. Controllers, with a global view of the interaction, instruct the individual agents how to act. We also investigate the use of an existing planning tool to implement the resolution mechanism of a controller. We investigate the ability of directives to coordinate the actions of agents in order to achieve a global objective more effectively. Finally, we present a case study of how directives can be used to determine the actions of autonomous mobile robots.

In this thesis we consider generic tools and techniques for the proof-theoretic investigation of not necessarily normal modal logics based on minimal, intuitionistic or classical propositional logic. The underlying framework is that of ordinary symmetric or asymmetric two-sided sequent calculi without additional structural connectives, and the point of interest are the logical rules in such a system. We introduce the format of a sequent rule with context restrictions and the slightly weaker format of a shallow rule. The format of a rule with context restrictions is expressive enough to capture most normal modal logics in the S5 cube, standard systems for minimal, intuitionistic and classical propositional logic and a wide variety of non-normal modal logics. For systems given by such rules we provide sufficient criteria for cut elimination and decidability together with generic complexity results. We also explore the expressivity of such systems with the cut rule in terms of axioms in a Hilbert-style system by exhibiting a corresponding syntactically defined class of axioms along with automatic translations between axioms and rules. This enables us to show a number of limitative results concerning amongst others the modal logic S5. As a step towards a generic construction of cut free and tractable sequent calculi we then introduce the notion of cut trees as representations of rules constructed by absorbing cuts. With certain limitations this allows the automatic construction of a cut free and tractable sequent system from a finite number of rules. For cases where such a system is to be constructed by hand we introduce a graphical representation of rules with context restrictions which simplifies this process. Finally, we apply the developed tools and techniques and construct new cut free sequent systems for a number of Lewis’ conditional logics extending the logic V. The systems yield purely syntactic decision procedures of optimal complexity and proofs of the Craig interpolation property for the logics at hand.

In this thesis, a combination of skeletonisation and graph matching techniques, coupled with a blend of supervised and unsupervised learning methodology is applied to the task of characterising and classifying natural shapes. A novel navigation-based skeletonisation algorithm is used to gather low level structural and morphological information about the shape. Subsequently, the data are converted into a series of attributed graphs, which characterise the image. Graphs of the same type can then be compared using an approximate graph matcher, which identifies a degree of similarity between them. Each degree of similarity corresponds to a data point in a conceptual space (as defined by Gärdenfors). The proposed method is applied to two distinct problems; the classification of leaf types, and the characterisation of river networks. The classification and characterisation systems are tested on a database of images of leaves and a collection of satellite images respectively. The novel navigation-based skeletonisation algorithm features several advantages; first, it allows the collection of topological and morphological information on the fly. This eliminates the need for any post-processing on the extracted skeletons. In addition, the adaptation of the algorithm to suit different applications is facilitated by the fact that any sort of morphological information can be included without alterations to the function of the algorithm. The conversion of the skeletons to attributed graphs is simplified by the existence of structural and morphological flags in the skeletal points. Last, concepts are created in the resulting conceptual space by means of a best-guess approach as well as a mechanism for accommodating external user input.

Partial specifications allow approximate models of systems such as Kripke structures, or labeled transition systems to be created. Using the abstraction possible with these models, an avoidance of the state-space explosion problem is possible, whilst still retaining a structure that can have properties checked over it. A single partial specification abstracts a set of systems, whether Kripke, labeled transition systems, or systems with both atomic propositions and named transitions. This thesis deals in part with problems arising from a desire to efficiently evaluate sentences of the modal µ-calculus over a partial specification. Partial specifications also allow a single system to be modeled by a number of partial specifications, which abstract away different parts of the system. Alternatively, a number of partial specifications may represent different requirements on a system. The thesis also addresses the question of whether a set of partial specifications is consistent, that is to say, whether a single system exists that is abstracted by each member of the set. The effect of nominals, special atomic propositions true on only one state in a system, is also considered on the problem of the consistency of many partial specifications. The thesis also addresses the question of whether the systems a partial specification abstracts are all abstracted by a second partial specification, the problem of inclusion. The thesis demonstrates how commonly used �specification patterns� � useful properties specified in the modal µ-calculus, can be efficiently evaluated over partial specifications, and gives upper and lower complexity bounds on the problems related to sets of partial specifications.