Timezone: »
This paper re-examines a continuous optimization framework dubbed NOTEARS for learning Bayesian networks. We first generalize existing algebraic characterizations of acyclicity to a class of matrix polynomials. Next, focusing on a one-parameter-per-edge setting, it is shown that the Karush-Kuhn-Tucker (KKT) optimality conditions for the NOTEARS formulation cannot be satisfied except in a trivial case, which explains a behavior of the associated algorithm. We then derive the KKT conditions for an equivalent reformulation, show that they are indeed necessary, and relate them to explicit constraints that certain edges be absent from the graph. If the score function is convex, these KKT conditions are also sufficient for local minimality despite the non-convexity of the constraint. Informed by the KKT conditions, a local search post-processing algorithm is proposed and shown to substantially and universally improve the structural Hamming distance of all tested algorithms, typically by a factor of 2 or more. Some combinations with local search are both more accurate and more efficient than the original NOTEARS.
Author Information
Dennis Wei (IBM Research)
Tian Gao (IBM Research AI)
Yue Yu (Lehigh University)
Related Events (a corresponding poster, oral, or spotlight)
-
2020 Poster: DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks »
Thu. Dec 10th 05:00 -- 07:00 PM Room Poster Session 5 #1526
More from the Same Authors
-
2022 Poster: On the Safety of Interpretable Machine Learning: A Maximum Deviation Approach »
Dennis Wei · Rahul Nair · Amit Dhurandhar · Kush Varshney · Elizabeth Daly · Moninder Singh -
2022 Poster: Logical Credal Networks »
Radu Marinescu · Haifeng Qian · Alexander Gray · Debarun Bhattacharjya · Francisco Barahona · Tian Gao · Ryan Riegel · Pravinda Sahu -
2021 Poster: CoFrNets: Interpretable Neural Architecture Inspired by Continued Fractions »
Isha Puri · Amit Dhurandhar · Tejaswini Pedapati · Karthikeyan Shanmugam · Dennis Wei · Kush Varshney -
2021 : AIMEE: Interactive model maintenance with rule-based surrogates »
Owen Cornec · Rahul Nair · Oznur Alkan · Dennis Wei · Elizabeth Daly -
2021 Poster: Causal Inference for Event Pairs in Multivariate Point Processes »
Tian Gao · Dharmashankar Subramanian · Debarun Bhattacharjya · Xiao Shou · Nicholas Mattei · Kristin P Bennett -
2018 Poster: Boolean Decision Rules via Column Generation »
Sanjeeb Dash · Oktay Gunluk · Dennis Wei -
2018 Spotlight: Boolean Decision Rules via Column Generation »
Sanjeeb Dash · Oktay Gunluk · Dennis Wei -
2018 Poster: Proximal Graphical Event Models »
Debarun Bhattacharjya · Dharmashankar Subramanian · Tian Gao -
2018 Spotlight: Proximal Graphical Event Models »
Debarun Bhattacharjya · Dharmashankar Subramanian · Tian Gao -
2017 Poster: Optimized Pre-Processing for Discrimination Prevention »
Flavio Calmon · Dennis Wei · Bhanukiran Vinzamuri · Karthikeyan Natesan Ramamurthy · Kush Varshney -
2016 Poster: A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++ »
Dennis Wei