Bid "A" Little "i" - Part II

In Part I I gave what I hope was a convincing argument for why software developers should care about Ai. In this article I will show how looking at problems from an Ai perspective can yield immediate benefits. I will then introduce the fundamental tenet of Ai, the red thread that ties all the approaches I will discuss (and indeed those I will not) together. 


It is Good to Talk

A seemingly obvious but rather useful thing that Ai does for us as software developers is it equips us with ways of thinking about thought and ways of talking about thought. By giving the techniques and algorithms we use names, it makes it easier to reason about them and to discuss them. The discussion or communication aspect should be familiar to most software developers as it is widely considered one the major benefits of Design Patterns, it is similarly beneficial in Ai.

An example of a rather simple algorithm that has been given a name in Ai is: Generate and Test. Lets say your task is to recognise a specific make and models of cars given a set of features, what would you do? Well, you could build yourself the Rube Goldberg machine below.

So what does this device do? The Generator flips through all the pages of the popular car buyers and sellers magazine Autotrader, it offers the cars on each page as possibilities to the Tester. The Tester takes each possibility from the Generator and checks its features to determine if it matches the type of car being searched for. Cars that don't match are discarded and the Tester moves on to the next possibility, once a match is found it presented as the result of the computation, if all the pages are exhausted but still no match is found no result is returned.

Why glorify such as simple computation with a name? As we eluded to earlier it allows us to answer concisely questions like: "How are you going to solve this problem?". We can now answer: "I am going to solve this problem using Generate and Test". Even more importantly we can now talk precisely about the properties of the Generator and the Tester.

Interesting properties of the Tester include:

•  Accuracy: Do we require 100% accuracy or would 99% accuracy suffice? A Bayesian mathematician would tell you that 99% accuracy is is definitely not good enough!
•  Speed: A tester that contemplates each possibility for too long may not find a solution in a reasonable amount of time.

Desirable properties of the Generator are:

• Complete: If there exists a car in the world we would like our generator to produce it. By this measure our choice of using the Autotrader magazine might have been a bad one since it is unlikely that all possible cars types are always for sale in this magazine.
• Inform-able: If I am looking for a small hatchback it does not make sense to offer a van as a possibility to the tester, it would be nice if we could tell the generator that.
• Non-Redundant: We do not want the same car offered as a possibility more than once, as could happen if our page turner went through pages at random rather than in sequence.

While it is helpful to be able to think and talk about ideas more freely, that is of course not the end of the story. Indeed it is but a single ice crystal on the tip of the iceberg, meant only to illustrate that you do not need to go far down the Ai road to get some real value.


Framing Problems

One of the most important things human beings do in problem solving is framing questions in a way that makes them easier to solve. We are all aware of this intuitively from phrases like: "looking at it from another point of view I realised...". My thesis is that the ability to frame problems appropriately is the basis for intelligence and indeed genius. Problem framing is at the heart of most of the topics that I am going to cover over the next few posts. I would argue that one of the biggest problems for Artificial General Intelligence (which as you may remember from Part I is about artificial agents comparable to, or smarter than humans) is that our algorithms are not very good at framing problems for themselves. A human being has to frame the problem then the computer can do its thing. This limitation places an upper bound on how intelligent an artificial agent can be.

This limitation is however perfectly acceptable for the masquerade of intelligence that I am interested in here. For our purposes we need to make the concept of problem framing more concrete, hence heretofore I will refer to Representations instead. To show how choosing the right representation is key to solving problems in general and in particular to conditioning problems for solution by a computer another example is order.

Most children have seen the puzzle of the farmer, the fox, the goose and the grain. All four are on one side of a river and the farmer wants to get all of them to the other side of the river (I always wondered why the farmer was ferrying a fox around). However the fox if left alone with the goose will eat it, the goose if left alone with the grain will eat it. A child would probably solve the problem relatively quickly by trial and error. What we need to do though is condition the problem for solving by a computer, we need a representation:

This representation looks promising as it makes explicit which side of the river everyone is on, lets see if we can use it to make progress with the puzzle. We did not mention it earlier but to get across the river the farmer must take the other across in a boat that has only room for two. What happens if our robot farmer takes whatever happens to be nearest to him across the river, in this case that is the fox:

This didn't work out too well, the goose was left unattended to feast on the grain - game over, we lost. Even though we lost the game, the representation has exposed an important constraint that might be obvious to us humans but must be explicitly stated for an Ai farmer, things that eat each other cannot be on the same side of the river without the farmer also being there. Our representation is serving us well so far, it has exposed constraints that we can exploit to solve the problem. The constraint shows which state transitions are valid and which ones are not:

There is really not much left for us to do to fully program our robot farmer. The problem can now be solved as a series of valid transitions between states involving the farmer moving from one side of the river to another. Once an appropriate representation has been chosen it is often a mechanical process to get to the solution, standard computer science algorithms (searching, sorting, finite state machines an so on) exploiting the constraints exposed are all that is required to take us the rest of the way.

It may seem like overkill to solve this rather simple puzzle which could be expressed in a few "if-else" statements in the manner we have but it is not! Take another look at what we have done, we have taken the puzzle and generalized it into a good representation and the constraints the representation exposes. This means we can solve any puzzle of this nature without any change to the code. Even if we change the entire cast, just by adding the knowledge of who eats who, that new puzzle is automatically solved.

An even more important point to note is that the person programming the farmer robot does not need to be able to solve the puzzle. They solve the problem at a different level, I doubt for example that any of the engineers that worked on Deep Blue were chess grandmasters. This is not such a big win for a simple puzzle like this, however there are problems which human beings cannot solve because of the time it would take, the errors a human would introduce, the amounts of data that need to be processed or host of other reasons. Hence Ai gives us the ability to solve problems that would otherwise be impossible to tackle!

We have seen how to get some quick wins out of Ai thinking and introduced the central concept of representations (as well as the ancillary concept of constraints). Having set the scene in Part I and given a technical introduction to Ai in this article the coming instalments will cover the main classical Ai techniques.

Big "A", Little "i" - Part I

Back in the 1980's there was a bubble in the technology industry that was to prove a good model for the dot-com bubble that would follow a couple of decades later. The 1980's bubble was due to the excitement and promise of Artificial Intelligence (AI). Thanks to some rather impressive but narrowly focused programs there was a feeling that the age of thinking machines was upon us. Investors and technologists alike rushed to get in on the act, a lot of money was spent, made and lost. People thought that AI technology would change the world¹, but when it didn't change the world overnight much the interest faded away. Of course it did not help that in the excitement a lot of money was spent on functional but rather basic software, like rudimentary Expert System shells.

The parallels with the dot-com bubble are obvious, a new technology comes along that seems like it will change the way we live, work and play, everyone gets overexcited, but it all comes to naught. Except... that it is not true! We know the rest of the story, the boom-bust cycle was just a capitol markets phenomenon and belies the fact there was real revolution taking place. Today we have internet companies that have market capitalisations in the tens of billions so clearly there was value there. Furthermore that is just the direct value to companies whose businesses are focused on the internet. There another fundamental shift from a technology perspective that is less conspicuous but more pervasive. Most software today has to be internet enabled, it is either entirely web-based or connects to web-services. Users now expect the richer experience enabled by the web, applications that sit entirely on the user's desktop with no gateway to the outside world seem dated and quaint.

The web is so integral that almost every working programmer must be at least aware of the technologies underlying it. I would argue that the same can be said about AI, though its importance is a little more subtle. The AI in most systems tends to be obscured, partly because it is not directly visible from the user interface, partly due to its nature² and partly because usually it does not make up a large part of the system. However a lot of the worlds most interesting software is only possible because of AI. AI systems are in use today in fields such as: flight control, manufacturing robots, search engines, fraud detection, medical diagnosis and games to name but a few. It is like raisins in a loaf of Raisin Bread - they may not occupy a large part of the volume of the bread, but you cannot have Raisin Bread without raisins!

Now you say to me: but AI has failed to make progress over the past few decades, where are those thinking machines and robots, show me the robots! Now we are getting to the crux of the matter, for AI can be about understanding and emulating human intelligence but it does not have to be! Indeed my thesis is that there are two closely related³ but nevertheless distinct sides to AI, the Science of AI and the Business of AI.

From the science perspective of trying to understand and emulate human cognition there may seem to be very little progress being made, but that is a misconception⁴ which unfortunately I do not have time to discuss in detail here. At any rate this aspect of AI is often referred to as  Artificial General Intelligence, but I like to think of it as aI little "a", big "I". That is because there is not that much that is artificial about this endeavour, the ultimate goal is to understand cognition to the point where we can create an artificial agent that thinks at human level and beyond.

The business of AI is what I think people interested in creating smart applications should be aware of. In contrast to the science of aI, the goal here is to build applications and machines that appear to be intelligent. Since in this case we only care about intelligence in the context of the specific application being built, this type of AI is typically referred to as Narrow Artificial Intelligence. I like to think of it however as Ai, big "A", little "i". Since the applications and machines only need to appear intelligent, so it is definitely artificial. Also the means by which this is achieved is not that important, a cheap trick that works is as worthy as an actual intelligent agent. I hope I did not give you the impression that I am down on Ai, quite the opposite! The techniques of AI used in narrow contexts are what enable the applications I mentioned earlier and many more besides. Without an understanding of basic AI algorithms, you may find yourself spending a lot of time creating unreliable and hard to maintain programs, that could be expressed in much simpler ways with standard AI techniques.

OK, so that was a very long-winded way to say that working programmers should know something about AI. After all that there had better be a pay-off and there is. The next few instalments will be introductions to what I consider the most useful and generally applicable Ai techniques. Stuff that you are guaranteed to find useful because it has been useful thousands of times in the past. Stay tuned...


1. And indeed it has, though perhaps not in the way people imagined back then!

2. When you meet a really smart person you might exclaim "Wow! That girl is really smart", I doubt you have ever thought "Wow! That girl has a smart brain".

3. Especially in terms of the techniques used, the research conducted and indeed the personnel involved.

4. This is an argument better made by the people working on Artificial General Intelligence: http://singinst.org; http://www.idsia.ch

Hot off the presses...

Here are the slides of the Python Puzzlers talk I gave literally a few minutes ago at PyCon Ireland, I love the internet!

Python Puzzlers

View more presentations from Tendayi Mawushe.

Hearing is believing!

A couple of weeks ago a few friends from the Python Ireland community and I were interviewed for the Code Mongrel podcast. The discussion was entertaining (for us anyway) and wide ranging but also rather long. The editor did a fantastic job creating two great podcasts from the interview session.

The first gave us an opportunity to plug the inaugural PyCon Ireland conference which is on this weekend, but we also discussed other interesting Python and Open Source topics: On PyCon Ireland 2010 and the role of Open Source

The second was more technical covering among other things, "dunder" methods, PyCharm, alternative Python implementations and Python design patterns: Python – I’m all about you, dude!

I would encourage you to subscribe to the Code Mongrel podcast, this is the second season and they were many great podcasts before ours and there are sure to be more in the future.

Walk a mile in a Lisp hacker's moccasins

"What's so great about YOUR programming language"? Bob asked Alice. Alice had been here before, she knew that if you are asked that question you should not answer, it's a trap! What Bob's question really meant is "I am OK coasting with the language I already know, you are trying to persuade me to do what seems to be unnecessary work to learn your new-fangled  language". Thinking quickly on his feet he came up with this trick question, which really means "in 30 seconds or less convince me that the language is superior to the one I already know or perfect for my needs". As with any nuanced argument, the case for a particular language cannot really be made in a pithy sentence that has high sound-bite value. In life there are pros and cons for any course of action.

Bob had succumbed to confirmation bias, for whatever reason (I would guess laziness) he had already decided that he was not going to learn the language. What he was really looking for was an excuse. So he posed a question of the form "give me the one killer reason to do it", since there is no ONE magic reason, Alice would fail to provide it and he could live on blissfully and effortlessly too! Alice did not take the bait  though. Instead she offered to teach Bob the basics of the language, little by little through progressively more interesting examples. She followed through on her offer and bit by bit time Bob began to see where her passion for the language stemmed from. At the end of it he was not quite ready to jump ship but he felt enriched by the experience he had a great time and learned a new language in the process.

You can substitute my name for Bob, (though indirectly) Hal Abelson and Gerry Sussman for Alice and Lisp is the unnamed language in the little story above. For long time and for no reason that I can think of other than that the nested braces where a little hard to read I had long resisted learning Lisp despite much cajoling from one or two friends. I had my little reasons like Polish notation arithmetic was hard to read and a host of others. Then one day I came across Abelson and Sussman's recordings from 1986 of the MIT course Structure and Interpretation of Computer Programs (SICP). That chance happening changed my view of Lisp completely in less than two weeks. SICP was taught in Scheme a dialect of Lisp, it took a few attempts but I eventually got into it, watched the videos attentively and was rewarded handsomely.

There are 10 lectures and by the end of the 5th one, having written with ridiculously little effort a host of interesting programs and in the process creating both an embedded an interpreted Domain Specific Language, I was a changed man! I had seen the light, I finally understood the ravings which just a fortnight earlier were incomprehensible.  My eyes no longer blind to the light I realised that similar derisions to those made against Lisp can and have been made against other languages like say Python¹ of which I am a great fan. So I whole heartedly encourage you watch the lectures or read the book which is available free on-line. After the first few chapters you may not be rushing to write your next web application in Lisp but I guarantee you will have a much better appreciation of the virtues of Lisp. The Native American prayer really rings true here: Grant that I may not criticize my neighbour until I have walked a mile in his moccasins. What's more with Lisp you need not even walk the full mile, a few hundred yards will do.


1. No curly braces? You rely on indentation to indicate block structure? That is crazy talk!

Trapped on a local maximum

A few months ago my laptop died and after several futile attempts to resurrect it¹ I finally let it go. So I purchased a new laptop, restored my data from the old one and proceeded to get it set up just the way I like it. This was going to be a long but enjoyable process. Finally though the Yak Shaving had to come to an end I had a project to get working on. It was a web project and I was going to use my de-facto choice, Python and TurboGears, but then I thought maybe I should reconsider my tool-kit. I never really considered using a language other than Python but on the web framework choice there was room to manoeuvre, or so I thought.

I was in a hurry, I had a project to get started on and the laptop saga had set me back significantly. So I decided to take a look at what many would consider the market leader in Python web frameworks: Django. No sooner than I had started going through the tutorial I was longing for TurboGears. I told myself that it might be worth it, the Django project seemed more active, the documentation significantly more complete and so on. As time was of the essence and motivation to learn something new lacking, I started my long overdue project using TurboGears and I was as happy as a Duck in water.

My reluctance to even take the time to learn another web framework got me thinking, what is it about TurboGears that I like so much? Sure I like the extra power SQLAlchemy brings to the party but other than that, in terms of fitness for purpose these web frameworks are pretty comparable. I came to the conclusion that TurboGears was just comfortingly familiar to me, not in a deep meaningful way, but rather in the most superficial way imaginable.

My programming experience until a few years ago was mainly with the the C family of languages with the majority of my professional programming life spent using Java and Java Enterprise Edition. When I thought about things in that context I realised I just wanted to stay true to the Java annotation and XML values instilled in me from my Java and JEE heritage. I just like the way TurboGears code looks, the @expose decorators remind me of Java annotations and the XML based templating engine reminds me of well... all those XML documents you have to create in a JEE application.

When I started using Python and TurboGears I think I subconsciously gravitated to what looked familiar. So even though I had taken the plunge and started using a dynamically typed language, perhaps I was trapped on a local maximum! Looking back over my code I was relieved to find that this is not the case. I write Python code in Python not Java code using Python syntax. It is funny though that I still and probably always will find @ symbols and angled brackets beautiful.

Update: August 2010
The internet allows us to collaborate with and befriend people in remote places, but I have always been a believer in meeting people face to face when ever possible. A few weeks ago I went to PyCon Ireland there I attended the Introduction to Django tutorial by Michael Twomey, it was a slightly informal walk through the basics of Django and some more advanced and very useful bits and bobs. Since then I have been able to work through the Django tutorial with much more success than before. A little bit of in person hand holding was all it took to get past the inertia that was holding me back.




1. Including foolishly replacing the motherboard which extended its life by about 6 weeks, instead of spending that €250 on maxing out a replacement.

Languages are magical!

I love programming and though I am loathed to admit it, I also love my chosen programming languages. Like many programmers I act like there is "one true path", the one true path is of course Python! Many a writer has been down this road before, yet I am still compelled to do the same. Why? Because I noticed something about myself that both surprised and disappointed me, I get angry when I hear someone bad mouthing Python.

I would like to think that I am above all that, that I and all those who are truly enlightened have long since moved past Vi versus Emacs, Perl versus Python, Dynamic versus Static typing and dare I say it even Windows versus Linux. I am wise therefore I know that these things all have different reasons for being and different places in history, thus a direct comparison of their merits and demerits is a fool's errand. Yet even here in the programming ivory tower, things are not so simple.

If I were truly enlightened I would start every new project¹ with an evaluation of the best tools to use, one of the most important being the programming language. The primary criteria for selection if I am being completely rational should be fitness for purpose. However it is almost inconceivable that unless I have no choice in the matter² that I would use anything other than Python. There are of course cases where this would be completely insane. When I am tinkering with the Arduino I use Processing, a great language it's own right, other than that I default to Python.

Much ink has been spilt addressing this issue directly, but I got more clarity from writers that were addressing orthogonal and indeed probably more important issues than the programming language wars. Eben Moglen the brilliant lawyer/historian/activist and once programming language designer said when Graphical User Interfaces were first becoming popular he did not perceive this as a good thing. In his opinion the key issue in computing was how we communicate with computers and each other, therefore language is where he thought at the time the focus should have been. In the context of Artificial Intelligence Terry Winograd and Fernando Flores in their book: Understanding Computers and Cognition -- A New Foundation for Design  placed similar importance on language when create what became known as the Language/Action Perspective. They said: "our position therefore in accordance with the preceding chapters is that computers cannot understand language"³. Concluding that since we cannot get computers to understand language: "software is unlikely to ever exhibit intelligent behaviour". These statements purportedly caused the nuclear winter in AI, but I digress.

What I take from all of this is that language is really powerful, powerful to the extent of appearing magical. Since it is magic, once you know one kind of magic, like the queen of Narnia it is inconceivable to us that there may be a deeper magic, of which we are not yet aware. So why do we obsess about our programming languages? Simple, because languages are magical!



Footnotes:

1.Ok maybe not every new project, it would probably not be a good idea to write three web applications in succession with different tool-sets.

2.For example if I join an existing project already using certain tools.

3.The original paper is from mid-1980's, in the fullness of time they may be proven wrong but that is what they said at the time.

Why is it hard to recognise crappy software?

A few years ago I had a commute to work that took over an hour and involved a couple of different modes of transport. I had a very short walk to the Luas¹ which took me to the City Centre. Once there I had a fifteen minute walk to catch a private bus service that ran and still runs I assume between the City Centre and a business park in the middle of no where. For some reason I always seem to end up working in difficult to get places.

Most of the time this was not too bad, a twenty five minute tram ride followed by a fifteen minute walk then a twenty five minute bus ride and I was there. This was not as bad as it sounds and it gave me one and half hours a day to myself. I got though a lot of reading those days and sometimes I even miss it a little, then I come to my senses! You see the, "just over an hour journey" was the ideal scenario, all too often the private bus was very late or did not show up at all. We were often left waiting there and when we called the bus company's office we got the standard line "he is just around the corner". Which was funny as the bus stop was close to a junction and we could see pretty much around every corner.

Forced to stand together for protracted periods of time and united by our common hatred of the bus company, strangers start to talk to strangers, strangers who over time (years in my case) become bus friends, then real friends and sometimes even good friends. It was on that bus that I met a friend of mine, who a few years later hired me for a great job and became my boss, so it wasn't all for naught. He loved and still loves a good metaphor, don't we all?

One my favourite metaphors he came up with² was to do with why it is hard to recognise bad software until it is too late. One day on the bus ride home (the bus was on time that day, saints be praised) we were discussing why it is hard for consumers and businesses alike to recognise crappy software. We were not breaking any new ground we were just having one of those discussions that programmers like to have. We talked about complexity of course, about user eduction and so on and so on. When we were came to how the inner workings of software are mostly hidden³ and how it is different in other fields he said this: "Anyone can make a table by taking a piece of ply-wood and hammering in some 2x4s for legs, but everyone can tell the difference between that table and a table made by a skilled carpenter".

The problem with software is that at first glance there can be no difference between the two tables and with a good coat of paint it can be near impossible to tell the difference until you take the table home arrange a fancy dinner party and make a terrible mess!





Footnotes:

1.For those of you that do not live in Dublin, "Luas" is "Fast" in Irish, it is a street going tram that is really handy if you happen to live on one of the only two lines.

2.I am not saying he was the first to make this analogy, but I first heard it from him.

3.In closed source software at least and even open source software to the average non-programmer computer user.