We focus on the prediction of structured outputs. A classical example is sequence labeling with applications in speech, vision, natural language or biology. Beyond sequences, the prediction of structured data, like trees, lattices or graphs also occurs in many domains. Structured prediction is usually considered as an extension of multi-class classification. It is considered as a challenging problem since the size of the output space increases drastically with the number of potential dependencies between output variables. Several methods have been recently proposed in the ML community in order to overcome this complexity and the domain is still largely open. We will provide a review of these methods and discuss there potential and limitations. These different ideas will be illustrated with Natural language processing and text mining applications.