Efficient polynomial mapping of data for use with linear support vector machines

  • US 8,463,591 B1
  • Filed: 07/29/2010
  • Issued: 06/11/2013
  • Est. Priority Date: 07/31/2009
  • Status: Active Grant
  • ×
    • Pin
First Claim
Patent Images

1. A computer-implemented method, comprising:

  • receiving, in a computing system comprising one or more computers, original training data including a plurality of training feature vectors and a respective decision for each training feature vector, each training feature vector representing a parse state of a parser, each element of each training feature vector indicating a presence or absence of a feature of the parse state, the parser constructing a dependency graph for a sentence having words and punctuation, the parser input comprising tokens corresponding to the words and punctuation of the sentence;

    generating, by the computing system, for each training feature vector, a condensed representation of a mapped vector corresponding to a degree-d polynomial mapping of the training feature vector, the mapping defining each component of the mapped vector as either a single element of the training feature vector or a product of up to d elements of the training feature vector, the condensed representation of the mapped vector including an index for each non-zero component of the mapped vector, each index indicating a position in a weight vector of a weight for the corresponding non-zero mapped vector component; and

    using a linear support vector machine to train a classifier on the condensed representations, the linear support vector machine configured to receive as training data the condensed representations and decisions for the training feature vectors corresponding to the condensed representations, and determine the weights in the weight vector from the condensed training data, where the classifier corresponds to a given parsing transition and uses the weight vector that was trained for the given parsing transition to generate a score for the given parsing transition, where the score for the given parsing transition is used to determine whether to perform the given parsing transition in building a dependency graph, the dependency graph representing syntactic modifiers for words in the sentence through labeled directed edges.

View all claims

    Thank you for your feedback