RECORD
Robust Estimation of Tree Structured Ising Models
Machine Learning · Submitted 10 Jun 2020
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We consider the task of learning Ising models when the signs of different random variables are flipped independently with possibly unequal, unknown probabilities. | background 1.00 | 0.14 | 0.03 | asserted 0.81 |
| s1 | In this paper, we focus on the problem of robust estimation of tree-structured Ising models. | background 0.51 | 0.44 | 0.05 | asserted 0.85 |
| s2 | Without any additional assumption of side information, this is an open problem. | gap 0.98 | 0.12 | 0.04 | asserted 1.00 |
| s3 | 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. | result 0.95 | 0.91 | 0.22 | asserted 1.00 |
| s4 | Next, we propose an algorithm to solve the above problem with logarithmic sample complexity in the number of nodes and polynomial run-time complexity. | method 0.51 | 0.95 | 0.41 | asserted 1.00 |
| s5 | 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. | result 0.95 | 0.94 | 0.41 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
How the literature uses it
5 arXiv papers cite this in 39 sentences
Papers citing it · 24 sentences without a confident label
Builds on it 3 papers
-
Our first main result is a generalization of the identifiability result in [ref] to the situation of arbitrary discrete variables with an arbitrary but equal number of states.
Robust estimation of tree structured models · Introduction · 1.00
-
More importantly, this also generalizes the identifiability results from earlier lines of work and identifies an equivalence class up to which one may hope to recover the underlying structure. * We devise a novel algorithm, called (for Noisy Model selection based on Ancestor Discovery), that tackles the robust model selection problem for general graphs extending the results of [ref] .
Robust Model Selection of Gaussian Graphical Models · Introduction · 0.98
-
In [ref] the authors extend the results in [ref] , providing better sample complexity results and a more efficient algorithm.
Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise · Related Work · 0.91
Compares with it 4 papers
-
Indeed, we show through error exponent analyses [ref] using Sanov’s theorem [ref] that the error exponents of SGA are higher (and hence better) than that in [ref] for all but a small fraction of trees.
SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples · Introduction · 0.86
-
Indeed, the equivalence class thus obtained is the same one identified by [ref] .
Robust Model Selection of Gaussian Graphical Models · The Robust Model Selection Problem · 0.95
-
This is in contrast to the Gaussian graphical model and Ising model results ( [ref] , [ref] , [ref] ) where, for a fixed tree structure, edges within a leaf cluster (a leaf node, its parent, and its siblings) are never recoverable irrespective of the probability distribution of the non-noisy random variables.
Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise · Introduction · 1.00
Cites it as background 2 papers
-
Similarly, Katiyar et al. studies the problem of recovering tree-structured Ising model from non-identically distributed noises [ref] .
Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data · Motivation and Literature Review · 0.80
-
Despite its simplicity, these models can be useful in image/video classification, for exploratory analysis in high-dimensional settings, and as first approximations in more complicated systems; see [ref] and references therein.
Robust estimation of tree structured models · Introduction · 0.89
What it cites · 5 sentences without a confident label
Cites as background 3 papers
-
Efficient algorithms for structure learning of Ising models can be divided into three main categories based on their assumptions: i) special graph structures [ref] , ii) nature of interaction between variables such as correlation decay property (CDP) [ref] , iii) bounded degree/width [ref] .
Learning a Tree-Structured Ising Model in Order to Make Predictions · Related Work · 0.97
-
Efficient algorithms for structure learning of Ising models can be divided into three main categories based on their assumptions: i) special graph structures [ref] , ii) nature of interaction between variables such as correlation decay property (CDP) [ref] , iii) bounded degree/width [ref] .
Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models · Related Work · 0.97
-
Recently, Ising models have also proven quite popular in biology [ref] , engineering [ref] , computer vision [ref] , and also in the optimization and OR communities, including in finance [ref] , and social networks [ref] .
Detecting Influence Campaigns in Social Networks Using the Ising Model · Introduction · 0.92
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.