128 research outputs found
Two classes of graphs in which some problems related to convexity are efficiently solvable
No full textMonophonic, geodesic and 2-geodesic convexities (m-convexity, g-convexity and 2g-convexity, for short) on graphs are based on the families of induced paths, shortest paths and shortest paths of length 2, respectively. We introduce a class of graphs, the class of cross-cyclicgraphs, in which every connected 2g-convex set is also g-convex and m-convex. We show that this class is properly contained in the class, say Γ, of graphs in which geodesic and monophonic convexities are equivalent and properly contains the class of distance-hereditary graphs. Moreover, we show that (1) an m-hull set (i.e., a subset of vertices, with minimum cardinality, whose m-convex hull equals the whole vertex set) and, hence, the m-hull number and the g-hull number of a graph in Γ can be computed in polynomial time and that (2) both the geodesic-convex hull and the monophonic-convex hull can be computed in linear time in a cross-cyclic graph without cycles of length 3 and, hence, in a bipartite distance-hereditary graph
Tree and local computations in a cross–entropy minimization problem with marginal constraints
Get PDFsummary:In probability theory, Bayesian statistics, artificial intelligence and database theory the minimum cross-entropy principle is often used to estimate a distribution with a given set of marginal distributions under the proportionality assumption with respect to a given ``prior'' distribution . Such an estimation problem admits a solution if and only if there exists an extension of that is dominated by . In this paper we consider the case that is not given explicitly, but is specified as the maximum-entropy extension of an auxiliary set of distributions. There are three problems that naturally arise: (1) the existence of an extension of a distribution set (such as and ), (2) the existence of an extension of that is dominated by the maximum entropy extension of , (3) the numeric computation of the minimum cross-entropy extension of with respect to the maximum entropy extension of . In the spirit of a divide-and-conquer approach, we prove that, for each of the three above-mentioned problems, the global solution can be easily obtained by combining the solutions to subproblems defined at node level of a suitable tree
Erratum: Equivalence of compositional expressions and independence relations in compositional models
Get PDFWe generalize Jiroušek's (right) composition operator in such a way that it can be applied to distribution functions with values in a "semifield", and introduce (parenthesized) compositional expressions, which in some sense generalize Jiroušek's "generating sequences" of compositional models. We say that two compositional expressions are equivalent if their evaluations always produce the same results whenever they are defined. Our first result is that a set system H is star-like with centre X if and only if every two compositional expressions with "base scheme" H and "key" X are equivalent. This result is stronger than Jiroušek's result which states that, if H is star-like with centre X, then every two generating sequences with base scheme H and key X are equivalent. Then, we focus on canonical expressions, by which we mean compositional expressions θ such that the sequence of the sets featured in θ and arranged in order of appearance enjoys the "running intersection property". Since every compositional expression, whose base scheme is a star-like set system with centre X and whose key is X, is a canonical expression, we investigate the equivalence between two canonical expressions with the same base scheme and the same key. We state a graphical characterization of those set systems H such that every two canonical expressions with base scheme H and key X are equivalent, and also provide a graphical algorithm for their recognition. Finally, we discuss the problem of detecting conditional independences that hold in a compositional model
The sum-product algorithm: algebraic independence and computational aspects
Get PDFsummary:The sum-product algorithm is a well-known procedure for marginalizing an “acyclic” product function whose range is the ground set of a commutative semiring. The algorithm is general enough to include as special cases several classical algorithms developed in information theory and probability theory. We present four results. First, using the sum-product algorithm we show that the variable sets involved in an acyclic factorization satisfy a relation that is a natural generalization of probability-theoretic independence. Second, we show that for the Boolean semiring the sum-product algorithm reduces to a classical algorithm of database theory. Third, we present some methods to reduce the amount of computation required by the sum-product algorithm. Fourth, we show that with a slight modification the sum-product algorithm can be used to evaluate a general sum-product expression
Auditing Sum Queries
No full textLecture Notes in Computer Science 2572 (G. Goos, J. Hartmanis, J. Van Leeuwen, eds.
An experimental set-up for the nucleation rate determination in supported undercooled liquid metal droplets
No full textEquivalence between hypergraph convexities
Get PDFLet G be a connected graph on V. A subset X of V is all-paths convex or ap-convex if X contains
each vertex on every path joining two vertices in X and ismonophonically convex orm-convex if
X contains each vertex on every chordless path joining two vertices in X. First of all, we prove that
ap-convexity and m-convexity coincide in G if and only if G is a tree. Next, in order to generalize
this result to a connected hypergraph H, in addition to the hypergraph versions of ap-convexity
and m-convexity, we consider canonical convexity or c-convexity and simple-path convexity
or sp-convexity for which it is well known that m-convexity is finer than both c-convexity and
sp-convexity and sp-convexity is finer than ap-convexity. After proving sp-convexity is coarser
than c-convexity, we characterize the hypergraphs in which each pair of the four convexities
above is equivalent. As a result, we obtain a convexity-theoretic characterization of Berge-acyclic
hypergraphs and of γ-acyclic hypergraphs
A backward selection procedure for approximating a discrete probability distribution by decomposable models
Get PDFsummary:Decomposable (probabilistic) models are log-linear models generated by acyclic hypergraphs, and a number of nice properties enjoyed by them are known. In many applications the following selection problem naturally arises: given a probability distribution over a finite set of discrete variables and a positive integer , find a decomposable model with tree-width that best fits . If is the generating hypergraph of a decomposable model and is the estimate of under the model, we can measure the closeness of to by the information divergence , so that the problem above reads: given and , find an acyclic, connected hypergraph of tree-width such that is minimum. It is well-known that this problem is -hard. However, for it was solved by Chow and Liu in a very efficient way; thus, starting from an optimal Chow-Liu solution, a few forward-selection procedures have been proposed with the aim at finding a `good' solution for an arbitrary . We propose a backward-selection procedure which starts from the (trivial) optimal solution for , and we show that, in a study case taken from literature, our procedure succeeds in finding an optimal solution for every
Characteristic properties and recognition of graphs in which geodesic and monophonic convexities are equivalent
No full textLet G be a connected graph. A subset X of V(G) is g-convex (mconvex)
if it contains all vertices on shortest (induced) paths between
vertices in X. We state characteristic properties of graphs in which every
g-convex set is m-convex, based on which we show that such graphs can
be recognized in polynomial time. Moreover, we state a new convexity - theoretic
characterization of Ptolemaic graphs
Canonical and monophonic convexities in hypergraphs
No full textKnown properties of "canonical connections" from database theory and of "closed sets" from statistics implicitly define a hypergraph convexity, here called canonical convexity (c-convexity), and provide an efficient algorithm to compute c-convex hulls. We characterize the class of hypergraphs in which c-convexity enjoys the Minkowski-Krein-Milman property. Moreover, we compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or m-convexity), and prove that: (1) m-convexity is coarser than c-convexity, (2) m-convexity and c-convexity are equivalent in conformal hypergraphs, and (3) m-convex hulls can be computed in the same efficient way as c-convex hulls. (C) 2009 Elsevier B.V. All rights reserved
- …
