Adaptive Exact Learning of Decision Trees from Membership Queries

被引：0

作者：

Bshouty, Nader H. ^{[1
]}

Haddad-Zaknoon, Catherine A. ^{[1
]}

机构：

[1] Technion, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

ALGORITHMIC LEARNING THEORY, VOL 98 | 2019年 / 98卷

关键词：

Decision Trees; Membership Queries; Adaptive Learning; Exact Learning; EFFICIENT; ALGORITHM; GRAPH; DNF;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper we study the adaptive learnability of decision trees of depth at most d from membership queries. This has many applications in automated scientific discovery such as drugs development and software update problem. Feldman solves the problem in a randomized polynomial time algorithm that asks (O) over tilde (2(2d)) log n queries. Kushilevitz-Mansour solve it in a deterministic polynomial time algorithm that asks 2(18d+o(d)) log n queries. We improve the query complexity of both algorithms. We give a randomized polynomial time algorithm that asks (O) over tilde (2(2d))+ 2(d) log n queries and a deterministic polynomial time algorithm that asks 2(5.83d) + 2(2d+o(d)) log n queries.

引用

页数：28

共 29 条

[1] Abasi H, 2014, LECT NOTES ARTIF INT, V8776, P111, DOI 10.1007/978-3-319-11662-4_9
[2] Alon N, 2002, ANN IEEE SYMP FOUND, P197, DOI 10.1109/SFCS.2002.1181943
[3] A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM
ALON, N
BABAI, L
ITAI, A
[J]. JOURNAL OF ALGORITHMS, 1986, 7 (04) : 567 - 583
[4] Angluin D., 1988, Machine Learning, V2, P319, DOI 10.1023/A:1022821128753
[5] Learning a hidden graph using O(log n) queries per edge
Angluin, Dana
Chen, Jiang
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2008, 74 (04) : 546 - 556
[6] Ben Basat R, 2018, Arxiv, DOI arXiv:1804.08902
[7] Biglieri E., 2007, Multiple Access Channels: Theory and Practice
[8] LEARNING IN THE PRESENCE OF FINITELY OR INFINITELY MANY IRRELEVANT ATTRIBUTES
BLUM, A
HELLERSTEIN, L
LITTLESTONE, N
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 50 (01) : 32 - 40
[9] Bshouty Nader, 2014, P 5 C INN THEOR COMP, P327
[10] Exact learning from an honest teacher that answers membership queries
Bshouty, Nader H.
[J]. THEORETICAL COMPUTER SCIENCE, 2018, 733 : 4 - 43

← 1 2 3 →