I'm studying Probably approximately correct learning, and I don't understand what an Instance Space and a Concept is.

I have see that wikipedia https://en.wikipedia.org/wiki/Probably_approximately_correct_learning provides various examples, but it's still rather an abstract concept.

Could you provide me with an intuitive definition and some tangible examples?


This kind of language is typically associated within a field of math called computational learning theory (clt). CLT is inherently abstract since it's trying to derive general observation about unknown target functions. That's why you get generic terms like instance space and concepts. Broadly speaking an instance space is typically just the domain of X (your sample population) and an instance of that space is a particular x with various features. For example, X may be the set of all people and an instance of x will be an individual person who is 30 female and medium height etc.

The concept space on the other hand is subset of the domain X such that X -> {0, 1} or in other words a subset that maps X via Boolean function as either 0 or 1. For example, Our concept space can be people who walk to work. Every person X can either say yes they walk to work (and thus x -> 1) or no (x -> 0).

If this is still too abstract for you, I would recommend stepping back and building a more foundation footing on basic machine learning before you start trying to study them as broad generic objects.

| improve this answer | |
  • $\begingroup$ Thank you, your explanation clarifies things a lot. Just one remark, if I say that a concept space is a subset of X, of all x sharing the same y is correct? $\endgroup$ – Tommaso Bendinelli Dec 21 '18 at 17:48
  • $\begingroup$ So for instance given the instance space of Fruits, with features shape color and so on. Can we consider all Bananas a concept space? $\endgroup$ – Tommaso Bendinelli Dec 21 '18 at 17:52
  • 1
    $\begingroup$ Your first comment, I wouldn't be inclined to phrase it that y, but it doesn't look wrong just inexact. As for comment two, that works. It could also be more abstract than that or a combination of features. $\endgroup$ – Tophat Dec 21 '18 at 19:08
  • $\begingroup$ Okey, So the concept space is a subset of X that can be categorised such that there is a Boolean function that returns 1 for all the element in the concept space and 0 for the others. It's rather a convoluted sentence, but please let me know if you think it's correct :) $\endgroup$ – Tommaso Bendinelli Dec 22 '18 at 12:27

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.