1
2
3
4
5
6
7
8
9 """Common to all SVM implementations functionality. For internal use only"""
10
11 __docformat__ = 'restructuredtext'
12
13 import numpy as N
14 import textwrap
15
16 from mvpa.support.copy import deepcopy
17
18 from mvpa.base import warning
19 from mvpa.base.dochelpers import handleDocString, _rst, _rst_sep2
20
21 from mvpa.clfs.base import Classifier
22 from mvpa.misc.param import Parameter
23 from mvpa.misc.transformers import SecondAxisSumOfAbs
24
25 if __debug__:
26 from mvpa.base import debug
27
28
29 -class _SVM(Classifier):
30 """Support Vector Machine Classifier.
31
32 Base class for all external SVM implementations.
33 """
34
35 """
36 Derived classes should define:
37
38 * _KERNELS: map(dict) should define assignment to a tuple containing
39 implementation kernel type, list of parameters adherent to the
40 kernel, and sensitivity analyzer e.g.::
41
42 _KERNELS = {
43 'linear': (shogun.Kernel.LinearKernel, (), LinearSVMWeights),
44 'rbf' : (shogun.Kernel.GaussianKernel, ('gamma',), None),
45 ...
46 }
47
48 * _KNOWN_IMPLEMENTATIONS: map(dict) should define assignment to a
49 tuple containing implementation of the SVM, list of parameters
50 adherent to the implementation, additional internals, and
51 description e.g.::
52
53 _KNOWN_IMPLEMENTATIONS = {
54 'C_SVC' : (svm.svmc.C_SVC, ('C',),
55 ('binary', 'multiclass'), 'C-SVM classification'),
56 ...
57 }
58
59 """
60
61 _ATTRIBUTE_COLLECTIONS = ['params', 'kernel_params']
62
63 _SVM_PARAMS = {
64 'C' : Parameter(-1.0,
65 doc='Trade-off parameter between width of the '
66 'margin and number of support vectors. Higher C -- '
67 'more rigid margin SVM. In linear kernel, negative '
68 'values provide automatic scaling of their value '
69 'according to the norm of the data'),
70 'nu' : Parameter(0.5, min=0.0, max=1.0,
71 doc='Fraction of datapoints within the margin'),
72 'cache_size': Parameter(100,
73 doc='Size of the kernel cache, specified in megabytes'),
74 'coef0': Parameter(0.5,
75 doc='Offset coefficient in polynomial and sigmoid kernels'),
76 'degree': Parameter(3, doc='Degree of polynomial kernel'),
77
78 'tube_epsilon': Parameter(0.01,
79 doc='Epsilon in epsilon-insensitive loss function of '
80 'epsilon-SVM regression (SVR)'),
81 'gamma': Parameter(0,
82 doc='Scaling (width in RBF) within non-linear kernels'),
83 'tau': Parameter(1e-6, doc='TAU parameter of KRR regression in shogun'),
84 'max_shift': Parameter(10, min=0.0,
85 doc='Maximal shift for SGs GaussianShiftKernel'),
86 'shift_step': Parameter(1, min=0.0,
87 doc='Shift step for SGs GaussianShiftKernel'),
88 'probability': Parameter(0,
89 doc='Flag to signal either probability estimate is obtained '
90 'within LIBSVM'),
91 'scale': Parameter(1.0,
92 doc='Scale factor for linear kernel. '
93 '(0 triggers automagic rescaling by SG'),
94 'shrinking': Parameter(1, doc='Either shrinking is to be conducted'),
95 'weight_label': Parameter([], allowedtype='[int]',
96 doc='To be used in conjunction with weight for custom '
97 'per-label weight'),
98
99 'weight': Parameter([], allowedtype='[double]',
100 doc='Custom weights per label'),
101
102
103
104 'epsilon': Parameter(5e-5, min=1e-10,
105 doc='Tolerance of termination criteria. (For nu-SVM default is 0.001)')
106 }
107
108
109 _clf_internals = [ 'svm', 'kernel-based' ]
110
111 - def __init__(self, kernel_type='linear', **kwargs):
112 """Init base class of SVMs. *Not to be publicly used*
113
114 :Parameters:
115 kernel_type : basestr
116 String must be a valid key for cls._KERNELS
117
118 TODO: handling of parameters might migrate to be generic for
119 all classifiers. SVMs are choosen to be testbase for that
120 functionality to see how well it would fit.
121 """
122
123
124 svm_impl = kwargs.get('svm_impl', None)
125 if not svm_impl in self._KNOWN_IMPLEMENTATIONS:
126 raise ValueError, \
127 "Unknown SVM implementation '%s' is requested for %s." \
128 "Known are: %s" % (svm_impl, self.__class__,
129 self._KNOWN_IMPLEMENTATIONS.keys())
130 self._svm_impl = svm_impl
131
132
133 kernel_type = kernel_type.lower()
134 if not kernel_type in self._KERNELS:
135 raise ValueError, "Unknown kernel " + kernel_type
136 self._kernel_type_literal = kernel_type
137
138 impl, add_params, add_internals, descr = \
139 self._KNOWN_IMPLEMENTATIONS[svm_impl]
140
141
142
143 if add_params is not None:
144 self._KNOWN_PARAMS = \
145 self._KNOWN_PARAMS[:] + list(add_params)
146
147
148
149 if self._KERNELS[kernel_type][1] is not None:
150 self._KNOWN_KERNEL_PARAMS = \
151 self._KNOWN_KERNEL_PARAMS[:] + list(self._KERNELS[kernel_type][1])
152
153
154 self._clf_internals = self._clf_internals[:]
155
156
157 if add_internals is not None:
158 self._clf_internals += list(add_internals)
159 self._clf_internals.append(svm_impl)
160
161 if kernel_type == 'linear':
162 self._clf_internals += [ 'linear', 'has_sensitivity' ]
163 else:
164 self._clf_internals += [ 'non-linear' ]
165
166
167 _args = {}
168 for param in self._KNOWN_KERNEL_PARAMS + self._KNOWN_PARAMS + ['svm_impl']:
169 if param in kwargs:
170 _args[param] = kwargs.pop(param)
171
172 try:
173 Classifier.__init__(self, **kwargs)
174 except TypeError, e:
175 if "__init__() got an unexpected keyword argument " in e.args[0]:
176
177
178 e.args = tuple( [e.args[0] +
179 "\n Given SVM instance of class %s knows following parameters: %s" %
180 (self.__class__, self._KNOWN_PARAMS) +
181 ", and kernel parameters: %s" %
182 self._KNOWN_KERNEL_PARAMS] + list(e.args)[1:])
183 raise e
184
185
186 for paramfamily, paramset in ( (self._KNOWN_PARAMS, self.params),
187 (self._KNOWN_KERNEL_PARAMS, self.kernel_params)):
188 for paramname in paramfamily:
189 if not (paramname in self._SVM_PARAMS):
190 raise ValueError, "Unknown parameter %s" % paramname + \
191 ". Known SVM params are: %s" % self._SVM_PARAMS.keys()
192 param = deepcopy(self._SVM_PARAMS[paramname])
193 param.name = paramname
194 if paramname in _args:
195 param.value = _args[paramname]
196
197
198 paramset.add(param)
199
200
201 if self.params.isKnown('C') and kernel_type != "linear" \
202 and self.params['C'].isDefault:
203 if __debug__:
204 debug("SVM_", "Assigning default C value to be 1.0 for SVM "
205 "%s with non-linear kernel" % self)
206 self.params['C'].default = 1.0
207
208
209 if self.params.isKnown('weight') and self.params.isKnown('weight_label'):
210 if not len(self.weight_label) == len(self.weight):
211 raise ValueError, "Lenghts of 'weight' and 'weight_label' lists" \
212 "must be equal."
213
214 self._kernel_type = self._KERNELS[kernel_type][0]
215 if __debug__:
216 debug("SVM", "Initialized %s with kernel %s:%s" %
217 (self, kernel_type, self._kernel_type))
218
219
221 """Definition of the object summary over the object
222 """
223 res = "%s(kernel_type='%s', svm_impl='%s'" % \
224 (self.__class__.__name__, self._kernel_type_literal,
225 self._svm_impl)
226 sep = ", "
227 for col in [self.params, self.kernel_params]:
228 for k in col.names:
229
230 if col[k].isDefault: continue
231 res += "%s%s=%s" % (sep, k, col[k].value)
232
233 for name, invert in ( ('enable', False), ('disable', True) ):
234 states = self.states._getEnabled(nondefault=False, invert=invert)
235 if len(states):
236 res += sep + "%s_states=%s" % (name, str(states))
237
238 res += ")"
239 return res
240
241
243 """Compute default C
244
245 TODO: for non-linear SVMs
246 """
247
248 if self._kernel_type_literal == 'linear':
249 datasetnorm = N.mean(N.sqrt(N.sum(data*data, axis=1)))
250 value = 1.0/(datasetnorm*datasetnorm)
251 if __debug__:
252 debug("SVM", "Default C computed to be %f" % value)
253 else:
254 warning("TODO: Computation of default C is not yet implemented" +
255 " for non-linear SVMs. Assigning 1.0")
256 value = 1.0
257
258 return value
259
260
262 """Compute default Gamma
263
264 TODO: unify bloody libsvm interface so it makes use of this function.
265 Now it is computed within SVMModel.__init__
266 """
267
268 if self.kernel_params.isKnown('gamma'):
269 value = 1.0 / len(dataset.uniquelabels)
270 if __debug__:
271 debug("SVM", "Default Gamma is computed to be %f" % value)
272 else:
273 raise RuntimeError, "Shouldn't ask for default Gamma here"
274
275 return value
276
278 """Returns an appropriate SensitivityAnalyzer."""
279 sana = self._KERNELS[self._kernel_type_literal][2]
280 if sana is not None:
281 kwargs.setdefault('combiner', SecondAxisSumOfAbs)
282 return sana(self, **kwargs)
283 else:
284 raise NotImplementedError, \
285 "Sensitivity analyzers for kernel %s is TODO" % \
286 self._kernel_type_literal
287
288
289 @classmethod
291
292
293 idoc_old = cls.__init__.__doc__
294
295 idoc = """
296 SVM/SVR definition is dependent on specifying kernel, implementation
297 type, and parameters for each of them which vary depending on the
298 choices made.
299
300 Desired implementation is specified in `svm_impl` argument. Here
301 is the list if implementations known to this class, along with
302 specific to them parameters (described below among the rest of
303 parameters), and what tasks it is capable to deal with
304 (e.g. regression, binary and/or multiclass classification).
305
306 %sImplementations%s""" % (_rst_sep2, _rst_sep2)
307
308
309 class NOSClass(object):
310 """Helper -- NothingOrSomething ;)
311 If list is not empty -- return its entries within string s
312 """
313 def __init__(self):
314 self.seen = []
315 def __call__(self, l, s, empty=''):
316 if l is None or not len(l):
317 return empty
318 else:
319 lsorted = list(l)
320 lsorted.sort()
321 self.seen += lsorted
322 return s % (', '.join(lsorted))
323 NOS = NOSClass()
324
325
326 idoc += ''.join(
327 ['\n %s : %s' % (k, v[3])
328 + NOS(v[1], "\n Parameters: %s")
329 + NOS(v[2], "\n%s Capabilities: %%s" %
330 _rst(('','\n')[int(len(v[1])>0)], ''))
331 for k,v in cls._KNOWN_IMPLEMENTATIONS.iteritems()])
332
333
334 idoc += """
335
336 Kernel choice is specified as a string argument `kernel_type` and it
337 can be specialized with additional arguments to this constructor
338 function. Some kernels might allow computation of per feature
339 sensitivity.
340
341 %sKernels%s""" % (_rst_sep2, _rst_sep2)
342
343 idoc += ''.join(
344 ['\n %s' % k
345 + ('', ' : provides sensitivity')[int(v[2] is not None)]
346 + '\n ' + NOS(v[1], '%s', 'No parameters')
347 for k,v in cls._KERNELS.iteritems()])
348
349
350 NOS.seen += cls._KNOWN_PARAMS + cls._KNOWN_KERNEL_PARAMS
351
352 idoc += '\n:Parameters:\n' + '\n'.join(
353 [v.doc(indent=' ')
354 for k,v in cls._SVM_PARAMS.iteritems()
355 if k in NOS.seen])
356
357 cls.__dict__['__init__'].__doc__ = handleDocString(idoc_old) + idoc
358
359
360
361 for k,v in _SVM._SVM_PARAMS.iteritems():
362 v.name = k
363