1
$\begingroup$

Let's say you are doing linear regression. We are trying to fit $w^Tx=y$. One way to do that is by utilizing gradient descent to minimize this function: $J(w) = \frac1{2n} \sum_{i=1}^{n} (w^Tx-y)^2$. (Context: slight variation from Andrew Ng's Coursera Machine Learning course).

Now, my question is, can you say $J(w)$ is our fitness function, and then apply, for instance, simulated annealing (SA), randomized hill climbing (RHC), a genetic algorithm (GA), or PBIL to it? (easy enough to take negatives or switch minima to maxima, depending on the implementation) Does it matter that the values I want for $w$ are going to be real-valued, or will that cause these optimization methods to not work well?

Edit/update for clarification: I know gradient descent will (unless I have a special example indeed!) give me real numbers (any number of digits after the decimal) rather than integer solutions. My question was whether with randomized optimization, would your precision be limited? Based on the answer given by jolvi, some versions of GA/PBIL could limit said answers (exactly my concern). I'm concluding that it doesn't matter for SA or RHC.

Additionally: I did want to ask if Mutual Information Maximizing Input Clustering (MIMIC) also caused limited precision, but I wasn't sure if this was a well-known algorithm. I found Wikipedia pages for everything else but this algorithm.

$\endgroup$
3
  • $\begingroup$ Most optimization methods (except for the most naive and simplistic) will succeed with this function, because it is purely quadratic. Could you explain your concern about real-valued parameters? None of the methods you mention are concerned with complex numbers; in fact, if you allow complex values then $J(w)$ will have no minimum value. $\endgroup$
    – whuber
    Feb 27, 2015 at 23:00
  • $\begingroup$ It sounds like you think I am concerned about real vs complex; actually I am concerned with real vs integer. I think this is addressed below in jolvi's answer(since encoding GA as binary/Gray code restricts your precision.) $\endgroup$ Feb 28, 2015 at 16:41
  • $\begingroup$ Thank you for the clarification. It is usual in mathematics to use "real-valued" in contradistinction to complex valued (because integers and rational numbers are automatically real) and in computer science to use "floating [point]" when the alternative of an integer format is intended. Slightly more surprising is the implication in your post that ordinarily the parameters $w$ are integral: that would be an unusual application. I suspect you may be conceiving of simulated annealing, etc., to be primarily discrete solvers, but they are not. $\endgroup$
    – whuber
    Feb 28, 2015 at 20:00

1 Answer 1

0
$\begingroup$

Conventional Genetic algorithms and PBIL rely on a discretization, which restricts the precision of the solution you can find. This can be particularly problematic if the optimal $w$ has both very large and small values in absolute terms. It seems more suggestive to use real-valued algorithms, like real-coded GAs or Evolution Strategies.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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