Research in natural language processing (NLP) is driving advances in many applications such as search engines and personal digital assistants, e.g. Apple's Siri and Amazon's Alexa. In many NLP tasks the output to be predicted is a graph representing the sentence, e.g. a syntax tree in syntactic parsing or a meaning representation in semantic parsing. Furthermore, in other tasks such as natural language generation and machine translation the predicted output is text, i.e. a sequence of words. Both types of NLP tasks have been tackled successfully with incremental modelling approaches in which prediction is decomposed into a sequence of actions constructing the output. Despite its success, a fundamental limitation in incremental modelling is that the actions considered typically construct the output monotonically, e.g. in natural language generation each action adds a word to the output but never removes or changes a previously predicted one. Thus, relying exclusively on monotonic actions can decrease accuracy, since the effect of incorrect actions cannot be amended. Furthermore, these actions will be used to predict the following ones, likely to result in an error cascade. We propose an 18-month project to address this limitation and learn non-monotonic incremental language processing models, i.e. incremental models that consider actions that can "undo" the outcome of previously predicted ones. The challenge in incorporating non-monotonic actions is that, unlike their monotonic counterparts, they are not straightforward to infer from the labelled data typically available for training, thus rendering standard supervised learning approaches inapplicable. To overcome this issue we will develop novel algorithms under the imitation learning paradigm to learn non-monotonic incremental models without assuming action-level supervision, relying instead on instance-level loss functions and the model's own predictions in order to learn how to recover from incorrect actions to avoid error cascades. To succeed in this goal, this proposal has the following research objectives: 1) To model non-monotonic incremental prediction of structured outputs in a generic way that can be applied to a variety of tasks with natural language text as output 2) To learn non-monotonic incremental predictors using imitation learning and improve upon the accuracy of monotonic incremental models both in terms of automatic measures such as BLEU and human evaluation. 3) To extend the proposed approach to structured prediction tasks with graph as output. 4) To release software implementations of the proposed methods to facilitate reproducibility and wider adoption by the research community. The research proposed focuses on a fundamental limitation in incremental language processing models, which have been successfully applied to a variety of natural language processing tasks, thus we anticipate the proposal to have a wide academic impact. Furthermore, the tasks we will evaluate it on, namely natural language generation and semantic parsing, are essential components to natural language interfaces and personal digital assistants. Improving these technologies will enhance accessibility to digital information and services. We will demonstrate the benefits of our approach through our collaboration with our project partners Amazon who are supporting the proposal both in terms of cloud computing credits but also by hosting the research associate in order to apply the outcomes of the project to industry-scale datasets.

Research in natural language processing (NLP) is driving advances in many applications such as search engines and personal digital assistants, e.g. Apple's Siri and Amazon's Alexa. In many NLP tasks the output to be predicted is a graph representing the sentence, e.g. a syntax tree in syntactic parsing or a meaning representation in semantic parsing. Furthermore, in other tasks such as natural language generation and machine translation the predicted output is text, i.e. a sequence of words. Both types of NLP tasks have been tackled successfully with incremental modelling approaches in which prediction is decomposed into a sequence of actions constructing the output. Despite its success, a fundamental limitation in incremental modelling is that the actions considered typically construct the output monotonically, e.g. in natural language generation each action adds a word to the output but never removes or changes a previously predicted one. Thus, relying exclusively on monotonic actions can decrease accuracy, since the effect of incorrect actions cannot be amended. Furthermore, these actions will be used to predict the following ones, likely to result in an error cascade. We propose an 18-month project to address this limitation and learn non-monotonic incremental language processing models, i.e. incremental models that consider actions that can "undo" the outcome of previously predicted ones. The challenge in incorporating non-monotonic actions is that, unlike their monotonic counterparts, they are not straightforward to infer from the labelled data typically available for training, thus rendering standard supervised learning approaches inapplicable. To overcome this issue we will develop novel algorithms under the imitation learning paradigm to learn non-monotonic incremental models without assuming action-level supervision, relying instead on instance-level loss functions and the model's own predictions in order to learn how to recover from incorrect actions to avoid error cascades. To succeed in this goal, this proposal has the following research objectives: 1) To model non-monotonic incremental prediction of structured outputs in a generic way that can be applied to a variety of tasks with natural language text as output 2) To learn non-monotonic incremental predictors using imitation learning and improve upon the accuracy of monotonic incremental models both in terms of automatic measures such as BLEU and human evaluation. 3) To extend the proposed approach to structured prediction tasks with graph as output. 4) To release software implementations of the proposed methods to facilitate reproducibility and wider adoption by the research community. The research proposed focuses on a fundamental limitation in incremental language processing models, which have been successfully applied to a variety of natural language processing tasks, thus we anticipate the proposal to have a wide academic impact. Furthermore, the tasks we will evaluate it on, namely natural language generation and semantic parsing, are essential components to natural language interfaces and personal digital assistants. Improving these technologies will enhance accessibility to digital information and services. We will demonstrate the benefits of our approach through our collaboration with our project partners Amazon who are supporting the proposal both in terms of cloud computing credits but also by hosting the research associate in order to apply the outcomes of the project to industry-scale datasets.

The field of mathematical optimization experienced a paradigm shift in the last decade: while the 20 years prior to about year 2005 were dominated by the development of interior-point methods, research activity since has almost entirely been focused on first-order methods. This was caused by several factors. Most notably, there has been a surge in the demand from practitioners, in fields such as machine learning, signal processing and data science, for new methods able to cope with new large scale problems. Moreover, an important role in the transition was played by the fact that accuracy requirements in many modern applications (such as classification and image denoising) were only moderate or low, which was in sharp contrast with the preceding focus on applications in classical domains such as engineering and physics where accuracy requirements were typically high. The paradigm shift would not have been possible, however, were it not for the development and success of modern gradient methods, the complexity of which improved upon classical results by an order of magnitude, using sophisticated tools such as the estimate sequence method and smoothing. At the moment, mathematical optimization is experiencing yet another revolution, related to the introduction of randomization as an algorithmic design and analysis tool, much in the same way that probabilistic reasoning has recently begun to transform several other "continuous" fields, including numerical linear algebra and control theory. The import of randomization is at least twofold: it makes it possible to design new algorithms which scale to extreme dimensions, and at the same time it often leads to improved theoretical complexity bounds. This project focuses on the design, complexity analysis and high-performing implementations of efficient randomized algorithms suitable for extreme convex optimization.

One in six people in the UK have a hearing impairment, and this number is certain to increase as the population ages. Yet only 40% of people who could benefit from hearing aids have them, and most people who have the devices don't use them often enough. A major reason for this low uptake and use, is the perception that hearing aids perform poorly. Perhaps the most serious problem is hearing speech in noise. Even the best hearing aids struggle in such situations. This might be in the home, where the boiling kettle forces conversations with friends to stop, or maybe in a railway station, where noise makes it impossible to hear announcements. If such difficulties force the hearing impaired to withdraw from social situations, this increases the risk of loneliness and depression. Moreover, recent research suggests hearing loss is a risk factor for dementia. Consequently, improving how hearing devices deal with speech in noise has the potential to improve many aspects of health and well-being for an aging population. Making the devices more effective should increase the uptake and use of hearing aids. Our approach is inspired by the latest science in speech recognition and synthesis. These are very active and fast moving areas of research, especially now with the development of voice interfaces like Alexa. But most of this research overlooks users who have a hearing impairment. There are innovative approaches being developed in speech technology and machine learning, which could be the basis for revolutionising hearing devices. But to get such radical advances needs more researchers to consider hearing impairments. To do this, we will run a series of signal processing competitions ("challenges"), which will deal with increasingly difficult scenarios of hearing speech in noise. Using such competitions is a proven technique for accelerating research, especially in the fields of speech technology and machine learning. We will develop simulation tools, models and databases needed to run the challenges. These will also lower barriers that currently prevent speech researchers from considering hearing impairment. Data would include the results of listening tests that characterise how real people perceive speech in noise, along with a comprehensive characterisation of each test subject's hearing ability, because hearing aid processing needs to be personalised. We will develop simulators to create different listening scenarios. Models to predict how the hearing impaired perceive speech in noise are also needed. Such data and tools will form a test-bed to allow other researchers to develop their own algorithms for hearing aid processing in different listening scenarios. We will also challenge researchers to improve our models of perception. The scientific legacy of the project will be improved algorithms for hearing aid processing; a test-bed that readily allows further development of algorithms, and more speech researchers considering the hearing abilities of the whole population.

The future information infrastructure will be characterized by massive streaming sets of distributed data-sources. These data will challenge classical statistical and machine learning methodologies both from a computational and a theoretical perspective. This proposal investigates a flexible class of models for learning and inference in the context of these challenges. We will develop learning infrastructures that are powerful, flexible and 'privacy aware' with a user-centric focus. These learning infrastructures will be developed in the context of particular application challenges, including mental health, the developing world and personal information management. These applications are inspired by collaborations with citizenme, the NewMind Network for Mental Health Technology Research and Makerere University in Kampala, Uganda.