Back from China Trip

Well I'm back from a month long holiday in China. The goal was to spend time with my wife's family and then relax on a sort of honeymoon.

We spent the first two weeks in Beijing (east of china), staying in a family apartment in Nanmencang Hutong (near ghost street, the military hospital, and the old grain warehouses from the Yuan Dynasty), only 20 minutes walk from Tiananmen Square and the Forbidden City. We visited many of the sights including the Great Wall at Badaling, the Summer Palace, the Forbidden City, Beihai Park, the Temple of Heaven, the Bird's Nest and Water Cube, and lots of markets (I bought mostly clothes, gifts, and a cool microlight helicopter for pocket change).

The markets were really interesting from the perspective of the selling culture. Every purchase involved a little dance of the seller trying to talk up the product and extract as much cash as possible from the buyer, and the buyer faining disinterest in the product, questioning the quality, and attempting to achieve the lowest price possible. Too aggressive, and the dance abruptly finished. From trinkets to bags of fake polo shirts to fake watches, a balance had to be negotiated to ensure the seller got their margin and the customer walked away happy. Once you achieved a purchase, tested each others metal, you could then bargain for other items the seller was pushing with a lot less resistance.

The interesting part for me was the aggressiveness of the sellers to push their wares, from yelling at you to grabbing you, to putting products in your bag and asking for the money. A 'get a sale at any cost' mentality. I was also very impressed that these young girls could switch languages and be functional (persuasive) so rapidly. Mandarin and English were the main two, but I was cases of girls trying Russian, German, and Spanish. More than that, I could clearly see differences in persuasive strategy between nationalities. More coy and playful with European men, child like to Russian men, confrontational with Chinese women, etc.

Besides the the tourist thing I was watching out for technology and captured some observations:

• Mobile phones were everywhere from the tourists, to the shoppers in department stalls, to grandmas riding bicycles through the hutong
• Most phones were simple handsets, although i did see a handful of unrecognizable smart phones and even a few iPhones.
• Sales staff in small shops and department stalls glued to PC's either watching divx TV shows or on chat clients. I learned that chat is used a lot for direct Q&A with stores. We even used it ourselves to ask questions about flights and tours.
  
• A friend spent some time in a poor village where a boy used the hold music on his telecom service number as a radio (an interesting case of exaptation)
• I saw a heap of fake iPhones in the markets although failed to make the effort to see any in action
  

October 1st was the national day and marked 60 years since liberation (communists oust the nationals in the Chinese Civil War A.K.A. war of liberation). In the preceding weeks, security at train stations, tourist sites, and in the CBD (down town) was ramping up with x-ray bag checks and soldiers on street corners. Around the square where the action took place there were a clear and strong military presence - I'm talking big guys waring armor with big scary guns. The city went into lock down the day before and even the airport was shutdown on the day of the celebration.

We watched the parade on TV (city residents were instructed to stay indoors, or so I was told) and could see the jets and helicopters buzzing through the city just before they appeared on the telecast. It was quite a thing to watch, and we all had fun watching, eating, and drinking the local beer.

After Beijing we went to Xian (middle of china) and saw the Terracotta Warriors, climbed Hua Shan, and played around in the city for a few days including a bicycle ride around the old city wall which was great fun.

Finally, we spent just under a week in Lijiang (south west near Tibet) in Yunnan province. We stayed in a quiet hotel right in old town. Yunnan has some of the most beautiful geography in China, and Lijiang has one of the most beautiful vistas in the country (at the black dragon pool). Old town is an ancient village that has been converted into a tourist town with old cobbled roads, each with a little canal. At night, the town is lit up with lanterns, and the restaurants are accessed with little bridges - all very romantic and relaxing. We climbed the Jade Dragon Snow Mountain (4500 of its 5500 meters, yes they sell oxygen up there), visited the Tiger Leaping Gorge, and went boating and horse riding in a near by valley.

A thoroughly relaxing time all in all, and I found some time to catch up on some reading and science podcasts which I should blog about soon enough. It's good to be home.

Competition hacking with Ruby and Objective-C

During August, github ran a recommendation engine contest. An objective of the contest was to generate a number of open source projects (on github) providing white label recommendation systems (a noble goal). A suite of github user data was provided including ~120K repository definitions and a corpus of nearly half a million user-repository relationships. Entries had to be hosted on github and released under an open source license. Assessment involved making predictions against a test set of more than 4700 users of between 0 and 10 recommended repositories. Submission involved setting up a post-commit hook for your codebase and committing a results.txt to your repository. The results file was automatically evaluated and you score updated on the competition leaderboard.

I tracked the announcement of the competition and associated commentary. Around mid-August I got an itch an decided to hack on the contest.

After downloading the 4MB dataset, I started by writing some ruby code to parse the files and load them into an RDBMS. Halfway through munging (active record outside of rails) I realized the stupidity of the approach. I was managing for (the unnecessary) scarcity of memory. Even with bloated datatypes, the 4MB of provided data could easily fit into main memory many times over. After having participated in many of these AI-programming competitions in years past, I felt severely out of practice an quickly pushed on.

I chose ruby because I felt I still had much to learn about it and hadn't had a real chance to use it in anger, other than some rails hacking. I bashed out some code to parse the files and build a simple data model in memory. I started processing the data model with a k-NN toward making basic predictions and quickly hit the wall. I got some strange results with my hashmap's and began to mistrust my assumptions about Ruby's dynamic typing, resulting in lots explicit casts and other savage hacking - an artifact of my inexperience.

The real problem was speed. Runs were taking waaaay toooo loooooooong on my 1920's era iBook. I started looking into optimizing the code, compilation options and even tried running on updated and optimized builds of the Ruby interpreter. I got improvements, but not enough.

The thing about prototyping is that you need to hack around to find a stable definition of the problem your solving while defining your solution. I could have hacked together my algorithms in C and called them from ruby, but I was not confident on exactly what I wanted to do. Having been breast fed on ANSI C, I had a feeling for how long these small files should take to load from disk and how long the should take take to crunch for crazy n^2 experiments. I dropped tools and switched to another language I've been looking for an excuse to use in anger, Objective-C.

Writing header files in C++ always felt like duplication of effort to me. Not only did I get this feeling with Objective-C, but it was far worse. Coming directly from ruby, the Objective-C verbosity was distressingly laughable! I had used Objective-C before, but I was improvising then, rather than directed and problem solving. Finally, the Objective-C standard library (Cocoa) is painfully minimal compared to Java or C++ (at least for simple things like string manipulation and collections).

I hung in there. I got used to the bracket syntax and the approach memory management was quite familiar. I aggressively used memory pools in data processing experiments, although I often felt the desire to peer into the framework code to see exactly what kind of wasteful things it was doing in the name of convenience. I had the second edition of Kochan's "Programming in Objective-C 2.0" open on the desk - which I found almost useless. What I needed was a API description and a summary of gotchas - basically an O'Reilly book. As I mentioned, my machine is a piece of shit, so I use VI or textmate, not XCode. I tried to use the Apple interface to the Cocoa API docs online, but their organization was useless (learn from javadocs already!). I resorted to googling class names and my ad hoc functional requirements to figure out how to do things.

Although I'd read some text books on datamining (like 10 years ago) and wrote some plugins for WEKA, I knew very little about recommendation systems and collaborative filtering. I'd followed the Netflix competition, reading the papers and such (I even ran some simple stats over the provided dataset loaded into a Postgresql instance). Also, I'd read up on SVD before for some text processing hacking, and knew it could have a role to play in feature detection.

My general approach involved thinking hard about the data and the domain, proposing indicators and heuristic predictions, and testing them via direct submissions. I partitioned indicators and heuristics at three levels: user, group (using a k-NN), and global. I tried rank based indicators (for example: global repository watch rank) which performed poorly. I then tried some probabilistic indicators (for example: probability of this user watching a repository with this owner) which got much better results. I tried indicators to confirm/disapprove assumptions then played with the weighting factors for combining them.

I was in the competition to hack (string code together outside of work) and to learn. To learn more about these languages, and to learn something about practical collaborative filtering (building one from scratch). The beauty of this competition was the openness. Not everyone checked in code during the competition, submitting just the results.txt. Others checked in most or their entire code base (I sure as hell did), and this provided an opportunity to poke around the indicators and algorithms used by others.

For me, the most useful lessons from poking around others code was how to structure a flexible recommendation pipeline. Algorithms are awesome, and there is a lot of work in tuning them to the dataset, but having well-structured recommendation pipeline allows you to add in new indicators, heuristics, algorithms and pre-processing steps with minimum disruption. The readme associated with jeremybarnes' project was very insightful for both the algorithms one should be thinking about, as well as the concerns on the information processing pipeline one should be building.

The pipeline I converged to was something like the following:

1. Parse sources, build first order data model
2. Second order data model processing (stats, clustering, etc)
3. Process test users one at a time
4. Generate a candidate set (sub-set of all possible recommendations)
5. Filter candidate set
6. Apply indicators (blended, voting, whatever)
7. Sort by scoring, and recommend

There may be some generality in this pipeline, although it's clearly specific to smalls scale recommendation engines, not for anything of scale (at least not in this form). Also, serializing the results of second order data model processing is also a great speedup.

I thought I could get some gains by building deep prediction models. Objective-C provides a convenient bridge to Java by booting an in-process JVM. I used this to hack in some classifiers I prepared in WEKA into my pipeline with no appreciable success. It was a fun exercise, and I tried a number of decision tree algorithms and configurations. I'm sure with the selection of appropriate predictive indicators at an appropriate level (cluster or user) that the approach would be great.

Toward the end of the project I started reading introductory papers to collaborative filtering and recommender systems. I'd had plenty of contact with vector space processing, so I was aware of dimensionally reduction approaches and also expected an array of vector distance measures for clustering. I was aware of the phrase 'item-based recommendation' but the realities of the approach were a lot more apparent after piecing together my toy system.

Next time I'll hit the ground running:

• Use C++ and using in line C functions for raw power and maybe script the pipeline, experiments, or indicator weighting using something fun like Ruby.
• Use SVD or similar to dimensionality reduction and use the resulting features for user and item clustering. I'll also use an off the shelf implementation.
• Create an explicit offline test set and an automated testing process. Automation is key here, and cross-validation of the offline test set with statistical tests for significance will be a powerful addition.
• EC2 server time, contingent on an robust test automation process. EC2 is cheap and worth the pocket change needed to cover a competition or pet project like this one.
• Test the effects of different clustering algorithms (KMeans, raw k-NN, arrays of distance metrics)
• Be more scientific regarding the testing of indicators and the testing of indicator combinations. I recorded results, but I could have been more careful, tested more things, and deduced trends that were only found by bugs or by reading other peoples submission code.
• Visualize the dataset and indicator trends, using R or at the very least WEKA or excel.
• Optimize indicator combination using gradient decent or a genetic algorithm.

As the deadline approached I tried all kinds of random hacks and managed to get a boost to just over 40% (my personal goal), and then on to 48.57% correct recommendations. I managed to place 15th the night before the competition closed (Aust. time), although ultimately finished with a place of 18th. It seemed that a number of people got involved late in the game using blending approaches on the leader's results files. Fun I'm sure, although not in the same league.

You can see my code (with a summary of my strategy in the readme), a history of my submissions, and the overall competition leaderboard. Github have not yet officially finalized the results and selected a winner.

I had fun, and the project was an excellent catalyst for me to get back into my off-hours programming groove. I'm kicking myself for not getting off my ass and at least participating in the Engine Yard competition or the Mario AI competition, the latter of which I believe is still open (second round).

Setting Old Projects Free

I've been pushing my source code to the web since I started pulling together game mods and apps I thought others could learn from or use. About a year ago I got together with a bunch of guys and hacked on a bunch of webapps with lofty ideas of starting a startup. One year on, only two apps are still ticking along (spicyelephant and 5st), the rest are defunct and have been rotting in private SVN repositories. What better way to do a final justice to the hard work we put in than by and give something back - by open sourcing the projects.

Over the last few days I've pushed three of the mayhem method projects to my github account. Like a free garage sale, have a browse below - maybe there is something you will find useful.

Screen Sponge
Screen Sponge is a movie management web site where you manage all the movies and television shows you have, want, and have seen. Screen Sponge provides an online community, connecting your broader circle of friends to trade shows they have that you want, write reviews, and discus the shows you love.

Comment Is King
"...the conversation has left the blogsphere", meaning that increasingly the conversations regarding online content are occurring offsite. Comment is King is an online tool for blog authors and other content producers for finding and participating in the broader conversations around their content from disparate services such as Reddit, Digg, Delicious, FriendFeed, and Twitter.

gantDB

gnatDB is a lightweight personal data tracking service that encourages users to record everything and add meaning to collected data at some later date. gnatDB collects daily data points (data, context, and tags), for example: 10 pushups, exercise, arms and 5.50 hamburger, food, purchase, junk.

I have also pushed some of my other personal project from the start of last year, as follows:

Human TSP Solver
The humanTSPsolver site was built to investigate the question: Can human spatial intelligence be harnessed to solve instances of the Travelling Salesman Problem? The approach taken involved: (1) partitioning TSP instances into sub-problems, (2) allowing users to make contributions in the context of the sub-problems, and (3) aggregating the contributions into a holistic solution. Note: a database dump of one years worth of user contributions is included in this project!

Thick Profile
Thick Profile is an experiment into the preparation and exploitation of a deep digital profile of an online user. The approach involved constructing a model of a user based on the users specification of written contributions such as websites, technical reports, research papers, and blog posts. The development effort involved the preparation of code to parse such data sources, construct a model, and visualizing that model as a graph or tag cloud.

I decided to release all code under the less-restrictive MIT License, especially after the issues I had with companies wanting to exploit some of my other projects on sourceforge released under GPL and now LGPL.

I am a big fan of github. It is slick, simple, and unlike google code that also fits this bill, it uses git! I expect to use github for small-public work going forward. Like hacking with Ruby, it is a pleasure to use.

What is a good optimization algorithm? A data-driven method for algorithm selection

I have been writing a book on unconventional optimization algorithms (for the lack of a better well known name). The phrase I use is "inspired algorithms", although people in the know may recognize the techniques drawn from fields such as computational intelligence algorithms, metaheuristics, biologically inspired algorithms, natural algorithms, biomimetic algorithms, and others. These are the type of global optimization methods used when traditional techniques are unavailable, ineffective, and/or do not meet the broader constraints of the problem (need a good enough result and need it fast). They are also typically easy to understand and interesting to investigate.

My vision for the book project has centered on producing a reference text, where a large and diverse set of algorithms (50+) are presented in a useful and consistent way (inspiration, strategy, procedure, configuration heuristics, etc.). Additionally, I have intended to provide working code for each technique (ruby), hoping that the final text would be useful to interested amateurs, programmers, and research scientists. Really, it's a book I'm writing for the enthusiastic ignorant kid with an aptitude for programming I was 10 years ago.

Problem
I have 'started' writing this book more than 6 times over the last year, and some incarnations have made it online, although at this point are not representative of what I am trying to achieve. In my most recent effort, I started by questioning the set of algorithms I'd previously selected to write about. I'd originally listed all algorithms I could think of and selected a subset of 50 that I felt were sufficiently diverse, interesting, and useful. The decision making process was purely subjective, based on and biased by my experiences, exposures and hacking.

This challenge lead to the question:

Is it possible to select a diverse, interesting, and useful set of inspired algorithms using a simple data driven method?

An ideal selection method would choose algorithms based on metrics that captured relative algorithm efficiency, efficacy, quality of research, and maybe even scope of innovation. Algorithms may ideally be grouped by relative similarity in computational process and problem class suitability. Unfortunately, many if not most of such measures are intractable, especially for the amount of time I'm willing to put in and for the expected benefit such a list would offer.

I need a metaheuristic for preparing a list of metaheuristics.

Superficially, the problem of preparing a set of algorithms to write about in a book is very much like the problem of selecting a set of algorithms to apply to a given problem (presuming suitability criteria listed above are met - that you are resorting to an unconventional search algorithms for defensible reasons). Such algorithms are (typically in my experience) easy to describe, easy to understand, easy to program, and easy to get some kind of solution quickly. The algorithms one selects to apply are strongly biased by what the books, colleagues, and experiences one has had with such algorithms, much like the bias a guy like me has in selecting algorithms to write about in a book. This suggests that a data driven algorithm selection method may be useful for a practitioner trying solving a problem.

This further raises the question as to how to assess a produced 'set of selected algorithms'. Why is one set better than another? Is it the number of books sold? Is it the number of in-references achieved after 2, 5, or 10 years? If one were solving a problem and applying an array of techniques, is one technique better than another because it produced a slightly better solution? Are you sure it was coded correctly, that it was sufficiently tuned to the specifics of the domain?

Some 'algorithms' are more general methods than strict procedures. If one were considering array sorting algorithms, one could prepare an extensive list of known algorithms and compare each precisely by min, max, avg, etc computational complexity over resources like space and time. This is because such algorithms can be precisely described mathematically and then programmatically. I presume this applies to the so-called heuristic methods of fields like operations research and (linear, quadratic, ...) programming for the same reasons. This generally does not apply to so-called metaheuristics either because the field has chosen not to do so, or (as I think is more likely) because it is not possible because their generality is a core strength.

Nevertheless, comparing the resultant sets of selected algorithm may not be tractable, and if it is, it may not be meaningful.

Rather than walk away from this challenge, I decided to have a crack at it. I likely got it wrong, but wrong can be fixed and at least we'll (I'll) have a base for improvement (no doubt an axiom of the general fields that originally produced these algorithms in the face of hard optimization problems).

Method
I'll call this method the 'Google method' or the 'common usage' method as it somewhat resembles the principle Google use to offer suggested corrections to misspelled search queries, as well as their translation services. The principle of my algorithm evaluation and selection method is:

An algorithm or method is as good its name, as useful and interesting as it is abundant.

A good optimization method is used a lot, and people write about using it. Further, a method that is used a lot stabilizes into a canonical form and coalesces under a common name. A corollary of this assumption that relates to the previous discussion is that those techniques that are not well described or implement correctly are not used and do not propagate. They are simplified and re-communicated for use or lost in the ever increasing flood of new material.

An algorithm that is used (written about) is an algorithm that is useful (worth knowing about).

The proposed data-driven method involves 1) eliciting an extensive list of algorithm names, 2) selecting algorithm names in a consistent manner, 3) tallying the number of search results hits for the exact algorithm name across a number of domains, and 4) compressing the tally measure into an ordinal algorithm ranking metric. The set or sets of useful and interesting algorithms may then be drawn from the the ranked listing.

It feels like an algorithm popularity contest, because that is exactly what it is, although popularity is re-measured across somewhat bounded to domains. A thread of research on an algorithm may publish and/or perish irrespective of the methods inherent qualities, and that may be the core argument against the proposed method.

Experiment
Here is what I did (a few hours a day between Wednesday 29th and yesterday):

1. Wrote down all the algorithms I could think of, generally limited to algorithms for finding something in a domain (optimization or search) that broadly fit into the fields listed at the beginning of this post (excluding traditional heuristics like branch and bound and A* and popular computational intelligence fields like fuzzy logic and artificial neural networks).
   
2. I tweeted my followers and emailed colleagues to send me a listing of their top 10 computational intelligence and metaheuristic algorithms, where the definition of favorite was left open. When domain experts start talking about their favorite things about their domain, one should listen: the collected survey data is valuable. I originally thought that I could construct a list from this survey data alone, although the lack of volume meant that at best I could do (at this point) is use it to update the master algorithm list.
   
3. Normalized algorithm names to their full unabbreviated form. No acronyms wherever reasonably possible.
4. Assigned each algorithm a superficial grouping or kingdom (I thought for use in a book chapter structure) based on general observation and intuition. Kingdom names were generally based on the motivation for the methods strategy, including: evolutionary, immunological, swarm, physical, probabilistic, and stochastic.
5. Recorded the estimated-total number of search results for the exact algorithm name (quoted) in Google Web Search, Google Scholar Search, Google Book Search, Springer Search, and Scirus Search.
   
6. Calculated the relative algorithm rank metric as the sum of the normalized search result measures.
   

Results
The raw results including all data collected is provided in a Google docs spreadsheet (note: with multiple sheets/tabs), entitled simply Algorithm List.

Have a play with the data (if you're that way inclined) and postulate some improvements in the comments of this post. If their is moderate interest, I'll update the algorithm listing, ranking equation, et cetera and edit/re-post the results. If there is significant interest, I bash out a web application to allow open algorithm name submission and automated assessment and rankings (I hope so!).

There are a lot of things that can be drawn from the collected data, at the very least the top 10 algorithms in each of the imposed algorithm groups (at least those groups with more than 10 algorithms). Pay heed optimization algorithm padawans:

• Top 10 Algorithms: Genetic Algorithm, Simulated Annealing, Genetic Programming, Random Search, Tabu Search, Evolutionary Programming, Evolution Strategies, Particle Swarm Optimization, Expectation-maximization algorithm, Bayesian Optimization Algorithm
  
• Top 10 Evolutionary Algorithms: Genetic Algorithm, Genetic Programming, Evolutionary Programming, Evolution Strategies, Differential Evolution, Grammatical Evolution, Learning Classifier System, Non-dominated Sorting Genetic Algorithm, Strength Pareto Evolutionary Algorithm, Messy Genetic Algorithm
  
• Top 10 Swarm Algorithms:Particle Swarm Optimization, Ant System, Ant Colony System, AntNet, MAX-MIN Ant System, Multiple ant colony system, Population-based Ant Colony Optimization, Bees Algorithm, Rank-Based Ant System, Bee Colony Optimization
• Top 10 Probabilistic Algorithms: Expectation-maximization algorithm, Bayesian Optimization Algorithm, Compact Genetic Algorithm, Extended Compact Genetic Algorithm, Cross-entropy method, Population-based incremental learning, Hierarchical Bayesian Optimization Algorithm, Probabilistic Incremental Program Evolution, Univariate Marginal Distribution Algorithm, Bivariate Marginal Distribution Algorithm
  
• Top 10 Stochastic Algorithms:Random Search, Tabu Search, Scatter Search, Hill Climbing Search, Iterated Local Search, Guided Local Search, Greedy Randomized Adaptive Search Procedure, Variable Neighbourhood Search, Adaptive Random Search, Stochastic gradient descent algorithm

Observations

• Algorithm relevance. How wrong is the compiled list of algorithms? A factor of 2 or 3 (likely)? An order of 1 or 2 (it's possible)? I have seen many cases in my own trawling where researchers have renamed an algorithm for each paper published. How relevant are such algorithms to the practitioner they may claim to facilitate if one cannot name them to find them? One might argue that if an approach cannot be found (or cannot be understood) by those who might use or extend it, then it may as well not exist. I am not ignoring the converse argument that such published nuggets may be found and exploited at a later date (I guess like mendel's post hoc initiation of the modern synthesis), I think it is moot given the shear abundance of publications. There could be explicit contributions to the thread of research as well as explicit contributions to engineering (practitioner) without confusing both sides. (end rant, and yes of course I have been part of the problem in the past)
• Algorithm awareness. How many algorithms does the average researcher or even research group know about? One may research a field, generate an algorithm and miss the observation that the same general computation had already been investigated in one or more closely related sister fields. Further, there is a lot of algorithm racing in the field, which is a shame. The utility of such racing is further diminished if you consider the limited scope of possible comparisons in the average racing paper. The general field/s will continue to spin their wheels until they start extending and fixing the broken techniques that came before, rather than re-proposing them.
  
• Potential research opportunities. The low raking algorithms and fields may represent new approaches that have the potential to rise. At the very least, they may represent an opportunity for new and interesting research. A related observation is that the popularity approach used to collate the top algorithms may result in a bland and already over-represented algorithm compendium. This is a crucial observation which I will come back to.
  

Limitations
The following are the areas for improvement based on observed (and obvious) limitations:

• A more extensive algorithm list. The listing is biased by my graduate experience with evolutionary computation and artificial immune systems, and my exposure to swarm algorithms. There are a lot more optimization algorithms in the published literature, and more importantly, there are a lot more algorithms that should appear on this list. I hope I can find or be made aware of them (unsubtle appeal!).
  
• An algorithm naming or search strategy that avoids ambiguity. There are algorithm names that are a subset of many other algorithm names, and thus receive their Google Juice. Additionally, there are likely algorithms in the list that are not using their most common name, and algorithms in the list that are more commonly known by their acronym. A consistent algorithm naming convention is the cornerstone of the adopted method. The list requires careful cleaning and the searches require careful exclusion, both of which require a reliable method in their own right.
  
• Algorithm grouping could (should) be data driven. A set of 'fields of study' of varying generality could be assembled and search in conjunction with each algorithm name to locate each has the higher level of association. Such fields could then be distilled into appropriate groups.
  
• More measures. The domains and their measures were selected for convenience. Additional search domains may be used to add fidelity to the calculated ranking. Additional algorithm measures may be used, such as citation rank of seminal papers, articles, and books.
• A relative algorithm rank metric that exploits the importance of the search domain. An algorithm references on a webpage means less than a mention in a research paper, which again is less valuable than a mention in a book. Google's index is not complete, and it is quite possible that the book and scholar indexes are not direct subsets of the web search. The metric must be updated such that the known relationship between the measures is accounted for in an algorithms rank.
  
• An absolute algorithm rank metric from the collected absolute measures. The measures collected are absolute, and although relative inferences can be drawn a metric that exploited the absolute nature of the collected measures may be more robust and additionally amenable broader comparison.
  
• Statistical significance in tally measures and resultant ranking metric. Algorithms are ordered by their relative rank, although there is no account of the statistical significance of measures or the metric, only their ordinal relationship. For example, algorithms in the current listing may be assigned different ranking metrics, the difference between which is not a significant basis for discrimination.

Outcomes
It took this micro-study for me to realize what may be apparent: the role of a book such as the one I want to write should be to educate and enlighten. The expertise I bring to the editing of the book - such as the choice and presentation of algorithms and sub-fields - is the key and true contribution of the text, more than the distillation of the research on each specific subject.

I will continue to curate the list, I think it is still interesting. At the very least, it will provoke reasonable attention to algorithms and sub-fields that I had thought less relevant and depressed others that I thought were more extensive than they possibly are.

Algorithm popularity alone will not define the contents of the book. Reflecting, I can remember books like New Ideas and Optimisation and first reading about Differential Evolution. I remember colleagues discovering algorithms in a similar manner that eventually took on large roles in their own research agendas. The skill in preparing this book will come in finding those nuggets, those under represented techniques that are interesting and could propagate.

Using a blog post as a publication medium for ad hoc experiment and rant is liberating! Thanks to those kind enough to send in your top 10 lists, and thanks to Dan Angus for giving my algorithm list a nice boost.

Natural Selection: Project Status Update

It is the start of a new month and it feels like an appropriate time to write a project status update for my Natural Selection iPhone game project.

I've been keeping keen records for this after-hours project which may interest number junkies:

• I started the project (tracking time) 44 days ago on March 18th 2009.
  
• I have worked a total of 109 man-hours on the project, which is 13.64 man-days (nearly 3 man weeks).
• I have averaged 2.48 man-hours a day and peaked at 8 man hours on some weekends
• I have spent 46 man-hours (5.75 man-days) on the code base and the remaining 63 man-days on documentation and R&D, although this ratio is sure to correct with time
  
• I am (under-)charging my time at a graduate salary ($25AUD/hour) totalling my time at $2,725.00.
  
• The sum of expenses to-date is a little more than $5,000AUD (2 iPhones sadly, apple dev program, phone case, and chargeable time).
• Weddings and other random commitments aside, a first cut by July with a launch soon after would be reasonable.
  

Progress has been reasonable, although could have been better. Efforts on the code base did not begin until a physics engine and game engine were selected. I spent a fair amount of time (nearly a calender month or approximately 42 man-hours) researching, testing, and evaluating physics engines, graphics engines, and game engines. I think my saving grace was my support network.

At the start of the project (20th March) I organized an on-going developer meet-up with the other mayhem guys. The goal was to spend 2 hours, every fortnight to discuss progress with our respective side-projects and offer ideas and support. We had our first meeting on the 25th March, and by our second meeting just before Easter (8th April) I felt self-conscious still chatting about requirements documents and my progress on engine evaluations. It was this second meeting that kicked me into gear. I got pragmatic over the Easter break, started the build, and real-progress has been steady since.

The following two images are screenshots of my app taken from my iPhone. The first (left) is an early version of the prototype taken April 20th and shows basic rendering of a two shape creature in a box world with functioning physics. The second shot (right) was taken today and shows a simple background (thanks Gimp) and a functioning creature and world definition/management and the start of an evolutionary process (goal is to reach the flag).

My medium term plan is to elaborate the evolutionary process some more and then start to flesh out the 'game' features. I am going to add some basic menus for selecting the proto-creatures from which to start an evolutionary process as well as the environments (levels) where the process will take place. Longer term, I want to start to develop a 'look' for the game, and start seriously developing/acquiring the assets (images, sounds, music). I'm thinking creative commons and sites like 99designs might be useful.

Most importantly, I'm having fun. Classical ANSI C and C++ memory management is still as painful as I remember, although objective-C is new to me and interesting as a different take on the OO paradigm.

Dropping a Dimension: Cocos2D and Box2D on iPhone

Over Easter I decided to drop a dimension in my iPhone project to go from a 3D evolution game simulator to 2D.

I started out playing with the Chipmunk physics engine, just out of curiosity. I watched some videos of the engine in action, read the forums and downloaded the code base and example moon buggy project. The code comes with an Xcode project and the 8 demos make working with the engine look easy.

I started playing around with cocos2d for the iphone because it came with Chipmunk already ported. I hacked on the chipmunk demos (also ported to cocos2d) and found the lack of OO-design frustrating and the speed terrible, even after reading tweaks from the cocos2d forum and blog.

I kept seeing references to the Box2d physics engine (elements of which Chipmunk is based) and eventually dropped what I was working on and grabbed a copy of the code base. The code also had an Xcode project and I was impressed by the number and variety of demos. I dug deeper and came across the box2d port to iphone donated by Simon Oliver who built Rolando using Box2D. I graped the port from the box2D SVN server and started developing my game. I started fleshing out a basic game engine with physics and rendering call backs each frame, tweaked based on some game tutorial screencasts on 71^2.

The speed of the demos was still not good enough, but the object-oriented design sat right and I assumed I could optimize my application into submission (I have so far). While googling fixes for the issues and questions I was having in my basic game engine I kept coming back to the cocos2d forums and codebase. It was obvious that cocos2d had already solved the problem of a simple game engine, and then some.

I was decided. The rapid progress I was able to affect in 2D with both chipmunk and box2d as well as the ready-to-exploit and well documented cocos2d game engine convinced me.

The following is the dead-simple procedure I wrote down for manually integrating the box2D physics engine into the cocos2d game engine for the iPhone:

1. Check-out cocos2d-iphone from SVN. This is because the downloadable archive from the site does not allow one to decouple Chipmunk as easily.
2. Check-out box2d physics engine from SVN. This is because the downloadable archive is outdated and does not include the iPhone port (and subsequent changes to the codebase?).
3. Create a new Xcode project for cocos2d based on Monocle Studios - Introduction to Cocos2d iPhone Whitepaper. I only included the cocos2d directory (no Chipmunk for example), and I tweaked a few things a long the way (OpenGL-based project as a starting point, names of things, etc).
   
4. Because Chipmunk is no longer in my codebase I used the new replacement macros whenever the old Chipmunk macros were referred to (such as in forum posts and in the new cocos2d project tutorial in the previous step).
5. Add the box2d source to the project, specifically the 'include' and 'sources' directories.
6. The first build had some compile issues (a 'FALSE' rather than a 'false' and missing ';') that required minor fixes.
   
7. The first thing I did was create a custom Box2D cocos2d layer that ran the physics engine and generated a basic world with cute 2-box creature (big box with a little box flipper).
   
8. I used the rendering code listed in the box2D iPhone port (GLES-Render.mm) for drawing shapes, segments and points, and used the debug-drawing engine in the box2D core (b2World.cpp) as the basis for traversing world elements for drawing each frame. I considered using the cocos2d primitives (ChipmunkDemo/main.m) as is done in the ported Chipmunk examples, but I figured I am going to need custom drawing routines anyway, so the simple custom OpenGL drawing routines were a good base. I also ripped the mouse/touch code from the iPhone port of Box2D which works great.
   
9. I had some initial problems importing Box2D.h into my Objective-C++ header files. The solution was simple enough, involving #ifdef __cplusplus/#endif around the cpp header.
10. Finally, when compiling for iPhone hardware I had some additional errors in Box2D ('finite' was not declared in this scope), that were easily fixed.
    

I'm sure there are easier/better ways to get up and running with Box2D in cocos2d-iPhone (tell me please!) and millage may vary as the code bases change (I checked out the working copies of each project), although it has worked well enough for me thus far. If there is sufficient demand, I'll create an opensource project with the bare-bones project, or even just open up my current codebase. Let me know.

I'm currently struggling with the fabled "codesign failed with exit code 1" while trying to push my application to my iPhone device, specifically "object file format invalid or unsuitable". I've dropped 6 hours into this problem already and am still nowhere, although I'm reasonably sure it is not project specific. I will get there, but it is so damn frustrating!

Reading has turned up an array of interesting snippets. Cocos2d game engine was originally written in Python and ported to Objective-C for the iPhone. Notes on Cocos2d iPhone Development provide a great intro to cocos2d and specifically the arrangement of scenes, layers and nodes. Box2D has been ported all over the place including to Flash, and there are lots of useful box2d-flash related posts that are directly useful (like this lot that helped me figure out Revolute Joints). I have also seen lots of discussion about tuning box2d for performance (like 1m bodies are the sweet spot) and interesting physics engine comparisons and speed tests.

My current plan is to continue to realize the procedural creature generation and evolutionary engine for my project in 2D and play-test the hell out of it. If something fun drops out I will polish and push it to the app store and/or consider a port to 3D. The raw computation required for any meaningful morphology/controller evolutionary process is still my biggest technical risk. I am still not convinced it is viable on this hardware. I've got some thoughts regarding work-arounds (pre-evaluated strata in the search space, amazon EC2 compute servers, etc), although I am also thinking about a creature app without evolution.

Oolong Engine for the iPhone: A First Look

I set a side some time this weekend to have a look at the Oolong Engine for the iPhone and one thing is clear - it is the domain of the graphics programmer, hardcore or otherwise (note: not me).

The project started as a side project by Wolfgang Engel exploring graphics programming on the iPhone and iPod Touch, seemingly initiated in late 2007. The project went by the name iGDK (the iPhone Game Development Kit), was located on google code, and got some early attention given that the official iPhone SDK was at that time unreleased. Still in late 2007, Wolfgang renamed the project to the Oolong Engine, seemingly changed the license agreement to the MIT License and created the still current google code project and public facing website. A mailing list followed soon after and is now the primarily means of support containing almost 12 months of user interest discussions.

The main form of documentation for the project is Wolfgang's blog entitled "Diary of a Graphics Programmer", that details (among other things) insight into his progress on the project as a free-time exercise, as well as a series of (at last count) 9 iPhone programming tips released at then end of 2008 (approximately one year after the project was initiated).

For completeness, the following list the Oolong related posts from the blog:

• iPhone Graphics Programming (Dec 2007), started looking into iPhone graphics programming
  
• Porting an Open-Source Engine to the iPhone? (Dec 2007), thoughts on porting an existing 3D engine to the platform
• Oolong Engine (Dec 2007), announce the Oolong project named after his favourite tea
• San Angeles Observation on the iPhone (Jan 2008), the porting of a graphics demonstration by Jetro Lauha called San Angeles
  
• Ported my iPhone Engine to OS 2.0 (Apr 2008), as the title suggests, the engine is ported to a beta of the 2.0 iPhone operating system
• iPhone development - Oolong Engine (Jul 2008), project now a real platform for iPhone game development with published titles
  
• Major Oolong Update (Dec 2008), a number of updates to the code base including a new math library
  

Interpreted as an attempt at induction for programmers new to the platform and his engine, Wolfgang's wrote a series of iPhone and iPod Touch (iP*) programming tips from November 2008 to January 2009. Wolfgang's contribution in the Quake III Arena port to the iPhone shines through in some of these articles.

• iP* programming tip #1, summary of the underlying hardware on the iPhone
• iP* programming tip #2, setting up Xcode including all-in-one-mode
• iP* programming tip #3, review of folders in an application (project organization)
• iP* programming tip #4, the basic Oolong app, bridging objective-C and C/C++
• iP* programming tip #5, on pixel shader's and references the 'Per-Pixel Lighting' example
  
• iP* programming tip #6, on Matrix Palettes and the related code example
  
• iP* programming tip #7, on Point Sprites and the code example of a particle system
  
• iP* programming tip #8, handling the touch interface in a game
  
• iP* programming tip #9, VFP assembly programming
  

From the blog posts and news entries on the projects webpage, one may deduce that the Wolfgang's contributions to the project peaked early to mid 2008 (around the launch and resultant integration with the iPhone 2.0 SDK) and have simmered down since, except for an interest in VFP and the writing of programming tips over the 2008 Christmas period. The google project also lists Erwin Coumans from the Bullet Physics project as a second project owner, and there are number of additional members listed as contributing to the effort.

Oolong is the side project and domain of serious graphics and game physics programmers, and as such code is what this project is all about.

The project incorporates a number of sister open source projects and offers a suite of example projects. There is no documentation provided with the project other than some out-dated and vapid readme files for the examples and some reasonable in-line comments littered throughout the examples and the core engine code.

The leveraged third-party open source projects that were listed (or that I could deduce) and integrated into the code base are as follows:

• Bullet Physics (2.73), for 3D physics simulation
  
• Memory Manager, apparently by Fluid Studios although seemingly previously listed on Flip Code
• IPROF, A Portable Industrial-Strength Interactive Profiler for C++ and C, by Sean Barrett
  
• enet, the network subsystem used in cube
• VFP math library (also by Wolfgang Engel) offering math functions in iPhone-friendly ASM
• OpenAL sound engine/wrapper, (?)
  

The /Examples directory offers a number of discrete example Xcode projects logically grouped into sub-directories. Many of the examples worked for me (in the iPhone Simulator), although some failed to demonstrate their intended feature, some black-screened (is that a thing?), and a number crashed (specifically the 10 Ported PowerVR Examples under the Renderer directory). Initially I thought that the 10 'Ported PowerVR Examples' were a direct porting of the 10 Imagination Technologies Khronos OpenGL ES 1.x SDK for POWERVR MBX examples, although this may not be the case given the the names of the examples do not clearly align.

Given my newness to the platform, I am unsure whether the failing example projects were an artifact of the 'project in flux' or my iPhone SDK that was hacked to run on my PPC iBook G4 (yep, non-Intel). Additionally, the PowerVR Examples use code optimized for the iPhone hardware and so may need to be deployed to the device for execution. Given that I tested the examples in the simulator, this is a third possible cause for the examples that crashed out.

I am in no position to assess the efficiency of the engines rendering pipeline, but I bet it is smokingly fast relative to competing engines. What is clear to me is that the engine is bare-bones, requiring the programmer to do a lot of work to realize the (in principle) simplest 3D scenes. I am not a graphics programmer and I've been spoiled recently by frameworks in other domains that have delivered big wins with modest effort. I'm not giving up, but I want to hedge my engine betting. My next objective is to assess SIO2 and see what it can offer in terms of a more scripted (ready to write game code) solution.