On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle | Zendy

Nader H. Bshouty | Zendy; Ehab Wattad | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle

Author(s) -

Nader H. Bshouty,

Ehab Wattad

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-46649-5

DOI - 10.1007/11894841_8

Subject(s) - oracle , equivalence (formal languages) , random oracle , counterexample , computer science , constant (computer programming) , time complexity , algorithm , discrete mathematics , mathematics , programming language , encryption , public key cryptography , operating system

We study exact learning of halfspaces from equivalence queries. The algorithm uses an oracle RCH that returns a random consistent hypothesis to the counterexamples received from the equivalence query oracle. We use the RCH oracle to give a new polynomial time algorithm for exact learning halfspaces from majority of halfspaces and show that its query complexity is less (by some constant factor) than the best known algorithm that learns halfspaces from halfspaces.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research