Analytic Properties of Trackable Weak Models
- URL: http://arxiv.org/abs/2001.07608v1
- Date: Wed, 8 Jan 2020 15:54:56 GMT
- Title: Analytic Properties of Trackable Weak Models
- Authors: Mark Chilenski, George Cybenko, Isaac Dekine, Piyush Kumar, Gil Raz
- Abstract summary: We present several new results on the feasibility of inferring the hidden states in strongly-connected trackable weak models.
A weak model is said to be trackable if the worst case number of such hypotheses grows as entropy in the sequence length.
We show that the number of hypotheses in strongly-connected trackable models is bounded by a constant and give an expression for this constant.
- Score: 2.204918347869259
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present several new results on the feasibility of inferring the hidden
states in strongly-connected trackable weak models. Here, a weak model is a
directed graph in which each node is assigned a set of colors which may be
emitted when that node is visited. A hypothesis is a node sequence which is
consistent with a given color sequence. A weak model is said to be trackable if
the worst case number of such hypotheses grows as a polynomial in the sequence
length. We show that the number of hypotheses in strongly-connected trackable
models is bounded by a constant and give an expression for this constant. We
also consider the problem of reconstructing which branch was taken at a node
with same-colored out-neighbors, and show that it is always eventually possible
to identify which branch was taken if the model is strongly connected and
trackable. We illustrate these properties by assigning transition probabilities
and employing standard tools for analyzing Markov chains. In addition, we
present new results for the entropy rates of weak models according to whether
they are trackable or not. These theorems indicate that the combination of
trackability and strong connectivity dramatically simplifies the task of
reconstructing which nodes were visited. This work has implications for any
problem which can be described in terms of an agent traversing a colored graph,
such as the reconstruction of hidden states in a hidden Markov model (HMM).
Related papers
- Learning-Order Autoregressive Models with Application to Molecular Graph Generation [52.44913282062524]
We introduce a variant of ARM that generates high-dimensional data using a probabilistic ordering that is sequentially inferred from data.
We demonstrate experimentally that our method can learn meaningful autoregressive orderings in image and graph generation.
arXiv Detail & Related papers (2025-03-07T23:24:24Z) - Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
We consider the linear causal representation learning setting where we observe a linear mixing of $d$ unknown latent factors.
Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them.
We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes.
arXiv Detail & Related papers (2024-10-31T15:56:50Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.
Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix.
Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
arXiv Detail & Related papers (2024-02-29T09:26:46Z) - ChiroDiff: Modelling chirographic data with Diffusion Models [132.5223191478268]
We introduce a powerful model-class namely "Denoising Diffusion Probabilistic Models" or DDPMs for chirographic data.
Our model named "ChiroDiff", being non-autoregressive, learns to capture holistic concepts and therefore remains resilient to higher temporal sampling rate.
arXiv Detail & Related papers (2023-04-07T15:17:48Z) - Joint graph learning from Gaussian observations in the presence of
hidden nodes [26.133725549667734]
We propose a joint graph learning method that takes into account the presence of hidden (latent) variables.
We exploit the structure resulting from the previous considerations to propose a convex optimization problem.
We compare the proposed algorithm with different baselines and evaluate its performance over synthetic and real-world graphs.
arXiv Detail & Related papers (2022-12-04T13:03:41Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton.
The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases.
In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
arXiv Detail & Related papers (2022-12-01T11:49:07Z) - Implicit vs Unfolded Graph Neural Networks [18.084842625063082]
Graph neural networks (GNNs) sometimes struggle to maintain a healthy balance between modeling long-range dependencies and avoiding unintended consequences.
Two separate strategies have recently been proposed, namely implicit and unfolded GNNs.
We provide empirical head-to-head comparisons across a variety of synthetic and public real-world benchmarks.
arXiv Detail & Related papers (2021-11-12T07:49:16Z) - An Interpretable Graph Generative Model with Heterophily [38.59200985962146]
We propose the first edge-independent graph generative model that is expressive enough to capture heterophily.
Our experiments demonstrate the effectiveness of our model for a variety of important application tasks.
arXiv Detail & Related papers (2021-11-04T17:34:39Z) - Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised
Node Classification [59.06717774425588]
We propose the Explicit Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph as a partially observed Markov Random Field.
It contains explicit pairwise factors to model output-output relations and uses a GNN backbone to model input-output relations.
We conduct experiments on various datasets, which shows that our model can effectively improve the performance for semi-supervised node classification on graphs.
arXiv Detail & Related papers (2021-07-27T19:47:53Z) - Robustness of Community Detection to Random Geometric Perturbations [16.575947847660778]
We consider the block model where connection between vertices is perturbed by some latent (and unobserved) random geometric graph.
The objective is to prove that spectral methods are robust to this type of noise, even if they are agnostic to the presence (or not) of the random graph.
arXiv Detail & Related papers (2020-11-09T10:15:40Z) - Structural Causal Models Are (Solvable by) Credal Networks [70.45873402967297]
Causal inferences can be obtained by standard algorithms for the updating of credal nets.
This contribution should be regarded as a systematic approach to represent structural causal models by credal networks.
Experiments show that approximate algorithms for credal networks can immediately be used to do causal inference in real-size problems.
arXiv Detail & Related papers (2020-08-02T11:19:36Z) - Fairness constraints can help exact inference in structured prediction [37.76221231305701]
We study a generative model with an undirected connected graph $G$ and true vector of binary labels.
We find that, in contrast to the known trade-offs between fairness and model performance, the addition of the fairness constraint improves the probability of exact recovery.
arXiv Detail & Related papers (2020-07-01T04:11:29Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.