Archive for March, 2009

Review of OmniGraphSketcher

March 26, 2009 at 4:14 pm · Filed under software ·Tagged , , ,

Last night I downloaded OmniGraphSketcher and gave it a test drive.  I’m a huge fan of OmniGraffle, OmniGroup’s diagramming program, so I was curious to see what their new graphing program had to offer.  In short, I like the usability that it inherited from OmniGraffle, but they need to make several improvements before I would even consider paying them $29.95.

For years I’ve been searching for a graphing platform that helps me quickly create Tufte-quality graphics.  I’ve had the best luck with programming-based environments such as NodeBox, Processing, or PSTricks (within LaTeX).  Back in 2000 I even wrote my own framework called TexLogo, which was a language and interactive system for illustrating Latex documents with logo turtle graphics. These frameworks are all drawing programs with an API.  As such, they give you the finest level of control with the unfortunate downside of being labor intensive.  Whenever you use them you risk diving down the rabbit hole.

The other end of the spectrum are programs that easily produce bad or misleading graphs.  Excel and gnuplot easily crank out ugly graphics.

So I like OmniGraphSketcher’s approach.  The program mixes hand-guided drawing with x-y data coordinate locations.  The default result is clean and sharp, just like diagrams that come out of OmniGraffle.  Unfortunately it’s not a finished product.  Specifically, I need it to include the following:

  1. Units other than foating point numbers.  Most importantly, they need to add support for dates.  You can’t draw a time series graph with the program.
  2. Titles.  Yes, you can double click to add a label, but there’s no built in support for title or sub-titles.
  3. Legends.  This can also be done manually, but they could facilitate it so that you can link data points or series with a legend.
  4. More options for the axes.  For example I’d like the option to only show tick marks.  And I’d like the ability to only show specific tick marks.  I don’t want to be forced to use evenly spaced tick marks.

If the OmniGroup developers make these improvements, then I’m likely to send them thirty bucks.

Here’s a quick example graph that I threw together.

omnigraphsketcher_visits1

Here’s something closer to what I’d like that I made with OmniGraffle.

omnigraffle_visits

Comments (3)

Randomized optimization algorithm

March 22, 2009 at 10:37 pm · Filed under Python ·Tagged ,

I thought of a simple randomized optimization algorithm today while I was working on a problem. The algorithm’s working well for me, and while I doubt it’s truly novel, it’s new to me.

Broadly speaking, I’m searching for for a vector of floating point numbers that optimizes my objective function. My objective function is complex enough to be thought of as a black box, and therefore there’s no closed-form gradient function. Although the function has no local minima, the parameters are subject to a number of boundary conditions.

I’m coding in python, so at first I tried using scipy.optimize.fmin. In the function passed to fmin, I returned a large number if the given vector violated the boundary conditions. Unfortunately those large numbers created singularities that caused fmin to get stuck. There are other functions within scipy.optimize that might work, but it wasn’t clear how to use them. This motivated me to code up my own algorithm.

The general approach is simple: at each step generate a random neighbor. If that neighbor is superior to the current point, move to it. I generate a neighbor by perturbing each element of my vector by some fixed delta. Specifically, I multiple a vector numpy.random.random_integers(low=-1, high=1, size=mysize) by delta. Then I normalize the result. Lastly, I find the closest vector point that satisfies the boundary conditions.

This has the succinctness that makes many randomized algorithm appealing. In addition, on my problem, its performance was better
than I expected. Two enhancements made it exceptional.

First, if I generate too many neighbors without finding a superior one, then I decrease delta by a factor of 10. The algorithm stops when delta drops below some threshold. This provides a natural transition between large, coarse steps for speed and small, fine steps for precision.

Second, when I’m at point x0, and I generate a superior point at x1, then I search for increasingly superior points along the trajectory from x0 to x1. Doing so yields the benefits of a poor man’s gradient.

example_search

The figure gives a rough illustration of the search technique. We start at a point with value 8, and randomly pick a neighbor using delta 4. Next we search along that trajectory and find a better point with value 4. Once again using delta 4 we pick a random superior neighbor. Note that we hop over a boundary point when we move there. Unfortunately we don’t randomly generate a better neighbor with delta 4 from that point (even though one exists). So we switch delta to 2, and continue the algorithm.

My code is currently embedded with logic that’s specific to the problem I’m solving.  If I abstract it out, I’ll post the code here.  I’m curious to hear from anybody else who’s implemented a randomized optimization algorithm like this one.

Comments (1)

Follow

Get every new post delivered to your Inbox.