There are many areas of scientific research, business analysis and engineering for which stochastic differential equations are the natural form of system model. Fields such as environmental modelling, systems biology, ecological systems, weather, market dynamics, traffic networks, neural modelling and fMRI are all areas which have regularly used stochastic differential equations for describing system dynamics and making predictions. In these same areas, ever-increasing data quantities are becoming available, and there is a demand to utilise this data to refine and develop good system models. However it is very rare for this data to be directly used to develop stochastic differential models. Where stochastic differential equations are used, simulation methods still seem to be the standard modelling approach. Downloadable or purchasable tools for utilising inference and learning in these continuous-time and nonlinear systems are currently unavailable. The long-term aim of this research agenda is to develop, implement and promote tools for practical data-driven modelling for continuous-time stochastic systems. The focus is on inference and learning in high dimensional, nonlinear stochastic differential systems. We aim to make stochastic differential modelling as easy to do as simulation of stochastic differential equations (SDEs), fixed time modelling or deterministic methods. The immediate goal of this pump priming proposal was to coordinate, focus and develop existing independent early efforts in this direction at the three sites that form part of this proposal. We provided a coherent framework and test environment for the collaborative research. We researched, developed and firmly established a baseline set of methods for stochastic differential inference and learning. We proved the benefits and feasibility of these methods within the test environment, and provided clear demonstrations of the capabilities. This provided an initial toolset for stochastic modelling, and a firm grounding for establishing a larger scale European collaborative research agenda in this area.

This project studied learning curves in multi-component systems, with a special focus on the situation where humans and machines interact via an adaptive interface. In this situation a system is formed by multiple adaptive components that need to learn how to optimise the system’s overall behaviour: each component learns to behave so as to achieve the system’s optimum. A special application is human-machine interaction, where both the users and the interfaces are trying to maximise information flow, by adapting to each other. This includes issues of co-learning, co-operation; concept tracking; exploration-exploitation. The presence of delayed, partial, noisy rewards is a necessary part of this scenario. The case of N=2 components was emphasised, to identify the various modalities of learning, before any attempt was made to model the N>2 case. We modelled various settings, including active, reinforcement, online and learning from independent and identically distributed data, in various conditions. The theoretical results were compared with experimental learning curves, obtained both for machine learning algorithms, and for humans engaged in various tasks (e.g., extensive data from Microsoft Research about users learning in various games on the Xbox; and web logs of users interacting with interfaces; also learning curves from neuroscience literature). Finally, we transferred our models to the task of designing cognitive interfaces, to deal with one or more users, in an adaptive way, including the scenario of interaction within online social tagging communities, and various other web based co-operation and co-learning settings.

With the explosive growth and ever increasing complexity of data, developing theory and algorithms for learning with high-dimensional data has become an important challenge in statistical machine learning. Although significant advances have been made in recent years, most of the research efforts have been focused on supervised learning problems. This project designed, analysed, and implemented reinforcement learning algorithms for high-dimensional domains. We investigated the possibility of using the recent results in l1-regularization and compressive sensing in reinforcement learning. Humans learn and act using complex and high-dimensional observations and are extremely good in knowing how to dispense of most of the observed data with almost no perceptual loss. Thus, we hope that the generated results can shed some light on understanding of human decision-making. Our main goal was to find appropriate representations for value function approximation in high-dimensional spaces, and to use them to develop efficient reinforcement learning algorithms. By appropriate we mean representations that facilitate fast and robust learning, and by efficient we mean algorithms whose sample and computational complexities do not grow too rapidly with the dimension of the observations. We further intend to provide theoretical analysis for these algorithms as we believe that such results will help us refine the performance of such algorithms. Finally, we intend to empirically evaluate the performance of the developed algorithms in real-world applications such as a complex network management domain and a dogfight flight simulator.

The ability of building robust semantic space representations of environments is crucial for the development of truly autonomous robots. This task, inherently connected with cognition, is traditionally achieved by training the robot with a supervised learning phase. This work argues that the design of robust and autonomous systems would greatly benefit from adopting a semi-supervised online learning approach. Indeed, the support of open-ended, lifelong learning is fundamental in order to cope with the dazzling variability of the real world, and online learning provides precisely this kind of ability. The research focused on the robot place recognition problem, and designed online categorization algorithms that occasionally ask for human intervention based on a confidence measure. By modulating the number of queries on the experienced data sequence, the system adaptively trades off performance with degree of supervision. Through a rigorous analysis, simultaneous performance and query rate guarantees are proven in extremely robust (game-theoretic) data generation scenarios. This theoretical analysis is supported and complemented by extensive evaluation on data acquired on real robotic platforms.

Machine Translation systems frequently encounter terms they are not able to translate appropriately. Assume for example, that an SMT system translating Fujitsu has filed a lawsuit against Tellabs for patent infringement is missing the phrases:“filed a lawsuit against” in its phrase table. A previously suggested solution is to paraphrase (e.g. to: “sued”), and then to translate the paraphrased sentence. In this work we suggest a novel solution taking place when a paraphrase is not available: By translating a sentence whose meaning is entailed by the original one, we may lose some information, yet produce a useful translation nonetheless: “Fujitsu has accused Tellabs for patent infringement”. Textual Entailment provides an appropriate framework for handling both these solutions through the use of entailment rules. We thus propose a first application of this paradigm for SMT, with a primary focus on context models. While verifying the validity of the context for a rule application is a key issue, little work has been done in that area beyond the single word level typically address in WSD tasks. To address this issue, we develop probabilistic context models for semantic inference in general and to apply them specifically in SMT setting, thus exploiting Bar Ilan’s and XRCE’s expertise in these fields.

A standard paradigm of supervised learning is the data-independent hypothesis space. In this model a data set is a sample of points from some space with a given geometry. Thus the distance between any two points in the space is independent of the particular sample. In a data-dependent geometry the distance depends on the particular points sampled. Thus for example consider a data set of “news stories,” containing a story in the Financial Times about a renewed investment in nuclear technology, and a story in the St. Petersburg Gazetteer about job losses from a decline in expected tourism. Although these appear initially to be dissimilar, the inclusion of a third story regarding an oil pipeline leakage creates an indirect “connection.” In the data-independent case the “distance” between stories is unchanged while in the data-dependent case, the distances reflect the connection. This project was designed to address the challenges posed both algorithmically and theoretically by data-defined hypothesis spaces. This project brought together three sites to address an underlying theme of the PASCAL2 proposal that of leveraging prior knowledge about complex data. The complexity of real world data is clearly offset by its intricate geometric structure – be it hierarchical, long-tailed distributional, graph based, and so forth. By allowing the data to define the hypothesis space we may leverage these structures to enable practical learning – the core aim of this project. This three-way collaboration was thought likely to give rise to a wide spectrum of possible applications, fostering future opportunities for joint research activities.

Precise models of technical systems and the task to be accomplished can be crucial in technical applications. In robot tracking control, only a well-estimated inverse dynamics model results in both high accuracy and compliant, low-gain control. For complex robots such as humanoids or lightweight robot arms, it is often hard to analytically model the system sufficiently well and, thus, modern regression methods can offer a viable alternative. Current regression methods such as Gaussian process regression or locally weighted projection regression either have high computational cost or are not straightforward to use (respectively). Hence, task-appropriate real-time methods are needed in order to achieve high performance. This project uses the large body of insights from modern online learning methods and applied them in the context of robot learning. Particularly, we focussed on three novel problems that have not yet been tackled in the literature. The first two problems are in the learning of inverse dynamics domain: current methods largely neglect the existence of input noise and only focus on output noise. We considered both sources of noise together. This may have far reaching consequences: the input noise only exists in training data while in the recall or control case it no longer occurs. Secondly, we studied the bias originating from the active data generation that is part of the online learning problem. Our intention was to build on recent advances in online learning algorithms, such as the confidence-weighted algorithm (CW) and the adaptive-regularization-algorithm (AROW), and design, analyze and experiment new techniques and method to cope with the above challenges. Success will allow us to build better robot controllers for smooth and delicate robot dynamics.

Classification, one of the most widely studied problems in machine learning, is also a central research topic in human cognitive psychology. So far these two parallel fields have mostly developed in isolation. Our research bridges machine learning with human psychology research by investigating discriminative vs. generative learning in humans. The distinction between discriminative and generative approaches is much studied in machine learning, but has not been examined in human learning. Discriminative learners find a direct mapping between inputs and class labels whereas generative learners model a joint distribution between inputs and labels. These approaches often result in classification differences. Our preliminary work indicated that humans can be prompted to adopt discriminative or generative approaches to learning the same dataset. In this work we conducted experiments in which we measured learning curves of humans who are trained on datasets under discriminative vs. generative learning conditions. We used datasets which have been previously used as machine learning benchmarks and also datasets of brain imaging scans used for medical diagnosis. Humans still outperform the most powerful computers in many tasks, such as learning from small amounts of data and comprehending language. Thus, insights from human learning have great potential to inform machine learning. An understanding of how humans solve the classification problem will be instructive for machine learning in several ways: for the many situations where humans still outperform computers, human results can set benchmarks for machine learning challenges. Additionally, understanding human learning approaches can help give direction to the machine learning approaches that will have the most potential. Finally, in many situations we want machines to behave like humans in order to facilitate human computer interactions. An understanding of human cognition is important for developing machines that think like humans.

Although significant advances in learning with high-dimensional data have been made in recent years, most of the research efforts have been focused on supervised learning problems. We propose to design, analyze, and implement reinforcement learning algorithms for high-dimensional domains. We will investigate the possibility of using the recent results in l1-regularization and compressive sensing in reinforcement learning. Humans learn and act using complex and high-dimensional observations and are extremely good in knowing how to dispense of most of the observed data with almost no perceptual loss. Thus, we hope that the generated results can shed some light on understanding of human decision-making.

The project researchers have built a generic open-source software package (Complearn) for building tree structured representations from normalised compression distance (NCD) or normalised Google distance (NGD) distance matrix. Preliminary empirical tests with the software have indicated that the data representation is crucial for the performance of the algorithms, which led us to further study applications of lossy compression algorithms (audio stream to midi and lossy image compression through wavelet transformation). In the second part of the project, the methods and tools developed in the project were applied in a challenging and exciting real-world problem. The goal was to recover the relations among different variants of a text that has been gradually altered as a result of imperfectly copying the text over and over again. In addition to using the currently available methods in Complearn, we also developed a new compression-based method that is specifically designed for stemmatic analysis of text variants.

The various methods developed in the project were applied and tested using the tradition of the legend of St. Henry of Finland, which forms a collection of the oldest written texts found in Finland. The results were quite encouraging: the obtained family tree of the variants, the stemma, corresponds to a large extent with results obtained with more traditional methods (as verified by the leading domain expert, Tuomas Heikkilä Ph.D., Department of History, University of Helsinki). Moreover, some of the identified groups of manuscripts are previously unrecognised ones. Due to the impossibility of manually exploring all plausible alternatives among the vast number of possible trees, this work is the first attempt at a complete stemma for the legend of St. Henry. The new compression-based methods developed specifically for the stemmatology domain will be released in the future as part of the open-source Complearn package. We are also considering the possibility of creating a Pascal challenge using this type of data.