When subjects are confronted with new stimuli and learn to categorize them according to a rule, they have to segment the stimuli into relevant features for categorization. A central question is whether children aged four or six who were able to discover the rule in a simplified version would generalize it to a “complex” version of the relevant features (i.e., in which there is more background noise) that they would be unable to learn before thirteen with no pre-training. Conditions promoting generalization from the simple version to the complex were also investigated. Two conditions were compared: relearning with or without feedback. Results showed that children aged 6 generalized the “simple” version of the target concept to more complex versions of the same concept with feedback in the generalization phase but less well without feedback. Children aged four did not generalize quite well in both conditions.