0
$\begingroup$

I am currently taking a class in machine learning. I had mentioned to a coworker that we were learning about randomized optimization, specifically randomized hill climbing (RHC). He said that it was possible to use RHC instead of backpropagation to find good weights for a neural network. Unfortunately, we didn't get to finish the conversation, and it's been bugging me all weekend. Does anyone know what he meant by that?

I've been playing around with Weka, using the weka.classifiers.bayes.net.search.local.K2 classifier...but I'm just not seeing how that would give me weights that could be used by a neural network, such as the multilayer perceptron.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hill Climbing doesn't use gradient information, while Backprop does. Thus backprop works / converges much faster. $\endgroup$ – Artem Sobolev Feb 9 '15 at 11:33
  • $\begingroup$ I am not an ANN expert, but a quick Google search reveals that the RHC algorithm involves changing a single weight, and see if the performance increases, and if so, keep this new weight. So it's a greedy method. You start with an initial set of weights, then changing one weight at a time, with a random amount (the maximum absolute value of this change might be called "learning rate" in this context) and if the performance of your classifier/regressor/whatever is better, than you will keep this new set of weights, and repeat until "convergence". $\endgroup$ – jeff Sep 12 '15 at 2:29
  • $\begingroup$ Related to using RHC for ANN training is Neuroevolution, which uses evolutionary/genetic algorithms for determining the weights of a neural network. The core idea is the same: they determine if candidate (=weights) get better by their fitness (=NN error/performance). GAs with Neuroevolution might be good complementary information for understanding how such concepts can be used with ANN training. $\endgroup$ – geekoverdose Jun 15 '16 at 13:15
  • $\begingroup$ You may also be interested in a few other questions about alternate ways to train a neural network, like stats.stackexchange.com/questions/207450/… and stats.stackexchange.com/questions/235862/… $\endgroup$ – Matt Krause Aug 23 '18 at 1:10
1
$\begingroup$

Recent papers show that there is nearly always some small step you can take to head toward a good solution: Saddle point problem It seems to me that something like random hill climbing (RHC) is fine for that. In practice I am starting to see that in my code too. For deep neural networks I wouldn't be surprised if RHC and back-propagation were comparable in the amount of computation required.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

Random search has great probability of finding you a solution among the top ones, see my answer to Practical hyperparameter optimization: Random vs. grid search.

So, with only 60 tries, and a constrained parameter set, you have 95 percent probability of finding a solution among the top 5 percent best solutions (inside those constraints). Great, right? Well...

Actually, it turns out that solution might still be totally garbage, and you might only get good solutions from NNs into the 0.1 or even less percent of solution, requiring even more trials to have a good probability of finding.

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

Yes, this is really possible to use RHC in NN. This algorithm is simple.

Let me set a few variables:

$W_{i}$ - current weight in i-th layer.

$Wnew_{i}$ - the new weight which we will compute in new epoch.

$CD$ - Some matrix with Cauchy distributed values in $(0, 1)$

$E(x)$ - Network error function. For example it can be MSE (Mean square error).

$a$ and $b$ - some small variables between $0$ and $1$ which correct your learning step.

$epoch$ - current trainig epoch

$countOfEpoch$ - total count of training epochs

$epochError$ - previous epoch error

$newEpochError$ - current epoch error

$errorLimit$ - this is some small parameter which tell you when you can stop your trainig process. For example $errorLimit = 0.001$

Algorithm:

1) Choose random matrix and assign it to $W$. (It can me normal distribution)

2) Compute your $epochError = E(W_{i})$ with random weights.

3) If your $epochError < errorLimit$ or $epoch < countOfEpoch$ - then stop training process. If not - go to the next step.

4) Update all your network weights. Fir of all you must compute $Wnew_{i} = W_{i} + CD * (CD * (a * min(epochError, 1) + b)$

5) Compute $newEpochError = E(Wnew_{i})$ with new weights.

6) Check epoch error difference. If $newEpochError - epochError < 0$ than you need save your update ($W_{i} = Wnew_{i}$) and update your current epoch error ($epochError = newEpochError$)

7) Increment variable $epoch$ and go back to step 3.

So that's it.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ This will never work well for neural networks with more than a dozen parameters. $\endgroup$ – Neil G Jun 6 '15 at 8:23
  • $\begingroup$ Word "never" is too strong, you could be lucky and get perfect weights after one learning epoch for any weight size, but probability could be extremely small for this event (but it possible). Also nobody says that this algorithms is good on practice, gradient descent gives you best direction without randomization and it solve problems much faster. As for me this algorithm is a good intuition for gradient descent and good starting point for people who not so good in calculus and what not just program and use learning algorithm, but get good intuition of how and why it works. $\endgroup$ – itdxer Jun 6 '15 at 8:45
  • 3
    $\begingroup$ Never in either of our lifetimes for any significantly sized problems. The chance that it stumbles on discovering features, like solving MNIST, is basically so tremendously unlikely that it might as well be impossible. Wikipedia defines hill-climbing whereby the proposal changes are single element changes. If you do that, then it definitely is impossible to solve mnist. I think he was asking whether it is good in practice. $\endgroup$ – Neil G Jun 6 '15 at 9:05
  • $\begingroup$ Just copy last part of question "...I'm just not seeing how that would give me weights that could be used by a neural network, such as the multilayer perceptron." $\endgroup$ – itdxer Jun 6 '15 at 10:02

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.