Probablistic Deshredder -in Python

The second exercise in the ai class was to recompose a shredded message, this is a bit harder than the Caesar Cypher -although still do-able by Mk1 eyeball. Here's the message :

de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on
ry|  |is|th|is| b|eo|as|  |  |f |wh| o|ic| t|, |  |he|h
ab|  |la|pr|od|ge|ob| m|an|  |s |is|el|ti|ng|il|d |ua|c
he|  |ea|of|ho| m| t|et|ha|  | t|od|ds|e |ki| c|t |ng|br
wo|m,|to|yo|hi|ve|u | t|ob|  |pr|d |s |us| s|ul|le|ol|e
 t|ca| t|wi| M|d |th|"A|ma|l |he| p|at|ap|it|he|ti|le|er
ry|d |un|Th|" |io|eo|n,|is|  |bl|f |pu|Co|ic| o|he|at|mm
hi|  |  |in|  |  | t|  |  |  |  |ye|  |ar|  |s |  |  |.

We want to put the columns in the correct order, the rows already are ordered. I made one cheat optimisation, I assumed that the first row of the first column wasn't indented and that it would begin with a capital letter. Which gives me column 4 as the first column.

Rather than trying to match words, which looked hard as we don't know where the boundaries are, I decided to match n-grams (sequences of letters) and in the end I used trigrams, as I haven't yet found a decent table of quad-grams.

A few Python first for me here, reading in a file, cleaning it up on the way :

f = open('shredded.txt')

regex = re.compile('[,."]')
input_table = []
output_table = []
for str in  f:
  str = regex.sub(' ', str.strip("\n"))
  str = str.split('|')
  input_table.append(str)

Transposing a table (this is nice) :

col_table = zip(*input_table)

Then I created a Trigram class to return the probabilities of any given sequence, I used data from the Brown Corpus , there was one 'gotcha' here, the sequence " s " -the corpus assumes that "'s " is transformed into " s " and assigns it a very high probability, I decided to change this to the same as that for " t ".

Other than that it's a straight forward naive Bayes sum of probabilities, although I do it for both 'foward' trigram sequences; i.e for |Cl|nf| I find the probabilities for 'Cln' and 'lnf' and sum them.

So how does it do?

Claude Shannon founded ition  manfor 
theory  which is the bas      f is o 
probabilistic language mand   s odel 
of the code breaking methat    thods 
you would use to solve toblem prhis  
with the paper titled  Amaticahe Matl
Theory of Communication ished bl  pu 
in this year 

not too shabby, you could answer the question from this, it gets the first 12 columns dead right and bits of the others in the correct order as well.

Longer columns would increase the chances of success, but what about algorithm tweaks? Things to try :

• Find a 4-gram table
• Post process for words (I was put off this as my WordFreq doesn't include names)
• Process for spaces -there should only be one space between words, I have more as I have substituted spaces for punctuation. We could use this to detect 'illegal' orderings.

Apple Cake

Apple and Cinnamon cake

I have a glut of apples on the allotment this year, especially the cookers, so I'm going through recipes trying to use them up. I came across this on the Internet, made a few alterations, and it has turned out well -so I though that I'd share.

Ingredients

• 500g of apples -peeled cored and chopped
• 125 ml sunflower oil
• 275g plain flour 
• 2 eggs
• 200g of soft brown sugar
• 1 tbsp runny honey
• 1 tsp vanilla essence
• 1 tsp bicarb
• 2tsp cinnamon
• 1/2 tsp salt

Cooking time ~50 min

 Method
  
Grease and flour a 20 * 20 c.m. tin, put the oven on at 180 C. Peel core and dice the apples. Beat the eggs and oil together until a bit frothy, they aren't going to foam. Add the rest of the ingredients, bar the apple, to the mixer and combine together until smooth (ish). The mixture will be pretty stiff at this point. Add the apples, I had the Kenwood going at 1 for this -some of the apples get squashed which loosens up the mixture. Turn out into the tin, levelling off the top and working the mixture into the corners.

Bake for 30 mins, try it with a skewer (you could try it with a Skua, but it will be noisy and the RSPB will hate you). I found that it needed more time so I knocked the heat down to 160 C and it needed 15 - 20 mins, but I got a cake that was just right in texture and not burnt on top.

Variations
Mixed spice, might be nice, or some ginger -perhaps the syrup from stem ginger?
You could add sultanas.
It would probably stand some treacle.
Change the apples -my cookers aren't Bramleys, they are Monarchs -which aren't as sharp as a Bramley and they hold their shape better -hence the chunks in the cake. I would recommend them as a tree for anyone wanting a cooker as you can buy Bramleys anywhere. Mine came from Adams Apples.

Caesar cypher solver in Python

An optional exercise in the ai class was to solve a Caesar cypher. The example given was pretty simple with only one shift, so the easiest way to solve it would be by inspection after printing out all 26 options.

But that isn't in the spirit of things, we want to solve it in an a.i. manner using probabilities, here's

the original cypher :

"Esp qtcde nzyqpcpynp zy esp ezatn zq Lcetqtntlw Tyepwwtrpynp hld spwo le Olcexzfes Nzwwprp ty estd jplc."

The first thing I noticed is that it has structure, if we assume that the punctuation has been left alone then we have a set of words. I can look up the probabilities of words in a table -I used the one from the British National Corpus:  ftp://ftp.itri.bton.ac.uk/bnc/all.num.o5

I created a Python class with a dictionary of words and probabilities (word_freqs) and a class method to return the probability of a word :

  @classmethod
  def word_prob(self,word):
    if word in self.word_freqs:
      return math.log(self.word_freqs[word] / self.corpus_freq)
    return math.log(1 / self.corpus_freq)

I take the log because, even with the correct, english, sentence, the probabilities soon get too small for simple arithmetic as they are multiplied together for each word in the sentence to get a 'sentence probability'

Storing and sorting the probabilities stumped me for a bit, but I eventually decided upon a list of tuples :

prob_map.append((prob, string2))


Which I sort, using the operator module, with :
 sorted(prob_map, key=operator.itemgetter(0), reverse=False):


This seems clunky compared to PHP, Perl or even C, but I'm still feeling my way around Python so I'm hoping that there's a better way.

To give me the answer :
(-7308.628573183837, 'the first conference on the topic of artificial intelligence was held at dartmouth college in this year.')

1956 BTW

There we go, a first bit of Natural Language Programming -which I have signed up for this term.

Kobo Touch eReader -it's not a Kindle!

Touch Me!

I decided that it is time to join the 21st century and get myself an eReader. I  read a lot, often on the commute, and if  go on holiday half the weight is books so it makes sense to look for a smaller and lighter solution. Earlier readers were generally pretty ugly, but the latest ones, like the Kobo and the Kindle look pretty good. So what to buy? I did a bit of research and ruled out a tablet straight away, although they are more versatile devices the screens aren't as good for reading and they are considerably heavier and pricier.

The major player is the Kindle, it's small, light and decent looking -but at the time of writing has no touch screen in the UK. Other drawbacks are the closed format and the fact that Amazon get enough of my money anyway, a market is only a market if there is competition, otherwise it is a monopoly. There's the Sony, but that's expensive, at £129 when compared to the Kobo Touch at under £100.

The Kobo Touch is less then a ton -a mere tenner more than the non-touch Kindle, looks pretty decent -especially in the matt black, and can be picked up in the high street from Smiths or Argos. The spec is much the same as the Sony and the Kindle, With a 6 inch Pearl E-ink display, battery life around a month and 1 GB of free storage, although on the Kobe you can insert a microSD card to increase this.

The Kobe, unlike the Kindle, reads E-PUB books, so you are not restricted to the Kobo shop. I haven't had a good poke around the shop yet -but it looks well enough stocked. Kobo also supports DRM locked books via Adobe Digital Editions, which means that I can read books from the county library, I've downloaded Flashman on the March to try it out.

It will also cope with PDFs -so I have copied the G3 manual onto it,, and it displays well enough. This is a bit of a boon as the manual comes as a PDF, which means either printing it out or lugging a laptop if you want to refer to it away from home.

In use -it hasn't had a real test yet, but so far so good. The display is clear and pleasant, the touch screen works well, although it can be a little slow compared to the phone. The Kobo Touch is light and easy to hold in the hand, the quilting on the back is solid and feels quite pleasant. My eyes are still adjusting to it, probably because I'm holding it at a different distance and angle than I would a book, but he font, size and spacing are all selectable. It strikes me that these devices might be good for older readers (which I am rapidly becoming one of) as they are a lot lighter and handier than large print books.

The software works well and the device is pretty intuitive, for someone who hasn't used a reader before, as it should be -there isn't much to it. It is easy to bring up the table of contents for a book and navigate around it, I was half way through 'The Castle of Otranto' on my android phone, and I'm now at the same place on the eReader. If you use the Kobo Reader software on your devices, then what you're reading should be kept in sync, but I haven't tried this. Words can be checked in a dictionary and highlighted, pages can be annotated -you can even browse the web if you are desperate enough. I'd advise sticking to what the Kobo does best just read books on it, it's very good at that.

In conclusion -right now, this Christmas, in the UK- the Kobo is a Kindle killer, when Amazon ship us the Touch and open up their shop in the same way that they have in the States then it won't be, except that the Touch may well be 30% more expensive, and that's a good few books.

Zuiko Your Way -Old Lenses On New Bodies.

The time has come, the walrus said,

to speak of many things,

of shoes and ships and sealing-wax,

of OM adaper rings.

Couldn't resist the rhyme, so now I'll have to write a post about it. One of the isuues with switching camera makers is that you are left with all the old kit. One thing to do with all the old glass is to reuse it, and Olympus OM fit Zuiko lenses are supposed to be good for this, and especially so for the micro 4/3 format of the Panasonic G3 . There are two reasons for this, firstly the lenses are quick, due to the width of the OM fitting, and secondly they are light -it was part of the OM way- and so should put less strain on the mounting ring of the G3.

One thing to consider though, is that the focal length of the lens will double when used with the 4/3 system, so the 50mm standard lens becomes a 100mm portrait lens. The 500mm mirror lens is now a 1000mm bird spotters delight (maybe).

Another thing to note is that you can pay more or less what you want for the adapter, this one was fourteen quid from eBay, best price on Amazon seemed to be double this, the official Olympus MF-2 is £130! So far this one seems to be well manufactured and it came from a UK supplier (all the Hong Kong wanted more).

Finally, these lenses won't integrate the camera's electronics, unsurprisingly as the OM lenses don't have any. This means that there is no auto-focus and you have to put the G3 into 'shoot without lens' mode and use Aperture priority (A) on the top dial to shoot. When you do that the camera seems to work pretty well, although at high focal lengths it seems to over-expose, but maybe I need to read the manual.

I'll perhaps talk about the individual lenses later -but for now here'a a shot from the Sirius mirror lens.

Birdie -watch me!

Panasonic G3 -a walk in the country.

Will you lot get away from that tree!

This is the first time I have taken the new camera out to play, and it's done pretty well. I was a bit worried that colours would be too cool, this wasn't the best day to prove it one way or another, it was getting near to sunset and the mist was rising, but all in all I am pretty pleased. I did play around with the camera settings a little, but I wasn't organised enough to write down what I used.

 

Mister friendly poses for the Panasonic

Generally I used the viewfinder, rather than the  screen, it has a dioptre adjuster so that you can compensate for any optical shortcomings that you have and bring the menu in focus. It's all pretty intuitive -which is just as well as I have yet to open up the CD with the manual in it. The viewfinder is good enough that I'm pleased that I chose this camera rather than, say, the Olympus without one.

I think I used the flash

One problem that I did have was with the buttons on the back of the camera by the screen, which I found myself hitting by accident, sending the camera into some strange modes. Another is that the touch screen, whilst usable, isn't the most responsive -it's quite a bit worse than the one on my LG Optimus phone.

Colours look pretty good here

Moody Views

New Toy -Panasonic G3 Camera.

Panasonic Lumix G3

We're off on holiday next year, and it's the sort of holiday where it's worth taking a decent camera. I have long been a fan of the Olympus OM cameras, currently I have an OM4, but the cost of e6 (slide to you) processing is going through the roof, £15 plus with a decent scan per  roll, plus the price of the film, and slides have never been the most user-friendly medium. Medium, that term does bring a smack of the spiritualist about it, gathering a darkened room to look at grainy images of the past -sounds like many a photo club meeting from the seventies and at least with 'the other side' you don't get the cheesy music (unless your spirit guide is Barry Manilow, what do you mean he's not dead!).

I have had a couple of digital cameras before; a Kodak DC120 which took surprisingly good pictures, and an Olympus 4000Z which you can still get CAMMEDIA memory for. But it is time for something that could produce quality shots rather than just snaps.

Why the G3? Firstly, I didn't want anything bigger and heavier than the OM4, small is beautiful, and that bought me to the small system cameras from Olympus, Panasonic and Sony. Secondly, call me old fashioned, but I wanted a viewfinder -that got me straight to the G3 (although some of the others offer it as an add on). Lastly price -it seems to offer the most bang for your buck. There's other good stuff too to wibble on about; such as the tilting touch screen, 16 MegaPixel sensor, cross-manufacturer micro four thirds system which means more lenses, the G3 looks like a proper camera without trying to fake one from 30+ years ago. If I wanted a range-finder I'd use my Nikonos or Voigtlander, come to think of it the Nik doesn't have a rangefinder -just 'f8 & be there'.

First impressions out of the box? The camera looks and feels great -the lens looks and feels cheap. Charge it up, turn the camera on and the G3 works pretty much as you'd expect, I was getting some sort of pictures out of the it at the first try.

I'll take it for a walk and let you see the results.