Never Read Passively

Back from China Trip

2009-10-21T11:40:00.000+11:00

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

2009-09-01T21:00:00.001+10:00

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:

Parse sources, build first order data model
Second order data model processing (stats, clustering, etc)
Process test users one at a time
Generate a candidate set (sub-set of all possible recommendations)
Filter candidate set
Apply indicators (blended, voting, whatever)
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

2009-08-17T21:00:00.007+10:00

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

2009-08-02T11:30:00.002+10:00

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):

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).
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.
Normalized algorithm names to their full unabbreviated form. No acronyms wherever reasonably possible.
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.
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.
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

2009-05-01T19:30:00.001+10:00

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

2009-04-19T16:30:00.001+10:00

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:

Check-out cocos2d-iphone from SVN. This is because the downloadable archive from the site does not allow one to decouple Chipmunk as easily.
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?).
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).
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).
Add the box2d source to the project, specifically the 'include' and 'sources' directories.
The first build had some compile issues (a 'FALSE' rather than a 'false' and missing ';') that required minor fixes.
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).
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.
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.
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

2009-04-05T17:30:00.002+10:00

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.

Review of 3D Engines for the iPhone

2009-03-28T11:30:00.004+11:00

I need a 3D engine for my iPhone project. I've hacked together my own 2D engines for rendering and physics in the past, but I have done very little OpenGL, and all the time I spent hacking around in the Quake, Quake2, Quake3 engines was focused on game logic and AI. This means that it is hard for me to define suitable requirements upon which to discriminate between available iPhone 3D engine middleware.

Requirements
Generally, I think my needs are modest (although still too rough to prepare a feature matrix comparison):

3D rendering and rigid body 3D physics
Demonstrated iPhone integration and deployment (technically possible and apple has permitted deployment)
Low polygon counts regarding world entities, robust physics simulation (one creature as a dozen or so cuboids connected by simulated muscles)
Facility to execute physics simulations in a/the world without rendering (at the same time as rendering would be really nice but implausible given the hardware)
Programmatic management of 3D world entities (definition, instantiation, post-simulation manipulation)
No cost (I don't mind open sourcing my project if it is permitted by the conditions of the Apple AppStore)

Candidates
Two clear candidates have emerged that may satisfy my needs, as follows:

SIO2 Interactive, SIO2: An opensource (LGPL) game engine for the iPhone. It uses the Bullet physics library and 3D objects and scenes are prepared using the opensource tool Blender. The project offers many tutorials (16) some of which are screencasts. The project also boasts a healthy number (15) of deployed iPhone applications available in the AppStore. The engine has a free version that imposes a flash screen (advertisement for the engine), an indie version is available without this restriction for $50USD. The volume of developer documentation in the form of tutorials is great, although the seeming dependence on Blender to prepare the 3D models and scenes used by the engine may be a deal breaker if there is no programmatic workaround.
Oolong Game Engine (on google code): An opensource (MIT License) game engine for the iPhone with some credibility given that it was developed in large part by Wolfgang Engel, Rockstar Games' lead graphics programmer. It uses the Bullet Physics Library for 3D physics and fluid studios for memory management. It has seemingly been used in a small number of titles (3?) currently available in the AppStore and proposes that it was used as the basis for the iTorque Game Builder. The source code comes with a number of demonstrations, although developer support documentation and tutorials are really lacking, and the mailing list is quite empty. This might be an engine for hard core developers.

Missed the cut
I came across four engines that missed the cut only because of an associated cost or maturity. I may reconsider selecting one of these engines if (and only if) it can be demonstrated that their adoption will save me time (or money - yes I'm keeping timesheets) on this project.

Unity 3D Engine (Unity Technologies): A cross platform engine that offers iPhone integration features and support. A large number of titles use the engine and presumably some of which are available in the AppStore. The core engine costs $199.00USD (Indie) plus there is a cost of $399USD (Basic) for iPhone integration totalling at least $600USD to get up and running. The cost buys support both in terms of documentation and a company that will return your support emails and calls. The engine looks slick and it seems a lot of people are using it.
tTGB - the iTorque Game Builder (Garage Games): The Torque engine has been ported to the iPhone and is offered as two products: iTGB for 2D games which is available now for $500USD (presumably built on the old TGEA platform), and a planned but as yet un-released T3D that presumably will have iPhone support. The software is both a builder software for making the game (WYSIWYG 2D editor) as well as an engine and packing tools for deploying your game. As with Unity 3D, the cost of iTGB is for the documentation and human support, and also like that engine it looks really slick. It was unclear to me how may titles have been built using this product and are available in the AppStore.
Ston3D Engine (ShiVa): The Ston3D engine offers iPhone integration support as a free add-on after purchasing the core product called ShiVa for $169.00GBP (about $244USD). ShiVa is a Windows-based game development product (like the Torque product) and offers a crippled free version that prevents publishing created games. A number (at least 8) of iPhone titles have been released based on the engine and are available in the AppStore.
CubicVR Engine (on sourceforge): An opensource (LGPL) game engine with no clear stable builds (only SVN access). There are some iPhone demonstration projects provided with the source code. It uses the Bullet physics library and supports other mobile and console platforms. The code base is seemingly the basis for the Pocket Hoops game in the AppStore. The project does not seem very mature and there are no clear tutorials or support documentation for starting a game project. As such, it did not make the cut.

Out of Scope
I came across a number of related projects that partially addressed some of my needs, but ultimately were out of scope. They are listed here for completeness, or in case I miss-interpreted the projects.

Irrlicht Engine: An opensource engine with a reasonably large community. At least one iPhone game has been released based on a private port of this engine although judging from some discussions, the port does not appear to have been released.
Cocos2D: A very cute 2D iPhone engine that uses the Chipmunk physics engine. Offers a FAQ and development best practices. The platform boasts a heap of games based on the engine and if I decide to go 2D instead of 3D, I'll give this engine serious consideration.
UtopiaGL: A private 3D iPhone engine project by Kevin Doolan. He does not appear to have plans on releasing the code although is tale of development is worth the read.
Icarus Studios: No product yet, but they have some cash behind them and were mentioned on VentureBeat.
Living Arcana: Lots of early discussion (2007) about building an opensource 3D engine for the iPhone, appears to be vapor.
Yeti3D: A port of an engine by Derek John Evans for the Gameboy Advance. Ported and released as a product by Marco Giorgini called iPac3D. Does not use OpenGL. It seems it was for jailbroken phones (accessible via Installer).
Cube: A first person shooter computer game (wikipedia entry) was ported to the iPhone and is available in the Apple AppStore for free. The engine is opensource (zlib/libpng License) and the source code for the port is available. This is not an iPhone 3D engine and was not appropriate or mature enough to be in scope.

Alternatives
Some alternatives popped into my head while 'deep googling' this problem and I thought I'd list them in the event I do decide to re-scope the project.

Write my own: One option that I briefly considered and dismissed given the time it would consume is to write a 3D rendering engine myself. I might be able to piece together the things I need from tutorial sites like Nehe and OpenGL ES. For the physics I could use an off-the-shelf solution like Box2D (used for Rolando) or Bullet.
Port an engine: There are many great 3D engines out there just ready and waiting to be ported to the iPhone. May of the communities of those engines have manifest demand, are discussing, or have already started the porting process like Irrlicht, OGRE, and Allegro. Frankly, I do not have the current chops or inclination to get into a port.
Use a Quake: Both the opensource (GPL) Quake and Quake III Arena game engines have been ported to the iPhone and are available on jailbroken phones via Cydia. Both engines are 3D, have long histories of community involvement (mods and engine ports), and the source code of their ports are available (quake4iphone and quake3-iphone). Also, id Software might be releasing these titles officially soon enough. I've had experience with these engines before, but not regarding the simulation and rendering of arbitrary programmatic generated world entities. As such I may have more trouble than a conventional 3D engine in trying to shoehorn non-quake techniques into the engine (maybe a good fallback position).

The Plan
As a warm up I was thinking of writing some tutorials on how to compile and deploy wolf3d, doom, quake, and quake3 for the iPhone. I suspect they will not be too hard to write given the sources are out there, and I expect it'll provide a good opportunity for getting up-to-speed on the environment.

Regarding my choice of 3D engine, I want to go with Oolong for as long as possible and fallback to SIO2 if progress proves too slow. I have booted the sample programs from both projects in the iPhone simulator, and have started to get a feeling for how one might map the algorithms and data structures from morphology evolution research into a 3D world. This brief research into available engines gives me some alternatives if the scope of the project changes or if I get fed up and decide I require developer documentation and support. I'm looking forward to starting the build early next month, after I finalize some GUI and algorithm designs.

Check out a similar round-up by Matthias Gall from September 2008 entitled "3D Engines on iPhone / iPod".

Please drop me a comment or email if you know of any further 3D engines or related resources.

Not Reading Passively: iPhone Links

2009-03-25T21:10:00.000+11:00

In the spirit of not reading passively, I've been trying hard to write summaries of all the iPhone related links I've been reading. Here are a recent mix from the last week of high-level iPhone propaganda and low level technical details:

iPhone SDK 3.0: A New Beginning: The new 3.0 iPhone OS as the new desktop. iPhone apps are more like simple desktop apps than conventional mobile apps. Android is a long way behind re developer base/app maturity. Constraints on the iPhone are liberating. iPhone is secure, no viruses like windows mobile and blackberry. Lots of fanboy spam in this post as well.
Should An iPhone App Developer Charge Or Run Ads? (Galaxy Impact Case Study): TechCrunch post on paid apps versus free app with advertising. Example app tanked after releasing for free then charging a dollar then free again. Lesson is to pick the right model at the start and stick with it.
Pinch Media Data Shows The Average Shelf Life Of An iPhone App Is Less Than 30 Days: Only 20% of users return to app after initial download. After 30 days, 5% of users still use app. Return is about 70c per user, equiv with free app is an $8 CPM (most are 0.50 to 2.00).
Coder's Half-Million-Dollar Baby Proves iPhone Gold Rush Is Still On: Wired article on the iShoot case study (lucky bastard). >600K in a month, 37K a day as number one in app store.
Good iPhone Practices: Discussion of managing buttons in UITableViewCells. Only use a XIB file only for a complicated interface. Discussion of instantiating UIViewController subclasses.
Intro to the Objective-C Runtime: How objective c works at the run time level. A class is a struct. An object is a pointer to a struct, the first variable of which is a pointer to its class. Struct contains compatibility info for older operating systems, built on top of C, can go rooting around to see how it works/hangs together.
Using Multiple OpenGL Views And UIKit: Discussion on how to mix openGL views with UIKit controls/views. Apple suggest to avoid doing transformations with opengl views, avoid putting transparent buttons on them. Stop doing frame updates when opengl view is not visible. Discussion of opengl view, mixed with uiview, mixed with multiple opengl views.
Cocos2D: Open Source 2D Game Engine for iPhone Developers: Engine for easy development of 2d games for the iphone. Open source, built in physics engine (chipmunk).
iPhone - Interface Builder Tutorial: Excellent interface builder tutorial that was recommended by someone/where. Step-by-step, very clear.
Tutorial: JSON Over HTTP On The iPhone: Tutorial that demonstrates how to consume, parse, and display a JSON feed from the web in an iPhone app.
Apple iPhone Makes Up Half Of U.S. Smart Phone Web Traffic: Study that suggests that 50% of smart phone traffic on the web is coming from iPhones. Up from 10% in August 2008. Android is at 5% in the same market.
Engineers show off "no jailbreak" iPhone keyboard hack: What I liked about this article was the clever workaround for interfacing with the phone, specifically by using the headphone port (WTF?). It "allows two-way transmission of data using frequency shift keying, the same method used in early modems". Awesome.
Apple Putting The Squeeze On iPhone Developers: A rumour site. Describes an amendment to the iPhone developer contract that forces developers to submit to a 90 day refund policy for apps in the app store. Developers would have to cover apples 30% cut as well, leaving them out of pocket (how could that be?). Although the clause may have always been in the contract.
PhoneGap: A very interesting project focused on automatically generating native (!) iPhone (and other) apps from javascript. Way Cool! You can access device features. Oh yeah, it's open source. Check the video.

Running a Genetic Algorithm on the iPhone

2009-03-23T21:10:00.001+11:00

I saw a post the other morning on the Genetic Argonaut blog entitled "Running Genetic Algorithms On A Cellphone". The post described the work by Christian Perone running a genetic algorithm in python on a mobile phone, specifically a Nokia N73 with Symbian and PyS60.

"Cool" I thought. "I can do something like that!"

I uploaded an old genetic algorithm script I wrote in Ruby for my Intelligent Algorithms project and it ran first time under iPhone Ruby (installed by Cydia), no problems at all. The above image is a screen shot I took in my jailbroken iPhone console running my GA script on a simple two-dimensional ("sphere") function optimization problem.

Not a big deal really. Wait until you can play with evolved 3D creatures on the iPhone, that will turn some heads!

If anyone wants the ruby script, shoot me an email.

3D Virtual Creature Evolution Part 1: Videos

2009-03-23T20:00:00.000+11:00

Inspiration is an important concern for Natural Selection, my current iPhone application under development. In communicating the inspiration for the app over recent weeks, I have reverted to accompanying any description I write with a link to a YouTube clip of Karl Sim's early 1990's research. I thought I would take some time to elaborate on this inspiration and dig up a bunch of related motivational resources.

I'm breaking this down into two posts, the first (this one) provides a collection of YouTube links to the results of 3D creature evolution, and the second longer more academic most summarises the state of research with lots of links to people and papers (I'll publish it in about a week).

An important element of broader success of the field of virtual creature evolution (and ALife) is the visual results it provides. Karl Sims is commonly referred to as the godfather of the of the study of evolved virtual creatures not because he released the first papers on the topic (he didn't), but because he (or someone close) ensured that digital videos of the work were released and popularised. Importantly, these videos are still around on the web and are held aloft as the seminal examples of this and the broader field can produce.

The two great video's of Sims' work I often share around are the following (they both have narration):

Sims' creatures are adapted to address very specific and narrow goals in simulated 3D environments including: swimming speed, walking (distance from origin, total distance traveled), jumping, light following, and block possession.

Any searching of this topic on YouTube will very quickly turn up results related to Lee Graham's 3D Virtual Creature Evolution (3DVCE) project. The project offers software to design and run experiments for creature evolution as well as a distributed environment for more elaborate experiments. A very clever marketing strategy adopted by Graham (intentionally or otherwise) was to exploit YouTube to both publicise the fruits of his efforts, and as a database for the favourites and the 'zoo' of user submitted creatures. The effect is a near dominance of video-based searching on the topic.

There are far too many videos to list (and I have watched a large number of those that are out there). I've listed a broad pseudo-popular and interesting collection, as follows:

Presentation to the Purdue Skeptics Society, April 2008 (6 parts including an overview of evolutionary computation and his project)
Darwin Day 2008 - Evolved virtual creature compilation video
End-over-end Worm - Evolved Virtual Creature (simply awesome!)
Frog - Evolved Virtual Creature
TAM6 - Evolved Virtual Creatures Video
Virtual creature evolved for flat terrain
HOW-TO Videos for 3D Virtual Creature Evolution (14 parts, interesting if you what to know details about the software)

Graham also links to an impressive number of related projects, providing an excellent summary of the state of web-available projects in the field.

Nicolas Lassabe has some interesting challenges involving walking, stair climbing, block pushing, walking across blocks, and even skateboarding:

Evolving artificial creatures

Evo Runners (I can't access their blog either) provides some good videos, some with some excellent production quality, including:

The AnimatLab have a very interesting video involving the evolution of different flapping strategies in a simulated bird:

Evolution of neuro-controllers for a flapping-wing animat

I really love the videos by Tyler Streeter of his evolved humanoid jumping behaviour. It makes me laugh out loud every time!

Finally, here are some additional random clips I came across and thought worthy of a look:

Polyworld: Using Evolution to Design Artificial Intelligence (google tech talk)
Evolved virtual creatures (2007) (by ERO including walking, swimming, and following)
Springs World 3D - Virtual Reality (using Springs World 3D)
Evolving Virtual Catapults (Hitting a block as far as possible)

An excellent aggregation of videos and links in this field (inspiring this post) was compiled and published by Alex Champandard of AIGameDev last February entitled: Evolving Virtual Creatures: The Definitive Guide.

Please, if you know of some more/better videos of three dimensional creature evolution leave a comment or get into contact with me.

iPhone Resurrection and New iPhone App Project

2009-03-22T10:38:00.005+11:00

After my iPhone fall from grace, I bit the bullet and bought a new iPhone. It sucks, I'm out of pocket. I'm trying to get over it and I'm optimistically looking to the future. I've jailbroken again, and I'm very aggressively developing a new iPhone application (out side work hours) with an estimated launch mid year.

I have been noodling around the idea for a while and even mentioned it before on this blog. I started development it on Wednesday 18th March, and since that time I've bashed out: 1) a project plan, 2) a functional requirements specification, and 3) draft technical designs for four major technical risks in my project (should one do business plan for a self-managed iPhone game?).

I have been debating with myself over the last few days how much information to publicly release on my ramp up to build. I've tendered comment on functional spec from mayhem and some developer friends, with excellent results so far. Frankly, I'm afraid that some kid with 6 months more ObjectiveC/OpenGL experience than me will see my idea and scoop me. I want to make some cash out of this (cover the cost of the phone/s), but more than the money (I have a good job in the real world) I want this app to exist in the world so that I can burn phone cycles (and my phone battery) playing with it. This latter need supersedes my concerns, so I'm going to release general descriptions of what I'm working on and release more (like the docs) to those who show an interest.

The code name for my project is 'Natural Selection', although iPity or iPhone Resurrection may be more appropriate project code names. The app is based on my obsession with simulated morphology evolution over the last 10 years, way before I dropped out of the world to do my Masters and PhD in Computational Intelligence.

The description from the head of my functional requirements specification is as follows:

The 'natural selection' iPhone application is an evolution simulator for the iPhone and iTouch platforms, providing light entertainment in a game like environment.

Natural Selection provides a selection of 3D environments and challenges for a virtual creature to adapt to and solve using an evolutionary process. Example environments include walking, swimming, flying, jumping, following, carrying an object, and fighting. The environment defines a virtual 3D space including a plane, obstacles, gravity, friction, and weather. Creatures are defined by a base body plan (head, body, arms, legs) in terms of 3D geometrical shapes that are connected via simulated muscles. The evolutionary process operates upon a genetic code that defines a given creatures body plan and muscle sensor-to-actuator configuration.

The user selects an environment and a base body plan from their respective libraries and watches as the creature adapts, specialising to the constraints of an environment under an evolutionary process. The user interacts with the process passively by moving the camera around the environment as the creatures evolve, and directly by manipulating the parameters of the evolutionary process. The parameters for the environment can be modified in real-time, changing the objective and constraints imposed on the creature under the evolutionary process.

Creatures and environments can be saved with screenshot and a symbolic name that can be used to load the creatures and/or environments in a later simulation. Creatures can be shared with friends via electronic communication such as email.

Naturally, there is more to it, especially along the lines of making it a 'game' (thanks Dave) and interactivity toward reinforcing behaviour (thanks Nigel). If you're at all interested, I hope that the description wets your appetite. Contact me if you want to know more, or get involved in some way! In the medium term I'm starting to evaluate 3D and physics engines for the iPhone platform (to give me a leg up), and I'm desperately going to need a source for sweet iPhone-esk graphics and music in coming weeks and months.

I think an iPhone or OpenGL hacker could whip something up in a few weeks to scoop me. Right now as I type this I think I would be pissed off (emotional brain). Nevertheless my rational brain keeps kicking in reminding me of the 10 years of my life I have dedicated to studding to this domain and the 5 years of that I spent designing building these kind of systems. I've got the heuristic and algorithmic savvy as well as the passion to pull this app off well, maybe better than potential scooping competitors. And if this suspension of disbelief fails me, at least there will be some incarnations of the idea out there in the wild (hopefully) for me to play with.

So I bricked my iPhone...

2009-03-11T18:42:00.007+11:00

My brand new iPhone is basically a write off, and I'm sad.

The story begins a little over a month ago. It was my birthday, there was a BBQ in the park, there were water balloons, and I had my iPhone in my pocket (super dumb in retrospect). When I got home I noticed that my clothes were quite damp, although the phone was relatively dry, so I thought little of it. Later that evening I played around with it and noticed the home button was not responding. Thinking that a little bit of moisture must have found its way inside the button, I switched it off for the night and left it alone (what I should have done is put it in a container of rice).

The home button was stuffed. No matter what I did, the home button would not work. I tried restoring. I tried pressing hard and pressing soft. I tried fiddling around with the button in case it was stuck. I started to get that sinking feeling in my stomach that a birthday afternoon of horsing around had fatally damaged my pride and joy.

I waited a week for the break of following weekend and took it to the geneses at the Chadstone apple store. I had recently jailbroken the phone, so I restored the device using iTunes back to a virgin state for the trip - this step also retrospectively was a poor move. The dude listened to my 'it doesn't work' story, inspected the water exposure indicators on the top and bottom of the device and said 'you have exposed it to water, we can't touch it'. Now, I concede that the home button must have got some moisture in there, although the damn phone was far from immersed! At most it would have been as much as few drops of rain if I were to use it briefly during bad weather. I pushed the point and the dude said that officially the water indicators were not completely triggered, the top was clear and the bottom indicator was partially indicating water exposure. I could have scraped the indicator and gone back on another day to try again - this retrospectively would have been worth a shot.

A new iPhone. Almost 2 months of use. Next to useless given fragile electronics, and apple tells me I'm on my own. I was a little sad at this point. I accepted the situation, more specifically my causal role, and optimistically began researching the next step: third party repair.

I researched the general class of problem from two perspectives: water damaged iPhone and broken home button. I read lots of similar problems and questions on iPhone related forums including a most impressive successful iPhone resurrection saga that involved (among other things) baking the phone in the oven!

I researched the components that I may need to replace and their prices: home button, flex cable assembly, etc. I also collected a long list of local third party iPhone repair stores and got quotes for fixing the general problem (in the order of $60 to $80 AUD for a home button replacement).

I picked a guy and dropped off the phone. Unfortunately, replacing the home button did not fix the problem. My guy deduced that it must be the flex cable assembly that the home button interfaces. He ordered an assembly from China, and I waited a number of weeks. The part finally arrived, although swapping out the flex cable assembly and the home button did not fix the problem. My guy deduced that the problem is likely the main board, and the cost would be close to half the value of a new phone. At this point I put a halt to the experiment, and took the device back. Fortunately, my guys policy is 'no fix, no pay', although unfortunately upon receiving the handset back the speaker no longer works and the screen no longer sits snug in the case. I plan on re-visiting my guy soon to resolve these issues, hoping that the speaker issue is simply a matter of a loose connection, and the screen can be reset in the case better than it was.

My fall back position was to use the device without a working home button, and use a software solution to close apps. I mean, the only thing the button is for is to close apps. That is what I thought until I went to re-jailbreak the phone so that I could install said software. The finally nail in the coffin is that I cannot re-install a jailbroken firmware on the device because I cannot enter DFU mode, a step needed in the quickpwn jailbreaking process. There was a way to get into DFU mode without a home button using software and hints of alternative jailbreaking software (ZiPhone or iLIBERTY) that may operate this way, but thus far these have not offered a viable path. Therefore: No home button, no DFU mode, no jailbreaking, and thus a bricked iPhone.

Options have eroded and my thoughts have settled on the following for my iPhone finale:

Continuing to use the iPhone as is. Maybe a software based DFU mode will come along allowing me to jailbreak and install a software based home button solution (Bossprefs or something). I might be able to install an older firmware and then use a software DFU mode solution. The phone would be a constant reminder of the penalty of not being careful enough with edge technology. The down side is that until a home button solution is found, I have to turn the phone off and on any time I want to change applications, which is VERY ANNOYING!
Selling the iPhone. I am seriously considering selling the lot for parts on eBay and forking out the cash for either a brand new/secondhand iPhone or more likely a G1 (or equivalent) Android based phone.
Rebuild from Parts. A third and final option may be to buy another broken phone from eBay - one with a broken screen (my screen is fine) and give them both to an iPhone repair guy to construct a viable phone. Slim chance of a payoff, although cheaper than a new phone.

My iPhone situation is dire, and I've had it locked in a draw for the last few weeks so that I didn't have to address it directly (also I was out of the country on business). It is time for me to move on I think, to bury my fallen comrade. Moving to a new (albeit less aesthetic) phone platform seems attractive at this glum point in time.

Intelligent Agents for Problem Solving

2009-01-26T11:00:00.015+11:00

I have just finished my first week at a new job. The place is called Agent Oriented Software (or the AOS Group), and they are a 10 year old multinational product/consulting firm focused on the application of intelligent agents (and related technology) to problem solving, seemingly mostly for R&D and defence. The company core product is called JACK, which is an agent-based platform for autonomous decision making and provides the basis for a host of extension products including team-based behaviour, simulation, cognitive behaviour, and more.

I had been exposed to intelligent agents, multi-agent systems, and agent-based modelling before, taking a course in my undergraduate, and reading some if the literature that came out our sister research group while completing my PhD on computational intelligence. I am only now starting to grasp the true nature of this movement as a new paradigm for software-based problem solving. So-called methodology for designing and building autonomous decision making software systems, now called agent-oriented programming and agent-oriented software engineering.

There is an IEEE special interest group focused on standardizing such systems called the Foundation of Intelligent Physical Agents (FIPA) providing a suite of specifications promoting interoperability. Interestingly, the now-defunct Australian Artificial Intelligence Institute (AAII) from what I can tell used to play an influential role in this country and to the field. Given that contributions have trailed off since the early 2000's, I have been poking around the history and projected trajectory of this field.

Intelligent agents and related technologies still feature in the research curriculum at some universities in my immediate vicinity, for example:

Intelligent Agent Laboratory (Agentlab) at Melbourne University, including an Autonomous and Intelligent Systems Group and an Agents Group. Interestingly, AOS was a start-up that spun out of this group and is still affiliated.
Intelligent Agents and Multi-Agent Systems (IAMAS) at Swinburne University, seemingly now integrated into the Centre for Complex Software Systems and Services.
Agent Group at RMIT responsible for the prometheus methodology.

I'm on the lookout for good inductive texts, other than the classics like Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, and more recent additions such as Developing Intelligent Agent Systems: A Practical Guide. I'm interested in cutting through the research agendas in the literature and better grasping the applicable niche for the approach. It seems that so-called agent-oriented programming is presented as an extension to object-oriented programming to address the complexity of problem solving with software, where the unit of modelling has shifted from the object to the agent and its interactions. One can achieve autonomous decision making without the application of an agent metaphor, so I'm interested in the specific benefits the approach can deliver. At the moment, the technology appears more complex than the problems it's trying to solve, I'm personally trying to figure out if it is overly so.

So I jailbroke my iPhone...

2009-01-17T19:00:00.004+11:00

I've had my iPhone for about a month now, and although the novelty has not worn off, my mind has been on pushing this little computer. I have been slowly been designing some AI-centric iPhone apps, although more than anything else the idea of jail breaking my iPhone has been weighing on me - coaxing me, slowly wearing me down.

Before taking the leap, I had some questions that needed to be addressed.

Would I loose my current configuration and apps? (no) Could I still use AppStore? (yes) Could I still manage and sync with iTunes? (yes), Could I restore to a virgin un-jailbroken state? (yes), Could I upgrade when future apple updates come down the pipe? (yes) Could I use the phone for development after the break? (yes)

I found these answers mostly piecewise, some on mentioned on guides, some from direct searching, and generally most of the answers came from iPhone/jailbreak-focused forms such as Hackint0sh, Whirlpool iPhone, and iPhone Hacks. There are some bad stories on some of those forums, which I tried to ignore, although reading through fixes for potential problems armed with some level of confidence if things went south.

Jailbreaking was all about changing small properties in software the runs the phone. Software like iTunes doesn't know or care about such modifications after they are made, allowing you to restore, restore from backup, sync, and continue life as per normal. I was satisfied about the process in general and turned my attention to the software used for the breaking. Who wrote it and where are the latest versions?

There may be a few iPhone cracking movements out there, although I focused on the most popular of the few who call themselves the iPhone Dev Team. They have a blog, a wiki, are on twitter, and most importantly maintain a list of the most recent versions of the required software. Some further reading taught me jailbreaking refers to acquiring the ability to install and execute unsigned code on the iPhone (basically homebrew apps and modified versions of proprietary apps). Another concern of this dev group is "unlocking" that refers to modifying a more specific aspect of the phone (it's modem or talking to the network thingo) and acquiring the ability to use sim cards from additional carriers (sim unlocking).

I was already familiar with jailbreaking although under a different name. I knew about modding in the context of game consoles, and had enjoyed the freedoms of watching movies across my network with a modded first generation XBOX for the 6 or more years.

I was only interested in jailbreaking my phone, not unlocking it. I discovered that there were two software tools to assist me with the process of liberating my phone: PwnageTool which is a is a wizard-like program for jailbreaking an iPhone by installing custom firmware through iTunes, and Quickpwn which is a tool to quickly and easily jailbreak an IPhone without as many steps (or as much control) as with PwnageTool. I believe PwnageTool is all about designing and constructing a custom firmware to push to the phone, whereas quickpwn is all about going with the defaults or the best practices.

I already had the most recent firmware installed on my 3G phone, and for the sake of simplicity I went with Quickpwn, using this outdated guide for the Quickpwn on OSX. I chose this guide for the clear and visual presentation of the steps required to get the firmware on the phone, specifically the combination and timing of button presses needed to get the phone into DFU mode. In retrospect, a quick read through the guide prior to running the software would have been all that would have been needed, as the wizard in the software provides sufficient detail.

I followed the instructions and still messed up the button combinations needed to get into DFU mode. I left iTunes running in the background, and it complained halfway through the process with a big ugly error message, which I ignored. Finally, at the end of the process, after the new firmware was uploaded, and after it rebooted and ran some on-phone updates, the phone sat in a cycle of rebooting and vibrating. After an impatient 10 minutes, I assumed the process was finished and pulled the cable out of the phone. It completed another reboot cycle and started up as per normal, although with the new Cydia and Installer homebrew apps installed. Success!

I've been jailbroken for a few days and have not had a single problem. Immediately after the jailbreaking process I tested wifi, 3G, inbound, and outbound calls. I proceeded to install an array of pre-researched/recommended homebrew apps through Cydia, not limited to: Cycorder, bossprefs, SBSettings, Doom, Quake, MXTube, mobilefinder, SSH, winterboard, Backgrounder, and many others. I have not yet installed any game console emulators, but they are high on my todo list. There are a lot of homebrew apps our there, and I'm always open to recommendations! In fact this has been the only way I have been able to navigate the avalanche!

From what I could read, the core application-centric motivation to jailbreak is to acquire functionalities such as recording video, streaming video from the phone, a zoomable camera, to use the phone as a modem (tethering), adding themes, and customizing the base system. They are fair reasons. In all truth think 'taking control' of the device and its software was a core motivation for me, and I think AppStore Piracy (and installation) is the core reason why an average Joe would jailbreak their phone.

I am really interested in pushing my own unsigned apps to my phone, and there are guides available. I am also interested in more edge homebrew apps that I have to compile and deploy myself. I'm thinking about getting involves in a few, just as learning exercise - maybe I'll port an open source game or two. We'll see.

If you are even remotely technical, jailbreak your iPhone already! You will know you made the right decision when you're killing processes from the command line and browsing the file system in MobileFinder. Just feels good knowing you can go there if you need to. Safe.

New Project: Inspired Algorithms

2009-01-11T11:00:00.000+11:00

I am happy to announce my new hobby project for 2009: Inspired Algorithms located at www.InspiredAlgorithms.com. As I outlined in the first post and enshrined in the web pages title bar, the goal of the project is to write and offer the largest set of explained and executable computational intelligence algorithms on the planet.

I have been writing copy for this project for about a month with the intention of releasing a self published book. The new year rolled around and I looked at my mess of private LaTeX files locked away on my hard drive and knew that the project needed to change. The important change in direction I made was the decision to start to release the content of the book piecewise, online, and for free.

My intention is to release 2 or 3 'inspired algorithm guides' per week for at least the next 6 months (8-10 per month), with the goal of amassing no less than 50 good quality guides by July 1st 2009. I then intend to release a book version shortly soon after, both in the form of a free PDF e-book and a paid (print on demand) hard copy book.

It is an ambitious project that I expect to contribute to in the evenings and weekends, channelling my so-called cognitive surplus toward something real and potentially useful to a wider audience. Already having a backlog of copy provides me with some buffer and slack to ride through any meatspace interruptions. I am also drawing heavily on my previous open source computational projects and my PhD research.

Already I have noticed a natural refinement of the copy from the dry guides I had written for myself to the more human and readable forms posted online. I have disabled comments on the blog as I don't think they're appropriate, and I've setup an Inspired Algorithms Discussion Group which I hope will generate some discussion and feedback that works towards further refining the the quality and accessibility of the content. I have also setup an Inspired Algorithms Open Source Project to maintain all ruby source code from the guides.

One of my concerns with using a blogger blog to host the project was how to effectively manage source code examples snippets in posts. I arrived at a somewhat antiquated solution that importantly looks pretty. I'm following a mixture advice from here that exploits the google-code-prettify project that offers javascript and style sheets specialised for syntax highlighting of code snippets in a web pages.

The setup process involved my adding the prettify links to the head of my blogger template (linked from the subversion trunk) and calling the prettyPrint() function in the onload of the page. Code sample inclusion involves writing the copy of guide first then editing the HTML and inserting the pre tags with the formatted code inside, then publishing immediately. I find that if I add the code and then view the draft post in compose mode that it messes up the indenting of the code. This is a real pain in the ass for maintaining a set of pre-prepared posts. The code looks really pretty in the blog posts, although sadly the effect is lost on those who subscribe via their feed reader.

I'm really excited about this project and the potential for building and refining a useful knowledge base of computational intelligence algorithms and explanations. I look forward to the challenge off my aggressive post schedule!

I'm Looking for a Job

2009-01-06T12:33:00.006+11:00

Since finishing up my PhD in Artificial Intelligence in June last year, I've been working with a group of guys on a number of websites with the intent of starting a profitable business. An agreement I made with my girlfriend way back in mid 2008 was that if my ventures were not financially viable or looking like they would be viable soon that I would seek gainful employment in the new year. That time has come. It's a new year and I'm looking for work.

I started some preparation toward the end of last year, contacting and organising professional referees, re-writing my resume in LaTeX, and setting up email alerts for key terms on local job sites. Initially I was unsure of the space of job sites in Australia. I built a small list and checked traffic on Alexa to ensure I wasn't wasting my time. Seek is still the dominant player with an estimated more than double the page views than the next two competitors.

Re-writing my resume forced me to consolidate my research work and more recent entrepreneurial aspirations into a communicable form which I found useful for really fleshing out the core take-aways. For me the PhD was a true apprenticeship in basic research, the scientific method and technical writing. Co-founding a number of website businesses was a crash course in product development and brand management with sprinkles of team coordination.

I condensed my resume and used the content to update my linkedin and facebook profiles in the off-chance that a potential employer does a background check. Like this blog post, I exploited my social networks to broadcast that fact that I'm looking for work using the linkedin and facebook status messages, as well as twitter. Although, unlike those social networking sites, this blog is far less of an advertisement and more a synthesis of ideas.

I've been thinking a lot about the kind of work I want to do. I'm a trained and experienced software engineer and research scientist and so dream jobs fall into the spectrum of programming complex intelligent systems. This observation ties in closely with a post I wrote back in March 2008 entitled "Cycling Hobbies to Day Jobs: A Personal Assessment of Starting a Startup". In that post I made the observation that in the past I had cycled between software engineer and AI researcher and that an ideal job would be to build such systems for a living. I now believe that I'm broadly suited to jobs within the spectrum defined on the boundaries between full time academic and full time software engineer. I am not convinced that jobs in the sweet spot such as 'AI research for development' or 'development of complex intelligent systems' is any better or worse suited than 'research scientist' or 'programmer analyst'. They all effectively exploit the skill set that has been accreted over the last 10 years, and I feel confident that so-called hobby projects can fill in any gaps not covered by a real job.

I still maintain aspirations of building and owning my own business, but I have seen hungry entrepreneurs and I don't think I'm one of them. Socialising and working with some of these guys in Melbourne as highlighted that what I desired from my own startup is the ability to call the shots. What I think I currently lack is the business experience (or perhaps discipline) to map hard work to financial independence. I am also not convinced that a service based business is the way to go. The bulk of my professional, personal, and creative projects have been produce and release. A business, especially a service-based business is focused on maintenance after release, not abandonment.

I attended a handful of interviews in the declining weeks of 2008. The positions where predominately at the edges of my spectrum of interest and the conversations during those interviews really woke me up. Paraphrased: "we're after a career academic, why so few publications? will you teach?" or "we're after a senior developer/team leader, how does your 4 year absence from this profession make you competitive?". Valid questions without a doubt which I addressed, although I can't help but think that being a specialist for the last 10 years and not having to answer such questions would be a better position. Perhaps not. Nevertheless I'm preparing for the long haul.

Artificial Intelligence on the iPhone

2009-01-01T13:15:00.006+11:00

On a first pass, the iPhone appears to be the perfect platform to deliver on the promise of the field of Intelligent Agents. It's a moderately powerful computer with a number of integrated sensors in meatspace (touch, orientation, location, audio, and visual) as well as connectivity to the web and relevant virtual sensors (search, subscription, message passing, etc). The platform could host the ultimate interactive intelligent software agent, but like the vagaries of the field from which this promise came, it is not clear what actions and behaviours such a virtual personal assistant can or should mediate.

I've had my eye out for any iPhone apps that directly utilize some form of artificial intelligence. I say 'directly' because unlike apps that indirectly exploit such technologies, those that advertise the far are easier for me to find via search.

I have come across a number of demonstration apps that appear to be written by enthusiasts. There are cellular automata simulations such as Lifegame that provides an implementation of Conway's game of Life. There are fractal geometry implementations that use the touch screen interface to zoom such as Mandelbrot. There is at least one chat bot app called Amy AI. Other examples include speech recognition like google mobile app, image recognition like SnapTell, and talk of augmented reality applications on the horizon. There are also related science applications like programming references, graphics calculators, circuit simulators, and many others.

I keep finding I have free time to burn on the phone, but find the games pointless. I have been thinking that the iPhone platform would be perfect for so-called games with a purpose as a more meaningful diversion. I have also been thinking that interactive computational intelligence approaches may be a lot of fun, especially applied to open ended problems like automated controller design and simulation in 2D or 3D environments (like soda race) or morphology evolution (like Karl Sims classical works).

I've idly been looking into this and have stared poking around some open source 3D engines for the iPhone such as Oolong and SIO2. Not sure where this will go, but I would much rather be exploited as a subjective human fitness function while killing a spare 20 minutes on a train than play another round at a vapid arcade game.

My iPhone Initiation

2008-12-20T10:00:00.000+11:00

Santa came early this year for me. On Tuesday (16th Dec) my girlfriend came home from work and presented me with a brand new iPhone. After some messing around with sim cards and pixels I've had a good two days of use with this slick device and thought I would capture my impressions.

The phone came home without a 3G sim card. Apparently the sales chick forgot to give us one. I didn't mind too much and postponed opening the packaging of the phone until the following day. On the Wednesday night I released the phone from its cardboard and cellophane prison and slapped the new sim in. Two more problems, the sim didn't work (my number didn't transfer nor was the sim activated on the network) and the phone itself had two dodgy pixels. I googled dead pixels and came to the conclusion that they were likely 'hot' or 'stuck' (brighter than the rest of the screen under all conditions), and tried various methods of flashing colors to wake them up, getting nowhere.

I stormed back to the phone store on the third day, got a new (and this time working) sim card and was bounced to the Apple store at Chadstone to get the replacement handset. I'd never been to the one and only apple store in my city and was surprised when I was told I needed an appointment (WTF?). I spent my 15 minute wait chatting to some other random worker about his iPhone. I interrogated him about cases and cool applications and he eventually sold me a Power Support Air Jacket for iPhone 3G for $40AUD. He had apparently been through three different cases, arriving on the clear version of this case with the crystal rather than glare resistant film. I chose the black backing for the more grippy feel, the clear and naked iPhone felt way too slippery to me. Anyway, I saw the 'genius' tech support guy who immediately switched out my phone leaving me a fully functional iPhone 3G, finally.

I was pretty ignorant about the device when I got it, so naturally I did some research reading iPhone on Wikipedia, the Apple propaganda page and videos, the PDF user guides some of which came with the phone, and the technical support page with some general information on specifications, resetting, and battery management.

Some details of this pocket computer: It is a black 16GB model (contrasted to the 8GB model) with a 9cm liquid crystal display with a resolution of 320x240. It runs a 620MHz CPU supposedly underclocked to 412MHz and has 128MB of RAM. The touchscreen is capacitive meaning it is requires human skin to operate (no glove or stylus). It has a 16GB flash drive (not a HDD), runs an iPhone OS (a derivative of OS X), use a powerVR 3D graphics chipset and has a 2 mega pixel camera. The Chadstone store gave me a 3 month warranty on the device, and Apple has a one year limited warranty.

Compared to the first generation iPhone, this second generation device has the addition of a plastic backing for improved reception, support for 3G connectivity for voice and broadband, and has built in assisted GPS. Some common criticisms of the device include: the lack of flash and Java in the web browser, crippled bluetooth, no video, no MMS, no cut/copy/paste functionality, and the low resolution camera with no flash, zoom, or autofocus.

The carrier is Optus who have good 3G coverage in major cities. The handset is apparently sim locked to the carrier, although Optus will remove this lock for free if requested. I'm on a 12 month contract with 100MB data and $50 of calls per month with a minimum of $19 of calls and a $65 contribution to the cost of the phone per month. Specifically: $0 up front, phone cost (12*$65=$780), min call costs (12*$19=$228), totalling ($780+$228=$1008) over the next 12 months. Call costs are step at 47c per 30 seconds, 35c flag fall, and 25c per text all in AUD.

Physically the phone is big. It fills my jeans pocket and is too big for my jacket pocket. I feel like a dick in public clumsily retrieving it from my pocket to change songs or answer a call because it is so big. I presume I'll get over this. The battery has been fine so far, giving me about a day of goofing around installing applications, listening to music, calling people, and playing games. About what I'd expect given heavy usage.

The interface is slick. I love the flick gestures for lists, and I love touching buttons and controls rather than using a disjoint keyboard and mouse. Mail hooked into my GMail account just fine, and AppStore is simple and intuitive to use. I've had applications crash on me a few times making me think a lot about how the OS is managing application serialization when I press the home key and later reinitialization. I had a situation where no third party application would open no matter what I did. I tried resetting, force restarting, and clearing settings all with no luck. I eventually restored the phone (basically a format) which initially pissed me off, although iTunes is set up to cache all the data I care about on the phone meaning after the restore and the subsequent transfer the phone was back to the way I had set it up - now with working third party apps. I had installed a lot of apps in 2 days (about 2 1/2 screens or about 40) and i suspect one of the apps wrote some data where it shouldn't have, stuffing things up for all the other apps.

I went to a dinner party the other night and an interesting situation occurred where almost everyone there had an iPhone. Almost all second generation, although there was one first generation phone. We all sat around playing on our phones, chatting about what cool applications we had tried or heard of recently, and playing games. Anti-social yet social. I got a lot of suggestions for cool apps and use cases for when device had proven useful in life situations (time tables and guides mostly). I was interested in the first gen phone. It was jail broken, meaning it had a modified firmware installed that allowed unsigned applications to be installed, much like modded xbox's (a domain I'm familiar with). He had a lot more flexibility with the phone, still accessing standard applications, as well as home brew apps like emulators and the array of games they provide.

The device is a computer in my eyes, and phone and mp3 features are secondary. I'm interested in applications, and more specifically applications that can exploit the features of the device such as multi-touch interface, 3-axis accelerometer, camera, GPS, and 2G/3G/wifi/bluetooth communication. Two days of app sampling is not long, but a few standouts so far include:

Google Mobile App - for the voice search where you hold the device to your ear and mouth like a phone and vocalize a search query. It just works.
Midomi - where you hum or sing a tune and it guesses what song and/or artist it is.
Topple - simple block game. I like it for the cool graphics, music, and use of multi-touch for block rotation. It was the first game I came across that gave me an impression of what this device could do. In fact, the few games I've tried by ngmoco:) have been impressive.
Aurora Feint - An RPG/puzzle game with great graphics, music and gameplay. Really quite immerse for such a simple game.

I use Fring for IM and skype, Twinkle for twitter, and the built in Mail for my GMail. I'm not too interested in reading my RSS feeds on the device yet, I'm guessing it may be too small. Photo's are geocoded by default, and so are my twitter messages. Besides those two cases, I haven't seen many good uses of the GPS or the mobility/portability of the device. A 'help me find Apple in Chadstone' app would have been useful. I can never interpret shopping center maps accurately - I think it's the scale.

I'm on the lookout for a public transport trip planner like Metlink Melbourne, a local TV guide application (don't watch all that much TV really), and a good movie trailers app (youtube is good, but there is lots of crap on there). The following are some applications that have been recommended to me from more than one source that I'm contemplating buying, mostly games to test the limits of the device:

Spore Origins - graphics, music, and game play are meant to be great, although it looks expensive.
Moto Chaser - this is the motorbike game advertised on the TV where the accelerometer is used to control the bike.
Iron Man: Aerial Assault - looks ok to me, but this 'guy flying around' game was recommended as being lots of fun
Cro-Mag Rally - cave man driving game, I think it was on the iPhone TV add as well.
Enigmo - similar in nature to The Incredible Machine although with water
Metro Melbourne - public transport timetables in Melbourne with time/location filtering for convenience
App Sniper - monitor free applications and changes in price, great for finding app store bargains (the apple store guy loved this app!)
Ocarina - blow into the microphone and use the device like a musical instrument - seems interesting
Oz Weather - for useful weather information (yahoo is crap) from the Australian BOM

I am trying to postpone app purchases until I understand more about the scope of the free applications out there. As a computer it is about as powerful as something I had 6-8 or so years ago, and I'd expect the apps to reflect that. Where is doom or quake? Where is the old classics like lemmings or the original incredible machine? Where is the Optus usage monitor application so I can see how many calls and how much data I have left for the month (I have to infer from general statistics in the phone).

Apparently there are about 13 million of these devices out there (both generations), and the development platform has been available for about a year now. I suspect the applications will only get better and better, and hopefully more innovative. Going forward I'm going to try lots more apps. I'm also going to further investigate jail breaking the phone and the home brew scene. Finally, I'm interested in getting into some iPhone development. I have a few ideas, although my old PPC iBook G4 and Tiger OS X are not immediately compatible with the iPhone development platform. I'm looking into some workarounds.

Evolutionary computation is popular in the holidays

2008-12-11T17:05:00.003+11:00

It seems to me that so-called exotic computer science topics become popular each holiday season, at least in the context of the news sources I consume. I eluded to this in a recent post, in particular computational intelligence. Now it seems the trend is evolutionary computation. Some highlights that have cropped up recently include:

Genetic algorithm for building a car: A flash program that begins execution on page load toward evolving a two-wheeled car in a two-dimensional landscape. The objective function appears to based on keeping the red circles from touching the ground, time, and perhaps distance travelled.
Genetic Programming: Evolution of Mona Lisa: Example by Roger Alsing of using genetic programming to evolve a set of 50 polygons to represent a source image, specifically the Mona Lisa. A FAQ is provided that comments that the objective function is the sum error between the generated image and the source image, meaning the result is an approximation of the source.
Image Evolution: A web application that uses simulated annealing to optimize the color, number of vertices, and orientation of a set of 50 polygons on an HTML canvas element to represent a given image, the default of which is Mona Lisa. Inspired by the popularity of the above approach.
Statistics vs. Machine Learning, fight! A great overview comparing and contrasting machine learning and statistics. This argument crops up every year or so, some good points though.
Application of Genetic Programming to the "Snake Game": The resurgence of this 2000 tutorial on using genetic programming to evolve a controller to successfully play snake.

Give the theme, there have been a number of recent requests for good tutorials, frameworks, and resources for learning about evolutionary computation and machine learning. Most are pretty crap, I'm sure this represents an opportunity, now that sites like ai-depot and generation5 are defunct.

Rationalizing the choice of ruby for code examples

2008-12-10T17:23:00.011+11:00

I am writing copy for a technical book that will present concepts predominately as example code in the Ruby Programming Language.

I recently explained the concept to some old colleagues which resulted in a discussion on the rationale for selecting ruby over math, pseudo code, or no examples at all. I'm not even going to try to justify the choice objectively (perhaps parsimony, prominence, popularity, etc.), rather I'm going to discuss some factors that influenced the decision.

It is a book by a programmer for programmers, that is people used to thinking about systems from a computational perspective. It is a natural fit therefore to communicate computation notions programmaticly. Further, to do so with small, sharp, and executable code examples ultimately makes the end product more engaging (at least it does when I project myself as a consumer).

Firstly I chose code examples over mathematical expressions. Equations can present concepts very compactly although generally at the cost of time and readability, at least for the types of things I'm interested in (systems and procedures). I made the same decision to use code snippets to express concepts in my dissertation, primarily because I felt a snippet was faster to write, faster to verify, and easier to read.

Secondly, I chose code over diagrams because I find most diagrams for conveying computation to be wasteful with regard to space and time. They have their place in design, but when communicating a programming concept I prefer short and sharp code snippets of conditional execution paths or an object and its use, over flow charts and class diagrams.

Given that I decided upon code examples, I chose to write snippets in a real language over a fictitious one (pseudo code) because I want code that can be executed. This is a no brainer, executable code adds substance to examples for the reader and provides an important verification step into the production of copy. The important decision here is the choice of language for general readability by programmer types.

I chose Ruby primarily because it is concise and reads well, two features it shares with pseudo code. The ruby syntax is quite general for modern languages, and procedures almost read like conversations between entities. The conciseness and readability come in part from the mixture of procedural, object-oriented, and functional features it supports, the blurred line between expressions and statements, and the fact that it is dynamically typed. Further, programming in Ruby "is fun", which is not surprising given that it was principled to be productive and enjoyable for programmers to work with.

To recap: code over mathematics for readability of computation, code over diagrams for conciseness, real over fictitious code for executability, ruby over other languages for its power and generality of syntax.

Ruby is a moderately popular language, although more readers will be unfamiliar than familiar with the specifics of its syntax. This can be addressed by providing a primer of 'Ruby for programmers' in the book, and limiting the use of features that do not align to the average C/C++/C#/Java programmers world view. It seems that a fine balance must to be negotiated here because constructs like closure's can significantly simplify examples in some cases. This is an important caveat to acknowledge because examples in a non-milk language (C or Java) may have been a deal breaker for the younger less experienced me of ten years ago.

Ruby does have some criticisms over other languages, the most relevant of which is execution speed. Some ruby interpreters are faster than others (checkout this great shootout), although ultimately the executable ruby examples are intended for education, not production. Speed of execution is happily sacrificed given that the intended readability of examples means code can be realized on demand for a problem and language of choice.

Thoughts on writing a book and self publishing

2008-12-08T16:00:00.009+11:00

I have started preparing copy for a book idea I've been noodling on for a long time. I'll go into the premise soon enough (in some future random post), although at this stage I've been thinking about the method of distribution I want to use. Without going too deeply into it, my first pass lead me to the current crop of self-publishing services.

I am a big believer in the notion that "obscurity is a far greater threat to authors and creative artists than piracy" espoused by Tim O'Reilly in a post Piracy is Progressive Taxation (2002). I am motivated to write because I want people to read and comment on what I have to say. I want to capture attention, inspire, and shed light in facets I think are truly interesting.

My planed book is technical. As a consumer of technical material my typically use case these days involves a search on google (web, scholar, books), visiting a small set of sources that have the potential of addressing my needs, and reading the slices of the opened sources relevant to my needs. When I was an enthusiastic kid with an interest in technical subjects (mostly programming related) my typical use case was very similar to what it us now, although it more typically ended with my completing a small code tutorial to grasp the concept or principle I was interested in at the time (the target audience and premise of the proposed book).

The commonality between these two examples is that I typically only ever needed a slice of the source that addressed my need a the time, not the source in its entirety. Services like google book search and similar are wonderful tools towards this end. A critical elaboration to these ideas is that when I locate a source I keep revisiting and/or a source I or peers respect, I typically acquire it. I buy the PDF or the dead tree book because I expect possessing the source will be more efficient for addressing my future needs. This is typically the case, although in non-linear ways such as concept seeding and discovery during a cover-to-cover read.

These thoughts lead me to the decision that I want to release the entire book as a series of web pages. The book idea is modular, so would translate neatly into a series of articles or posts on a dedicated website. The posts would be index by search engines, and if any good (referenced by readers) will float up in the search results and naturally accrue a readership. The webpage approach is intended to addresses the specific needs of searchers, and is intended to provide a gateway to the book as a consumer product. The web content would be free, and at this stage the e-book and dead tree version would be have to be purchased.

Self publishing appears to be a good approach for fiction authors that are able to promote their own product. I think natural promotion through search engines and careful SEO falls under this category, especially for the niche technical domain and market for which I am writing.

There are many-many print on demand (POD) services out there, although some of the newer or more popular sites I have uncovered include:

LuLu: A range of self-publishing services not limited to hosting, printing, syndication, and transaction management. Lulu offer more advanced features like analysis, cover design, and a range of editing and page layout service starting around $350 USD.
CreateSpace: Apparently acquired by Amazon, offering integration into Amazon's listings. According to their prices, createspace's approach involves taking a small fixed cut as well as a percentage from the list price.

I hear a lot about LuLu, and their site and services look great! The website promotion and/or POD models really appeal to me as I have seen them in action and have participated as a consumer a number of times. For example:

Kevin Kelly's Out of Control (1995). A book basically about complexity science that can be purchased like a regular dead tree book or can be read online. What I like about the online version is that it has been broken up for piecewise consumption, although not necessarily suitable to read end-to-end making me want to buy it. Note that there is nothing stopping you from reading the whole thing online other than convenience.
Cory Doctorow's fiction. I've read many of Doctorow's books by downloading, printing, and binding the PDF's. The easy access to a spiral binder as a postgrad made this an attractive option, although now that I do not have such access I am more than happy to buy new books as they come out.
A Field Guide to Genetic Programming (2008). A technical book on a machine learning technique released for free as an ebook and print on demand. A truly progressive move by these academics, which as of the end of November 2008 has seen more that 20k downloads in 8 months with 1.3% as POD purchases at approximately $13USD per copy.

I intended to spend my southern hemisphere summer focusing on writing the bulk of the copy for the book. There are some unsolved technical issues coming up which I'm looking forward to addressing including selection of appropriate (read: "nice looking") latex packages for type setting the book and sample code, and effectively managing the editing process.

I really want to split test the book and article format online, but I'm concerned that it would take away from professionalism of the final site and product. I suspect I will exploit the fall back position of enlisting a large pool of technical editors to achieve the same ends.

Computational Intelligence in the wind

2008-11-28T09:36:00.003+11:00

There seems to be a lot of chatter about genetic algorithms in recent days, for example:

Genetic A/B Testing with JavaScript: a discussion by John Resig about reverse engineering the Genetify service that seemingly uses a genetic algorithm to drive split testing. Seems like a problematic approach to me, good for sampling the space, but poor for confidence-based decision making over what design to choose.
CSSEvolve: guided stylesheet evolution: an introduction by Andrew Cantino to CSS Evolve service by IterationLabs that provides an interactive GA for basic sampling CSS designs for a given page (varies fonts, colors, etc). Interesting notion, and likely a good application for an interactive evolutionary algorithm.
Evolution Produces Better Antenna; Casey Luskin Very Upset: on Good Math, Bad Math by Mark Chu-Carroll discussing how some intelligent design evangelist talking about the post of another evangelist, both of which were unhappy by the (awesome) GA-designed antenna work at NASA from 2004 (old news).

For some reason (I was procrastinating), all of this GA talk motivated me to update the wikipedia page for the general and specific fields of research for my doctoral work. I definition and techniques sections as well as cleaned up the Artificial Immune Systems page, and kicked off a new Clonal Selection Algorithms wiki entry. All very basic, but I expect to add more content over the coming days.

Although I've created wiki pages before, this recent bout got me thinking how useful this service could be if it were elaborated by experts in the field. Although it's an encyclopedia, it would be within scope to motivate fields of research, even highlight open problems and provide sample code and test data. Wiki pages could be a useful valuable scientific resources, rather than a #1 Google result that is ignored by those in the field. I'm now thinking how Knol fits into these perspective...

Complexity Research in Australia

2008-11-20T11:00:00.004+11:00

I have been doing a little reading in the complexity sciences of late, and have uncovered a network of local (Australia) organisations, projects, and labs focused on this field of research. I presume I had not detected their presence before given my focus on learning and adaptation processes. This subtle influence lead me through adaptationism vs selectionism, selectionist theories, adaptive system formalisms and ultimately to complex adaptive systems, all of which played a critical role in my doctoral dissertation. The difference is that complexity sciences is broader than adaptation by a complex system, where systems can have the attributes of complexity (impervious to reductionism, non-linear interactions between components, emergent phenomena, etc) irrespective of 'improving their performance in an environment' - such concerns are irrelevant in systems such as climate systems, cosmological systems, and other physical systems.

Anyway, I started with Professor David Green at Monash who has a long histroy of complex systems research, including a recent book on landscape ecology looking at networks in ecosystems. Green's lab has setup VLAB, a virtual laboratory for complexity research intended to market some of the more interactive aspects of the field to a broader audience including a large number of in-browser simulations (Java applets).

The Australian Research Council (ARC) appear to have at least three web presences for their interests in complex systems, specifically the Complex Open Systems Research Network (COSNet) that seems to be a network of researches involved in ARC funded complex research, and the ARC Center for Complex Systems (ACCS) hosted at UQ, and the ARC Centre of Excellence for Mathematics and Statistics of Complex Systems (MASCOS). The COSNet site seems the more elaborate of the three, not limited to some insight into the history of the center, its vision that motivates the field of inquiry, and more interestingly example software. I am unclear of the relationship between the ACCS, MASCOS, and COSNet other than an obvious overlap in the source of funding and in some cases center members.

The Commonwealth Scientific and Industrial Research Organisation (CSIRO) also has an interest in complexity, demarcating complex systems science as an emerging science area, and setting up the CSIRO Centre for Complex Systems Science (CSS) directed by John Finnigan. The CSS motivate the field well with specific divisions in biological, physical, and social-ecological systems as well as the fundamentals. The 'emerging science area' site does have some interesting descriptions, presentations, and software downloads, although you have to dig deep into their mesh of pages.

Interestingly some of these organisations have emerged from theoretical physics an atmospheric research, which makes sense given the cross-disciplinary nature of the field and that what are now defined as complex systems are prevalent in such fields. This community seems larger and more motivated in this country (to do: test this assumption) than the field of computational intelligence that I previously chose to pursue, likely given the broader aims of complexity science that clearly have a strong overlap with (encompass?) my field.