Efficient Quantum Agnostic Improper Learning of Decision Trees Sagnik Chatterjee1 Tharrmashastha SAPV1 and Debajyoti Bera12

2025-05-02 0 0 873.43KB 36 页 10玖币

侵权投诉

Eﬃcient Quantum Agnostic Improper Learning of

Decision Trees

Sagnik Chatterjee1, Tharrmashastha SAPV1, and Debajyoti Bera1,2

1Indraprashta Institute of Information Technology (IIIT-D), Delhi, India∗

2Centre for Quantum Technologies, IIIT-Delhi

Abstract

The agnostic setting is the hardest generalization of the PAC model since it is akin

to learning with adversarial noise. In this paper, we give a poly (n, t, 1

/ε) quantum

algorithm for learning size tdecision trees over n-bit inputs with uniform marginal

over instances, in the agnostic setting, without membership queries (MQ). This is the

ﬁrst algorithm (classical or quantum) for eﬃciently learning decision trees without MQ.

First, we construct a quantum agnostic weak learner by designing a quantum variant

of the classical Goldreich-Levin algorithm that works with strongly biased function

oracles. Next, we show how to quantize the agnostic boosting algorithm by Kalai and

Kanade (2009) to obtain the ﬁrst eﬃcient quantum agnostic boosting algorithm (that

has a polynomial speedup over existing adaptive quantum boosting algorithms). We

then use the quantum agnostic boosting algorithm to boost the weak quantum agnostic

learner constructed previously to obtain a quantum agnostic learner for decision trees.

Using the above framework, we also give quantum decision tree learning algorithms

without MQ in weaker noise models.

∗{sagnikc,tharrmashasthav,dbera}@iiitd.ac.in

arXiv:2210.00212v3 [quant-ph] 6 Mar 2024

Contents

1 Introduction 3

1.1 Our Contributions and Technical Overview . . . . . . . . . . . . . . . . . . . 5

1.1.1 Quantum agnostic boosting . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.2 Weak Quantum Agnostic Learner for Decision Trees . . . . . . . . . . 6

1.2 RelatedWork ................................... 7

2 Notation and Preliminaries 8

3 Quantum Agnostic Boosting 10

4 Quantum Decision Tree Learning without Membership Queries 12

4.1 The Adversarial Noise (Agnostic) setting . . . . . . . . . . . . . . . . . . . . 13

4.2 The Noiseless (Realizable) Setting . . . . . . . . . . . . . . . . . . . . . . . . 16

4.3 The Random Classiﬁcation Noise setting . . . . . . . . . . . . . . . . . . . . 16

5 Discussion 16

6 Acknowledgements 17

Appendix 20

7 The Kalai-Kanade Algorithm 21

7.1 Proof of Lemma 11 ................................ 23

8 Details of Quantum Agnostic Boosting Algorithm (Algorithm 1)24

9 Analysis of Algorithm 1 26

9.1 ProofofCorrectness ............................... 26

9.2 ComplexityAnalysis ............................... 28

10 Quantum Goldreich-Levin Algorithm 28

10.1 Proof of correctness of Algorithm 3:....................... 29

11 Quantum Decision Tree Learning: Agnostic Setting 33

11.1 Proofs of Agnostic Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

11.2 Proofs of Realizable Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

12 Discussion on Iwama, Raymond, and Yamashita [IRY05]36

1 Introduction

Eﬃciently learning decision trees is a central problem in algorithmic learning theory since

any Boolean function is learnable as a decision tree [Bsh93]. There has been a large body

of work (see Table 1) centered around providing theoretical guarantees for learning decision

trees under various generalizations and restrictions of the Probably Approximately Correct

(PAC) model model introduced by Valiant [Val84].

The original PAC model model [Val84] is in the noiseless setting where the learning

algorithm is trained on a training set S={(xi, yi)}i∈[m]consisting of mtuples of instances

xi∈Fn

2and their corresponding binary labels yi. In the random classiﬁcation noise (RCN)

setting, the learning algorithm is trained on a set S′where each label yiin Sis ﬂipped with

a uniform probability p. In the agnostic setting (adversarial noise), each label in Sis ﬂipped

with some probability which is dependent on the example.

There are two types of decision tree learning algorithms: proper learning algorithms,

where the output is a decision tree, and improper learning algorithms, where the output

hypothesis is not necessarily required to be a decision tree. Proper learning of decision

trees, even in the noiseless setting, is known to be computationally hard [KST23], and all

the eﬃcient improper learning algorithms (for diﬀerent noise models) are designed to use

Membership Query (MQ) oracles (see Table 1).

Downsides of MQ oracles. A MQ oracle allows a learning algorithm to fetch the label

of any desired instance in the input space, even among the ones absent in the training set.

In the famous experiment by Baum and Lang [BL92], the MQ oracle was queried by the

learning algorithm on instances outside the domain of the labeling function. This makes

MQ oracles diﬃcult to implement and is probably one reason that makes them unattractive

to the applied machine learning community [BF02;AFK13], which brings us to the main

question tackled in this work.

Question: Does there exist a polynomial time (im-

proper) decision tree learning algorithm without

membership queries?

Quantum as the silver bullet. In practice, machine learning algorithms use data in

the training set to learn a hypothesis. This setup can be modeled as having query access

to a random example oracle where we sample training points according to the uniform

distribution. Theoretically, it is known that the PAC+MQ model is strictly stronger than

the PAC model model with only random examples [Ang88;Bsh93;Fel06;Val84]. Similar

to the random example oracle, access to a uniform superposition over the training set is an

equivalent and a natural requirement in quantum computing. This was ﬁrst demonstrated

by Bshouty and Jackson [BJ98] where they introduced the notion of the Quantum PAC

model model. Many subsequent works (see Atıcı and Servedio [AS07], Arunachalam and

Maity [AM20], Izdebski and Wolf [IW20], and Chatterjee, Bhatia, Singh Chani, and Bera

[Cha+23]) have been designed in the realizable quantum PAC model model with access

to a uniform superposition over the training examples. It is not known whether random

Table 1: Comparing diﬀerent algorithms for learning size-tdecision trees on n-bit Boolean functions. Note

here that tand 1

/εcan be as large as poly(n), which renders the running time of many of the algorithms

given below as super-polynomial. Our quantum algorithms are strictly polynomial in all parameters while

being the only algorithm to work in the agnostic and realizable settings and not use membership queries

(denoted by MQ). Here we note that the number of training samples mrequired for learning is poly(n). QC

denotes query complexity.

Work Setting Type Noise Set-

ting

MQ Runtime

EH 1989 Classical Proper Realizable No poly nlog t,1

/ε

KM 1991 Classical Improper Realizable Yes poly (n, t, 1

/ε)

LMN 1993 Classical Proper Realizable No poly nlog (t/ε)

MR 2002 Classical Proper Agnostic No poly nlog (t/ε)

GKK 2008

Classical Improper Agnostic Yes poly (n, t, 1

/ε)

KK 2009

Feldman 2009

BLT 2020 Classical Proper Agnostic No poly nlog t,1

/ε

This Work

Quantum Improper Realizable No poly (n, t, 1

/ε)QC:

O1/ε2

Quantum Improper Agnostic No poly (n, t, 1

/ε)QC:

On2/ε3

examples are suﬃcient for any (quantum or classical) agnostic learning task, which was

another motivation behind this work.

The query models used in our quantum algorithm for improperly learning decision trees

were proposed by Bshouty and Jackson [BJ98] and Arunachalam and Wolf [AW17]; and are

generalizations of the random example oracle where the learning algorithm has query access

to a superposition over all instances in the domain. A detailed description of the Quantum

Example (Qex) and Quantum Agnostic Example (Qaex) oracles is given in Section 2. While

the random example query model is weaker than the Qex model, the MQ model is stronger

than the Qex model w.r.t. uniform marginal distribution [BJ98].

1.1 Our Contributions and Technical Overview

The main contribution of this work is a quantum polynomial time algorithm for improp-

erly learning decision trees without MQ in the agnostic setting (and hence, in weaker noise

settings). The importance is twofold.

1. To our knowledge, ours is the ﬁrst quantum algorithm for decision tree learning (real-

izable or agnostic, with or without MQ).

2. Our algorithm is also the only known eﬃcient agnostic PAC learning algorithm for

decision trees (classical or quantum) without MQ 1.

We state a simpliﬁed version of our main result now.

Theorem 1. Given mtraining examples, there exists a quantum algorithm for learning size-t

decision trees in the agnostic setting without MQ in poly (m, t, 1

/ε)time.

Here we note that the number of training samples mrequired for learning is polynomial

w.r.t. to nwhere the decision trees correspond to n-bit Boolean functions. Following earlier

work (see Section 1.2), we also assume a uniform marginal distribution over the instances.

In Table 1, we compare our decision tree learning algorithm against existing decision tree

learning algorithms. Our algorithm (see Fig. 1) follows from the existence of

•an eﬃcient quantum agnostic boosting algorithm (see Section 3), and

•an eﬃcient weak quantum agnostic learner for decision trees (see Section 4).

1.1.1 Quantum agnostic boosting

Quantum boosting algorithms for the realizable setting have been shown to exist (see Sec-

tion 1.2), but their existence in the agnostic setting was an open question [IW20]. The chal-

lenge in such algorithms is precisely estimating the margins under the presence of instance-

dependent noise. Our idea was to quantize the Kalai and Kanade [KK09] (KK) algorithm

whose use of relabeling let us avoid using the amplitude ampliﬁcation subroutine (a staple in

the previous quantum boosting algorithms) explicitly, thereby removing a signiﬁcant source

of error. In Section 3, we show that given a weak quantum agnostic learner Awith an associ-

ated hypothesis class Cand a set of mtraining examples, we can construct a poly (m, 1

/ε) time

quantum boosting algorithm to produce a hypothesis that is εclose to the best hypothesis

in C.

1Our result subsumes the classical realizable learning algorithm for monotone decision trees without MQ

by O’Donnell and Servedio [OS07].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

EfficientQuantumAgnosticImproperLearningofDecisionTreesSagnikChatterjee1,TharrmashasthaSAPV1,andDebajyotiBera1,21IndraprashtaInstituteofInformationTechnology(IIIT-D),Delhi,India∗2CentreforQuantumTechnologies,IIIT-DelhiAbstractTheagnosticsettingisthehardestgeneralizationofthePACmodelsinceitisakintole...

展开>> 收起<<

Efficient Quantum Agnostic Improper Learning of Decision Trees Sagnik Chatterjee1 Tharrmashastha SAPV1 and Debajyoti Bera12.pdf

共36页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Efficient Quantum Agnostic Improper Learning of Decision Trees Sagnik Chatterjee1 Tharrmashastha SAPV1 and Debajyoti Bera12

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: