Predicting the next most probable part of speech.

I have recently been spending some of my spare time learning and about AI and machine learning , after a couple books, a bunch of tutorials and most of Andrew Ng's Coursera course. I decided enough with the theory, time for some real code.
During all my late night reading I also stumbled across some of the following. The Loebner Prize, and it's most recent winner Mitsuku, A.L.I.C.E and Cleverbot and to be honest, maybe given my naivety of the field of AI, I expected much more from the above "AI" / technology, most of these current chatbots are easily confused and honestly not very impressive.
Thankfully I also found Eric Horvitz's video of his AI personal assistant, which resonated with what I wanted to achieve with my ventures into AI.

So, with human interaction as a focus point, I started designing: "Aria" - (Artificially Intelligent Research Assistant - in reverse). Which, since most of my development experience is based in the Java Enterprise environment, will be built on a distributed enterprise scale using the amazing technologies that it offers to mention some Hadoop, Spark, Mahout, Solr, MySQL, Neo4J, Spring...

My moonshot/daydream goal is to better the interactions of people and computers, but in reality if I only learn to use, implement and enjoy all that is involved with AI and ML, I will see myself as successful.

So, for my first bit of functional machine learning...

Predicting the next most probable part of speech. One of the issues with natural language processing is that words used in different contexts end up having different meanings and synonyms. To try assist with this I figured I would train a neural network with the relevant parts of speech, and then use that to assist in understanding user submitted text.

This full code for this example is available on Github.

I used a number of Java open source libraries for this:
Encog
Neuroph 
Stanford NLP
Google Guava

I used a dataset of 29 000 English sentences that I sourced from a bunch of websites and open corpus's. I won't be sharing those as I have no clue what the state of the copyright is, so unfortunately to recreate this you'd need to source our own data.

For the neural network implementation, I tried both Neuroph and Encog. Neuroph got my attention first with their great UI to allow me to experiment with my neural network visually in the beginning, but as soon as I created my training data with ended up being about 300MB of 0's and 1's it fell over and didn't allow me to use it. I then began looking at Encog again as I had used initially when just starting to read about ML and AI

When using Neuroph in code it worked with the dataset, but then only with BackPropagation the ResilientPropagation implementation never seemed to return.
So I ended up much preferring Encog, it's resilient propagation implementation (iRPROP+) worked well and reduces the network error to about 0.018 in under 100 iterations, without me having to fine tune the settings and network architecture.

How this works, I take text data, I use the Stanford NLP library to generate a list of the parts of speech in the document. I translate their Annotation into an internal enum, and then use that to build up a training data set. I persist that to file currently, just to save some time while testing. I then train and persist the neural network and test it.

The Parts of Speech Enum:

The creation of the training data:

Train the network:

Test:

Things I learned while reading Programming Collective Intelligence.

I have been working through Programming Collective Intelligence over the last couple months. I have to say it's probably been one of the best learning experiences I have had in my years programming. Comparing to some of my previous technology stack / paradigm change experiences:
Muggle -> VB4
VB6 - > Java
 Java -> .Net
 Java -> iOS mobile / game development
This is the biggest, not so much just from the technology stack, but more purely due to the size and complexity of all things ML, AI. Not coming from a mathematical / statistical background, it's really quite a deep hole to jump into, and quite a challenge.

Not only did this book walk me through a bunch of machine learning and data analysis theory, it got me to learn Python and in translating to Java I also got introduced to a whole bunch on Java related tools and frameworks.

I created blog posts for chapters 2-8, and decided to just work through the Python for chapters 9, 10, 11 and 12, for 2 reasons;
1. Improve my Python
2. Get it done so I can move onto my new personal project, using all this ML and Python knowledge to create an cross platform application with a rich UI using either Kivy or QT.

To list some the ML / Data Analysis topics covered in PCI:

• Classifiers 
• Neural Networks
• Clustering
• Web crawlers 
• Data indexers 
• PageRank algorithm 
• Genetic Algorithms
• Simulated Annealing
• K-Nearest Neighbours
• Bayesian filtering
• Decision trees 
• Support vector machines
• Kernel Methods
• Linear Regression
• Evolving intelligence 

The Java tools, libs and frameworks investigated:

• Encog
• Neo4J
• Google Guava
• Crawler4J
• Java Tuples
• Graphstream
• SQLite
• Rome
• JSoup

Python tools, libs and resources discovered:

• Kivy
• PyCharm
• QT
• The hitchhikers guide to Python
• IPython
• MatPlotLib

Creating a price model using k-Nearest Neighbours + Genetic Algorithm

Chapter 8 of Programming Collective Intelligence (PCI) explains the usage and implementation of the k-Nearest Neighbours algorithm. (k-NN).

Simply put:
k-NN is a classification algorithm that uses (k) for the number of neighbours to determine what class an item will belong to.  To determine the neighbours to be used the algorithm uses a distance / similarity score function, in this example (Euclidian Distance).

PCI takes it a little further to help with accuracy in some scenarios. This includes the usage of a weighted average of the neighbours, as well as then using either simulated annealing or genetic algorithms to determine the best weights, building on Optimization techniques - Simulated Annealing & Genetic Algorithms

As with all the previous chapters the code is in my github repository.

So the similarity score function looked like (slightly different to the one used earlier, which was inverted to return 1 if equals):

The simulated annealing and genetic algorithm code I updated as I originally implemented them using Ints... (lesson learnt when doing anything it do with ML or AI, stick to doubles).

Then finally putting it all together my Java implementation of the PCI example

While reading up some more on k-NN I also stumbled upon the following blog posts
First one describing some of the difficulties around using k-NN.
k-Nearest Neighbors - dangerously simple

And then one giving a great overview of k-NN
A detailed introduction to k-NN algorithm

Decision Trees

I just completed working through Chapter 7 of Programming Collective Intelligence (PCI). This chapter demonstrates how, when and who you should use the decision tree construct. The method described was the CART technique.

The basic summary is: A decision tree has each branch node represent a choice between a number of alternatives, and each leaf node represents a decision or (classification). This makes decision tree another supervised machine learning algorithm useful in classifying information.

The main problem it overcome in defining a decision tree is how to identify the best split of the data points. To find this you need to go through all the sets of data, and identify which will give you the best split (gain) and start from there.
For some more technical information about this split / gain:
http://en.wikipedia.org/wiki/Information_gain_in_decision_trees

The biggest advantages I see in using a decision tree are:
It's easy it is to interpret and visualise.
Data didn't need to be normalised or something between -1 and 1.

Decision trees however cant be effectively used on large datasets with a large number of results.

As with my previous Classifiers post, I ended up using SQLite in memory db as it's such a pleasure to use. I did venture into using LambdaJ, but it actually ended up being such an ugly line of code I left it and simply did it manually. I have not looked at the Java 8 implementation of lambdas yet, I just hope it doesn't end in code like (with a whole bunch of static imports):

falseList.add(filter(not(having(on(List.class).get(col).toString(), equalTo((String) value))), asList(rows)));

So my java implementation of the PCI decision tree ended up looking like (All code in Github) :

(once again ...  about 50% more code :) ).. really beginning to enjoy Python, I do see me using that for all future AI / ML type work as a first choice.

Document Filtering - Classifiers

Chapter 6 of Programming Collective Intelligence (PCI) demonstrates how to classify documents based on their content.

I used one extra Java open source library for this chapter, and it's implementation was completely painless.

Sqlite

What a pleasure, simple maven include, and thats it's little file or memory based SQL based db in your code.

My full java implementation of some of the topics are available on my GitHub repo, but will highlight the Fisher Method (or  Fisher's discriminant analysis or LDA) if you want to get a lot more technical.

What has made PCI a good book is it's ability to summarise quite complex theoretical and mathematical concepts down to basics and code, for us lowly developers use to practically.

To Quote:

"the Fisher method calculates the probability of a category for each feature of the document, then combines the probabilities and test to see if the set of probabilities is more or less likely than a random set. This method also returns a probability for each category that can be compared to others"

Although for this particular chapter and example, I would have liked a bit more layman's information surrounding Chi-squared distribution, as you will notice in the TODO of the following code example.
During the writing of this post, I discovered the following blog:
Shape of data
Seems well worth the read, will be spending the next couple days on that before continuing with PCI, chapter 7.. Decision Trees.

Optimization techniques - Simulated Annealing & Genetic Algorithms

Chapter 5 of Programming Collective Intelligence (PCI) deals with optimisation problems.

To Quote:
"Optimisation finds the best solution to a problem by trying many different solution and scoring them to determine their quality. Optimisation is typically used in cases where there are too many possible solutions to try them all"

Before embarking on this chapter I decided that it would be best to quickly learn Python, there just seems to be a lot of Python around as soon as you start learning and reading about machine learning and data analysis, it can't actually be ignored.
(Still not sure why this is the case, but set out to get up an running with Python, in 1 weekend)

Some of the resources I used:
http://www.python.org
http://www.stavros.io/tutorials/python/
http://www.diveintopython.net/index.html
http://docs.python-guide.org/en/latest/

As a developer, learning the basics of Python really isn't very difficult,  to be honest it probably took me longer to find an development environment I was happy with, consoles and text editors just don't do it for me.

The main ones I investigated were:
Ninja IDE (Free)
Eclipse + PyDev (Free)
PyCharm ($99)

I spent quite a bit of time playing with Ninja IDE and Eclipse, but there were just little things that kept bugging me, from strange short cuts to highlighting correct code / syntax as incorrect.

10 minutes after installing PyCharm, I was sold. To be fair, I am probably not the best person to judge.
I code in IntelliJ daily and actually ended up converting all the java developers in my department to drop Eclipse and start using IntelliJ.... I also did the majority of my Objective-C work in AppCode, in other words... I am a JetBrains fanboy, happy to hand over my money for an awesome tool.

Getting back to PCI, where were a couple issues with the code in this chapter, which caused me (a person that just learnt Python) a little bit of pain, 'cause I figured the code had to be right and I was just doing something wrong, eventually I went searching and found:

PCI Errata

With that I corrected the issues in the hillclimb and genetic algorithm functions:

The java implementation for the 3 functions ended up twice as long and looking like:

And unlike my previous posts on PCI, I didn't use a whole bunch of open source libraries, only added one.
Java Tuples.

The whole Chapter 5 Optimisation solution is in my Blog Github repo, the concepts used in both the Simulated Annealing and Genetic Algorithm could easily be adapted and used again if looking for a simple example of those concepts.

Now for Chapter 6 ... Document Filtering...

Blog Categorisation using Encog, ROME, JSoup and Google Guava

Continuing with Programming Collection Intelligence  (PCI) the next exercise was using the distance scores to pigeonhole a list of blogs based on the words used within the relevant blog.

I had already found Encog as the framework for the AI / Machine learning algorithms, for this exercise I needed an RSS reader and a HTML parser.
The 2 libraries I ended up using were:
ROME
JSoup

For general other utilities and collection manipulations I used:
Google Guava

I kept the list of blogs short, included some of the software bloggers I follow, just to make testing quick, had to alter the %'s a little from the implementation in (PCI), but still got the desired result.

Blogs Used:

http://blog.guykawasaki.com/index.rdf
http://blog.outer-court.com/rss.xml
http://flagrantdisregard.com/index.php/feed/
http://gizmodo.com/index.xml
http://googleblog.blogspot.com/rss.xml
http://radar.oreilly.com/index.rdf
http://www.wired.com/rss/index.xml
http://feeds.feedburner.com/codinghorror
http://feeds.feedburner.com/joelonsoftware
http://martinfowler.com/feed.atom
http://www.briandupreez.net/feeds/posts/default

For the implementation I just went with a main class and a reader class:


Main:


The Results:


*** Cluster 1 ***
[http://www.briandupreez.net/feeds/posts/default]
*** Cluster 2 ***
[http://blog.guykawasaki.com/index.rdf]
[http://radar.oreilly.com/index.rdf]
[http://googleblog.blogspot.com/rss.xml]
[http://blog.outer-court.com/rss.xml]
[http://gizmodo.com/index.xml]
[http://flagrantdisregard.com/index.php/feed/]
[http://www.wired.com/rss/index.xml]
*** Cluster 3 ***
[http://feeds.feedburner.com/joelonsoftware]
[http://feeds.feedburner.com/codinghorror]
[http://martinfowler.com/feed.atom]

Some Java based AI Frameworks : Encog, JavaML, Weka

While working through I am working through Programming Collection Intelligence I found myself sending a lot of time translating the Python code to java, being typically impatient at my slow progress, I went searching for alternatives.

I found 3:
Encog - Heaton Research
JavaML
Weka

This is by no means an in-depth investigation, I simply downloaded what the relevant projects had available and quickly compared what was available to me to learn and implement AI related samples / applications.
 

Encog

Advantages

1. You Tube video tutorials
2. E-Books available for both Java and .Net
3. C# implementation
4. Closure wrapper
5. Seems active

Disadvantages

1. Quite large code base to wrap your head around, this is probably due to the size of the domain we are looking at, but still much more intimidating to start off with vs. the Java ML library.

JavaML

Advantages

1. Seems reasonably stable
2. Well documented source code
3. Well defined simple algorithm implementations

Disadvantages

1. Lacks the tutorial support for a AI newbie like myself

Weka

Advantages

1. E-Book Data Mining Practical Techniques

Disadvantages

1. Could not install Weka 3-7-9 dmg... kept on giving me a "is damaged and can't be opened error, so left it there, as Sweet Brown says: "Ain't nobody got time for that". 

So no surprise I went with Encog, and started on their video tutorials....
A couple hours later, first JUnit test understanding, training and testing a Hopfield neural network using the Encog libs.

Similarity Score Algorithms

As per my previous post, I am working through Programming Collection Intelligence the first couple algorithms described in this book are regarding finding a similarity score, the methods they work through are Euclidean Distance and the Pearson Correlation Coefficient. The Manhattan distance score is also mentioned but some what I could find it seems that it is just the sum of the (absolute) differences of their coordinates, instead of Math.pow 2 used in Euclidean distance.

I worked through this and wrote/found some java equivalents for future use:

Euclidean Distance:

Pearson Correlation Coefficient:

Venture into AI, Machine Learning and all those algorithms that go with it.

It's been a 4 months since my last blog entry, I took it easy for a little while as we all need to do from time to time... but before long my brain got these nagging ideas and questions:

How hard can AI and Machine learning actually be?
How does it work?
I bet people are just over complicating it..
How are they currently trying to solve it?
Is it actually that difficult?
Could it be done it differently?

So off I went search the internet, some of useful sites I came across:
http://www.ai-junkie.com
Machine-learning Stanford Video course
Genetic algorithm example

I also ended up buying 2 books on Amazon:

Firstly, from many different recommendations:
Programming Collective Intelligence

I will be "working" through this book. While reading I will be translating, implementing and blogging the algorithms defined (in Python) as well as any mentioned that I will research separately in Java. Mainly for my own understanding and for the benefit of reusing them later, and an excuse to play with Java v7.

However, since I want to practically work through that book, I needed another for some "light" reading before sleep, I found another book from an article on MIT technology review Deep Learning, a bit that caught my eye was:

For all the advances, not everyone thinks deep learning can move artificial intelligence toward something rivaling human intelligence. Some critics say deep learning and AI in general ignore too much of the brain’s biology in favor of brute-force computing.

One such critic is Jeff Hawkins, founder of Palm Computing, whose latest venture, Numenta, is developing a machine-learning system that is biologically inspired but does not use deep learning. Numenta’s system can help predict energy consumption patterns and the likelihood that a machine such as a windmill is about to fail. Hawkins, author of On Intelligence, a 2004 book on how the brain works and how it might provide a guide to building intelligent machines, says deep learning fails to account for the concept of time. Brains process streams of sensory data, he says, and human learning depends on our ability to recall sequences of patterns: when you watch a video of a cat doing something funny, it’s the motion that matters, not a series of still images like those Google used in its experiment. “Google’s attitude is: lots of data makes up for everything,” Hawkins says.

So the second book I purchased - On Intelligence
So far (only page upto page 54) 2 things have from this book have imbedded themselves in my brain:
"Complexity is a symptom of confusion, not a cause" - so so common in the software development world.
&
"AI defenders also like to point out historical instances in which the engineering solution differs radically from natures version"
...
"Some philosophers of mind have taken a shine to the metaphor of the cognitive wheel, that is, an AI solution to some problem that although entirely different from how the brain does it is just as good"

Jeff himself believes we need to look deeper into the brain for a better understanding, but could it be possible to have completely different approach to solve the "intelligence" problem?