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
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.
