Pasky’s Log

I’m still working on YodaQA and there is quite some interest in it in my mailbox. One thing leads to another and our startup Ailao already has a few first customers, we work together on various related semantic NLP / search projects.

In YodaQA, we have a much neater web interface as well as a mobile app as the natural way to interact with a QA system is using your voice. Plus, on a limited domain (movies), we are getting pretty close to crossing the 80% mark for accuracy on simpler questions, entering the “magic zone” where people might start really trusting the system. A few essential blocks for that are still in the pipeline, though.

I’ll try to post a bit more about YodaQA and other work we are doing in the coming weeks / months (as well as some of my hobby projects, of course).

For a course of Jan Šedivý, I prepared a presentation on building apps around the semantic web and linked data. See it here for an intro to the tech, it also includes two silly web mashups that might be inspiring.

I was working on Question Answering last year. Guess what, I’m still on it!

I threw away my first prototype BlanQA and started building a second system, YodaQA. It currently has reasonable performance of answering about a third of trivia questions properly and listing the correct answer in top five candidates for half of the questions – without doing any googling or binging.

A few weeks ago, I published the first paper on YodaQA. With a few fellow scientists, we also re-started the qa-oss Google Group on open source question answering systems.

Today, I finally made a proper homepage for YodaQA and launched a live demo of the system. It’s pretty primitive, but hopefully will serve as a proof of concept.

So what’s the strongest program you can make with minimum effort and code size while keeping maximum clarity? Chess programers were exploring this for long time, e.g. with Sunfish, and that inspired me to try out something similar in Go over a few evening recently:

https://github.com/pasky/michi

Unfortunately, Chess rules are perhaps more complicated for humans, but much easier to play for computers! So the code is longer and more complicated than Sunfish, but hopefully it is still possible to understand it for a Computer Go newbie over a few hours. I will welcome any feedback and/or pull requests.

Contrary to other minimalistic UCT Go players, I wanted to create a program that actually plays reasonably. It can beat many beginners and on 15×15 fares about even with GNUGo; even on 19×19, it can win about 20% of its games with GNUGo on a beefier machine. Based on my observations, the limiting factor is time – Python is sloooow and a faster language with the exact same algorithm should be able to speed this up at least 5x, which should mean at least two ranks level-up. I attempt to leave the code also as my legacy, not sure if I’ll ever get back to Pachi – these parts of a Computer Go program I consider most essential. The biggest code omission wrt. strength is probably lack of 2-liberty semeai reading and more sophisticated self-atari detection.

P.S.: 6k KGS estimate has been based on playtesting against GNUGo over 40-60 games – winrate is about 50% with 4000 playouts/move. Best I can do… But you can connect the program itself to KGS too:

http://www.gokgs.com/gameArchives.jsp?user=michibot

In part of my research, I have been heavily involved with building portfolios of optimization algorithms. Optimization algorithms stay at the root of many computational tasks, from designing laser mirror systems to neural network training. We want to find a minimum (or maximum) of some mathematical function, and for some functions it’s easier than for others.

For very many fairly hairy functions, the best state-of-art optimization algorithm is based on genetic algorithms and it’s called CMA-ES. It also has a very nice Python implementation by its original author, Nikolaus Hansen.

CMA-ES is still not as good as it could be on some functions with many local optima, but its performance can be much improved by establishing a restart strategy that will repeatedly restart it with varying population size and parameters. The best performing restart strategy is BIPOP-CMA-ES and unfortunately, it had no Python implementation so far. I took care of that more than a month ago, but since it’s taking some time to get my modifications upstreamed, if anyone would find that useful,

here is a patch for CMA-1.1.02 adding BIPOP restart strategy

A few hours ago, I have read about Spritz, a new speed-reading app, and I was quite impressed by the idea. I know the underlying concept is not new and I didn’t even try out Spritz itself (they announce their idea but not release the software, huh?), but this was the first time I have heard about it and I really liked it!

So I decided to implement my own terminal version of this idea, acting as a regular command-line filter. Find the new tool speedread at:

https://github.com/pasky/speedread

(Yes, it may not work well for beletry. Or slides. Yes, it may not work well for emails that you want to just skim for keywords. But then there’s the other 80% of text I need to chew through that does not fall in either category. I’ll have to continue trying it out for longer but it might be really useful.)

Meanwhile, I have also learned about OpenSpritz, a web-based implementation of Spritz. Can be a good match for speedread!

I have recently been dabbling in Natural Language Processing, in particular Question Answering. I have been fascinated by the success of IBM Watson and have gradually came to believe that this technology can serve as a great basis of autonomous agents operating in the complex world of human knowledge. (I later came across Project Aristo – I’m not alone.) This approach, compared to projects like OpenCog that aim to create autonomous agents understanding and operating in the physical world, seems to offer many advantages – but let’s talk about that some other time.

Let’s say we wanted to take a stab on approximating IBM Watson with easily available technology, in “at home” conditions (or rather, “at hackerspace” – I gave this aim a temporary callsign “Project Brmson”). What’s the best we can do?

So I took a look at the current open source question-answering technologies and found – well, just one, and none that would be immediately usable by anyone. I have put together a short survey of the current landscape.

The only OSS framework I found that (i) could be used with not-so-many modifications to produce something functional, and (ii) would be a good base to build a truly good system on, is OAQA / OpenQA. It seems appealing from multiple viewpoints – it builds on the UIMA unstructured data processing platform which is also at the basis of IBM Watson, it originates at CMU which collaborated with IBM in this area; and, well, it’s the only platform that already exists anyway, so it’s a good starting point for someone who has no prior clue about the field. A honorable mention goes to OpenEphyra, basically a non-UIMA OAQA predecessor by the same institution; it’s not a good base to use for new systems, but can be sourced for a lot of NLP functionality.

In my first stab, I looked if there is actually a working QA system built on top of OAQA, and the answer was non-obvious. There is a helloqa project, but its master branch can currently do nothing useful. However, there is also a prototype branch that can actually answer some terrorism-related questions! It doesn’t work out of the box, but our fork does if you follow the instructions. But overally the project seems to be a bit of a hack and not a good base for a universal system usable by anyone but the original author.

So I set out to rewrite the helloqa-prototype from scratch on top of OAQA and build a different, clean and extendable QA pipeline (that shares bits of the original code and is much simpler). Thus, behold the project BlanQA! :-)

BlanQA is focused on universality, practicality and user-friendliness. That means there is a relatively detailed documentation and easy to follow installation instructions (try BlanQA out yourself!). By default, BlanQA offers interactive mode and will answer on top of Project Gutenberg corpus; but you can also connect it to IRC (#brmson @ freenode) or run on top of Wikipedia.

BlanQA is still a very stupid program at this point. It gets the answer right about 10-30% of the time, depending on how nicely you ask. But it’s more important as a base on top of which you can add clever algorithms (the smartest parts of BlanQA are currently outsourced from the OpenEphyra project, mainly guessing the type of the answer – is it a person? location? amount of something?). And if you want an OSS question-answering engine now, BlanQA is where to turn!

I want to develop this further, but the way ahead remains a little unclear. The thing is, OAQA appears to have significant architectural problems, as I realized while I continued hacking BlanQA and learning more about both OAQA and the UIMA framework it builds on top of. The rest of this section is a bit technical, c.f. also a quick intro to BlanQA architecture.

The basic UIMA principle is that each artifact (in this case: question, document/passage, answer) should have its own CAS (“piece of data” with a set of annotations and other featuresets derived from it) with a dedicated type system and appropriate Sofa (view of this piece of data). This would enable easy creation of stand-off annotations of e.g. fetched documents.

However, the OAQA model works with just a single CAS that has just the question text set as a Sofa and then a variety of types mashed together, partitioned only into phase-based views. This seems to me as a substantially less appealing option – it doesn’t allow to use third-party UIMA annotators that expect their subject to be the Sofa, it might be harmful for scaleout and it seems generally awkward to use; I actually have hard time seeing what advantages does using UIMA bring on the table in this model.

So it seems the way forward for BlanQA (or likely a differently-named successor) is to break away of OAQA and build directly on top of UIMA (possibly with a hacked version of uima-ecd that supports multiple CAS, but that seems as a bit intimidating proposition).

Tue Jan 28 2014 update: Note that we have started work on a new Question Answering engine YodaQA built on UIMA from scratch.

At our hackerspace brmlab, one of the things we do is picking up landed weather sondes. In short, fun hardware literally falling off the sky, several times a day, every day. These are stratospheric balloons used for weather data prediction, launched from various sites, that reach the 35km altitude, then the balloon bursts and it lands back on the ground at a random location. At the whole time, it transmits its current GPS coordinates via radio, making this a rather exciting sub-class of geocaching.

As a simple hack today (idea by chido), I created a simple script sonde.sh that is designed to be run three times a day, runs sonde trajectory prediction (a predict.habhub.org service – example) and if the sonde is predicted to land in a certain radius, reports that with a link to the prediction. By default, it is connected to jendabot, one of our brmlab IRC robotic minions, written in an appealingly crazy way as a collection of bash scripts.

One commercial project I was working on for Raspberry Pi involved playing various MP3 samples when a button is pushed. The original implementation used mplayer to play back the samples, however the issue is that there was up to 1500ms latency between mplayer was executed and start of playback.

I didn’t do detailed profiling, but I think two factors causing high latency of mplayer were that (i) just loading all the .so libraries mplayer depends on can take many hundreds of milliseconds (ii) the file is being scanned for whatever stuff, streams detected etc. and that can also take some extra time; perhaps I could force mplayer to realize this is a simple MP3 file, but (i) is still the much bigger factor.

I wanted to avoid recoding all the samples to wav. That would allow me to use aplay directly and the playback starts immediately, but it would also feel really silly; decoding of MP3 is not the bottleneck, just the latency of mammoth software loading and initializing itself is. I also didn’t try mpd as that might have been a bit painful to set up.

Another point worth noting is that I didn’t use the crappy on-board PWM audio but a $3 chinese USB soundcard (which is still much better than PWM audio). And using reasonably up-to-date Raspbian Wheezy. So I tried…

• mplayer -slave -idle, started in parallel with my program and receiving commands via FIFO. It hangs after the first file (even though it works fine when ran without -slave).
• cmus running in parallel with my program, controlled by cmus-remote. Convincing it to use ALSA device of my choice was really hard, but eventually I managed, only to hear my files sped up about 20x.
• madplay I couldn’t convince about using a non-default ALSA device at all.
• mpg123 started immediately and could play back the MP3 files on a non-default ALSA device. Somehow, the quality was very low though (telephone grade) and there was an intense high-pitched clip at the end of the playback.
• mpg321 I couldn’t convince to produce any sound and anyway it had about 800ms latency before playback started, probably due to its libao dependency.
• sox, or rather AUDIODEV=hw:1 play worked! (After installing a package with MP3 support for sox.) No latency, normal quality, no clips, no hangs. Whew.

Verdict: There still is a software on Linux that can properly and quickly play MP3 files on Raspberry Pi, though it was a challenge to find it. I didn’t think of sox at first and I was almost giving up hope. BTW, normally you would use sox and play for applying a variety of audio transformations and effects in a batch/pipeline fashion and it can do a lot of awesome magic.

For about 13 years now, I’m running the Muaddib IRC bot that serves a range of Czech channels. Its features varied historically, but the main one is providing conversational AI services (it learns from people talking to him and replies back based on the learnt stuff). It runs the Megahal Markov chain algorithm, using the Hailo implementation right now.

Sometimes, I need to reset its brain. Most commonly when the server happens to hit a disk full situation, something no Megahal implementation seems to be able to deal with gracefully. :-) (Hailo is SQLite-based.) Thankfully, it’s a simple sed job with all the IRC logs archived. However, Muaddib always had trouble with non-ASCII data, mixing a variety of encodings and liking to produce a gibberish result.

So, historically, people used to talk to Muaddib using ISO-8859-2 and UTF8 encodings and now I had mixed ISO-8859-2/UTF8 lines and I wanted to convert them all to UTF8. Curiously, I have not been able to quickly Google out a solution and had to hack together my own (and, well, dealing with Unicod ein Perl is never something that goes quickly). For the benefit of fellow Google wanderers, here is my take:

perl -MEncode -ple 'BEGIN { binmode STDOUT, ":utf8"; }
  $_ = decode("UTF-8", $_, sub { decode("iso-8859-2", chr(shift)) });'

It relies on the Encode::decode() ability to specify a custom conversion failure handler (and the fact that Latin2 character sequences that are also valid UTF-8 sequences are fairly rare). Note that Encode 2.35 (found in Debian squeeze) is broken and while it documents this feature, it doesn’t work. Encode 2.42_01 in Debian wheezy or latest CPAN version (use perl -MCPAN -e 'install Encode' to upgrade) works fine.

On Wednesday, I have bought myself an Android phone, as my good old S-E C510 suffered from worse and worse charging problems. I have found that I find it pretty much impossible to type on a touchscreen and did not see any improvement even after light practice (on a spare second hand Android phone I acquired just for its sensor – sometime in the future, maybe it will drive a quadcopter). So, I went for Sony-Ericsson Xperia Pro (codename iyukan) with its hardware keyboard. It’s a pretty neat phone, my only complaint is a difficult-to-press power button.

However, just after turning it on for the first time, the phone prompted me to upgrade it from Android 2.3 to Android 4. The fool I was, thinking that newer is better and wanting to summarily get rid of all the preloadware apps… And since a friend told me that CyanogenMod works all right on this phone, I would need a Windows PC to upgrade to Android 4 the Sony Ericsson way, I like to have full control over the systems I use and I like CM’s tray design ;-), I went for it.

First, some tips and tricks for fellow Googlers that come by this post in a need to get CyanogenMod working on their Xperia Pro:

• Do not expect CyanogenMod wiki to be a place to document even critical issues, learn about them and solving them. Your only shot is hitting the issue blindly and then followup wild googling and IRC. More on that below.
• Ignore stock CyanogenMod. What you want is using CyanogenMod fork FreeXperia (FXP) which contains CM tuned for Xperia phones, with both custom kernel and set of drivers and applications. Follow the regular CyanogenMod flashing howto, just use .zip files provided by FreeXperia. The latest CM9.1 Xperia version FXP136 worked quite well for me, aside of wifi troubles (more on that below), camera autofocus on touching the cmaera button and maybe some compass weirdness (I didn’t verify that yet, but there are workarounds in the tracker in case it proves to be a real issue).
• If you insist on stock CyanogenMod 9.0.0-rc2, replace the boot.img you will be flashing (kernel image) with the one from FXP136, or your phone will essentially refuse to start up with applications like the Setup Wizard crashing and if you manage to get past that, the phone being quite sluggish.
• New FXP WiFi drivers for Xperia Pro (wl12xx, specifically wl1271) have support for some extended powersaving features that depend on RX streaming. On some APs, that means the device will receive packets only up to 100ms after it transmits packets itself – any packets coming after that will be lost, which means that communication with sites that take a little to process your requests (e.g. the Market) or using any kind of streaming breaks.
  I have spent the whole last night fiddling with wifi and binary patching wl12xx.ko to tweak the parameters, but I just didn’t manage to get it working with my Wifi AP. However, over the night I have tilted to thinking that this is slightly more likely bug in powersaving support of my AP rather than in the wifi firmware, which is simply using more aggressive powersaving modes now than other Android phones visiting my home wifi network before and other devices like notebooks. I have pretty much given up on debugging this now and will just buy a new AP, since with all other APs I have came by so far the phone works fine (but there are scattered reports about this problem on the net).
• My phone refuses to properly authenticate with my AP (always stuck in the “Obtaining IP address stage”, but in fact it never comes to DHCP, instead it fails right after authentication), wpa-supplicant logs WPA: EAPOL-Key Replay Counter did not increase - dropping packet and that’s it. After I restart my AP, the authentication succeeds… once; if I disconnect, I won’t connect again anymore. Again, this happens just with my AP, so maybe there is some connection to the previous problem, perhaps some authentication packets being dropped… This happens with WEP, WPA-PSK TKIP or AES, … The only workaround I have found is to restart the AP.
• Before, my phone would get stuck in a different way, believing that its rightful IP address is 169.254.222.something and never asking using DHCP for an actual IP address. The solution to that problem is to open a terminal, su, and rm /data/misc/dhcp/*.leases. Also, don’t panic if you are to connect to eduroam; even though the WiFi authentication dialog will show phase 2 to be “None”, that does not mean wpa_supplicant on the phone is not internally using MSCHAP. :-)

So, in the end, the phone has eaten much of my last three days, and it was not spent installing and fiddling with neat apps but debugging some frustrating issues. I hope it will serve me better from now on… :-)

But this has been also an interesting lesson in dysfunctioning open source projects – yes, I mean CyanogenMod and FreeXperia. First of all.

The problem is that the projects are very unfriendly to their audience. Sure, CyanogenMod has a pretty front website and after some very non-straightforward you may even reach a straightforward HOWTO for your phone that you may follow to do the installation, but the project becomes unfriendly once you need to do some powerusery things with your phone or even start taking look at the source and doing some development. First, I should take a note that some of the issues are probably FreeXperia specific. Let’s take a look at some of the problems:

• Bad overview documentation. I found no way to actually learn on my own about FreeXperia and its relationship to CyanogenMod (which is still not completely clear to me). Even long after first hints to “use FXP136” or whatever, I was clueless about what the “FXP” actually meant.
• Bad release documentation. On Xperia Pro, the latest CyanogenMod official is 9.0.0-RC2. There appears to be absolutely no way to learn about what kind of state is it in – what blocker bugs are there to keep this at RC2? Is it worth waiting for 9.0.0? It appears to be all just in the minds of the maintainers so the only way to decide which version of CM to pick is to waste time trying to install it. Also, FreeXperia homepage caries essentially no documentation either, not even linking a fairly essential companion forum thread.
• Bad detailed documentation. It appears that the only way to learn about issues and try to solve them is either asking on the forum and navigating its unwieldy paginated threads, or asking on IRC and hoping someone knowledgeable is by accident following the channel at that moment. There is a Wiki but most attempts to document issues and help out fellow users or simply correct factual errors appear to be reverted without explanation.
• Bad development documentation. Xperia Pro is actually a huge exception here since there is an actual HOWTO on compiling CyanogenMod for it using the arcane build system. However, trying to navigate the masses of github repositories of both CyanogenMod and FreeXperia and understanding how they relate, in which repository and in which branch can I actually find the kernel I’m running and where does my wl21xx module come from has taken me several hours anyway. While FreeXperia is supposed to be an “open source” project, there is actualy no word on its homepage about where to get the sources and how are they built; you are on your own in the GitHub maze (and no, there is no link to GitHub’s FreeXperia account on its homepage either). I’d say this is on the verge of violating GPL, though probably not quite behind the line yet…
• Less than ideal developer attitude. The people at IRC are mostly very helpful and I thank them again for all their help. But I have been rather discouraged by my wiki experience and why should I even bother reporting bugs?

I complained a bit about some of these issues in the past few days. A fellow IRC user asked “would you rather developers spend their time on documentation than fixing bugs?”. I think resounding “YES” is in order. Most basic documentation (what is what) does not take long to write and goes a long way. Also, putting effort to fixing bugs is usually no excuse for bad attitude to users.

It seems to me that to be a happy CyanogenMod user, you either do not actually put much effort in poking the system and you are lucky to have a most mainstream device with all the major issues ironed out, or you go all the way to become a core developer and learn about all the details. If you are stuck somewhere in-between, willing to get to the bones of the system to solve your problem but just wanting to solve your problem, CyanogenMod/FreeXperia gives you no choice but to spend days learning about all the ways things work and are getting done.

Given that, it is actually surprising to me that it still works as well as it does. It is an interesting case study in open source dynamics. I think it will be interesting to see whether FreeXperia can survive for long time as the original developers, who don’t work in a much open environment, wear out and enthusiasm of newcoming fresh developers will be required… Let’s watch and learn!