Talk:Shattered set

new

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

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)

I performed the move. One should not use cut and paste in the future to move a page. Oleg Alexandrov (talk) 22:34, 16 December 2005 (UTC)

Some questions

Hi,

I have no prior knowledge of the concept of shattering, but having read the article I encountered several issues:

1. The definitions at the top relate to the condition $G\subset A$, where $G\subseteq A$ seems to make much more sense to me ($\subset$ usually means partial-and-not-equal).
2. Perhaps the broken link empirical processes could be made to link to one of the several articles relating to empirical methods?
3. 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 $s\cap A$ cannot equal $G$. Perhaps I misunderstood some concept?
4. 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.

I hope I have been helpful.

--Meni Rosenfeld 09:13, 24 December 2005 (UTC)

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)

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." linas 22:54, 25 December 2005 (UTC)

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. linas 23:02, 25 December 2005 (UTC)

Also, the definition of "shattering coefficient" doesn't seem to make sense if s must be a singleton; so this is confusing as well. linas 23:19, 25 December 2005 (UTC)

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.

--Meni Rosenfeld 06:42, 26 December 2005 (UTC)

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 $s\in C$ 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.

4) We really need MathStatWoman to deal with this, I know nothing further than what I wrote here. linas 04:34, 29 December 2005 (UTC)

response from me

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. MathStatWoman 23:28, 11 January 2006 (UTC)

I was beginning to worry you have lost all interest in Wikipedia :). I'll write my replies in correspondence with my questions above:

1. What about this question?
2. Very well.
3. I still don't get it. Perhaps you meant the unit circle?
4. 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.

--Meni Rosenfeld 06:28, 12 January 2006 (UTC)

Answers to Meni Rosenfeld, Part I

First, thank you for your questions.

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 $G\subset A$ 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.

Cheers! MathStatWoman 21:01, 13 January 2006 (UTC)

Thanks for your reply.

The problem is that the common convention (in most areas of mathematics, and consequently, in WP) is to use $\subseteq$ for this relation. Having every article in WP use a different convention would be just too confusing. See my question regarding this issue and (hopefully) pending answer. --Meni Rosenfeld 14:18, 15 January 2006 (UTC)

Answers to Meni Rosenfeld, Part II

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). linas 18:05, 15 January 2006 (UTC)

MathStatWoman has already answered that one - She meant every set in the unit circle, and not in the plane. She promises to answer all questions when she has the time. --Meni Rosenfeld 18:17, 15 January 2006 (UTC)

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. linas 22:04, 16 January 2006 (UTC)

Maybe this will clear things up. We discussed the issue in my talk page, so you probably missed it. --Meni Rosenfeld 07:57, 17 January 2006 (UTC)

Answers to Meni Rosenfeld, Part III

I answered on Meni Rosenfeld's user talk page. MathStatWoman 13:28, 16 January 2006 (UTC)

Copied the following answers from my talk page: --Meni Rosenfeld 19:45, 16 January 2006 (UTC)

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.

I have put up a discussion about subset notation in Wikipedia talk:WikiProject Mathematics. About cdf, I will now delete the part which I don't think belongs in this article so you can see what I mean. If you don't think this is right, discuss the issue here. --Meni Rosenfeld 19:45, 16 January 2006 (UTC)

Change

Your change seems ok. MathStatWoman 21:48, 16 January 2006 (UTC)

Then we should probably leave it this way. If you like the blackjack example, try to find a proper place to put it in cumulative distribution function. --Meni Rosenfeld 08:00, 17 January 2006 (UTC)

VC class

I think, we need a more comprehensive article on Vapnik-Chervonenkis classes with examples. (Igny 16:04, 20 June 2006 (UTC))

"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)

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))

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))

Disambiguation needed

This page needs to be moved so that disambiguation from other meanings is possible. For example, shattering is important in agriculture. Would "Shattering (machine learning)" be an appropriate title? Nadiatalent (talk) 17:07, 16 October 2011 (UTC)

For want of other suggestions, moved as above. Nadiatalent (talk) 16:45, 3 November 2011 (UTC)