Robust Estimation of Tree Structured Ising Models

• URL: http://arxiv.org/abs/2006.05601v1
• Date: Wed, 10 Jun 2020 01:32:45 GMT
• Title: Robust Estimation of Tree Structured Ising Models
• Authors: Ashish Katiyar, Vatsal Shah, Constantine Caramanis
• Abstract summary: We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities. We first prove that this problem is unidentifiable, however, this unidentifiability is limited to a small equivalence class of trees formed by leaf nodes exchanging positions with their neighbors.
• Score: 20.224160348675422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities. In this paper, we focus on the problem of robust estimation of tree-structured Ising models. Without any additional assumption of side information, this is an open problem. We first prove that this problem is unidentifiable, however, this unidentifiability is limited to a small equivalence class of trees formed by leaf nodes exchanging positions with their neighbors. Next, we propose an algorithm to solve the above problem with logarithmic sample complexity in the number of nodes and polynomial run-time complexity. Lastly, we empirically demonstrate that, as expected, existing algorithms are not inherently robust in the proposed setting whereas our algorithm correctly recovers the underlying equivalence class.

Related papers

• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Identification for Tree-shaped Structural Causal Models in Polynomial Time [1.5151556900495786]
  Identifying causal parameters from correlations between nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. We present a randomized-time algorithm, which solves the identification problem for tree-shaped SCMs.
  arXiv  Detail & Related papers  (2023-11-23T15:26:29Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Robust Model Selection of Gaussian Graphical Models [16.933125281564163]
  Noise-corrupted samples present significant challenges in graphical model selection. We propose an algorithm which provably recovers the underlying graph up to the identified ambiguity. This information is useful in a range of real-world problems, including power grids, social networks, protein-protein interactions, and neural structures.
  arXiv  Detail & Related papers  (2022-11-10T16:50:50Z)
• Estimating large causal polytrees from small samples [6.322831694506287]
  We consider the problem of estimating a large causal polytree from a relatively small i.i.d. sample. We give an algorithm that recovers the tree with high accuracy in such settings.
  arXiv  Detail & Related papers  (2022-09-15T03:41:09Z)
• Certifiable Robustness for Nearest Neighbor Classifiers [6.487663563916903]
  We study the complexity of certifying for a simple but widely deployed classification algorithm, $k$-Nearest Neighbors ($k$-NN) Our main focus is on inconsistent datasets when constraints are functional dependencies (FDs) We exhibit a similar counting version of the problem, where the goal is to count the number of possible worlds that predict a certain label.
  arXiv  Detail & Related papers  (2022-01-13T02:55:10Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [57.89518300699042]
  We study the problem of learning Ising models satisfying Dobrushin's condition in the outlier-robust setting where a constant fraction of the samples are adversarially corrupted. Our main result is to provide the first computationally efficient robust learning algorithm for this problem with near-optimal error guarantees.
  arXiv  Detail & Related papers  (2021-02-03T18:00:57Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure. We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
  arXiv  Detail & Related papers  (2021-01-22T01:57:35Z)
• Sample-Optimal and Efficient Learning of Tree Ising models [24.201827888085944]
  We show that $n$-variable tree-structured Ising models can be learned computationally-efficiently to within total variation distance $epsilon$ from an optimal $O(n ln n/epsilon2)$ samples. Our guarantees do not follow from known results for the Chow-Liu algorithm.
  arXiv  Detail & Related papers  (2020-10-28T10:17:48Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)

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.