Many realistic visual recognition tasks are “open” in the sense that the number and nature of the categories to be learned are not initially known, and there is no closed set of training images available to the system. We argue that open recognition tasks require incremental learning methods, and feature sets that are capable of expressing distinctions at any level of specificity or generality. We describe progress toward such a system that is based on an infinite combinatorial feature space. Feature primitives can be composed into increasingly complex and specific compound features. Distinctive features are learned incrementally, and are incorporated into dynamically updated Bayesian network classifiers. Experimental results illustrate the applicability and potential of our approach.