Mining frequent subsequences in Python

So, I was trying to reimplement [Zaki et al 2009, "VOGUE: A Variable Order Hidden Markov Modelwith Duration based on Frequent Sequence Mining"] where they describe VGS, an algorithm for frequent k-subsequence mining while keeping track of the gap symbols. The author has the VGS algorithm implemented in python already, but I decided to implement my own "simulation" of VGS in a map-reduce way.

Here's the code of the function, it accepts a sequence as a python list of objects (tested only with strings though), a minimum support minsup and a maximum gap maxgap between symbols, and it returns a record of the kind {k-subsequence : , (Frequency : , Gap_Symbols : }:

https://gist.github.com/mmxgn/2693bebb28d5a71f42c7

An example (from the VOGUE paper):

>>> seq = list("ACBDAHCBADFGAIEB")

>>> print find_frequent_subsequences(seq,3, 2, 3)

{('A', 'C', 'A'): (2, ['H']), ('C', 'B', 'A'): (2, []), ('C', 'B', 'D'): (2, []), ('A', 'B', 'A'): (2, ['C', 'H', 'C']), ('A', 'C', 'B'): (2, ['H']), ('A', 'B', 'D'): (2, ['C', 'H', 'C']), ('C', 'D', 'A'): (2, ['B', 'B', 'A']), ('D', 'A', 'B'): (2, ['F', 'G']), ('A', 'C', 'D'): (2, ['H']), ('A', 'D', 'A'): (2, ['C', 'B']), ('B', 'D', 'A'): (2, ['A'])}

 

I hope someone finds that useful. Sorry if I re-invented the wheel. I am sure there are faster ways to do it but I needed to build on that.

Explanation:

As described in [Zaki, 2001], map every symbol s in our sequence S, to its position in S. For example the first  2 items will be: [(A, 1), (C, 2), ...].

Then we reduce to F1 = {A: [1, 5, ...], B: [3, ...] } and filter out those elements that appear less tha
n minsup.

Then combine F1 with itself. I.e produce [(AB, [1,3]), (AB, [5,8]), ...] keeping only those elements that have a maximum gap of maxgap. Subsequently, reduce that again to F_k = {AB: [[1,3],[5,8],...],...} and filter out based on the minsup value.

Repeat the same by combining F_k with F_1 until you have reached the desired subsequence length k.

An Introjucer .desktop file for gnome.

An excellent class library for C++ VST development is Julian Storer's JUCE. It can produce plugins in the VST (2.x, 3.x), RTAS, AAX and  AU formats  and is cross platform across Windows, Linux and Mac OSX.

The best way to program in Juce is through Juce's own Project Management tool Introjucer which relies under `../extras/Introjucer' when cloning JUCE from its GitHub repository.

After installing it by running make in `../extras/Introjucer/builds/Linux' and sudo install Introjucer /usr/local/bin (or your desired installation path) you can copy `../extras/Introjucer/Source/BinaryData/juce_icon.png' to your `~/.icons' directory and then put the following .desktop file into your  `~/.local/share/applications' folder:

#!/usr/bin/env xdg-open
[Desktop Entry]
Type=Application
Encoding=UTF-8
Name=Introjucer
Comment=JUCE's project-management tool and secret weapon.
Exec=PATH_ΤΟ_BIN_DIR/Introjucer
Icon=PATH_TO_YOUR_HOME_DIR/.icons/juce_icon.png

and then you can easily run Introjucer from your gnome-shell.

Fun with finite-state machines, graphviz and python

Hello,

I have come in need for a grammar parser in python (context-free). While there are plenty in python, many of them are very undocumented, some seem to have become orphaned projects and `yapps2` and `pyparsing` that I tried seem to be a bit limited for what I need them (or most probably I'm a noob). So, also in order to refresh my memory on grammars, I decided to make my own parser in python.

The first step was, as I saw it to go back to the roots, to finite-state machines. It happened that it is quite a bit of fun especially because it allows me to have a dip into `graphviz` and `pydot` for pretty plotting the state machines.

Here are some examples from "Elements of the Theory of Computation - H.Lewis, Ch. Papadimitriou, 2nd ed.


The first one is for the language L(M) = { w \in (a,b)* : w has an even number of b's}

And the second one decides the language L(M) = { w \in (a,b)* : w does not have three consecutive b's }

And here is the code: https://gist.github.com/mmxgn/5973875

Musical CSPs with Mingus and python-constraint

Hello,

I was looking for a nice python library for constraint programming. Unfortunately, the only one I could find was python-constraint which seemed quite nice and straightforward, but after using it for a while, I find it very limited.

So, as a first example, I tried solving the pretty classic musical CSP described at the Strasheela Examples page as the 'All Interval Series' which is taken from music serialism.

The problem states that we want to put a series of all different pitch classes on the chromatic scale, where each interval appears exactly once. We also take account for inversely equivalent intervals.

I used python-constraint in order to construct my CSP by using pure python syntax, and mingus to create a midi track and render it to .pdf, .png and .mid files.

Here's the code:
https://gist.github.com/mmxgn/5891884

Here's the output score with lilypond:

and the link to the midi file.

Python generator awesomeness: SEND+MORE=MONEY

Hello,

One awesome thing with python is its "yield" keyword and the notion of generators. It can be applied in order to program in the functional and logic paradigms.

For example, let's take the following problem:

You have the expression:

SEND + MORE = MONEY

where every letter corresponds to a distinct digit (0 to 9, except S and M that cannot be 0). Find the corresponding digits for each of the letters so that the above equation holds.

So we have the variables S,E,N,D,M,O,R,Y.
With the domains:

S,M = [1,..., 9] 

E,N,D,O,R,Y = [0,...,9]

And the constraints:

S,E,N,D,M,O,R,Y distinct. 

SEND + MORE = MONEY

A beautiful way to do this is with python generators. For example, this can be solved in a single python statement as such:

    solutionGen = (\

        (s,e,n,d,m,o,r,y)\

        for s in range(1,10)\

        for m in range(1,10)\

        for e in range(0,10)\

        for n in range(0,10)\

        for d in range(0,10)\

        for o in range(0,10)\

        for r in range(0,10)\

        for y in range(0,10)\

        if len(set([s,e,n,d,m,o,r,y])) != len([s,e,n,d,m,o,r,y]) and\

        s*1000 + e*100 + n*10 + d +\

        m*1000 + o*100 + r+10 + e ==\

        m*10000 + o+1000 + n*100 + e*10 + y)

Just like that. You can get a single solution to this problem to SingleSolution with:

SingleSolution = solution.next()

Or every possible solution in a list with:

Solutions = [i for i in solution]

Magic.

Of course the above is not really efficient. This gave me a runtime of 122s on my core 2 duo e8400.

What you can do to improve it a bit? Well, for starters, replace the domains ( i.e range(0,10) ) with two constants out of the loop, i.e. Dom1 = range(1,10) and Dom2=range(1,10) so that they are not computed at each iteration. Then, a solution is more probable to appear at a range of bigger integers (we want two 4-digit numbers added to give a 5-digit number) so we can reverse the way we search the domains. So let's replace the above with:

    Dom1 = range(9,0,-1)

    Dom2 = range(9,-1,-1)

This, will give me a runtime of 16s.

Can we do more (less)? Yes. If you watch carefully to the above snipplet, we test every possible assignment for a solution while we could reduce the search space by not testing values that could not appear in a solution in the first place. For example, when S gets a value of '3', E cannot appear with the same value in the solution. So, while we search for a solution we sould "propagate" the distinction constraint. Using the yield keyword we can write the above snipplet as:

def solution():

    Dom1 = range(9,0,-1)

    Dom2 = range(9,-1,-1)

    for s in Dom1:

        for m in Dom1:

            if m == s:

                continue

            for e in Dom2:

                if e in [s,m]:

                    continue

                for n in Dom2:

                    if n in [s,m,e]:

                        continue

                    for d in Dom2:

                        if d in [s,m,e,n]:

                            continue

                        for o in Dom2:

                            if o in [s,m,e,n,d]:

                                continue

                            for r in Dom2:

                                if r in [s,m,e,n,d,o]:

                                    continue

                                for y in Dom2:

                                    if y in [s,m,e,n,d,o,r]:

                                        continue

                                    if C2(s,e,n,d,m,o,r,y):

                                        yield (s,e,n,d,m,o,r,y)

 Which gave me a runtime of  0.56s.

Not bad.

9 months of Army Service

On 9th of April, I finally completed my 9 month mandatory Service to the Greek Army Armed Forces. It actually seemed like a century of service.

I served:

• One month of training at the Engineering Corps training camp in Nafplio. First Batallion Third Company.
• Three months at the Hellenic Presidential Guard Company of Administration.
• Five months at the Hellenic Army General Staff Batallion as a soldier of the Honor Guard. 

So, now it is over. Time to pick up where I left off: http://9gag.com/gag/7044336.

See you around.

PCL&RCL Oz code

Hello,

Just a small update.

Code for my PCL (Propositional Clausal Logic) and RCL (Relational Clausal Logic) theorem prover and model searcher can be found at my github:

git://github.com/mmxgn/generic-logic.git

I was hoping to finish it before giving the link, but I am going to give it anyway.
I hope the usage becomes obvious at the last lines of logic2.oz.


There are some personal life issues that will forbid me to work on it for a long time.

Propositional Clausal Logic in Oz

Okay,

Just a little update. I wanted to see how one could implement a model searcher/theorem prover in Oz. I found some very useful presentation slides for Declarative Programming by Coen De Roover at:

http://prog.vub.ac.be/~cderoove/declarative_programming/

 Which I use as a guide for what I am trying to accomplish. Up to now, I have managed to create a PCL model searcher that can do proof by refutation using resolution. Here is some spoiler code:

% Set up a new Propositional Clausal Logic Knowledge base


PCLKB = {New KnowledgeBase init(PCL)}


% Assert some facts in it.


{List.forAll
 [
  [happy ':-' has_friends]
  [friendly ':-' happy]
  [wet ':-' rains]
  [':-' wet]
 ]
 proc {$ I}
    {PCLKB assert(I)}
 end
}


% Prove takes place with resolution by refutation


{List.forAll
 [
  [friendly ':-' has_friends]
  [friendly]
  [':-' rains]
 ]
 proc {$ I}
    {Browse prove(I)}
    {Browse
     {PCLKB prove(I $)}
    }
 end
}

and the necessary browser output:

prove([friendly ':-' has_friends])
true
prove([friendly])
false
prove([':-' rains])
true

For the moment, I will move to relational clausal logic so I am not going to bother with fixing up and releasing the code, unless someone asks for it of course. 

Set of Subsets in Oz and other stuff

Hello,

I think it is time to start posting to this blog again. I will try and keep it updated with things that have more or less bothered me and other people will more likely find them in their way. These posts will mainly concern Oz and its implementation Mozart, stuff in Inductive Logic Programming, and things about Digital Music .

Generally, what are some interesting things I have been up to these last months:

• Re-factoring the code I have published with my Diploma Thesis. I am planning to re-create it at last as a pure Oz/Strasheela implementation (I have done some progress on that). 
• Functional AUdio STream: Faust is a functional programming language that allows rapid development of efficient digital music instruments in C++. It allows easy implementation of VST technology instruments and effects, as well as PureData, etc.
• Fun with wavelets and music.

I am also searching for postgraduate studies in the fields of digital music/music technology.

I will generally update my blog mainly with progress on the above.

To begin, I have come to the following problem in Oz:

Given a list of distinct elements L, give me a list that contains all the possible sub-lists with distinct elements of L. 

This could be helpful, for example if you want to, given a set S, to construct the powerset of S.

So, I have come to the following implementation. I hope someone finds that useful:

fun {SearchSubsets L N}
   {SearchAll
    proc {$ Sol}
       SolT in
       SolT = {FD.list N 1#{List.length L}}
       {FD.distinct SolT}
       for K in 1..{List.length SolT}-1 do
 {Nth SolT K} <: {Nth SolT K+1}
       end
       {FD.distribute naive SolT}
       {List.map SolT fun {$ I} {Nth L I} end Sol}
    end
   }
end
fun {SearchAllSubsets L N}
   case N of
      0 then
      nil|nil
   else
      {List.append
       {SearchSubsets L N}
       {SearchAllSubsets L N-1}
      }
   end
end

As you can see here, I implemented it using a search strategy and finite domain constraints. I will change it to a purely algorithmic one.

What do the functions do?

• {SearchSubsets L N}: Returns the subsets of L with exactly N elements. For example, given L=[a b c] and N=2 it will return [a b], [b c] and [a c].
• {SearchAllSubsets L N}: Returns the subsets of L with at most N elements. In the example above, it will return [a b], [b c] and [a c] as well as [a], [b], [c] and the empty set nil.

In order to produce the powerset, we must call SearchAllSubsets as {SearchAllSubsets L {List.length L}}.

i.e if we feed the following:

S = [a b c d]
{Browse {SearchAllSubsets S {List.length S}}}

we will get in the browser window the list with 16 elements:

[[a b c d] [a b c] [a b d] [a c d] [b c d] [a b]
 [a c] [a d] [b c] [b d] [c d] [a] [b] [c] [d] nil]

OK, I think that is all for now. Stay tuned.

P.S. Is there a way to easily embed code to blogspot posts?

Edit: I just wrote a dummy Propositional Clausal Logic (PCL) model searcher in Oz. I will return to this once it's in a usable form.

Sooperlooper loses connection to engine

If it happens that sooperlooper shows you this dialog:

Lost connection to SooperLooper engine.
See the Preferences->Connections tab to start a new one

on newer distributions (I tried it with Fedora 16 beta 1), add your
. (substitude with your host and with your domain) to your `/etc/hosts' file on the line for 127.0.0.1 and try again.

For example, my hostname is `mmxgn' and domain is `emergencia' so my hosts file was:

127.0.0.1 localhost.localdomain localhost

and I added mmxgn.emergencia next to localhost.

127.0.0.1 localhost.localdomain localhost mmxgn.emergencia

Now when I run `slgui' I can use sooperlooper without the engine dying.

Guitar Pro 6 on Fedora 15

I had some problems installing Guitar Pro 6 for Linux on Fedora 15.
The problem was that, after extracting the .deb file on the cd, on /opt/ the updater would fail when I ran it as a user because of wrong permissions, and if I chmodded 777 the Guitar Pro directory, or ran with sudo, It would not run at all.

So, what I did:

1. I ran ./GPUpdater as the regular user, with the original directory permissions
2. While running, I chmodded 777 /opt/GuitarPro6
3. Updated

And finally (I'm at the third step right now) changing to the original 755 permissions.

Mozart/Oz and Gedit

Mozart/Oz is a very powerful language, which I recently started using.

Unfortunately, the most efficient way to use it, is from within emacs and the OPI.

I tried to find a way to use it with other editors, even for simple functionality like syntax highlighting but with no success.

Today, I tried to make a syntax `.lang' file for gedit, for Mozart/Oz so I took a .lang file
I found in `/usr/share/gtksourceview-2.0/language-specs/' (`scheme.lang'), modified it
and there I have a far-from-complete-yet-working `.lang' file for Mozart/Oz and gedit, as well some `tools' for the `external-tools' plugin (compile & compile-run with and respectively).

If you want to use it, access my github at:http://github.com/mmxgn/mozart-stuff/tree/master/mozart-gedit/

Download mozart-gedit.tar.gz, untar-gzip it and read `INSTALL'.

Here's a screenshot:

Calculating conditional pmf matrices in python (numpy)

Here is the thing that has tormented me for some time now.

I have a conjunctive probability table, with shape, for example (1,2,3,4,5,6) .

And I want to calculate the probability table, conditional to a value for some of the dimensions, for decision-making purposes. We define the values we want

The code I came up with at the moment is the following (the input is the dictionary "vdict" of the form {'variable_1': value_1, 'variable_2': value_2 ... } )

for i in vdict:

dim = self.invardict.index(i) # The index of the dimension that our Variable resides in

val = self.valdict[i][vdict[i]] # The value we want it to be

d = d.swapaxes(0, dim)

d = array([d[val]])

d = d.swapaxes(0, dim)

...

So, what I currently do is:

1. I translate the variables to the corresponding dimension in the cpt.

2. I swap the zero-th axis with the axis I found before.

3. I replace whole 0-axis with just the desired value.

I put the dimension back to its original axis.

Now, the problem is, in order to do step 2, I have (a.) to calculate a submatrix

and (b.) to put it in a list and translate it again to array so I'll have my new array.

Thing is, stuff in bold means that I create new objects, instead of using just the references to the old ones and this, if d is very large (which happens to me) and methods that use d are called many times (which, again, happens to me) the whole result is very slow.

So, has anyone come up with an idea that will subtitude this little piece of code and will run a lot faster? Maybe something that will allow me to calculate the conditionals in place.

Edit: I replaced the command in bold, with the code below:

d = conditionalize(d, dim, val)

where:

def conditionalize(arr, dim, val):

arr = arr.swapaxes(dim, 0)

shape = arr.shape[1:] # shape of the sub-array when we omit the desired

count = array(shape).prod() # count of elements omitted the desired dimension.

arr = arr.reshape(array(arr.shape).prod()) # flatten the array in-place.

arr = arr[val*count:(val+1)*count] # take the needed elements

arr = arr.reshape((1,)+shape) # the desired sub-array shape.

arr = arr. swapaxes(0, dim) # fix dimensions

return arr

Now, what before took 15 minutes to complete, now takes only about 6 seconds!

cast from 'void*' to 'int' loses precision

Irritating message, it happens because:

int a = sizeof(b)

is bad, where:

size_t a = sizeof(b)

is better.

So if you happen to try to compile something and it gives you this message, try to figure out what tries to make it an int and change it to a size_t.

Cross platform?

Ok, I know I have some days to write into this blog and I am going to ressurect it a little big.
This summer I finally started to get my hands dirty with python (since it's a so nice language). I tried to do some stuff with sockets, threads, gtk and wx since I had in mind the cross platform nature of python.

What I have as a result in my mind is that, I don't find it so "cross-platform" (at least not as much as java is - which I haven't got my hands dirty on, yet - ) . I mean, surely what I write, runs on both linux and windows (haven't tried it on my G5 mac tho, I should try) but with what cost? While it seems to run flawlessly on linux with gtk, threads and all, I had to remove thread support on windows in order to make it work (I didn't need threads anyway in the first place, just for educational purposes ) which has something to do with gtk I guess (wx didn't complain). Oh that and the nearly 50% CPU usage of pythonw.exe (you don't want a background app to take that much, do you?) and/or the executable I made with py2exe.

Also another story is py2exe. I tried to make a distributable package for python-unaware systems. It took me some time because of missing modules and stuff, made an, about 16mb dist package (about 7mb compressed) so I was happy to give it to two friends to test it.

First hit under the belt. While I had corrected the box-letters on my system (runned pango-querymodules.exe on a file under my dist directory) my buddies had the same problem, so I sent the pango and freetype dlls which it seems it worked to one of the systems (the other still had the box-letters )

Second hit under the belt. The app is supposed to be a cute and minimalistic IM client, lighter than the heavyweight Live Messenger (educational purposes only, I may release it under gpl
if its fully working tho). In a way, it succeeds, but only on linux. On windows, it made my friend's computer...fry (mine too). 50% CPU usage for a small and light app is not ok (tho I seem to have made something wrong. Emesene is on python and It runs with almost no CPU usage, on Windows)

To not get misunderstood. I love python, it just provides everything I would need so I would design and go (also scipy is awesome), but I think the current CPython is not really what I would turn to if I wanted cross platform support (web applications is another story where I want to see how it works)

But I see light on the horizon. It shines, it's pretty, and it is Java. It's jython and I think I will fell in love with it.

But anyway, next stop: undestanding how to write efficient windows apps in python, and also having a look at PARLEY