Authors:Shufeng Kong; Sanjiang Li; Yongming Li; Zhiguo Long Pages: 241 - 271 Abstract: The study of tractable subclasses of constraint satisfaction problems is a central topic in constraint solving. Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. However, it is NP-complete to decide whether a tree convex constraint network has solutions. This paper studies and compares three subclasses of tree convex constraints, which are called chain-, path-, and tree-preserving constraints respectively. The class of tree-preserving constraints strictly contains the subclasses of path-preserving and arc-consistent chain-preserving constraints. We prove that, when enforcing strong path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of consistent tree-preserving networks after enforcing strong path-consistency, and also guarantees the applicability of the partial path-consistency algorithms to tree-preserving constraint networks, which is usually much more efficient than the path-consistency algorithms for large sparse constraint networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem. PubDate: 2017-12-01 DOI: 10.1007/s10472-017-9552-z Issue No:Vol. 81, No. 3-4 (2017)

Authors:Manuele Leonelli; Eva Riccomagno; Jim Q. Smith Pages: 273 - 313 Abstract: Influence diagrams provide a compact graphical representation of decision problems. Several algorithms for the quick computation of their associated expected utilities are available in the literature. However, often they rely on a full quantification of both probabilistic uncertainties and utility values. For problems where all random variables and decision spaces are finite and discrete, here we develop a symbolic way to calculate the expected utilities of influence diagrams that does not require a full numerical representation. Within this approach expected utilities correspond to families of polynomials. After characterizing their polynomial structure, we develop an efficient symbolic algorithm for the propagation of expected utilities through the diagram and provide an implementation of this algorithm using a computer algebra system. We then characterize many of the standard manipulations of influence diagrams as transformations of polynomials. We also generalize the decision analytic framework of these diagrams by defining asymmetries as operations over the expected utility polynomials. PubDate: 2017-12-01 DOI: 10.1007/s10472-017-9553-y Issue No:Vol. 81, No. 3-4 (2017)

Authors:C. E. Larson; N. Van Cleemput Pages: 315 - 327 Abstract: Discovery in mathematics is a prototypical intelligent behavior, and an early and continuing goal of artificial intelligence research. We present a heuristic for producing mathematical conjectures of a certain typical form and demonstrate its utility. Our program conjectures relations that hold between properties of objects (property-relation conjectures). These objects can be of a wide variety of types. The statements are true for all objects known to the program, and are the simplest statements which are true of all these objects. The examples here include new conjectures for the hamiltonicity of a graph, a well-studied property of graphs. While our motivation and experiments have been to produce mathematical conjectures—and to contribute to mathematical research—other kinds of interesting property-relation conjectures can be imagined, and this research may be more generally applicable to the development of intelligent machinery. PubDate: 2017-12-01 DOI: 10.1007/s10472-017-9559-5 Issue No:Vol. 81, No. 3-4 (2017)

Authors:Vladimir Vapnik; Rauf Izmailov Pages: 3 - 19 Abstract: The paper considers general machine learning models, where knowledge transfer is positioned as the main method to improve their convergence properties. Previous research was focused on mechanisms of knowledge transfer in the context of SVM framework; the paper shows that this mechanism is applicable to neural network framework as well. The paper describes several general approaches for knowledge transfer in both SVM and ANN frameworks and illustrates algorithmic implementations and performance of one of these approaches for several synthetic examples. PubDate: 2017-10-01 DOI: 10.1007/s10472-017-9538-x Issue No:Vol. 81, No. 1-2 (2017)

Authors:Vladimir Vovk; Dusko Pavlovic Pages: 47 - 70 Abstract: We construct universal prediction systems in the spirit of Popper’s falsifiability and Kolmogorov complexity and randomness. These prediction systems do not depend on any statistical assumptions (but under the IID assumption they dominate, to within the usual accuracy, conformal prediction). Our constructions give rise to a theory of algorithmic complexity and randomness of time containing analogues of several notions and results of the classical theory of Kolmogorov complexity and randomness. PubDate: 2017-10-01 DOI: 10.1007/s10472-017-9547-9 Issue No:Vol. 81, No. 1-2 (2017)

Authors:Anthony Bellotti Pages: 71 - 84 Abstract: Accurate property valuation is important for property purchasers, investors and for mortgage-providers to assess credit risk in the mortgage market. Automated valuation models (AVM) are being developed to provide cheap, objective valuations that allow dynamic updating of property values over the term of a mortgage. A useful feature of automated valuations is to provide a region of plausible price estimates for each individual property, rather than just a single point estimate. This would allow buyers and sellers to understand uncertainty on pricing individual properties and mortgage providers to include conservatism in their credit risk assessment. In this study, Conformal Predictors (CP) are used to provide such region predictions, whilst strictly controlling for predictive accuracy. We show how an AVM can be constructed using a CP, based on an underlying k-nearest neighbours approach. Time trend in property prices is dealt with by assuming a systematic effect over time and adjusting prices in the training data accordingly. The AVM is tested on a large data set of London property prices. Region predictions are shown to be reliable and the efficiency, ie region width, of property price predictions is investigated. In particular, a regression model is constructed to model the uncertainty in price prediction linked to property characteristics. PubDate: 2017-10-01 DOI: 10.1007/s10472-016-9534-6 Issue No:Vol. 81, No. 1-2 (2017)

Authors:Henrik Boström; Henrik Linusson; Tuve Löfström; Ulf Johansson Pages: 125 - 144 Abstract: The conformal prediction framework allows for specifying the probability of making incorrect predictions by a user-provided confidence level. In addition to a learning algorithm, the framework requires a real-valued function, called nonconformity measure, to be specified. The nonconformity measure does not affect the error rate, but the resulting efficiency, i.e., the size of output prediction regions, may vary substantially. A recent large-scale empirical evaluation of conformal regression approaches showed that using random forests as the learning algorithm together with a nonconformity measure based on out-of-bag errors normalized using a nearest-neighbor-based difficulty estimate, resulted in state-of-the-art performance with respect to efficiency. However, the nearest-neighbor procedure incurs a significant computational cost. In this study, a more straightforward nonconformity measure is investigated, where the difficulty estimate employed for normalization is based on the variance of the predictions made by the trees in a forest. A large-scale empirical evaluation is presented, showing that both the nearest-neighbor-based and the variance-based measures significantly outperform a standard (non-normalized) nonconformity measure, while no significant difference in efficiency between the two normalized approaches is observed. The evaluation moreover shows that the computational cost of the variance-based measure is several orders of magnitude lower than when employing the nearest-neighbor-based nonconformity measure. The use of out-of-bag instances for calibration does, however, result in nonconformity scores that are distributed differently from those obtained from test instances, questioning the validity of the approach. An adjustment of the variance-based measure is presented, which is shown to be valid and also to have a significant positive effect on the efficiency. For conformal regression forests, the variance-based nonconformity measure is hence a computationally efficient and theoretically well-founded alternative to the nearest-neighbor procedure. PubDate: 2017-10-01 DOI: 10.1007/s10472-017-9539-9 Issue No:Vol. 81, No. 1-2 (2017)

Authors:Ernst Ahlberg; Oscar Hammar; Claus Bendtsen; Lars Carlsson Pages: 145 - 154 Abstract: We present two applications of conformal prediction relevant to drug discovery. The first application is around interpretation of predictions and the second one around the selection of compounds to progress in a drug discovery project setting. PubDate: 2017-10-01 DOI: 10.1007/s10472-017-9550-1 Issue No:Vol. 81, No. 1-2 (2017)

Authors:Claus Bendtsen; Andrea Degasperi; Ernst Ahlberg; Lars Carlsson Pages: 155 - 166 Abstract: The high cost for new medicines is hindering their development and machine learning is therefore being used to avoid carrying out physical experiments. Here, we present a comparison between three different machine learning approaches in a classification setting where learning and prediction follow a teaching schedule to mimic the drug discovery process. The approaches are standard SVM classification, SVM based multi-kernel classification and SVM classification based on learning using privileged information. Our two main conclusions are derived using experimental in-vitro data and compound structure descriptors. The in-vitro data is assumed to i) be completely absent in the standard SVM setting, ii) be available at all times when applying multi-kernel learning, or iii) be available as privileged information during training only. The structure descriptors are always available. One conclusion is that multi-kernel learning has higher odds than standard SVM in producing higher accuracy. The second is that learning using privileged information does not have higher odds than the standard SVM, although it may improve accuracy when the training sets are small. PubDate: 2017-10-01 DOI: 10.1007/s10472-017-9541-2 Issue No:Vol. 81, No. 1-2 (2017)

Authors:Evgeny Burnaev; Ivan Panin; Bruno Sudret Pages: 187 - 207 Abstract: Global sensitivity analysis aims at quantifying respective effects of input random variables (or combinations thereof) onto variance of a physical or mathematical model response. Among the abundant literature on sensitivity measures, Sobol indices have received much attention since they provide accurate information for most of models. We consider a problem of experimental design points selection for Sobol’ indices estimation. Based on the concept of D-optimality, we propose a method for constructing an adaptive design of experiments, effective for calculation of Sobol’ indices based on Polynomial Chaos Expansions. We provide a set of applications that demonstrate the efficiency of the proposed approach. PubDate: 2017-10-01 DOI: 10.1007/s10472-017-9542-1 Issue No:Vol. 81, No. 1-2 (2017)

Abstract: Answer Set Programming has become an increasingly popular formalism for declarative problem solving. Among the huge body of theoretical results, investigations of different equivalence notions between logic programs play a fundamental role for understanding modularity and optimization. While strong equivalence between two programs holds if they can be faithfully replaced by each other in any context (facts and rules), uniform equivalence amounts to equivalent behavior of programs under any set of facts. Both notions (as well as several variants thereof) have been extensively studied. However, the somewhat reverse notion of equivalence which holds if two programs are equivalent under the addition of any set of proper rules (i.e., all rules except facts) has not been investigated yet. In this paper, we close this gap and give a thorough study of this notion, which we call rule equivalence , and its parameterized version where we allow facts over a given restricted alphabet to appear in the context. This notion of equivalence is thus a relationship between two programs whose input is (partially) fixed but where additional proper rules might still be added. Such a notion might be helpful in debugging of programs. We give full characterization results and a complexity analysis for the propositional case of rule equivalence and its relativized versions. Moreover, we address the problem of program simplification under rule equivalence. Finally, we show that rule equivalence is decidable in the non-ground case. PubDate: 2017-11-10 DOI: 10.1007/s10472-017-9567-5

Authors:Wafa Jguirim; Wady Naanaa; Martin C. Cooper Abstract: Finding a solution to a constraint satisfaction problem (CSP) is known to be an NP-hard task. Considerable effort has been spent on identifying tractable classes of CSP, in other words, classes of constraint satisfaction problems for which there are polynomial time recognition and resolution algorithms. In this article, we present a relational tractable class of binary CSP. Our key contribution is a new ternary operation that we name mjx. We first characterize mjx-closed relations which leads to an optimal algorithm to recognize such relations. To reduce space and time complexity, we define a new storage technique for these relations which reduces the complexity of establishing a form of strong directional path consistency, the consistency level that solves all instances of the proposed class (and, indeed, of all relational classes closed under a majority polymorphism). PubDate: 2017-10-26 DOI: 10.1007/s10472-017-9566-6

Authors:Cynthia Maushagen; Jörg Rothe Abstract: Control by partition refers to situations where an election chair seeks to influence the outcome of an election by partitioning either the candidates or the voters into two groups, thus creating two first-round subelections that determine who will take part in a final round. The model of partition-of-voters control attacks is remotely related to “gerrymandering” (maliciously resizing election districts). While the complexity of control by partition has been studied thoroughly for many voting systems, there are no such results known for the important veto voting system. We settle the complexity of control by partition for veto in a broad variety of models. In addition, by giving a counterexample we observe that a reduction from the literature (Chen et al. 2015) showing the parameterized complexity of control by adding candidates to plurality elections, parameterized by the number of voters, is technically flawed, and we show how this reduction can be adapted to make it correct. PubDate: 2017-10-26 DOI: 10.1007/s10472-017-9565-7

Authors:Olivier Caelen Abstract: We propose a way to infer distributions of any performance indicator computed from the confusion matrix. This allows us to evaluate the variability of an indicator and to assess the importance of an observed difference between two performance indicators. We will assume that the values in a confusion matrix are observations coming from a multinomial distribution. Our method is based on a Bayesian approach in which the unknown parameters of the multinomial probability function themselves are assumed to be generated from a random vector. We will show that these unknown parameters follow a Dirichlet distribution. Thanks to the Bayesian approach, we also benefit from an elegant way of injecting prior knowledge into the distributions. Experiments are done on real and synthetic data sets and assess our method’s ability to construct accurate distributions. PubDate: 2017-09-11 DOI: 10.1007/s10472-017-9564-8

Authors:Hiromi Narimatsu; Hiroyuki Kasai Abstract: Sequential data modeling and analysis have become indispensable tools for analyzing sequential data, such as time-series data, because larger amounts of sensed event data have become available. These methods capture the sequential structure of data of interest, such as input-output relations and correlation among datasets. However, because most studies in this area are specialized or limited to their respective applications, rigorous requirement analysis of such models has not been undertaken from a general perspective. Therefore, we particularly examine the structure of sequential data, and extract the necessity of “state duration” and “state interval” of events for efficient and rich representation of sequential data. Specifically addressing the hidden semi-Markov model (HSMM) that represents such state duration inside a model, we attempt to add representational capability of a state interval of events onto HSMM. To this end, we propose two extended models: an interval state hidden semi-Markov model (IS-HSMM) to express the length of a state interval with a special state node designated as “interval state node”; and an interval length probability hidden semi-Markov model (ILP-HSMM) which represents the length of the state interval with a new probabilistic parameter “interval length probability.” Exhaustive simulations have revealed superior performance of the proposed models in comparison with HSMM. These proposed models are the first reported extensions of HMM to support state interval representation as well as state duration representation. PubDate: 2017-08-31 DOI: 10.1007/s10472-017-9561-y

Authors:Ignacio Montes; Sebastien Destercke Abstract: Within imprecise probability theory, the extreme points of convex probability sets have an important practical role (to perform inference on graphical models, to compute expectation bounds, …). This is especially true for sets presenting specific features that make them easy to manipulate in applications. This easiness is the reason why extreme points of such models (probability intervals, possibility distributions, …) have been well studied. Yet, imprecise cumulative distributions (a.k.a. p-boxes) constitute an important exception, as the characterization of their extreme points remain to be studied. This is what we do in this paper, where we characterize the maximal number of extreme points of a p-box, give a family of p-boxes that attains this number and show an algorithm that allows to compute the extreme points of a given p-box. To achieve all this, we also provide what we think to be a new characterization of extreme points of a belief function. PubDate: 2017-08-11 DOI: 10.1007/s10472-017-9562-x

Authors:Pavel Surynek Abstract: This paper deals with solving cooperative path finding (CPF) problems in a makespan-optimal way. A feasible solution to the CPF problem lies in the moving of mobile agents where each agent has unique initial and goal positions. The abstraction adopted in CPF assumes that agents are discrete units that move over an undirected graph by traversing its edges. We focus specifically on makespan-optimal solutions to the CPF problem where the task is to generate solutions that are as short as possible in terms of the total number of time steps required for all agents to reach their goal positions. We demonstrate that reducing CPF to propositional satisfiability (SAT) represents a viable way to obtain makespan-optimal solutions. Several ways of encoding CPFs into propositional formulae are proposed and evaluated both theoretically and experimentally. Encodings based on the log and direct representations of decision variables are compared. The evaluation indicates that SAT-based solutions to CPF outperform the makespan-optimal versions of such search-based CPF solvers such as OD+ID, CBS, and ICTS in highly constrained scenarios (i.e., environments that are densely occupied by agents and where interactions among the agents are frequent). Moreover, the experiments clearly show that CPF encodings based on the direct representation of variables can be solved faster, although they are less space-efficient than log encodings. PubDate: 2017-08-02 DOI: 10.1007/s10472-017-9560-z

Authors:S. Zhou; E. N. Smirnov; G. Schoenmakers; R. Peeters Abstract: Instance transfer for classification aims at boosting generalization performance of classification models for a target domain by exploiting data from a relevant source domain. Most of the instance-transfer approaches assume that the source data is relevant to the target data for the complete set of features used to represent the data. This assumption fails if the target data and source data are relevant only for strict subsets of the input features which we call “partially input-feature relevant”. In this case these approaches may result in sub-optimal classification models or even in a negative transfer. This paper proposes a new decision-tree approach to instance transfer when the source data are partially input-feature relevant to the target data. The approach selects input features for tree nodes using univariate transfer of source instances. The instance transfer is guided by a conformal test for source relevance estimation. Experimental results on real-world data sets demonstrate that the new decision-tree approach is capable of outperforming existing instance-transfer approaches, especially, when the source data are partially input-feature relevant to the target data. PubDate: 2017-06-17 DOI: 10.1007/s10472-017-9554-x

Authors:Alexander Kuleshov; Alexander Bernstein Abstract: Consider unknown smooth function which maps high-dimensional inputs to multidimensional outputs and whose domain of definition is unknown low-dimensional input manifold embedded in an ambient high-dimensional input space. Given training dataset consisting of ‘input-output’ pairs, regression on input manifold problem is to estimate the unknown function and its Jacobian matrix, as well to estimate the input manifold. By transforming high-dimensional inputs in their low-dimensional features, initial regression problem is reduced to certain regression on feature space problem. The paper presents a new geometrically motivated method for solving both interrelated regression problems. PubDate: 2017-05-16 DOI: 10.1007/s10472-017-9551-0