Kernel Engineering for Fast and Easy Design of Natural Language Applications

Previous work on the use of Machine Learning for Computational Linguistics has shown that most of the design effort is devoted to feature engineering. Indeed, the latter requires expertise, intuition and deep knowledge about the target problem to convert linguistic objects into attribute-value representations. Kernel Methods (KM) are powerful techniques, which can simplify data modeling by defining abstract representations and implicit feature spaces. More in particular, KM allow for: (a) directly using a similarity function between instances in learning algorithms, thus avoiding explicit feature design; and (b) implicitly defining huge feature spaces, e.g. structures can be represented in the substructure space. 
 
In this tutorial, practical recipes to successfully use KM for target language applications will be presented: first, after an introduction to Support Vector Machines (explained from an application viewpoint), KM theory will be explained in a way that useful practical methods can be derived. Second, basic kernels, such as linear, polynomial, sequence and tree kernels will be presented, by focusing on the implementation, accuracy and efficiency perspectives. KMapplication to typical natural language tasks, e.g. text categorization, question and answer classification, semantic role labeling, textual entailment and so on, will be shown. The aim is to provide practical procedures for the selection and exploitation of the right kernel for the target task. Third, the SVM-Light-TK toolkit, which encodes several kernels in SVMs, will be illustrated along with the associated data structures and its practical use in NL tasks. Finally, the tutorial will illustrate how innovative and effective kernels can be engineered starting from basic kernels and using systematic data transformation. Such know-how allows for a very fast and accurate design of applications even if the underlying language phenomena and properties are still not very well understood, e.g. Arabic SRL or relation extraction between pairs of text fragments.


Linear Classifier
The equation of a hyperplane is is the vector representing the classifying example is the gradient of the hyperplane The classification function is Mapping vectors in a space where they are linearly separable

A mapping example
Given two masses m 1 and m 2 , one is constrained Apply a force f a to the mass m 1 Experiments Features m 1 , m 2 and f a We want to learn a classifier that tells when a mass m 1 will get far away from m 2 The gravitational law is not linear so we need to change space

Novikoff's Theorem
Let S be a non-trivial training-set and let Let us suppose there is a vector and with γ > 0. Then the maximum number of errors of the perceptron is: In each step of perceptron only training data is added with a certain weight So the classification function Note that data only appears in the scalar product

Dual Representation for Learning
as well as the updating function The learning rate only affects the re-scaling of the hyperplane, it does not affect the algorithm, so we can fix We can rewrite the classification function as As well as the updating function

Support Vector Machines
The margin is equal to 2 k w Support Vector Machines

Support Vector Machines
Var 1 Var 2 There is a scale for which k=1.
The problem transforms in:

Optimization Problem
Optimal Hyperplane:

Subject to
The dual problem is simpler

Dual Transformation
To solve the dual problem we need to evaluate: Given the Lagrangian associated with our problem Let us impose the derivatives to 0, with respect to w 

Dual Transformation (cont'd)
and wrt b Then we substituted them in the objective function

Khun-Tucker Theorem
Necessary and sufficient conditions to optimality

Properties coming from constraints
Lagrange constraints: Karush-Kuhn-Tucker constraints Support Vectors have not null To evaluate b, we can apply the following equation

Soft Margin SVMs
slack variables are added Some errors are allowed but they should penalize the objective function i ξ

Soft Margin SVMs
The new constraints are The objective function penalizes the incorrect classified examples C is the trade-off between margin and the error

Dual formulation
By deriving wrt

Soft Margin Support Vector Machines
The algorithm tries to keep ξ i low and maximize the margin NB: The number of error is not directly minimized (NP-complete problem); the distances from the hyperplane are minimized If C→∞, the solution tends to the one of the hard-margin algorithm If C increases the number of error decreases. When C tends to infinite the number of errors must be 0, i.e. the hard-margin formulation

Kernels in Support Vector Machines
In Soft Margin SVMs we maximize: By using kernel functions we rewrite the problem as:

Kernel Function Definition
Kernels are the product of mapping functions such as

The Kernel Gram Matrix
With KM-based learning, the sole information used from the training data set is the Kernel Gram Matrix If the kernel is valid, K is symmetric definite-positive .

Valid Kernels cont'd
If the matrix is positive semi-definite then we can find a mapping φ implementing the kernel function

Mercer's Theorem (finite space)
Let us consider for Takagi factorization of a complex-symmetric matrix, where: Λ is the diagonal matrix of the eigenvalues λ t of K are the eigenvectors, i.e. the columns of V Let us assume lambda values non-negative Therefore , which implies that K is a kernel function

Mercer's Theorem (necessary conditions)
Suppose we have negative eigenvalues λ s and eigenvectors the following point has the following norm: this contradicts the geometry of the space.

Is it a valid kernel?
It may not be a kernel so we can use M´·M

Feature Conjunction (polynomial Kernel)
The initial vectors are mapped in a higher space More expressive, as encodes

Stock+Market vs. Downtown+Market features
We can smartly compute the scalar product as

Lexical Semantic Kernel [CoNLL 2005]
The document similarity is the SK function: where s is any similarity function between words, e.g. WordNet [Basili et al.,2005] similarity or LSA [Cristianini et al., 2002] Good results when training data is small

String Kernel
Given two strings, the number of matches between their substrings is evaluated

Evaluating DP2
Evaluate the weight of the string of size p in case a character will be matched This is done by multiplying the double summation by the number of substrings of size p-1 Evaluating the Predictive DP on strings of size 2 (second row) Let's consider substrings of size 2 and suppose that: we have matched the first "a" we will match the next character that we will add to the two strings We compute the weights of matches above at different string positions with some not-yet known character "?" If the match occurs immediately after "a" the weight will be λ 1+1 x λ 1+1 = λ 4 and we store just λ 2 in the DP entry in ["a","a"]

Evaluating the DP wrt different positions (second row)
If the match for "gatta" occurs after "t" the weight will be λ 1+2 (x λ 2 = λ 5 ) since the substring for it will be with "a☐?" We write such prediction in the entry ["a","t"] Same rationale for a match after the second "t": we have the substring "a☐☐?" (matching with "a?" from "catta") for a weight of λ 3+1 (x λ 2 )

Evaluating the DP wrt different positions (third row)
If the match occurs after "t" of "cata", the weight will be λ 2+1 (x λ 2 = λ 5 ) since it will be with the string "a☐?", with a weight of λ 3 If the match occurs after "t" of both "gatta" and "cata", there are two ways to compose substring of size two: "a☐?" with weight λ 4 or "t?" with weight λ 2 ⇒ the total is λ 2 +λ 4
Between "gatta" and "cata" is λ 7 + λ 5 + λ 4 , i.e the matches of "a☐☐a", "t☐a", "ta" with "a☐a" and "ta"   Fast Evaluation of STK [Moschitti, EACL 2006] where P(n x ) and P(n z ) are the production rules used at nodes n x and n z €

Algorithm Observations
We order the production rules used in T x and T z , at loading time

Observations
We order the production rules used in T x and T z , at loading time If we relax such constraint we get more general substructures [Kashima and Koyanagi, 2002]

Weighting Problems
Both matched pairs give the same contribution.
Gap based weighting is needed.
A novel efficient evaluation has to be defined

Partial Tree Kernel
By adding two decay factors we obtain:

Efficient Evaluation (1)
In [Taylor and Cristianini, 2004 book], sequence kernels with weighted gaps are factorized with respect to different subsequence sizes.
We treat children as sequences and apply the same theory D p

Efficient Evaluation (2)
The complexity of finding the subsequences is Therefore the overall complexity is where ρ is the maximum branching factor (p = ρ)

Tree forests, vector sets
The new SVM-Light-TK toolkit will be released asap

Predicate Argument Classification
In an event: target words describe relation among different entities the participants are often seen as predicate's arguments.

Example:
Paul gives a talk in Rome

Predicate Argument Classification
In an event: target words describe relation among different entities the participants are often seen as predicate's arguments. Example:

Predicate-Argument Feature Representation
Given a sentence, a predicate p:

Bags of words (BOW) and POS-tags (POS)
To save time, apply STK to these trees:

Re-ranking Framework
Local classifier generates the most likely set of hypotheses.
These are used to build annotation pairs, .
positive instances if h i more correct than h j , A binary classifier decides if h i is more accurate than h j .
Each candidate annotation h i is described by a structural representation € h i , h j

Re-ranking framework
Local Model

Syntactic Parsing Re-ranking
Pairs of parse trees (Collins and Duffy, 2002) Re-ranking concept labeling [

Conclusions
Kernel methods and SVMs are useful tools to design language applications Kernel design still requires some level of expertise Engineering approaches to tree kernels Basic Combinations Canonical Mappings, e.g.

Node Marking
Merging of kernels in more complex kernels Easy modeling produces state-of-the-art accuracy in many tasks, RTE, SRL, QC, NER, RE SVM-Light-TK efficient tool to use them

Future (on going work)
Once we have found the right kernel, are we satisfied?
What about knowing the most relevant features?
Can we speed up learning/classification at real-application scenario level?
The answer is reverse kernel engineering: [Pighin&Moschitti, CoNLL2009, EMNLP2009, CoNLL2010] Mine the most relevant fragments according to SVMs gradient Use the linear space Software for reverse kernel engineering available in the next months Thank you