AI Computer Vision

Scala, Eclipse and Maven integration tutorial

2011-07-23T23:37:00.022-04:00

I have evaluated Scala as a language for cloud computing and Hadoop. One requirement was a robust development environment, with a real build system, a good IDE with code completion and debugging.

The combination of Scala, Eclipse and Maven seemed like a fit for this requirement, but my initial experience was mixed.

Problems with Scala, Eclipse and Maven integration

It was easy to install Scala, Eclipse and Maven, but when I set up a project it had a persistent error in Eclipse:

object Predef does not have a member AnyRef

Natural language processing in F# and Scala

2011-07-12T00:28:00.018-04:00

I do natural language processing in C# 3.5 and Python. My work includes classification, named entity recognition, sentiment analysis and information extraction. Both C# and Python are great languages, but I have some unmet needs. I am investigating if there are any new languages that would help.

I 2010 I tried out 3 new languages:
Natural language processing in Clojure, Go and Cython

Recently I have investigated F# and Scala. They are both hybrid functional - object oriented languages; inspired by ML / OCaml / Haskell and Java / C#.

Python as the benchmark

Python is widely used in natural language processing. I am most productive in Python for NLP work. Here are a few reasons why:

NLTK is a great Python NLP library
Lot of open source math and science libraries e.g. NumPy and SciPy
PyDev is a good development environment
Good integration with MongoDB library
Great for rapid development

Python shortcomings

Slow compared to compiled language
GUI support is crude
Multi-threading is crude
Compilation does give more robustness

It should be possible to make a super language that has the elegance of Python, but without these shortcomings.

My first Scala experience

In 2006 I thought Scala was this super language. It is very advanced; you can call any Java libraries from Scala, including all the open source libraries. But I ran into a list of problems with Scala:

The Scala IDE was far behind Eclipse Java
Scala is a quite complex language
The Java libraries and the functional programming libraries were badly integrated
There were no Scala REPL or interpreter like in Python

Scala was stable enough for use, but it did not improve my productivity so after some months I went back to using Python as my scripting language.

Python's weakness

Recently I had to make a small text processing application that end users could use directly. This was not the best fit for Python. Normally my Python programs have no GUI and are controlled by command line parameters.

I had 2 Python options:

Make simple GUI using TkInter
TkInter is a Python wrapper of TK, the cross platform GUI toolkit. It is pretty crude by modern GUI standards, but would have been good enough. However trying to install all the Python libraries that I needed on the end users machine would be setting myself of for a maintains nightmare.

Wrap code in web application
I could wrap a web interface around it. The application is using a lot of memory and I would have to maintain a web application.

I had a 1 week hard deadline for the task and both of these options looked unappealing. I needed something else...

My first F# application

I took a chance on F#, and managed to learn enough F# to finish the program by my 1 week deadline.

There is no GUI builder for F# in Visual Studio, but it was pretty easy to hand code a simple WinForms GUI to wrap around the core code. It was not pretty but you could give it to an end user. The whole application ended up being one 40KB executable file, and it was very fast. F# had actually filled a niche that Python does not do so well.

There were also problems, I wrote the whole application from scratch, while in Python I would have been able to use NLTK, write the code faster and get better results.

All in all this was very good experience. I thought that F# would be a good supplement to my Python library. It would both give me raw speed when I need it and good connectivity with C#, ASP.NET, WPF and Microsoft Office.

Functional programming benefits

Functional programming is a great fit for my NLP work.

I have a lot of different text sources: database, flat file, directory, public RESTful web application services.

I have many word transformations: stop word filters, stemmers, custom filters.

I need many operations building on other operations: Bigram finder, POS tagger, named entity recognizer.

Created different reports: database, csv, Excel.

In functional languages you can just take any combinations of these operations and easily pipe them together while getting good compiler support. This does not fit so well with object oriented programming were you are more concerned with encapsulation.

F# impression

F# is the first compiled language I tried that is comparable to Python in simplicity and elegance. It has a real Pythonic feel:

F# is fast
Simple and elegant
Good development environment in Visual Studio 2010
Best concurrency support of any language I have seen
Good database support
Good MongoDB library
Simple to combine F# with C# or VB.NET for ASP or WPF
Good REPL

Issues

Runs best under Windows
For an IDE you really need Visual Studio 2008 or 2010, and that cost at least $700
F# can be compiled and run the shell from SharpDevelop 4.0 and 4.1, but you do not have the same productivity
The math libraries under .NET are not as good as NumPy and SciPy
The NLP libraries are better under Python

Scala revisited

After the success with F# I was very curious about why F# has been so much more successful than my first experience with Scala.

I looked at an F# and Scala cheat sheet and thought they look remarkably similar. I watched a few screen casts and found no obvious problems. I bought the book: Programming in Scala, Second Edition, it turned out to be a very interesting computer science book and I read the whole 852 pages. Scala still looked good.

I installed the Scala Eclipse plugin and wrote some code. Both the language and the IDE have come a long way during the last 5 years:

15 books about Scala
2 great free books
Tooling is much better
IDE is much better with code completion
Native NLP libs: ScalaNLP and Kiama

Of all the issues I had when I first tried Scala. The only remaining one is:
Scala is a pretty complex language

It is incredible how Scala has taken a lot of messy features from Java and turned it into a clean modular system, at the cost of some complex abstractions.

F# vs. Scala

Despite many similarities, the languages have a different feel. F# is simpler to understand, while Scala is the more orthogonal language. I have been very impressed by both.

F# better

Simpler to understand
Fantastic concurrency
Tail recursion optimized
Works well with Windows Azure

Scala better

More orthogonal, reusing the same constructs
Works with any Java library so more libraries
Better NLP libraries
Works well with Hadoop

Cloud computing

Functional programming works well with cloud computing. For me the availability of a good functional language is a substantial factor in selecting a cloud platform.

Google introduced MapReduce to handle massive parallel multi computer applications.

Hadoop is the Java based open source version of MapReduce. To run Hadoop natively it has to run a JVM language like Java or Scala.

Hadoop Streaming extends a limited version of Hadoop to work with programs written in other programming languages as long as they work like a UNIX pipes that read from stdin and write to stdout.

There is a Python wrapper for Hadoop Streaming called Dumbo. Python is around 10 times slower than Java and Dumbo is a limited version of the Hadoop, so if you are trying to do NLP on massive amount of data this might not solve your problems.

Scala is fast and will give you full access to run native Hadoop.

Microsoft's version or MapReduce is called: Dryad or LINQ to HPC. It is not officially released yet, but F# works well with Windows Azure.

NLP and other languages

Let me finish by giving a few short comparisons of F# and Scala with other languages:

Clojure vs. Scala

Clojure is a LISP dialect that it also running on the JVM, and it the other big functional language running there. Clojure has some distinct niches for NLP:

Clojure better

Language understanding
Formal semantic: taking text and translating it to first order propositional logic
Artificial intelligence tasks

Scala better

It is easy to write fast Scala code
Smaller learning curve coming from Java

I tried Clojure recently and was very impressed; but more of my work falls in the category that would benefit from Scala.

Java vs. Scala

Java better

Better IDE tools and support
Better GUI builders
Great refactoring support
Many more programmers that know Java

Scala better

Terser code
Closures
First class function
More expressive language

C# vs. F#

C# better

Better IDE tools and support
Better GUI builders
There are a lot more programmers that know C#
Better LINQ to SQL support

F# better

Terse code
Better support for concurrency, Synch, continuations
More productive for NLP

Conclusion

F# and Scala are similar hybrid functional object oriented languages.

For years I have periodically tried functional programming languages to see if they were ready for mainstream corporate computing; and they were not. With the recent spread of functional features into object oriented languages I thought that real functional programming languages would soon be forgotten.

I was pleasantly surprised by how well F# and Scala work now. Functional languages are finally coming of age and becoming useful in mainstream corporate computing. They are stable enough, and they have niches were they are more productive than object oriented languages like C# and Java.

I really enjoy programming in F# and Scala, they are a very good fit for natural language processing and cloud computing. For bigger NLP projects I now prefer to use F# or Scala over C# or Java.

For GUI and web programming the object oriented languages still rules. Stick with C# or Java if the NLP part is small or GUI or web interface is the domineering part.

Java and C# are also improving e.g. by adding more functional features. Many working programmers are well served by just waiting for Java 8 or C# 5. But functional programming is here to stay. Rejoice...

Cloud Computing For Data Mining Part 1

2011-06-17T14:30:00.011-04:00

The first half of this blog post is about selecting a cloud provider for a data mining and natural language processing system. I will compare 3 leading cloud computing providers Amazon Web Services, Windows Azure, OpenStack.
To help me chose a cloud provider I have been looking for users with experience running cloud computing for application similar to data mining. I found them at CloudCamp New York June 2011. It was an unconference, so the attendees were split into user discussion groups. The last half of the post I will mention the highlight from these discussions.

The Hype

"If you are not in the cloud you are not going to be in business!"

This is the message many programmers, software architects and project managers faces today. You do not want to go out of business because you could not keep up with the latest technologies; but looking back many companies have gone out of business because they invested in the latest must have technology, that turned out to be expensive and over engineered.

Reason For Moving To Cloud

I have a good business case from using cloud computing: Namely scale a data mining system to handle a lot of data. To begin with it could be a moderate amount of data, but it could be changed to a Big Data with short notice.

Horror Cloud Scenario

I am trying minimize the risk of this scenario:

I port to a cloud solution that is tied closely to one cloud provider
Move the applications over
After a few months I find that there are unforeseen problems
No easy path back
Angry customers are calling

Goals

Here are my cloud computing goals in a little more details:

Port data mining system and ASP.NET web applications to the cloud
Chose cloud compatible with code base in .NET and Python
Initially the data volume is moderate but it could possibly scale to Big Data
Keep cost and complexity under control
No downtime during transition
Minimize risk
Minimize vendor lock in
Run the same code in house and in the cloud
Make rollback to in house application possible

Amazon Web Services vs. Windows Azure vs. OpenStack

Choosing the right cloud computing provider has been time consuming, but also very important.

I took a quick stroll through Cloud Expo 2011, and most big computer companies were there presenting their cloud solutions.

Google App Engine is a big cloud service well suited for front end web application, but not good for data mining, so I will not cover that here.

The other 3 providers that have generated most momentum are: EC2, Azure and OpenStack.

Let me start by listing their similarities:

Virtual computers that can be started with short notice
Redundant robust storage
NoSQL structured data
Message queue for communication
Mountable hard disk
Local non persistent hard disk

Now I will write a little more about where they differ, and their good and the bad part:

Amazon Web Services, AWS, EC2, S3

Good:

This is the oldest cloud provider dating back to 2004
Very mature provider
Other providers are catching up with AWS's features
Well documented
Work well with open source, LAMP and Java
Integrated with Hadoop: Electric Map Reduce
A little cheaper than Windows Azure
Runs Linux, Open Solaris and Windows servers
You can run code on your local machine and just save the result into S3 storage

Bad:

You cannot run the same code in house and in the cloud
Vendor lock in

Windows Azure

Good:

Works well with the .NET framework and all Microsoft's tools
It is very simple to port an ASP.NET application to Azure
You can run the same code on you development machine and in the cloud
Very good development and debugging tools
F# is a great language for data mining in cloud computing
Great series of video screen casts

Bad:

Only run Windows
You need a Windows 7, Windows Server 2008 or Windows Vista to develop
Preferably you should have Visual Studio 2010
Vendor lock in

OpenStack

OpenStack is a new open source collaboration that is making a software stack that can be run both in house and it the cloud.

Good:

Open source
Generating a lot of buzz
Main participants NASA and Rackspace
Backed by 70 companies
You can run your application either in house or in the cloud

Bad:

Not yet mature enough for production use
Windows support is immature

Java, .NET Or Mixed Platform

For data mining selecting the right platform is a hard choice. Both Java and .NET are very attractive options.

Java only
For data mining and NLP there are a lot of great open source project written in Java. E.g. Mahout is a system for collaborative filtering and clustering of Big Data, with distributed machine learning. It is integrated with Hadoop.
There are many more OSS: OpenNLP, Solr, ManifoldCF,

.NET only
The development tools in .NET are great. It works well with Microsoft Office.
Visual Studio 2010 comes with F#, which is a great language for writing worker roles. It is very well suited for light weight threads or async, for highly parallel reactive programs.

Mix Java and .NET
You can mix Java and .NET. Cloud computing makes is easier than ever to integrate different platforms. You already have abstract language agnostic service for communication with message queue, blob storage, structured data. If you have an ASP.NET front end on top of a collaborative filtering of Big Data this would be a very attractive option.

I still think that combining 2 big platforms like Java and .NET is introducing complexity, compared to staying within one platform. You need an organization with good resources and coordination to do this.

Choice Of Cloud Provider

I still have a lot of unanswered questions at this point.

At the time of writing June 2011 OpenStack is not ready for production use. So that is out for now.

I have run some test on AWS. It was very easy to deploy my Python code to EC2 under Linux. Programming C# that used AWS services was simple.

I am stuck waiting to get a Window 7 machine so I can test Window Azure.

Both EC2 and Azure seem like viable options for what I need. I will get back to this in part 2 of the blog post.

Highlights from Cloud Camp 2011

A lot of people are trying to sell you cloud computing solutions. I have heard plenty of cloud computing hype. I have been seeking advice from people that were not trying to sell me anything and had some real experience, and try to find some of the failures and problems in cloud computing.

I went to Cloud Camp June 2011 during Cloud Expo 2011 in New York. Cloud computing users shared their experience. It was an unconference, meaning spontaneous user discussion breakout groups were formed. The rest of this post is highlight from these discussions.

Hadoop Is Great But Hard

Hadoop is a Java open source implementation of Google's Map Reduce. You can set up a workflow of operations and Hadoop will distribute them over a multiple computers, aggregate the result and rerun operations that fail. This sounds fantastic, but Hadoop is a pretty complex system, with a lot of new terminology and a steep learning curve.

Security Is Your Responsibility

Security is a big issue. You might assume that the cloud will take care of security, but you should not. E.g. you should clean up the hard disks that you have used it, so the next user cannot see your data.

Cloud Does Not Automatically Scale To Big Data

The assumption is that you put massive amounts of data in the cloud. And the cloud takes care of the scaling problems.
If you have a lot of data that needs little processing. Then cloud computing becomes expensive: you store all data in 3 different locations and it is expensive and slow to take it down to different compute nodes. This was mentioned as the reason why NASA could not using S3, but build its own Nebula platform.

You Accumulate Cost During Development

An entrepreneur building a startup ended up paying $2000 / month for EC2. He used a lot of different servers and they had to be running with multiple instances, even though he was no using a lot of resources. This might be cheap compared to going out and buying your own servers, but it was more expensive than he expected.

Applications Written In .NET Run Fine Under EC2 Windows

An entrepreneur said that he was running his company's .NET code under EC2. He thought that Amazon was more mature than Azure, and Azure was catching up. He preferred to make his own framework.

Simpler To Run .NET Application On Azure Than On EC2

A cloud computing consultant with lots of experience in both Azure and EC2 said: EC2 gives you a raw machine you have to do more to get your application running than if you plop it into Windows Azure.
It is very easy to port an ASP.NET application to Windows Azure.

Cash Flow, Operational Expenses And Capital Expenses

An often cited reason why cloud computing is great is that a company can replace big upfront capital expenses with smaller operational expenses. A few people mentioned that companies live by their cash flow and they do not like to have an unpredictable operational expenses, but are more comfortable with predictable capital expenses.

Practical Probabilistic Topic Models for NLP

2011-04-01T13:29:00.002-04:00

Latent Dirichlet Allocation, LDA is a new and very powerful technique for finding the topics in a collection of texts, using unsupervised learning. LDA is a probabilistic topic models. LDA was developed in 2003 and rely on advanced math. This post is a practical guide about how to get started building LDA models and software.

LDA will have a substantial impact on corpus based natural language processing; since it opens up for easy creation of semantic models based on machine learning.

Motivation for topic models

With the Internet we have large amount of text available. Having the text categorized into topics make text search much more precise and makes it possible to find similar documents.

Text categorization is not an easy problem:

Texts usually deals with more than one topic
There is no clear standard for categorization
Doing it by hand is infeasible

Nuanced categorized is a hard problem, with many moving parts, but in 2003 David M. Blei, Andrew Y. Ng and Michael I. Jordan published an article on a new approach called Latent Dirichlet Allocation. LDA can be implemented base on research articles, but if you are not a machine learning academic the math is intimidating and the material is still new.

There is actually good material available, but finding all the pieces takes some work. Most things you need are available online for free. Here is a chronological account for what I did to understanding LDA and start implementing it.

Need for more sophisticated hierarchical topic models

In 2009 I needed a fine grained classification of text, using unsupervised or semi supervised training. I spend a little time thinking about it, and had some idea about making bootstrapped training in a 2 layered hierarchy. It was hackish, complex and I was not sure how numerically stable it was. I never got around to implement it.

David Blei

I went to 4 Annual Machine Learning Symposium in 2009 and asked around for solutions to my problem. Several attendees told me to look at David Blei work. I did but he has written a lot of math heavy articles, so I did not know were to start.

I was lucky to see David Blei give a presentation on LDA first at the 5 Annual Machine Learning Symposium. David Blei works at Princeton and just exudes brilliance. He gave a lucid entertaining description of the LDA with examples. It wa really shocking to see the LDA algorithm find scientific topics on its own with no human intervention.

I saw him give the same talk at the NYC Machine Learning Meetup, and luckily that was videotaped here are part 1 and part 2. I watched these videos a few times. This gave me a good intuition for the algorithm.

I looked through his articles and found a good beginner articles BleiLafferty2009. I read through that several time, but I could not understand it.

I went out and bought the text book that David Blei recommended: Pattern Recognition and Machine Learning by Christopher M. Bishop. After reading the introduction chapter, I read BleiLafferty2009 again and was able to understand it. On page 10 the essence of the algorithm is described in a small text box.

Software implementation of LDA

There are plenty open source implementation of LDA. Here are a few observations:

lda-c in C by David Blei is an implementation in old school C. The code is readable, concise and clean.

lda for R package by Jonathan Chang. Implementing many models with extensive documentation.

Online LDA in Python by Matt Hoffman. Short code, but not too much documentation.

LDA Apache Mahout in Java. Active development community works with Hadoop / MapReduce.

JGibbLDA in Java

GibbsLDA++ C++

Arbylon Projects Java

No matter what language you prefer there should be a good implementation.

Practical software considerations

All the implementations looked good. But if you want to use LDA software then robustness, scalability and extendibility are big issues. First you just want the algorithm to run for simple text input. Next day you want the following options:

Better word tokenizer
Bigrams and collocation
Words stemmer
LDA on structured text
Read from database

Programming language choice for LDA

Here is a little common sense advice on choice of programming language for LDA programming.

C
C is an elegant, simple system programming language.
C is not my first choice of a language for text processing.

C++
C++ is a very powerful but also complex language.

NLP lib: The Lemur Project

I would be happy to use C++ for text processing.

C# is a great language.

NLP lib: SharpNLP.

You will have to implement LDA yourself or port one of the other implementations. SciPy is getting ported to C# but it does not have the best numeric libraries.

Clojure

Clojure is a moderate sized LISP dialect build on the Java JVM.

NLP lib: OpenNLP through clojure-opennlp.

LISP is classic AI language and you can use one of the Java LDA implementations.

Java

Java is modern object oriented programming language with access to every thinkable library.

NLP lib: OpenNLP.

Python

Python is an elegant language very well suited for NLP.

NLP lib: NLTK, using NumPy and SciPy

R
R is a fantastic language for statistics, but not so great for low level text processing.
NLP lib:
The R implementation of LDA looks great; I think that it is common to do all the preprocessing in another language say Perl. And then do all the rest of the work in R.

Different versions of LDA

There are now a lot of different LDA models geared towards different domains. Let me just mention a couple:

Online LDA
Online means that: you do learning of the models in small batches; instead of on all the documents. This is useful for a continuously running system.

Dynamic LDA
Good for handling text that stretches over a long time interval say 100 years.

Hierarchical LDA
This will handle topics are organized in hierarchies.

Gray box approach to LDA

The math needed for LDA is advanced. If you do not succeed in understand it I still think that you can learn to use the code, if you are willing to take something on faith and get your hands dirty.

Bedtime Science Stories My Science Education Blog

2011-04-01T13:29:00.000-04:00

I started a science education blog called: Bedtime Science Stories. Here is a little excerpt from my first post: Can and should a 3 year old girl be into science?

I have a 3 year old daughter that has take a bit of an interest in science. We have been talking about science when I put her to bed at night.

Last Sunday I discovered a new book called Battle Hymn of the Tiger Mother by Amy Chua, who is a law professor at Yale. She is using extreme methods to push her 2 daughters to academic excellence. They had to be the best in their class in everything except drama and physical education. Math was a topic that she really drilled them in. Just reading the back cover sent me into a rage; so much that I decided to start a new blog: Bedtime Science Stories, just to get my anger out.

Science should not be an elite activity. Making it very competitive will make a new generation of kids hate math and science. Understanding our world is worthwhile activity even if you are not the best in your class.

My 3 year old daughter

Is IBM Watson Beginning An AI Boom?

2011-02-15T01:56:00.043-05:00

Artificial intelligence fell out of favor in the 1970s, the start of first artificial intelligence winter, and has mainly been out of favor since. In April 2010 I wrote a post about how you can now get a paying job doing AI, machine learning and natural language processing outside academia.

Now barely one year later I have seen a few demonstrations that signal that artificial intelligence has taken another leap towards mainstream acceptance:

Yann LeCun demonstrated a computer vision system that could learn to recognize objects from his pocket after being shown a few examples, under a talk about learning feature hierarchies for computer vision
Andrew Hogue demonstrated Google Squared and Google Sentiment Analysis at Google Tech Talk, those systems both show rudimentary understanding of web pages and use word association
IBM Watson super computer is competing against the best human players on Jeopardy

All these 3 systems contain some real intelligence. Rudimentary by human standard, but AI has gone from the very specialized systems to handling more general tasks. It feels like AI is picking up steam. I am seeing startups based on machine learning pop up. This reminds me of the Internet boom in 1990s. I moved to New York in 1996, at the beginning of the Internet boom. I saw firsthand the crazy gold rush where fortunes were made and lost in short time, Internet startups were everywhere and everybody was talking about IPOs. This got me thinking, are we headed towards an artificial intelligence boom, and what would it look like?

IBM Watson

IBM Watson is a well executed factoid extraction system, but it is a brilliant marketing move, promoting IBM's new POWER7 system and their Smart Planet consulting services. It gives some people the impression that we already have human-like AI, and in that sense it could serve as a catalyst for investments in AI. This post is not about human-like artificial intelligence, but about the spread of shallow artificial intelligence.

Applications For Shallow Artificial Intelligence

Both people and corporations would gain value from having AI systems that they could ask free form questions to and get answers from in very diverse topics. In particular in these fields:

Medical science
Law
Surveillance
Military

Many people, me included, are concerned about a big brother state and military use of AI, but I do not think that is going to stop adaption. These people play for keeps.

There are signs that the financial service industry is starting to use sentiment analysis for their pricing and risk models. Shallow AI would be a good candidate for more advanced algorithmic trading.

Bottom Up vs. Top Down Approaches

Here is a very brief simplified introduction to AI techniques and tools. AI is a loosely defined field, with a loose collection of techniques. You can roughly categorize them it top down and bottom up approaches.

Top down or symbolic techniques

Automated reasoning
Logic
Many forms of tree search
Semantic networks
Planning

Bottom up or machine learning techniques

Neural networks, computer with similar structure to the brain
Machine learning

The top down systems are programmed by hand, while the bottom up systems learns themselves based on examples without human intervention, a bit like the brain.

What Is Causing This Sudden Leap?

Many top down techniques were developed by the 1960s. They were very good ideas, but they did not scale; they only worked for small toy problems.
Neural networks are an important bottom up technique. They started in 1950s, but fell out of favor; they came roaring back in 1980s. In the 1990 the machine learning / statistical approaches to natural language processing beat out Chomsky's generative grammar approach.

The technology that is needed for what we are doing now have been around for a long time. Why are these systems popping up now?

I think that we are seeing the beginning of a combination machine learning with top down techniques. The reason why this have taken so long is that it is hard to combine top down and bottom up techniques. Let me elaborate a little bit:

Bottom up AI / machine learning are black boxes that you give some input and expected output and it will adjust a lot of parameter numbers so it can mimic the result. Usually the numbers will not make much sense they just work.

In top down / symbolic AI you are creating detailed algorithms for working with concepts that make sense.

Both top down and bottom up techniques are now well developed and better understood. This makes it easier to combine them.

Other reasons for the leap are:

Cheap, powerful and highly parallel computers
Open source software, were programmers from around the world develop free software. This makes programming into more of an industrial assembly of parts.

Who Will Benefit From An AI Boom?

Here are some groups of companies that made a lot of money during the Internet boom:

Cisco and Oracle the tool makers
Amazon and eBay small companies that grew to become domineering in e-commerce
Google and Yahoo advertisement driven information companies

Initially big companies like IBM and Google that can create the technology should have an advantage, whether it will be in the capacity of tool makers or domineering players.

It is hard to predict how high the barrier to entry in AI will be. AI programs are just trained on regular text found on or off the Internet. And today's super computer is tomorrow's game console. The Internet has a few domineering players, but it is generally decentralized and anybody can have a web presence.

New York is now filled with startups using machine learning as a central element. They are "funded", but it seems like they got some seed capital. So maybe there is room for smaller companies to compete in the AI space.

Job Skills That Will Be Required In An AI Boom

During the Internet boom I met people with a bit of technical flair and no education beyond high school who picked up HTML in a week and next thing they were making $60/hour doing plain HTML. I think that the jobs in artificial intelligence are going to be a little more complex than those 1990s web developer jobs.

In my own work I have noticed a move from writing programming to teaching software based on examples. This is a dramatic change, and it requires a different skill set.

I think that there will still be plenty of need for programmers, but cognitive science, mathematics, statistics and linguistics will be skills in demand.

My work would benefit from me having better English language skills. The topic that I am dealing with is, after all, the English language. So maybe that English literature degree could come in handy.

Currently I feel optimistic about the field of artificial intelligence; there is progress after years of stagnation. We are wrestling a few secrets away from Mother Nature, and are making progress in understanding how the brain works. Sill, introduction of such powerful technology as artificial intelligence is going to affect society for better and worse.

NLTK under Python 2.7 and SciPy 0.9.0

2010-12-16T13:09:00.037-05:00

Python 2.7 has been out for months, but I have been stuck using Python 2.6 since SciPy was not working for Python 2.7. SciPy 0.9 Beta 1 binary distribution has just been released.
Normally I try to stay clear of beta quality software, but I really like some of the new features in Python 2.7 especially the argparse module, so despite my better judgement I installed Python 2.7.1 and SciPy 0.9.0 Beta 1, to run with a big NLTK based library. This is blog post describes the configuration that I use; and my first impression of the stability.

SciPy 0.9 RC1 was released January 2011.
SciPy 0.9 was released February 2011.
I tried both of them and found almost the same result as for SciPy 0.9 Beta 1, which this review was originally written for.

Direct downloads
Here is a list of the programs I installed directly:

Installation of NLTK

The install was very simple just type:

\Python27\lib\site-packages\easy_install.py nltk

Other libraries installed with easy_install.py

CherryPy
ipython
PIL
pymongo
pyodbc

YAML Library
On a Windows Vista computer with no MS C++ compiler were I tested this NLTK install I also had to do a manual install of YAML from:
http://pyyaml.org/wiki/PyYAML

Libraries from unofficial binary distributions
There are a few packages that have build problems, but can be loaded from Christoph Gohlke's site with Unofficial Windows Binaries for Python Extension Packages: http://www.lfd.uci.edu/~gohlke/pythonlibs/ I downloaded and installed:

matplotlib-1.0.0.win32-py2.7.exe
opencv-python-2.2.0.win32-py2.7.exe

Stability

The installation was simple. Everything installed cleanly. I ran some bigger scripts and they ran fine. Development and debugging also worked fine. Out of 134 NLTK related unit tests only one failed under Python 2.7

Problems with SciPy algorithms

The failing unit test was maximum entropy training using the LBFGSB optimization algorithm. These were my settings:
nltk.MaxentClassifier.train(train, algorithm='LBFGSB', gaussian_prior_sigma=1, trace=2)

First the maximum entropy training would not run because it was calling the method rmatvec() in scipy/sparse/base.py. This method has been deprecated for a while and has been taken out of the SciPy 0.9. I found this method in SciPy 0.8 and added it back. My unit test ran, but instead of finishing in a couple of seconds it took around 10 minutes eating up 1.5GB before it crashed. After this I gave up on LBFGSB.

If you do not want to use LBFGSB, megam is another efficient optimization algorithm. However it is implemented in OCaml and I did not want to install OCaml on a Windows computer.

This problem occurred for both SciPy 0.9 Beta 1 and RC1.

Python 2.6 and 2.7 interpreters active in PyDev

Another problem was that having both Python 2.6 and 2.7 interpreters active in PyDev made it less stable. When I started scripts from PyDev sometime they timed out before starting. PyLint would also show errors in code that was correct. I deleted Python 2.6 interpreter under PyDev Preferences, and PyDev worked fine with just Python 2.7.

I also added a version check the one failing unit test, since it caused problems for my machine.
if (2, 7) < sys.version_info: return

Multiple versions of Python on Windows

If you install Python 2.7 and realize that some code is only running under Python 2.6 or that you have to rollback. Here are a few simple suggestions:

I did a Google search for:
python multiple versions windows
This will show many ways to deal with this problem. One way is calling a little Python script that change the Windows register settings.

Multiple versions of Python have not been a big problem for me. So I favor a very simple approach. The main issue is file extension binding. What program gets called when you double click a py file or type script.py on the command line.

Changing file extension binding for rollback to Python 2.6

Under Windows XP You can change file extensions in Windows Explorer:
Under Tools > Folder Option > File Types
Select the PY Extension and press Advanced then press Change
Select open press Edit
The value is:
"C:\Python27\python.exe" "%1" %*
You can change this to use a different interpreter:
"C:\Python26\python.exe" "%1" %*

Or even simpler when I want to run the older Python interpreter I just type:
\Python26\python.exe script.py
Instead of typing
script.py

Is Python 2.7 and SciPy 0.9.0 Beta 1 stable enough for NLTK use?

The installation of all the needed software was fast and unproblematic. I would certainly not use it in a production environment. If you are doing a lot of numerical algorithms you should probably hold off. If you are impatient and you do not need to do new training it is worth trying it, you can always roll back.

Growing Python projects from small to large scale

2010-11-12T21:50:00.005-05:00

You need significantly different principles for developing small, medium and large scale software system.

When my project started to become big I searched the Internet for some guidelines or best practices for how to scale Python, but did not find much. Here are a few of my observations on what technique to use for what project sizes.

General principle

For a small system you can spend most of your time solving the problem, but the bigger the system gets the more time you spend on project plans, coordination and documentation. The complexity and cost does not scale linearly with the size of the project but maybe scales with the square of the size. This holds for different styles of project management both waterfall and agile.

A central problem is minimizing dependencies and avoiding tight coupling. John Lakos has written an excellent book on software scaling called: Large-Scale C++ Software Design here is a summary. It is a very scientific and stringent approach, which is specific for C++. He developed a metric for how much dependencies you have in your system. His technique are not a good fit for smaller projects, you could finish several scripts before you could even implement his methodology.

Small scripts
Keep it simple. Focus on the core functionality. Minimize the time you spend on setting up the project.

Medium applications
Spending some time organizing things, will save you time in the long run.

Large applications
Here you need a lot of structure; otherwise the project will not be stable.

Development environment

Small scripts

I use PyWin Windows IDE.

It is lightweight
No need for Java or Eclipse
Syntax highlighting
Code completion at run time and some at write time
Allow primitive debugging
You do not need to set up a project to use it.

Medium applications
I have used both PyWin and PyDev.

Large applications
I would strongly recommend PyDev Eclipse plugin. It is a modern IDE and runs pylint continuously and has good code completion while writing code. It will find maybe half the error a compiler would find. This improves the stability a lot and was the most important change that I made from my old coding style.

Organization of code

Small scripts
Use one module / file with all the code in. This can have several classes. The advantage is that deployment becomes trivial: you just email the script to the user. This works for modules up to around 3000 lines of code.

Medium applications
Use one directory with all modules in. This gives you fewer issues with PYTHONPATH.

Make a convention for naming field names, database name and parameter name. Put all these names in a module that only contains string constants, and use these in your code instead of raw string.

Use a separate repository for the project. I package the Python and other self written executable together in a repository, even when I have another source control system for the compiled sources.

This works up till around 40 Python modules, then it become hard to find anything.

Large applications
Read and follow the Python style guide. Before I followed a Java style guide since Java is big on coding convention, but the Python style is actually pretty different. A noticeable difference is a Java file contains a main class with a title case name and the file has the same name. In python modules should have short lowercase name while the classes still should have title case names.

Organizing packages as an a-cyclical graph
Refactor the modules into packages. The packages should be organized as an a-cyclical graph. So at the lowest level you would have an util package that is not allowed to reference anything else. You can have other specialized packages that can access the util package. Over that I have the main source directory with code that is central and general. Over that I have a loader package that can access all the other packages.

One problem when you have different directories is that you need the PYTHONPATH include all the code. A good way to do this is to try to add the parent directory to the system path before you import any of the modules.

Documentation

Small scripts
Usually I have:

Python docstring in the program.
Print a usage message

Medium applications
Have a directory for documentation. To keep it simple I prefer to use simple HTML. I find that Mozilla SeaMonkey is simple to use and generates clean HTML you can do a diff on. Often I have:

User documentation page
Programmer documentation page
Release notes
Example data

Large applications
At this point using automatically generated documentation and some sort of wiki format for writing documentation is a good idea.

Communication

Input and output account for a sizable part of your code. I prefer to use the most lightweight method I can get away with.

Small scripts and medium applications
Communication is done with flat files, csv files and database.

Large applications
Communication is done with flat files, csv files, database, MongoDB and CherryPy.

MongoDB have dramatically simplified my work, before different types of structured data demanded their own database with several tables. Now I just load the data into a MongoDB collection. MongoDB make very different structured documents look very uniform and trivial to load from Python. After that I can use the same script on very different data.

When you have a script and find out that you need to have other programs call it. It is very simple to create XML, JSON or text based RESTful web service using CherryPy. You just add a 1 line annotation to a method and it is now a web service. You barely have to make any changes to your program. CherryPy feels very Pythonic. This will give you very cheap way to connect to a GUI and a web site written in other languages.

Unit tests

Small scripts
Unit tests give you a small advantage. I still write unit tests unless there is an emergency, and then I usually regret it.

Large applications
The bigger the system the more important it is that the individual pieces works. Large systems are not maintainable if you do not have unit tests.

Source control system

I put any code that I use for production in a source control system. I usually use Subversion or GIT.

Subversion is good for centralized development, and it is nice that each check in has a sequential revision number so that you can see revision number 123 and next 124.

GIT is better for distributed development; it is easy to create a local repository for a project.

Small scripts
One repository for each type of script.

Medium and large applications
One repository for each project.

Use of standard libraries

Small scripts
Use the simplest approach that gets the work done.

Large applications

When my application grew I realized that I recreated functionality from the standard libraries; for instance from these libraries:

I refactored my program to use the standard library and found that it were much better than what I had written. For bigger application using standard libraries makes your code less buggy and more maintainable. So spend some time to find what has already been written.

How well does Python scale compared to compiled languages

There are mixed opinions on this topic. Scripts are generally small and large systems are generally written in compiled languages. The extra checks and rigidity you get from a compiled language is more important the bigger you applications get. If you are writing a financial application and have very low tolerance for errors this could be significant.

I am using Python for natural language processing: classification, named entity recognition, sentiment analysis and information extraction. I have to write many complex custom scripts fast.

Based on my earlier experience with writing smaller Python scripts I was concerned about writing a bigger application. I found a good setup with PyDev, unit test and source control. It gives me much of the stability I am used to in a compiled language, while I can still can do rapid development.

-Sami Badawi

Natural language processing in Clojure, Go and Cython

2010-10-29T22:51:00.001-04:00

I work in natural language processing, programming in C# 3.5 and Python. My work includes classification, named entity recognition, sentiment analysis and information extraction. Both C# and Python are great languages, but I do have some unmet needs. I investigated if there are any new languages that would help. I only looked at minimal language that would be simple to learn. The 3 top contenders were: Clojure, Go and Cython. Both Clojure, Go have innovative approaches to non locking concurrency. This is my first impression of working with these languages.

For contrast let me start by listing the features of my current languages.

C# 3.5

C# is an advanced object orientated / functional hybrid language and programming platform:

It is fast
Great development environment
You can do almost any tasks in it
Great database support with LINQ to SQL
Advanced web development with ASP.net
Advanced GUI toolkit with WPF
Good concurrency with threading library
Good MongoDB library

Issues

Works best on Windows
Not well suited for rapid development

While many features of C# are not directly related to NLP they are very convenient. C# has some NLP libraries: SharpNLP is a port of OpenNLP from Java. Lucene has also been ported. The ports are behind the Java implementation, but still give a good foundation.

Python

Python is an elegant scripting language, with a strong focus on simplicity.

NLTK is a great NLP library
Lot of open source math and science libraries
PyDev is a good development environment
Good MongoDB library
Great for rapid development

Issues

It is interpreted and not very fast
Problems with GIL based threading model

C# vs. Python and unmet needs

I was not sure what language I would prefer to work with. I suspected that C# would win out with all it advanced features. Due to demand for fast turnaround, I ended up doing more work in Python, and have been very happy with that choice. I have a lot of scripts that can be piped together to create new applications, with the help of the very fast and flexible MongoDB.

I do have some concerns about Python moving forward:

Will it scale if I get really large amount of text
Will speed improve on multi core processors
Will it work with cloud computing
Part of speech tagging is slow

Java

Java is a modern object oriented language. Like C# it is a programming platform:

Has most NLP libraries: OpenNLP, Mahout, Lucene, WEKA
It is fast
Great development environment: Eclipse and NetBeans
You can do almost any tasks in it
Great database support with JDBC and Hibernate
Many web development frameworks
Good GUI toolkit: Swing and JavaFX
Good concurrency with threading library

Issues

Functional style programming is clumsy
Working with MongoDB is clumsy
Java code is verbose

I would not hesitate using Java for NLP, but my company is not a Java shop.

Clojure

Clojure was released in 2007. It is a right sized LISP. Not very big like Common LISP or very small like Scheme.

Gives easy access to Java libraries: OpenNLP, Mahout, Lucene, WEKA, OpinionFinder
Innovative non locking concurrency primitives
Good IDEs in Eclipse and NetBeans
Easy to work with
Code and data is unified
Interactive REPL
LISP is the classic artificial intelligence language
If you need speed you can write Java code
Good MongoDB library

Issues

The IDE is not working as well as IDEs for Java or C#

Clojure is minimal in the sense that it is build on around 10 primitive programming constructs. The rest of the language is constructed with macros written in Clojure.

Once I got Clojure installed it was easy to work with and program in. Most of the good features about Python also applies to Clojure: it is minimal and has batteries included. Still I think that Python is a simpler language than Clojure.

Use case
Clojure is a good way to script the extensive Java libraries, for rapid development. It has more natural interaction with MongoDB than Java.

Clojure OpenNLP

The clojure-opennlp project is a thin Clojure wrapper around OpenNLP. It came with all the corpora used as training data for OpenNLP nicely packaged and it works well. You can script OpenNLP approximately as terse as NLTK, from an interactively repl.

I tried it in both Eclipse and NetBeans. They seem somewhat equal in number of features. I had a little better luck with the Eclipse version.

clojure-opennlp is using a Maven built system, but has a nontraditional directory layout, this caused problems for both Eclipse and NetBeans, they both took some configuration.

Eclipse Counterclockwise
The Counterclockwise instruction for labrepl mainly worked for installing clojure-opennlp.
When you were done you had to go in add the example directory the source directories under properties.

NetBeans Enclojure
I imported the project. I had to move the Clojure file from example directory to a different position to get it to work.

Maven plugins for Clojure
The standard Maven directory layout has several advantages, e.g. if you want to mix Java and Clojure code. I created my own Maven pom configuration file up, based on examples of other Clojure Maven projects. They used Clojure plugins for Maven, I could not get this to work. Eventually I ripped these plugins out and was left with very pain POM file that worked.

Go / Golang

Go was announced November 2009. It is created by Google to deal with multicore and networked machines. It feels like a mixture of Python and C. It is a very clean and minimal language.

It is fast
Good standard library
Excellent support for concurrency
It is trivial to write your own load balancer

Issues

The Eclipse IDE is in an early stage
Debugger is not working
Windows port is not done and has just been released

It was hard to find the right Go Windows port, there are several Go windows port projects with no code.

Use cases
I currently have a problem when downloading a lot HTML pages and parsing them to a tree structure. This does not have the best support in C#. I found a library that translates HTML to XHTML and then I can use LINQ to process it. The library is not documented, not very fast and fails for some HTML files.

Go comes with a HTML library that parses HTML 5, it is simple to write a program with some threads that download and other that parse the files into a DOM tree structure.
I would use Golang for loading large amounts of text in a cloud computing environment.

Cython

Cython was released in July 2007. It is a static compiler to write Python extension modules in a mixture of Python and C.

Process for using Cython

Start by writing normal Python code
Find modules that are too slow
Add static types
Compile it with Cython using the setup tool
This produces compiled modules that can be used with normal Python

Issues

It is still more complex that normal Python code
You need to know C to use it

I was surprised how simple it was to get it working both under Windows and Linux. I did not have to mess with make files or configure the compiles. Cython integrated well with NumPy and SciPy. This expands the programming tasks you can do with Python substantially.

Use cases
Speed up slow POS tagging.

My previous language experience

Over the years I have experimented with a long list of non mainstream languages: functional, declarative, parallel, array, dynamic and hybrid languages. Many of these were frustrating experiences. I would read about a new language and get very excited. However this would often be the chain of events:

Download language
Installed Cygwin
Find out how the language's build system works
Try to find a version of the GCC compiler that will compile it
Get the right version of Emacs installed
Try to get the debugger working under Emacs
Start programming from scratch since the libraries were sparse
Burn out

You only have so much mental capacity, and if you do not use a language you forget it. Only Scala made it into my toolbox.

Do Clojure, Go or Cython belong in your programmer's toolbox

Clojure, Go and Cython are all simple languages. They are easy to install, easy learn, they all have big standard libraries so you can be productive in them right away. This is my first impression:

Clojure is a good way to script the extensive Java libraries, for rapid application development and for AI work.
Go is a great language but it is still rough around the edges. There are not any big NLP libraries written for Go yet. I would not try to use it for my main NLP tasks.
Cython was useful right away for my NLP work. It makes it possible to do fast numerical programming in Python without too much trouble.

-Sami Badawi

Orange, R, RapidMiner, Statistica and WEKA

2010-06-23T21:20:00.122-04:00

Review of open source and cheap software packages for Data Mining

This blog posting is comparing the following tools, after working with them for 2 months and using them for solving a real data mining problem:

Orange
R
RapidMiner
Statistica 8 with Data Miner module
WEKA

Statistica is commercial, all the other are open source. There is also a brief mention of the following Python libraries: mlpy, ffnet, NLTK.

Summary of first impression

This is a follow up on my previous post R, RapidMiner, Statistica, SSAS or WEKA describing my impression of the following software packages after using them for a couple of days each:

R
RapidMiner
SciPy
SQL Server Analysis Services, Business Intelligence Development Studio
SQL Server Analysis Services, Table Analysis Tool for Excel
Statistica 8 with Data Miner module
WEKA

Let me summarize what I found:

SciPy did not have what I needed. However I found a few other good Python-based solutions: Orange, mlpy, ffnet and NLTK.

The SSAS-based solutions held promise due to their close integration with Microsoft products, but I found them to be too closely tied to data warehouses so I postponed exploring them.

Statistica and RapidMiner had a lot of functionality and were polished, but the many features were overwhelming.

R was harder to get started with and WEKA was less polished, so I did not spend too much time on them.

Comparison matrix

In order to compress my current findings I am summarizing it in this matrix. This metric is only based on limited work with the different software packages and is not very accurate. The categories are:
Documentation; GUI and graphics; how polished the package is; ease of learning; controlling package from a script or program; how many machine learning algorithms that are available:

	Doc	GUI	Polished	Ease	Scripting	Algorithms
Orange	2	3	2	3	3	2
Python libs	1	1	1	3	3	2
R	3	2	2	1	3	2
RapidMiner	2	3	2	2	2	3
Statistica	3	3	3	2	2	3
WEKA	2	2	2	3	2	3

Criteria for software package comparison

The comparison is based on a real data mining task that is relatively simple:

Supervised learning for categorization.
Over 200 attributes mainly numeric but 2 categorical / text.
One of the categorical attributes is the most important predictor.
Data is clean, so no need to clean outliers and missing data.
Accuracy is a good metric.
GUI with good graphic to explore the data is a plus.

General observations

The most popular data mining packages in the industry are SAS and SPSS, but they are quite expensive. Orange, R, RapidMiner, Statistica and WEKA all can be used for doing real data mining work. While some of them are unpolished.

There was a similar learning curve for most of the programs. Most programs took me a few days to get working, between the documentation and experimenting.

I had to reformulate my original problem. Neural network models did not work well on my categorical / text attributes. Statistica produced an accuracy of 90%, while RapidMiner produced an accuracy of 82%.
I replaced the 2 categorical attributes with a numeric attribute and accuracy of the best model increased to around 97%, and was much more uniform between the different tools.

Orange

Orange is an open source data mining package build on Python, NumPy, wrapped C, C++ and Qt.

Works both as a script and with an ETL work flow GUI.
Shortest script for doing training, cross validation, algorithms comparison and prediction.
I found Orange the easiest tool to learn.
Cross platform GUI.

Issues:

Not super polished.
The install is big since you need to install QT.

Python libs: ffnet, NumPy, mlpy, NLTK

A few Python libs deserve to be mentioned here: ffnet, NumPy, mlpy and NLTK.

If you do not care about the graphic exploration, you can set up an ffnet neural network in few lines of code.
There are several machine learning algorithms in mlpy.
The machine learning is NLTK is very elegant if you have a text mining or NLP problem.
The libraries are self contained.

Issues:

Limited list of machine learning algorithms.
Machine learning is not handled uniformly between the different libraries.

R

R is an open source statistical and data mining package and programming language.

Very extensive statistical library.
It is a powerful elegant array language in the tradition of APL, Mathematica and MATLAB, but also LISP/Scheme.
I was able to make a working machine learning program in just 40 lines of code.

Issues:

Less specialized towards data mining.
There is a steep learning curve, unless you are familiar with array languages.

R vs. Orange written in Python

Python and R have a lot in common: they are both elegant, minimal, interpreted languages with good numeric libraries. Still they have a different feel. So I was interested in seeing how they compared.

Orange / Python advantages

R is quite different from common programming languages.
Python is easier for most programmers to learn.
Python has better debugger.
Scripting data mining categorization problems is simpler in Orange.
Orange also has an ELT work flow GUI.

R advantages

R is even more minimal than Python.
Numerical programming is better integrated in R, in Python where you have to use external packages NumPy and SciPy.
R has better graphics.
R is more transparent since the Orange are wrapped C++ classes.
Easier to combine with other statistical calculations.

I made small script to solve my data mining problem in both Orange and R. This was my impression:

If all you want to do is to solve a categorization problem I found Orange to be simpler. You have to become very familiar with how Orange read the spreadsheet, the different attribute types, notably the Meta attribute.

Import and export of data from spreadsheet is easier in R, spreadsheet are stored in a data frames that the different machine learning algorithms are operating on. Programming in R really is very different, you are working on a higher abstraction level, but you do lose control over the details.

RapidMiner

RapidMiner is an open source statistical and data mining package written in Java.

Solid and complete package.
It easily reads and writes Excel files and different databases.
You program by piping components together in a graphic ETL work flows.
If you set up an illegal work flows RapidMiner suggest Quick Fixes to make it legal.

Issues:

I only got it to works under Windows, but others have gotten it to work in other environments, see comment below.
There are a lot of different ETL modules; it took a while to understand how to use them.
First I had a hard time making a comparison between different models. Eventually I found a way: You chose a cross validation and select different models one by one. When you run the model the will all be stored on the result page and you can do comparison there.

Statistica 8

Statistica is a commercial statistics and data mining software package for Windows.
There is a 90 day trial for Statistica 8 with data miner module in the textbook:
Handbook of Statistical Analysis and Data Mining Applications. There is also a free 30 day trial.

Generally very polished and good at everything, but it is also the only non open source program.
High accuracy even when I gave it bad input.
You can script everything in Statistica in VB.
Cheap compared to SPSS and SAS.

Issues:

So many options that it was hard to navigate the program.
The most important video about Data Miner Recipes is the very last out of 36.
Cost of Statistica is not available on their website.
It is cheap in a corporate setting, but not for private use.

WEKA

WEKA is an open source statistical and data mining library written in Java.

A lot of machine learning algorithms.
Easy to learn and use.
Good GUI.
Platform independent.

Issues:

Worse connectivity to Excel spreadsheet and non Java based databases.
CSV reader not as robust as in RapidMiner.
Not as polished.

RapidMiner vs. WEKA

The most similar data mining packages are RapidMiner and WEKA. There have many similarities:

Written in in Java.
Free / open source software with GPL license.
RapidMiner includes many learning algorithms from WEKA.

My first thought what that RapidMiner has everything that WEKA has, plus a lot of other functionality and is more polished. Therefore I did not spend too much time on WEKA. For the sake of completeness I took a second look at WEKA and I have to say that it was a lot easier to get WEKA to work. Sometimes less is more. Depending on what is more important functionality or ease of use.

Conclusion

There are several good and very different solutions. Let me finish by listing the strongest aspect of each tool:

Orange has elegant and concise scripting and can also be run in an ETL GUI mode.
R has elegant and concise scripting integrated with a vast statistical library.
RapidMiner has a lot of functionality, is polished and has good connectivity.
Statistica is the most polished product, and generally performed well in all categories. It gave good result when I gave it bad input.
WEKA is the easiest GUI to learn and use.

-Sami Badawi

R, RapidMiner, Statistica, SSAS or WEKA

2010-04-29T20:58:00.082-04:00

Choosing cheap software packages to get started with Data Mining

You have a data mining problem and you want to try to solve it with a data mining software package. The most popular packages in the industry are SAS and SPSS, but they are quite expensive, so you might have a hard time convincing your boss to purchase them before you already have produced impressive results.

When I needed data mining or machine learning algorithms in the past, I would program it from scratch and integrate it in my Java or C# code. But recently I needed a more interactive graphics environment to help with what is called Data Understanding phase in the CRISP-DM. I also wanted a way to compare the predictive accuracy of a broad array of algorithms, so I tried out several packages:

R
RapidMiner
SciPy
SQL Server Analysis Services, Business Intelligence Development Studio
SQL Server Analysis Services, Table Analysis Tool for Excel
Statistica 8 with Data Miner module
WEKA

Disclaimer for review

Here is a review of my first impression of these packages. First impression is not the best indicator for what going to work for you in the long run. I am sure that I have missed many features. Still I hope this can save you some time finding a solution that will work for your problem.

R

R is an open source statistical and data mining package and programming language.

Very extensive statistical library.
Very concise for solving statistical problems.
It is a powerful elegant array language in the tradition of APL, Mathematica and MATLAB, but also LISP/Scheme.
In a few lines you can set up an R program that does data mining and machine learning.
You have full control.
It is easier to integrate this into a work flow with your other programs. You just spawn an R program and pass input in and read output from a pipe.
Good plotting functionality.

Issues:

Less interactive GUI.
Less specialized towards data mining.
Language is pretty different from current mainstream languages like C, C#, C++, Java, PHP and VB.
There is a learning curve, unless you are familiar with array languages.
R was created in 1990.

Link: Screencast showing how a trained R user can generate a PMML neural network model in 60 seconds.

RapidMiner

RapidMiner is an open source statistical and data mining package written in Java.

Lot of data mining algorithms.
Feels polished.
Good graphics.
It easily reads and writes Excel files and different databases.
You program by piping components together in a graphic ETL workflows.
If you set up an illegal workflows RapidMiner suggest Quick Fixes to make it legal.
Good video tutorials / European dance parties. *:o)

Issues:

I only got it to works under Windows, but others have gotten it to work in other environments.
Harder to compare different algorithms than WEKA.

SciPy

SciPy is an open source Python wrapper around numerical libraries.

Good for mathematics.
Python is a simple, elegant and mature language.

Issues:

Data mining part is too immature.
Too much duct tape.

SQL Server Business Intelligence Development Studio

Microsoft SQL Server Analysis Services comes with data mining service.
If you have access to SQL Server 2005 or later with SSAS installed, you can use some of the data mining algorithms for free. If you want to scale it can become quite expensive.

If your are working with the Microsoft stack this integrate well.
Good data mining functionality.
Organized well.
Comes with some graphics.

Issues:

The machine learning is closely tied to data warehouses and cubes. This makes the learning curve steeper and deployment harder.
Documentation about using the BIDS GUI was hard to find. I looked in several books and several videos.
I need to do my data mining from within a web server or a command line program. For this you need to access the models using: Analysis Management Objects (AMO). Documentation for this was also hard to find.
You need good cooperation from your DBA, unless you have your own instance of SQL Server.
If you want to evaluate the performance of your predictive model, cross-validation is available only in SQL Server 2008 Enterprise.

Link: Good screencast about data mining with SSAS.

SQL Server Analysis Services, Table Analysis Tool Excel

Microsoft Excel data mining plug-in is dependent on SQL Server 2008 and Excel 2007.

This takes less interaction with the database and DBA than the Development Studio.
A lot of users have their data in Excel.
There is an Analysis ribbon / menu that is very simple to use. Even for users with very limited understanding of data mining.
The Machine Learning ribbon has more control over internals of the algorithms.
You can run with huge amount of data since the number crunching is done on the server.

Issues:

This also needs a connection to a SQL Server 2008 with Analysis Services running. Despite the data mining algorithms being relatively simple.
You need a special database inside Analysis Services that you have write permissions to.

Link: Excel Table Analysis Tool video

Statistica 8

Statistica is a commercial statistics and data mining software package.
There is a 90 day trial for Statistica 8 with data miner module in the textbook:
Handbook of Statistical Analysis and Data Mining Applications. There is also a free 30 day trial.

Statistica is cheaper than SAS and SPSS.
Six hours of instructional videos.
Data Miner Recipes wizard is the easiest tool for a beginner.
Lot of data mining algorithms.
GUI with a lot of functionality.
You program using menus and wizards.
Good graphics.
Easy to find and clean up outliers and missing data attributes.

Issues:

Overwhelming number of menu items.
The most important video about Data Miner Recipes is the very last.
Cost of Statistica is not available on their website.
It is cheap in a corporate setting, but not for private use.

WEKA

WEKA is an open source statistical and data mining library written in Java.

Many machine learning packages.
Good graphics.
Specialized for data mining.
Easy to work with.
Written in pure Java so it is multi platform.
Good for text mining.
You can train different learning algorithms at the same time and compare their result.

RapidMiner vs WEKA:

The most similar data mining packages are RapidMiner and WEKA. There have many similarities:

Written in in Java.
Free / open source software with GPL license.
RapidMiner includes many learning algorithms from WEKA.

Therefore the issues with WEKA is really how it compares to RapidMiner.

Issues compared to RapidMiner:

Worse connectivity to Excel spreadsheet and non Java based databases.
CSV reader not as robust.
Not as polished.

Criteria for software package comparison

My current data mining needs are relatively simple. I do not need the most sophisticated software packages. This is what I need now:

Supervised learning for categorization.
Over 200 features mainly numeric but 2 categorical.
Data is clean so no need to clean outliers and missing data.
Not important to avoiding mistakes.
Equal cost for type 1 and type 2 errors.
Accuracy is a good metric.
Easy to export model to production environment.
Good GUI with good graphic to explore the data.
Easy to compare a few different models e.g. boosted trees, naive bayes, neural network, random forest and vector support machine.

Summary

I did not have time to test all the tools enough for a real review. I was only trying to determine what data mining software packages to try first.

Try first list

Statistica: Most polished, easiest to get started with. Good graphics and documentation.
RapidMiner: Polished. Simplest and most uniform GUI. Good graphics. Open source.
WEKA: A little unpolished. Good functionality for comparing different data mining algorithms.
SSAS Table Analysis Tool, Data Mining ribbon: Showed promise, but I did not get it to do what I need.
SSAS BIDS: Close tie to cube and data warehouse. Hard to find documentation about AMO programming. Could possibly give best integration with C# and VB.NET.
SSAS Table Analysis Tool, Analysis ribbon: Simple to use but does not have the functionality I need.
R: Not specialized towards data mining. Elegant but different programming paradigm.
SciPy: Data mining library too immature.

Both RapidMiner and Statistica 8 do what I need now. So far I have found it easier to find functions using Statistica's menus and wizards, than RapidMiner's ETL workflows, but RapidMiner is open source. Still I would not be surprised if ended up using one or more than one package.

Preliminary quality comparison of Statistica and RapidMiner

I ran my predictive modeling task in both Statistica and RapidMiner. In the first match the model that preformed best in Statistica was neural network, with an error rate of approximately 10%.

I ran the neural network in RapidMiner the error rate was approximately 18%. I was surprised about the big difference. The reason is probably that one of my most important attributes is categorical with many values, and neural network does not work well with that. Statistica might have preformed better due to more hidden layers.

Second time I ran my predictive model, Statistica was having some numeric overflow for neural network and there were missing prediction values. This also surprised me I would expect that there could be problems with the training of the neural network, but not the calculation of and input on a trained model.

These problems can easily be the result of me being unfamiliarity with the software packages, but this was my first impression.

Link to my follow up post that is based on solving an actual data mining problem in Orange, R, RapidMiner, Statistica and WEKA after working with them for 2 months.

-Sami Badawi

Data Mining rediscovers Artificial Intelligence

2010-04-03T23:08:00.040-04:00

Artificial intelligence started in the 1950s with very high expectations. AI did not deliver on the expectations and fell into decades long discredit. I am seeing signs that Data Mining and Business Intelligence are bringing AI into mainstream computing. This blog posting is a personal account of my long struggle to work in artificial intelligence during different trends in computer science.

In the 1980s I was studying mathematics and physics, which I really enjoyed. I was concerned about my job prospects, there are not many math or science jobs outside of academia. Artificial intelligence seemed equally interesting but more practical, and I thought that it could provide me with a living wage. Little did I know that artificial intelligence was about to become an unmentionable phrase that you should not put on your resume if you wanted a paying job.

Highlights of the history of artificial intelligence

In 1956 AI was founded.
In 1957 Frank Rosenblatt invented Perceptron, the first generation of neural networks. It was based on the way the human brain works, and provided simple solutions to some simple problems.
In 1958 John McCarthy invented LISP, the classic AI language. Mainstream programming languages have borrowed heavily from LISP and are only now catching up with LISP.
In the 1960s AI got lots of defense funding. Especially military translation software translating from Russian to English.

AI theory made quick advances and a lot was developed early on. AI techniques worked well on small problems. It was expected that AI could learn, using machine learning, and this soon would lead to human like intelligence.

This did not work out as planned. The machine translation did not work well enough to be usable. The defense funding dried up. The approaches that had worked well for small problems did not scale to bigger domains. Artificial intelligence fell out of favor in the 1970s.

AI advances in the 1980s

When I started studying AI, it was in the middle of a renaissance and I was optimistic about recent advances:

The discovery of new types of neural networks, after Perceptron networks had been discredited in an article by Marvin Minsky
Commercial expert system were thriving
The Japanese Fifth Generation Computer Systems project, written in the new elegant declarative Prolog language had many people in the West worried
Advances in probability theory Bayesian Networks / Causal Network

In order to combat this brittleness of intelligence Doug Lenat started a large scale AI project CYC in 1984. His idea was that there is no free lunch, and in order to build an intelligent system, you have to use many different types of fine tuned logical inference; and you have to hand encode it with a lot of common sense knowledge. Cycorp spent hundreds of man years building their huge ontology. Their hope was that CYC would be able to start learning on its own, after training it for some years.

AI in the 1990s

I did not loose my patience but other people did, and AI went from the technology of the future to yesterday's news. It had become a loser that you did not want to be associated with.

During the Internet bubble when venture capital founding was abundant, I was briefly involved with an AI Internet start up company. The company did not take off; its main business was emailing discount coupons out to AOL costumers. This left me disillusioned, thinking that I just have to put on a happy face when I worked on the next web application or trading system.

AI usage today

Even though AI stopped being cool, regular people are using its use it in more and more places:

Spam filter
Search engines use natural language processing
Biometric, face and fingerprint detection
OCR, check reading in ATM
Image processing in coffee machine detecting misaligned cups
Fraud detection
Movie and book recommendations
Machine translation
Speech understanding and generation in phone menu system

Euphemistic words for AI techniques

The rule seem to be that you can use AI techniques as long as you call it something else, e.g.:

Business Intelligence
Collective Intelligence
Data Mining
Information Retrieval
Machine Learning
Natural Language Processing
Predictive Analytics
Pattern Matching

AI is entering mainstream computing now

Recently I have seen signs that AI techniques are moving into mainstream computing:

I went to a presentation for SPSS statistical modeling software, and was shocked how many people now are using data mining and machine learning techniques. I was sitting next to people working in a prison, adoption agency, marketing, disease prevention NGO.
I started working on a data warehouse using SQL Server Analytic Services, and found that SSAS has a suite of machine learning tools.
Functional and declarative techniques are spreading to mainstream programming languages.

Business Intelligence compared to AI

Business Intelligence is about aggregating a company's data into an understandable format and analyzing it to provide better business decisions. BI is currently the most popular field using artificial intelligence techniques. Here are a few words about how it differs from AI:

BI is driven by vendors instead of academia
BI is centered around expensive software packages with a lot of marketing
The scope is limited, e.g. find good prospective customers for your products
Everything is living in databases or data warehouses
BI is data driven
Reporting is a very important component of BI

Getting a job in AI

I recently made a big effort to steer my career towards AI. I started an open source computer vision project, ShapeLogic and put AI back on my resume. A head hunter contacted me and asked if I had any experience in Predictive Analytics. It took me 15 minutest to convince her that Predictive Analytics and AI was close enough that she could forward my resume. I got the job, my first real AI and NLP job.

The work I am doing is not dramatically different from normal software development work. I spend less time on machine learning than on getting AJAX to work with C# ASP.NET for the web GUI; or upgrade the database ORM from ADO.NET strongly typed datasets to LINQ to SQL. However, it was very gratifying to see my program started to perform a task that had been very time consuming for the company's medical staff.

Is AI regaining respect?

No, not now. There are lots of job postings for BI and data mining but barely any for artificial intelligence. AI is still not a popular word, except in video games where AI means something different. When I worked as a games developer what was called AI was just checking if your character was close to an enemy and then the enemy would start shooting in your character's direction.

After 25 long years of waiting I am very happy to see AI techniques has finally become a commodity, and I enjoy working with it even if I have to disguise this work by whatever the buzzword of the day is.

-Sami Badawi

SharpNLP vs NLTK called from C# review

2010-03-17T22:23:00.023-04:00

C# and VB.net have fewer open source NLP libraries than languages like C++, Java, LISP and Perl. My last blog post: Open Source NLP in C# 3.5 using NLTK is about calling NLTK, which is written in Python, from IronPython embedded under C# or VB.net.

An alternative is to use SharpNLP, which is the leading open source NLP project written in C# 2.0. SharpNLP is not as big as other Open Source NLP projects. This blog posting is a short comparison of SharpNLP and NLTK embedded in C#.

Documentation

NLTK has excellent documentation, including an introductory online book on NLP and Python programming.

For SharpNLP the source code is the documentation. There is also a short introductory article by SharpNLP's author Richard J. Northedge.

Ease of learning

NLTK is very easy to work with under Python, but integrating it as embedded IronPython under C# took me a few days. It is still a lot simpler to get Python and C# to work together than Python and C++.

SharpNLP's lack of documentation makes it harder to use; but it is very simple to install.

Ease of use

NLTK it is great to work with in the Python interpreter.

SharpNLP simplifies life by not having to deal with the embedding of IronPython under C# and the mismatching between the 2 languages.

Machine learning and statistical models

NLTK comes with a variety of machine learning and statistical models: decision trees, naive Bayesian, and maximum entropy. They are very easy to train and validate, but do not preform well for large data sets.

SharpNLP is focused on maximum entropy modeling.

Tokenizer quality

NLTK has a very simple RegEx based tokenizer that works well in most cases.

SharpNLP has a more advanced maximum entropy based tokenizer that can split "don't" into "do | n't". On the other hand it sometimes makes errors and splits a normal word into 2 words.

Development community

NLTK has an active development community, with an active mailing list.

SharpNLP was last release was in December 2006. It is a port of the Java based OpenNLP, and can read models from OpenNLP. SharpNLP has a low volume mailing list.

Code quality

NLTK lets you write programs that read from web pages, clean HTML out of text and do machine learning in a few lines of code.

SharpNLP is written in C# 2.0 using generics. It is a port from OpenNLP and maintains a Java flavor, but it is still very readable and pleasant to work with.

License

NLTK's license is Apache License, Version 2.0, which should fit most people's need.

SharpNLP's license is LGPL 2.1. This is a versatile license, but maybe a little harder to work with when the project is not active.

Applications

NLTK comes with a theorem prover for reasoning about semantic content of text.

SharpNLP comes with an name, organization, time, date and percentage finder.
It is very simple to add an advanced GUI, using WPF or WinForms.

Conclusion

Both packages comes with a lot of functionality. They both have weaknesses, but they are definitely usable. I have both SharpNLP and embedded NLTK in my NLP toolbox.

-Sami Badawi

Open Source NLP in C# 3.5 using NLTK

2010-03-11T07:02:00.022-05:00

I am working on natural language processing algorithms in a C# 3.5 environment. I did not find any open source NLP packages for C# or VB.NET.
NLTK is a great open source NLP package written in Python. It comes with an online book. I decided to try to embed IronPython under C# and run NLTK from there. Here are a few thoughts about the experience.

Problems with embedding IronPython and NLTK

Some libraries that NLTK uses are not installed in IronPython, e.g. zlib and numpy, you can mainly patch this up
You need a good understanding of how embedded IronPython works
The connection between Python and C# is not seamless
Sending data between Python and C# takes work
NLTK is pretty slow at starting up
Doing large scale machine learning in NLTK is slow

C# and IronPython

IronPython is a very good implementation of Python, but in C# 3.5 there is still a mismatch between C# and Python; this becomes an issue when you are dealing with a library as big as NLTK.
The integration between IronPython and C# is going to improve with C# 4.0. How much remains to be seen.

To embed or not to embed

When is embedding IronPython and NLTK inside C# a good idea?

Separate processes for NLTK under CPython and C#

If your C# tasks and your NLP tasks are not interacting too much, it might be simpler to have a C# program call a NLP CPython program as an external process. E.g. you want to analyze the content of a Word document. You would open the Word document in C# create a Python process pipe the text into it and read the result back in JSON or XML and display it in ASP, WPF or WinForms.

Small NLP tasks

There is a learning curve for both NLTK and embedded IronPython, that slows down you down when you start work.

Medium sized NLP projects

The setup cost is not an issue so embedding IronPython and NLTK could work very well here.

Big NLP projects

The setup cost is not an issue, but at some point the mismatch between Python and C#, will start to outweigh the advantages you get.

Prototyping in NLTK

Start writing your application in NLTK either under CPython or IronPython. This should improve development time substantially. You might find that your prototype is good enough and you do not need to port it to C#; or you will have a working program that you can port to C#.

References

Post about running NLTK from IronPython
Chapter 15 of IronPython in Action is about embedding IronPython in C# or VB.NET
Source code examples from IronPython in Action
Here is a short intro to embedding IronPython by Michael Foord
I tried loading Jeff Hardy's IronPython.Zlib.dll using Assembly.LoadFile, that did not work but I could add it with clr.AddReference from the embedded Python code

-Sami Badawi

Computer vision C++ libraries review

2008-11-17T15:23:00.004-05:00

I am trying to create an easy to use, minimalistic C++ cross-platform computer vision system, with a non-restrictive license. My biggest challenge was to chose the best libraries and to get them to work together; this took some investigation and experimenting. This posting is a brief description of my findings.

This is what ShapeLogic C++ currently looks like:

Windows

Linux

In order to construct ShapeLogic C++, I had to make choices within the following categories:

Computer vision and image processing libraries
GUI libraries
Unit test systems
Build systems
Compilers under Windows
C++ IDEs under UNIX

ImageJ, the Java open source image processing tool, is the inspiration for the first part of my work: it is very simple to learn, use and program in. This is a follow up to my last posting: Computer Vision C++ vs Java. The result of my work is released as an open source project ShapeLogic C++, under the MIT license.

Computer vision and image processing libraries

The candidates I considered were:

GIL, Generic Image Library
OpenCV
VXL

GIL, Generic Image Library

GIL, Generic Image Library by Adobe.

Pros

Very non intrusive, only based on header files
Puts a wrapper around most image format
You can write a algorithm once and it will work for most image types
Part of Boost since 1.35

Cons

Does not come with a lot of image processing algorithms

OpenCV

OpenCV, Open Computer Vision by Intel.

Pros

Very simple
Works with both C and C++
Very broad range of algorithms
Complex algorithms: face detection, convexity defects
Very popular

Cons

You have to use OpenCV's IplImage
IplImage byte order is BGR instead of the normal RGB

VXL, Vision X Library

VXL a combination of 2 big older vision libraries TargetJR and IUE

Pros

Well tested technology
Simpler build process using cmake
Uses modern programming techniques: classes, template and STL
It has a lot of functionality
Simple to get started with

Cons

It is not using normal STL, but in order to work on different compiler it had to make its own version with different names.
Class structure is somewhat complex.

Choice computer vision library for ShapeLogic C++
OpenCV for existing image processing and vision algorithms. GIL for writing new algorithms.

Cross platform GUI

The candidates I considered were:

GIMP plugin
GTK+, GIMP toolkit
FLTK
HighGui from OpenCV
PhotoShop plugin
wxWidget

Run ShapeLogic as a GIMP plugin

Pros

GIMP is the main cross platform OSS image editing programs.
It is in wide use.
Has a lot of powerful features including scripting functionality in Scheme and Python.
From a user perspective this would be an excellent choice.

Cons

GIMP is GPL, but you could have a wrapper around plugins in order to access them as GIMP plugins.
The plugin works with tiles, which gives good performance, but does not fit well with either the way OpenCV or GIL are processing images.

GTK+, GIMP Toolkit

Pros

GTK+ is a great looking and very powerful framework that works on: Windows, Linux, Mac, a.o.

Cons

It is written in C and has a homegrown object system, which is not type safe.

GTKMM C++ wrapper around GTK+

Pros

CTKMM is a great looking and very powerful framework, that works on: Windows, Linux, Mac, a.o.
It feels natural to program in for a C++ programmer.

Cons

The class hierarchy is somewhat deep since it is built on top of GTK.

FLTK, Fast light toolkit

Pros

FLTK is very lightweight.
Very clean C++, you actually have a main().
Native C++ build on top of X11 or Windows.
Fluid, a simple GUI builder

Cons

Not as many widgets.
Dated look.

HighGui from OpenCV

Pros

Very lightweight.
There is some functionality for displaying images, video and an event handler for mouse events.

Cons

Does not come with a menu system.

Run ShapeLogic as a PhotoShop plugin

Pros

PhotoShop is the main image editing programs.
It is in wide use, has a lot of powerful features including macros.
From a user perspective this would be an excellent choice.

Cons

The PhotoShop SDK is not freely available, you have to apply to get it.
The plugin does not fit well with either the way OpenCV or GIL are processing images.

wxWidgets

Pros

wxWidgets is a full featured GUI toolkit, built on top of native toolkits: Win32, Mac OS X, GTK+, X11, Motif, WinCE and more.
Looks good and modern.
Big community.
Several GUI builders.

Cons

The programming style is close to Windows MFC programming.
There are many layers.

Choice
This was a hard choice and I went back and forth between FLTK and wxWidgets, but went with FLTK. All the GUI code is separate from the image processing code, so if I wanted to change from FLTK to another toolkit later it should not be too dramatic.

C++ unit test frameworks

There are a lot of different choices and no clear leader. Some of the candidates were:

Boost.test
CppUnit
Google C++ Testing Framework

Boost.test

Pros

Boost.test is part of the Boost library.
Powerful with a lot of options.

Cons

You have to manually set up test suites.
It is somewhat heavy.
The documentation is extensive but not easy to read.

CppUnit

Pros

CppUnit is following a standard unit testing convention XUnit.
Integration with Eclipse CDT.

Cons

You have to manually set up test suites.
It is an extra library to install.

Google C++ Testing Frameworks

Pros

Google test is following a standard unit testing convention XUnit.
Strong focus on simplicity.
Documentation is short and easy to read.

Cons

It is an extra library to install.

Choice of C++ unit test framework for ShapeLogic C++

I spent quite a bit of time reading the Boost Test documentation, finally I tried Google C++ Testing Framework and got it working very fast.

Build system

The candidates I considered were:

Boost build
Make

Boost build

Pros

Boost build is part of Boost.
Clean design, made as a Make replacement.
Works on most platforms and with most compilers.
The scripts are pretty short.

Cons

There is a learning curve.

Make

Pros

Make is the standard for build on C++.
Widely used.
Works with Eclipse, MSVC, NetBeans.
Short scripts.

Cons

It has gotten messy over time.
Shell script dependency.
There is too much magic for my taste.

Choice of build system for ShapeLogic C++

I chose to go with Boost Build because it has a cleaner design, but Make looks very competitive when looking over the pros and cons.

Compilers under Windows

In order to compile Boost you need a pretty modern and standard compliant compiler. The candidates that I looked at are:

Cygwin GCC
MinGW GCC
MSVC Microsoft Visual C++

Cygwin GCC

Pros

Cygwin GCC is close to GCC under UNIX

Cons

Uses emulation of UNIX system call.
You can only use it to build GPL compatible application.

MinGW GCC

Pros

MingGW integrates well with Eclipse CDT.
Works more natively with Windows.
Most libraries build fine with MinGW.

Cons

It was supposed to be able to build FLTK, but I tried a few times and could not get it to work.
In order to run Make files you also have to install MSYS, which is a minimal shell.

MSVC, Microsoft Visual C++

Pros

MSVC is a high quality compiler.
Most used compiler under Windows.
There is a free Express version.

Cons

There seems to be some restrictions of the Express version that I did not quite understand.

Choice of compiler under Windows for ShapeLogic C++

MSVC.

C++ IDEs under UNIX

The candidates I considered were:

Eclipse 3.4
Emacs / Xemacs
NetBeans 6.1

Eclipse 3.4

Pros

Eclipse 3.4 CDT has a good debugger.
Easy to jump from classes to files defining the classes.

Cons

Not nearly as good as Eclipse for Java.
Unstable under Linux AMD64.

Emacs

Pros

Emacs is powerful tools that runs in a terminal.
Takes up less resources.
Not dependent on Java.

Cons

The Java bases IDE have more features.
Demands more knowledge to use.

NetBeans 6.1

Pros

NetBeans 6.1 seem a little lighter than Eclipse.

Cons

It is made to work with Make files, and ShapeLogic C++ is using Boost Build / Bjam.

Choice of IDE under UNIX for ShapeLogic C++

Eclipse.

Summary of libraries and tools used

Boost the C++ library
Generic Image Library for writing new image processing code
OpenCV for existing computer vision algorithms
FLTK, Fast Light Toolkit lightweight cross platform GUI
Google C++ Testing Framework
Boost.build v2 for command line based build system

Status of ShapeLogic C++

ShapeLogic C++ 0.4 is the first alpha release. It can do some useful work, but it still mainly an example application.

Currently has

Comes with some image processing operation
Comes with 3 brushes
It is pretty simple to program an image processing algorithm

Missing

Drawing is currently slow and there is only one pen size
None of the ShapeLogic Java algorithms have been ported yet
Documentation is poor

Hardest problems

Learning how FLTK works
Building a cross platform C++ build script covering several libraries

None of these problems will effect ShapeLogic users.

Porting computer vision code from Java to C++

Before I started porting ShapeLogic from Java, I thought that C++ was moving towards becoming a legacy language. What I have learned from this work is that C++ has advanced substantially since 2002, when I last used it professionally. C++ still seems competitive, at least in computer vision, and according to my old video game colleagues also in games, where I though that C# might have taken a lead by now. Both C++ and Java have substantial advantages.

C++

OpenCV has a lot of vision algorithms, e.g. face recognition
C++ is faster than Java
Better for video processing
Programs are shorter
Generic programming working on primitive types
You can make build script that build under both Windows and UNIX

Java / ImageJ

ImageJ has more open source algorithms for medical image processing
Better support for medical image files formats under ImageJ
IDEs are better under Java
Build process is simpler than C++
Simpler language
Better support for parallel processing
A lot easier to dynamically load plugins

The next step is to port my framework for declarative programming -- it is based on lazy streams -- and port the Color Particle Analyzer. C++ / Boost have good support for functional programming techniques: Boost.Bind and Boost.Lambda, and the Phoenix library has just been accepted into Boost. When complete, I will do another posting about how it went.

-Sami Badawi
http://www.shapelogic.org

Computer Vision C++ vs Java review

2008-09-02T06:43:00.031-04:00

In 2007 I created an open source computer vision project, ShapeLogic, built in Java to work with ImageJ. This setup has been very easy to work with and very productive. Bjarne Stroustrup the creator of C++ gave an interview about the new features in the C++0x standard and TR1. C++ now has a lot of innovating programming constructs e.g. template meta programming, lambda functions, concepts and traits. When I found out that "axiom" is going to be a keyword in C++ my inner mathematician demanded that I take a second look at C++ in connection with computer vision.

This post is a review of my personal past experience with computer vision in C++ and Java. I did my masters thesis in computer vision in the early 90ies, but I ended up working in other fields: video games, Internet and finance, which only left a little time to do vision in my free time. While both C++ and Java were good choices for professional vision programmers, several of the approaches I chose caused me to run out of steam. I also tried to do computer vision with functional, declarative and hybrid languages e.g. Oz, Scheme and Scala but will not cover that here.

Borland C++ early 90ies

C++ did not have STL or any other standard library so I used Borland's OWL library for images and for the application. I used C++ templates, classes with multiple inheritance, RTTI just to set up basic container functionality. There were a few books that has some free C or C++ source code for image processing and vision, but they did not spawn a user community. I did not really get to do anything interesting.

JAI, Java Advanced Imaging late 90ies

I was very excited when Java came around, this was the language to cure all programming ailments. Now they had added a library that could be used for vision and a lot of big companies were sponsoring JAI. It turned out to be a very complex framework with a deep class hierarchy, I spent a lot of time reading the manual trying to find out how to get access to image pixels. I gave up using it and the framework never gained much popularity.

VXL, C++, STL, Boost, Python, GCC, Linux around 2000

Open source software, OSS had started to become prominent. There were 2 OSS libraries:

OpenCV (Open Computer Vision), wich was still in alpha.
VXL (Vision X Library) wich was a merge of 2 big non OSS libs TargetJR and IUE.

VXL finally got into beta and I tried to combine it with Python for more high level processing.

Tools needed for build and GUI

VXL does builds using CMake to create Make files
Boost uses BJam to do builds
Python bindings using Pyste from Boost
VXL used FLTK and OpenGL as a GUI

Problems encountered

It was hard to get the different build systems, CMake, Bjam and Make, to work together
GCC 3.1 and 3.2 core dumped when compiling certain Boost classes
Python bindings worked for simple C++ classes, but not for the nested template classes in VXL
It was hard to debug the template programs
Emacs was not really as easy to use as Visual Studio
Bad drivers for OpenGL on Linux

I actually got some examples set up, but spent more time fighting with the tool stack than doing vision work.

ImageJ in Java around 2004

A colleague showed me a visualization tool he had worked on and said that he did it in around 1 month. I barely believed him, but tried the underlying framework, ImageJ. To my big surprise I was up and running and doing real work in a few hours. ImageJ just got things right. It was built using pure Java by one man, Wayne Rasband. It is very easy to work with and very modular, so a lot of people have made plugins and there is a vibrant development community. When I started working on ShapeLogic that was the best choice.

OpenCV, GIL Generic Image Library, Boost and Eclipse in C++ 2008

In the light of advance in the C++ language and tools, I have decided to try it again.
C++ image libraries choices

I chose to start with OpenCV made by Intel and GIL made by Adobe but a part of Boost since 1.35.

C++ IDE tried

Eclipse 3.4
NetBeans 6.1

Eclipse worked better for me, it has its own build system so you do not have to mess with Make files.

C++ cross platform GUIs

Not sure which one will be best for my purpose.

First attempt
I tried Boost, OpenCV and GIL and got them up and running under both Linux and Windows in a few hours. Eclipse CDT C++ IDE works great.

Porting ShapeLogic algorithms to C++ version

My plan is to port some algorithms from ShapeLogic from Java to C++. ShapeLogic is a toolkit for declarative programming, specialized for vision. In principle you should be able to make a list of rules for categorizing say the shape of a particle in a particle analyzer. You put them in a database or a flat file and the same rules should work for C++ and Java version of ShapeLogic. In practice this might not work out.

Advantages of C++ and Java

This is a loose first assessment.
Constructs used in ShapeLogic that are missing or less convenient in C++

Uniform cross platform GUI
Dynamic cross platform libraries
HashTable
Reflection
Garbage collection
Antlr for parsing logic language

Advantages of C++ over Java in vision

Substantially higher speed
Better handling of video
Used more frequently for computer vision programming
Good tracking and face recognition algorithms in OpenCV

For me, Java has been very good for doing medical image processing algorithms. I have heard conflicting evidence about whether it is feasible for doing computer vision on video using Java. Video handling in Java has been bad up to now, this is supposed to be fixed with the new JavaFX. Shadow Monsters is a computer vision based art piece taking video footage of silhouette of the viewer and adding monsters to them, I saw it on display at Museum of Modern Art. It was programmed using Processing, which is a Java based image processing tool for artists. I discussed the issue with a computer programmer / artist who said that he had tried to do a motion algorithm in Processing and had to port it to C++ based Openframeworks since Java was too slow. After being discouraged by my prior attempts to do vision in C++, I am very happy to see the dramatic developments in C++ and see if it is suitable for a simple port of ShapeLogic algorithms. The result of this C++ port will be covered in 2 postings:

Computer vision C++ libraries review
Declarative framework and Particle Analyzer Java to C++ port

-Sami Badawi
http://www.shapelogic.org

ShapeLogic 1.2 with color particle analyzer released

2008-07-07T02:43:00.006-04:00

Here are the release notes for ShapeLogic 1.2

Changes

Particle analyzer working directly on color and gray scale images without manual user intervention
Both particle counter and particle analyzer now take parameters and print reports about each particle's color, area, standard deviation to result table
Color replacer replaces one color within a tolerance with another color. Parameter input dialog with preview check box
Organize plugins and macros under ShapeLogic? and ShapeLogicOld? menus, until 1.1 they where all placed under shapelogic menu
ShapeLogic still has beta development status

The particle analyzer in ShapeLogic v 1.2 has gone through limited
testing and seems to work well. There is still a bug in the edge
tracer.

Using particle analyzer as a ImageJ plugin

The particle analyzer was tested on the particle sample images from ImageJ embryos.jpg

To run it from ImageJ select "Color Particle Analyzer" in the ShapeLogic? menu:

First a particle count dialog is displayed:

Here is the result of running the non-customized particle analyzer on it. This is written to a result table that can be exported to Excel:

The categories for the particles are only examples, it is easy to setup different rules for categorizing particles. In ShapeLogic? 1.3 there will be custom rules to recognize specific cells.

ShapeLogic? 1.2 also contains the second version of a color particle counter. It also prints a smaller report of the particle's properties.

Plans for next release

The next release, ShapeLogic v 1.3, will be a more mature particle analyzer which will come with custom rules to recognize specific cells.

Seeking particle images

In order to create these rules, I am looking for images of particles on a relatively uniform background. Please let me know if you have sample images that I could work from, preferably standard images like the embryo sample image that comes with ImageJ.

Possible future plans for particle analyzer

Create rule for recognizing cells using neural networks or machine learning techniques
Be able to handle a background that is not uniform, and cell organelles
Incorporate reasoning under uncertainty using the lazy stream library
Find overlapping particles and distinguish them as separate

Download ShapeLogic 1.2

-Sami Badawi
http://www.shapelogic.org

ShapeLogic 1.1 with particle counter released

2008-05-09T07:05:00.009-04:00

Here are the release notes for ShapeLogic 1.1

Changes

Particle counter working directly on color and gray scale images without manual user intervention
Particle counter finds average color, standard deviation, area and location for each particle
Framework to build more advanced particle counters and particle analyzers
Color clustering using K-mean algorithm
Background color finder
Extend all the image processing algorithms in ShapeLogic to work in both ImageJ and in plain Java
Better support for NetBeans
ShapeLogic still has beta development status
29000 lines of Java code
440 unit test that all works on local machine

The particle counter in ShapeLogic v 1.1 has gone through limited testing, and seems to work well though tweaking the parameters is still a bit clumsy. Users looking for a mature particle counter should probably wait for ShapeLogic v 1.2.

Test on sample images from ImageJ

The particle counter was tested on the particle images from ImageJ:

embryos.jpg. The un-tweaked particle counter in ShapeLogic 1.1 found

particle count = 9

embryos.jpg contains 6 particles and a few shadows.

After changing the parameter setting it found

particle count = 5

which is the correct value since ShapeLogic 1.1 cannot split overlapping particles.

Direction

This is the first use of ShapeLogic in medical image processing. The next few releases should also be focused on the particle counter, making it more robust and automatic. This is the plan for ShapeLogic 1.2:

More testing and tweaking of particle counter
Make it easier to set parameters for particle counter in a macro or a configuration file
Print report about each particle's color, area, standard deviation to a file
Different implementations of particle counters
Vectorize particles by tracing the edge
Filter particles based geometric properties of the edge using the same techniques as letter matcher

Download ShapeLogic 1.1

-Sami Badawi
http://www.shapelogic.org

ShapeLogic 1.0 with stream based rules released

2008-03-07T08:56:00.006-05:00

Here are the release notes for ShapeLogic 1.0

Changes

Rule for image processing have been migrated, previously they were implemented as goal driven tasks with sub tasks. Version 1.0 uses lazy streams which are simpler and more powerful.
Letter match example now matches all polygons instead of just the first found.
When running ShapeLogic as ImageJ plugin, it is now easy for users to define rules for matching in external Java files.
New number matcher to demonstrate how to define rules for matching in an external Java file in 130 lines of code.
Enabled use of Java 6 Scripting for rule database, which gives the user access to the 25 scripting languages that are supported
ShapeLogic now has beta development status
Many unit tests added for Lazy Stream library
Fixed bugs in Lazy Stream library
Fixed bugs in vectorizer

Lazy streams features

Lazy streams can be named and defined based on other lazy streams
They work similarly to UNIX pipes or calculation Legos
They serve as your query construct, you can directly query them
A stream can be wrapped around an Iterator
A stream can be created from an input stream and a Calculation
They can be instantiated lazily, so you can load calculation networks independently

The lazy stream worked very well with the letter match. It started out as a functional construct, but with the named streams they got a more declarative feel to them.

The Calculation in the stream is using the same signature as Neal Grafter's Java 7 closure prototype. This might make integration with Java 7 easier.

User defined rules for number match

The most significant change is that it has become a lot simpler for users to define rules. Here is the start of DigitStreamVectorizer_ the number matchre in 130 lines of code. Notice that there is barely any setup code. It is almost only rules, defined in a very simple format.


public class DigitStreamVectorizer_ extends StreamVectorizer_ {

@Override
public void matchSetup(ImageProcessor ip) {
 loadDigitStream();
}

public static void loadDigitStream() {
 LoadPolygonStreams.loadStreamsRequiredForLetterMatch();
 makeDigitStream();
 String[] digits = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
LoadLetterStreams.makeLetterXOrStream(digits);
}

public static void makeDigitStream() {

 rule("0", HOLE_COUNT, "==", 1.);
 rule("0", T_JUNCTION_POINT_COUNT, "==", 0.);
 rule("0", END_POINT_COUNT, "==", 0.);
 rule("0", MULTI_LINE_COUNT, "==", 1.);
 rule("0", CURVE_ARCH_COUNT, ">", 0.);
 rule("0", HARD_CORNER_COUNT, "==", 0.);
 rule("0", SOFT_POINT_COUNT, ">", 0.);

 rule("1", HOLE_COUNT, "==", 0.);
 rule("1", T_JUNCTION_LEFT_POINT_COUNT, "==", 0.);
 rule("1", T_JUNCTION_RIGHT_POINT_COUNT, "==", 0.);
 rule("1", END_POINT_BOTTOM_POINT_COUNT, "==", 1.);
 rule("1", HORIZONTAL_LINE_COUNT, "==", 0.);
 rule("1", VERTICAL_LINE_COUNT, "==", 1.);
 rule("1", END_POINT_COUNT, "==", 2.);
 rule("1", MULTI_LINE_COUNT, "==", 0.);
 rule("1", SOFT_POINT_COUNT, "==", 0.);
 rule("1", ASPECT_RATIO, "<", 0.4);

ShapeLogic's 3 different approaches to declarative programming

Here is a chronological listing of ShapeLogic's 3 different approaches declarative logic:

Declarative goal driven logic engine. From ShapeLogic 0.2.
Logic filter language. From ShapeLogic 0.8 The syntax and development of the logic language is better described in Logic language.
Lazy streams. From ShapeLogic 0.9.

Result of different approaches so far

For the letter matching example, the lazy stream approach has been both simpler and more powerful than the goal driven logic engine.

The Artificial Intelligence choice tree is built into the logical structure of goal driven logic engine, so this approach might work well when reasoning under uncertainty.

The logic filter language is used with both lazy streams and goal driven approach.

ShapeLogic is a toolkit, all 3 approaches are available with unit tests.

For now development is focused on the lazy stream approach.

JSR 223 scripting surprise

I had put a lot of energy into making it easy to create a stream from a Scripting snippet in either Groovy, JRuby or JavaScript. This was clearly superior to text snippet rules defined using Apache Commons JEXL under the Declarative goal driven approach, but using the new Stream it turned out not to be necessary. The rules could easily be defined in plain Java. I still think that good integration with streams and Scripting from ShapeLogic might turn out to be useful.

Download ShapeLogic 1.0

-Sami Badawi
http://www.shapelogic.org

Lazy streams in mathematics and vision

2008-01-29T06:50:00.000-05:00

ShapeLogic 0.9 contains new functional and declarative constructs

Lazy streams
Simplified and expanded lazy calculations

The functional and declarative construct of ShapeLogic can be used independently of the image processing code. It only requires a 200 KB jar file to use this in other application, and there is no dependency of third party jars.

ShapeLogic 0.9 letter recognition example is still using a different system for declarative programming. More on that later in this post.

To test lazy streams in pure form I tried them on the 10 first mathematical problems in Project Euler. I think that ShapeLogic streams provided for simple solutions to the mathematical problems.
However they are more verbose that say solutions in the Scala language:
http://scala-blogs.org/2007/12/project-euler-fun-in-scala.html

Solutions to a few of the Project Euler mathematical problems

Project Euler is a list of 178, mathematical problems, that can be solved by computers.

1 Add all the natural numbers below 1000 that are multiples of 3 or 5

NaturalNumberStream naturalNumberStream = new NaturalNumberStream(1,999);
ListFilterStream<Integer> filter = new BaseListFilterStream<Integer>(naturalNumberStream) {
public boolean evaluate(Integer object) {return object % 3 == 0 || object % 5 == 0;}
};
SumAccumulator accumulator = new SumAccumulator(filter);
System.out.println(accumulator.getValue());

2 Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million

BaseListStream1<Object,Integer>fibonacci = new BaseListStream1<Object,Integer>(){
{ _list.add(1); _list.add(2);}
public Integer invoke(Object input, int index) {return get(index-2) + get(index-1);}
};
ListFilterStream<Integer> filter = new BaseListFilterStream<Integer>(fibonacci) {
public boolean evaluate(Integer object) { return object % 2 == 0; }
};
SumAccumulator accumulator = new SumAccumulator(filter) {
{_inputElement = 0;}
public boolean hasNext(){ return _inputElement <= theNumber; }
};
System.out.println(accumulator.getValue());

Comparison between streams and old declarative constructs

In ShapeLogic 0.8 a cornerstone in declarative programming was a goal driven system of tasks with sub tasks. The letter recognition example reads in a rule database and translated it into goals/tasks with sub tasks. Somewhat like the programming language Prolog.
In case of uncertainty the different choices would live in an artificial intelligence choice tree that is tied to the tree of tasks and sub tasks.

Integrating old declarative constructs with lazy streams

Based on what is needed in the current letter match example. It seems like the stream based approach is simpler and able to handle all the problem that the goal driven approach could.
I expect the stream approach to supersede the goal approach.
The rule database will be read and translated to streams. So the rule for the letter A would be translated into a filter that could filter a stream of polygons into a stream of polygons that represent the letter A.

Also currently the rules now are using JEXL to translate a text rule into something executable.
Example:
Rule for letter A: polygon.holeCount == 1.
In ShapeLogic 1.0, you should be able to use Java 6 Scripting, JSR 223, to be able to define these rules, in one of the 25 supported scripting languages. In ShapeLogic 0.9: Groovy, JRuby, and JavaScript was tested with streams, but not with the rule databases.

Using streams for concurrent programming

Streams can also support parallel or concurrent programming, which is important with the CPU intensive operations in image processing and computer vision. Especially with the advent of cheap multi processor machines.

Example: Find polygons in a stack of images

You define a lazy data stream for this and set a stream property
randomAccess = true
This indicates that individual elements can be calculated independently. The factory creating the stream could create a parallel version of the stream and assign each operation its own thread. Note that the result would be a stream of polygons for each image.

-Sami Badawi

ShapeLogic 0.9 with lazy stream library released

2008-01-23T01:02:00.000-05:00

Here are the release notes, I will soon describe the changes in more details.

This is the first release where ShapeLogic is moving beyond current parameters as a plugin library for ImageJ, currently only used in a letter recognition example. The improved system will be for declarative programming where the user can define rules in either a database or flat file. The focus will still be on image processing and computer vision, but the system will be more broadly applicable. There has been no new work on image processing or letter recognition in this release. ShapeLogic 1.0 will combine these new changes with the current image processing code.

Changes

Introduce new functional, declarative and query constructs to Java
Implement lazy streams like Haskell, Scala or Scheme
These functional constructs are very lightweight and you only need one 200KB jar file to use it in other applications
Test streams by solving the first 10 mathematical problems from Project Euler
Enabled Java 6 Scripting for evaluating expressions.
Tested with Groovy, JRuby, JavaScript, but should work with other supported Scripting languages, currently that are 25 of these. This makes it possible for users to add rule, formulas and queries in real time using text format. They can interact with a running Java application, which can be useful in science, finance or web applications.

-Sami Badawi

Lazy streams in Java, Groovy, JavaScript, JRuby

2008-01-12T20:40:00.000-05:00

This is a follow up to my last blog: Functional constructs Java 7, Groovy, Commons

I have finished coding the first part of the lazy streams for ShapeLogic. They are going to be key for the declarative programming query interface to ShapeLogic. As a proof of concept I wanted to see how easy it would be to implement a lazy stream of Fibonacci numbers. So far I have tested my framework with definitions written in:

Groovy
JavaScript
JRuby
Java

It is essential that lazy streams are are easy to define so they can be put in a flat file or a database. I was very satisfied with the concise definitions of the Fibonacci streams in the different languages:

Lazy Fibonacci stream in Groovy

new FunctionStream("fibo","def fibo_FUNCTION_ = { fibo.get(it-2) + fibo.get(it-1) };",1,1);

fibo is the name the lazy stream has in the context / name space
fibo_FUNCTION_ it is a naming convention that the function that is use to create the stream has this name
1,1 is the first part of the lazy stream

Lazy Fibonacci stream in JRuby

new FunctionStream("fibo","jruby",null,"def fibo_FUNCTION_(it) return $fibo.get(it-2) + $fibo.get(it-1) end",1,1)

Lazy Fibonacci stream in JavaScript

new FunctionStream("fibo","javascript",null,"function fibo_FUNCTION_(it) { return parseInt(fibo.get(it-2) ) + parseInt(fibo.get(it-1))};",1,1);

Scripting using JSR 223

I added a formula language for users to an enterprise Java system a few years back using Antlr and BeanShell. JSR 223 is dramatically easier to work with, but there are still some problems.

The only scripting language that works out of the box with Java 6 is JavaScript. To get others to work you have to download jsr223-engines.zip from:
https://scripting.dev.java.net/servlets/ProjectDocumentList
For each language you want to use there is a engine jar file.
E.g. jruby-engine.jar.
They have to be on your path. So does the jar file implementing the language.

JSR 223 and Maven 2 problems

JSR 223 does not work well with Maven 2. The engine jar file does not reside in the Maven repository so you have to separately install them into you local Maven repository. Here is the command to install JRuby:
~/bin/maven-2.0.8/bin/mvn install:install-file -Dfile=jruby-engine.jar -DgroupId=org.jruby -DartifactId=jruby-engine -Dversion=1.0.1 -Dpackaging=jar

Scripting languages currently under JSR 223

beanshell, browserjs, ejs, freemarker, groovy, jacl, jaskell, java, javascript, jawk, jelly, jep, jexl, jruby, jst, judo, juel, jython, ognl, pnuts, scheme, sleep, velocity, xpath, xslt.
These languages should in theory work with ShapeLogic, without any additional code.

Other implementations of lazy streams

BaseStream: That is the abstract base class with most of the lazy stream functionality
IteratorStream: Generates elements using Java Iterator
TransformerStream: Generates elements using Java interface
FunctionStream: Generates elements using JRS 223 as described above

Next step for functional constructs for ShapeLogic

Filter that is easy to define in external text using scripting
Transformer transforming one lazy stream to the next
Query interface from where a result can be retrieved

-Sami Badawi

Functional constructs Java 7, Groovy, Commons

2008-01-09T07:17:00.000-05:00

What functional constructs to use for ShapeLogic

I have started to code the lazy streams for ShapeLogic. They are going to be key for the query interface to ShapeLogic. I need some functional constructs to work with these. The top sources candidates are:

Apache Commons
Groovy
Java 7
Hand coding

None of these are a perfect fit. This post list some of the advantages and disadvantages of these.

Apache Commons functional constructs

I am currently using Apache Commons JEXL for user expressions.

Apache Commons do not use templates
Apache Commons Functor are still in the sandbox and not actively developed
The code is not uniform
You cannot make user define functions in Apache Commons JEXL

Groovy functional constructs

I need to use a scripting language, to define user functions.

Groovy contains all of Java's constructs
Groovy comes with good functional constructs
I like the Groovy syntax for using these
I cannot use these expressions directly since Groovy is not a lazy language

Java 7 functional constructs

Java 7 comes with good functional constructs.

There are a lot of interest for functional constructs in Java 7
I would rather use Java 7 than compete with it
Java 7 still seem to be pretty far away
It is not sure that closures will make it into Java 7

Thoughts on immutable constructs

I will probably make the convention that a lazy stream like the Fibonacci numbers are immutable, but not enforce this by making a LISP list.

Scala envy

Now I suffer from Scala language envy. These Scala language features would come in handy now:

Lazy streams
List comprehension, with same syntax for lists, iterators and streams
First class function
Closures
Lazy calculation
Uniform access to functions and lists

I could of cause try to include the scala.jar and directly use the Scala constructs in ShapeLogic, but there lay the road to madness.

Hand coding functional constructs

This might not be too much work, but I would rather not create yet another implementation of functional constructs. Apache Commons Functor never took off, despite some good press. That is probably an indication that Java was not that well suited for elegant functional constructs when this library was made, and maybe still isn't.

Current work plan

I will start by implementing a lazy Fibonacci stream
Then I will move the polygon finder to a lazy stream, before it could only find one polygon

I will try to get ShapeLogic 0.9 out soon, even if it is a very limited version.

If you know of any libraries that would fit my need and not be too heavyweight, please let me know.

Two Fibonacci implementations

The Haskell language has an incredibly elegant lazy stream implementation:
fibs :: [Int]
fibs = 1 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

Drools Fibonacci implemented. This is not a good fit for my computer vision project.

-Sami Badawi

Good resources about generating a Site and Documentation in Maven 2

2008-01-05T05:22:00.000-05:00

The ShapeLogic project site is generated with Maven site generation tool.

I am trying to customize the ShapeLogic site a little more. Unfortunately the documentation for using Maven site generation tool is very spotty, but Eric Redmond has made 2 great resources about this:

His online Maven 2 book:
http://propellors.net/maven/book/site-generation.html

His blog entry:
過労死 Death by Overcoding: Generating a Site and Documentation in Maven

Now the whole ShapeLogic site is generated cleanly with this command:
mvn clean site
Before you manually had to copy the directories: images and css

-Sami Badawi

ShapeLogic for general declarative programming

2008-01-02T15:21:00.000-05:00

ShapeLogic 0.9 is going to be the first release where users define rule sets read from either databases or flat files. I have decided to broaden the scope of the project.

First I hoped that I would be able to make minor adjustment to ShapeLogic's letter match example so that it would read the rules from an external source and gradually expand. But since backward compatibility is not a problem yet, I came to the conclusion that it was better to try to construct a solid foundation for declarative programming. While it will be primarily geared toward computer vision problem solving, the system will have other, broader, applications as well.

Do we need another system for declarative programming?

SQL rules supreme in the field of simple data, but once you go outside this field there are many different directions that you can take.

The declarative logic programming system that I had highest expectations for was CYC. It is a large, hand coded knowledge base trying to capture common sense, using many different inference techniques. Strangely, it never got a big following even after they released part of the engine as open source.

I hope to find a sweet spot where a simple system will be able to do some real work and be simple to learn. My work is geared toward a domain where there are a limited number of objects with somewhat constant features.

A few of the changes in ShapeLogic 0.9

Lazy data streams

Implement lazy data streams like Scala or Scheme.

Decouple annotation

Make the annotation of shapes more loosely coupled to classes in ShapeLogic. I was not super happy with the first solution that I came up with of how to annotate point, lines and polygon.
If ShapeLogic should be used for more general problem this is completely unacceptable.

Better interpreter

I order to save user defined rule in a database or a flat file, I need to be able to compile or interpret this code. This code in the rules should mainly be fairly straightforward.

The top contenders are:

Java 6 Scripting interface, that should give access to different scripting languages for the JDK

Java 6 Compiler interface, the problem is that Java is pretty verbose

Groovy intepreter

Do the parsing in ShapeLogic and write a little interpreter

Stick with JEXL for now, and make the move in a later release

-Sami Badawi

Language and tutorials for the external rule base

2007-12-26T13:12:00.000-05:00

Language

I have spent a couple of weeks thinking about how to organize the external rule database for ShapeLogic, and have done more reading about Java 6 Scripting. That should be adequate for my need, but I am reluctant to add more dependencies to ShapeLogic than absolutely necessary.

I am now debating what scripting language would be best for Java 6 Scripting:
Groovy: Comes out as maybe the strongest contender, but I tried Groovy 2 times before only to find out it was not ready for prime time yet, but maybe with version 1.5 it is finally there.
BeanShell 2: It has been in beta for over 2 years and does not seem to be in active development.
Jyton: I have been a big fan of Python for almost 10 years now, but the white space indention does not work so well with code stored in a database or flat file.
JavaScript/Rhino: I like it and people know it, but it would be better if it was a language that was using native Java types.

Tutorial

After seeing a 20 minute screen cast for Ruby on Rail by David Heinemeier Hansson, my new test for if a programming library or language is worth spending time on is if it has a 20 minute screen cast, where they can do something non-trivial. I do not adhere to this rigorously.
Given that I have a thicker Danish accent than David Hansson, I have been looking for other options.
One of my friends Joe Orr, see Joe's blog 3DTree Notebook, has created a very interesting alternative to screen casts called Screenbook Maker, it is a program that takes screen shots of a demonstration and adds text to it, to turn it into a tutorial, which is searchable.
Joe has promised me to help make a Screenbook tutorial when the external rule database is released.

-Sami Badawi

Declarative programming using Java 6 Scripting

2007-12-19T18:48:00.000-05:00

I am working on moving the declarative programming in ShapeLogic into an external rule database now.

Currently the rules in ShapeLogic are parsed from strings using Apache Commons JEXL library.
So the letter A would have a rule saying:
polygon.holeCount == 1

This is not trivial since a variable say polygon.holeCount could have different values in different contexts.
E.g. if there was a choice of 2 different thresholds levels, then in one part of the choice tree we could have
polygon.holeCount == 1 and in another we could have
polygon.holeCount == 2.

I am considering changing from JEXL to using the Java 6 Scripting instead.
JEXL has not been released for over 1 year, and it is a little awkward to handle static fields and functions.
It might also be better to let the user chose what scripting language they want to use.
Currently there languages should be available for scripting: JavaScript, BeanShell, Jython, Groovy and JRuby.

One issue is that I cannot just use variable binding in a global scripting context.
In my example from above if the variable polygon.holeCount does not exist in the top context, I will have to make sure that it is taken from the right context. This was relatively easy in JEXL since a context here mainly is just a map you store your key values pairs in, I am not sure if this is a problem when you are dealing with a whole dynamic scripting language. I am also a little concerned about performance.

I might make a release of ShapeLogic 0.9 where you just can select another rule database stored in a flat file or a database, but using the current system, in order not to drag the next release out too long. This should allow the users to define rules for matching a separate alphabet, say the Greek.
But it is far from what I want ShapeLogic to be able to do.

-Sami Badawi

Declarative and Object Oriented programming

2007-12-18T22:11:00.000-05:00

One of the main objectives for ShapeLogic is to make a good hybrid of Declarative programming and Object Oriented programming. This is not specific to computer vision, but is a general problem. This is a daunting task, and many people have tried and the state of the art still leaves a lot to be desired.

I have started to work on the first release of ShapeLogic with an external rule based engine, I have not worked through all the problems yet. I think that this is a case of evolutionary programming where you have to try out and approach, not knowing if it will lead to anything useful. Hopefully I will have ShapeLogic 0.9 ready pretty soon.

I think that the key is to keep it simple and keep the syntax easy to work with. Let me just give my 2 cents on a few project that combined Declarative programming and Object Oriented programming.

Approaches that impressed me

Prova is a Java Prolog hybrid. I was very impressed by the simplicity and how well it managed to integrate queries with normal database access. Unfortunately I do not think that Prolog is applicable to the approach to computer vision, that I am pursuing in ShapeLogic now.

List Comprehension in Python and Haskell. It is somewhat limited, but it is very convenient to work with.

Microsoft LINQ, I think that it is great that you can use the same simple syntax to query databases, XML and collections.

Hibernate and ORM tools: While I do not think that the dust has settled yet as to how feasible they are for production system with large databases. I think they are very promising. This was the reason that I included Hibernate in ShapeLogic, despite it not being used much yet.

Promising approaches that I found hard to work with

Drools: An open source RETE engine for the Java JVM. It comes with a lot of cool features, but I thought that the example program setting a rule up to calculate Fibonacci numbers was too complicated.

OWL: Works with XML / RDF. It is a standard. It comes with good open source tools, but it just seems too heavy weight for my purpose.

-Sami Badawi

Registered blog with technorati

2007-12-15T17:40:00.000-05:00

Blogging is still new to me, but I registered my blog with Technorati.
I also adjusted my terminology from Robotic Vision to Computer Vision.
In 1990 when I told people that I was writing my thesis on Computer Vision they would always say:
Oh you mean virtual reality.
That was big in the early 90ies, so I started saying Robotic Vision instead. I now realized that this term is not used much, and not applicable as a tag.

Day of Judgment was postponed

2007-12-14T11:36:00.001-05:00

Yesterday I sent out an announcement about ShapeLogic to the ImageJ mailing list, not sure if it would generate any interest at all. I was very happy to see that there were 21 downloads on the first day, so at least there was some interest.

I was considering to start working on a medical image analysis problem next. It was presented to me by a medical scientist doing Alzheimer's research. It was a very interesting problem, but it would take me at least a few months to finish it.

Since there are some interest in ShapeLogic I am now thinking that maybe it is better to first focus on ShapeLogic primary focus, to be a toolkit for declarative logic in machine vision and image processing.

When a user is trying the letter matching example the rules are stored in a Java class. There is a unit test that is writing these rules to a database first and then gets them from the database before doing the letter match, but this is not available in the user interface yet.
It would be better if the users could define a new set of rules themselves in a database or a flat file. E.g. the user could have a file that does matching for a different alphabet or other symbols.

I will probably also clean the letter match example up a little more. E.g.: The skeletonizer will create little Y junctions at the bottom point of a V, which will trick some rules.

I hope that this will get ShapeLogic to beta quality in a couple of releases, maybe around ShapeLogic v 1.0. This is probably a statement that I will live to regret, when I announce that ShapeLogic v 2.0 finally have reached beta quality in half a year.

-Sami Badawi

Day of Judgment or day of indifference?

2007-12-13T14:57:00.000-05:00

The time of hiding in shame is over. ShapeLogic is finally presentable enough, so I sent out an announcement about ShapeLogic to the ImageJ mailing list this morning.

I have not had any contact with the image processing or vision community. So I have no idea if the list readers will think it is horrible or promising or not think anything at all.

I have still not made my mind up about what to work on next: There is an idea for a medical image processing example that is interesting, but also quite involved.

The letter match could also use a little more cleanup:

Sometimes the skeletonizer will create little Y junctions at the bottom point of a V, which will trick simple rules.

I would like to get ShapeLogic to beta quality as soon as possible, I hope that this will happen in the next couple of releases.

-Sami Badawi

100 downloads of ShapeLogic

2007-12-09T21:35:00.000-05:00

I am Sami Badawi, robotic vision has been my biggest passion since 1989, but starting in August 2007 I created a Java software library for image processing and robotic vision called ShapeLogic: http://www.shapelogic.org

I have not advertised ShapeLogic since it was pre alpha quality, however, two weeks ago I released ShapeLogic v 0.7, which was the first alpha quality release. Last week I got the website up and running, then to my big surprise somebody found it, and I got over 100 downloads of ShapeLogic 0.7 last week. I am not sure how many were downloads by spiders and robots, but this was enough to create this blog and a mailing list: http://groups.google.com/group/shapelogic

I released ShapeLogic v 0.8 two days ago, which has a better syntax for the logical expressions, which were pretty convoluted in 0.7 and also completely undocumented.

I am planning to improve the documentation and clean up the web site next.
After that I would like to work on applying ShapeLogic to a medical image processing problem.

This is my first blog so I am in unknown territory.

Thanks for your interest,
-Sami Badawi