bluuebunny/crossref_metadata_2025 huggingface dataset:
Weibull distribution and dynamics of germination of Rangpur lime seeds at different temperatures
Authors: Ávila Marizangela Rizzatti , Barbosa Juliana , Fonseca Júnior Nelson da Silva , Nagashima Getúlio Takashi , Oliveira Carolina Maria Gaspar de
Published: September 2019

Abstract: Rangpur lime is the most commonly used rootstock in Brazil, and its propagation occurs through seeds. Currently, no methodology is described in the prescriptions of the Rules for Seed Testing to perform the germination test of Rangpur lime. Thus, this research aimed to study the dynamics of germination in Rangpur lime seeds according to the Weibull distribution under the effect of different temperatures and lots. The experiment was conducted in a completely randomized design, with treatments arranged in a 3 × 5 factorial scheme (temperatures of 25, 30 and 35 °C for the germination test and five seed lots, respectively) and four replications. The percentage of germination, the number of days required obtaining 50% of germination, and the parameters of the Weibull equation were determined. The optimum temperature for germination of Rangpur lime seeds was 30 °C, with the first and last counts at 21 and 30 days after test installation, respectively. The germination process can be described by the three-parameter Weibull cumulative distribution function.
High Sunflower Densities as a Weed Control Strategy in an Integrated Crop-Livestock System
Authors: DOMINSCHEK R. , DEISS L. , LANG C.R. , MORAES A. , PELISSARI A.
Published: September 2019

ABSTRACT: Sunflower is an important crop for Integrated Crop-livestock Systems (ILCS), and one of the main management difficulties identified in this crop is weed control, especially under no-till conditions when chemical weed control is not allowed. Therefore, the aim of this research was to evaluate the effect of greater sunflower population density on weed control, and its impact on sunflower yield, in an ILCS with eucalyptus in an Environmental Protection Area. Two population densities were tested (45 and 90 thousand pl. ha-1) in two crop systems (sunflower monoculture and sunflower-eucalyptus integration). An additional treatment was provided in the sunflower-eucalyptus integration, and 5 positions (2,4; 4,8; 7,2; 9,6; and 12 m) between the tree rows were evaluated. In a randomized block design, with eight repetitions, weed density and weed dry matter were determined at 40, 70 and 100 days after crop emergence. Also, phytosociological indices were calculated. The following yield components were evaluated: head diameter, number of achenes per head, and 1000-achene weight. There was lower weed infestation on the high density treatment in both systems. There was no difference of weed occurrence in the 5 positions between the tree rows. Sunflower yield was higher in the greatest population density in both systems. Increasing population density in sunflower crop is a practicable management to control weeds and to gain higher yield under free-herbicide conditions.
Dynamics of Clomazone Formulations Under Different Applications Conditions
Authors: TROPALDI L. , BRITO I.P.F.S. , DIAS R.C. , TRINDADE M.L.B. , CARBONARI C.A. , VELINI E.D.
Published: September 2019

ABSTRACT: Maintenance of straw on the soil surface in sugarcane production areas can influence weed occurrence and herbicide dynamics. After application, considerable losses of clomazone can occur as a result of its physicochemical characteristics. For this reason, novel formulations have been developed. In addition to the conventional formulation, microencapsulated formulations are currently available. Thus, the aim of this study was to observe and compare the effect of clomazone formulations under different application conditions. For this purpose, the experiment was carried with 12 treatments in a completely randomized design, with four replications, using clomazone formulations (1,200 g a.i. ha-1), on soils with different moisture levels, in the presence and absence of sugarcane straw, followed or not by rainfall simulation. The treatments were compared by observation of number of emerged plants and phytotoxicity at 7 and 14 DAA, as well shoot dry matter at 14 DAA for Ipomoea nil, Urochloa decumbens and Panicum maximum. In general, the microencapsulated formulation presented a better performance under the less suitable application conditions when compared to the conventional one. However, for the other conditions, both formulations had a similar performance.
Disjunctive Normal Form for Multi-Agent Modal Logics Based on Logical Separability
Authors: Fang Liangda , Wang Kewen , Wang Zhe , Wen Ximing
Published: September 2019

Modal logics are primary formalisms for multi-agent systems but major reasoning tasks in such logics are intractable, which impedes applications of multi-agent modal logics such as automatic planning. One technique of tackling the intractability is to identify a fragment called a normal form of multiagent logics such that it is expressive but tractable for reasoning tasks such as entailment checking, bounded conjunction transformation and forgetting. For instance, DNF of propositional logic is tractable for these reasoning tasks. In this paper, we first introduce a notion of logical separability and then define a novel disjunctive normal form SDNF for the multiagent logic Kn, which overcomes some shortcomings of existing approaches. In particular, we show that every modal formula in Kn can be equivalently casted as a formula in SDNF, major reasoning tasks tractable in propositional DNF are also tractable in SDNF, and moreover, formulas in SDNF enjoy the property of logical separability. To demonstrate the usefulness of our approach, we apply SDNF in multi-agent epistemic planning. Finally, we extend these results to three more complex multi-agent logics Dn, K45n and KD45n.
Counting Complexity for Reasoning in Abstract Argumentation
Authors: Fichte Johannes K. , Hecher Markus , Meier Arne
Published: September 2019

In this paper, we consider counting and projected model counting of extensions in abstract argumentation for various semantics. When asking for projected counts we are interested in counting the number of extensions of a given argumentation framework while multiple extensions that are identical when restricted to the projected arguments count as only one projected extension. We establish classical complexity results and parameterized complexity results when the problems are parameterized by treewidth of the undirected argumentation graph. To obtain upper bounds for counting projected extensions, we introduce novel algorithms that exploit small treewidth of the undirected argumentation graph of the input instance by dynamic programming (DP). Our algorithms run in time double or triple exponential in the treewidth depending on the considered semantics. Finally, we take the exponential time hypothesis (ETH) into account and establish lower bounds of bounded treewidth algorithms for counting extensions and projected extension.
Forgetting in Modular Answer Set Programming
Authors: Gonçalves Ricardo , Janhunen Tomi , Knorr Matthias , Leite João , Woltran Stefan
Published: September 2019

Modular programming facilitates the creation and reuse of large software, and has recently gathered considerable interest in the context of Answer Set Programming (ASP). In this setting, forgetting, or the elimination of middle variables no longer deemed relevant, is of importance as it allows one to, e.g., simplify a program, make it more declarative, or even hide some of its parts without affecting the consequences for those parts that are relevant. While forgetting in the context of ASP has been extensively studied, its known limitations make it unsuitable to be used in Modular ASP. In this paper, we present a novel class of forgetting operators and show that such operators can always be successfully applied in Modular ASP to forget all kinds of atoms – input, output and hidden – overcoming the impossibility results that exist for general ASP. Additionally, we investigate conditions under which this class of operators preserves the module theorem in Modular ASP, thus ensuring that answer sets of modules can still be composed, and how the module theorem can always be preserved if we further allow the reconfiguration of modules.
Partial Awareness
Authors: Halpern Joseph Y. , Piermont Evan
Published: September 2019

We develop a modal logic to capture partial awareness. The logic has three building blocks: objects, properties, and concepts. Properties are unary predicates on objects; concepts are Boolean combinations of properties. We take an agent to be partially aware of a concept if she is aware of the concept without being aware of the properties that define it. The logic allows for quantification over objects and properties, so that the agent can reason about her own unawareness. We then apply the logic to contracts, which we view as syntactic objects that dictate outcomes based on the truth of formulas. We show that when agents are unaware of some relevant properties, referencing concepts that agents are only partially aware of can improve welfare.
Modular Materialisation of Datalog Programs
Authors: Hu Pan , Motik Boris , Horrocks Ian
Published: September 2019

The seminaïve algorithm can be used to materialise all consequences of a datalog program, and it also forms the basis for algorithms that incrementally update a materialisation as the input facts change. Certain (combinations of) rules, however, can be handled much more efficiently using custom algorithms. To integrate such algorithms into a general reasoning approach that can handle arbitrary rules, we propose a modular framework for computing and maintaining a materialisation. We split a datalog program into modules that can be handled using specialised algorithms, and we handle the remaining rules using the semina¨ıve algorithm. We also present two algorithms for computing the transitive and the symmetric– transitive closure of a relation that can be used within our framework. Finally, we show empirically that our framework can handle arbitrary datalog programs while outperforming existing approaches, often by orders of magnitude.
Bi-Kronecker Functional Decision Diagrams: A Novel Canonical Representation of Boolean Functions
Authors: Huang Xuanxiang , Fang Kehang , Fang Liangda , Chen Qingliang , Lai Zhao-Rong , Wei Linfeng
Published: September 2019

In this paper, we present a novel data structure for compact representation and effective manipulations of Boolean functions, called Bi-Kronecker Functional Decision Diagrams (BKFDDs). BKFDDs integrate the classical expansions (the Shannon and Davio expansions) and their bi-versions. Thus, BKFDDs are the generalizations of existing decision diagrams: BDDs, FDDs, KFDDs and BBDDs. Interestingly, under certain conditions, it is sufficient to consider the above expansions (the classical expansions and their bi-versions). By imposing reduction and ordering rules, BKFDDs are compact and canonical forms of Boolean functions. The experimental results demonstrate that BKFDDs outperform other existing decision diagrams in terms of sizes.
Minimum Intervention Cover of a Causal Graph
Authors: Kandasamy Saravanan , Bhattacharyya Arnab , Honavar Vasant G.
Published: September 2019

Eliciting causal effects from interventions and observations is one of the central concerns of science, and increasingly, artificial intelligence. We provide an algorithm that, given a causal graph G, determines MIC(G), a minimum intervention cover of G, i.e., a minimum set of interventions that suffices for identifying every causal effect that is identifiable in a causal model characterized by G. We establish the completeness of do-calculus for computing MIC(G). MIC(G) effectively offers an efficient compilation of all of the information obtainable from all possible interventions in a causal model characterized by G. Minimum intervention cover finds applications in a variety of contexts including counterfactual inference, and generalizing causal effects across experimental settings. We analyze the computational complexity of minimum intervention cover and identify some special cases of practical interest in which MIC(G) can be computed in time that is polynomial in the size of G.
Knowledge Refinement via Rule Selection
Authors: Kolaitis Phokion G. , Popa Lucian , Qian Kun
Published: September 2019

In several different applications, including data transformation and entity resolution, rules are used to capture aspects of knowledge about the application at hand. Often, a large set of such rules is generated automatically or semi-automatically, and the challenge is to refine the encapsulated knowledge by selecting a subset of rules based on the expected operational behavior of the rules on available data. In this paper, we carry out a systematic complexity-theoretic investigation of the following rule selection problem: given a set of rules specified by Horn formulas, and a pair of an input database and an output database, find a subset of the rules that minimizes the total error, that is, the number of false positive and false negative errors arising from the selected rules. We first establish computational hardness results for the decision problems underlying this minimization problem, as well as upper and lower bounds for its approximability. We then investigate a bi-objective optimization version of the rule selection problem in which both the total error and the size of the selected rules are taken into account. We show that testing for membership in the Pareto front of this bi-objective optimization problem is DP-complete. Finally, we show that a similar DP-completeness result holds for a bi-level optimization version of the rule selection problem, where one minimizes first the total error and then the size.
LENA: Locality-Expanded Neural Embedding for Knowledge Base Completion
Authors: Kong Fanshuang , Zhang Richong , Mao Yongyi , Deng Ting
Published: September 2019

Embedding based models for knowledge base completion have demonstrated great successes and attracted significant research interest. In this work, we observe that existing embedding models all have their loss functions decomposed into atomic loss functions, each on a triple or an postulated edge in the knowledge graph. Such an approach essentially implies that conditioned on the embeddings of the triple, whether the triple is factual is independent of the structure of the knowledge graph. Although arguably the embeddings of the entities and relation in the triple contain certain structural information of the knowledge base, we believe that the global information contained in the embeddings of the triple can be insufficient and such an assumption is overly optimistic in heterogeneous knowledge bases. Motivated by this understanding, in this work we propose a new embedding model in which we discard the assumption that the embeddings of the entities and relation in a triple is a sufficient statistic for the triple’s factual existence. More specifically, the proposed model assumes that whether a triple is factual depends not only on the embedding of the triple but also on the embeddings of the entities and relations in a larger graph neighbourhood. In this model, attention mechanisms are constructed to select the relevant information in the graph neighbourhood so that irrelevant signals in the neighbourhood are suppressed. Termed locality-expanded neural embedding with attention (LENA), this model is tested on four standard datasets and compared with several stateof-the-art models for knowledge base completion. Extensive experiments suggest that LENA outperforms the existing models in virtually every metric.
Combining Deep Learning and Qualitative Spatial Reasoning to Learn Complex Structures from Sparse Examples with Noise
Authors: Krishnaswamy Nikhil , Friedman Scott , Pustejovsky James
Published: September 2019

Many modern machine learning approaches require vast amounts of training data to learn new concepts; conversely, human learning often requires few examples—sometimes only one—from which the learner can abstract structural concepts. We present a novel approach to introducing new spatial structures to an AI agent, combining deep learning over qualitative spatial relations with various heuristic search algorithms. The agent extracts spatial relations from a sparse set of noisy examples of block-based structures, and trains convolutional and sequential models of those relation sets. To create novel examples of similar structures, the agent begins placing blocks on a virtual table, uses a CNN to predict the most similar complete example structure after each placement, an LSTM to predict the most likely set of remaining moves needed to complete it, and recommends one using heuristic search. We verify that the agent learned the concept by observing its virtual block-building activities, wherein it ranks each potential subsequent action toward building its learned concept. We empirically assess this approach with human participants’ ratings of the block structures. Initial results and qualitative evaluations of structures generated by the trained agent show where it has generalized concepts from the training data, which heuristics perform best within the search space, and how we might improve learning and execution.
Representing and Learning Grammars in Answer Set Programming
Authors: Law Mark , Russo Alessandra , Bertino Elisa , Broda Krysia , Lobo Jorge
Published: September 2019

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.
Multi-Context System for Optimization Problems
Authors: Le Tiep , Son Tran Cao , Pontelli Enrico
Published: September 2019

This paper proposes Multi-context System for Optimization Problems (MCS-OP) by introducing conditional costassignment bridge rules to Multi-context Systems (MCS). This novel feature facilitates the definition of a preorder among equilibria, based on the total incurred cost of applied bridge rules. As an application of MCS-OP, the paper describes how MCS-OP can be used in modeling Distributed Constraint Optimization Problems (DCOP), a prominent class of distributed optimization problems that is frequently employed in multi-agent system (MAS) research. The paper shows, by means of an example, that MCS-OP is more expressive than DCOP, and hence, could potentially be useful in modeling distributed optimization problems which cannot be easily dealt with using DCOPs. It also contains a complexity analysis of MCS-OP.
Reasoning over Assumption-Based Argumentation Frameworks via Direct Answer Set Programming Encodings
Authors: Lehtonen Tuomo , Wallner Johannes P. , Järvisalo Matti
Published: September 2019

Focusing on assumption-based argumentation (ABA) as a central structured formalism to AI argumentation, we propose a new approach to reasoning in ABA with and without preferences. While previous approaches apply either specialized algorithms or translate ABA reasoning to reasoning over abstract argumentation frameworks, we develop a direct approach by encoding ABA reasoning tasks in answer set programming. This significantly improves on the empirical performance of current ABA reasoning systems. We also give new complexity results for reasoning in ABA+, suggesting that the integration of preferential information into ABA results in increased problem complexity for several central argumentation semantics.
Implanting Rational Knowledge into Distributed Representation at Morpheme Level
Authors: Lin Zi , Liu Yang
Published: September 2019

Previously, researchers paid no attention to the creation of unambiguous morpheme embeddings independent from the corpus, while such information plays an important role in expressing the exact meanings of words for parataxis languages like Chinese. In this paper, after constructing the Chinese lexical and semantic ontology based on word-formation, we propose a novel approach to implanting the structured rational knowledge into distributed representation at morpheme level, naturally avoiding heavy disambiguation in the corpus. We design a template to create the instances as pseudo-sentences merely from the pieces of knowledge of morphemes built in the lexicon. To exploit hierarchical information and tackle the data sparseness problem, the instance proliferation technique is applied based on similarity to expand the collection of pseudo-sentences. The distributed representation for morphemes can then be trained on these pseudo-sentences using word2vec. For evaluation, we validate the paradigmatic and syntagmatic relations of morpheme embeddings, and apply the obtained embeddings to word similarity measurement, achieving significant improvements over the classical models by more than 5 Spearman scores or 8 percentage points, which shows very promising prospects for adoption of the new source of knowledge.
Complexity of Inconsistency-Tolerant Query Answering in Datalog+/– under Cardinality-Based Repairs
Authors: Lukasiewicz Thomas , Malizia Enrico , Vaicenavičius Andrius
Published: September 2019

Querying inconsistent ontological knowledge bases is an important problem in practice, for which several inconsistencytolerant query answering semantics have been proposed, including query answering relative to all repairs, relative to the intersection of repairs, and relative to the intersection of closed repairs. In these semantics, one assumes that the input database is erroneous, and the notion of repair describes a maximally consistent subset of the input database, where different notions of maximality (such as subset and cardinality maximality) are considered. In this paper, we give a precise picture of the computational complexity of inconsistencytolerant (Boolean conjunctive) query answering in a wide range of Datalog± languages under the cardinality-based versions of the above three repair semantics.
SDRL: Interpretable and Data-Efficient Deep Reinforcement Learning Leveraging Symbolic Planning
Authors: Lyu Daoming , Yang Fangkai , Liu Bo , Gustafson Steven
Published: September 2019

Deep reinforcement learning (DRL) has gained great success by learning directly from high-dimensional sensory inputs, yet is notorious for the lack of interpretability. Interpretability of the subtasks is critical in hierarchical decision-making as it increases the transparency of black-box-style DRL approach and helps the RL practitioners to understand the high-level behavior of the system better. In this paper, we introduce symbolic planning into DRL and propose a framework of Symbolic Deep Reinforcement Learning (SDRL) that can handle both high-dimensional sensory inputs and symbolic planning. The task-level interpretability is enabled by relating symbolic actions to options.This framework features a planner – controller – meta-controller architecture, which takes charge of subtask scheduling, data-driven subtask learning, and subtask evaluation, respectively. The three components cross-fertilize each other and eventually converge to an optimal symbolic plan along with the learned subtasks, bringing together the advantages of long-term planning capability with symbolic knowledge and end-to-end reinforcement learning directly from a high-dimensional sensory input. Experimental results validate the interpretability of subtasks, along with improved data efficiency compared with state-of-the-art approaches.
Group Decision Diagram (GDD): A Compact Representation for Permutations
Authors: Maehara Takanori , Inoue Yuma
Published: September 2019

Permutation is a fundamental combinatorial object appeared in various areas in mathematics, computer science, and artificial intelligence. In some applications, a subset of a permutation group must be maintained efficiently. In this study, we develop a new data structure, called group decision diagram (GDD), to maintain a set of permutations. This data structure combines the zero-suppressed binary decision diagram with the computable subgroup chain of the permutation group. The data structure enables efficient operations, such as membership testing, set operations (e.g., union, intersection, and difference), and Cartesian product. Our experiments demonstrate that the data structure is efficient (i.e., 20–300 times faster) than the existing methods when the permutation group is considerably smaller than the symmetric group, or only subsets constructed by a few operations over generators are maintained.
Declarative Question Answering over Knowledge Bases Containing Natural Language Text with Answer Set Programming
Authors: Mitra Arindam , Clark Peter , Tafjord Oyvind , Baral Chitta
Published: September 2019

While in recent years machine learning (ML) based approaches have been the popular approach in developing endto-end question answering systems, such systems often struggle when additional knowledge is needed to correctly answer the questions. Proposed alternatives involve translating the question and the natural language text to a logical representation and then use logical reasoning. However, this alternative falters when the size of the text gets bigger. To address this we propose an approach that does logical reasoning over premises written in natural language text. The proposed method uses recent features of Answer Set Programming (ASP) to call external NLP modules (which may be based on ML) which perform simple textual entailment. To test our approach we develop a corpus based on the life cycle questions and showed that Our system achieves up to 18% performance gain when compared to standard MCQ solvers.
Blameworthiness in Strategic Games
Authors: Naumov Pavel , Tao Jia
Published: September 2019

There are multiple notions of coalitional responsibility. The focus of this paper is on the blameworthiness defined through the principle of alternative possibilities: a coalition is blamable for a statement if the statement is true, but the coalition had a strategy to prevent it. The main technical result is a sound and complete bimodal logical system that describes properties of blameworthiness in one-shot games.
Belief Change and Non-Monotonic Reasoning Sans Compactness
Authors: Ribeiro Jandson S. , Nayak Abhaya , Wassermann Renata
Published: September 2019

Belief change and non-monotonic reasoning are arguably different perspectives on the same phenomenon, namely, jettisoning of currently held beliefs in response to some incompatible evidence. Investigations in this area typically assume, among other things, that the underlying (background) logic is compact, that is, whatever can be inferred from a set of sentences X can be inferred from a finite subset of X. Recent research in the field shows that this compactness assumption can be dispensed without inflicting much damage on the AGM paradigm of belief change. In this paper we investigate the impact of such relaxation on non-monotonic logics instead. In particular, we show that, when compactness is not guaranteed, while the bridge from the AGM paradigm of belief change to expectation logics remains unaffected, the “return trip” from expectation logics to AGM paradigm is no longer guaranteed. We finally explore the conditions under which such guarantee can be given.
ATOMIC: An Atlas of Machine Commonsense for If-Then Reasoning
Authors: Sap Maarten , Le Bras Ronan , Allaway Emily , Bhagavatula Chandra , Lourie Nicholas , Rashkin Hannah , Roof Brendan , Smith Noah A. , Choi Yejin
Published: September 2019

We present ATOMIC, an atlas of everyday commonsense reasoning, organized through 877k textual descriptions of inferential knowledge. Compared to existing resources that center around taxonomic knowledge, ATOMIC focuses on inferential knowledge organized as typed if-then relations with variables (e.g., “if X pays Y a compliment, then Y will likely return the compliment”). We propose nine if-then relation types to distinguish causes vs. effects, agents vs. themes, voluntary vs. involuntary events, and actions vs. mental states. By generatively training on the rich inferential knowledge described in ATOMIC, we show that neural models can acquire simple commonsense capabilities and reason about previously unseen events. Experimental results demonstrate that multitask models that incorporate the hierarchical structure of if-then relation types lead to more accurate inference compared to models trained in isolation, as measured by both automatic and human evaluation.
Efficient Concept Induction for Description Logics
Authors: Sarker Md Kamruzzaman , Hitzler Pascal
Published: September 2019

Concept Induction refers to the problem of creating complex Description Logic class descriptions (i.e., TBox axioms) from instance examples (i.e., ABox data). In this paper we look particularly at the case where both a set of positive and a set of negative instances are given, and complex class expressions are sought under which the positive but not the negative examples fall. Concept induction has found applications in ontology engineering, but existing algorithms have fundamental performance issues in some scenarios, mainly because a high number of invokations of an external Description Logic reasoner is usually required. In this paper we present a new algorithm for this problem which drastically reduces the number of reasoner invokations needed. While this comes at the expense of a more limited traversal of the search space, we show that our approach improves execution times by up to several orders of magnitude, while output correctness, measured in the amount of correct coverage of the input instances, remains reasonably high in many cases. Our approach thus should provide a strong alternative to existing systems, in particular in settings where other systems are prohibitively slow.
An Open-World Extension to Knowledge Graph Completion Models
Authors: Shah Haseeb , Villmow Johannes , Ulges Adrian , Schwanecke Ulrich , Shafait Faisal
Published: September 2019

We present a novel extension to embedding-based knowledge graph completion models which enables them to perform open-world link prediction, i.e. to predict facts for entities unseen in training based on their textual description. Our model combines a regular link prediction model learned from a knowledge graph with word embeddings learned from a textual corpus. After training both independently, we learn a transformation to map the embeddings of an entity’s name and description to the graph-based embedding space.In experiments on several datasets including FB20k, DBPedia50k and our new dataset FB15k-237-OWE, we demonstrate competitive results. Particularly, our approach exploits the full knowledge graph structure even when textual descriptions are scarce, does not require a joint training on graph and text, and can be applied to any embedding-based link prediction model, such as TransE, ComplEx and DistMult.
Induction of Non-Monotonic Logic Programs to Explain Boosted Tree Models Using LIME
Authors: Shakerin Farhad , Gupta Gopal
Published: September 2019

We present a heuristic based algorithm to induce nonmonotonic logic programs that will explain the behavior of XGBoost trained classifiers. We use the technique based on the LIME approach to locally select the most important features contributing to the classification decision. Then, in order to explain the model’s global behavior, we propose the LIME-FOLD algorithm —a heuristic-based inductive logic programming (ILP) algorithm capable of learning nonmonotonic logic programs—that we apply to a transformed dataset produced by LIME. Our proposed approach is agnostic to the choice of the ILP algorithm. Our experiments with UCI standard benchmarks suggest a significant improvement in terms of classification evaluation metrics. Meanwhile, the number of induced rules dramatically decreases compared to ALEPH, a state-of-the-art ILP system.
End-to-End Structure-Aware Convolutional Networks for Knowledge Base Completion
Authors: Shang Chao , Tang Yun , Huang Jing , Bi Jinbo , He Xiaodong , Zhou Bowen
Published: September 2019

Knowledge graph embedding has been an active research topic for knowledge base completion, with progressive improvement from the initial TransE, TransH, DistMult et al to the current state-of-the-art ConvE. ConvE uses 2D convolution over embeddings and multiple layers of nonlinear features to model knowledge graphs. The model can be efficiently trained and scalable to large knowledge graphs. However, there is no structure enforcement in the embedding space of ConvE. The recent graph convolutional network (GCN) provides another way of learning graph node embedding by successfully utilizing graph connectivity structure. In this work, we propose a novel end-to-end StructureAware Convolutional Network (SACN) that takes the benefit of GCN and ConvE together. SACN consists of an encoder of a weighted graph convolutional network (WGCN), and a decoder of a convolutional network called Conv-TransE. WGCN utilizes knowledge graph node structure, node attributes and edge relation types. It has learnable weights that adapt the amount of information from neighbors used in local aggregation, leading to more accurate embeddings of graph nodes. Node attributes in the graph are represented as additional nodes in the WGCN. The decoder Conv-TransE enables the state-of-the-art ConvE to be translational between entities and relations while keeps the same link prediction performance as ConvE. We demonstrate the effectiveness of the proposed SACN on standard FB15k-237 and WN18RR datasets, and it gives about 10% relative improvement over the state-of-theart ConvE in terms of HITS@1, HITS@3 and HITS@10.
Iterated Belief Base Revision: A Dynamic Epistemic Logic Approach
Authors: Souza Marlo , Moreira Álvaro , Vieira Renata
Published: September 2019

AGM’s belief revision is one of the main paradigms in the study of belief change operations. In this context, belief bases (prioritised bases) have been largely used to specify the agent’s belief state - whether representing the agent’s ‘explicit beliefs’ or as a computational model for her belief state. While the connection of iterated AGM-like operations and their encoding in dynamic epistemic logics have been studied before, few works considered how well-known postulates from iterated belief revision theory can be characterised by means of belief bases and their counterpart in dynamic epistemic logic. This work investigates how priority graphs, a syntactic representation of preference relations deeply connected to prioritised bases, can be used to characterise belief change operators, focusing on well-known postulates of Iterated Belief Change. We provide syntactic representations of belief change operators in a dynamic context, as well as new negative results regarding the possibility of representing an iterated belief revision operation using transformations on priority graphs.
Safe Partial Diagnosis from Normal Observations
Authors: Stern Roni , Juba Brendan
Published: September 2019

Model-based diagnosis (MBD) is difficult to use in practice because it requires a model of the diagnosed system, which is often very hard to obtain. We explore theoretically how observing the system when it is in a normal state can provide information about the system that is sufficient to learn a partial system model that allows automated diagnosis. We analyze the number of observations needed to learn a model capable of finding faulty components in most cases. Then, we explore how knowing the system topology can help us to learn a useful model from the normal observations for settings in which many of the internal system variables cannot be observed. Unlike other data-driven methods, our learned model is safe, in the sense that subsystems identified as faulty are guaranteed to truly be faulty.
Reasoning over Streaming Data in Metric Temporal Datalog
Authors: Wałęga Przemysław Andrzej , Kaminski Mark , Grau Bernardo Cuenca
Published: September 2019

We study stream reasoning in datalogMTL—an extension of Datalog with metric temporal operators. We propose a sound and complete stream reasoning algorithm that is applicable to a fragment datalogMTLFP of datalogMTL, in which propagation of derived information towards past time points is precluded. Memory consumption in our algorithm depends both on the properties of the rule set and the input data stream; in particular, it depends on the distances between timestamps occurring in data. This is undesirable since these distances can be very small, in which case the algorithm may require large amounts of memory. To address this issue, we propose a second algorithm, where the size of the required memory becomes independent on the timestamps in the data at the expense of disallowing punctual intervals in the rule set. Finally, we provide tight bounds to the data complexity of standard query answering in datalogMTLFP without punctual intervals in rules, which yield a new PSPACE lower bound to the data complexity of the full datalogMTL.
TransGate: Knowledge Graph Embedding with Shared Gate Structure
Authors: Yuan Jun , Gao Neng , Xiang Ji
Published: September 2019

Embedding knowledge graphs (KGs) into continuous vector space is an essential problem in knowledge extraction. Current models continue to improve embedding by focusing on discriminating relation-specific information from entities with increasingly complex feature engineering. We noted that they ignored the inherent relevance between relations and tried to learn unique discriminate parameter set for each relation. Thus, these models potentially suffer from high time complexity and large parameters, preventing them from efficiently applying on real-world KGs. In this paper, we follow the thought of parameter sharing to simultaneously learn more expressive features, reduce parameters and avoid complex feature engineering. Based on gate structure from LSTM, we propose a novel model TransGate and develop shared discriminate mechanism, resulting in almost same space complexity as indiscriminate models. Furthermore, to develop a more effective and scalable model, we reconstruct the gate with weight vectors making our method has comparative time complexity against indiscriminate model. We conduct extensive experiments on link prediction and triplets classification. Experiments show that TransGate not only outperforms state-of-art baselines, but also reduces parameters greatly. For example, TransGate outperforms ConvE and RGCN with 6x and 17x fewer parameters, respectively. These results indicate that parameter sharing is a superior way to further optimize embedding and TransGate finds a better trade-off between complexity and expressivity.
Recursively Learning Causal Structures Using Regression-Based Conditional Independence Test
Authors: Zhang Hao , Zhou Shuigeng , Yan Chuanxu , Guan Jihong , Wang Xin
Published: September 2019

This paper addresses two important issues in causality inference. One is how to reduce redundant conditional independence (CI) tests, which heavily impact the efficiency and accuracy of existing constraint-based methods. Another is how to construct the true causal graph from a set of Markov equivalence classes returned by these methods.For the first issue, we design a recursive decomposition approach where the original data (a set of variables) is first decomposed into three small subsets, each of which is then recursively decomposed into three smaller subsets until none of subsets can be decomposed further. Consequently, redundant CI tests can be reduced by inferring causality from these subsets. Advantage of this decomposition scheme lies in two aspects: 1) it requires only low-order CI tests, and 2) it does not violate d-separation. Thus, the complete causality can be reconstructed by merging all the partial results of the subsets.For the second issue, we employ regression-based conditional independence test to check CIs in linear non-Gaussian additive noise cases, which can identify more causal directions by x−E(x|Z)⊥z (or y−E(y|Z)⊥z). Therefore, causal direction learning is no longer limited by the number of returned Vstructures and the consistent propagation.Extensive experiments show that the proposed method can not only substantially reduce redundant CI tests but also effectively distinguish the equivalence classes, thus is superior to the state of the art constraint-based methods in causality inference.
Tracking Logical Difference in Large-Scale Ontologies: A Forgetting-Based Approach
Authors: Zhao Yizheng , Alghamdi Ghadah , Schmidt Renate A. , Feng Hao , Stoilos Giorgos , Juric Damir , Khodadadi Mohammad
Published: September 2019

This paper explores how the logical difference between two ontologies can be tracked using a forgetting-based or uniform interpolation (UI)-based approach. The idea is that rather than computing all entailments of one ontology not entailed by the other ontology, which would be computationally infeasible, only the strongest entailments not entailed in the other ontology are computed. To overcome drawbacks of existing forgetting/uniform interpolation tools we introduce a new forgetting method designed for the task of computing the logical difference between different versions of large-scale ontologies. The method is sound and terminating, and can compute uniform interpolants for ALC-ontologies as large as SNOMED CT and NCIt. Our evaluation shows that the method can achieve considerably better success rates (>90%) and provides a feasible approach to computing the logical difference in large-scale ontologies, as a case study on different versions of SNOMED CT and NCIt ontologies shows.
State Abstraction as Compression in Apprenticeship Learning
Authors: Abel David , Arumugam Dilip , Asadi Kavosh , Jinnai Yuu , Littman Michael L. , Wong Lawson L.S.
Published: September 2019

State abstraction can give rise to models of environments that are both compressed and useful, thereby enabling efficient sequential decision making. In this work, we offer the first formalism and analysis of the trade-off between compression and performance made in the context of state abstraction for Apprenticeship Learning. We build on Rate-Distortion theory, the classic Blahut-Arimoto algorithm, and the Information Bottleneck method to develop an algorithm for computing state abstractions that approximate the optimal tradeoff between compression and performance. We illustrate the power of this algorithmic structure to offer insights into effective abstraction, compression, and reinforcement learning through a mixture of analysis, visuals, and experimentation.
An Exponential Tail Bound for the Deleted Estimate
Authors: Abou–Moustafa Karim , Szepesvári Csaba
Published: September 2019

There is an accumulating evidence in the literature that stability of learning algorithms is a key characteristic that permits a learning algorithm to generalize. Despite various insightful results in this direction, there seems to be an overlooked dichotomy in the type of stability-based generalization bounds we have in the literature. On one hand, the literature seems to suggest that exponential generalization bounds for the estimated risk, which are optimal, can be only obtained through stringent, distribution independent and computationally intractable notions of stability such as uniform stability. On the other hand, it seems that weaker notions of stability such as hypothesis stability, although it is distribution dependent and more amenable to computation, can only yield polynomial generalization bounds for the estimated risk, which are suboptimal. In this paper, we address the gap between these two regimes of results. In particular, the main question we address here is whether it is possible to derive exponential generalization bounds for the estimated risk using a notion of stability that is computationally tractable and distribution dependent, but weaker than uniform stability. Using recent advances in concentration inequalities, and using a notion of stability that is weaker than uniform stability but distribution dependent and amenable to computation, we derive an exponential tail bound for the concentration of the estimated risk of a hypothesis returned by a general learning rule, where the estimated risk is expressed in terms of the deleted estimate. Interestingly, we note that our final bound has similarities to previous exponential generalization bounds for the deleted estimate, in particular, the result of Bousquet and Elisseeff (2002) for the regression case.
Model Learning for Look-Ahead Exploration in Continuous Control
Authors: Agarwal Arpit , Muelling Katharina , Fragkiadaki Katerina
Published: September 2019

We propose an exploration method that incorporates lookahead search over basic learnt skills and their dynamics, and use it for reinforcement learning (RL) of manipulation policies. Our skills are multi-goal policies learned in isolation in simpler environments using existing multigoal RL formulations, analogous to options or macroactions. Coarse skill dynamics, i.e., the state transition caused by a (complete) skill execution, are learnt and are unrolled forward during lookahead search. Policy search benefits from temporal abstraction during exploration, though itself operates over low-level primitive actions, and thus the resulting policies does not suffer from suboptimality and inflexibility caused by coarse skill chaining. We show that the proposed exploration strategy results in effective learning of complex manipulation policies faster than current state-of-the-art RL methods, and converges to better policies than methods that use options or parametrized skills as building blocks of the policy itself, as opposed to guiding exploration. We show that the proposed exploration strategy results in effective learning of complex manipulation policies faster than current state-of-the-art RL methods, and converges to better policies than methods that use options or parameterized skills as building blocks of the policy itself, as opposed to guiding exploration.
Character-Level Language Modeling with Deeper Self-Attention
Authors: Al-Rfou Rami , Choe Dokook , Constant Noah , Guo Mandy , Jones Llion
Published: September 2019

LSTMs and other RNN variants have shown strong performance on character-level language modeling. These models are typically trained using truncated backpropagation through time, and it is common to assume that their success stems from their ability to remember long-term contexts. In this paper, we show that a deep (64-layer) transformer model (Vaswani et al. 2017) with fixed context outperforms RNN variants by a large margin, achieving state of the art on two popular benchmarks: 1.13 bits per character on text8 and 1.06 on enwik8. To get good results at this depth, we show that it is important to add auxiliary losses, both at intermediate network layers and intermediate sequence positions.