In this section we described a discriminative online learning approach to sentence compression, the core of which is a decoding algorithm that searches the entire space of compressions.
let the score of a compression y for a sentence x as we are going to factor this score using a first-order Markov assumption on the words in the compressed sentence Finally, we define the score function to be the dot product between a high dimensional feature representation and a corresponding weight vector Note that this factorization will allow us to define features over two adjacent words in the compression as well as the words in-between that were dropped from the original sentence to create the compression.