3
$\begingroup$

Apologize in advance for intentional vagueness. Questions I'd like answered highlighted in bold.

Intro

So we have an algorithm which, given a weighting function and an item to process, processes the item and returns a result. We want to optimize the weighting function this algorithm uses.

We've identified about 15 different potential weighting functions that we'd like to run through this process. Each weighting function has about 4 parameters, and each of these parameters ranges from let's say 0 to 15 (as a real value).

We have a dataset to train on. Further, we also have a fitness function for a given weighting function on the dataset.

Another issue arises is that there is some configuration/state that must be added to the algorithm for the data set to be processed. This configuration is variable as well (and not part of the actual data set), and contains a series of N items, each with 3 variables. Some of these configurations will result in the weighting functions performing identically, while others make certain functions perform better than others.

So, to sum up:

  • W = {Weighting Function, Parameter Set}
  • C = {Configuration Variable Set} * N

So we've run into this issue where there is a "chicken and egg" problem. In order to optimize the weighting function, we need the 'best' configuration (C), for whatever that means. In order to find the 'best' C, we need the 'best' weighting function/parameters (W).

Based on this, I'm considering a process in which we:

  1. Choose a random C.
  2. Search for Optimal W on that C.
  3. Choose Optimal C based on the output W.
  4. Input C into 2.

Based on my limited ML experience from college, this sounds very similar to the EM algorithm, though not identical (for obvious reasons). Is there a name for this algorithm? Is it right to call it "EM"?

Am I off the rails with this approach? Is there a better way I could go about doing this?

Genetic Algorithm

Based on the definition above, you may be asking where GA comes in. Well, it seems to me like it's quite simple to define two different chromosomes, one for W and one for C, and use this as my optimization method in each step. The reasons for this include that I believe the data to have many local maxima, this process won't be run in real time at all, and the search space is quite vast (many, deep variables).

Are there any caveats to using GA in this manner? Is there anything glaring I'm missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

From what you've described, I don't see any reason to call it an EM algorithm.

Rather, this is a conditional optimization algorithm: it's easier to update parameters $\theta_1$ conditional on the values of parameters $\theta_2$ (and $\theta_2$ conditional on the values of $\theta_1$) than to jointly update $\{\theta_1,\theta_2\}$. So you are switching back and forth between updating each set of parameters, conditional on the other set of parameters.

It still could be an EM-algorithm that's doing the updates (i.e. an ECM algorithm). But that's orthogonal to what you've told us about the problem so far.

$\endgroup$
1
  • $\begingroup$ That makes sense. I've been doing some reading since posting (and quite a bit before), and just happened to come across this paper which seems to call something which seems close to it an EARL (Evolutionary Algorithm for Reinforcement Learning). After looking up what you posted though, it does seem that it's an Iterative/Conditional Optimization Algorithm, though I guess these two are not mutually exclusive. $\endgroup$ Oct 20, 2015 at 23:40

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.