We present an approach to structure prediction based upon a reduction to binary classification. This binary classification task typically involves many examples and many features. We propose a learning method for these large-scale classification tasks that is simple, accurate, and efficient. We apply this approach large-scale structure prediction problems in NLP: parsing and machine translation.