Home | Publications | CS Home

Occam's Razor Just Got Sharper

---

Saher Esmeir and Shaul Markovitch. Occam's Razor Just Got Sharper. In Proceedings of The Twentieth International Joint Conference for Artificial Intelligence, 768-773 Hyderabad, India, 2007.

---

Abstract

Occam's razor is the principle that, given two hypotheses consistent with the observed data, the simpler one should be preferred. Many machine learning algorithms follow this principle and search for a small hypothesis within the version space. The principle has been the subject of a heated debate with theoretical and empirical arguments both for and against it. Earlier empirical studies lacked sufficient coverage to resolve the debate. In this work we provide convincing empirical evidence for Occam's razor in the context of decision tree induction. By applying a variety of sophisticated sampling techniques, our methodology samples the version space for many real-world domains and tests the correlation between the size of a tree and its accuracy. We show that indeed a smaller tree is likely to be more accurate, and that this correlation is statistically significant across most domains.

---

Keywords: Decision Trees

---

Secondary Keywords:

---

Online version:

---

Bibtex entry:

 @inproceedings{Esmeir:2007:ORJ,
  Author = {Saher Esmeir and Shaul Markovitch},
  Title = {Occam's Razor Just Got Sharper},
  Year = {2007},
  Booktitle = {Proceedings of The Twentieth International Joint Conference for Artificial Intelligence},
  Pages = {768--773},
  Address = {Hyderabad, India},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Esmeir-Markovitch-ijcai2007.pdf},
  Keywords = {Decision Trees},
  Secondary-keywords = {},
  Abstract = {
    Occam's razor is the principle that, given two hypotheses
    consistent with the observed data, the simpler one should be
    preferred. Many machine learning algorithms follow this principle
    and search for a small hypothesis within the version space. The
    principle has been the subject of a heated debate with theoretical
    and empirical arguments both for and against it. Earlier empirical
    studies lacked sufficient coverage to resolve the debate. In this
    work we provide convincing empirical evidence for Occam's razor in
    the context of decision tree induction. By applying a variety of
    sophisticated sampling techniques, our methodology samples the
    version space for many real-world domains and tests the
    correlation between the size of a tree and its accuracy. We show
    that indeed a smaller tree is likely to be more accurate, and that
    this correlation is statistically significant across most domains.
  }

  }