Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Concise Function Representation for Faster Exact MPE and Constrained Optimisation in Graphical Models
71
0
0.0
(
0
)
Added by
Filippo Bistaffa
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Filippo Bistaffa
Ask ChatGPT about the research
No Arabic abstract
We propose a novel concise function representation for graphical models, a central theoretical framework that provides the basis for many reasoning tasks. We then show how we exploit our concise representation based on deterministic finite state automata within Bucket Elimination (BE), a general approach based on the concept of variable elimination that accommodates many inference and optimisation tasks such as most probable explanation and constrained optimisation. We denote our version of BE as FABE. By using our concise representation within FABE, we dramatically improve the performance of BE in terms of runtime and memory requirements. Results on standard benchmarks obtained using an established experimental methodology show that FABE often outperforms the best available approach (RBFAOO), leading to significant runtime improvements (up to 2 orders of magnitude in our tests).
rate research
Read More
We develop a general framework for MAP estimation in discrete and Gaussian graphical models using Lagrangian relaxation techniques. The key idea is to reformulate an intractable estimation problem as one defined on a more tractable graph, but subject to additional constraints. Relaxing these constraints gives a tractable dual problem, one defined by a thin graph, which is then optimized by an iterative procedure. When this iterative optimization leads to a consistent estimate, one which also satisfies the constraints, then it corresponds to an optimal MAP estimate of the original model. Otherwise there is a ``duality gap, and we obtain a bound on the optimal solution. Thus, our approach combines convex optimization with dynamic programming techniques applicable for thin graphs. The popular tree-reweighted max-product (TRMP) method may be seen as solving a particular class of such relaxations, where the intractable graph is relaxed to a set of spanning trees. We also consider relaxations to a set of small induced subgraphs, thin subgraphs (e.g. loops), and a connected tree obtained by ``unwinding cycles. In addition, we propose a new class of multiscale relaxations that introduce ``summary variables. The potential benefits of such generalizations include: reducing or eliminating the ``duality gap in hard problems, reducing the number or Lagrange multipliers in the dual problem, and accelerating convergence of the iterative optimization procedure.
Given a belief network with evidence, the task of finding the I most probable explanations (MPE) in the belief network is that of identifying and ordering the I most probable instantiations of the non-evidence nodes of the belief network. Although many approaches have been proposed for solving this problem, most work only for restricted topologies (i.e., singly connected belief networks). In this paper, we will present a new approach for finding I MPEs in an arbitrary belief network. First, we will present an algorithm for finding the MPE in a belief network. Then, we will present a linear time algorithm for finding the next MPE after finding the first MPE. And finally, we will discuss the problem of finding the MPE for a subset of variables of a belief network, and show that the problem can be efficiently solved by this approach.
In this paper, we present an InSphereNet method for the problem of 3D object classification. Unlike previous methods that use points, voxels, or multi-view images as inputs of deep neural network (DNN), the proposed method constructs a class of more representative features named infilling spheres from signed distance field (SDF). Because of the admirable spatial representation of infilling spheres, we can not only utilize very fewer number of spheres to accomplish classification task, but also design a lightweight InSphereNet with less layers and parameters than previous methods. Experiments on ModelNet40 show that the proposed method leads to superior performance than PointNet and PointNet++ in accuracy. In particular, if there are only a few dozen sphere inputs or about 100000 DNN parameters, the accuracy of our method remains at a very high level (over 88%). This further validates the conciseness and effectiveness of the proposed InSphere 3D representation. Keywords: 3D object classification , signed distance field , deep learning , infilling sphere
Graphical causal models are an important tool for knowledge discovery because they can represent both the causal relations between variables and the multivariate probability distributions over the data. Once learned, causal graphs can be used for classification, feature selection and hypothesis generation, while revealing the underlying causal network structure and thus allowing for arbitrary likelihood queries over the data. However, current algorithms for learning sparse directed graphs are generally designed to handle only one type of data (continuous-only or discrete-only), which limits their applicability to a large class of multi-modal biological datasets that include mixed type variables. To address this issue, we developed new methods that modify and combine existing methods for finding undirected graphs with methods for finding directed graphs. These hybrid methods are not only faster, but also perform better than the directed graph estimation methods alone for a variety of parameter settings and data set sizes. Here, we describe a new conditional independence test for learning directed graphs over mixed data types and we compare performances of different graph learning strategies on synthetic data.
We analyze the performance of membrane filters represented by pore networks using two criteria: 1) total volumetric throughput of filtrate over the filter lifetime and 2) accumulated foulant concentration in the filtrate. We first formulate the governing equations of fluid flow on a general network, and we model transport and adsorption of particles (foulants) within the network by imposing an advection equation with a sink term on each pore (edge) as well as conservation of fluid and foulant volumetric flow rates at each pore junction (network vertex). Such a setup yields a system of partial differential equations on the network. We study the influence of three geometric network parameters on filter performance: 1) average number of neighbors of each vertex; 2) initial total void volume of the pore network; and 3) tortuosity of the network. We find that total volumetric throughput depends more strongly on the initial void volume than on average number of neighbors. Tortuosity, however, turns out to be a universal parameter, leading to almost perfect collapse of all results for a variety of different network architectures. In particular, the accumulated foulant concentration in the filtrate shows an exponential decay as tortuosity increases.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
