Sometimes, a "brute force feature generation and selection-athon" is irresistible.
I had a feeling that some data I was looking at contained hidden relationships between attributes that could have yielded an improved prediction performance. I had a gut feel that dividing one attribute by another or perhaps taking the log of one and adding it the reciprocal of another might give a new attribute with more predictive power. How to do this without a tiresome manual intervention that would have been boring, could have missed some permutation, and could have made mistakes?
There are a number of ways of doing this in RapidMiner. One approach uses one of the iterating operators, collectively known as YAGGA, to perform an evolutionary search. Each iteration generates new attributes by combining existing attributes using simple functions. The performance is assessed and attributes that don't lead to an improvement are eliminated whilst those that do are retained to allow them to generate yet more attributes. This process repeats until the desired stopping conditions have been reached.
For the masochist, there is a lower level operator called "Generate Function Set" that allows control to be exerted over the operation. I adopted this because I wanted to look in detail at the attributes that were leading to improvements and equally see those that led nowhere.
So I made a process. But then I got stuck because I found that there was no way in the RapidMiner Studio GUI, to see what construction had been applied to generate new attributes. A bit of background; when RapidMiner generates new attributes, they show up with names of the form "gensymxxx". In the old days, there was a way of seeing the attribute construction from one of the viewing panes. Alas, it's not there anymore.
Luckily, there is an operator called "Write Constructions". This takes an example set and writes it to a file which contains details of the construction. A bit laborious but workable.
Did I find a new attribute that made an improvement? Yes I did. It was a small improvement but enough to be interesting. The improvement is the sort of thing that would get you from the middle of the leaderboard to be a contender in a Kaggle competition.
Showing posts with label GeneticAlgorithms. Show all posts
Showing posts with label GeneticAlgorithms. Show all posts
Saturday, 8 December 2018
Thursday, 18 January 2018
Genetic Algorithms with R and Shiny
Following on from this post, here's an application that uses a genetic algorithm to find the maximum of a complex function as the inputs to it are varied.
I've implemented this in R and Shiny and the application is hosted on shinyapps.io here. The application lets a user try to beat the computer and find the optimum by brute force alone. Needless to say, there's no chance of a human managing this in any meaningful time.
As with the previous post, the Rastrigin function is being used as the function to which the optimum inputs are to be sought. The R package GA is being used to find the optimum. Gratifyingly, hardly any code is needed; it is on GitHub here.
The progress of the genetic algorithm towards the goal can be plotted. Here's an example.
As with RapidMiner, convergence towards the optimum is quick, and it usually happens in about 30 generations.
In summary, of course R can do this, but for me the cool part is how concise the code is and by using Shiny how easy it is to show to others.
I've implemented this in R and Shiny and the application is hosted on shinyapps.io here. The application lets a user try to beat the computer and find the optimum by brute force alone. Needless to say, there's no chance of a human managing this in any meaningful time.
As with the previous post, the Rastrigin function is being used as the function to which the optimum inputs are to be sought. The R package GA is being used to find the optimum. Gratifyingly, hardly any code is needed; it is on GitHub here.
The progress of the genetic algorithm towards the goal can be plotted. Here's an example.
In summary, of course R can do this, but for me the cool part is how concise the code is and by using Shiny how easy it is to show to others.
Wednesday, 8 November 2017
Evolutionary process that helped me to win $1000
As the recent successful winner of the RapidMiner farming on Mars competition, I thought I would post the evolutionary process that helped lead me to the best solution.
I've tidied it up a bit and in fact there are 4 processes. The main one calls the others using "Execute Process" which ensures that common processing is placed in one location to avoid making errors.
The four processes are.
I've tidied it up a bit and in fact there are 4 processes. The main one calls the others using "Execute Process" which ensures that common processing is placed in one location to avoid making errors.
The four processes are.
When saving these, ensure the names are as above and they are all saved in the same repository. It's also important to point the processes at the locations of the training and test files. Download the training data from here and the test data from here. Unzip in the normal way and enter the locations into the "ReadAllData" process by changing the macros associated with the "ExecuteProcess" operator that runs the "ImportData" process.
When all the dust has settled, run the "EvoExample" process and observe the log output that writes a row each time a test has been performed with the specific settings of hour and misclassification cost.
These two parameters are contained in the depths of the process and the evolutionary process chooses values for these parameters and determines how they affect performance.
The process has a couple of interesting features. Firstly, the performance is extracted from a calculation to match the scoring used in the competition. The operator "Extract Performance" is used to do this. Secondly, the process shows a way of varying the value of a macro inside the evolutionary operator. This is a bit of a hack and involves using the varying parameter of the evolutionary operator to control the execution of the example set made by a "Generate Data" operator and then using other operators to extract the details of this dummy example set to place into a macro. Maybe there's an easier way; I couldn't find one.
The contest did reveal an issue with the way nominal values are read and assigned which show up when running in Windows and in Linux environments. I hope this will lead to an enhancement to allow more control to be exerted. In the meantime, the process tries to get round these by sorting and being explicit in assigning positive and negative labels. Despite this, there is a chance that different environments will yield different results. The interested reader is referred to this process.
Have fun!...
Friday, 10 June 2016
Using Genetic Algorithms to find global extremes in arbitrary functions
Genetic algorithms offer the possibility to find global maxima and minima in arbitrary functions as the inputs to the functions are varied. RapidMiner has a number of evolutionary operators and one in particular is "Optimize Parameters (Evolutionary)" that, on the face of it, allows the parameters of operators contained within it to be varied as a performance vector is calculated based on how the varied parameters cause the inner operators to behave. There is a slight difficulty because not all parameters can be exposed for control by the Optimize operator so a work-around is needed. We'll come back to that shortly.
Firstly, let's choose a function to optimize. A good candidate is the Rastrigin function that, in two dimensions, has the following form.
f(i1, i2) = 20 + i1*i1 + i2*i2 - 10*(cos(2*pi*i1) + cos(2*pi*i2))
Within the range -5.12 to 5.12 for both i1 and i2, the function has many local minima which makes finding the lowest a challenging problem for some techniques. The following graph shows the function.
By inspection and exploration we can find that the global minimum is 0 when i1 and i2 are both 0. The process to generate this data is here.
Now let's see if we can find this minimum using a RapidMiner process. The process is here.
The inner operators inside the Optimize operator are shown below.
The two operators labelled i1 and i2 are there purely to allow parameters to be passed from the control part of the Optimize operator. This is the work around I mentioned earlier. Basically, operators i1 and i2 expose parameters that can be seen from the Optimize operator and can be varied. The parameter settings for the Optimize operator are shown in the following.
This shows that the i1.constant value is allowed to vary between -5.12 and 5.12; the Optimize operator chooses the values as it proceeds.
Returning to the inner operators, the values of the parameters are accessed using a "Generate Attributes" operator. The first two attributes show how to get the values from the i1 and i2 operators. The third attribute calculates the Rastrigin value and the fourth attribute copies this into a result attribute (not strictly necessary - this process used to have other functions which I deleted to make the cut down process for this blog post).
From this point, the "Optimize" operator needs a performance vector to work on. The simplest thing to use is the "Extract Performance" operator to extract a specific value from the example set containing the Rastrigin result. This is shown below and the optimization direction is set to minimize since we are looking for a minimum.
The final "Log" operator records what happens.
If we run this process the Log result is shown in the following plot.
This shows the performance tending to 0, the global minimum, as the process proceeds and this corresponds to i1 and i2 both being 0. Plotting the log result as a scatter plot shows clusters of blue points which show how the genetic algorithm successfully keeps to areas where there are minima.
Genetic algorithms are not guaranteed to find the global minimum and in fact, even the process in this blog occasionally does not find it. If you set the parameter "specify population size" in "Optimize Parameters (Evolutionary)" to a small number like 5, you should observe this because fewer individuals are used to test the solution space and so the chance of being near the global minimum is low. Note that a little known feature of the "Process" operator is that setting "random seed" to -1 causes a new random seed to be selected for each run thereby ensuring that each run produces different results.
Of course, there is no way to detect when the global extreme is not found in the more normal case when the answer is not known beforehand. As usual, be sceptical and alive to the possibility that the result is not the best and try different parameter settings to see how results change. As mentioned, the population size affects this as do the "crossover prob" and "tournament fraction" parameters. There is no free lunch of course and an exhaustive search will always take longer.
In summary, we can see that RapidMiner can, with a bit of a work around, be used to optimize arbitrary functions. My experiments show that it seems to do a good job in most cases. A future post will show the same thing using R.
Firstly, let's choose a function to optimize. A good candidate is the Rastrigin function that, in two dimensions, has the following form.
f(i1, i2) = 20 + i1*i1 + i2*i2 - 10*(cos(2*pi*i1) + cos(2*pi*i2))
Within the range -5.12 to 5.12 for both i1 and i2, the function has many local minima which makes finding the lowest a challenging problem for some techniques. The following graph shows the function.
By inspection and exploration we can find that the global minimum is 0 when i1 and i2 are both 0. The process to generate this data is here.
Now let's see if we can find this minimum using a RapidMiner process. The process is here.
The first part of the process shown above uses a "Generate Data by User Specification" operator to generate a small example set that needs a label and a regular attribute in order for the "Optimize Parameters (Evolutionary)" operator to work.
The inner operators inside the Optimize operator are shown below.
This shows that the i1.constant value is allowed to vary between -5.12 and 5.12; the Optimize operator chooses the values as it proceeds.
Returning to the inner operators, the values of the parameters are accessed using a "Generate Attributes" operator. The first two attributes show how to get the values from the i1 and i2 operators. The third attribute calculates the Rastrigin value and the fourth attribute copies this into a result attribute (not strictly necessary - this process used to have other functions which I deleted to make the cut down process for this blog post).
From this point, the "Optimize" operator needs a performance vector to work on. The simplest thing to use is the "Extract Performance" operator to extract a specific value from the example set containing the Rastrigin result. This is shown below and the optimization direction is set to minimize since we are looking for a minimum.
The final "Log" operator records what happens.
If we run this process the Log result is shown in the following plot.
This shows the performance tending to 0, the global minimum, as the process proceeds and this corresponds to i1 and i2 both being 0. Plotting the log result as a scatter plot shows clusters of blue points which show how the genetic algorithm successfully keeps to areas where there are minima.
Of course, there is no way to detect when the global extreme is not found in the more normal case when the answer is not known beforehand. As usual, be sceptical and alive to the possibility that the result is not the best and try different parameter settings to see how results change. As mentioned, the population size affects this as do the "crossover prob" and "tournament fraction" parameters. There is no free lunch of course and an exhaustive search will always take longer.
In summary, we can see that RapidMiner can, with a bit of a work around, be used to optimize arbitrary functions. My experiments show that it seems to do a good job in most cases. A future post will show the same thing using R.
Subscribe to:
Posts (Atom)