Kittur, Hummel and Holyoak (2004) showed that people have great difficulty learning relation-based categories with a probabilistic (i.e., family resemblance) structure. We investigated three interventions hypothesized to facilitate learning family-resemblance based relational categories: Naming the relevant relations, providing a hint to look for a family resemblance structure, and changing the description of the task from learning about categories to choosing the winning object in each stimulus, which was predicted to encourage subjects to form an invariant higher-order relation. We crossed these variables orthogonally in a factorial design. Of the three, the change in task description had by far the greatest impact on subjects ability to learn probabilistic relation-based categories. For subjects in the category learning task, naming the relations and the no single relation clue both improved performance individually, but in combination, they substantially impaired learning. These results suggest that the best way to learn a probabilistic relation-based category is to discover a higher-order relation that remains invariant over the categorys exemplars.