Subscribe to Vincent Granville's Weekly Digest:

Function minimization: Simulated Annealing led by variance criteria vs Nelder Mead

Most of the datamining problems can be reduced as a minimization/maximization problem.

... click here to read the entire post

Examples
Let's consider  easy scenarios where the function cost is conditionated just by two parameters.

... click here to read the entire post

As you can see the above problems have in common a massive presence of local minimum :).
Let's see how to handle these problems through an approach that I define hybrid, that is, obtained mixing different methods and properties.
Simulated Annealing (SA) "variance based" approach
 

... click here to read the entire post

Variance trick 

Let's consider a sampling in two different region of a function f :

  • sampling_1 in a region having a smooth minimum and evaluate such points
  • sampling_2 in a region having a spiky minimum and evaluate such points
Take now the variance of these evaluated sets.
How does the variance of f(sampling_1)  change respect the variance of f(sampling_2)?  
Here you are the answer:
As you can see the variance can be used as indicator of a minimum region of the cost function.
Instead of explore randomly the solution space, the approach I propose is led by the variance used as  above. 
What happens if the smooth valley is a global minimum?
There are two intuitive factors to avoid that the algorithm jams in a local minimum:
1. The acceptance law admit also pejorative solutions.
2. The sampling procedure moderate by variance (if the variance is chosen high enough) allows explorations of better regions.
The algorithm

... click here to read the entire post

Tests
Let's see how the approach works.
As usual, all my experiments are compared with other techniques. In this case I chose as comparative method the well known "Nelder Mead" method.
I tried to optimize the Nelder Mead method playing around its param setting: shrink ratio, contraction ratio and reflection ratio.

... click here to read the entire post

On the left side it has been represented the solution found by Nelder Mead method.
On the right side the solution found by the SA presented in this post: the blue point depicts the starting point and the red point depicts the solution found.
The last chart shows the space solution explored

... click here to read the entire post

EXPERIMENT 2:

On the left side it has been represented the solution found by Nelder Mead method.
On the right side the solution found by the SA presented in this post: the blue point depicts the starting point and the red point depicts the solution found.

Experiment 3

Experiment 4:

Conclusion
The approach seems promising and works well in different contexts:  I'm quite sure that many improvements can be implemented.
I'm looking forward to receive your comments, ideas and other comparative tests.
Stay tuned!
 
cristian

 

 

 

 

Views: 217

Comment

You need to be a member of AnalyticBridge to add comments!

Join AnalyticBridge

Top Content 

1 How to develop churn prediction model for telecom company?

How to develop churn prediction model for telecom company?
2 Map of Data Science University Programs

Map of Data Science University Programs
3 Use PRESS, not R squared to judge predictive power of regression

Use PRESS, not R squared to judge predictive power of regression
4 Text mining: alternative to Wordflex?

Text mining: alternative to Wordflex?
5 Audience expansion

Audience expansion
6 Simple solutions to make videos with R

Simple solutions to make videos with R
7 Strategy for building a “good” predictive model

Strategy for building a “good” predictive model
8 The End of Theory: The Data Deluge Makes the Scientific Method Obsolete | Wired

The End of Theory: The Data Deluge Makes the Scientific Method Obsolete | Wired
9 Is Open Source Really Free?

Is Open Source Really Free?
10 Understanding the Kalman Filter Application in Economic Time Series Data

Understanding the Kalman Filter Application in Economic Time Series Data

Follow us

Big Data Jobs

Data Scientist - Amazon

Business Analyst - Amazon

Senior Statistician, Marketing Analytics

Fraud Data Analyst

Data Scientist - Apple

Data Mining Scientist - Apple

Data Scientist

Analytics Consultant

Marketing Analyst - Mobile (Zappos.com)

Director, Network Data Science

© 2013   AnalyticBridge.com is a subsidiary and dedicated channel of Data Science Central LLC

Badges  |  Report an Issue  |  Terms of Service