Your concept reminds me of the idea of Kolmogorov complexity - the length of the shortest program to output a string is the complexity of the string. Yet, spheres are highly regular. In an abstract manner, you try to generalize Kolmogorov's idea to a space, merging adjacent regions. But adjacency depends on the way you define geometry in that space. Many regularizing approaches in machine learning therefore calibrate concept complexity with cross validating approaches.

Thank you Matthias. The question is, does this method of sphere set covering influenced by the size of training set or it is not resistant when we increase the amount of training example in a certain Concept?

You should consider the complexity of the concept is related to the complexity of the domain to which it belongs. The same machine learning algorithm has different behaviors depending depending on the complexity of the domain on which is intended to teach concepts.

Interesting question. But can you give some examples of concepts you want to learn and how are those concept represented in your input space? Because concepts can be understood in different ways ...

Thanks Ramon, but can you provide me little more information? for example some references about domain complexity and the relation between domain complexity and concept complexity. I appreciate it

Dear Xavier, this is a general question. I don't have any specific dataset in my hand to with now. Actually, I am trying to find a general idea to develop a pure computational theory i.e. suppose we want to work with 1000 different datasets presenting 1000 different concepts in different scopes. Now the question is,if there is a unique criteria or method measuring the complexity of this concepts?

Dear Pouya, I understand that you want a general measure. But I do not understand what you have in mind when you talk about concept. Is it like a category, a cluster, an analogy, or something else? Are your concepts independent (i.e. the intersection of all concepts is void)?

Xavier, I'm not sure what you exactly mean but let me describe it in this way using a classical example : suppose we want to train a machine to recognize whether the situation is good for playing tennis or not and it depends on many weather factor, playing tennis with all relevant factors are the concept that we want to train the machine with. In the other case, suppose a machine want to determine if a cat is in an image or not. depending on presented dataset, the attributes are different in quality and quantity. Here, being a cat in an image with its all presented attributes are the concept.

Please, see: http://www.unla.edu.ar/sistemas/gisi/GISI/papers/DySES-2012_Garcia-Martinez_&_Lopez-Nocera.pdf

Pouya, I think I see better what you mean now. Are you familiar with V. Vapnik theories of learning? You may found some hints for your question. But, to my point of view, the hardness of training a concept is higly dependent on the data you have! If all the cats are in bright images, and all images that have no cats are dark, then it is an easy task that a simple perceptron can do.

thanks Ramon and Xavier