Active Structure Learning of Bayesian Networks in an Observational Setting

• URL: http://arxiv.org/abs/2103.13796v1
• Date: Thu, 25 Mar 2021 12:50:14 GMT
• Title: Active Structure Learning of Bayesian Networks in an Observational Setting
• Authors: Noa Ben-David and Sivan Sabato
• Abstract summary: We study active structure learning of Bayesian networks in an observational setting. We propose a new active learning algorithm that finds with a high probability a structure with a score that is $epsilon$-close to the optimal score. We show that for a class of distributions that we term stable, a sample complexity reduction of up to a factor of $widetildeOmega(d3)$ can be obtained, where $d$ is the number of network variables.
• Score: 21.376800678915558
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study active structure learning of Bayesian networks in an observational setting, in which there are external limitations on the number of variable values that can be observed from the same sample. Random samples are drawn from the joint distribution of the network variables, and the algorithm iteratively selects which variables to observe in the next sample. We propose a new active learning algorithm for this setting, that finds with a high probability a structure with a score that is $\epsilon$-close to the optimal score. We show that for a class of distributions that we term stable, a sample complexity reduction of up to a factor of $\widetilde{\Omega}(d^3)$ can be obtained, where $d$ is the number of network variables. We further show that in the worst case, the sample complexity of the active algorithm is guaranteed to be almost the same as that of a naive baseline algorithm. To supplement the theoretical results, we report experiments that compare the performance of the new active algorithm to the naive baseline and demonstrate the sample complexity improvements. Code for the algorithm and for the experiments is provided at https://github.com/noabdavid/activeBNSL.

Related papers

• Scaling LLM Inference with Optimized Sample Compute Allocation [56.524278187351925]
  We propose OSCA, an algorithm to find an optimal mix of different inference configurations. Our experiments show that with our learned mixed allocation, we can achieve accuracy better than the best single configuration. OSCA is also shown to be effective in agentic beyond single-turn tasks, achieving a better accuracy on SWE-Bench with 3x less compute than the default configuration.
  arXiv  Detail & Related papers  (2024-10-29T19:17:55Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Is Stochastic Gradient Descent Near Optimal? [0.0]
  We show that gradient descent achieves small expected error with a number of samples and total number of queries. This suggests that SGD nearly achieves the information-theoretic sample complexity bounds of Joen & Van Roy (arXiv:2203.00246) in a computationally efficient manner.
  arXiv  Detail & Related papers  (2022-09-18T18:26:43Z)
• Parallel Sampling for Efficient High-dimensional Bayesian Network Structure Learning [6.85316573653194]
  This paper describes an approximate algorithm that performs parallel sampling on Candidate Parent Sets (CPSs) The modified algorithm, which we call Parallel Sampling MINOBS (PS-MINOBS), constructs the graph by sampling CPSs for each variable.
  arXiv  Detail & Related papers  (2022-02-19T22:35:59Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
  Several sampling algorithms with variance reduction have been proposed for accelerating the training of Graph Convolution Networks (GCNs) These sampling algorithms are not applicable to more general graph neural networks (GNNs) where the message aggregator contains learned weights rather than fixed weights, such as Graph Attention Networks (GAT)
  arXiv  Detail & Related papers  (2020-06-10T12:48:37Z)
• Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
  Learning a robust classifier from a few samples remains a key challenge in machine learning. In this paper, we study a minimax distributionally robust formulation of weighted $k$-nearest neighbors. We develop an algorithm, textttDr.k-NN, that efficiently solves this functional optimization problem.
  arXiv  Detail & Related papers  (2020-06-07T00:34:33Z)
• Towards Robust and Reproducible Active Learning Using Neural Networks [15.696979318409392]
  Active learning (AL) is a promising ML paradigm that has the potential to parse through large unlabeled data. Recently proposed neural network based AL methods help reduce annotation cost in domains where labeling data can be prohibitive. In this study, we demonstrate that different types of AL algorithms produce inconsistent gain over random sampling baseline.
  arXiv  Detail & Related papers  (2020-02-21T22:01:47Z)

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.