Parameter Search Methods

From MindModelingWiki

Search techniques used by MindModeling@Home Media:AMR.ogg

[edit] Quick (boincAMR)

Definition

Quick is a simple implementation of an Adaptive Mesh Refinement algorithm. Provided with two vertices of a hypercube, Quick will sample the remaining vertices and the center. The space is deamed smooth if predicted values and sampled values are within a configured tolerance (residual). Essentially Quick “drills in” to a parameter space until it determines a region is smooth.

The History of Quick - Mr. Rick Moore User:Rick

Here at the PALM lab I am tasked to generate and work with fairly large data sets to support our fatigue research. These large data sets are a result of cognitive model runs using variations of parameter combinations. For example, three parameters ranging from 1 to 100 with a step of 1 will result in 100 * 100 * 100 = 1,000,000 model runs and associated data files-- unless of course you do something more clever.

There are many approaches to cutting down the number of permutations and model runs. For example, I have heard favorable comment from a colleague regarding genetic algorithms, but have no personal experience to speak of. Some brief investigation on the web suggests that they deserve more scrutiny when I get the time.

Another popular approach that we did spent some time on was the gradient descent. After running thousands of gradient descents using different seed approaches and algorithm variations, it occurred to me that a more global view of our data was required-- the gradient descents just weren't bearing usable fruit.

So, late one Friday night I started tinkering with some code to combine an adaptive mesh with a gradient descent. There is a lot of overlap between the two approaches and it seemed like there was some opportunity to do get the global perspective of the adaptive mesh with the local optimization of the gradient descent.

Well that was a flop, but I wouldn't characterize it as a waste of time. The result was a very simple adaptive mesh, and I never really had time to work out how to integrate the gradient descent. The short story is that the adaptive mesh did what we needed at the time, so I stopped there and "Quick" was born.

Quick works about like any other adaptive mesh: You provide it with two vertices of a hypercube and Quick will sample the remaining vertices and the center. If the space is smooth, we can predict the value of the center vertex based on the corners. Quick does this and subtracts the sampled value from the predicted value to compute a residual. If the residual is greater than the configured amount, then Quick will break the hypercube into smaller hypercubes and repeat the process in the smaller spaces. Essentially it “drills in” until it finds smooth spaces.

Although the adaptive mesh algorithm is simple, it works, and always seems to be improving. In some ways I would suggest that the main value of Quick is not the adaptive mesh itself, but the architecture around it which was designed with distributed computing in mind. This is what made it viable for BOINC and the high performance computing clusters and filled a long empty gap in our tool chain.