nltk/nltk — Issue #168: SVMlight integration
Author: alexrudnick
Created: 2012-01-17 06:27:37+00:00
State: open

Please describe what your program code does, including information about any data formats, literature references, etc. Please use the following header format. Note that, by uploading your code, you are giving permission for it to be distributed with NLTK under the terms of the Apache License.

This code allows the use of a support vector machine via NLTK's standard classifier interface. The SVM implementation is T. Joachims' SVMlight, in C, and wrapped by W. Cauchois' Python bindings.

SVMlight - http://svmlight.joachims.org/
Thorsten Joachims, Learning to Classify Text Using Support Vector Machines. Dissertation, Kluwer, 2002.

PySVMlight - https://bitbucket.org/wcauchois/pysvmlight
Bill Cauchois

The following changes are made to the NLTK 2.0.1rc1 downloadable:

* Add a new file, nltk/classify/svm.py (also available at http://www.dcs.shef.ac.uk/~leon/svm.py)
* Modify nltk/classify/__init__.py as follows:

@@ -88,6 +88,7 @@
from util import *
from naivebayes import *
from decisiontree import *
+from svm import *
from rte_classify import *

__all__ = [
@@ -95,7 +96,7 @@
'ClassifierI', 'MultiClassifierI',

# Classifiers
- 'NaiveBayesClassifier', 'DecisionTreeClassifier', 'WekaClassifier',
+ 'NaiveBayesClassifier', 'DecisionTreeClassifier', 'WekaClassifier', 'SvmClassifier',

# Utility functions. Note that accuracy() is intentionally
# omitted -- it should be accessed as nltk.classify.accuracy();

Further, one will need to install PySVMlight. As it is not (yet!) included as a package in many operating systems, the easiest way is likely to be to download it from https://bitbucket.org/wcauchois/pysvmlight/get/tip.zip. This includes SVMlight, so there's just one thing to download. Unpack, enter the top-level resultant directory, and run "python setup.py build install" (just as with Numpy and MatPlotLib). As far as I know, this will only work on systems that have GCC installed - I don't have a Mac to test on, I could try on Win7, and it works seamlessly in Ubuntu 10.04 LTS (i686 / 32bit) and 10.10 (x64). You might need root to do the install.

Hope this module helps - it works for my purposes and I'll need it for a while yet. It runs as fast as SVMlight. I'm happy to maintain/bugfix for a few years, within reason.

All the best,

Leon Derczynski

# Natural Language Toolkit: BRIEF STATEMENT ABOUT FUNCTIONALITY
#
# Copyright (C) 2001-2011 NLTK Project
# Author: Leon Derczynski <leon@dcs.shef.ac.uk>
#
# URL: <http://www.nltk.org/>
# For license information, see LICENSE.TXT

"""
A classifier based on a support vector machine. This code uses Thorsten Joachims'
SVM^light implementation (http://svmlight.joachims.org/), wrapped using
PySVMLight (https://bitbucket.org/wcauchois/pysvmlight). The default settings are to
train a linear classification kernel, though through minor modification, full SVMlight
capabilities should be accessible if needed. Only binary classification is possible at present.
"""

from nltk.probability import *

from api import *

#
# Interface to Support Vector Machine
#

try:
import svmlight
except:
raise Exception('PySVMlight was not successfully imported. You can install it from https://bitbucket.org/wcauchois/pysvmlight or via instructions in the NLTK documentation.')

"""
create a boolean feature name for the SVM from a feature/value pair, that'll take on a 1.0 value if the original feature:value is asserted.
"""
def featurename(feature, value):
"""
@param feature: a string denoting a feature name
@param value: the value of the feature
"""
return '|'.join([feature, type(value).__name__, str(value)])

"""
convert a set of NLTK classifier features to SVMlight format
"""
def map_features_to_svm(features, svmfeatureindex):
"""
@param features: a dict of features in the format {'feature':value}
@param svmfeatureindex: a mapping from feature:value pairs to integer SVMlight feature labels
"""
instancefeatures = []
# svmlight supports sparse feature sets and so we simply omit features that we don't include
for k,v in features.iteritems():
# each feature is represented as an (int, float) tuple where the int is the SVMlight feature label and the float is the value; as we either have or have not a feature, this is 1.0
# this does not support scalar features - rather, each value that a feature may take on is a discrete independent label
# use 1.0 as the feature value to specify the presence of a feature:value couple
svmfeaturename = featurename(k, v)
if svmfeaturename not in svmfeatureindex.keys():
# skip over feature:value pairs that were not in the training data and so not included in our mappings
continue
instancefeatures.append( (svmfeatureindex[svmfeaturename], 1.0) )
return instancefeatures

"""
Converts a whole instance (including label) from NLTK to SVMlight format
"""
def map_instance_to_svm(instance, labelmapping, svmfeatureindex):
"""
@param instance: an NLTK format instance, which is in the tuple format (dict(), label), where the dict contains feature:value pairs, and the label signifies the target attribute's value for this instance (e.g. its class)
@param labelmapping: a previously-defined dict mapping from text labels in the NLTK instance format to SVMlight labels of either +1 or -1
@svmfeatureindex: a mapping from feature:value pairs to integer SVMlight feature labels
"""
(features, label) = instance
instancefeatures = map_features_to_svm(features, svmfeatureindex)
return (labelmapping[label], instancefeatures)

class SvmClassifier(ClassifierI):
"""
A Support Vector Machine classifier. To explain briefly, support vector machines (SVM) treat each feature as a dimension, and position features in n-dimensional feature space.
An optimal hyperplane is then determined that best divides feature space into classes, and future instances classified based on which side of the hyperplane they lie on,
and their proximity to it.

This implementation is for a binary SVM - that is, only two classes are supported. You may achieve perform classification with more classes by training an SVM per class and then picking
a best option for new instances given results from each binary class-SVM.
"""

def __init__(self, labels, labelmapping, svmfeatures, model=None):
"""
@param labels: a list of text labels for classes
@param labelmapping: a mapping from labels to SVM classes (-1,+1)
@param svmfeatures: a list of svm features, where the index is the integer feature number and the value an feature/value pair
@param model: the model generated by svmlight.learn()
"""
self._labels = labels
self._model = model
self._labelmapping = labelmapping
self._svmfeatures = svmfeatures
# _svmfeatureindex is the inverse of svmfeatures, allowing us to find an SVM feature name (int) given a feature/value
self._svmfeatureindex = dict(zip(svmfeatures, range(len(svmfeatures))))
self._verbose = False

def labels(self):
"""
Return the list of class labels.
"""
return self._labels

def svm_label_name(self, label):
"""
searches values of _labelmapping to resolve +1 or -1 to a string
@param label: the string label to look up
"""
labelname = [k for k, v in self._labelmapping.iteritems() if v == label][0]
return labelname

def resolve_prediction(self, prediction):
"""
resolve a float (in this case, probably from svmlight.learn().classify()) to either -1 or +1, and then look up the label for that class in _labelmapping, and return the text label
@param prediction: a signed float describing classifier confidence
"""
classification = cmp(prediction, 0)
return self.svm_label_name(classification)

def _get_svm_classification(self, featureset):
"""
given a set of features, classify them with our trained model and return a signed float
@param featureset: a dict of feature/value pairs in NLTK format, representing a single instance
"""
instance_to_classify = (0, map_features_to_svm(featureset, self._svmfeatureindex))
if self._verbose:
print 'instance', instance_to_classify
# svmlight.classify expects a list; this should be taken advantage of when writing SvmClassifier.batch_classify / .batch_prob_classify.
# it returns a list of floats, too.
[prediction] = svmlight.classify(self._model, [instance_to_classify])
return prediction

def prob_classify(self, featureset):
"""
Return a probability distribution of classifications
@param featureset: a dict of feature/value pairs in NLTK format, representing a single instance
"""
if self._model == None:
raise Exception('This classifier is not yet trained')
return None

# do the classification
prediction = self._get_svm_classification(featureset)
if self._verbose:
print 'prediction', prediction

# lump it into a boolean class, -1 or +1
predicted_label = cmp(prediction, 0)

# sometimes the result is not within -1 ... +1; clip it so that it is, and we get a sane-looking probability distribution
# this will upset some results with non-linear partitioning where instance-hyperplane distance can be many orders of magnitude larger; I don't have a fix for that
if prediction < -1.0:
prediction = -1.0
if prediction > 1.0:
prediction = 1.0

# if the prediction is negative, then we will maximise the value of the -1 class; otherwise, that of the 1 class will be greater.
if predicted_label == 1:
distribution = {str(self.resolve_prediction(1)): prediction, str(self.resolve_prediction(-1)): 1 - prediction}
else:
distribution = {str(self.resolve_prediction(1)): prediction + 1, str(self.resolve_prediction(-1)): -prediction}

return DictionaryProbDist(distribution)

def classify(self, featureset):
"""
Use a trained SVM to predict a label given for an unlabelled instance
@param featureset: a dict of feature/value pairs in NLTK format, representing a single instance
"""
prediction = self._get_svm_classification(featureset)
if self._verbose:
print 'prediction', prediction
return self.resolve_prediction(prediction)

@staticmethod
def train(featuresets):
"""
given a set of training instances in nltk format - [ ( {feature:value, ..}, str(label) ) ] - train a support vector machine
@param featuresets: training instances
"""

# build a unique list of labels
labels = set()
for (features, label) in featuresets:
labels.add(label)

# this is a binary classifier only
if len(labels) > 2:
raise ValueError('Can only do boolean classification (labels: '+ str(labels) + ')')
return False

# we need ordering, so a set's no good
labels = list(labels)

# next, assign -1 and 1
labelmapping = {labels[0]:-1, labels[1]:1}

# now for feature conversion
# iter through instances, building a set of feature:type:str(value) triples
svmfeatures = set()
for (features, label) in featuresets:
for k,v in features.iteritems():
svmfeatures.add(featurename(k, v))
# svmfeatures is indexable by integer svm feature number
# svmfeatureindex is the inverse (svm feature name -> number)
svmfeatures = list(svmfeatures)
svmfeatureindex = dict(zip(svmfeatures, range(len(svmfeatures))))

# build svm feature set case by case
svmfeatureset = []
for instance in featuresets:
svmfeatureset.append(map_instance_to_svm(instance, labelmapping, svmfeatureindex))

# train the svm
# TODO: implement passing of SVMlight parameters from train() to learn()
return SvmClassifier(labels, labelmapping, svmfeatures, svmlight.learn(svmfeatureset, type='classification'))

def demo():
return

if __name__ == '__main__':
demo()

Migrated from http://code.google.com/p/nltk/issues/detail?id=695

earlier comments

StevenBird1 said, at 2011-07-07T20:24:19.000Z:

Thanks Leon. I've committed this in r8798. I made slight modifications to the formatting, to reduce the number of lines greater than 80 characters long. I would be grateful for some regression tests to add to nltk/test/classify.doctest please.