This article is within the scope of WikiProject Robotics, a collaborative effort to improve the coverage of
Robotics on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.RoboticsWikipedia:WikiProject RoboticsTemplate:WikiProject RoboticsRobotics articles
This page was previously known as "shatter"; it has a new title.
Shattering is an important concept and warrents its own article; I shall continue to improve the article. —Preceding
unsigned comment added by
MathStatWoman (
talk •
contribs)
move Information
ok, let's move it. I have more to add about "shattering", and I want to do it before I forget what it was I wanted to add. Thanks for the help. —Preceding
unsigned comment added by
MathStatWoman (
talk •
contribs)
You claim that the class of all convex sets in the plane shatters every finite set. I find that hard to believe. Imagine a regular hexagon, whose vertices we shall denote 1,2,3,4,5,6, and its center, 0. Now take the sets A = {0,1,2,3,4,5,6}, and G = {1,3,5}. Any convex set which includes 1,3, and 5 will also include the center 0, and thus cannot equal . Perhaps I misunderstood some concept?
You give a rather lengthy paragraph about the
cumulative distribution function. I find that off the topic, since most people who will read your article already know that concept, and those requiring additional information can easily follow the link. I don't think anything more than a quick reminder is in order. Perhaps you should consider adding your examples to that article instead.
The primary contributor to this article, MathStatWoman, is rather new and might not be used to checking her watchlist. If she does not reply in a while, you could I guess alert her on her talk page to take a look here.
Oleg Alexandrov (
talk)
17:11, 24 December 2005 (UTC)reply
Re: 3) -- see
Voronoi diagram. You can draw convex polygons around 1,3,5 which do not contain 0. The way I understood the example was: "The class of all Voronai diagrams shatters all finite point-sets on the plane."
linas22:54, 25 December 2005 (UTC)reply
Never mind, Meni is right, the definition is worded as if s must be a singleton, in which case there seems to be no way to shatter the hexagon example. So the article definition is confusing.
linas23:02, 25 December 2005 (UTC)reply
Also, the definition of "shattering coefficient" doesn't seem to make sense if s must be a singleton; so this is confusing as well.
linas23:19, 25 December 2005 (UTC)reply
Quite frankly, I have no idea what you meant. Why must s be a singleton? And what does the
Voronoi diagram have to do with the problem (I know you deleted it, but apparently, not for the right reasons)? A convex set that includes 1,3 and 5 (the vertices of an equilateral triangle) must also include 3*, the midpoint of 1 and 5, and therefore include 0, which is on the segment connecting 3 and 3*. Remember that I intentionally introduced a regular hexagon (otherwise "center" would be ambiguous).
Please clarify your ideas, for misunderstandings are the roots of a sterile discussion.
Sigh. This is all getting cloudier, which means I'm not enjoying this.
1) Look at the article one Voronoi diagrams. One way to shatter your set {0..6} is to draw small convex sets around each of your points 0..6. To me, this means that there are seven that are required to shatter your example, yet the article speaks of s in the singular, not the plural. Maybe C should be described as the class of sets of sets?
2) I agree with you that if s is to be only one set, there is no way to choose a convex s that contains 1,3,5 but does not contain 0. (although a star-shaped s would do the trick).
3) The talk about 3* confused me, I don't know what 3* is, and it just muddied things.
About empirical processes: this is a huge area of study within the theory of probability. I have just begun an article on the topic. It stands alone, not part of other articles on empirical studies of various types. Correction made about convex sets; it was about sampling on the unit disc; thanks for the comments on that. Also the richness of a collection is important, hence the reference to shattering coefficient.
MathStatWoman23:28, 11 January 2006 (UTC)reply
I was beginning to worry you have lost all interest in
Wikipedia :). I'll write my replies in correspondence with my questions above:
What about this question?
Very well.
I still don't get it. Perhaps you meant the
unit circle?
If mentioning the importance of richness related to this question, then still, this is not a reason to include here a lengthy description of a known concept. That's what the article on
cumulative distribution function is for.
Second, since we all have real jobs or school or both, we all understand that we each can spend only a bit of time now and then on Wikipedia. Hence, partial answers.
About question 1: Probabilists use the notation for G is a subset of A, proper subset or entire set. This is in all the literature, but for example, you could refer to Klartag and Mendelson, Empirical Processes and Random Projections, or Wellner, Empirical Processses: Theoory and Applications, 2005, as well as a multitude of other articles and texts in probability theory.
Since shattering had its birth in probability theory, especially empirical processes, I use the probabilists' notation.
My field is probability theory, especially empirical processes, order statistics, and distributions, so for this reason too, I use notation of probabilists.
More responses to your questions when I have time.
I would be very very interested in seeing answers to Meni's hexagon example, as well as a clarification of the discussion that followed. (I think these are far more important to clarify than the subset/proper set question).
linas18:05, 15 January 2006 (UTC)reply
Oh, ah, um, OK; it seems I had previously misread something, and was confused by that; I seem to no longer be confused. (except I don't understand why I was confused in the first place). Thanks.
linas22:04, 16 January 2006 (UTC)reply
1. About subsets, we probabilists do indeed use the notation that I used, but if it bothers set theorists, and I change it, then the notation will annoy the probabilists. Sigh... we cannot satisfy everyone... I really want to leave it as it is, but if Wikipedia demands otherwise, let me know, and we'll discuss it further.
2. We settled that, right?
3. More to come on empirical process article as I get time between work, research, school.
Thanks to everyone who entitled that article well and re-directed it properly.
4. About discussing distribution functions (df's): [incidentally, probabilists, when doing serious research, do not use the teminology "cumulative" df's(cdf's), but just df (see all the peer-reviewed papers in Ann.Prob,. J.Appl Prob, and texts such as Loeve's on the grad level); cdf is used for undergrads, though.] Anyway, in the article on shattering, we re-cast df's in terms of collections of sets because this is a very important example: we want to study sets on the real line of the form { v : v ≤ x }, that is, sets of values that are less than or equal to x. Let C be the collection of all such sets on the real line, that is, of the form , { v : v ≤ x } for all real numbers x. This is not done in the article on df's because it does not belong there; it belongs in the article on shattering. It really is vital to discuss it in the article shattering. It is an example that appears in many peer-reviewed articles on shattering.
Does anyone know exactly what the etymology of this term is? It makes some intuitive sense, I guess, but a concrete reference would be nice!
Reb42 (
talk)
23:54, 7 April 2009 (UTC)reply
In original paper by V&C in 1969, I believe they used the word "разбиение", which could be loosely translated as partitioning/ breaking down into parts. In their English version (published in 1971) Authors used the word "inducing", which is not quite correct as a translation. Steele claimed that he first used the word "shattering" in his PhD dissertation in 1975. (
Igny (
talk)
03:14, 8 April 2009 (UTC))reply
Interestingly enough, the modern translation of the term back into Russian is "коэффициент разнообразия", loosely translated as "variety/diversity coefficient" (
Igny (
talk)
03:59, 8 April 2009 (UTC))reply