Each rule of the parse derivation was assigned a score according to a log-linear factor.
each rule R = ( with features over the rule and derivation so far φ(R), subject to parameters θ, is given a probability: Naïvely, this parsing algorithm gives us a complexity of O(n 3 k 2 ), where n is the length of the sentence, and k is the size of the beam.