Linear causal models known as structural equation models (SEMs) are widely used for data analysis in the social sciences, economics, and artificial intelligence, in which random variables are assumed to be continuous and normally distributed. This paper deals with one fundamental problem in the applications of SEMs -- parameter identification. The paper uses the graphical models approach and provides a procedure for solving the identification problem in a special class of SEMs.

Qualitative constraint calculi are representation formalisms that allow for efficient reasoning about spatial and temporal information. Many of the calculi discussed in the field of Qualitative Spatial and Temporal Reasoning can be defined as combinations of other, simpler and more compact formalisms. On the other hand, existing calculi can be combined to a new formalism in which one can represent, and reason about, different aspects of a domain at the same time. For example, Gerevini and Renz presented a loose combination of the region connection calculus RCC-8 and the point algebra: the resulting formalism integrates topological and qualitative size relations between spatially extended objects. In this paper we compare the approach by Gerevini and Renz to a method that generates a new qualitative calculus by exploiting the semantic interdependencies between the component calculi. We will compare these two methods and analyze some formal relationships between a combined calculus and its components. The paper is completed by an empirical case study in which the reasoning performance of the suggested methods is compared on random test instances.

Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of  finding an improved  solution. However,  for inputs of size n,  a naive brute-force search of the k-exchange neighborhood requires n (O(k)) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently.  Our algorithms run in time O(T(k)*n c ), where T is a function depending on k only and c is a constant independent of k.  We demonstrate the applicability of this  approach on different  problems like r-Center, Vertex Cover,  Odd Cycle Transversal, Max-Cut, and  Min-Bisection.  In particular, on planar graphs, all our algorithms searching for a k-local improvement run in time O(2 (O(k) ) * n (2) ), which is polynomial for k=O(log n). We also complement the algorithms with complexity results indicating that brute force search is unavoidable in more general classes of sparse graphs.

In the context of Dung's theory of abstract argumentation frameworks, the recently introduced resolution-based grounded semantics features the unique property of fully complying with a set of general requirements, only partially satisfied by previous literature proposals. This paper contributes to the investigation of resolution-based grounded semantics by analyzing its computational properties with reference to a standard set of decision problems for abstract argumentation semantics: (a) checking the property of being an extension for a set of arguments; (b) checking agreement with traditional grounded semantics; (c) checking the existence of a non-empty extension; (d) checking credulous acceptance of an argument; (e) checking skeptical acceptance of an argument. It is shown that problems (a)-(c) admit polynomial time decision processes, while (d) is NP-complete and (e) coNP-complete.

These existing algorithms discover projections policies in very high dimensional state spaces. of the training data under which nearby points are likely We propose a linear dimensionality reduction algorithm to have the same class label or similar regression targets. The that discovers predictive projections: projections algorithm described in this paper makes use of the same machinery in which accurate predictions of future states but attempts to find low-dimensional projections under can be made using simple nearest neighbor style which current state vectors accurately predict future states learning. The goal of this work is to extend the in the projected space. The intuition is that projections which reach of existing reinforcement learning algorithms capture the state dynamics in this way are likely to contain to domains where they would otherwise be inapplicable information that will be useful for control.

Many problems have a huge state space and no good heuristic to order moves so as to guide the search toward the best positions. Random games can be used to score positions and evaluate their interest. Random games can also be improved using random games to choose a move to try at each step of a game. Nested Monte-Carlo Search addresses the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. The algorithm is studied theoretically on simple abstract problems and applied successfully to three different games: Morpion Solitaire, SameGame and 16x16 Sudoku.

Recent results have shown the interest  of trees-of-BDDs as a suitable target language for propositional knowledge compilation from the practical side. In the present paper,  the concept of tree-of-BDDs is extended to additional classes of data structures C, thus leading to trees-of-C representations (ToC). We provide a number of generic results enabling one to determine the queries/transformations satisfied by ToC depending on those satisfied by C. We also present some results about the spatial efficiency of the ToC languages. Focusing on the ToB language (and other related languages), we address a number of issues that remained open in (Subbarayan et al 2007). We show that beyond co and va, the ToB fragment satisfies im and me but satisfies neither cd nor any query among ce, se unlesssf P = NP. Among other results, we prove that ToB is not comparable w.r.t. succinctness with any of cnf, dnf,  Dnnf unless the polynomial hierarchy collapses.This contributes to the explanation of  some empirical results reported in (Subbarayan et al 2007).

We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their "unlabeled-labeled" representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.

A general framework is proposed for integration of rules and external first order theories. It is based on the well-founded semantics of normal logic programs and inspired by ideas of Constraint Logic Programming (CLP) and constructive negation for logic programs. Hybrid rules are normal clauses extended with constraints in the bodies; constraints are certain formulae in the language of the external theory. A hybrid program is a pair of a set of hybrid rules and an external theory. Instances of the framework are obtained by specifying the class of external theories, and the class of constraints. An example instance is integration of (non-disjunctive) Datalog with ontologies formalized as description logics. The paper defines a declarative semantics of hybrid programs and a goal-driven formal operational semantics. The latter can be seen as a generalization of SLS-resolution. It provides a basis for hybrid implementations combining Prolog with constraint solvers. Soundness of the operational semantics is proven. Sufficient conditions for decidability of the declarative semantics, and for completeness of the operational semantics are given.

Variable selection for high-dimensional linear models has received a lot of attention lately, mostly in the context of l1-regularization. Part of the attraction is the variable selection effect: parsimonious models are obtained, which are very suitable for interpretation. In terms of predictive power, however, these regularized linear models are often slightly inferior to machine learning procedures like tree ensembles. Tree ensembles, on the other hand, lack usually a formal way of variable selection and are difficult to visualize. A Garrote-style convex penalty for trees ensembles, in particular Random Forests, is proposed. The penalty selects functional groups of nodes in the trees. These could be as simple as monotone functions of individual predictor variables. This yields a parsimonious function fit, which lends itself easily to visualization and interpretation. The predictive power is maintained at least at the same level as the original tree ensemble. A key feature of the method is that, once a tree ensemble is fitted, no further tuning parameter needs to be selected. The empirical performance is demonstrated on a wide array of datasets.