It's just a workshop, but still: first acceptance. Yay.
This post's theme word: legerdemain, "a slight of hand" or "a display of skill." Very apropros for imposter syndrome.
Tuesday, May 4, 2010
Tuesday, April 20, 2010
VC-dimension?
Do you know anything about computing VC-dimension? Or about the Sauer-Shelah lemma?
Both Wikipedia and the CC blog state the lemma in a way that I do not understand. Namely, they define the VC-dimension as, at some point, determined by the cardinality of the intersection of the set {x1,…,xk} with some other set. And both sources upper bound this number by 2k, which seems absurd: how can it possibly be more than k? We have indexed the set; it has exactly k elements; set intersection is a strictly nonincreasing function in terms of set size.
It also seems unlikely to me that both these sources would have typos. So I must be misunderstanding something.
If you know something about VC-dimension, the Sauer-Shelah lemma, or related combinatorics, please send me an email and I shall grill you with my questions (seasoned with confusion... and paprika, if you like).
Update: I figured it out with the help of these lecture notes. It was an issue of misunderstood notation. (My bad, as usual.)
This post's theme word: curtilage, "an area of land encompassing a dwelling and its surrounding yard, considered as enclosed whether fenced or not." In my present frame of mind, it relates to set theory.
Both Wikipedia and the CC blog state the lemma in a way that I do not understand. Namely, they define the VC-dimension as, at some point, determined by the cardinality of the intersection of the set {x1,…,xk} with some other set. And both sources upper bound this number by 2k, which seems absurd: how can it possibly be more than k? We have indexed the set; it has exactly k elements; set intersection is a strictly nonincreasing function in terms of set size.
It also seems unlikely to me that both these sources would have typos. So I must be misunderstanding something.
If you know something about VC-dimension, the Sauer-Shelah lemma, or related combinatorics, please send me an email and I shall grill you with my questions (seasoned with confusion... and paprika, if you like).
Update: I figured it out with the help of these lecture notes. It was an issue of misunderstood notation. (My bad, as usual.)
This post's theme word: curtilage, "an area of land encompassing a dwelling and its surrounding yard, considered as enclosed whether fenced or not." In my present frame of mind, it relates to set theory.
Subscribe to:
Posts (Atom)