Performance analysis of a greedy algorithm for inferring Boolean functions

DOI10.1016/J.IPL.2004.09.017MaRDI QIDQ834975zbMATH OpenOpenAlexFDO

Authors Daiji Fukagawa, Tatsuya Akutsu

Publication date 27 August 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.09.017

zbMATH Keywords

analysis of algorithmsmachine learningunbalanced functionuniform distribution

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms (68W40)

Recommendations

• A greedy randomized adaptive search procedure (GRASP) for inferring logical clauses from examples in polynomial time and some extensions
• Robust inference of relevant attributes
• scientific article; zbMATH DE number 847791
• Bounds on the Performance of a Greedy Algorithm for Probabilities
• The worst case behavior of a greedy algorithm for a class of pseudo- Boolean functions

Cites work

• A simple greedy algorithm for finding functional relations: Efficient implementation and average case analysis
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Finding essential attributes from binary data
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Learning juntas
• On the complexity of inferring functional dependencies
• Robust inference of relevant attributes
• Selection of relevant features and examples in machine learning

Cited in

(4)

• Algorithms for Inference, Analysis and Control of Boolean Networks
• scientific article; zbMATH DE number 1543307 (Why is no real title available?)
• Robust inference of relevant attributes
• An efficient top-down search algorithm for learning Boolean networks of gene expression

This page was built for publication: Performance analysis of a greedy algorithm for inferring Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q834975)