bluuebunny/crossref_metadata_2025 huggingface dataset:
Efficient Markov Network Structure Discovery Using Independence Tests
Authors: Bromberg F. , Margaritis D. , Honavar V.
Published: July 2018

We present two algorithms for learning the structure of a Markov network from data: GSMN* and GSIMN. Both algorithms use statistical independence tests to infer the structure by successively constraining the set of structures consistent with the results of these tests. Until very recently, algorithms for structure learning were based on maximum likelihood estimation, which has been proved to be NP-hard for Markov networks due to the difficulty of estimating the parameters of the network, needed for the computation of the data likelihood. The independence-based approach does not require the computation of the likelihood, and thus both GSMN* and GSIMN can compute the structure efficiently (as shown in our experiments). GSMN* is an adaptation of the Grow-Shrink algorithm of Margaritis and Thrun for learning the structure of Bayesian networks. GSIMN extends GSMN* by additionally exploiting Pearl's well-known properties of the conditional independence relation to infer novel independences from known ones, thus avoiding the performance of statistical tests to estimate them. To accomplish this efficiently GSIMN uses the Triangle theorem, also introduced in this work, which is a simplified version of the set of Markov axioms. Experimental comparisons on artificial and real-world data sets show GSIMN can yield significant savings with respect to GSMN*, while generating a Markov network with comparable or in some cases improved quality. We also compare GSIMN to a forward-chaining implementation, called GSIMN-FCH, that produces all possible conditional independences resulting from repeatedly applying Pearl's theorems on the known conditional independence tests. The results of this comparison show that GSIMN, by the sole use of the Triangle theorem, is nearly optimal in terms of the set of independences tests that it infers.
Content Modeling Using Latent Permutations
Authors: Chen H. , Branavan S.R.K. , Barzilay R. , Karger D. R.
Published: July 2018

We present a novel Bayesian topic model for learning discourse-level document structure. Our model leverages insights from discourse theory to constrain latent topic assignments in a way that reflects the underlying organization of document topics. We propose a global model in which both topic selection and ordering are biased to be similar across a collection of related documents. We show that this space of orderings can be effectively represented using a distribution over permutations called the Generalized Mallows Model. We apply our method to three complementary discourse-level tasks: cross-document alignment, document segmentation, and information ordering. Our experiments show that incorporating our permutation-based model in these applications yields substantial improvements in performance over previously proposed methods.
Approximate Strong Equilibrium in Job Scheduling Games
Authors: Feldman M. , Tamir T.
Published: July 2018

A Nash Equilibrium (NE) is a strategy profile resilient to unilateral deviations, and is predominantly used in the analysis of multiagent systems. A downside of NE is that it is not necessarily stable against deviations by coalitions. Yet, as we show in this paper, in some cases, NE does exhibit stability against coalitional deviations, in that the benefits from a joint deviation are bounded. In this sense, NE approximates strong equilibrium.

Coalition formation is a key issue in multiagent systems. We provide a framework for quantifying the stability and the performance of various assignment policies and solution concepts in the face of coalitional deviations. Within this framework we evaluate a given configuration according to three measures: (i) IR_min: the maximal number alpha, such that there exists a coalition in which the minimal improvement ratio among the coalition members is alpha, (ii) IR_max: the maximal number alpha, such that there exists a coalition in which the maximal improvement ratio among the coalition members is alpha, and (iii) DR_max: the maximal possible damage ratio of an agent outside the coalition.

We analyze these measures in job scheduling games on identical machines. In particular, we provide upper and lower bounds for the above three measures for both NE and the well-known assignment rule Longest Processing Time (LPT).

Our results indicate that LPT performs better than a general NE. However, LPT is not the best possible approximation. In particular, we present a polynomial time approximation scheme (PTAS) for the makespan minimization problem which provides a schedule with IR_min of 1+epsilon for any given epsilon. With respect to computational complexity, we show that given an NE on m >= 3 identical machines or m >= 2 unrelated machines, it is NP-hard to determine whether a given coalition can deviate such that every member decreases its cost.
Constructing Reference Sets from Unstructured, Ungrammatical Text
Authors: Michelson M. , Knoblock C. A.
Published: July 2018

Vast amounts of text on the Web are unstructured and ungrammatical, such as classified ads, auction listings, forum postings, etc. We call such text posts. Despite their inconsistent structure and lack of grammar, posts are full of useful information. This paper presents work on semi-automatically building tables of relational information, called reference sets, by analyzing such posts directly. Reference sets can be applied to a number of tasks such as ontology maintenance and information extraction. Our reference-set construction method starts with just a small amount of background knowledge, and constructs tuples representing the entities in the posts to form a reference set. We also describe an extension to this approach for the special case where even this small amount of background knowledge is impossible to discover and use. To evaluate the utility of the machine-constructed reference sets, we compare them to manually constructed reference sets in the context of reference-set-based information extraction. Our results show the reference sets constructed by our method outperform manually constructed reference sets. We also compare the reference-set-based extraction approach using the machine-constructed reference set to supervised extraction approaches using generic features. These results demonstrate that using machine-constructed reference sets outperforms the supervised methods, even though the supervised methods require training data.
Active Tuples-based Scheme for Bounding Posterior Beliefs
Authors: Bidyuk B. , Dechter R. , Rollon E.
Published: July 2018

The paper presents a scheme for computing lower and upper bounds on the posterior marginals in Bayesian networks with discrete variables. Its power lies in its ability to use any available scheme that bounds the probability of evidence or posterior marginals and enhance its performance in an anytime manner. The scheme uses the cutset conditioning principle to tighten existing bounding schemes and to facilitate anytime behavior, utilizing a fixed number of cutset tuples. The accuracy of the bounds improves as the number of used cutset tuples increases and so does the computation time. We demonstrate empirically the value of our scheme for bounding posterior marginals and probability of evidence using a variant of the bound propagation algorithm as a plug-in scheme.
Mixed Strategies in Combinatorial Agency
Authors: Babaioff M. , Feldman M. , Nisan N.
Published: July 2018

In many multiagent domains a set of agents exert effort towards a joint outcome, yet the individual effort levels cannot be easily observed. A typical example for such a scenario is routing in communication networks, where the sender can only observe whether the packet reached its destination, but often has no information about the actions of the intermediate routers, which influences the final outcome. We study a setting where a principal needs to motivate a team of agents whose combination of hidden efforts stochastically determines an outcome. In a companion paper we devise and study a basic ''combinatorial agency'' model for this setting, where the principal is restricted to inducing a pure Nash equilibrium. Here we study various implications of this restriction. First, we show that, in contrast to the case of observable efforts, inducing a mixed-strategies equilibrium may be beneficial for the principal. Second, we present a sufficient condition for technologies for which no gain can be generated. Third, we bound the principal's gain for various families of technologies. Finally, we study the robustness of mixed equilibria to coalitional deviations and the computational hardness of the optimal mixed equilibria.
Using Local Alignments for Relation Recognition
Authors: Katrenko S. , Adriaans P. W. , Van Someren M.
Published: July 2018

This paper discusses the problem of marrying structural similarity with semantic relatedness for Information Extraction from text. Aiming at accurate recognition of relations, we introduce local alignment kernels and explore various possibilities of using them for this task. We give a definition of a local alignment (LA) kernel based on the Smith-Waterman score as a sequence similarity measure and proceed with a range of possibilities for computing similarity between elements of sequences. We show how distributional similarity measures obtained from unlabeled data can be incorporated into the learning task as semantic knowledge. Our experiments suggest that the LA kernel yields promising results on various biomedical corpora outperforming two baselines by a large margin. Additional series of experiments have been conducted on the data sets of seven general relation types, where the performance of the LA kernel is comparable to the current state-of-the-art results.
Change in Abstract Argumentation Frameworks: Adding an Argument
Authors: Cayrol C. , Dupin de Saint-Cyr F. , Lagasquie-Schiex M.
Published: July 2018

In this paper, we address the problem of change in an abstract argumentation system. We focus on a particular change: the addition of a new argument which interacts with previous arguments. We study the impact of such an addition on the outcome of the argumentation system, more particularly on the set of its extensions. Several properties for this change operation are defined by comparing the new set of extensions to the initial one, these properties are called structural when the comparisons are based on set-cardinality or set-inclusion relations. Several other properties are proposed where comparisons are based on the status of some particular arguments: the accepted arguments; these properties refer to the evolution of this status during the change, e.g., Monotony and Priority to Recency. All these properties may be more or less desirable according to specific applications. They are studied under two particular semantics: the grounded and preferred semantics.
Cause Identification from Aviation Safety Incident Reports via Weakly Supervised Semantic Lexicon Construction
Authors: Abedin M. A. , Ng V. , Khan L.
Published: July 2018

The Aviation Safety Reporting System collects voluntarily submitted reports on aviation safety incidents to facilitate research work aiming to reduce such incidents. To effectively reduce these incidents, it is vital to accurately identify why these incidents occurred. More precisely, given a set of possible causes, or shaping factors, this task of cause identification involves identifying all and only those shaping factors that are responsible for the incidents described in a report. We investigate two approaches to cause identification. Both approaches exploit information provided by a semantic lexicon, which is automatically constructed via Thelen and Riloff's Basilisk framework augmented with our linguistic and algorithmic modifications. The first approach labels a report using a simple heuristic, which looks for the words and phrases acquired during the semantic lexicon learning process in the report. The second approach recasts cause identification as a text classification problem, employing supervised and transductive text classification algorithms to learn models from incident reports labeled with shaping factors and using the models to label unseen reports. Our experiments show that both the heuristic-based approach and the learning-based approach (when given sufficient training data) outperform the baseline system significantly.
Multiattribute Auctions Based on Generalized Additive Independence
Authors: Engel Y. , Wellman M. P.
Published: July 2018

We develop multiattribute auctions that accommodate generalized additive independent (GAI) preferences. We propose an iterative auction mechanism that maintains prices on potentially overlapping GAI clusters of attributes, thus decreases elicitation and computational burden, and creates an open competition among suppliers over a multidimensional domain. Most significantly, the auction is guaranteed to achieve surplus which approximates optimal welfare up to a small additive factor, under reasonable equilibrium strategies of traders. The main departure of GAI auctions from previous literature is to accommodate non-additive trader preferences, hence allowing traders to condition their evaluation of specific attributes on the value of other attributes. At the same time, the GAI structure supports a compact representation of prices, enabling a tractable auction process. We perform a simulation study, demonstrating and quantifying the significant efficiency advantage of more expressive preference modeling. We draw random GAI-structured utility functions with various internal structures, generate additive functions that approximate the GAI utility, and compare the performance of the auctions using the two representations. We find that allowing traders to express existing dependencies among attributes improves the economic efficiency of multiattribute auctions.
Approximate Model-Based Diagnosis Using Greedy Stochastic Search
Authors: Feldman A. , Provan G. , Van Gemund A.
Published: July 2018

We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.
Intrusion Detection using Continuous Time Bayesian Networks
Authors: Xu J. , Shelton C. R.
Published: July 2018

Intrusion detection systems (IDSs) fall into two high-level categories: network-based systems (NIDS) that monitor network behaviors, and host-based systems (HIDS) that monitor system calls. In this work, we present a general technique for both systems. We use anomaly detection, which identifies patterns not conforming to a historic norm. In both types of systems, the rates of change vary dramatically over time (due to burstiness) and over components (due to service difference). To efficiently model such systems, we use continuous time Bayesian networks (CTBNs) and avoid specifying a fixed update interval common to discrete-time models. We build generative models from the normal training data, and abnormal behaviors are flagged based on their likelihood under this norm. For NIDS, we construct a hierarchical CTBN model for the network packet traces and use Rao-Blackwellized particle filtering to learn the parameters. We illustrate the power of our method through experiments on detecting real worms and identifying hosts on two publicly available network traces, the MAWI dataset and the LBNL dataset. For HIDS, we develop a novel learning method to deal with the finite resolution of system log file time stamps, without losing the benefits of our continuous time model. We demonstrate the method by detecting intrusions in the DARPA 1998 BSM dataset.
Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints
Authors: Greco G. , Malizia E. , Palopoli L. , Scarcello F.
Published: July 2018

Coalitional games serve the purpose of modeling payoff distribution problems in scenarios where agents can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. In the classical Transferable Utility (TU) setting, coalition worths can be freely distributed amongst agents. However, in several application scenarios, this is not the case and the Non-Transferable Utility setting (NTU) must be considered, where additional application-oriented constraints are imposed on the possible worth distributions.

In this paper, an approach to define NTU games is proposed which is based on describing allowed distributions via a set of mixed-integer linear constraints applied to an underlying TU game. It is shown that such games allow non-transferable conditions on worth distributions to be specified in a natural and succinct way. The properties and the relationships among the most prominent solution concepts for NTU games that hold when they are applied on (mixed-integer) constrained games are investigated. Finally, a thorough analysis is carried out to assess the impact of issuing constraints on the computational complexity of some of these solution concepts.
A Minimum Relative Entropy Principle for Learning and Acting
Authors: Ortega P. A. , Braun D. A.
Published: July 2018

This paper proposes a method to construct an adaptive agent that is universal with respect to a given class of experts, where each expert is designed specifically for a particular environment. This adaptive control problem is formalized as the problem of minimizing the relative entropy of the adaptive agent from the expert that is most suitable for the unknown environment. If the agent is a passive observer, then the optimal solution is the well-known Bayesian predictor. However, if the agent is active, then its past actions need to be treated as causal interventions on the I/O stream rather than normal probability conditions. Here it is shown that the solution to this new variational problem is given by a stochastic controller called the Bayesian control rule, which implements adaptive behavior as a mixture of experts. Furthermore, it is shown that under mild assumptions, the Bayesian control rule converges to the control law of the most suitable expert.
Implicit Abstraction Heuristics
Authors: Katz M. , Domshlak C.
Published: July 2018

State-space search with explicit abstraction heuristics is at the state of the art of cost-optimal planning. These heuristics are inherently limited, nonetheless, because the size of the abstract space must be bounded by some, even if a very large, constant. Targeting this shortcoming, we introduce the notion of (additive) implicit abstractions, in which the planning task is abstracted by instances of tractable fragments of optimal planning. We then introduce a concrete setting of this framework, called fork-decomposition, that is based on two novel fragments of tractable cost-optimal planning. The induced admissible heuristics are then studied formally and empirically. This study testifies for the accuracy of the fork decomposition heuristics, yet our empirical evaluation also stresses the tradeoff between their accuracy and the runtime complexity of computing them. Indeed, some of the power of the explicit abstraction heuristics comes from precomputing the heuristic function offline and then determining h(s) for each evaluated state s by a very fast lookup in a ``database.'' By contrast, while fork-decomposition heuristics can be calculated in polynomial time, computing them is far from being fast. To address this problem, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. We demonstrate that an equivalent of the explicit abstraction notion of a ``database'' exists for the fork-decomposition abstractions as well, despite their exponential-size abstract spaces. We then verify empirically that heuristic search with the ``databased" fork-decomposition heuristics favorably competes with the state of the art of cost-optimal planning.
An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem
Authors: Jäger G. , Zhang W.
Published: July 2018

The Hamiltonian cycle problem (HCP) is an important combinatorial problem with applications in many areas. It is among the first problems used for studying intrinsic properties, including phase transitions, of combinatorial problems. While thorough theoretical and experimental analyses have been made on the HCP in undirected graphs, a limited amount of work has been done for the HCP in directed graphs (DHCP).
The main contribution of this work is an effective algorithm for the DHCP. Our algorithm explores and exploits the close relationship between the DHCP and the Assignment Problem (AP) and utilizes a technique based on Boolean satisfiability (SAT). By combining effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms, including an algorithm based on the award-winning Concorde TSP algorithm. The second result of the current study is an experimental analysis of phase transitions of the DHCP, verifying and refining a known phase transition of the DHCP.
Narrowing the Modeling Gap: A Cluster-Ranking Approach to Coreference Resolution
Authors: Rahman A. , Ng V.
Published: July 2018

Traditional learning-based coreference resolvers operate by training the mention-pair model for determining whether two mentions are coreferent or not. Though conceptually simple and easy to understand, the mention-pair model is linguistically rather unappealing and lags far behind the heuristic-based coreference models proposed in the pre-statistical NLP era in terms of sophistication. Two independent lines of recent research have attempted to improve the mention-pair model, one by acquiring the mention-ranking model to rank preceding mentions for a given anaphor, and the other by training the entity-mention model to determine whether a preceding cluster is coreferent with a given mention. We propose a cluster-ranking approach to coreference resolution, which combines the strengths of the mention-ranking model and the entity-mention model, and is therefore theoretically more appealing than both of these models. In addition, we seek to improve cluster rankers via two extensions: (1) lexicalization and (2) incorporating knowledge of anaphoricity by jointly modeling anaphoricity determination and coreference resolution. Experimental results on the ACE data sets demonstrate the superior performance of cluster rankers to competing approaches as well as the effectiveness of our two extensions.
A Monte-Carlo AIXI Approximation
Authors: Veness J. , Ng K.S. , Hutter M. , Uther W. , Silver D.
Published: July 2018

This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. Our approach is based on a direct approximation of AIXI, a Bayesian optimality notion for general reinforcement learning agents. Previously, it has been unclear whether the theory of AIXI could motivate the design of practical algorithms. We answer this hitherto open question in the affirmative, by providing the first computationally feasible approximation to the AIXI agent. To develop our approximation, we introduce a new Monte-Carlo Tree Search algorithm along with an agent-specific extension to the Context Tree Weighting algorithm. Empirically, we present a set of encouraging results on a variety of stochastic and partially observable domains. We conclude by proposing a number of directions for future research.
Non-Deterministic Policies in Markovian Decision Processes
Authors: Milani Fard M. , Pineau J.
Published: July 2018

Markovian processes have long been used to model stochastic environments. Reinforcement learning has emerged as a framework to solve sequential planning and decision-making problems in such environments. In recent years, attempts were made to apply methods from reinforcement learning to construct decision support systems for action selection in Markovian environments. Although conventional methods in reinforcement learning have proved to be useful in problems concerning sequential decision-making, they cannot be applied in their current form to decision support systems, such as those in medical domains, as they suggest policies that are often highly prescriptive and leave little room for the user's input. Without the ability to provide flexible guidelines, it is unlikely that these methods can gain ground with users of such systems.

This paper introduces the new concept of non-deterministic policies to allow more flexibility in the user's decision-making process, while constraining decisions to remain near optimal solutions. We provide two algorithms to compute non-deterministic policies in discrete domains. We study the output and running time of these method on a set of synthetic and real-world problems. In an experiment with human subjects, we show that humans assisted by hints based on non-deterministic policies outperform both human-only and computer-only agents in a web navigation task.
Second-Order Consistencies
Authors: Lecoutre C. , Cardon S. , Vion J.
Published: July 2018

In this paper, we propose a comprehensive study of second-order consistencies (i.e., consistencies identifying inconsistent pairs of values) for constraint satisfaction. We build a full picture of the relationships existing between four basic second-order consistencies, namely path consistency (PC), 3-consistency (3C), dual consistency (DC) and 2-singleton arc consistency (2SAC), as well as their conservative and strong variants. Interestingly, dual consistency is an original property that can be established by using the outcome of the enforcement of generalized arc consistency (GAC), which makes it rather easy to obtain since constraint solvers typically maintain GAC during search. On binary constraint networks, DC is equivalent to PC, but its restriction to existing constraints, called conservative dual consistency (CDC), is strictly stronger than traditional conservative consistencies derived from path consistency, namely partial path consistency (PPC) and conservative path consistency (CPC). After introducing a general algorithm to enforce strong (C)DC, we present the results of an experimentation over a wide range of benchmarks that demonstrate the interest of (conservative) dual consistency. In particular, we show that enforcing (C)DC before search clearly improves the performance of MAC (the algorithm that maintains GAC during search) on several binary and non-binary structured problems.
Identifying Aspects for Web-Search Queries
Authors: Wu F. , Madhavan J. , Halevy A.
Published: July 2018

Many web-search queries serve as the beginning of an exploration of an unknown space of information, rather than looking for a specific web page. To answer such queries effec- tively, the search engine should attempt to organize the space of relevant information in a way that facilitates exploration.

We describe the Aspector system that computes aspects for a given query. Each aspect is a set of search queries that together represent a distinct information need relevant to the original search query. To serve as an effective means to explore the space, Aspector computes aspects that are orthogonal to each other and to have high combined coverage.

Aspector combines two sources of information to compute aspects. We discover candidate aspects by analyzing query logs, and cluster them to eliminate redundancies. We then use a mass-collaboration knowledge base (e.g., Wikipedia) to compute candidate aspects for queries that occur less frequently and to group together aspects that are likely to be semantically related. We present a user study that indicates that the aspects we compute are rated favorably against three competing alternatives  related searches proposed by Google, cluster labels assigned by the Clusty search engine, and navigational searches proposed by Bing.
Soft Constraints of Difference and Equality
Authors: Hebrard E. , Marx D. , O'Sullivan B. , Razgon I.
Published: July 2018

In many combinatorial problems one may need to model the diversity or similarity of assignments in a solution. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.
Value of Information Lattice: Exploiting Probabilistic Independence for Effective Feature Subset Acquisition
Authors: Bilgic M. , Getoor L.
Published: July 2018

We address the cost-sensitive feature acquisition problem, where misclassifying an instance is costly but the expected misclassification cost can be reduced by acquiring the values of the missing features. Because acquiring the features is costly as well, the objective is to acquire the right set of features so that the sum of the feature acquisition cost and misclassification cost is minimized. We describe the Value of Information Lattice (VOILA), an optimal and efficient feature subset acquisition framework. Unlike the common practice, which is to acquire features greedily, VOILA can reason with subsets of features. VOILA efficiently searches the space of possible feature subsets by discovering and exploiting conditional independence properties between the features and it reuses probabilistic inference computations to further speed up the process. Through empirical evaluation on five medical datasets, we show that the greedy strategy is often reluctant to acquire features, as it cannot forecast the benefit of acquiring multiple features in combination.
Probabilistic Relational Planning with First Order Decision Diagrams
Authors: Joshi S. , Khardon R.
Published: July 2018

Dynamic programming algorithms have been successfully applied to propositional stochastic planning problems by using compact representations, in particular algebraic decision diagrams, to capture domain dynamics and value functions. Work on symbolic dynamic programming lifted these ideas to first order logic using several representation schemes. Recent work introduced a first order variant of decision diagrams (FODD) and developed a value iteration algorithm for this representation. This paper develops several improvements to the FODD algorithm that make the approach practical. These include, new reduction operators that decrease the size of the representation, several speedup techniques, and techniques for value approximation. Incorporating these, the paper presents a planning system, FODD-Planner, for solving relational stochastic planning problems. The system is evaluated on several domains, including problems from the recent international planning competition, and shows competitive performance with top ranking systems. This is the first demonstration of feasibility of this approach and it shows that abstraction through compact representation is a promising approach to stochastic planning.
Scaling up Heuristic Planning with Relational Decision Trees
Authors: De la Rosa T. , Jimenez S. , Fuentetaja R. , Borrajo D.
Published: July 2018

Current evaluation functions for heuristic planning are expensive to compute. In numerous planning problems these functions provide good guidance to the solution, so they are worth the expense. However, when evaluation functions are misguiding or when planning problems are large enough, lots of node evaluations must be computed, which severely limits the scalability of heuristic planners. In this paper, we present a novel solution for reducing node evaluations in heuristic planning based on machine learning. Particularly, we define the task of learning search control for heuristic planning as a relational classification task, and we use an off-the-shelf relational classification tool to address this learning task. Our relational classification task captures the preferred action to select in the different planning contexts of a specific planning domain. These planning contexts are defined by the set of helpful actions of the current state, the goals remaining to be achieved, and the static predicates of the planning task. This paper shows two methods for guiding the search of a heuristic planner with the learned classifiers. The first one consists of using the resulting classifier as an action policy. The second one consists of applying the classifier to generate lookahead states within a Best First Search algorithm. Experiments over a variety of domains reveal that our heuristic planner using the learned classifiers solves larger problems than state-of-the-art planners.
Sequential Diagnosis by Abstraction
Authors: Siddiqi S. A. , Huang J.
Published: July 2018

When a system behaves abnormally, sequential diagnosis takes a sequence of measurements of the system until the faults causing the abnormality are identified, and the goal is to reduce the diagnostic cost, defined here as the number of measurements. To propose measurement points, previous work employs a heuristic based on reducing the entropy over a computed set of diagnoses. This approach generally has good performance in terms of diagnostic cost, but can fail to diagnose large systems when the set of diagnoses is too large. Focusing on a smaller set of probable diagnoses scales the approach but generally leads to increased average diagnostic costs. In this paper, we propose a new diagnostic framework employing four new techniques, which scales to much larger systems with good performance in terms of diagnostic cost.
First, we propose a new heuristic for measurement point selection that can be computed efficiently, without requiring the set of diagnoses, once the system is modeled as a Bayesian network and compiled into a logical form known as d-DNNF. Second, we extend hierarchical diagnosis, a technique based on system abstraction from our previous work, to handle probabilities so that it can be applied to sequential diagnosis to allow larger systems to be diagnosed. Third, for the largest systems where even hierarchical diagnosis fails, we propose a novel method that converts the system into one that has a smaller abstraction and whose diagnoses form a superset of those of the original system; the new system can then be diagnosed and the result mapped back to the original system. Finally, we propose a novel cost estimation function which can be used to choose an abstraction of the system that is more likely to provide optimal average cost. Experiments with ISCAS-85 benchmark circuits indicate that our approach scales to all circuits in the suite except one that has a flat structure not susceptible to useful abstraction.
Efficient Multi-Start Strategies for Local Search Algorithms
Authors: György A. , Kocsis L.
Published: July 2018

Local search algorithms applied to optimization problems often suffer from getting trapped in a local optimum. The common solution for this deficiency is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resources (in particular, processing time) to the instances depending on their behavior. Hence, a multi-start strategy has to decide (dynamically) when to allocate additional resources to a particular instance and when to start new instances. In this paper we propose multi-start strategies motivated by works on multi-armed bandit problems and Lipschitz optimization with an unknown constant. The strategies continuously estimate the potential performance of each algorithm instance by supposing a convergence rate of the local search algorithm up to an unknown constant, and in every phase allocate resources to those instances that could converge to the optimum for a particular range of the constant. Asymptotic bounds are given on the performance of the strategies. In particular, we prove that at most a quadratic increase in the number of times the target function is evaluated is needed to achieve the performance of a local search algorithm started from the attraction region of the optimum. Experiments are provided using SPSA (Simultaneous Perturbation Stochastic Approximation) and k-means as local search algorithms, and the results indicate that the proposed strategies work well in practice, and, in all cases studied, need only logarithmically more evaluations of the target function as opposed to the theoretically suggested quadratic increase.
On the Intertranslatability of Argumentation Semantics
Authors: Dvořák W. , Woltran S.
Published: July 2018

Translations between different nonmonotonic formalisms always have been an important topic in the field, in particular to understand the knowledge-representation capabilities those formalisms offer. We provide such an investigation in terms of different semantics proposed for abstract argumentation frameworks, a nonmonotonic yet simple formalism which received increasing interest within the last decade. Although the properties of these different semantics are nowadays well understood, there are no explicit results about intertranslatability. We provide such translations wrt. different properties and also give a few novel complexity results which underlie some negative results.
Controlling Complexity in Part-of-Speech Induction
Authors: Graca J. V. , Ganchev K. , Coheur L. , Pereira F. , Taskar B.
Published: July 2018

We consider the problem of fully unsupervised learning of grammatical (part-of-speech) categories from unlabeled text. The standard maximum-likelihood hidden Markov model for this task performs poorly, because of its weak inductive bias and large model capacity. We address this problem by refining the model and modifying the learning objective to control its capacity via para- metric and non-parametric constraints. Our approach enforces word-category association sparsity, adds morphological and orthographic features, and eliminates hard-to-estimate parameters for rare words. We develop an efficient learning algorithm that is not much more computationally intensive than standard training. We also provide an open-source implementation of the algorithm. Our experiments on five diverse languages (Bulgarian, Danish, English, Portuguese, Spanish) achieve significant improvements compared with previous methods for the same task.
Decidability and Undecidability Results for Propositional Schemata
Authors: Aravantinos V. , Caferra R. , Peltier N.
Published: July 2018

We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions and iterated connectives ranging over intervals parameterized by arithmetic variables. The satisfiability problem is shown to be undecidable for this new logic, but we introduce a very general class of schemata, called bound-linear, for which this problem becomes decidable. This result is obtained by reduction to a particular class of schemata called regular, for which we provide a sound and complete terminating proof procedure. This schemata calculus allows one to capture proof patterns corresponding to a large class of problems specified in propositional logic. We also show that the satisfiability problem becomes again undecidable for slight extensions of this class, thus demonstrating that bound-linear schemata represent a good compromise between expressivity and decidability.
Denis Earp: a lifetime in dam engineering
Authors: Pether Rachel
Published: July 2018

Denis Earp has been one of the UK's longest serving and most prolific panel engineers, undertaking 330 reservoir inspections during 30 years of continuous appointment to the panel. In the 1980s, he inspected every single reservoir owned at that time by the predecessor of Dŵr Cymru Welsh Water. I interviewed Denis at his home in Swansea, where he lives with his wife Jean.
A Cardiac Risk Score Based on Sudomotor Function to Evaluate Cardiac Autonomic Neuropathy in asymptomatic Chinese Patients with Diabetes Mellitus v1
Authors: YUAN* Tao , LI* Jiapei , FU Yong , LI Juan , WANG Xiangqing , ZHOU Ying , Dong Yingyue , ZHAO Weigang
Published: July 2018

This is a cross-sectional study among patients with diabetes mellitus who visit Peking Union Medical College Hospital. The recruited subjects undertake sudomotor function tests using SUDOSCAN(Impeto Medical, Paris, France) and cardiac autonomic reflex tests (CARTs), including heart rate variability due to Valsalva maneuver (Valsalva ratio), heart rate response due to deep breathing (HRB) and heart rate response due to standing up (HRS). Presenting 2 abnormal CARTs is defined as cardiac autonomic neuropathy(CAN). CANRS is calculated by the results of sudomotor function tests using SUDOSCAN. Subjects with CAN are included into the Positive Group and subjects without CAN are included into the Negative Group.The clinical parameters and sudomotor functions are compared between the two groups. The relationship between CANRS and the results of the CARTs is evaluated by Spearman’s rank correlation and linear regression analysis. A series of receiver operating character (ROC) curves are calculated to evaluate the diagnostic efficacy of CANRS detecting CAN.
Quando eu sou o Outro: problemas de ethos e identidade no filme Pequeno Grande Homem
Authors: De Oliveira Carlos Böes
Published: July 2018

RESUMO: Este artigo pretende estudar a relação da construção do ethos e da identidade no personagem principal do filme Pequeno Grande Homem (Little Big Man, 1970) de Arthur Penn, além de salientar as representações do Outro (os nativos norte-americanos) na narrativa fílmica. Através de um encontro interdisciplinar entre componentes da Análise do discurso (AD), da linha francesa de Maingueneau, e os estudos culturais, propomos uma visão mais ampla sobre a questão do eu e do Outro no gênero de faroeste. Os referencias teóricos estão focados em Tzvetan Todorov e Stuart Hall, para analisarmos a questão do Outro, a cultura e a identidade. Para enveredarmos na temática do ethos, buscamos teorias do discurso baseadas nos estudos de Dominique Maingueneau, que, por sinal, pertencem à linha de pesquisa da AD de linha francesa. Pretendemos, através deste estudo, problematizar a questão do Outro, entendendo que o personagem principal do filme desconstrói um ethos pré-discursivo, estabelecido na cultura norte-americana, em que a tradição via o nativo como selvagem e bestial.

PALAVRAS-CHAVE: Pequeno Grande Homem; outro; ethos; identidade; faroeste.

 

ABSTRACT: This paper intends to analyze the relation of ethos and identity construction in the protagonist of the film Little Big Man (Arthur Penn, 1970), besides stressing out the representations of the Other (the North American natives) in the filmic narrative. Through an interdisciplinary approach between components of the Discourse Analysis from the French studies of Maingueneau, and cultural studies, we propose a substantial vision about the matter of the other and I in the western genre. The theoretical references are focused on Tzvetan Todorov and Stuart Hall, to analyze the matter of the other, culture and identity. To analyze the discursive ethos, we relied on discourse theories based on the studies of Dominique Maingueneau, that, by the way, belong to the French Discourse Analysis. Through this study, we intend to problematize the issue of the other, understanding that the protagonist of the film deconstructs a pre-discursive ethos, established on the North American culture, where tradition saw the native as a savage.

KEYWORDS: Little Big Man; other; ethos; identity; western.
Uso de recursos podcast e webquest no estudo do tema avaliação na educação infantil
Authors: Carvalho Fernanda Beatriz da Costa Miranda de , Lima Cristhiane Pereira de , Dutra Alessandra , Rosa Vanderley Flor da , Oliveira Jair de
Published: July 2018

RESUMO:As tecnologias de informação e comunicação estão presentes na vida das pessoas nas mais diversas esferas sociais. Na educacional, por exemplo, elas colaboram no sentido de otimizar o processo de ensino e aprendizagem. No entanto, é necessário que os profissionais da educação desenvolvam conhecimentos e competências para saber utilizar de maneira significativa todos esses recursos. Assim, este estudo busca discutir os resultados da aplicação das ferramentas podcast e webquest na apresentação do conteúdo “Avaliação na Educação Infantil” a alunos de uma escola pública localizada ao norte do Paraná, de um curso de formação de professores, modalidade Médio Integrado, voltado para formação de docentes da Educação Infantil e dos anos iniciais do Ensino Fundamental. Para isso, foram utilizados os tipos de pesquisa bibliográfica, de campo e analítica. Os resultados apontam que o uso da ferramenta podcast na prática pedagógica enriqueceu as tarefas propostas e executadas e despertou a autonomia e a criticidade nas respostas fornecidas pelos alunos. Além disso, as tarefas propostas aos alunos por meio da webquest despertaram maior interesse, curiosidade e entusiasmo nos alunos, os quais participaram de forma dinâmica e colaborativa, instigando-os a serem sujeitos ativos do processo de construção do próprio conhecimento.

PALAVRAS-CHAVE: tecnologias; ensino; formação de professor.

 

ABSTRACT:The Information and communication technologies are present in the lives of people in many different spheres. In education, for instance, they collaborate to optimize the teaching and learning process. However, it is necessary for professionals of education to develop knowledge and skills to know how to use these resources in a meaningful way. Thus, this study seeks to discuss the results of the application of the podcast and webquest tools used to present the content Assessment in Early Childhood Education to students of a teacher training course, Integrated High School modality, aimed at the training of Teachers of Early Childhood Education and Early Years of Teaching of a public school, located in the north of Paraná. For this, the types of bibliographic, field and analytical research were used. The results point out that the use of the podcast tool in pedagogical practice, enriched the tasks proposed and executed and awoke the autonomy and criticality in the answers provided by the students. In addition, the proposed tasks aroused greater interest and curiosity in the students, who participated in activities in a dynamic and collaborative way, being instigated to be active subjects of the process of building their own knowledge.

KEYWORDS: technologies; teaching; teacher training.