Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Sauer's Lemma

Expand Messages
  • Lance
    The recent post Discovering the Discovered reminded me of one of my favorite combinatorial lemma known as Sauer s Lemma. Sauer s Lemma roughly states that if a
    Message 1 of 1 , Feb 7, 2006
      The recent post Discovering the Discovered reminded me of one of my favorite combinatorial lemma known as Sauer's Lemma.

      Sauer's Lemma roughly states that if a collection of sets has VC dimension bounded by d then any set of n elements can only be split nd ways. More precisely

      Fix a collections Φ of subsets of U such that for all x1,…,xk in U,
      |{S∩{x1,…,xk} | S∈Φ}| < 2k
      then for all x1,…,xn in U,
      |{S∩{x1,…,xn} | S∈Φ}| ≤ O(nk-1)
      This lemma has many important applications, most notably a famous result of Blumer, Ehrenfeucht, Haussler and Warmuth showing that if you don't care about computation costs, then one can PAC learn a concept class iff the VC dimension of that class is bounded.

      Why is Sauer's lemma connected to Discovering the Discovered. According to Till Tantau,

      Vapnik and Chervonenkis appear to have been the first to discover it. They published it in 1968 in Russian and 1971 in English. Sauer, whose paper was published in 1972, claims that Erdös was the first to have conjectured the lemma. Subsequently, Sauer's Lemma has been rediscovered by Clarke, Owings, and Spriggs, and later again by Beigel.


      --
      Posted by Lance to Computational Complexity at 2/07/2006 07:24:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.