Imperial College London

DrKrysiaBroda

Faculty of EngineeringDepartment of Computing

Honorary Senior Lecturer
 
 
 
//

Contact

 

+44 (0)20 7594 8426k.broda Website

 
 
//

Location

 

573Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Publication Type
Year
to

113 results found

Law M, Russo A, Bertino E, Broda K, Lobo Jet al., 2019, Representing and learning grammars in answer set programming, AAAI-19: Thirty-third AAAI Conference on Artificial Intelligence, Publisher: Association for the Advancement of Artificial Intelligence, Pages: 2919-2928

In this paper we introduce an extension of context-free grammars called answer set grammars (ASGs). These grammars allow annotations on production rules, written in the language of Answer Set Programming (ASP), which can express context-sensitive constraints. We investigate the complexity of various classes of ASG with respect to two decision problems: deciding whether a given string belongs to the language of an ASG and deciding whether the language of an ASG is non-empty. Specifically, we show that the complexity of these decision problems can be lowered by restricting the subset of the ASP language used in the annotations. To aid the applicability of these grammars to computational problems that require context-sensitive parsers for partially known languages, we propose a learning task for inducing the annotations of an ASG. We characterise the complexity of this task and present an algorithm for solving it. An evaluation of a (prototype) implementation is also discussed.

Conference paper

Broda K, Dore M, 2019, Towards Intuitive Reasoning in Axiomatic Geometry, 7th International Workshop on Theorem proving components for Educational software, ISSN: 2075-2180

Conference paper

Law M, Russo A, Broda K, 2019, Inductive Learning of Answer Set Programs from Noisy Examples, Advances in Cognitive Systems

Journal article

Russo A, Law M, Broda K, 2018, AAAI 2019, Proceedings pf the 33rd AAAI Conference on Artificial Intelligence, AAAI-19: Thirty-Third AAAI Conference on Artificial intelligence

Conference paper

Aspis Y, Broda K, Russo A, 2018, Tensor-based abduction in horn propositional programs, ILP 2018 - 28th International Conference on Inductive Logic Programming, Publisher: CEUR Workshop Proceedings, Pages: 68-75, ISSN: 1613-0073

This paper proposes an algorithm for computing solutions of abductive Horn propositional tasks using third-order tensors. We first introduce the notion of explanatory operator, a single-step operation based on inverted implication, and prove that minimal abductive solutions of a given Horn propositional task can be correctly computed using this operator. We then provide a mapping of Horn propositional programs into third-order tensors, which builds upon recent work on matrix representation of Horn programs. We finally show how this mapping can be used to compute the explanatory operator by tensor multiplication.

Conference paper

Law M, Russo AM, Broda K, 2018, The complexity and generality of learning answer set programs, Artificial Intelligence, Vol: 259, Pages: 110-146, ISSN: 1872-7921

Traditionally most of the work in the field of Inductive Logic Programming (ILP) has addressed the problem of learning Prolog programs. On the other hand, Answer Set Programming is increasingly being used as a powerful language for knowledge representation and reasoning, and is also gaining increasing attention in industry. Consequently, the research activity in ILP has widened to the area of Answer Set Programming, witnessing the proposal of several new learning frameworks that have extended ILP to learning answer set programs. In this paper, we investigate the theoretical properties of these existing frameworks for learning programs under the answer set semantics. Specifically, we present a detailed analysis of the computational complexity of each of these frameworks with respect to the two decision problems of deciding whether a hypothesis is a solution of a learning task and deciding whether a learning task has any solutions. We introduce a new notion of generality of a learning framework, which enables us to define a framework to be more general than another in terms of being able to distinguish one ASP hypothesis solution from a set of incorrect ASP programs. Based on this notion, we formally prove a generality relation over the set of existing frameworks for learning programs under answer set semantics. In particular, we show that our recently proposed framework, Context-dependent Learning from Ordered Answer Sets, is more general than brave induction, induction of stable models, and cautious induction, and maintains the same complexity as cautious induction, which has the highest complexity of these frameworks.

Journal article

Doré M, Broda K, 2018, The ELFE System - Verifying Mathematical Proofs of Undergraduate Students, 10th International Conference on Computer Supported Education, Publisher: SCITEPRESS - Science and Technology Publications

Conference paper

Chabierski P, Russo A, Law M, Broda Ket al., 2017, Machine comprehension of text using combinatory categorial grammar and answer set programs, COMMONSENSE 2017, Publisher: CEUR Workshop Proceedings, ISSN: 1613-0073

We present an automated method for generating Answer Set Programs from narratives written in English and demonstrate how such a representation can be used to answer questions about text. The proposed approach relies on a transparent interface between the syntax and semantics of natural language provided by Combinatory Categorial Grammars to translate text into Answer Set Programs, hence creating a knowledge base that, together with background knowledge, can be queried.

Conference paper

Dragiev S, Russo A, Broda K, Law M, Turliuc Ret al., 2017, An abductive-inductive algorithm for probabilistic inductive logic programming, 26th International Conference on Inductive Logic Programming, Pages: 20-26, ISSN: 1613-0073

The integration of abduction and induction has lead to a variety of non-monotonic ILP systems. XHAIL is one of these systems, in which abduction is used to compute hypotheses that subsume Kernel Sets. On the other hand, Peircebayes is a recently proposed logic-based probabilistic programming approach that combines abduction with parameter learning to learn distributions of most likely explanations. In this paper, we propose an approach for integrating probabilistic inference with ILP. The basic idea is to redefine the inductive task of XHAIL as a statistical abduction, and to use Peircebayes to learn probability distribution of hypotheses. An initial evaluation of the proposed algorithm is given using synthetic data.

Conference paper

Broda KB, Law M, Russo A, 2016, Iterative Learning of Answer Set Programs with Context Dependent Examples, Theory and Practice of Logic Programming, Vol: 16, Pages: 834-848, ISSN: 1475-3081

In recent years, several frameworks and systems have been proposed that extend InductiveLogic Programming (ILP) to the Answer Set Programming (ASP) paradigm. In ILP, examplesmust all be explained by a hypothesis together with a given background knowledge. In existingsystems, the background knowledge is the same for all examples; however, examples may becontext-dependent. This means that some examples should be explained in the context ofsome information, whereas others should be explained in different contexts. In this paper, wecapture this notion and present a context-dependent extension of the Learning from OrderedAnswer Sets framework. In this extension, contexts can be used to further structure thebackground knowledge. We then propose a new iterative algorithm, ILASP2i, which exploitsthis feature to scale up the existing ILASP2 system to learning tasks with large numbersof examples. We demonstrate the gain in scalability by applying both algorithms to variouslearning tasks. Our results show that, compared to ILASP2, the newly proposed ILASP2isystem can be two orders of magnitude faster and use two orders of magnitude less memory,whilst preserving the same average accuracy

Journal article

Turliuc R, Dickens L, Russo AM, Broda Ket al., 2016, Probabilistic abductive logic programming using Dirichlet priors, International Journal of Approximate Reasoning, Vol: 78, Pages: 223-240, ISSN: 1873-4731

Probabilistic programming is an area of research that aims to develop general inference algorithms for probabilistic models expressed as probabilistic programs whose execution corresponds to inferring the parameters of those models. In this paper, we introduce a probabilistic programming language (PPL) based on abductive logic programming for performing inference in probabilistic models involving categorical distributions with Dirichlet priors. We encode these models as abductive logic programs enriched with probabilistic definitions and queries, and show how to execute and compile them to boolean formulas. Using the latter, we perform generalized inference using one of two proposed Markov Chain Monte Carlo (MCMC) sampling algorithms: an adaptation of uncollapsed Gibbs sampling from related work and a novel collapsed Gibbs sampling (CGS). We show that CGS converges faster than the uncollapsed version on a latent Dirichlet allocation (LDA) task using synthetic data. On similar data, we compare our PPL with LDA-specific algorithms and other PPLs. We find that all methods, except one, perform similarly and that the more expressive the PPL, the slower it is. We illustrate applications of our PPL on real data in two variants of LDA models (Seed and Cluster LDA), and in the repeated insertion model (RIM). In the latter, our PPL yields similar conclusions to inference with EM for Mallows models.

Journal article

Maimari N, Pedrigi RM, Russo A, Broda K, Krams Ret al., 2016, Integration of flow studies for robust selection of mechanoresponsive genes, Thrombosis and Haemostasis, Vol: 115, Pages: 474-483, ISSN: 0340-6245

Blood flow is an essential contributor to plaque growth, composition and initiation. It is sensed by endothelial cells, which react to blood flow by expressing > 1000 genes. The sheer number of genes implies that one needs genomic techniques to unravel their response in disease. Individual genomic studies have been performed but lack sufficient power to identify subtle changes in gene expression. In this study, we investigated whether a systematic meta-analysis of available microarray studies can improve their consistency. We identified 17 studies using microarrays, of which six were performed in vivo and 11 in vitro. The in vivo studies were disregarded due to the lack of the shear profile. Of the in vitro studies, a cross-platform integration of human studies (HUVECs in flow cells) showed high concordance (> 90 %). The human data set identified > 1600 genes to be shear responsive, more than any other study and in this gene set all known mechanosensitive genes and pathways were present. A detailed network analysis indicated a power distribution (e. g. the presence of hubs), without a hierarchical organisation. The average cluster coefficient was high and further analysis indicated an aggregation of 3 and 4 element motifs, indicating a high prevalence of feedback and feed forward loops, similar to prokaryotic cells. In conclusion, this initial study presented a novel method to integrate human-based mechanosensitive studies to increase its power. The robust network was large, contained all known mechanosensitive pathways and its structure revealed hubs, and a large aggregate of feedback and feed forward loops.

Journal article

Athakravi D, Satoh K, Law M, Broda K, Russo AMet al., 2015, Automated inference of rules with exception from past legal cases using ASP, International Conference on Logic Programming and Non Monotonic Reasoning (LPNMR 2015), Publisher: Springer, Pages: 83-96, ISSN: 0302-9743

In legal reasoning, different assumptions are often considered when reaching a final verdict and judgement outcomes strictly depend on these assumptions. In this paper, we propose an approach for generating a declarative model of judgements from past legal cases, that expresses a legal reasoning structure in terms of principle rules and exceptions. Using a logic-based reasoning technique, we are able to identify from given past cases different underlying defaults (legal assumptions) and compute judgements that (i) cover all possible cases (including past cases) within a given set of relevant factors, and (ii) can make deterministic predictions on final verdicts for unseen cases. The extracted declarative model of judgements can then be used to make automated inference of future judgements, and generate explanations of legal decisions.

Conference paper

Law M, Russo A, Broda K, 2015, Learning weak constraints in answer set programming, Theory and Practice of Logic Programming, Vol: 15, Pages: 511-525, ISSN: 1475-3081

This paper contributes to the area of inductive logic programming by presenting a new learning framework that allows the learning of weak constraints in Answer Set Programming (ASP). The framework, called Learning from Ordered Answer Sets, generalises our previous work on learning ASP programs without weak constraints, by considering a new notion of examples as ordered pairs of partial answer sets that exemplify which answer sets of a learned hypothesis (together with a given background knowledge) are preferred to others. In this new learning task inductive solutions are searched within a hypothesis space of normal rules, choice rules, and hard and weak constraints. We propose a new algorithm, ILASP2, which is sound and complete with respect to our new learning framework. We investigate its applicability to learning preferences in an interview scheduling problem and also demonstrate that when restricted to the task of learning ASP programs without weak constraints, ILASP2 can be much more efficient than our previously proposed system.

Journal article

Athakravi D, Alrajeh D, Broda K, Russo A, Satoh Ket al., 2015, Inductive Learning Using Constraint-Driven Bias, 24th International Conference on Inductive Logic Programming (ILP), Publisher: SPRINGER-VERLAG BERLIN, Pages: 16-32, ISSN: 0302-9743

Conference paper

Turliuc CR, Dickens L, Russo A, Broda Ket al., 2015, Probabilistic abductive logic programming using Dirichlet priors, Pages: 85-98, ISSN: 1613-0073

Probabilistic logic programming has traditionally focused on languages where probabilities or weights are specified or inferred directly, rather than through Bayesian priors. To address this limitation, we propose a probabilistic logic programming language that bridges the gap between logical and probabilistic inference in categorical models with Dirichlet priors. The language is described in terms of its general plate model, syntax, semantics and the relation between the three. A prototype implementation is evaluated on two case studies: latent Dirichlet allocation (LDA) on synthetic data, where we compare it with collapsed Gibbs sampling, and repeated insertion model (RIM) on real data. Universal probabilistic programming is not always scalable beyond toy examples on some models. However, our promising results show that the inference yields similar results to state-of-the-art solutions reported in the literature, produced with model-specific implementations.

Conference paper

Maimari N, Towhidi L, Oh D, Broda K, Russo A, Krams Ret al., 2014, A novel integrated platform for gene network inference and validation: beyond the dream consortium, Atherosclerosis, Vol: 237, Pages: e11-e11, ISSN: 0021-9150

Journal article

Maimari N, Broda K, Kakas A, Russo A, Krams Ret al., 2014, Symbolic representation and inference of regulatory networks: uncovering mechanosensitive gene networks, Atherosclerosis, Vol: 237, Pages: e11-e11, ISSN: 0021-9150

Journal article

Russo AM, Athakravi D, Corapi D, Broda Ket al., 2014, Learning through Hypothesis Refinement using Answer Set Programming, 23rd International Conference on Inductive Logic Programming

Conference paper

Law M, Russo A, Broda K, 2014, Inductive Learning of Answer Set Programs, 14th European Conference on Logics in Artificial Intelligence (JELIA), Publisher: Springer, Pages: 311-325, ISSN: 0302-9743

Conference paper

Maimari N, Broda K, Kakas A, Krams R, Russo Aet al., 2014, Symbolic Representation and Inference of Regulatory Network Structures, Logical Modeling of Biological Systems, Publisher: John Wiley & Sons, Inc., Pages: 1-48, ISBN: 9781119005223

Book chapter

Turliuc C-R, Maimari N, Russo A, Broda Ket al., 2013, On Minimality and Integrity Constraints in Probabilistic Abduction, LPAR Logic for Programming,Artificial Intelligence and Reasoning, Publisher: Springer Verlag

Conference paper

Maimari N, Turliuc C-R, Broda K, Kakas A, Krams R, Russo Aet al., 2013, ARNI: Abductive inference of complex regulatory network structures, 11th COnference on Computational Methods in Systems Biology, Publisher: Springer Verlag, Pages: 235-237

Conference paper

Maimari N, Krams R, Turliuc C-R, Broda K, Russo A, Kakas Aet al., 2013, ARNI: Abductive inference of complex regulatory network structures, 11th International Conference, CMSB 2013, Pages: 235-237, ISSN: 0302-9743

Physical network inference methods use a template of molecular interaction to infer biological networks from high throughput datasets. Current inference methods have limited applicability, relying on cause-effect pairs or systematically perturbed datasets and fail to capture complex network structures. Here we present a novel framework, ARNI, based on abductive inference, that addresses these limitations. © Springer-Verlag 2013.

Conference paper

Athakravi D, Broda K, Russo A, 2012, Predicate invention in inductive logic programming, Pages: 15-21

The ability to recognise new concepts and incorporate them into our knowledge is an essential part of learning. From new scientific concepts to the words that are used in everyday conversation, they all must have at some point in the past, been invented and their definition defined. In this position paper, we discuss how a general framework for predicate invention could be made, by reasoning about the problem at the meta-level using an appropriate notion of top theory in inductive logic programming.© Duangtida Athakravi, Krysia Broda, and Alessandra Russo.

Conference paper

Smith J, Dickens L, Broda K, 2012, Balancing Public Cycle Sharing Schemes using Independent Learners, International Conference on Machine Learning Applications 2012

Conference paper

Ma J, Russo A, Broda K, Lupu Eet al., 2011, Multi-agent abductive reasoning with confidentiality, Pages: 1071-1072

In the context of multi-agent hypothetical reasoning, agents typically have partial knowledge about their environments, and the union of such knowledge is still incomplete to represent the whole world. Thus, given a global query they need to collaborate with each other to make correct inferences and hypothesis, whilst maintaining global constraints. There are many real world applications in which the confidentiality of agent knowledge is of primary concern, and hence the agents may not share or communicate all their information during the collaboration. This extra constraint gives a new challenge to multi-agent reasoning. This paper shows how this dichotomy between "open communication" in collaborative reasoning and protection of confidentiality can be accommodated, by extending a general-purpose distributed abductive logic programming system for multi-agent hypothetical reasoning with confidentiality. Specifically, the system computes consistent conditional answers for a query over a set of distributed normal logic programs with possibly unbound domains and arithmetic constraints, preserving the private information within the logic programs. Copyright © 2011, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

Conference paper

Maimari N, Frueh JA, Lamb JR, Broda K, Russo A, Krams Ret al., 2011, Inductive Logic Programming Driven Framework for the Inference of Atheroprotective Gene Regulatory networks, Bioengineering

Conference paper

Ma J, Russo A, Lupu E, Broda Ket al., 2011, Multi-agent Confidential Abductive Reasoning, 27th International COnference on Logic Programming

Conference paper

Ma J, Russo A, Broda K, Lupu Eet al., 2011, Multi-agent Hypothetical Reasoning with Confidentiality, 10th Conference on Autonomous Agents and Multi-Agent Systems

Conference paper

This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.

Request URL: http://wlsprd.imperial.ac.uk:80/respub/WEB-INF/jsp/search-html.jsp Request URI: /respub/WEB-INF/jsp/search-html.jsp Query String: respub-action=search.html&id=00000741&limit=30&person=true