An efficient query learning algorithm for zero-suppressed binary decision diagrams

Hayato Mizumoto, Shota Todoroki,  Diptarama, Ryo Yoshinaka, Ayumi Shinohara
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:360-371, 2017.

Abstract

A ZDD is a directed acyclic graph that represents a family of sets over a fixed universe set. In this paper, we propose an algorithm that learns zero-suppressed binary decision diagrams (ZDDs) using membership and equivalence queries. If the target ZDD has $n$ nodes and the cardinality of the universe is $m$, our algorithm uses $n$ equivalence queries and at most $n(\lfloor \log m \rfloor + 4n)$ membership queries to learn the target ZDD.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-mizumoto17a, title = {An efficient query learning algorithm for zero-suppressed binary decision diagrams}, author = {Mizumoto, Hayato and Todoroki, Shota and Diptarama, and Yoshinaka, Ryo and Shinohara, Ayumi}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {360--371}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/mizumoto17a/mizumoto17a.pdf}, url = {https://proceedings.mlr.press/v76/mizumoto17a.html}, abstract = {A ZDD is a directed acyclic graph that represents a family of sets over a fixed universe set. In this paper, we propose an algorithm that learns zero-suppressed binary decision diagrams (ZDDs) using membership and equivalence queries. If the target ZDD has $n$ nodes and the cardinality of the universe is $m$, our algorithm uses $n$ equivalence queries and at most $n(\lfloor \log m \rfloor + 4n)$ membership queries to learn the target ZDD.} }
Endnote
%0 Conference Paper %T An efficient query learning algorithm for zero-suppressed binary decision diagrams %A Hayato Mizumoto %A Shota Todoroki %A Diptarama %A Ryo Yoshinaka %A Ayumi Shinohara %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-mizumoto17a %I PMLR %P 360--371 %U https://proceedings.mlr.press/v76/mizumoto17a.html %V 76 %X A ZDD is a directed acyclic graph that represents a family of sets over a fixed universe set. In this paper, we propose an algorithm that learns zero-suppressed binary decision diagrams (ZDDs) using membership and equivalence queries. If the target ZDD has $n$ nodes and the cardinality of the universe is $m$, our algorithm uses $n$ equivalence queries and at most $n(\lfloor \log m \rfloor + 4n)$ membership queries to learn the target ZDD.
APA
Mizumoto, H., Todoroki, S., Diptarama, , Yoshinaka, R. & Shinohara, A.. (2017). An efficient query learning algorithm for zero-suppressed binary decision diagrams. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:360-371 Available from https://proceedings.mlr.press/v76/mizumoto17a.html.

Related Material