ML Anthology

Research Note on Decision Lists

Ron Kohavi, Scott Benson
MLJ 1993 pp. 131-134
doi:10.1007/BF00993105 /mlj/1993/kohavi1993mlj-research/

Abstract

In his article “Learning Decision Lists,” Rivest proves that ( k -DNF ∪ k -CNF) is a proper subset of k -DL. The proof is based on the following incorrect claim: ... if a function f has a prime implicant of size t , then f has no k -DNF representation if k < t . In this note, we show a counterexample to the claim and then prove a stronger theorem, from which Rivest's theorem follows as a corollary.

PDF MLJ Semantic Scholar

Cite

Text

Kohavi and Benson. "Research Note on Decision Lists." Machine Learning, 1993. doi:10.1007/BF00993105

Markdown

[Kohavi and Benson. "Research Note on Decision Lists." Machine Learning, 1993.](https://mlanthology.org/mlj/1993/kohavi1993mlj-research/) doi:10.1007/BF00993105

BibTeX

@article{kohavi1993mlj-research,
  title     = {{Research Note on Decision Lists}},
  author    = {Kohavi, Ron and Benson, Scott},
  journal   = {Machine Learning},
  year      = {1993},
  pages     = {131-134},
  doi       = {10.1007/BF00993105},
  volume    = {13},
  url       = {https://mlanthology.org/mlj/1993/kohavi1993mlj-research/}
}