Authors:André Abramé; Djamal Habet; Donia Toumi Pages: 5 - 24 Abstract: Abstract Local search algorithms based on the Configuration Checking (CC) strategy have been shown to be efficient in solving satisfiable random k-SAT instances. The purpose of the CC strategy is to avoid the cycling problem, which corresponds to revisiting already flipped variables too soon. It is done by considering the neighborhood of the formula variables. In this paper, we propose to improve the CC strategy on the basis of an empirical study of a powerful algorithm using this strategy. The first improvement introduces a new and simple criterion, which refines the selection of the variables to flip for the 3-SAT instances. The second improvement is achieved by using the powerful local search algorithm Novelty with the adaptive noise setting. This algorithm enhances the efficiency of the intensification and diversification phases when solving k-SAT instances with k ≥ 4. We name the resulting local search algorithm Ncca+ and show its effectiveness when treating satisfiable random k-SAT instances issued from the SAT Challenge 2012. Ncca+ won the bronze medal of the random SAT track of the SAT Competition 2013. PubDate: 2017-03-01 DOI: 10.1007/s10472-016-9515-9 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Balasim Al-Saedi; Olivier Fourdrinoy; Éric Grégoire; Bertrand Mazure; Lakhdar Saïs Pages: 25 - 44 Abstract: Abstract This paper explores several polynomial fragments of SAT that are based on the unit propagation (UP) mechanism. As a first case study, one Tovey’s polynomial fragment of SAT is extended through the use of UP. Then, we answer an open question about connections between the so-called UP-Horn class (and other UP-based polynomial variants) and Dalal’s polynomial Quad class. Finally, we introduce an extended UP-based pre-processing procedure that allows us to prove that some series of benchmarks from the SAT competitions are polynomial ones. Moreover, our experimentations show that this pre-processing can speed-up the satisfiability check of other instances. PubDate: 2017-03-01 DOI: 10.1007/s10472-015-9452-z Issue No:Vol. 79, No. 1-3 (2017)

Authors:Salem Benferhat; Zied Bouraoui; Odile Papini; Eric Würbel Pages: 45 - 75 Abstract: Abstract In real world applications, information is often provided by multiple sources having different priority levels reflecting for instance their reliability. This paper investigates ”Prioritized Removed Sets Revision” (PRSR) for revising stratified DL-Lite knowledge bases when a new sure piece of information, called the input, is added. The strategy of revision is based on inconsistency minimization and consists in determining smallest subsets of assertions (prioritized removed sets) that should be dropped from the current stratified knowledge base in order to restore consistency and accept the input. We consider different forms of input: A membership assertion, a positive or a negative inclusion axiom. To characterize our revision approach, we first rephrase Hansson’s postulates for belief bases revision within a DL-Lite setting, we then give logical properties of PRSR operators. In some situations, the revision process leads to several possible revised knowledge bases where defining a selection function is required to keep results within DL-Lite fragment. The last part of the paper shows how to use the notion of hitting set in order to compute the PRSR outcome. We also study the complexity of PRSR operators, and show that, in some cases, the computational complexity of the result can be performed in polynomial time. PubDate: 2017-03-01 DOI: 10.1007/s10472-015-9494-2 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Natalia Flerova; Radu Marinescu; Rina Dechter Pages: 77 - 128 Abstract: Abstract Weighted heuristic search (best-first or depth-first) refers to search with a heuristic function multiplied by a constant w [31]. The paper shows, for the first time, that for optimization queries in graphical models the weighted heuristic best-first and weighted heuristic depth-first branch and bound search schemes are competitive energy-minimization anytime optimization algorithms. Weighted heuristic best-first schemes were investigated for path-finding tasks. However, their potential for graphical models was ignored, possibly because of their memory costs and because the alternative depth-first branch and bound seemed very appropriate for bounded depth. The weighted heuristic depth-first search has not been studied for graphical models. We report on a significant empirical evaluation, demonstrating the potential of both weighted heuristic best-first search and weighted heuristic depth-first branch and bound algorithms as approximation anytime schemes (that have sub-optimality bounds) and compare against one of the best depth-first branch and bound solvers to date. PubDate: 2017-03-01 DOI: 10.1007/s10472-015-9495-1 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Dan Gutfreund; Aryeh Kontorovich; Ran Levy; Michal Rosen-Zvi Pages: 129 - 144 Abstract: Abstract In the standard agnostic multiclass model, <instance, label > pairs are sampled independently from some underlying distribution. This distribution induces a conditional probability over the labels given an instance, and our goal in this paper is to learn this conditional distribution. Since even unconditional densities are quite challenging to learn, we give our learner access to <instance, conditional distribution > pairs. Assuming a base learner oracle in this model, we might seek a boosting algorithm for constructing a strong learner. Unfortunately, without further assumptions, this is provably impossible. However, we give a new boosting algorithm that succeeds in the following sense: given a base learner guaranteed to achieve some average accuracy (i.e., risk), we efficiently construct a learner that achieves the same level of accuracy with arbitrarily high probability. We give generalization guarantees of several different kinds, including distribution-free accuracy and risk bounds. None of our estimates depend on the number of boosting rounds and some of them admit dimension-free formulations. PubDate: 2017-03-01 DOI: 10.1007/s10472-015-9465-7 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Utz-Uwe Haus; Carla Michini Pages: 145 - 162 Abstract: Abstract It is well known that (reduced, ordered) binary decision diagrams (BDDs) can sometimes be compact representations of the full solution set of Boolean optimization problems. Recently they have been suggested to be useful as discrete relaxations in integer and constraint programming (Hoda et al. 2010). We show that for every independence system there exists a top-down (i.e., single-pass) construction rule for the BDD. Furthermore, for packing and covering problems on n variables whose bandwidth is bounded by \(\mathcal {O}(\log n)\) the maximum width of the BDD is bounded by \(\mathcal {O}(n)\) . We also characterize minimal widths of BDDs representing the set of all solutions to a stable set problem for various basic classes of graphs. Besides implicitly enumerating or counting all solutions and optimizing a class of nonlinear objective functions that includes separable functions, the results can be applied for effective evaluation of generating functions. PubDate: 2017-03-01 DOI: 10.1007/s10472-016-9496-8 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Gabriele Kern-Isberner; Marco Wilhelm; Christoph Beierle Pages: 163 - 179 Abstract: Abstract An often used methodology for reasoning with probabilistic conditional knowledge bases is provided by the principle of maximum entropy (so-called MaxEnt principle) that realises an idea of least amount of assumed information and thus of being as unbiased as possible. In this paper we exploit the fact that MaxEnt distributions can be computed by solving nonlinear equation systems that reflect the conditional logical structure of these distributions. We apply the theory of Gröbner bases that is well known from computational algebra to the polynomial system which is associated with a MaxEnt distribution, in order to obtain results for reasoning with maximum entropy. We develop a three-phase compilation scheme extracting from a knowledge base consisting of probabilistic conditionals the information which is crucial for MaxEnt reasoning and transforming it to a Gröbner basis. Based on this transformation, a necessary condition for knowledge bases to be consistent is derived. Furthermore, approaches to answering MaxEnt queries are presented by demonstrating how inferring the MaxEnt probability of a single conditional from a given knowledge base is possible. Finally, we discuss computational methods to establish general MaxEnt inference rules. PubDate: 2017-03-01 DOI: 10.1007/s10472-015-9457-7 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Seishi Ouchi; Tomohiko Okayama; Keisuke Otaki; Ryo Yoshinaka; Akihiro Yamamoto Pages: 181 - 203 Abstract: Abstract This paper is concerned with a sufficient condition under which a concept class is learnable in Gold’s classical model of identification in the limit from positive data. The standard principle of learning algorithms working under this model is called the MINL strategy, which is to conjecture a hypothesis representing a minimal concept among the ones consistent with the given positive data. The minimality of a concept is defined with respect to the set-inclusion relation – the strategy is semantics-based. On the other hand, refinement operators have been developed in the field of learning logic programs, where a learner constructs logic programs as hypotheses consistent with given logical formulae. Refinement operators have syntax-based definitions – they are defined based on inference rules in first-order logic. This paper investigates the relation between the MINL strategy and refinement operators in inductive inference. We first show that if a hypothesis space admits a refinement operator with certain properties, the concept class will be learnable by an algorithm based on the MINL strategy. We then present an additional condition that ensures the learnability of the class of unbounded finite unions of concepts. Furthermore, we show that under certain assumptions a learning algorithm runs in polynomial time. PubDate: 2017-03-01 DOI: 10.1007/s10472-015-9458-6 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Xia Qu; Prashant Doshi Pages: 205 - 227 Abstract: Abstract Experiments show that in sequential bargaining games ( \(\mathcal {SBG}\) ), subjects usually deviate from game-theoretic predictions. Previous explanations have focused on considerations of fairness in the offers, and social utility functions have been formulated to model the data. However, a recent explanation by Ho and Su (Manag. Sci. 59(2), 452–469 2013) for observed deviations from game-theoretic predictions in sequential games such as the Centipede game is that players engage in limited backward induction. In this article, a suite of new and existing computational models that integrate different choice models with utility functions are comprehensively evaluated on \(\mathcal {SBG}\) data. These include DeBruyn and Bolton’s recursive quantal response with social utility functions, those based on Ho and Su’s dynamic level-k, and analogous extensions of the cognitive hierarchy with dynamic components. Our comprehensive analysis reveals that in extended \(\mathcal {SBG}\) with 5 rounds, models that capture violations of backward induction perform better than those that model fairness. However, we did not observe this result for \(\mathcal {SBG}\) with less rounds, and fairness of the offer remains a key consideration in these games. These findings contribute to the broader observation that non-social factors play a significant role in non-equilibrium play of sequential games. PubDate: 2017-03-01 DOI: 10.1007/s10472-015-9481-7 Issue No:Vol. 79, No. 1-3 (2017)

Authors:Takahisa Toda Pages: 229 - 244 Abstract: Abstract Dualization of Boolean functions is a fundamental problem that appears in various fields such as artificial intelligence, logic, data mining, etc. For monotone Boolean functions, many empirical researches that focus on practical efficiency have recently been done. We extend our previous work for monotone dualization and present a novel method for dualization that allows us to handle any Boolean function, including non-monotone Boolean functions. We furthermore present a variant of this method in cooperation with all solutions solver. By experiments we evaluate efficiency and characteristics of our methods. PubDate: 2017-03-01 DOI: 10.1007/s10472-016-9520-z Issue No:Vol. 79, No. 1-3 (2017)

Authors:Weifu Ding; Jiangshe Zhang Abstract: Abstract This paper presents a novel online object tracking algorithm with sparse representation for learning effective appearance models under a particle filtering framework. Compared with the state-of-the-art ℓ 1 sparse tracker, which simply assumes that the image pixels are corrupted by independent Gaussian noise, our proposed method is based on information theoretical Learning and is much less sensitive to corruptions; it achieves this by assigning small weights to occluded pixels and outliers. The most appealing aspect of this approach is that it can yield robust estimations without using the trivial templates adopted by the previous sparse tracker. By using a weighted linear least squares with non-negativity constraints at each iteration, a sparse representation of the target candidate is learned; to further improve the tracking performance, target templates are dynamically updated to capture appearance changes. In our template update mechanism, the similarity between the templates and the target candidates is measured by the earth movers’ distance(EMD). Using the largest open benchmark for visual tracking, we empirically compare two ensemble methods constructed from six state-of-the-art trackers, against the individual trackers. The proposed tracking algorithm runs in real-time, and using challenging sequences performs favorably in terms of efficiency, accuracy and robustness against state-of-the-art algorithms. PubDate: 2017-03-23 DOI: 10.1007/s10472-017-9543-0

Authors:Federico Bergenti; Stefania Monica Abstract: Abstract This paper describes an algorithm to enforce hyper-arc consistency of polynomial constraints defined over finite domains. First, the paper describes the language of so called polynomial constraints over finite domains, and it introduces a canonical form for such constraints. Then, the canonical form is used to transform the problem of testing the satisfiability of a constraint in a box into the problem of studying the sign of a related polynomial function in the same box, a problem which is effectively solved by using the modified Bernstein form of polynomials. The modified Bernstein form of polynomials is briefly discussed, and the proposed hyper-arc consistency algorithm is finally detailed. The proposed algorithm is a subdivision procedure which, starting from an initial approximation of the domains of variables, removes values from domains to enforce hyper-arc consistency. PubDate: 2017-03-20 DOI: 10.1007/s10472-017-9544-z

Authors:Claus Bendtsen; Andrea Degasperi; Ernst Ahlberg; Lars Carlsson Abstract: 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-03-18 DOI: 10.1007/s10472-017-9541-2

Authors:Vladimir Vovk; Ilia Nouretdinov; Valentina Fedorova; Ivan Petej; Alex Gammerman Abstract: Abstract We study optimal conformity measures for various criteria of efficiency of set-valued classification in an idealised setting. This leads to an important class of criteria of efficiency that we call probabilistic and argue for; it turns out that the most standard criteria of efficiency used in literature on conformal prediction are not probabilistic unless the problem of classification is binary. We consider both unconditional and label-conditional conformal prediction. PubDate: 2017-03-14 DOI: 10.1007/s10472-017-9540-3

Authors:Piotr Wojciechowski; Pavlos Eirinakis; K. Subramani Abstract: Erratum to: Ann Math Artif Intell (2017) 79:245-266 DOI 10.1007/s10472-016-9525-7 Owing to an error in the production process, the following article has been published incorrectly online. The article including the illustrations is presented hereafter. PubDate: 2017-03-03

Authors:Henrik Boström; Henrik Linusson; Tuve Löfström; Ulf Johansson Abstract: 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-03-01 DOI: 10.1007/s10472-017-9539-9

Authors:Vladimir Vapnik; Rauf Izmailov Abstract: 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-02-20 DOI: 10.1007/s10472-017-9538-x

Authors:Alberto Belussi; Sara Migliorini Abstract: Abstract Space and time are two important characteristics of data in many domains. This is particularly true in the archaeological context where information concerning the discovery location of objects allows one to derive important relations between findings of a specific survey or even of different surveys, and time aspects extend from the excavation time, to the dating of archaeological objects. In recent years, several attempts have been performed to develop a spatio-temporal information system tailored for archaeological data.The first aim of this paper is to propose a model, called \(\mathcal {S}\) tar, for representing spatio-temporal data in archaeology. In particular, since in this domain dates are often subjective, estimated and imprecise, \(\mathcal {S}\) tar has to incorporate such vague representation by using fuzzy dates and fuzzy relationships among them. Moreover, besides to the topological relations, another kind of spatial relations is particularly useful in archeology: the stratigraphic ones. Therefore, this paper defines a set of rules for deriving temporal knowledge from the topological and stratigraphic relations existing between two findings. Finally, considering the process through which objects are usually manually dated by archeologists, some existing automatic reasoning techniques may be successfully applied to guide such process. For this purpose, the last contribution regards the translation of archaeological temporal data into a Fuzzy Temporal Constraint Network for checking the overall data consistency and reducing the vagueness of some dates based on their relationships with other ones. PubDate: 2017-01-27 DOI: 10.1007/s10472-017-9535-0

Authors:Piotr Wojciechowski; Pavlos Eirinakis; K. Subramani Abstract: Abstract The theory of linear arithmetic (TLA), also known as the Theory of Rationals, is an extremely well-studied theory. It has been widely applied to a number of domains, including program verification and constraint specification. This paper discusses the computational complexities of two broad fragments of TLA, namely Quantified Linear Programs (QLPs) and Quantified Linear Implications (QLIs). These fragments are ideal for expressing specifications in real-time scheduling, and for modeling reactive systems. In this paper, we study the computational complexities of several variants of QLPs and QLIs. Our principal result shows that there exists a one-to-one correspondence between alternations in a class of QLIs and the complexity classes comprising the polynomial hierarchy PH. In other words, for each class of the PH, there exists a class of QLIs that is complete for that class. Our work mirrors the work in [L.J. Stockmeyer, The Polynomial-Time Hierarchy, Theoretical Computer Science, 3:1-22, 1977] which established the connection between the classes of PH and quantifier alternations in a Quantified Boolean Formula. Our results are surprising, since the variables in the fragments that we consider are continuous, as opposed to discrete. PubDate: 2016-09-23 DOI: 10.1007/s10472-016-9525-7