Document Open Access Logo

Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph

Author Hasan Abasi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.3.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Hasan Abasi
  • Department of Computer Science, Technion, Haifa, 32000, Israel

Cite As Get BibTex

Hasan Abasi. Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.3

Abstract

We consider the problem of learning the hypergraph using edge-detecting queries. In this model, the learner is allowed to query whether a set of vertices includes an edge from a hidden hypergraph. Except a few, all previous algorithms assume that a query's result is always correct. In this paper we study the problem of learning a hypergraph where alpha -fraction of the queries are incorrect. The main contribution of this paper is generalizing the well-known structure CFF (Cover Free Family) to be Dense (we will call it DCFF - Dense Cover Free Family) while presenting three different constructions for DCFF. Later, we use these constructions wisely to give a polynomial time non-adaptive learning algorithm for a hypergraph problem with at most alpha-fracion incorrect queries. The hypergraph problem is also known as both monotone DNF learning problem, and complexes group testing problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Boolean function learning
Keywords
  • Error Tolerant Algorithm
  • Hidden Hypergraph
  • Montone DNF
  • Group Testing
  • Non-Adaptive Learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hasan Abasi, Nader H. Bshouty, and Hanna Mazzawi. On exact learning monotone DNF from membership queries. In Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, editors, Algorithmic Learning Theory - 25th International Conference, ALT 2014, Bled, Slovenia, October 8-10, 2014. Proceedings, volume 8776 of Lecture Notes in Computer Science, pages 111-124. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-11662-4_9.
  2. Hasan Abasi, Nader H. Bshouty, and Hanna Mazzawi. Non-adaptive learning of a hidden hypergraph. Theor. Comput. Sci., 716:15-27, 2018. URL: http://dx.doi.org/10.1016/j.tcs.2017.11.019.
  3. Dana Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1987. URL: http://dx.doi.org/10.1007/BF00116828.
  4. Dana Angluin and Jiang Chen. Learning a hidden hypergraph. Journal of Machine Learning Research, 7:2215-2236, 2006. URL: http://www.jmlr.org/papers/v7/angluin06a.html.
  5. Dana Angluin and Jiang Chen. Learning a hidden graph using o(logn) queries per edge. J. Comput. Syst. Sci., 74(4):546-556, 2008. URL: http://dx.doi.org/10.1016/j.jcss.2007.06.006.
  6. Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, and Lance Fortnow. An optimal procedure for gap closing in whole genome shotgun sequencing. In Thomas Lengauer, editor, Proceedings of the Fifth Annual International Conference on Computational Biology, RECOMB 2001, Montréal, Québec, Canada, April 22-25, 2001, pages 22-30. ACM, 2001. URL: http://dx.doi.org/10.1145/369133.369152.
  7. Mathilde Bouvel, Vladimir Grebinski, and Gregory Kucherov. Combinatorial search on graphs motivated by bioinformatics applications: A brief survey. In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers, volume 3787 of Lecture Notes in Computer Science, pages 16-27. Springer, 2005. URL: http://dx.doi.org/10.1007/11604686_2.
  8. Nader H. Bshouty. Linear time constructions of some d -restriction problems. In Vangelis Th. Paschos and Peter Widmayer, editors, Algorithms and Complexity - 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings, volume 9079 of Lecture Notes in Computer Science, pages 74-88. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-18173-8_5.
  9. Nader H. Bshouty. Derandomizing chernoff bound with union bound with an application to dollarkdollar-wise independent sets. CoRR, abs/1608.01568, 2016. URL: http://arxiv.org/abs/1608.01568.
  10. Nader H. Bshouty and Ariel Gabizon. Almost optimal cover-free families. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings, volume 10236 of Lecture Notes in Computer Science, pages 140-151, 2017. URL: http://dx.doi.org/10.1007/978-3-319-57586-5_13.
  11. Hong-Bin Chen, Hung-Lin Fu, and Frank K. Hwang. An upper bound of the number of tests in pooling designs for the error-tolerant complex model. Optimization Letters, 2(3):425-431, 2008. URL: http://dx.doi.org/10.1007/s11590-007-0070-5.
  12. Hong-Bin Chen and Frank K. Hwang. A survey on nonadaptive group testing algorithms through the angle of decoding. J. Comb. Optim., 15(1):49-59, 2008. URL: http://dx.doi.org/10.1007/s10878-007-9083-3.
  13. Dingzhu Du, Frank K Hwang, and Frank Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 2000. Google Scholar
  14. Vladimir Grebinski and Gregory Kucherov. Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discrete Applied Mathematics, 88(1-3):147-165, 1998. URL: http://dx.doi.org/10.1016/S0166-218X(98)00070-5.
  15. Hwang Frank Kwang-ming and Du Ding-zhu. Pooling designs and nonadaptive group testing: important tools for DNA sequencing, volume 18. World Scientific, 2006. Google Scholar
  16. Weiwei Lang, Yuexuan Wang, James Yu, Suogang Gao, and Weili Wu. Error-tolerant trivial two-stage group testing for complexes using almost separable and almost disjunct matrices. Discrete Math., Alg. and Appl., 1(2):235-252, 2009. URL: http://dx.doi.org/10.1142/S1793830909000191.
  17. Anthony J. Macula and Leonard J. Popyack. A group testing method for finding patterns in data. Discrete Applied Mathematics, 144(1-2):149-157, 2004. URL: http://dx.doi.org/10.1016/j.dam.2003.07.009.
  18. Douglas R. Stinson and Ruizhong Wei. Generalized cover-free families. Discrete Mathematics, 279(1-3):463-477, 2004. URL: http://dx.doi.org/10.1016/S0012-365X(03)00287-5.
  19. Douglas R. Stinson, Ruizhong Wei, and Lie Zhu. Some new bounds for cover-free families. J. Comb. Theory, Ser. A, 90(1):224-234, 2000. URL: http://dx.doi.org/10.1006/jcta.1999.3036.
  20. David C Torney. Sets pooling designs. Annals of Combinatorics, 3(1):95-101, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact