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 chosen 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._setName(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 if datasetnorm == 0:
251 warning("Obtained degenerate data with zero norm for training "
252 "of %s. Scaling of C cannot be done." % self)
253 return 1.0
254 value = 1.0/(datasetnorm**2)
255 if __debug__:
256 debug("SVM", "Default C computed to be %f" % value)
257 else:
258 warning("TODO: Computation of default C is not yet implemented" +
259 " for non-linear SVMs. Assigning 1.0")
260 value = 1.0
261
262 return value
263
264
266 """Compute default Gamma
267
268 TODO: unify bloody libsvm interface so it makes use of this function.
269 Now it is computed within SVMModel.__init__
270 """
271
272 if self.kernel_params.isKnown('gamma'):
273 value = 1.0 / len(dataset.uniquelabels)
274 if __debug__:
275 debug("SVM", "Default Gamma is computed to be %f" % value)
276 else:
277 raise RuntimeError, "Shouldn't ask for default Gamma here"
278
279 return value
280
282 """Returns an appropriate SensitivityAnalyzer."""
283 sana = self._KERNELS[self._kernel_type_literal][2]
284 if sana is not None:
285 kwargs.setdefault('combiner', SecondAxisSumOfAbs)
286 return sana(self, **kwargs)
287 else:
288 raise NotImplementedError, \
289 "Sensitivity analyzers for kernel %s is TODO" % \
290 self._kernel_type_literal
291
292
293 @classmethod
295
296
297 idoc_old = cls.__init__.__doc__
298
299 idoc = """
300 SVM/SVR definition is dependent on specifying kernel, implementation
301 type, and parameters for each of them which vary depending on the
302 choices made.
303
304 Desired implementation is specified in `svm_impl` argument. Here
305 is the list if implementations known to this class, along with
306 specific to them parameters (described below among the rest of
307 parameters), and what tasks it is capable to deal with
308 (e.g. regression, binary and/or multiclass classification).
309
310 %sImplementations%s""" % (_rst_sep2, _rst_sep2)
311
312
313 class NOSClass(object):
314 """Helper -- NothingOrSomething ;)
315 If list is not empty -- return its entries within string s
316 """
317 def __init__(self):
318 self.seen = []
319 def __call__(self, l, s, empty=''):
320 if l is None or not len(l):
321 return empty
322 else:
323 lsorted = list(l)
324 lsorted.sort()
325 self.seen += lsorted
326 return s % (', '.join(lsorted))
327 NOS = NOSClass()
328
329
330 idoc += ''.join(
331 ['\n %s : %s' % (k, v[3])
332 + NOS(v[1], "\n Parameters: %s")
333 + NOS(v[2], "\n%s Capabilities: %%s" %
334 _rst(('','\n')[int(len(v[1])>0)], ''))
335 for k,v in cls._KNOWN_IMPLEMENTATIONS.iteritems()])
336
337
338 idoc += """
339
340 Kernel choice is specified as a string argument `kernel_type` and it
341 can be specialized with additional arguments to this constructor
342 function. Some kernels might allow computation of per feature
343 sensitivity.
344
345 %sKernels%s""" % (_rst_sep2, _rst_sep2)
346
347 idoc += ''.join(
348 ['\n %s' % k
349 + ('', ' : provides sensitivity')[int(v[2] is not None)]
350 + '\n ' + NOS(v[1], '%s', 'No parameters')
351 for k,v in cls._KERNELS.iteritems()])
352
353
354 NOS.seen += cls._KNOWN_PARAMS + cls._KNOWN_KERNEL_PARAMS
355
356 idoc += '\n:Parameters:\n' + '\n'.join(
357 [v.doc(indent=' ')
358 for k,v in cls._SVM_PARAMS.iteritems()
359 if k in NOS.seen])
360
361 cls.__dict__['__init__'].__doc__ = handleDocString(idoc_old) + idoc
362
363
364
365 for k,v in _SVM._SVM_PARAMS.iteritems():
366 v._setName(k)
367