Can someone please explain to me (with normal language) - how is VC dimension related to data mining (frequent itemset mining - PAC learning). (incl. how we define range space as it's written in Matteo Riondate and Eli Upfal (Brown University) as it's really hard for me to understand what they mean)

More precisely I'm interested in the definition of range space and how it used to represent the VC dimension (you could say I'm looking for a conceptual presentation of what they are using to define it in that context)

Here's how it is defined:

Definition 11. Let D be a dataset of transactions that are subsets of a ground set I. We
define S = (X, R) to be a range space associated with D such that:
1. X = D is the set of transactions in the dataset.
2. R = {TD(W) | W ⊆ I} is a family of sets of transactions such that for each
itemset W ⊆ I, the set TD(W) = {τ ∈ D | W ⊆ τ} of all transactions containing
W is an element of R.
  • 1
    $\begingroup$ As much as I wish I could answer a question on my own paper, this looks like homework to me. $\endgroup$
    – Matteo
    Mar 14 '18 at 11:28
  • $\begingroup$ @Matteo thank you for your reply. No it’s not for my homework. My homework is to understand your paper, and I currently cannot understand the definition of range space intuitively $\endgroup$ Mar 14 '18 at 13:46
  • $\begingroup$ A range space is just a collection of sets. I don't understand what additional intuition one can give about what "a collection of sets" is. Maybe there is a more specific question, for example about how the define the range space associated with a dataset in their frequent itemset mining paper? $\endgroup$ Mar 14 '18 at 14:28
  • $\begingroup$ @SashoNikolov of course, in the context of frequent itemset mining(as it's explained as: (X,R) where X is the universe of items(conceptually) and R is a family of subsets, X is quite clear, but R is not so much in that context $\endgroup$ Mar 14 '18 at 16:16
  • $\begingroup$ $X$ is not the universe of items. As clearly written in the definition that you cite, $X$ is the set of transactions in the dataset. $\endgroup$
    – Matteo
    Mar 14 '18 at 17:17

A range space is just a pair $(X,\mathcal{R})$ where $X$ is a finite or infinite set and a $\mathcal{R}$ is a finite or infinite collection of subsets of $X$ (the elements of $\mathcal{R}$ are called "ranges").

Note that a range space is not used to "represent" the VC-dimension (whatever meaning of "represent" you are using). Rather, the VC-dimension is a property of the range space.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.