The category learning literature has focused primarily on how category knowledge develops under fully supervised or unsupervised learning (i.e., cases where labels/feedback are provided on all or none of the learning trials, respectively). However, it would seem most natural categories are likely to be acquired neither exclusively through supervision, nor in the absence thereof, but rather through a combination of supervised and unsupervised learning episodes (i.e., via semi-supervised learning). Yet, little is understood about semi-supervised learning. Evidence for its existence as a phenomenon has been limited primarily to unidimensional categories—suggesting the phenomenon does not scale—and the factors that affect whether it occurs are poorly understood. Guided by a novel distinction between improvement-based and change-based semi-supervised learning effects, we argue across four experiments that semi-supervised learning can scale beyond simple category structures and identify two novel factors that affect the degree to which unsupervised exposures alter representations attained through supervision. In Experiments 1–3 we explore improvement-based semi-supervised learning using multidimensional relational categories, whose basis of membership remains fixed but surface characteristics vary between supervised and unsupervised exposures. We vary degree of superficial similarity between supervised and unsupervised exposures, as well as whether supervised learning occurs under paired or sequential presentation. We find some evidence that high degrees of superficial similarity and paired presentations lead to improved category knowledge. In Experiment 4, we explore change-based semi-supervised learning using two-dimensional feature-based categories, where the underlying basis of membership is suggested to change between supervised and unsupervised exposures. Further, we provide a preliminary investigation of two prominent process models in their ability to fit the behavioral data. We find some evidence of change-based semi-supervised learning when those changes occur across two dimensions and that, preliminarily, both models hold promise for explaining behavioral data. These findings: (1) suggest that semi-supervised learning effects scale to more complex categories; (2) suggest that superficial similarity between supervised and unsupervised exposures, as well as type of supervised learning format, play a critical role in whether effects accrue; and, (3) highlight a need for additional research extending process models to the problem of semi-supervised learning.