The Experts below are selected from a list of 11478 Experts worldwide ranked by ideXlab platform
Yuan Yao - One of the best experts on this subject based on the ideXlab platform.
-
boosting with structural sparsity a differential inclusion approach
Applied and Computational Harmonic Analysis, 2018Co-Authors: Chendi Huang, Xinwei Sun, Jiechao Xiong, Yuan YaoAbstract:Abstract Boosting as gradient descent algorithms is one popular method in machine learning. In this paper a novel Boosting-type algorithm is proposed based on restricted gradient descent with structural sparsity control whose underlying dynamics are governed by differential inclusions. In particular, we present an iterative regularization Path with structural sparsity where the parameter is sparse under some linear transforms, based on variable splitting and the Linearized Bregman Iteration. Hence it is called Split LBI. Despite its simplicity, Split LBI outperforms the popular generalized Lasso in both theory and experiments. A theory of Path Consistency is presented that equipped with a proper early stopping, Split LBI may achieve model selection Consistency under a family of Irrepresentable Conditions which can be weaker than the necessary and sufficient condition for generalized Lasso. Furthermore, some l 2 error bounds are also given at the minimax optimal rates. The utility and benefit of the algorithm are illustrated by several applications including image denoising, partial order ranking of sport teams, and world university grouping with crowdsourced ranking data.
-
boosting with structural sparsity a differential inclusion approach
arXiv: Machine Learning, 2017Co-Authors: Chendi Huang, Xinwei Sun, Jiechao Xiong, Yuan YaoAbstract:Boosting as gradient descent algorithms is one popular method in machine learning. In this paper a novel Boosting-type algorithm is proposed based on restricted gradient descent with structural sparsity control whose underlying dynamics are governed by differential inclusions. In particular, we present an iterative regularization Path with structural sparsity where the parameter is sparse under some linear transforms, based on variable splitting and the Linearized Bregman Iteration. Hence it is called \emph{Split LBI}. Despite its simplicity, Split LBI outperforms the popular generalized Lasso in both theory and experiments. A theory of Path Consistency is presented that equipped with a proper early stopping, Split LBI may achieve model selection Consistency under a family of Irrepresentable Conditions which can be weaker than the necessary and sufficient condition for generalized Lasso. Furthermore, some $\ell_2$ error bounds are also given at the minimax optimal rates. The utility and benefit of the algorithm are illustrated by several applications including image denoising, partial order ranking of sport teams, and world university grouping with crowdsourced ranking data.
Jochen Renz - One of the best experts on this subject based on the ideXlab platform.
-
Weak Composition for Qualitative Spatial and Temporal Reasoning
2005Co-Authors: Jochen Renz, Gérard LigozatAbstract:It has now been clear for some time that for many qualitative spatial or temporal calculi, for instance the well-known RCC8 calculus, the operation of composition of relations which is used is actually only weak composition, which is defined as the strongest relation in the calculus that contains the real composition. An immediate consequence for qualitative calculi where weak composition is not equivalent to composition is that the well-known concept of Path-Consistency is not applicable anymore. In these cases we can only use algebraic closure which corresponds to applying the Path-Consistency algorithm with weak composition instead of composition. In this paper we analyse the effects of having weak compositions. Starting with atomic CSPs, we show under which conditions algebraic closure can be used to decide Consistency in a qualitative calculus, how weak Consistency affects different important techniques for analysing qualitative calculi and under which conditions these techniques can be applied. For our analysis we introduce a new concept for qualitative relations, the " closure under constraints ". It turns out that the most important property of a qualitative calculus is not whether weak composition is equivalent to composition, but whether the relations are closed under constraints. All our results are general and can be applied to all existing and future qualitative spatial and temporal calculi. We close our paper with a road map of how qualitative calculi should be analysed. As a side effect it turns out that some results in the literature have to be reconsidered.
-
combining topological and size information for spatial reasoning
Artificial Intelligence, 2002Co-Authors: Alfonso Gerevini, Jochen RenzAbstract:Information about the size of spatial regions is often easily accessible and, when combined with other types of spatial information, it can be practically very useful. In this paper we introduce four classes of qualitative and metric size constraints, and we study their integration with the Region Connection Calculus RCC-8, a well-known approach to qualitative spatial reasoning with topological relations. We propose a new Path-Consistency algorithm for combining RCC-8 relations and qualitative size relations. The algorithm is complete for deciding satisfiability of an input set of topological constraints over one of the three maximal tractable subclasses of RCC-8 containing all the basic relations. Moreover, its time complexity is cubic and is the same as the complexity of the best-known method for deciding satisfiability when only these topological relations are considered. We also provide results on finding a consistent scenario in cubic time for these combined classes. Regarding metric size constraints, we first study their combination with RCC-8 and we show that deciding satisfiability for the combined sets of constraints is NP-hard, even when only the RCC-8 basic relations are used. Then we introduce RCC-7, a subalgebra of RCC-8 that can be used for applications where spatial regions cannot partially overlap. We show that reasoning with the seven RCC-7 basic relations and the universal relation is intractable, but that reasoning with the RCC-7 basic relations combined with metric size information is tractable. Finally, we give a polynomial algorithm for the latter case and a backtracking algorithm for the general case.
-
maximal tractable fragments of the region connection calculus a complete analysis
International Joint Conference on Artificial Intelligence, 1999Co-Authors: Jochen RenzAbstract:We present a general method for proving tractability of reasoning over disjunctions of jointly exhaustive and pairwise disjoint relations. Examples of these kinds of relations are Allen's temporal interval relations and their spatial counterpart, the R.CC8 relations by Randell, Cui, and Colin. Applying this method does not require detailed knowledge about the considered relations; instead, it is rather sufficient to have a subset of the considered set of relations for which Path-Consistency is known to decide Consistency. Using this method, we give a complete classification of tractability of reasoning over RCC8 by identifying two large new maximal tractable subsets and show that these two subsets together with H∞, the already known maximal tractable subset, are the only such sets for RCC8 that contain all base relations. We also apply our method to Allen's interval algebra and derive the known maximal tractable subset.
Bernhard Nebel - One of the best experts on this subject based on the ideXlab platform.
-
the finest of its class the natural point based ternary calculus lr for qualitative spatial reasoning
International Conference Spatial Cognition, 2004Co-Authors: Alexander Scivos, Bernhard NebelAbstract:In this paper, a ternary qualitative calculus ${\mathcal LR}$ for spatial reasoning is presented that distinguishes between left and right. A theory is outlined for ternary point-based calculi in which all the relations are invariant when all points are mapped by rotations, scalings, or translations (RST relations). For this purpose, we develop methods to determine arbitrary transformations and compositions of RST relations. We pose two criteria which we call practical and natural. ‘Practical' means that the relation system should be closed under transformations, compositions and intersections and have a finite base that is jointly exhaustive and pairwise disjoint. This implies that the well-known Path Consistency algorithm [10] can be used to conclude implicit knowledge. ‘Natural' calculi are close to our natural way of thinking because the base relations and their complements are connected. The main result of the paper is the identification of a maximally refined calculus amongst the practical natural RST calculi, which turns out to be very similar to Ligozat's flip-flop calculus. From that it follows, e.g., that there is no finite refinement of the TPCC calculus by Moratz et al that is closed under transformations, composition, and intersection.
-
on the complexity of qualitative spatial reasoning a maximal tractable fragment of the region connection calculus
Artificial Intelligence, 1999Co-Authors: Bernhard NebelAbstract:The computational properties of qualitative spatial reasoning have been investigated to some degree. However, the question for the boundary between polynomial and NP-hard reasoning problems has not been addressed yet. In this paper we explore this boundary in the ``Region Connection Calculus'''' RCC-8. We extend Bennett''s encoding of RCC-8 in modal logic. Based on this encoding, we prove that reasoning is NP-complete in general and identify a maximal tractable subset of the relations in RCC-8 that contains all base relations. Further, we show that for this subset Path-Consistency is sufficient for deciding Consistency.
-
reasoning about temporal relations a maximal tractable subclass of allen s interval algebra
Journal of the ACM, 1995Co-Authors: Bernhard Nebel, Hansjurgen BurckertAbstract:We introduce a new subclass of Allen's interval algebra we call “ORD-Horn subclass,” which is a strict superset of the “pointisable subclass.” We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem and show that the Path-Consistency method is sufficient for deciding satisfiability. Further, using an extensive machine-generated case analysis, we show that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P ≠ NP). In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations.
Jeanfrancois Condotta - One of the best experts on this subject based on the ideXlab platform.
-
a lazy algorithm to efficiently approximate singleton Path Consistency for qualitative constraint networks
International Conference on Tools with Artificial Intelligence, 2017Co-Authors: Michael Sioutis, Anastasia Paparrizou, Jeanfrancois CondottaAbstract:Partial singleton (weak) Path Consistency, or partial ♦-Consistency, for a qualitative constraint network, ensures that the process of instantiating any constraint of that network with any of its base relations b and enforcing partial (weak) Path Consistency, or partial ⋄-Consistency, in the updated network, yields a partially ⋄-consistent subnetwork where the respective constraint is still defined by b. This local Consistency is essential for helping to decide the satisfiability of challenging qualitative constraint networks and has been shown to play a crucial role in tackling more demanding problems associated with a given qualitative constraint network, such as the problem of minimal labeling. One of the main downsides to using partial ♦-Consistency, is that it is computationally expensive to enforce in a given qualitative constraint network, as, despite being a local Consistency in principle, it retains a global scope of the network at hand. In this paper, we propose a lazy algorithm that restricts the singleton checks associated with partial ♦-Consistency to constraints that are likely to lead to the removal of a base relation upon their propagation. A key feature of this algorithm is that it collectively eliminates certain unfeasible base relations by exploiting singleton checks. Further, we show that the closure that is obtained by our algorithm is incomparable to the one that is entailed by partial ♦-Consistency and non-unique in general. We demonstrate the efficiency of our algorithm via an experimental evaluation with random Interval Algebra networks from the phase transition region of two separate models and, moreover, show that it can exhibit very similar pruning capability for such networks to the one of an algorithm for enforcing partial ♦-Consistency.
-
vertex incremental Path Consistency for qualitative constraint networks
Hellenic Conference on Artificial Intelligence, 2014Co-Authors: Michael Sioutis, Jeanfrancois CondottaAbstract:The Interval Algebra (IA) and a subset of the Region Connection Calculus, namely, RCC-8, are the dominant Artificial Intelligence approaches for representing and reasoning about qualitative temporal and topological relations respectively. Such qualitative information can be formulated as a Qualitative Constraint Network (QCN). In this framework, one of the main tasks is to compute the Path Consistency of a given QCN. We propose a new algorithm that applies Path Consistency in a vertex incremental manner. Our algorithm enforces Path Consistency on an initial Path consistent QCN augmented by a new temporal or spatial entity and a new set of constraints, and achieves better performance than the state-of-the-art approach. We evaluate our algorithm experimentally with QCNs of RCC-8 and show the efficiency of our approach.
-
from Path Consistency to global Consistency in temporal qualitative constraint networks
Artificial Intelligence: Methodology Systems Applications, 2012Co-Authors: Nouhad Amaneddine, Jeanfrancois CondottaAbstract:We study in this paper the problem of global Consistency for qualitative constraints networks (QCNs) of the Point Algebra (PA) and the Interval Algebra (IA). In particular, we consider the subclass $\mathcal{S}_{\sf PA}$ corresponding to the set of relations of PA except the relations { ,=}, and the subclass $\mathcal{S}_{\sf IA}$ corresponding to pointizable relations of IA one can express by means of relations of $\mathcal{S}_{\sf PA}$. We prove that Path-Consistency implies global Consistency for QCNs defined on these subclasses. Moreover, we show that with the subclasses corresponding to convex relations, there are unique greatest subclasses of PA and IA containing singleton relations satisfying this property.
-
Consistency of triangulated temporal qualitative constraint networks
International Conference on Tools with Artificial Intelligence, 2011Co-Authors: Assef Chmeiss, Jeanfrancois CondottaAbstract:In this paper, we introduce for the qualitative constraint networks (QCNs) a new Consistency: the partial weak composition Consistency. The partial weak composition Consistency, similarly to the partial Path-Consistency, considers triangles of a graph and corresponds to the weak composition Consistency restricted to these triangles. We show that for the pre-convex QCNs of the Interval Algebra (IA), the partial weak composition Consistency with respect to a triangulation of the graph of constraints is sufficient to decide the Consistency problem. From this result, we propose an algorithm allowing to solve QCNs of IA. The experiments that we have conducted show the interest of this algorithm to solve the Consistency problem of the QCNs of IA.
-
a tractable subclass of the block algebra constraint propagation and preconvex relations
Portuguese Conference on Artificial Intelligence, 1999Co-Authors: P. Balbiani, Jeanfrancois Condotta, Luis Farinas Del CerroAbstract:We define, in this paper, for every n ≥ 1, n-dimensional block algebra as a set of relations, the block relations, together with the fundamental operations of composition, conversion and intersection. We examine the 13n atomic relations of this algebra which constitute the exhaustive list of the permitted relations that can hold between two blocks whose sides are parallel to the axes of some orthogonal basis in the n-dimensional Euclidean space over the field of real numbers. We organize these atomic relations in ascending order with the intention of defining the concept of convexity as well as the one of preconvexity. We will confine ourselves to the issue of the Consistency of block networks which consist of sets of constraints between a finite number of blocks. Showing that the concepts of convexity and preconvexity are preserved by the fundamental operations, we prove the tractability of the problem of the Consistency of strongly preconvex block networks, on account of our capacity for deciding it in polynomial time by means of the Path-Consistency algorithm.
Michael Sioutis - One of the best experts on this subject based on the ideXlab platform.
-
exploring directional Path Consistency for solving constraint networks
The Computer Journal, 2018Co-Authors: Shufeng Kong, Michael SioutisAbstract:Among the local Consistency techniques used for solving constraint networks, Path-Consistency (PC) has received a great deal of attention. However, enforcing PC is computationally expensive and som ...
-
a lazy algorithm to efficiently approximate singleton Path Consistency for qualitative constraint networks
International Conference on Tools with Artificial Intelligence, 2017Co-Authors: Michael Sioutis, Anastasia Paparrizou, Jeanfrancois CondottaAbstract:Partial singleton (weak) Path Consistency, or partial ♦-Consistency, for a qualitative constraint network, ensures that the process of instantiating any constraint of that network with any of its base relations b and enforcing partial (weak) Path Consistency, or partial ⋄-Consistency, in the updated network, yields a partially ⋄-consistent subnetwork where the respective constraint is still defined by b. This local Consistency is essential for helping to decide the satisfiability of challenging qualitative constraint networks and has been shown to play a crucial role in tackling more demanding problems associated with a given qualitative constraint network, such as the problem of minimal labeling. One of the main downsides to using partial ♦-Consistency, is that it is computationally expensive to enforce in a given qualitative constraint network, as, despite being a local Consistency in principle, it retains a global scope of the network at hand. In this paper, we propose a lazy algorithm that restricts the singleton checks associated with partial ♦-Consistency to constraints that are likely to lead to the removal of a base relation upon their propagation. A key feature of this algorithm is that it collectively eliminates certain unfeasible base relations by exploiting singleton checks. Further, we show that the closure that is obtained by our algorithm is incomparable to the one that is entailed by partial ♦-Consistency and non-unique in general. We demonstrate the efficiency of our algorithm via an experimental evaluation with random Interval Algebra networks from the phase transition region of two separate models and, moreover, show that it can exhibit very similar pruning capability for such networks to the one of an algorithm for enforcing partial ♦-Consistency.
-
efficient Path Consistency algorithm for large qualitative constraint networks
International Joint Conference on Artificial Intelligence, 2016Co-Authors: Zhiguo Long, Michael SioutisAbstract:We propose a new algorithm called DPC+ to enforce partial Path Consistency (PPC) on qualitative constraint networks. PPC restricts Path Consistency (PC) to a triangulation of the underlying constraint graph of a network. As PPC retains the sparseness of a constraint graph, it can make reasoning tasks such as Consistency checking and minimal labelling of large qualitative constraint networks much easier to tackle than PC. For qualitative constraint networks defined over any distributive subalgebra of well-known spatio-temporal calculi, such as the Region Connection Calculus and the Interval Algebra, we show that DPC+ can achieve PPC very fast. Indeed, the algorithm enforces PPC on a qualitative constraint network by processing each triangle in a triangulation of its underlying constraint graph at most three times. Our experiments demonstrate significant improvements of DPC+ over the state-of-the-art PPC enforcing algorithm.
-
vertex incremental Path Consistency for qualitative constraint networks
Hellenic Conference on Artificial Intelligence, 2014Co-Authors: Michael Sioutis, Jeanfrancois CondottaAbstract:The Interval Algebra (IA) and a subset of the Region Connection Calculus, namely, RCC-8, are the dominant Artificial Intelligence approaches for representing and reasoning about qualitative temporal and topological relations respectively. Such qualitative information can be formulated as a Qualitative Constraint Network (QCN). In this framework, one of the main tasks is to compute the Path Consistency of a given QCN. We propose a new algorithm that applies Path Consistency in a vertex incremental manner. Our algorithm enforces Path Consistency on an initial Path consistent QCN augmented by a new temporal or spatial entity and a new set of constraints, and achieves better performance than the state-of-the-art approach. We evaluate our algorithm experimentally with QCNs of RCC-8 and show the efficiency of our approach.