Flirting With Models

I got bored because I moved into a new apartment and had no internet or television access to do any work, so I decided to write a Particle Swarm Optimization implementation in Ruby. It ain’t fast, but it seems to get the job done.

# Alter the array class to add a method that allows us to use our comparator
# to find not only the max value, but also it's index
class Array
  public
  def comparator_with_index(comparator)
    return nil unless self.size > 0
 
    m = self[0]
    mi = 0
 
    self[1..self.size-1].each_with_index { |e, i| if send(comparator,e,m); m = e; mi = (i+1); end }
    return [m, mi]
  end
end #end Array definition
 
class ParticleSwarmOptimization
  private
 
  # A private vector implementation
  # Basically just adds a + function to Arrays
  class Vector < Array
    def +(other)
      raise "Vectors must have same dimensions" unless self.size == other.size
      ret = []
      0.upto(self.size-1) { |i| 
        ret[i] = self[i] + other[i]
      }
 
      return ret
    end
  end #end Vector definition
 
  # Our particles
  class Fly
    attr_accessor :position, :velocity, :current_fitness
 
    # Define the feature dimensions, feature limits, et cetera
    def initialize(feature_dimension, feature_limits, inertia, cognitive, social, comparator)
      @position = Vector.new(feature_dimension)
      @velocity = Vector.new(feature_dimension, 0)
 
      feature_limits.each_index { |i| 
        @position[i] = feature_limits[i][0] + (feature_limits[i][1] - feature_limits[i][0]) * rand
      }
 
      @current_fitness = nil
      @fitness_max = nil
      @position_max = nil
 
      @inertia = inertia
      @cognitive = cognitive
      @social = social
 
      @comparator = comparator
    end #end initialize
 
    # update the best local fitness
    def update_fitness!
      if @fitness_max.nil?
        @fitness_max = @current_fitness
        @position_max = @position
      else
        if send(@comparator, @current_fitness, @fitness_max)
          @fitness_max = @current_fitness
          @position_max = @position
        end
      end
    end #end min_max_compare!
 
    # update the position based on local and global best, as well as momentum factors
    def update!(global_best_features)
      @velocity.each_index { |i| 
        @velocity[i] = @inertia * @velocity[i] + 
                       @cognitive * rand * (@position_max[i] - @position[i]) + 
                       @social * rand * (global_best_features[i] - @position[i])
      }
 
      @position = @position + @velocity
    end #end update!
  end #end Fly definition
 
  public
 
  # The big function
  # Inputs:
  #   population_size: Number of particles you want in the swarm
  #   feature_dimension: How many features are in the problem
  #   feature_limits: What range are the features defined in (for initialization only)
  #   max_iterations: Number of iterations to perform
  #   inertia: How fast the particle will move in its current direction
  #   cognitive: How fast the particle moves towards its own personal max
  #   social: How fast the particle moves towards the global max
  #   comparator: A function that takes the fitness of two particles and determines which is 
  #               'better'.  Takes the form of comparator(x,y), and returns true if x is 
  #               'better' than y.
  #
  #   Returns the global best fitness and feature set
 
  def self.optimize_over(population_size, feature_dimension, feature_limits, max_iterations, 
                        inertia, cognitive, social, comparator)
    raise "Feature limit definition must be equal to feature size definition" unless feature_dimension == feature_limits.size
    raise "Block must be provided to optimize features" unless block_given?
    raise "Comparator must not have identical name of Array methods" unless !Array.instance_methods.include?(comparator.to_s)
 
    # initialize our population
    @population = Array.new(population_size)
    @population.map! { Fly.new(feature_dimension, feature_limits, inertia, cognitive, social, comparator) }
 
    global_best = nil
    global_best_features = nil
 
    iteration = 0
    begin
      # find the fitness of each fly and see if it is a local best
      @population.each { |fly| 
        fly.current_fitness = yield fly.position.clone
        fly.update_fitness!
      }
 
      # find the best fitness of the current swarm
      best_fitness, best_fitness_index = @population.map { |fly| fly.current_fitness }.comparator_with_index(comparator)
 
      # check to see if it is a global best
      if global_best.nil?
        global_best = best_fitness
        global_best_features = @population[best_fitness_index].position
      elsif send(comparator, best_fitness, global_best)
        global_best = best_fitness
        global_best_features = @population[best_fitness_index].position
      end
 
      # update each fly with the global best feature set
      @population.each { |fly| 
        fly.update!(global_best_features)
      }
 
      iteration = iteration + 1
    end while iteration < max_iterations
 
    return [global_best, global_best_features]
  end #end optimize_over
end #end ParticleSwarmOptimization definition

And some example code on how to use it…

def maximize(x,y)
  return (x > y ? true : false)
end
 
def minimize(x,y)
  return (x < y ? true : false)
end
 
fitness, value = ParticleSwarmOptimization.optimize_over(50, 1, [[-10, 10]], 4000, 1, 2, 2, :minimize) { |x| 
              Math::cos(x[0]) * Math::exp(Math::sin(x[0])) * Math::sin(x[0])  / 1.5 }
 
puts "x: #{value} y: #{fitness}"

I found a cool paper which discusses using multiple swarms, and using Darwinism to evolve swarms. A cool concept.

I wrote a post a little while back that discussed the idea of moving from using one language for a project to taking a very vertical approach, and writing the subsystems of the application in the language that best suited it. Ideally, you wouldn’t even need to restrict the languages in any way. Maybe you wrote a fault-tolerant application in Erlang that you wanted to add some meta-programming capabilities to. Perhaps you could rub in a little Ruby. Then maybe you wanted to give it a front end using C#. Need access to the GPU? Throw in some CUDA code. Basically, use the language that makes the job the easiest.

Well, it seems we are getting closer. Sort of. I just re-discovered Thrift, a very cool Apache incubator project from Facebook. Basically, it allows you to create structs and services (basically, structs and functions) in Thrift and access it from almost any language (C++, C#, Cocoa, Erlang, Haskell, Java, OCaml, Perl, PHP, Python, Ruby, Smalltalk). Now maybe this isn’t a huge leap towards letting you use multiple languages within the same application, but if you don’t mind interprocess communication, this might work. If someone were to figure out a way to make separate processes co-mingle like light Erlang threads, we would really be getting somewhere. Imagine writing your models in Ruby, your Controllers in Erlang, and your Views in C#, all running in a sandbox and passing constant object definitions. Tasty.

Not necessarily earth-shattering, but very cool nonetheless, if you ask me.

As an intern at an independent consultancy firm, I had the privilege to interview dozens of money managers. They were all intelligent and well-intentioned individuals. After all, the better their clients did, the better they did. However, when all was said and done, I came to one conclusion: it is not surprising that most actively managed funds underperform passive investing in the benchmark.

Firstly, fees automatically put an active manager at a disadvantage. It is like starting a foot-race several meters behind. This not only has a very real and tangible effect on returns, but may also have a psychological affect on managers. Not only do they have to out-perform the market, but they have to out-perform the market and fees.

Secondly, style boxes. Morningstar may have been well intentioned in their invention, but style boxes are the absolute worst thing to happen to investing. Ever. While it allows clients to discover talent in a style that they are looking for exposure to, it locks managers into specific styles. As we all know, markets and economies move in cycles, and not all time periods are good for all styles. However, as investors paying fees, we demand that our managers not only retain their exposure to their style (that is what we are paying them for, after all), but to be invested 100% of the time. This is where we, as investors, shoot ourselves in the foot. We effectively are handcuffing our managers. With these restrictions, we are saying that we as investors know more than the managers do. Truthfully, who knows better than the manager whether it is a good time to be employing their style strategy? Perhaps it just isn’t a good time to be buying small-cap value? But with our restrictions, we force our managers to be in 100% of the time.

Next, as managers get more assets under management, they run into liquidity issues. It takes longer for them to build and get out of positions. It also limits the companies they can invest in. A pure equity investment manager with several billion under management will never truly add alpha by picking companies, because he either has to purchase hundreds of different equities, or purchase large cap stocks. In either way, his bets become strictly macro-economic. This further limits the time-frame the manager can invest in. Eventually, most traditional mutual fund managers just end up with an S&P 500 or Dow Jones look alike.

With these factors stacked against traditional mutual fund managers, it is no wonder that they cannot out-perform passive investing. As investors, we effectively guarantee that result by the restrictions we place on them.

In my last post, I wrote about a simple method to determine if your model is statistically significant by seeing if it “out-performs” random. There are a lot of ways to measure your model’s performance. They start as simple as measuring return, and only get more complex from there. After my last post, a friend of mine wrote me an e-mail about a method he uses to test the performance of his model that I thought was interesting and would pass along.

First, we determine what the model is trying to capture. What we would then do is create a ‘perfect’ system, by looking ahead into the future. We then run this perfect system on data to generate what he would consider ‘perfect’ signals.

We can then create fitness functions to measure your systems performance against the theoretical perfect performance. We might, for example, use a ‘time matching’ measurement, where we measure how closely our system’s trades match those of the perfect system. If our model has the same signals for 95% of the time, we know we are probably doing something right.

The power of this system lies in creating accurate and telling fitness functions. Preferably, your fitness functions should give some way to measure statistical confidence levels.

Cool concept. One to throw in the bag.

When developing a quantitative model, I typically break my process down into seven steps. I follow the standard outline that econometricians use when developing models.

Theory
The very first step to take in developing a quantitative system is defining the underlying theory behind the model. If we have recognized a phenomenon in the markets that we feel we can exploit, we want to ask ourselves why the phenomenon exists, and more importantly, will it continue to exist? Effectively, what we are asking is, “if this idea works in practice, does it work in theory?” In this stage we develop a fundamental understanding of what we will be modeling and why we are modeling it. By taking the time to define the underlying theory, we can avoid ‘data-mining’ strategies that have no defendable basis.

Data Collection
In the second stage, we collect data that is relevant to our model. Availability of data has a large influence on how the model is designed, so we must keep in mind not only what information we have available now, but what we will have available going forward.

Specifying the Model
In model specification, we begin outlining how the data we have collected will influence the results of our model. In econometrics, this may be determining whether or not certain data elements should have a positive or negative affect, or what form the data should be in (normal, logarithmic, exponential). More broadly, we are trying to determine how to translate the data we have collected into signals we can use.

This is the step that the most time will be spent on. Modelers should do their best to keep their model as simple as possible, using Occam’s razor at each turn, to prevent over-fitting. We want to ensure that the model is as robust as possible while using as little input as possible. John von Neumann once said, “with four parameters I can fit an elephant, and with five I can make him wiggle his trunk.” The goal here should be to create the simplest model possible that still explains the underlying theory.

To ensure that models will work over a large input range, as many parameters as possible should be made adaptive. This means that instead of changing them by hand, the model should change them itself based on the data it is receiving. This helps the model adapt to new conditions.

Estimating Results
After the model has been specified, tests should be run on ‘out-of-sample’ data. Ideally, we would like to perform tests on as much data as possible. What is important is that the data we test on should not be the same data we used to help specify and determine our model. We want to see how well our model works on data it has never seen before. If it does extremely poorly, we should attempt to re-specify our model.

Running Diagnostic Tests
Diagnostic tests in Econometrics often deal with determining whether certain features of the model are statistically significant, or whether we are allowed to make certain assumptions. For example, is our error term white noise, or is it auto-regressive? Does our data have any breaks? Are we using too many parameters to fit our data? What is our trade-off between bias and goodness of fit? While many of the same questions can be asked in developing quantitative investment methods, I choose to use this section of the development cycle to run general tests that quantify the robustness and performance of our model.

Just because a method is mathematical does not mean it is precise. Applying a numerical method to a set of data will result in numbers — just not necessarily meaningful ones. It is important, then to run tests to ensure that our model is robust and statistically significant. We should ensure that our method is available over a large range of parameters, and that the model succeeds in different time-frames and markets. Sometimes, we even would like to test to make sure that our mode does not work on different markets and time-frames, if our theory calls for it. If we have written a model to take advantage of certain liquidity occurrences in forex markets based on time of day, we would not expect it to work on U.S. equities, because it does not follow our underlying thesis. If it does, than we should seriously rethink our theory or our model. On the other hand, if we are running a breakout strategy on U.S. futures, we should expect it to work over several time-frames and futures markets, unless we are specifically taking advantage of certain qualities of a specific instrument, which would then be defined in our theory.

If we find that our model fails our diagnostic tests, we would want to return to specifying our model.

Run Hypothesis Tests
After developing a model and running diagnostic tests, we want to determine whether our not our hypothesis is true. Ultimately, we want to ask, “if it works in theory, does it work in practice?” Sometimes a theory may not take into account realities such a commission and slippage which may reduce the edge of a certain strategy. Our hypothesis, more often than not, is quite simply that the model will provide a methodology for creating alpha. Ultimately, this tests comes in two parts. First, does it generate the returns we are looking for? Second, is it statistically significant?

The first is fairly easy to perform. The second one takes a bit of creativity. One of the best tests I have found is to simply determine whether our model is significantly better than ‘random.’ Let’s assume that your model outputs 1, 0, or -1 for buy, neutral, or short signals. When you run your model over the data, determine the percentage of 1s, 0s, and -1s that are in the output. Then, generate several thousand random outputs with the same distribution of 1s, 0s, and -1s. Determine the theoretical returns of these systems. If your system does not decisively outperform the vast majority of these systems, it is more than likely that your model simply stumbled upon a method that gives the right distribution of 1s, 0s, and -1s instead of actually modeling the underlying data.

For example, let’s say I had data on the S&P 500 from 2003 to 2007, and I am attempting to generate monthly buy or sell signals. Let’s say I start with a simple system that always generates a buy signal. What we would find is that even though our model performs extremely well, it does not beat random. Every other random model would also have a distribution of 100% buy signals, and give an identical return. What we have discovered, then, is not that our model necessarily appropriately describes the data, but rather chose an appropriate distribution of signals to maximize return.

Conclusion
Now that our thesis has been defined, our model specified, tested for robustness, and successfully shown to not only generate positive returns in a statistically significant manner, we are ready to run it in the wild — and with confidence; we have successfully developed a model that is defendable both in theory and in practice!

Random programming libraries that I have discovered in trying to solve some problems lately…

C++
Acedia: acedia is designed to be an easy to use C++ library. It provides an ERLANG like actor implementation with message passing and pattern matching. It’s main goal is to support development of distributed software – also across a network.
POCO: The POCO C++ Libraries (POCO stands for POrtable COmponents) are open source C++ class libraries that simplify and accelerate the development of network-centric, portable applications in C++.

Ruby
Sinatra: Embeddable website DSL
Nanite: Nanite is a new way of thinking about building cloud ready web applications. Having a scalable message queueing back-end with all the discovery and dynamic load based dispatch that Nanite has is a very scalable way to construct web application back-ends.
Journeta: Journeta is a dirt simple library for peer discovery and message passing between Ruby applications on a LAN.

That’s all for now. I’ve been working on some interesting stuff, developing a client registration and authentication system. I started out in C++ using boost::ASIO to handle server connections, but then I just got annoyed, switched to Ruby, and have been running along ever since. I am using Revactor (with a few personal tweaks in the code) to handle my components, SQLite3 for a simple database (though, I might have to switch to MySQL for production), and Sinatra for a web-interface (running on Thin with Shotgun). All in all, I must say that simply plugging in working components instead of having to develop the resources makes production so much easier… As always, hardware is cheaper than programmer hours.

Speaking of which, why did I not notice Amazon’s Auto Scaling and Load Balancing features before? If you don’t have the hardware resources to build your own cloud (Eucalyptus with Xen), Amazon really does seem like a very cheap alternative. I mean, think of all the money you save not having to hire I.T. guys to figure out why your harddrive failed in the middle of the night. Amazon does it all for you!

Hopefully, some sort of Cloud Computing standard will come out soon. The only current problem with Amazon’s model is that it doesn’t give the clients any leverage. Start using Amazon and you can’t make the threat to leave and go to Google (well, easily at least). Worse yet, if Amazon goes out of business, you are in a world of hurt. Eucalyptus adopted the Amazon scheme, so at least there is a bit of leverage saying that you will just buy your own hardware — but it would be much better if we could get some pricing competition going on.