Efficient and Scalable Structure Learning for Bayesian Networks: Algorithms and Applications

• URL: http://arxiv.org/abs/2012.03540v1
• Date: Mon, 7 Dec 2020 09:11:08 GMT
• Title: Efficient and Scalable Structure Learning for Bayesian Networks: Algorithms and Applications
• Authors: Rong Zhu, Andreas Pfadler, Ziniu Wu, Yuxing Han, Xiaoke Yang, Feng Ye, Zhenping Qian, Jingren Zhou, Bin Cui
• Abstract summary: We propose a new structure learning algorithm, LEAST, which comprehensively fulfills our business requirements. LEAST is deployed and serves for more than 20 applications with thousands of executions per day. We show that LEAST unlocks the possibility of applying BN structure learning in new areas, such as large-scale gene expression data analysis and explainable recommendation system.
• Score: 33.8980356362084
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Structure Learning for Bayesian network (BN) is an important problem with extensive research. It plays central roles in a wide variety of applications in Alibaba Group. However, existing structure learning algorithms suffer from considerable limitations in real world applications due to their low efficiency and poor scalability. To resolve this, we propose a new structure learning algorithm LEAST, which comprehensively fulfills our business requirements as it attains high accuracy, efficiency and scalability at the same time. The core idea of LEAST is to formulate the structure learning into a continuous constrained optimization problem, with a novel differentiable constraint function measuring the acyclicity of the resulting graph. Unlike with existing work, our constraint function is built on the spectral radius of the graph and could be evaluated in near linear time w.r.t. the graph node size. Based on it, LEAST can be efficiently implemented with low storage overhead. According to our benchmark evaluation, LEAST runs 1 to 2 orders of magnitude faster than state of the art method with comparable accuracy, and it is able to scale on BNs with up to hundreds of thousands of variables. In our production environment, LEAST is deployed and serves for more than 20 applications with thousands of executions per day. We describe a concrete scenario in a ticket booking service in Alibaba, where LEAST is applied to build a near real-time automatic anomaly detection and root error cause analysis system. We also show that LEAST unlocks the possibility of applying BN structure learning in new areas, such as large-scale gene expression data analysis and explainable recommendation system.

Related papers

• Coordinated Multi-Neighborhood Learning on a Directed Acyclic Graph [6.727984016678534]
  Learning the structure of causal directed acyclic graphs (DAGs) is useful in many areas of machine learning and artificial intelligence. It is challenging to obtain good empirical and theoretical results without strong and often restrictive assumptions. This paper develops a new constraint-based method for estimating the local structure around multiple user-specified target nodes.
  arXiv  Detail & Related papers  (2024-05-24T08:49:43Z)
• Divide-and-Conquer Strategy for Large-Scale Dynamic Bayesian Network Structure Learning [13.231953456197946]
  Dynamic Bayesian Networks (DBNs) are renowned for their interpretability. Structure learning of DBNs from data is challenging, particularly for datasets with thousands of variables. This paper introduces a novel divide-and-conquer strategy, originally developed for static BNs, and adapts it for large-scale DBN structure learning.
  arXiv  Detail & Related papers  (2023-12-04T09:03:06Z)
• Learning the Finer Things: Bayesian Structure Learning at the Instantiation Level [0.0]
  Successful machine learning methods require a trade-off between memorization and generalization. We present a novel probabilistic graphical model structure learning approach that can learn, generalize and explain in elusive domains.
  arXiv  Detail & Related papers  (2023-03-08T02:31:49Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation. We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
  arXiv  Detail & Related papers  (2022-06-01T23:26:51Z)
• Arch-Graph: Acyclic Architecture Relation Predictor for Task-Transferable Neural Architecture Search [96.31315520244605]
  Arch-Graph is a transferable NAS method that predicts task-specific optimal architectures. We show Arch-Graph's transferability and high sample efficiency across numerous tasks. It is able to find top 0.16% and 0.29% architectures on average on two search spaces under the budget of only 50 models.
  arXiv  Detail & Related papers  (2022-04-12T16:46:06Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  The area under the ROC curve (AUC) is one of the most widely used performance measures for classification models in machine learning. We develop an efficient approximated gradient descent method based on recent practical envelope smoothing technique. Our proposed algorithm can also be used to minimize the sum of some ranked range loss, which also lacks efficient solvers.
  arXiv  Detail & Related papers  (2022-03-03T03:46:18Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A* [12.117737635879037]
  Recent works related to data-driven planning aim at learning either cost functions or planner functions, but not both. We propose Neural Weighted A*, a differentiable anytime planner able to produce improved representations of planar maps as graph costs and planners. We experimentally show the validity of our claims by testing Neural Weighted A* against several baselines, introducing a novel, tile-based navigation dataset.
  arXiv  Detail & Related papers  (2021-05-04T13:17:30Z)

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.