Inferring structured predictions based on correlated covariates remains a central problem in many fields, including NLP, computer vision, and computational biology. Popular paradigms for training structured input/output models include the maximum (conditional) likelihood estimation, which leads to the well-known CRF; and the max-margin learning, which leads to the structured SVM (a.k.a. M3N), each enjoys some advantages, as well as weaknesses. In this talk, I present a new general framework called Maximum Entropy Discrimination Markov Networks (MEDN), which integrates the margin-based and likelihood-based approaches and combines and extends their merits. This new learning paradigm naturally facilitates integration of the generative and discriminative principles under a unified framework, and the basic strategies can be generalized to learn arbitrary graphical models, such as the generative Bayesian networks or models with structured hidden variables. I will discuss a number of theoretical properties of this model, and show applications of MEDN to learning fully supervised structured i/o model, max-margin structured i/o models with hidden variables, and a max-margin LDA model for jointly discovering discriminative latent topic representations and predicting document label/score of text documents, with compelling performance in each case.