A module m function takes value 0 when the weighted sum of the input variables is congruent to 0 mod m and takes value 1 otherwise. In this work we show a polynomial time algorithm for learning with equivalence queries the class of conjunctions of module p functions on n variables, for any fixed prime p. The result is also extended to learning with bounded adversarial noise

Bertoni, A., Cesa Bianchi, N., Fiorino, G. (1995). Efficient learning with equivalence queries of conjunctions of modulo functions. INFORMATION PROCESSING LETTERS, 56(1), 15-17 [10.1016/0020-0190(95)00126-W].

Efficient learning with equivalence queries of conjunctions of modulo functions

Fiorino, GG
1995

Abstract

A module m function takes value 0 when the weighted sum of the input variables is congruent to 0 mod m and takes value 1 otherwise. In this work we show a polynomial time algorithm for learning with equivalence queries the class of conjunctions of module p functions on n variables, for any fixed prime p. The result is also extended to learning with bounded adversarial noise
Articolo in rivista - Articolo scientifico
learning with queries; modulo functions; analysis of algorithms
English
15
17
3
Bertoni, A., Cesa Bianchi, N., Fiorino, G. (1995). Efficient learning with equivalence queries of conjunctions of modulo functions. INFORMATION PROCESSING LETTERS, 56(1), 15-17 [10.1016/0020-0190(95)00126-W].
Bertoni, A; Cesa Bianchi, N; Fiorino, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/8193
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
Social impact