Bye Octave, hello Lua!

I have translated the few scripts that I had coded in Octave so far, into Lua. Now that the amount of code is small it was just the time to make such a decision. There a many reasons behind this:

  • Lua supports argument passing by reference, which results in more elegant code, and the stack suffers less during function calls.
  • Lua is a highly embeddable language, from embedded systems to games.
  • Lua is much faster (the breadth-first search unit test with Octave takes 34ms, while with Lua it takes 0.073ms).
  • Lua is darn lightweight (see the amount of RAM used by the respective live interpreters: Octave 15.1MB, Lua 523kB, measured with ps_mem.py).
  • Lua provides a means for code encapsulation (modules and classes) and thus paves the way better organisation.

Apparently, the only common aspect between Octave and Lua  is the array indexation starting at 1. Octave is a great numerical platform for scientific computing, Matlab is the evidence of such interest, but Lua seems to be the least risky strategic approach due to its broader applicability. Moreover, Lua is a language that pushes the tools beyond its limits. There’s a lot of going on about this recently at the Facebook AI Research centre with deep learning.

Doing AI in Lua is definitely a clever deed. There is an incipient predecessor of this approach, the aima-lua project, developed by James Graves. James kindly warned me about the difficulty of structuring it, so I’m talking his piece of advice by delaying such a decision, and now I’m defaulting to a plain function-based organisation. Eventually, my goal is to switch to speech and language processing when I get to “communicating, perceiving and acting” (AIMA book, part 4), so this even increases the uncertainty about the adequate module structure at this moment. Time will tell. Wish me luck :-)

The A-star algorithm

A-star is an informed search method that evaluates nodes by combining both the cost to reach the node (step cost) and the cost to get to the goal state (heuristic):

Provided that the heuristic function satisfies the optimality conditions (i.e., admissibility for tree-search and consistency for graph-search), A-star search is both complete and optimal despite its large space complexity. Its implementation is based on the best-first search algorithm using an anonymous evaluation function that returns the sum of the two cost criteria, see Figure 1.

Figure 1. A-star search algorithm.

## @deftypefn {Function File} {@var{solution} =} a_star_search (@var{problem}, @var{start}, @var{finish}, @var{treegraph}, @var{heuristic})
## A-star search algorithm.
##
## PRE:
## @var{problem} must be the cost-weighted adjacency matrix.
## @var{start} must be the starting node index.
## @var{finish} must be the finishing node index.
## @var{treegraph} must be the tree/graph version flag. 0 is tree-version.
## @var{heuristic} must be the heuristic vector.
##
## POST:
## @var{solution} is the solution path. State set to zero if failure.
## @end deftypefn

## Author: Alexandre Trilla <alex@atrilla.net>

function [solution] = a_star_search(problem, start, finish, treegraph,
  heuristic)

  % eval func is anonymous and returns path cost + heuristic
  solution = best_first_search(problem, start, finish, treegraph, ...
    @(cost) cost(1) + cost(2), heuristic);

endfunction

At this point, the last mile to delivering useful and feasible results is to reduce the amount of memory consumed by A-star. This will be the topic of the next post. Stay tuned!

Welcome

Today I decided to become a better engineer, especially in Artificial Intelligence (AI). And I’m determined to do something about it. I’m going to do deliberate practice in order to sharpen my technical and business skills, and eventually attain this goal. That’s why I’m starting this blog. Here I will scrutinise the contents of the AIMA book, from A to Z, implement its algorithms, and use them to reengineer commonplace intelligent systems, just for kicks. As it is commonly stated in the maker community: DIY cannot compete with commercial products, but it is very rewarding to learn and understand how things work by making them (and even get to make them a little better).

The big scope

Borrowing the words from Paul Arden: it’s not how good you are, it’s how good you want to be. As a telecoms engineer with 10 years of professional experience, now helping companies leverage data to improve their competitiveness, I feel it’s time to compile all the knowledge I’ve gained over this time and do something awesome. It is also my goal to do so in the context of a healthy competitive business market. If intelligent systems are indeed in growing demand at present, e.g., see Figure 1 below, let’s discover the needs of the prospect customers and target them to drive future research. Pragmatic AI is so prevalent in the industry nowadays that there are many insights that will be of my interest to explore here.

Figure 1. Aggregate usage of the “intelligent systems” bigram in books (case-insensitive). Source: Google Ngram Viewer.

Aggregate usage of the “intelligent systems” bigram (case-insensitive). Source: Google Ngram Viewer.
Intelligent systems bigram in books

And the deep understanding of AI is not only relevant for the technical issues from the trenches, management is also in great benefit of this. In the end, suppliers are only as good as you are. Nobody else will do the magic but you. Thus, acing it as a project manager entails knowing first about the problem scope and how to tackle it appropriately.

The tools

In this journey through AI, the use of the AIMA book as a main guiding reference will be most necessary (among other relevant references). Its contents are broad, comprehensive, of general purpose, and written in plain words. Then, in order to bring its ideas to tangible code, Octave will be used for several good reasons (as an approach to using a Matlab-like syntax with open-source software). Primarily, I aim to evaluate algorithms, avoiding to get bogged down in the details of an “actual” programming language. Also, it is wise to program with a language close to the problem domain, i.e., the pragmatic programming tip number 17. And no matter how fancy would it be to code AIMA in Python, this has already been done by Peter Norvig (one of its authors). You already use Python extensively at work, don’t you? Thus, let’s approach this differently. My will is to add value here by implementing this with a clear data-analysis-driven scripting language that has not been considered yet (as far as I know).

Matlab is a great tool, there’s no doubt about that, don’t get me wrong. In fact, it’s one the first tools that experienced a most rapid growth wrt the number of users for its convenience. Given its wide reach, it is the numerical computing platform that rules in academia, in the corporate world, and also within the maker scene. Some say that you ought to adopt the best tools that money can buy to increase productivity. I cherish this piece of advice, especially for my professional development, but I’m not paying the license fee myself to do the same work I can do with Octave, nor I want Matworks to ever sue me if I use a pirate version of their beloved product. So let’s give it a shot with Octave! In the end, it can be seamlessly blended into Matlab. Andrew Ng did a great job to prove this with the Machine Learning class.

An appeal

Now, before I bring this first post to a close, let me just tell you that this is a most thrilling project for me, for the sake of knowledge, and that I’ll grind away at unravelling the details of such intelligent techniques, paying careful attention to detail. The only thing I ask of you is to give some feedback if you find this interesting. If you have similar personal deeds, please share them too! So feel free to collaborate, post your doubts, tips, quips, whatever. Everything is welcome. I’m eager to be of help if I can. Take it for a free consulting service as long as you openly discuss it here. On the downside, though, I’m afraid the posting rate won’t be much high or steady (perhaps @ai_maker is more adequate for such a more frequent usage), especially if experiments are to be conducted, but the fruitful discussions are another story. Enjoy.