×

Non-adaptive learning of a hidden hypergraph. (English) Zbl 1388.68146

Summary: We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential time or have non-optimal query complexity. We give the first polynomial time non-adaptive learning algorithm for learning hypergraphs that asks an almost optimal number of queries.

MSC:

68Q32 Computational learning theory
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angluin, D., Queries and concept learning, Mach. Learn., 2, 4, 319-342 (1987) · Zbl 1470.68050
[2] Alon, N.; Asodi, V., Learning a hidden subgraph, SIAM J. Discrete Math., 18, 4, 697-712 (2005) · Zbl 1078.68111
[3] Abdi, A. Z.; Lower, N. H. Bshouty, Bounds for cover-free families (2015), CoRR
[4] Alon, N.; Beigel, R.; Kasif, S.; Rudich, S.; Sudakov, B., Learning a hidden matching, SIAM J. Comput., 33, 2, 487-501 (2004) · Zbl 1055.05142
[5] Abasi, H.; Bshouty, N. H.; Mazzawi, H., On exact learning monotone DNF from membership queries, (ALT 2014 (2014)), 111-124, CoRR · Zbl 1432.68202
[6] Angluin, D.; Chen, J., Learning a hidden hypergraph, J. Mach. Learn. Res., 7, 2215-2236 (2006) · Zbl 1222.68091
[7] Angluin, D.; Chen, J., Learning a hidden graph using \(O(\log n)\) queries per edge, J. Comput. System Sci., 74, 4, 546-556 (2008) · Zbl 1147.68033
[8] Alon, N.; Moshkovitz, D.; Safra, S., Algorithmic construction of sets for \(k\)-restrictions, ACM Trans. Algorithms, 2, 2, 153-177 (2006) · Zbl 1321.68445
[9] Bshouty, N. H., Exact learning from membership queries. Some techniques, results and new directions, (ALT 2013 (2013)), 33-52 · Zbl 1405.68150
[10] Bshouty, N. H., Linear time constructions of some \(d\)-restriction problems, (CIAC 2015 (2015)), 74-88 (2014), CoRR · Zbl 1459.68150
[11] Bshouty, N. H., Testers and their applications, (Electronic Colloquium on Computational Complexity (ECCC), vol. 19 (2012)). (ITCS 2014 (2014)), 327-352 · Zbl 1364.68359
[12] Bshouty, N. H.; Gabizon, A., Almost optimal cover-free families (2015), CoRR · Zbl 1487.68259
[13] Beigel, R.; Alon, N.; Kasif, S.; Serkan Apaydin, M.; Fortnow, L., An optimal procedure for gap closing in whole genome shotgun sequencing, (RECOMB 2001 (2001)), 22-30
[14] Bshouty, N. H.; Goldman, S. A.; Hancock, T. R.; Matar, S., Asking questions to minimize errors, J. Comput. System Sci., 52, 2, 268-286 (1996) · Zbl 0851.68094
[15] Bouvel, M.; Grebinski, V.; Kucherov, G., Combinatorial search on graphs motivated by bioinformatics applications: a brief survey, (WG 2005 (2005)), 16-27 · Zbl 1126.68514
[16] Bshouty, N. H.; Hellerstein, L., Attribute-efficient learning in query and mistake bound models, (COLT 1996 (1996)), 235-243
[17] Chang, H.; Chen, H.-B.; Fu, H.-L.; Shi, C.-H., Reconstruction of hidden graphs and threshold group testing, J. Comb. Optim., 22, 2, 270-281 (2011) · Zbl 1232.05135
[18] Chang, H.; Fu, H-L.; Shih, C-H., Learning a hidden graph, Optim. Lett. (2014) · Zbl 1303.90113
[19] Chen, H-B.; Hwang, F. K., A survey on nonadaptive group testing algorithms through the angle of decoding, J. Comb. Optim., 15, 1, 49-59 (2008) · Zbl 1182.94063
[20] Chin, F. Y.L.; Leung, H. C.M.; Yiu, S.-M., Non-adaptive complex group testing with multiple positive sets, Theoret. Comput. Sci., 505, 11-18 (2013) · Zbl 1416.68184
[21] Du, D. Z.; Hwang, F., Pooling Design and Nonadaptive Group Testing: Important Tools for DNA Sequencing (2006), World Scientific: World Scientific Singapore · Zbl 1284.62009
[22] D’yachkov, A.; Vilenkin, P.; Macula, A.; Torney, D., Families of finite sets in which no intersection of \(ℓ\) sets is covered by the union of \(s\) others, J. Combin. Theory Ser. A, 99, 195-218 (2002) · Zbl 1020.94027
[23] Kautz, W. H.; Singleton, R. C., Nonrandom binary superimposed codes, IEEE Trans. Inform. Theory, 10, 4, 363-377 (1964) · Zbl 0133.12402
[24] Fomin, F. V.; Lokshtanov, D.; Saurabh, S., Efficient computation of representative sets with applications in parameterized and exact algorithms, (SODA 2014 (2014)), 142-151 · Zbl 1421.68077
[25] Gao, H.; Hwang, F. K.; Thai, M. T.; Wu, W.; Znati, T., Construction of d(H)-disjunct matrix for group testing in hypergraphs, J. Comb. Optim., 12, 3, 297-301 (2006) · Zbl 1115.92019
[26] Grebinski, V.; Kucherov, G., Reconstructing a Hamiltonian cycle by querying the graph: application to DNA physical mapping, Discrete Appl. Math., 88, 1-3, 147-165 (1998) · Zbl 0936.68107
[27] Macula, A. J.; Popyack, L. J., A group testing method for finding patterns in data, Discrete Appl. Math., 144, 149-157 (2004) · Zbl 1078.68756
[28] Macula, A. J.; Rykov, V. V.; Yekhanin, S., Trivial two-stage group testing for complexes using almost disjunct matrices, Discrete Appl. Math., 137, 1, 97-107 (2004) · Zbl 1039.05045
[29] Ma, X.; Wei, R., On bounds of cover-free families, Des. Codes Cryptogr., 32, 303-321 (2004) · Zbl 1046.05019
[30] Reyzin, L.; Srivastava, N., Learning and verifying graphs using queries with a focus on edge counting, (ALT 2007 (2007)), 285-297 · Zbl 1142.68404
[31] Stinson, D. R.; Wei, R.; Zhu, L., Some new bounds for cover free families, J. Combin. Theory Ser. A, 90, 1, 224-234 (2000) · Zbl 0948.05055
[32] Stinson, D. R.; Wei, R.; Zhu, L., New constructions for perfect hash families and related structures using combinatorial designs and codes, J. Combin. Des., 8, 3, 189-200 (2000) · Zbl 0956.68159
[33] Torney, D. C., Sets pooling designs, Ann. Comb., 3, 95-101 (1999) · Zbl 0932.05018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.