Traditional noun phrase coreference resolution systems represent features only of pairs of noun phrases. In this paper, we propose a machine learning method that enables features over sets of noun phrases, resulting in a first-order probabilistic model for coreference. We outline a set of approximations that make this approach practical, and apply our method to the ACE coreference dataset, achieving an 11% error reduction over a comparable method that only considers features of pairs of noun phrases. This result demonstrates an example of how a powerful representation language can be incorporated into a probabilistic model and be scaled efficiently.