Quality of machine translation of natural language is determined by computing a sequence kernel that provides a measure of similarity between a first sequence of symbols representing a machine translation in a target natural language and a second sequence of symbols representing a reference translation in the target natural language. The measure of similarity takes into account the existence of non-contiguous subsequences shared by the first sequence of symbols and the second sequence of symbols. When the similarity measure does not meet an acceptable threshold level, the translation model of the machine translator may be adjusted to improve subsequent translations performed by the machine translator.