Data Mining: Text Mining, Visualization and Social Media

Timberpost: Farecast for Stocks

Farecast (recently acquired by MIcrosoft) does just what you want when making an airplane ticket purchase: it predicts if the price is going to go up, down or stay level and advises when you should buy (now, wait). Timberpost is a small company founded by Peter Ross and Tim Taylor (Peter was a professor at Edinburgh University when I was there studying AI and Tim completed his PhD in the same department). Timberpost’s product – TRAITS – takes a crack at a real chestnut of an AI problem: predicting the stock market. The difference with this solution appears to be that it actually does a good job of it.

The graph below shows the performance of a hedge fund run (in simulation) by TRAITS compared against the FTSE EuroFund 300 Index.

A recent overview published by Timberpost says:

This portfolio is currently showing an annualised return of +23%, which would rank it 6th out of 200 peer funds according to the latest performance data on real European Long/Short Equity hedge funds published by EuroHedge magazine.

Timberpost describes their technology as follows:

Many machine learning techniques have been applied in finance, including neural nets, genetic algorithms, reinforcement methods and rule induction. We are developing a new approach that is inspired by ideas about how the human immune system functions. Like the immune system, our software can not only discover effective responses to new conditions (in our case, potential trading opportunities), it also adapts to remember past successes in order to be able to re-activate them quickly when conditions change.

In biological systems, recognition happens by molecular binding. In our software, recognition is based on elaborate mathematical expressions that describe features of the behaviour of stocks. The system is designed to be efficient; it can look at many thousands of elaborate expressions per second.

Strong AI

Wired's latest edition has an interesting article summarizing the life and vision of Ray Kurzweil. Not present in the online version of the article is a sidebar entitled 'Never mind the singularity, here's the science'. This piece, written by Mark Anderson, states:

[P]roponents of the so-called strong-AI school believe that a sufficient number of digitally simulated neurons, running at a high enough speed, can awaken into awareness.

This is an unfortunate summarization of strong-AI as it suggest that brain simulation is identical with strong-AI. While we can recognize an intuitive path to the goals of strong-AI (a self-aware intelligence machine) through the simulation of the human brain in a very literal sense, it is more appropriate to think of the brain itself as an implementational detail. What is more interesting is to capture the fundamental truths of intelligence and self-awareness abstractly and then implement them in an appropriate manner with the tools at hand. The big difference here is that this approach leads to a deeper understanding of intelligence.

Anderson does go on to make some excellent points about the disconnect between the continuous increases in the power of machines (e.g. Moore's law) and the very discontinuous nature of the study of the brain. In other words, it doesn't matter if we have the hardware at hand if we don't understand the system that we are trying to simulate.

The Wikipedia article on this topic is pretty interesting, though the origins of the term strong AI are buried at the bottom.

Be Big or Be Smart

I've written before about the differences between clever algorithms and approaches to AI which use massive data volumes as their core MO. Philipp Lenssen over at Google Blogoscoped has a great example of this supplied by Google's spell checker. Typing in 'she invented' returns the spelling suggestion 'he invented'. Other examples surface in the comments. There is a nice irony here. I used Schmidt's claim that the Google spell checker was a form of AI as an example of why Google's centrality in the public's perception of AI is a sort of tragedy.

An issue that came up in the Future of Search event (about which I'm attempting to write a longer piece) is that of correctness (the term precisiation came up...). You search for some information and get a page that makes a statement of the correct form, but is it correct? Some great examples flew about regarding claims of the origin of various electrical applications and the names of Edison and Tesla. The problem is that the majority vote may not always be correct.

AI, Language and Symbols

The fallibility of introspection as a means to understanding consciousness is well known and understood. Tempting as it may be to refer to the 'voice' inside our head - the inner monologue, or the thought process - one can never win any arguments by playing this card. While we may, at the most, use the common experience as an indication of the separation between conscious and subconscious thought, we can't claim that intelligence works thisway or that way by summarizing a thought process.

If we could do that, then we would simply declare that intelligence involves inference, self-awareness, symbolic reasoning, etc. This argument can be brushed aside by reasoning that we have no evidence that any of our inner monologue, or stream of consciousness is a prime mover - rather, it may well be a post hoc phenomenon.

However, when it comes to communicating with other agents in what we perceive to be the real world, we have created an interface that does appear to have all of these nice qualities: symbols, structure, stereotypes and so on are all used to externalize our thoughts and as an input mechanism to grasp the inner workings of our fellow beings. And while it is attractive to believe in the emergence of intelligence via huge data sets and massive but simple processing power, that intelligence will arise from the simplest machines if only we throw enough data at them - the fact of the matter is that much of what we learn as humans we do so by the consumption of structured symbols of various types.

Fernando ask

How do you know [that] the power to generalize [doesn't come from massive scale]?

Fernando's post is somewhat confusing. He argues that scientific discovery is perhaps the most celebrated example of the qualities of intelligence that I require for AI. Science is perhaps the most formal, structured, symbolic and hierarchical form of communication that society has created. Fernando's example of scientists creating machines to mine genomic data for repeated structures is, he claims, one that supports the use of scale for AI. But how did we get from the genomic data - represented as simple sequence - to the problem of finding patterns in it? That requires all the symbolic, hierarchical structured knowledge: the genetic model.

In (partial) answer to Fernando's question - clearly the parallelism of the brain is considerable, but that is not the type of scale that Larry Page is talking about (that is to say, the symbols - or units/mechanism of representation - and operations involved are quite different).

Why Google's AI Vision Is Wrong

On the way back from Boulder, I picked up Business Week. I read therein yet another story about Google which raises the bar, perhaps, for main stream coverage of Google paranoia. Here's the link to the story.

With all Google coverage of late, regardless of the author's affection or repulsion for the company, artificial intelligence (AI) is nearly always mentioned. The central theme of Google's AI is that massive scale, vast data sets and planet-sized computers will, eventually - almost naturally - result in AI.

This is a weak 'vision'. The reason it upsets me is that driving for scale of this type sidesteps the fundamental power to generalize. Human intelligence excels at establishing and exploiting generalizations. It is fundamental to language, reasoning, logic, philosophy, music, and thought itself.

Artificial intelligence as a term has for many reasons, been diluted over the last decade. While the behaviour of such an intelligence as envisioned by Larry Page may not be that much different from mine, evidence of the terms maltreatment can be found in some of the additional content. Here, when Schmidt (Google's CEO) is asked about AI, he notes:

Our spelling correction...is an example of AI.

Nice.

To be honest, when I talk about AI, I really mean: systems that exhibit human-like intelligence (which could be far more powerful in some dimension than a human, but ultimately with a capacity to reason, conjecture, plan and execute). AI, as used by Eric Schmidt, clearly means something more like: a useful tool.

Back To The Future: NLP, Search, Google and Powerset

For those following the parallel debates concerning NLP and search (NLP discussion from the technical side in parallel to the thy-shall-not-hype discussion from the Web 2.0 pundit-sphere) may be interested in this post by John Battelle from October 12th, 2004 (!). In the context of recent discussion, one hardly knows where to begin quoting:

"Named entity extraction" is a relatively new project [] which Norvig said Google had been working on for about six months. As Norvig explained the concept - essentially identifying semantically important concepts and the meaning wrapped around them[.]

This is in the context of a technology demo which Google gave around that time. Battelle continues, quoting Norvig in an eWeek story:

For example, Norvig said, researchers are looking for ways to break down sentences by looking for a phrase like "such as" and grabbing the names that follow it. The goal is to not only pull out the name but also its clusters, so that a name such as "Java" can be associated both with the computer language and with language in general, Norvig said.

"We want to be able to search and find these [entities] and the relationships between them, rather than you typing in the words specifically," Norvig said.

Battelle then goes on to speculate about how these capabilities might surface in the Google UI. The last sentence in the above quote seems so close - at least in terms of vision - with some of the current wave of NLP search debate that is provokes the question: what happened to this project? Did Google try and fail? If you read it closely, you'll see that Norvig is talking about some key NLP concepts:

• Entities (typed concepts expressed in short spans of text, generaly noun phrases)
• Ontologies (Java IS_A programming language)
• Relationships (between entities)

I mean - couldn't you build a next gen search engine on such wonderful ideas?

The Time To Build NLP Applications

Bob Carpenter makes an important contribution to the debate around NLP and search (thanks to Mark Liberman for capturing this as it unfolds). Before addressing Bob's post, I'd like to put a stake in the sand. Some of the discussion around NLP is to do with the ability of certain, one might say atomic, elements of any NLP system and the performance of those components. In terms of quality, I don't believe that we are really at the point where we need to wait to eek out another .01 % improvement. This has been the course for a while in various tasks (including POS tagging and parsing). It is interesting to see a reflection of this point of view in the ACL's attitude towards paper reviewing. I say that now is the time to take what we have and figure out how to apply it. Sure, it would be nice to get a slightly better parser or a slightly better POS tagger, but these shouldn't be fundamental barriers to creating rich applications.

Ok - so Bob's post. Bob asks what a search engine which took advantage of NLP would actually look like. He uses the example of trying to find out if Ian Anderson (famed flute player and salmon farmer) is Scottish or English. To illustrate some of the challenges here, Bob reports the results from Google via the use of the wild card '*' in Google's search syntax.

Google QUERY: ian anderson was born in *

Here’s the first few “answers”:

1. Paiseley, Scotland
2. 1947
3. Scotland in 1947
4. Fife in 1947
5. Philadelphia
6. Croydon before England won the world cup
7. Williston, ND
8. Nottingham on June 29, 1948
9. 1981
10. digg

Now which of those is the “right” answer? Well, first it depends on which Ian Anderson we’re talking about. There are 10 with their own Wikipedia pages.

The voting thing doesn’t help much here unless you happen to know that Dunfermline is in West Fife, which is in Scotland, which is in the United Kingdom. I’m confused about answer 1, because it’s “Paiseley”, which is spelled wrong. Wikipedia claims the answer is Dunfermline. Clearly the source is important in providing answers.

This is such a great example due to the ambiguity of the word 'in'. In addition, a system with a modicum of world knowledge would be off to a running start knowing that a person was being discussed (simple entity extraction would deal with this). Consequently, it would be able to report relationships between people and (birth) times and people and (birth) places. I believe that for this example, we can easily imagine the presentation of these results involving an explicit indication of the potential for ambiguity.

However, this example would better be discussed in the light of the information in the entire corpus. For example, Google reports 372k pages for 'ian anderson fife'. Discussion around being able to parse correctly has always to consider this level of redundant information  - the same facts expressed over and over in many different ways.

• Notable Fifers: ... Ian Anderson (list format)
• Born: Aug 10, 1947 in Dunfermline, Fife, Scotland (semi-structured)
• Ian Scott Anderson, born August 10, 1947 in Dunfermline, Fife, Scotland, is a Scottish singer, songwriter, guitarist and flautist, and is best known as the head of the rock band Jethro Tull.
• Ian was born in 1947 in Dunfermline, Fife, Scotland.
• Birthplace: Dunfermline, Fife,  Scotland (semi-structured)
• ...and so on, 372, 000 times.

Note here, BTW, that there is some number of expressions of this information in a semi-structured form. While parsing sentences is a key area of NLP research, there are many ways in which the relationships between things and ideas may be expressed and tabular and list-like formats are potentially more accessible than sentential forms (it is this observation that drives much of the technology behind Google's simple onebox answers - see this post for a description, or amuse yourself by asking Google 'what is the density of France?').

While I haven't really addressed Bob's question, I believe I am proposing that a more sophisticated search engine would be explicit about ambiguity (rather than let the user and documents figure this out for themselves) and would take information from many sources to resolve ambiguity, recognize ambiguity and synthesize results.

NLP and Search: Free Your Mind

I've been playing ping-pong with Fernando over the potential and value of NLP in search. I've yet to respond to Fernando's latest post (which I hope to do RSN). However, I'd like to point to something in this recent interview with Peter Norvig, Google's Director of Research. In an interview with VentureBeat, which was prompted by a news cycle from Powerset, though not directly concerning the company, Norvig states:

It would be great if we understood every word of every document and every query, but that’s a long way off.

To me, this kind of statement illustrates a crucial issue in the NLP debate. Norvig quite rightly talks about evaluating technologies from a user needs and quality perspective. This quote indicates a very traditional search point of view: a query is entered and a set of documents is returned. If one thinks outside those extreme constraints, and instead views the information found online independently of the documents that capture that information in human language, the huge redundancy in those documents suggests approaches to serving the user that don't require the perfect analysis of every document.

One of the basic paradigms of text mining, and a simple though constraining architectural paradigm, is the one document at a time pipeline. A document comes in, the machinery turns, and results pop out. However, this is limiting. It fails to leverage redundancy - the great antidote to the illusion that perfection  is required at every step. The key to cracking the problem open is the ability to measure, or estimate, the confidence in the results. With this in mind, given 10 different ways in which the same information is presented, one should simply pick the results which are associated with the most confident outcome - and possibly fix the other results in that light. Another, related approach, is to be able to measure the difficulty associated with a particular interpretation. This is an approach that is very pertinent to social media, or blog data. While there is plenty of reasonably well formed language in blogs, there is also a huge volume of noisy text, with little or no traditional grammatical quality, dysfluencies, etc. What a system does, or attempts to do, with this data could be different from what is attempted with the more formal language.

And as for the issue of 'understanding every query' this is where the issue of what Barney calls a grunting pidgin language comes in. For example, I saw recently someone landing on this blog via the query - to Google - 'youtube data mining'. As the Google results page suggested, this cannot be 'understood' in the same way that a query like 'data mining over youtube data' can. Does the user want to find out about data mining over YouTube data, or a video on YouTube about data mining?

One thing is clear about the current debate - the issue is gaining visibility and there will be pressure for various parties to force particular points of view or interpretations of the capability of these technologies. This PR move may well become disassociated with what is really going on, and the real debate about the liberating potential of freeing users from existing behaviours and expectations - which is, of course, the hardest part of any fundamental change.

Since writing the above, I see that Fernando has another post up. In this he argues that while relevance wrt some keyword query is in some sense a natural - or observable - function (it makes sense because it deals with constructs that we can observe, namely the query and the documents), this is not the case for NLP type analysis in which the result is an artificial construct (a parse tree or a relational assertion for example). I don't disagree with the basis of this argument.

The situation is different for keyword-based search, because the input-output function is in a sense trivial: return all the documents containing query terms. The only, very important, subtlety is the order in which to return documents, so that those most relevant are returned first. Relevance judgments are relatively easy to elicit in bulk, compared with trying to figure out whether an entity or relation is an appropriate answer to a natural language question across a wide range of domains.

It is the notion of relevancy against keywords which is problematic, however. As in the example I illustrated, one can't determine the intention of the user simply from the keywords, thus while there may be a gradation to the relevance of some set of documents, there are also wholly separate collections of results which are not all relevant in the same way. To change this perspective, one needs to get the combination of the user and the system to deal with accurately capturing the intention of the user - which is where Barney's 'books for children' and 'books by children' example comes in (or my 'youtube data mining' example).

Powerset In PARC Deal

VentureBeat (once a critic of Powerset, now more of a believer) covers the story. In summary, Powerset's technology is not some rushed together start-up demo, but the result of many man years of research and development at PARC.

VentureBeat's post contains an interview around the topic of NLP with Google's Peter Norvig. While Norvig gives some insight into the work on NLP at Google, he doesn't mention one of their main areas of focus: machine translation (MT). It is interesting to learn of his caution in the area of NLP for search while they are tasking a number of scientist at MT, possibly the hardest AI problem known to man.

Update: It took this to have John Battelle blog about the story...

Google Book Search and How To Really Blog

In my previous post Google Book Search and Geographic Entity Extraction I fell, regrettably, into a blogger hackerism. Having been aware via my feed reading of the post that I cited, and having been reminded of it by a friend via email, I thought I should post something about it. What I should have been doing was looking at the feature, discussing the potential technology behind it and giving some thought to how well the feature works. Hopefully, this post will remedy these oversights.

Firstly, a little about entity extraction. The simplest type of entity extraction ought really to be termed entity recognition. This is the task of identifying spans of text that the author has used to identify a real world entity of a particular type. For example, in the following, from Around The World In 80 Days, we can easily identify the span denoting a location.

Mr. Phileas Fogg lived, in 1872, at No. 7, Saville Row, Burlington Gardens, the house in which Sheridan died in 1814.

The next part of the problem is to provide a logical reduction of this span of text. Clearly, even with the above - the first location in this particular novel - this is challenging for we don't know which town/city or country this address is located in. This is where all the clever bits of work come in. The next paragraph, for example, starts

Certainly an Englishman, it was more doubtful whether Phileas Fogg was a Londoner.

We might, then, guess that the address was in London. This example introduces another problem: Does one capture the term 'Londoner' and recognize the location. Ultimately, as in the application being discussed, locate it on the map?

The Google Book Search system lists 10 location in its analysis of Jules Verne's classic. The map, shown below, shows many more.

However, it doesn't show No. 7, Saville Row, Burlington Gardens [London].

So then the question is: what is the precision and recall. Without really knowing the answer to this, we must question the general impression given by the visualization of the collection of locations discovered in a book. I'm not familiar with the book, but there appears to be a bit of a hop between Cairo and India - a recall issue perhaps?