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 = {Hayato Mizumoto and Shota Todoroki and Diptarama and Ryo Yoshinaka and Ayumi Shinohara}, pages = {360--371}, year = {2017}, editor = {Steve Hanneke and Lev Reyzin}, volume = {76}, series = {Proceedings of Machine Learning Research}, address = {Kyoto University, Kyoto, Japan}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/mizumoto17a/mizumoto17a.pdf}, url = {http://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 %J Proceedings of Machine Learning Research %P 360--371 %U http://proceedings.mlr.press %V 76 %W PMLR %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 PMLR 76:360-371

Related Material