bluuebunny/crossref_metadata_2025 huggingface dataset:
Generalizing Boolean Satisfiability II: Theory
Authors: Dixon H. E. , Ginsberg M. L. , Luks E. M. , Parkes A. J.
Published: July 2018

This is the second of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper presents the theoretical basis for the ideas underlying ZAP, arguing that existing ideas in this area exploit a single, recurring structure in that multiple database axioms can be obtained by operating on a single axiom using a subgroup of the group of permutations on the literals in the problem. We argue that the group structure precisely captures the general structure at which earlier approaches hinted, and give numerous examples of its use. We go on to extend the Davis-Putnam-Logemann-Loveland inference procedure to this broader setting, and show that earlier computational improvements are either subsumed or left intact by the new method. The third paper in this series discusses ZAP's implementation and presents experimental performance results.
Generalizing Boolean Satisfiability III: Implementation
Authors: Dixon H. E. , Ginsberg M. L. , Hofer D. , Luks E. M. , Parkes A. J.
Published: July 2018

This is the third of three papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal has been to define a representation in which this structure is apparent and can be exploited to improve computational performance. The first paper surveyed existing work that (knowingly or not) exploited problem structure to improve the performance of satisfiability engines, and the second paper showed that this structure could be understood in terms of groups of permutations acting on individual clauses in any particular Boolean theory. We conclude the series by discussing the techniques needed to implement our ideas, and by reporting on their performance on a variety of problem instances.
Risk-Sensitive Reinforcement Learning Applied to Control under Constraints
Authors: Geibel P. , Wysotzki F.
Published: July 2018

In this paper, we consider Markov Decision Processes (MDPs) with error states. Error states are those states entering which is undesirable or dangerous. We define the risk with respect to a policy as the probability of entering such a state when the policy is pursued. We consider the problem of finding good policies whose risk is smaller than some user-specified threshold, and formalize it as a constrained MDP with two criteria. The first criterion corresponds to the value function originally given. We will show that the risk can be formulated as a second criterion function based on a cumulative return, whose definition is independent of the original value function. We present a model free, heuristic reinforcement learning algorithm that aims at finding good deterministic policies. It is based on weighting the original value function and the risk. The weight parameter is adapted in order to find a feasible solution for the constrained problem that has a good performance with respect to the value function. The algorithm was successfully applied to the control of a feed tank with stochastic inflows that lies upstream of a distillation column. This control task was originally formulated as an optimal control problem with chance constraints, and it was solved under certain assumptions on the model to obtain an optimal solution. The power of our learning algorithm is that it can be used even when some of these restrictive assumptions are relaxed.
Hiding Satisfying Assignments: Two are Better than One
Authors: Achlioptas D. , Jia H. , Moore C.
Published: July 2018

The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-SAT formulas whose clauses are chosen uniformly from among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, for a number of different algorithms, A acts as a stronger and stronger attractor as the formula's density increases. Motivated by recent results on the geometry of the space of satisfying truth assignments of random k-SAT and NAE-k-SAT formulas, we introduce a simple twist on this basic model, which appears to dramatically increase its hardness. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and compliment of A are satisfying. It appears that under this "symmetrization" the effects of the two attractors largely cancel out, making it much harder for algorithms to find any truth assignment. We give theoretical and experimental evidence supporting this assertion.
The Fast Downward Planning System
Authors: Helmert M.
Published: July 2018

Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multi-valued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactions of operators.

In this article, we give a full account of Fast Downward's approach to solving multi-valued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward's best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multi-heuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way.

Fast Downward has proven remarkably successful: It won the "classical'' (i.e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.
Representing Conversations for Scalable Overhearing
Authors: Gutnik G. , Kaminka G. A.
Published: July 2018

Open distributed multi-agent systems are gaining interest in the academic community and in industry. In such open settings, agents are often coordinated using standardized agent conversation protocols. The representation of such protocols (for analysis, validation, monitoring, etc) is an important aspect of multi-agent applications. Recently, Petri nets have been shown to be an interesting approach to such representation, and radically different approaches using Petri nets have been proposed. However, their relative strengths and weaknesses have not been examined. Moreover, their scalability and suitability for different tasks have not been addressed. This paper addresses both these challenges. First, we analyze existing Petri net representations in terms of their scalability and appropriateness for overhearing, an important task in monitoring open multi-agent systems. Then, building on the insights gained, we introduce a novel representation using Colored Petri nets that explicitly represent legal joint conversation states and messages. This representation approach offers significant improvements in scalability and is particularly suitable for overhearing. Furthermore, we show that this new representation offers a comprehensive coverage of all conversation features of FIPA conversation standards. We also present a procedure for transforming AUML conversation protocol diagrams (a standard human-readable representation), to our Colored Petri net representation.
On Graphical Modeling of Preference and Importance
Authors: Brafman R. I. , Domshlak C. , Shimony S. E.
Published: July 2018

In recent years, CP-nets have emerged as a useful tool for supporting preference elicitation, reasoning, and representation. CP-nets capture and support reasoning with qualitative conditional preference statements, statements that are relatively natural for users to express. In this paper, we extend the CP-nets formalism to handle another class of very natural qualitative statements one often uses in expressing preferences in daily life - statements of relative importance of attributes. The resulting formalism, TCP-nets, maintains the spirit of CP-nets, in that it remains focused on using only simple and natural preference statements, uses the ceteris paribus semantics, and utilizes a graphical representation of this information to reason about its consistency and to perform, possibly constrained, optimization using it. The extra expressiveness it provides allows us to better model tradeoffs users would like to make, more faithfully representing their preferences.
A Continuation Method for Nash Equilibria in Structured Games
Authors: Blum B. , Shelton C. R. , Koller D.
Published: July 2018

Structured game representations have recently attracted interest as models for multi-agent artificial intelligence scenarios, with rational behavior most commonly characterized by Nash equilibria. This paper presents efficient, exact algorithms for computing Nash equilibria in structured game representations, including both graphical games and multi-agent influence diagrams (MAIDs). The algorithms are derived from a continuation method for normal-form and extensive-form games due to Govindan and Wilson; they follow a trajectory through a space of perturbed games and their equilibria, exploiting game structure through fast computation of the Jacobian of the payoff function. They are theoretically guaranteed to find at least one equilibrium of the game, and may find more. Our approach provides the first efficient algorithm for computing exact equilibria in graphical games with arbitrary topology, and the first algorithm to exploit fine-grained structural properties of MAIDs. Experimental results are presented demonstrating the effectiveness of the algorithms and comparing them to predecessors. The running time of the graphical game algorithm is similar to, and often better than, the running time of previous approximate algorithms. The algorithm for MAIDs can effectively solve games that are much larger than those solvable by previous methods.
The Power of Modeling---a Response to PDDL2.1
Authors: Bacchus F.
Published: July 2018

In this commentary I argue that although PDDL is a very useful standard for the planning competition, its design does not properly consider the issue of domain modeling. Hence, I would not advocate its use in specifying planning domains outside of the context of the planning competition. Rather, the field needs to explore different approaches and grapple more directly with the problem of effectively modeling and utilizing all of the diverse pieces of knowledge we typically have about planning domains.
PDDL 2.1: Representation vs. Computation
Authors: Geffner H. A.
Published: July 2018

I comment on the PDDL 2.1 language and its use in the planning competition, focusing on the choices made for accommodating time and concurrency. I also discuss some methodological issues that have to do with the move toward more expressive planning languages and the balance needed in planning research between semantics and computation.
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
Authors: Jia H. , Moore C. , Strain D.
Published: July 2018

To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is to choose a random truth assignment A, and then choose clauses randomly from among those satisfied by A. However, this method tends to produce easy problems, since the majority of literals point toward the "hidden'' assignment A. Last year, Achlioptas, Jia and Moore proposed a problem generator that cancels this effect by hiding both A and its complement. While the resulting formulas appear to be just as hard for DPLL algorithms as random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT in only polynomial time.

Here we propose a new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to q^t for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to "deceptively'' point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially hard both for DPLL algorithms and for incomplete algorithms such as WalkSAT.
Auctions with Severely Bounded Communication
Authors: Blumrosen L. , Nisan N. , Segal I.
Published: July 2018

We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove non-surprising properties of these kinds of auctions, e.g., that in optimal mechanisms bidders simply report the interval in which their valuation lies in, as well as some surprising properties, e.g., that asymmetric auctions are better than symmetric ones and that multi-round auctions reduce the communication complexity only by a linear factor.
Anytime Heuristic Search
Authors: Hansen E. A. , Zhou R.
Published: July 2018

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.
Junta Distributions and the Average-Case Complexity of Manipulating Elections
Authors: Procaccia A. D. , Rosenschein J. S.
Published: July 2018

Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation.
Indeed, we demonstrate that NP-hard manipulations may be tractable in the average case. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant.
Obtaining Reliable Feedback for Sanctioning Reputation Mechanisms
Authors: Jurca R. , Faltings B.
Published: July 2018

Reputation mechanisms offer an effective alternative to verification authorities for building trust in electronic markets with moral hazard. Future clients guide their business decisions by considering the feedback from past transactions; if truthfully exposed, cheating behavior is sanctioned and thus becomes irrational.

It therefore becomes important to ensure that rational clients have the right incentives to report honestly. As an alternative to side-payment schemes that explicitly reward truthful reports, we show that honesty can emerge as a rational behavior when clients have a repeated presence in the market. To this end we describe a mechanism that supports an equilibrium where truthful feedback is obtained. Then we characterize the set of pareto-optimal equilibria of the mechanism, and derive an upper bound on the percentage of false reports that can be recorded by the mechanism. An important role in the existence of this bound is played by the fact that rational clients can establish a reputation for reporting honestly.
Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language
Authors: Resnik P.
Published: July 2018

This article presents a measure of semantic similarity in an IS-A taxonomy based on the notion of shared information content. Experimental evaluation against a benchmark set of human similarity judgments demonstrates that the measure performs better than the traditional edge-counting approach. The article presents algorithms that take advantage of taxonomic similarity in resolving syntactic and semantic ambiguity, along with experimental results demonstrating their effectiveness.
Solving Highly Constrained Search Problems with Quantum Computers
Authors: Hogg T.
Published: July 2018

A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms.
Constructing Conditional Plans by a Theorem-Prover
Authors: Rintanen J.
Published: July 2018

The research on conditional planning rejects the assumptions that there is no uncertainty or incompleteness of knowledge with respect to the state and changes of the system the plans operate on. Without these assumptions the sequences of operations that achieve the goals depend on the initial state and the outcomes of nondeterministic changes in the system. This setting raises the questions of how to represent the plans and how to perform plan search. The answers are quite different from those in the simpler classical framework. In this paper, we approach conditional planning from a new viewpoint that is motivated by the use of satisfiability algorithms in classical planning. Translating conditional planning to formulae in the propositional logic is not feasible because of inherent computational limitations. Instead, we translate conditional planning to quantified Boolean formulae. We discuss three formalizations of conditional planning as quantified Boolean formulae, and present experimental results obtained with a theorem-prover.
Reasoning about Minimal Belief and Negation as Failure
Authors: Rosati R.
Published: July 2018

We investigate the problem of reasoning in the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries, and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF. In particular, we show that entailment in propositional MBNF lies at the third level of the polynomial hierarchy, hence it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore's autoepistemic logic.
Backbone Fragility and the Local Search Cost Peak
Authors: Singer J. , Gent I. P. , Smaill A.
Published: July 2018

The local search algorithm WSat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called `satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of WSat on high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in WSat's search. This pattern leads us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for local search are those with very large backbones which are also backbone-fragile. We suggest that the decay in cost beyond the satisfiability threshold is due to increasing backbone robustness (the opposite of backbone fragility). Our hypothesis makes three correct predictions. First, that the backbone robustness of an instance is negatively correlated with the local search cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSat. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone. In understanding the pathologies of local search methods, we hope to contribute to the development of new and better techniques.
Mean Field Methods for a Special Class of Belief Networks
Authors: Bhattacharyya C. , Keerthi S. S.
Published: July 2018

The chief aim of this paper is to propose mean-field approximations for a broad class of Belief networks, of which sigmoid and noisy-or networks can be seen as special cases. The approximations are based on a powerful mean-field theory suggested by Plefka. We show that Saul, Jaakkola and Jordan' s approach is the first order approximation in Plefka's approach, via a variational derivation. The application of Plefka's theory to belief networks is not computationally tractable. To tackle this problem we propose new approximations based on Taylor series. Small scale experiments show that the proposed schemes are attractive.
Grounding the Lexical Semantics of Verbs in Visual Perception using Force Dynamics and Event Logic
Authors: Siskind J. M.
Published: July 2018

This paper presents an implemented system for recognizing the occurrence of events described by simple spatial-motion verbs in short image sequences. The semantics of these verbs is specified with event-logic expressions that describe changes in the state of force-dynamic relations between the participants of the event. An efficient finite representation is introduced for the infinite sets of intervals that occur when describing liquid and semi-liquid events. Additionally, an efficient procedure using this representation is presented for inferring occurrences of compound events, described with event-logic expressions, from occurrences of primitive events. Using force dynamics and event logic to specify the lexical semantics of events allows the system to be more robust than prior systems based on motion profile.
Infinite-Horizon Policy-Gradient Estimation
Authors: Baxter J. , Bartlett P. L.
Published: July 2018

Gradient-based approaches to direct policy search in reinforcement learning have received much recent attention as a means to solve problems of partial observability and to avoid some of the problems associated with policy degradation in value-function methods. In this paper we introduce GPOMDP, a simulation-based algorithm for generating a biased estimate of the gradient of the average reward in Partially Observable Markov Decision Processes POMDPs controlled by parameterized stochastic policies. A similar algorithm was proposed by (Kimura et al. 1995). The algorithm's chief advantages are that it requires storage of only twice the number of policy parameters, uses one free beta (which has a natural interpretation in terms of bias-variance trade-off), and requires no knowledge of the underlying state. We prove convergence of GPOMDP, and show how the correct choice of the parameter beta is related to the mixing time of the controlled POMDP. We briefly describe extensions of GPOMDP to controlled Markov chains, continuous state, observation and control spaces, multiple-agents, higher-order derivatives, and a version for training stochastic policies with internal states. In a companion paper (Baxter et al., this volume) we show how the gradient estimates generated by GPOMDP can be used in both a traditional stochastic gradient algorithm and a conjugate-gradient procedure to find local optima of the average reward.
Learning Geometrically-Constrained Hidden Markov Models for Robot Navigation: Bridging the Topological-Geometrical Gap
Authors: Shatkay H. , Kaelbling L. P.
Published: July 2018

Hidden Markov models (HMMs) and partially observable Markov decision processes (POMDPs) provide useful tools for modeling dynamical systems. They are particularly useful for representing the topology of environments such as road networks and office buildings, which are typical for robot navigation and planning. The work presented here describes a formal framework for incorporating readily available odometric information and geometrical constraints into both the models and the algorithm that learns them. By taking advantage of such information, learning HMMs/POMDPs can be made to generate better solutions and require fewer iterations, while being robust in the face of data reduction. Experimental results, obtained from both simulated and real robot data, demonstrate the effectiveness of the approach.
Accelerating Reinforcement Learning through Implicit Imitation
Authors: Price B. , Boutilier C.
Published: July 2018

Imitation can be viewed as a means of enhancing learning in multiagent environments. It augments an agent's ability to learn useful behaviors by making intelligent use of the knowledge implicit in behaviors demonstrated by cooperative teachers or other more experienced agents. We propose and study a formal model of implicit imitation that can accelerate reinforcement learning dramatically in certain cases. Roughly, by observing a mentor, a reinforcement-learning agent can extract information about its own capabilities in, and the relative value of, unvisited parts of the state space. We study two specific instantiations of this model, one in which the learning agent and the mentor have identical abilities, and one designed to deal with agents and mentors with different action sets. We illustrate the benefits of implicit imitation by integrating it with prioritized sweeping, and demonstrating improved performance and convergence through observation of single and multiple mentors. Though we make some stringent assumptions regarding observability and possible interactions, we briefly comment on extensions of the model that relax these restricitions.
Parameter Learning of Logic Programs for Symbolic-Statistical Modeling
Authors: Sato T. , Kameya Y.
Published: July 2018

We propose a logical/mathematical framework for statistical parameter learning of parameterized logic programs, i.e. definite clause programs containing probabilistic facts with a parameterized distribution. It extends the traditional least Herbrand model semantics in logic programming to distribution semantics, possible world semantics with a probability distribution which is unconditionally applicable to arbitrary logic programs including ones for HMMs, PCFGs and Bayesian networks. We also propose a new EM algorithm, the graphical EM algorithm, that runs for a class of parameterized logic programs representing sequential decision processes where each decision is exclusive and independent. It runs on a new data structure called support graphs describing the logical relationship between observations and their explanations, and learns parameters by computing inside and outside probability generalized for logic programs. The complexity analysis shows that when combined with OLDT search for all explanations for observations, the graphical EM algorithm, despite its generality, has the same time complexity as existing EM algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside algorithm for PCFGs, and the one for singly connected Bayesian networks that have been developed independently in each research field. Learning experiments with PCFGs using two corpora of moderate size indicate that the graphical EM algorithm can significantly outperform the Inside-Outside algorithm.
A Critical Assessment of Benchmark Comparison in Planning
Authors: Howe A. E. , Dahlman E.
Published: July 2018

Recent trends in planning research have led to empirical comparison becoming commonplace. The field has started to settle into a methodology for such comparisons, which for obvious practical reasons requires running a subset of planners on a subset of problems. In this paper, we characterize the methodology and examine eight implicit assumptions about the problems, planners and metrics used in many of these comparisons. The problem assumptions are: PR1) the performance of a general purpose planner should not be penalized/biased if executed on a sampling of problems and domains, PR2) minor syntactic differences in representation do not affect performance, and PR3) problems should be solvable by STRIPS capable planners unless they require ADL. The planner assumptions are: PL1) the latest version of a planner is the best one to use, PL2) default parameter settings approximate good performance, and PL3) time cut-offs do not unduly bias outcome. The metrics assumptions are: M1) performance degrades similarly for each planner when run on degraded runtime environments (e.g., machine platform) and M2) the number of plan steps distinguishes performance. We find that most of these assumptions are not supported empirically; in particular, that planners are affected differently by these assumptions. We conclude with a call to the community to devote research resources to improving the state of the practice and especially to enhancing the available benchmark problems.
Inducing Interpretable Voting Classifiers without Trading Accuracy for Simplicity: Theoretical Results, Approximation Algorithms
Authors: Nock R.
Published: July 2018

Recent advances in the study of voting classification algorithms have brought empirical and theoretical results clearly showing the discrimination power of ensemble classifiers. It has been previously argued that the search of this classification power in the design of the algorithms has marginalized the need to obtain interpretable classifiers. Therefore, the question of whether one might have to dispense with interpretability in order to keep classification strength is being raised in a growing number of machine learning or data mining papers. The purpose of this paper is to study both theoretically and empirically the problem. First, we provide numerous results giving insight into the hardness of the simplicity-accuracy tradeoff for voting classifiers. Then we provide an efficient ``top-down and prune'' induction heuristic, WIDC, mainly derived from recent results on the weak learning and boosting frameworks. It is to our knowledge the first attempt to build a voting classifier as a base formula using the weak learning framework (the one which was previously highly successful for decision tree induction), and not the strong learning framework (as usual for such classifiers with boosting-like approaches). While it uses a well-known induction scheme previously successful in other classes of concept representations, thus making it easy to implement and compare, WIDC also relies on recent or new results we give about particular cases of boosting known as partition boosting and ranking loss boosting. Experimental results on thirty-one domains, most of which readily available, tend to display the ability of WIDC to produce small, accurate, and interpretable decision committees.
Latour, Foucault und das Postfaktische: Zur Rolle und Funktion von Kritik im Zeitalter der "Wahrheitskrise"
Authors: Flatscher Matthias , Seitz Sergej
Published: July 2018

This paper scrutinizes Bruno Latour's critique of contemporary critical theory. According to Latour, poststructuralist conceptions of critical inquiry are increasingly behind the times: in our "post-factual" era, attempts to expose facts as results of power-laden processes of social construction play in the hands of obscurantist anti-scientific positions. Arguing at the same time against reductionist notions of objectivity, Latour proposes a new form of critical realism. While Latour plausibly advocates the necessity of widening our epistemological paradigm, we aim to show that his critique of poststructuralism is unjust and hyperbolic. Moreover, his own conception misses out on explicating the relationship between epistemology, power, and subjectivity. Therefore, we argue that a Foucauldian form of critique, as it allows to account for this relationship, is all but outdated. Rather, it remains a necessary critical device in the context of the present truth-crisis.
STS and the Importance of Being a Collective: Gill Haddow Talks with Barry Barnes
Authors: Haddow Gill , Barnes Barry
Published: July 2018

Professor Barry Barnes was a key, founding member of the early Science Studies Unit (SSU) at the University of Edinburgh.  In this interview with Gill Haddow he reflects on what is was like to be part of this fertile period of scholarly enterprise with David Bloor and others and describes some of the key influences that effected his thinking such as Thomas Kuhn.  The eighties were a time of political unrest and SSU, was not outwardly political in vision but was not immune.  The Science Wars also had detrimental effects for some.  The origin of the concept of “boot-strapped induction,” or feedback loops was also being brought into existence with the idea that scientific knowledge was both self-referential and self-validating.  At the center lay the most basic and enduring tenets of Barnes’ thought and that was the collective and how people could never truly be independent. A reflection by Gill Haddow follows the interview.
“These Were Not Boring Meetings”: Miguel García-Sancho Talks with Karin Knorr Cetina
Authors: Garcia-Sancho Miguel , Knorr Cetina Karin
Published: July 2018

In this interview, Karin Knorr Cetina evokes the first Annual Meeting of the Society for Social Studies of Science at Cornell University in 1976 as a foundational moment for science and technology studies (STS). This conference consolidated a new approach to the study of science based on the anthropological observation of scientists at work in the laboratory. Knorr Cetina argues that, despite geographically cementing in the United States, this approach originated mainly through the work of European scholars. The years that followed the Cornell meeting were marked by intense debates between the defenders of this anthropological approach and other scholars more focused on ideas than on scientific practice. Knorr Cetina describes these debates as “bloodbaths” and recalls having first coined the term “constructivist” as applied to science studies in 1977. For Knorr Cetina, STS is now shifting its attention from the production to the consumption of technoscientific knowledge. Her current interest in the financial markets and other forms of screen technologies is an example of this transition. She argues that STS needs to overcome its current fragmentation and emphasis in isolated case studies. The establishment of basic research centers with the financial resources to develop collective and long-term programs would help scholars to expand their horizons. In his following reflection, Miguel García-Sancho explores the connections between STS and travel in both a sense of intellectual shift and a more mundane meaning of physical movement.
methylated DNA immunoprecipitation combined with microarray v1
Authors: Wang Juan
Published: July 2018

Background: Aberrant DNA methylation occurs frequently in cancer. The aim of this study was to identify novel methylation markers in lung cancer in Xuanwei, China, through integrated genome-wide DNA methylation and gene expression studies. Methods: Differentially methylated regions (DMRs) and differentially expressed genes (DEGs) were detected on 10 paired lung cancer tissues and noncancerous lung tissues by methylated DNA immunoprecipitation combined with microarray (MeDIP-chip) and gene expression microarray analyses, respectively. Integrated analysis of DMRs and DEGs was performed to screen out candidate methylation-related genes. Both methylation and expression changes of the candidate genes were further validated and analyzed. Results: Compared with normal lung tissues, lung cancer tissues expressed a total of 6,899 DMRs, including 5,788 hypermethylated regions and 1,111 hypomethylated regions. Integrated analysis of DMRs and DEGs identified 45 tumor-specific candidate genes: 38 genes whose DMRs were hypermethylated and expression was downregulated, and 7 genes whose DMRs were hypomethylated and expression was upregulated. The methylation and expression validation results identified 4 candidate genes (STXBP6, BCL6B, FZD10, and HSPB6) that were significantly hypermethylated and downregulated in most of the tumor tissues compared with the noncancerous lung tissues. Conclusions: This integrated analysis of genome-wide DNA methylation and gene expression in lung cancer in Xuanwei revealed several genes regulated by promoter methylation that have not been described in lung cancer before. These results provide new insight into the carcinogenesis of lung cancer in Xuanwei and represent promising new diagnostic and therapeutic targets.
Analysis of whole genome sequences from spotted owl populations in California v3
Authors: R Hanna Zachary , P. Dumbacher John , C.K. Bowie Rauri , D. Wall Jeffrey
Published: July 2018

Supplementary details of materials and methods for article entitled 'Whole-genome sequences suggest long term declines of spotted owl (Strix occidentalis) (Aves: Strigiformes: Strigidae) populations in California'.
In vitro digestion of DNA with Cas9 Nuclease, S. pyogenes (M0386) v1
Authors: Kaur Binnypreet
Published: July 2018

Cas9 Nuclease,S. pyogenes, (Cas9) is a double-stranded DNA endonuclease that is guided to its target by sequence complementarity of a small RNA loaded into the protein. This protocol describes how to digest double-stranded DNAin vitrousing Cas9 and a single guide RNA (sgRNA).
La crisis económica de 2008. algunas reflexiones teóricas a partir de j.m. keynes y h. p. minsky
Authors: VENEGAS CALLE STELLA DEL PILAR
Published: July 2018

From the Keynesian theory and the developments Poskeynesianos de Hyman Minsky, the present article shows some of the principal theoretical elements of reference that they allow to realize an analytical approximation in the study of the economic crisis that became visible about August, 2007. The work begins with an explanation of the phenomena that characterizes the economic crisis of ends of 2007, known also as crisis of the mortgages l suboccupies first place. In the second and third part, the principal topics approached by J. M are exposed. Keynes and H.P. Minsky, respectively, which constitute fundamental aspects in the understanding of the mentioned crisis. Finally, in the last section, the conclusions of the work are elaborated.
La relación entre las agencias de comunicación en mercadeo y sus clientes: visión de las agencias
Authors: GÓMEZ RAMÍREZ CLAUDIA MARGARITA
Published: July 2018

In this study it is pretended to identify the current behavior of the factors for the success and the threatening that affect on the continuity of an account, and therefore of the business, from the perception of the agencies of advertising, means, events and public relations. Points as the expectations, the performance, the vulnerability of the relation and the profitability of the clients were examined. To understand better the factors that affect this relation, will allow to the businessmen of the industry to support or to improve the profitability of his business, to obtain more harmonious relations in a long term basis, what will turn into a considerable advantage to face the uncertain futures.
Estimación econométrica de la oferta laboral de los hogares nucleares en colombia
Authors: CUSBA GARCÍA JAIME ENRIQUE , RAMÍREZ PINZÓN IVÁN ANDRÉS , MAYORGA MOGOLLÓN WILSON
Published: July 2018

The theoretical recent developments show that the decisions to the interior of the homes arise from the interaction between the individual preferences of every member with regard to the consumption of goods, but also they depend on the use of his time, of the budgetary restriction of the home and of the process of negotiation that takes place to the interior of this one. Since proved from these decisions it is possible to determine the expense added of the home in different goods and services, the labor participation and the distribution of the income of his members. For this reason, from this investigation it is intended to seek to evaluate empirically, by using of the collective models approach, the process of decision of the homes in Colombia, with particular emphasis in the decision of labor offer. The results show that the spouse who has major income is the one who determines his distribution to the interior of the home and that the woman obtains great part of the not labor income of the home. These facts affect in a significant way in the labor offer of all the members of the home.
El método de la economía política
Authors: RAVIER ADRIÁN
Published: July 2018

This is the fi rst review that I will write about two books of the same author. I don’t pretend to summarize his work of more than three decades and represented in many publications, but to invite the readers and mainly Economists to seriously consider studying the political economics research program made by a philosopher inspired by diverse arguments of many colleagues and that offers a unique and innovative systematic approach. Professor Zanotti on the preface: “The general theory of knowledge is previous to the philosophy of science, this one previous to the philosophy of social science and this one, previous to the methodology of any social science in particular” (Zanotti, 2004, p. 12). I think that we, the economists, have an enormously biased formation when introducing our studies into a “general theory of knowledge”, which makes us come closer to philosophy in order to understand what we do and the way we operate. So, there’s nothing better than approximating a philosopher, who has concentrated his work in how to organize a political economics research program. We summarize his proposal here and understand that it should compete with others designed by other Economists. The book has five chapters. In the first chapter, the author takes the contributions of two epistemologists: Popper and Lakatos. In the second chapter, he adds three more: Mises, Hayek and Machlup. The author clarifies though, that he will not describe each thinker’s position as a whole, but only what is interesting for his Organization. The third chapter, considering the previously mentioned contributions, is the systematical organization of his research program. We consider that it is convenient to reproduce so far, the review’s structure of the first three chapters of the book. The fourth chapter presents systematically, the three methods that in the author’s opinion are harmonically combined in the methodology of social science. These last chapters hold the biggest philosophical contents. Strictly due to space restrictions, we will take the essential components and insert them in the structure of the first three chapters.
Riqueza, pobreza e impuestos como factores de desarrollo
Authors: AVELLANEDA BAUTISTA CAMPO ALCIDES
Published: July 2018

This article deals with the topics of richness, poverty and taxes and dialectic factors in sustainable development. This research pretends to propose a formula that allows Colombian territorial entities to obtain resources in order to attend programs oriented to repair the human capital identified as poverty. Nevertheless, this advance will conclude in the interdependence between richness, poverty and taxes as a development factor. This advance is one of the final products of a project called: “Tax for the Fund of the Poor”, developed in five stages that started in 2005 and is expected to end in 2011.
Un ejemplo del románico inicial en Álava: el ábside con modillones de ornamentación bifacial en Nuestra Señora de Elizmendi, Kontrasta
Authors: López de Ocáriz Alzola José Javier
Published: July 2018

El objeto de estudio es una ermita situada en el valle de Arana, al oriente de Álava, junto a Navarra. En su entorno y muros predomina el contexto funerario, con lápidas romanas y tumbas altomedievales. Su interés arquitectónico y escultórico radica en el ábside de robustos sillares, donde se adivina una aspillera cegada aún inédita, y se exhiben diez modillones, originales por su perfil abombado y sus relieves bifaciales. Junto a tallas de diseño geométrico, similar al de las estelas discoideas, se ve un ingenuo Crucificado y el prótomo voluminoso de un lobo. La iglesia formó parte de un monasteriolo donado en 1203 por doña Sancia Pedriz de Uztuniga al Monasterio de Irache, cuando contaría un siglo aproximado desde la construcción del ábside estudiado. Puede valorarse como una primicia entre los más antiguos testimonios del románico de Álava.