The Common Ground Algorithm - A Possible Remedy for Filter Bubbles

People have a tendency towards Confirmation Bias, whereby they seek out things that confirm their existing opinions and avoid things that challenge them. On social networks and recommendation systems, this can lead to the development of a filter bubble, whereby their sources of information come to be structured around what they already believe. This, of course, acts as an obstacle to healthy discussion between people of differing opinions, and causes their positions to become ever more deeply entrenched and polarised. Instead of seeing those with whom they differ as being decent people who have something of value to offer them, and who may be persuadable on some of their differences, people start seeing their opponents as the enemy. To prevent this, people need something that will put them in touch with people with whom they have generally opposing viewpoints. Of course, we can't just confront people with contrary opinions - this will risk provoking hostile reactions. What we need is to show people what they have in common with those whose opinions are different, so that they can build trust and begin to interact in a healthy way. As an attempt to do this, I present The Common Ground Algorithm. This uses a combination of topic modelling and sentiment analysis to characterise a user's opinions. It then finds people whose opinions are generally opposed to theirs, and identifies the topics on which they share common ground, recommending posts where they agree on something with people they disagree with in general. I've coded up a reference implementation in Python, and am releasing it under the MIT Licence to encourage its use and further development.

Integrating Java with Python the Easy Way

I have an idea for something I want to build, which will involve a speech recognition component, written in Java and a Hidden Markov Model, written in Python. So that means I have to integrate components written in two different languages. What's the best way of doing it? One way would be to run Python on the JVM. There is a Python implementation for the JVM, Jython, but from what I've heard it's painfully slow. Since I'm aiming for something as close to real time as possible, it's unlikley to meet my needs. It did occur to me that there could be a faster way to run Python on the JVM. Pypy is a self-hosting, JIT-compliled implementation of Python, which is much faster than the reference implementation. If its code generation phase were modified to emit Java Bytecode, then Pypy could run on the JVM. This approach, which I call Jypy, would be a worthwhile project for somebody who knows Java Bytecode. Unfortunately, I'm not that person. However, I then thought about the architecture of my project. I'd already realised that it would have to be organised as a number of concurrent processes, communicating via pipes. I then realised that meant that I didn't need to run Python on the JVM at all. The Java and Python components could each run in their own processes, and didn't need to share any resources. The only integration I needed was pipes. You know the sense of delight when you realise that something complicated is actually simple? That's how I felt when I worked that out.

The Bootstrap Problem

A post on Data Community DC discusses Why You Should Not Build a Recommendation Engine. The main point is that recommendation engines need a lot of data to work properly, and you're unlikely to have that when you start out.

I know the feeling. In a previous job I created a recommendation engine for a business communication system. It used tags on the content and user behaviour to infer the topics that the user was most likely to be interested in, and recommend content accordingly. Unfortunately, my testbed was my employer's own instance of the product, and the company was a start-up that was too small to need its own product. I never really got a handle on how well it worked.

This brings me to Emily. Emily isn't a product. It's a personal portfolio project. I had an idea for a recommendation system that would infer users' interests from content they posted in blogs, and recommend similar content. The problem is, the content it recommends comes from the other users, so at its current early stage of operation, it doesn't have much to recommend. The more people use it, the better it will become, but what's the incentive to be an early adopter?

What I seem to have at the moment is a recommendation engine that needs somebody to recommend it.

Emily Has Moved

As those of you who've tried out my semantic recommendation system, Emily, will have noticed, it didn't work. The reason was, I'd used the wrong cloud platform. Google App Engine isn't meant for anything that needs as much computation as Emily does, so I've ported Emily to OpenShift. This has the advantage that it gives me much more control of how I write the code, and I can use things like MongoDB and multiprocessing. Let's try this again!

Developing Emily - Revision 24: Porting to OpenShift. AppEngine wasn't suitable for the computationally intense

Changed Paths:
    Modify    /trunk/Emily.py
    Modify    /trunk/EmilyBlogModel.py
    Modify    /trunk/EmilyTreeNode.py
    Modify    /trunk/emily.js

Porting to OpenShift. AppEngine wasn't suitable for the computationally intense parts of Emily.

from Subversion commits to project emily-found-a-thing on Google Code http://ift.tt/1G9GWoV
via IFTTT

Introducing Emily - my latest Fantastical Device

Emily is a semantic recommendation system for blogs that I've been working on. If you give it an Atom or RSS feed from a blog, it will create a feed of items from other blogs that hopefully match your interests.

It does this by using significant associations between words to infer your interests. Suppose a randomly-chosen sentence from your blog has a probability P(A) of containing word A, and a probability P(B) of containing word B. If there were no relationship between the words, we would expect the probability of a sentence containing both words to be P(AB)=P(A)P(B). If there is significant information contained in the relationship between the words, they will cooccur more frequently than this, and we can quantify this with an entropy, H=log2 P(AB) - log2 P(A) - log2 P(B)

Emily uses the strengths of these associations to calculate the similarity between two blogs. Then, if you post an article that makes your blog more similar to somebody else's blog than it was before, that article is recommended to them.

This has been an interesting project for me. I've learned about Google App Engine, pubsubhubbub and Atom. What I need now is for people to try it out. I'm looking forward to when Emily starts finding things for me.

Developing Emily - Revision 23: Ready to launch

Changed Paths:
    Modify    /trunk/Emily.py
    Modify    /trunk/EmilyBlogModel.py
    Modify    /trunk/EmilyTreeNode.py
    Add    /trunk/emily.js

Ready to launch

from Subversion commits to project emily-found-a-thing on Google Code http://ift.tt/1IN7SNv
via IFTTT

Experimenting with IFTTT

I've just started trying out IFTTT. Partly this is because the Feedburner feed for this blog has needed manually prompting to update my Twitter feed, but also because I'm investigating using it to post automatically to Blogger on behalf of my friends at Speculative Grammarian.

To do this, I'm using a feed from one of my Google Code projects. It's a semantic recommendation system I've been working on. I call it Emily, because it finds things (or at least, it will do when it's up and running). Code updates from the project should be appearing here.

One of my Fantastical Devices is on PyPI

I've mentioned in previous posts that I've been working on a Python library for Hidden Markov Models. I've been encouraged to put this up on the Python Package Index, so, after a little while getting the hang of registering and uploading a project here it is. It's alpha, or course, so there are probably plenty of bugs to be found in it, but if you want to play with something I've made, all you have to do is type

sudo pip install Markov

, and try it out. If you feel you can help me improve it, contact me and I can add you to the Google Code project.

A Couple of my Fantastical Devices

with the recent news about the Voynich Manuscript, as mentioned in my last post, I thought it opportune to share a couple of pieces of code I'd written. First off, as I mentioned earlier, a couple of years ago I wrote a Python implementation of Montemurro and Zanette's algorithm for calculating the entropy of words in documents. If you're interested in using the technique yourself, you may want to have a look. Secondly, my own attempts to uncover the syntax use a Python library for Hidden Markov Models that I created. It probably still has a few bugs in it, but it's attracted a bit of interest online, and I'm hoping to develop it further. So, if you're at all interested in AI, computational linguistics, or analytics, please have a look at these. Feedback is welcome, as is anybody who wishes to contribute further to these projects.

Exciting Voynich Manuscript News

A couple of years ago, I came across a new technique for analysing documents, developed by Marcello Montemurro and Damian Zanette.  It identifies the most significant words in a document by the entropy of their distribution in the text. I tried it out on subtitles at the BBC, and got promissing early results.

Now Dr Montemurro has applied the technique to the infamous Voynich Manuscript, and discovered that it appears to contain a meaningful language, rather than gibberish. No news yet as to what any of it might mean, but hopefully my own efforts to uncover the syntax with a Hidden Markov Model might eventually bear fruit. I'm convinced it's a conlang.

The Voynich Manuscript

As you may have noticed, I haven't been posting for a while. I changed jobs, and while I'm enjoying my new job, I'm working longer hours so I haven't had as much time for things like blogging. I also did Peter Norvig and Sebastian Thrun's online AI course and as you can see here, I did pretty well. Doing the course gave me some ideas. For a while, I've been interested in the Voynich Manuscript, an enigmatic document dating from some time in the 15th century. It's written in an otherwise unknown script, in a language that nobody has been able to identify. Judging by the illustrations, it seems to cover such subjects as alchemy, astrology and herbalism. I personally suspect that it may be written in a conlang, which, if correct, would make it one of the earliest known. I think that by using Artificial Intelligence techniques I might be able to have a go at cracking it. In particular, I'm planning to use a combination of clustering and Hidden Markov Models to try to work out the syntax of the language. In the process I'm working on a Python library for Hidden Markov Models, which I hope other people might find useful.

Quantum Thinking and Function Words

Two articles in New Scientist caught my eye this week - one about a quantum mechanics like system of logic and the other about function words. According to the first article, many of our thought processes don't follow the rules of classical logic, but a system of inference that can be described in terms of Hilbert Space, which is a vector space with an arbitrary number of dimensions. Quantum mechanics uses Hilbert spaces to describe the states of quantum systems, and the mathematics of Hilbert space allows quantum states to interact in counter-intuitive ways. The same logic apparently allows human minds to combine ideas in ways that don't necessarily follow the rules of classical logic, but do allow greater flexibility. To quote from the article -

If you want to research a topic such as the "story of rock" with geophysics and rock formation in mind, you don't want a search engine to give you millions of pages on rock music. One approach would be to include "-songs" in your search terms in order to remove any pages that mention "songs". This is called negation and is based on classical logic. While it would be an improvement, you would still find lots of pages about rock music that just don't happen to mention the word songs. Widdows has found that a negation based on quantum logic works much better. Interpreting "not" in the quantum sense means taking "songs" as an arrow in a multidimensional Hilbert space called semantic space, where words with the same meaning are grouped together. Negation means removing from the search pages that shares any component in common with this vector, which would include pages with words like music, guitar, Hendrix and so on. As a result, the search becomes much more specific to what the user wants.

Obviously, if you're interested in Artificial Intelligence, where a key aim is to enable computers to emulate the flexibility of human thought, this is a useful approach. The second article, by James W. Pennebacker, concerns his work on the importance of function words. These are things like pronouns, conjunctions and prepositions, the words that don't seem to mean very much, but act like glue holding the sentence together. Professor Pennebaker has discovered that there's a lot of psychological information hidden in these apparently insignificant words - for example, in a conversation between two people, the more socially dominant one will tend to use the word "I" less than the other one. Most natural language processing software treats words like this as stop words and ignores them, but for some applications (eg sentiment analysis, social network analytics) it could be just the data you need.

Robots invent a language

IEEE Spectrum describes an interesting experiment in artificial intelligence and linguistics. Two robots, equipped with microphones and loudspeakers to talk to each other, managed to create a set of words useful for navigating their environment.

I think it would be interesting to extend this experiment to see if it could give insight into how language evolves. Starting with a larger population of robots, you could give them time to make up a language, and then start deleting the memories of individual robots at intervals. In real life, languages have to be continually relearned by sucessive generations of speakers, and this is probably part of the reason why the undergo changes. It would be possible to vary the size of the population and the rate of deletions to see what influence these might have, and also to add varying amounts of background noise.

Mind you, to give a real insight into the development of human language, you might want to give the robots more complex tasks to do than simply finding their way around, so that they would have to invent a grammar to express their meaning. Then you would be seeing how language might develop in a mind fundamentally unlike a humans. There's been considerable debate amongst linguists about how many of the constraints on human languages are hard-wired into the human brain, and how many are simply a result of circumstance, and what can evolve from what already exists.

Not as easy as it sounds

A while ago, I came up with the idea of a spoken language recogniser. The idea was that it would use a stripped down speech recognition engine to identify the phonemes in an utterance, and then feed these into an AI system which could identify which of a given set of languages a particular sequence was most likely to come from. You may have noticed that I've been a bit quiet about this recently. I've run into a few snags.

The first is that a speech recogniser needs to be trained to recognise all the different sounds it has to identify. I can't just use an off-the-shelf model for this, as there aren't any that are designed for multi-language use. As far as I can tell, nobody else has needed a multi-language speech recognition app before. So, I'll have to build my own model. Fortunately this site has recordings of many sounds from many different languages, and so gives me a good starting point for building a phonetic model.

The second problem is with transcribing all these sounds. The speech recognition engine I'm likely to use, CMU Sphinx, seems to want phonetic transcriptions to be case insensitive and alphanumeric. I'd prefer to use an X-SAMPA derivative called CXS, but the constraints the speech recogniser places on me won't allow that. Fortunately, sounds within a transcription can be separated by spaces, allowing for multicharacter notation, but with the sheer number of sounds the system has to recognise, I'll probably end up with something like htwvitbveuotkvwvahfi, a logical but unusable system I created as a parody of spelling reform proposals.

Musical moods

Some colleagues of mine are running an experiment to find out what you can deduce about a television programme from its signature tune. The experiment is described in more detail in the BBC R&D Blog.

I had a go myself earlier - you have to listen to a number of theme tunes and then answer questions about each one. The questions change from tune to tune - quite a clever piece of experimental design, in that it prevents you from getting into a rut where you're calculating your answers before the music's finished. Hopefully, it will enable my colleagues to train an AI to recognise genre and mood from theme music.

PS - sorry for the lack of posts recently.

A Fantastical Device for Identifying languages

If I were to say to you,

hajimemashite. buriikurii piitaa desu. douzo yoroshiku

you probably wouldn't understand what I meant. However, you would know that I wasn't speaking English (it's Japanese, as a matter of fact). Were I to say, however

'Twas brillig, and the slithy toves
Did gyre and gimbal in the wabe.
All mimsy were the borogoves,
And the mome raths outgrabe.

you would be able to recognise what I said as English, even though it doesn't make sense. Each language has its own phonotactics, the rules determining how sounds can be combined to make words. Therefore, you can identify a language by its sound even if you can't understand it.

I've seen a lot of language identification software on the web, but it all works from written text. We conlangers, or course, like to game the system by putting in our conlangs and seeing what happens. I thought it would be fun to try building a system that could identify languages from speech. So, I've started off a project on Google code to try my ideas out. The idea is to use a stripped-down speech recognition engine to extract a stream of phonemes from audio, and then feed those phonemes into an AI system that has been trained to recognise the phonotactics of various languages.

AI is No Longer a Dirty Word

I recently did a search for Artificial Intelligence London, and then looked at the results on a map. By doing so, I discovered a company called Cognitive Match. They're a start-up whose product aims to customise a client's website to match a user's needs on the fly. What particularly caught my attention was the following quote

Our software combines mathematics with psychology and artificial intelligence to give your customers what they want.

It's very unusual to see anyone outside the games industry use the term Artificial Intelligence for something they're actually selling. The reasons for this are largely historical. A few years ago, a lot of people made rather overhyped claims for what AI would be able to do, which didn't match up with what it could actually do at the time. This created the impression that anything that was described as Artificial Intelligence belonged in the lab, and wasn't likely to turn into a usable product in the forseeable future.

There's a gradual change in the perception of AI going on. This is partly because researchers have been taking a more pragmatic approach to AI, and partly because the internet is making large datasets more readily available. Good data is the limiting factor in most AI applications, so, the more data is available, the better AI works.

How do you identify what a word means?

Seen on del.icio.us



Artificial Intelligence has been described as "Trying to get a computer to do anything that it's easier for a human to do." Trying to disambiguate the various possible senses of a word is a classic example of this - having heard a lecture from somebody who works in this field, I know that it's very difficult to create an algorithm that improves on the naive approach of just picking the most common meaning every time. 92% accuracy looks pretty impressive.