On Learning Ring-Sum-Expansions

Fischer, Paul; Simon, Hans Ulrich

doi:10.1016/B978-1-55860-146-8.50013-8

On Learning Ring-Sum-Expansions

Paul Fischer, Hans Ulrich Simon

COLT 1990 pp. 130-143

doi:10.1016/B978-1-55860-146-8.50013-8 /colt/1990/fischer1990colt-learning/

Abstract

Abstract We study the problem of learning ring-sum-expansions from examples. Ring-sum-expansions (RSE) are representations of Boolean functions over the base Λ,⊕, 1, which reflect arithmetic operations in GF(2). k-RSE is the class of ring-sum-expansions containing only monomials of length at most k. k-term-RSE is the class of ring-sum-expansions having at most k monomials. We show that k-RSE, k ≤ 1, is learnable while k-term-RSE, k ≤ 2, is not learnable if RP ≠ NP. We also prove that unrestricted RSE is not heuristically learnable by k-term-RSE, if RP ≠ NP. Without using a complexity theoretical hypothesis on can show that k-RSE, k ≤ 1, and k-term-RSE, k ≤ 2 cannot be learned from positive (negative) examples alone. However, if we suspend the restriction that the hypothesis which is output by the learning algorithm is also a k-RSE, then k-RSE is learnable from positive (negative) examples only. One can also show that k-RSE is learnable by k-RSE using only positive (negative) examples if one makes restrictions on the distributions of the examples. Moreover, it is proved that 2-term-RSE is learnable by a conjunction of a 2-CNF and a 1-DNF. Finally we present learning (on-line prediction) algorithms for k-RSE which are optimal with respect to the sample size (worstcase mistake bound).

COLT Semantic Scholar

Cite

Text

Fischer and Simon. "On Learning Ring-Sum-Expansions." Annual Conference on Computational Learning Theory, 1990. doi:10.1016/B978-1-55860-146-8.50013-8

Markdown

[Fischer and Simon. "On Learning Ring-Sum-Expansions." Annual Conference on Computational Learning Theory, 1990.](https://mlanthology.org/colt/1990/fischer1990colt-learning/) doi:10.1016/B978-1-55860-146-8.50013-8

BibTeX

@inproceedings{fischer1990colt-learning,
  title     = {{On Learning Ring-Sum-Expansions}},
  author    = {Fischer, Paul and Simon, Hans Ulrich},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1990},
  pages     = {130-143},
  doi       = {10.1016/B978-1-55860-146-8.50013-8},
  url       = {https://mlanthology.org/colt/1990/fischer1990colt-learning/}
}