2
$\begingroup$

To find the best fit for an SVM, I have to constantly re-train my classifier with different parameters based on the result of the test set.

I created a helper function which trains the SVM with the given parameters p1 and p2 then classifies the test set and gives back the HammingDistance from the original one (as an accuracy measure):

SVMError[X_, y_, testY_, p1_?NumericQ, p2_?NumericQ] := Block[
  {prediction, trainedSVM},
    trainedSVM = ...;
    prediction = ...;
    Return[HammingDistance[prediction, testY]];
];

The returned Hamming distance is between [0..70] with lower being better.

When I run NMinimize with constrains (p1, p2) ∈ [0.01..30] and write out both the evaluations and the steps, "Step taken" is written out only once, although the function evaluates many times.

NMinimize[
  {SVMError[X, y, testY, p1, p2], 0.01 <= p1 <= 30, 0.01 <= p2 <= 30},
  {p1, p2},
  StepMonitor -> Print["Step taken"], EvaluationMonitor -> Print["Evaluated"]
]

My problem is that NMinimize doesn't want to converge. It outputs Hamming distance sequence like this one: 30, 31, 29, 31, 25, 20, 12, 32, 29, 31, etc. when I stop it after 100 iterations.

I've tried the followings so far:

  • Different methods: DifferentialEvolution, MeshSearch, RandomSearch, SimulatedAnnelaing, and NelderMead.
  • Setting MaxIterations, but it has no use (at least with DifferentialEvolution). When I set it to 5, I have to stop the algorithm manually after 30.
  • FindMinimum and Minimize without ?NumericQ. They stalled for an hour doing nothing.
  • Setting AccuracyGoal between [1..30].
  • Returning a fraction of the Hamming distance.
  • Debugging with Optimization`NMinimizeDump`$DiagnosticLevel = 6;. This showed that after each evaluation a numericCheck[{HD}{{p1, p2}}] gets called with the returned Hamming distance and the two given parameters (but I don't know its function body).

My questions are:

  • How can I make NMinimize to "step" into a direction?
  • Is it a better (faster) approach to find the best fitting parameters?
$\endgroup$
  • 1
    $\begingroup$ Can you provide the function SVMError and some X, y and testY that we can play with? Without that it's really hard to say anything specific. Have you tried simply evaluating the function at a grid of values for p1, p2? Since it will be a 2D grid it should be possible to do. $\endgroup$ – Marius Ladegård Meyer May 22 '16 at 15:42
  • 1
    $\begingroup$ One small note: typically StepMonitor and EvaluationMonitor are used with RuleDelayed (I.e. :>) rather than ->. This may not make a difference in your situation above, but it is best practice to avoid the monitoring expression being immediately evaluated. $\endgroup$ – MarcoB May 22 '16 at 15:48
  • $\begingroup$ @MariusLadegårdMeyer: Thank you! I uploaded everything which you can download in a ZIP file from here: github.com/szotsaki/mathematica-nminimize . It should work out of the box after Evaluation > Evaluate Notebook. I know the SVM implementation is slow, but it is for learning purposes only (to better understand background mechanics). I wanted to avoid manually computing random p values since NMinimize can be much better at that. $\endgroup$ – szotsaki'gofundme-DefendFromSO May 22 '16 at 16:24
  • $\begingroup$ @MariusLadegårdMeyer: Thank you for your answer! I'll try it in two days and give detailed feedback (I'm sorry for the delay). In the meanwhile NMinimize finished in 68 steps with 4000 function evaluations, which is clearly slow. $\endgroup$ – szotsaki'gofundme-DefendFromSO May 24 '16 at 14:20
  • $\begingroup$ What was the lowest Hamming distance it found? $\endgroup$ – Marius Ladegård Meyer May 24 '16 at 14:24
2
$\begingroup$

After doing a few test runs where I varied either p1 or p2 while keeping the other fixed, the Hamming distance did not seem to fluctuate wildly, so a grid-based approach may be viable here. Note however that the evaluation time for SVMError is so large in your example ZIP file that any kind of search will require patience :P

The idea is to first evaluate the function over an evenly spaced grid with numGridPoints in both the p1 and p2 directions, from about 0.01 to 30, that is, centered in the "middle", close to {p1,p2}={15,15}. From this grid we pick out either all the n points {p1,p2} that shared the lowest Hamming distance, or the keep points that were among the lowest, if keep>n. Now for each of these points, we make new grids centered at each of them, with smaller widths, to "zoom" in on good candidate points. We can either keep doing this until we are stuck at some minimum value one or more iterations, or until we have made new grids a set number of times. This is the basic setup, with which we can then try lots of things, like changing the amount of "zooming" for each step in the iteration, changing the number of gridpoints etc.

Here is the code:

gridMinimize[centersList_, numGridPoints_, width1_, width2_, keep_, 
  bestval_] :=
 Block[{tab, vals, candidates, min},
  tab = Join @@ (gridding[#, numGridPoints, width1, width2] & /@ 
      centersList);
  vals = tab[[All, 2]];
  min = Min[vals];
  candidates = MinimalBy[tab, Last, Max[Count[vals, min], keep]];

  If[min < bestval,
   gridMinimize[candidates[[All, 1]], numGridPoints, 0.3*width1, 
    0.3*width2, keep, min],
   candidates
   ]
  ]

gridding[{p1center_, p2center_}, numGridPoints_, width1_, width2_] :=

  Block[{w1, w2, r1, r2, window},
  w1 = Min[width1, p1center - 0.01, 30 - p1center];
  w2 = Min[width2, p2center - 0.01, 30 - p2center];
  r1 = If[w1 == 0., {0.}, Range[-w1, w1, 2 w1/(numGridPoints - 1)]];
  r2 = If[w2 == 0., {0.}, Range[-w2, w2, 2 w2/(numGridPoints - 1)]];

  Flatten[
   Table[{{p1, p2},
     SVMError[dataSet3X, dataSet3y, dataSet3CrossValX, 
      dataSet3CrossValy, p1, p2]}, {p1, p1center + r1}, {p2, 
     p2center + r1}
    ], 1]
  ]

The stuff happening in the start of gridding just ensures that our grids don't take us outside the allowed ranges for p1,p2.

As an example run, I ran

gridMinimize[{{15, 15}}, 3, 14.5, 14.5, 2, 70]

and got

{{{1.5785, 14.51}, 13}, {{1.97, 14.51}, 13}, {{2.3615, 14.1185}, 
13}, {{2.3615, 14.51}, 13}, {{1.5785, 14.51}, 13}, {{1.97, 14.51}, 
13}, {{2.3615, 14.1185}, 13}, {{2.3615, 14.51}, 13}}

That is, 8 points close to one another, all with Hamming distance 13. The next step could be to input this set of points (or a subset of them) as the first argument again, and much smaller widths etc. and see if we can go even lower. Or one might start in another region and use widths that exclude the already discovered region, but now with more gridpoints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.