New Blog

I'm quite lazy... and to keep this blog clean, I decided to create a now one solely dedicated to security and programming. Please check it out: dakhma.net

Oh by the way, a dakhma is construction for the purification of dead bodies in Zarathustrian religion, i.e. the bodies get cleaned by birds.


Last notice: I hope to post more language/linguistic related news soon. Though I'm currently working on quite a lot of projects.

Zipf's law

Last friday I gave presentation on Zipf's law primarily concerned with processing frequency lists and spectra in R and zipfR. The scripts contain two Python programs for extracting frequencies out of NLTK's internal Gutenberg selection corpus and the section J of the ACL Anthology corpus. If you don't have access to the ACL, I provide the processed TFL and SPC files for both corpora in the ZIP file.

Download:
[Slides]
[Scripts]

Some NLP-related Python code

1. A program that counts the Flesch Score of a text. Code here. Don't know if the syllables are computed correctly.

2. A program that searches a wordlist for minimal pairs. Code here. Example here. The format of the wordlist is restrictive and the minimal pairs are printed twice!

3. A program that obfuscates the input, which means that first and last letter are the same but everything in between is mixed around. Code here.

4. A program that constructs a tree from a file and searches for the common minimal ancestor of two nodes. Code here. Example here.

Python-based RPN Evaluator

This program evaluates logic expressions out of a textfile with Reveresed Polish Notation (RPN) syntax.

Example world file:
wind
/sun
/rain
red

wind and red have the value of 1, sun and rain 0 since they are prefixed by "/".
Here's the syntax to run the program: "python log.py myworld.world".
It quits when an empty expression occurs.

Example usage:
C:\Python26>python log.py myworld.world
Logical Expression: rain sun &
0
Logical Expression: sun red |
1
Logical Expression: sun wind ^
True
Logical Expression: winter sun &
*** Error while evaluating: Bad name: 'winter'.
Logical Expression: sun red
*** Error while evaluating: Unbalanced expression: 'sun red'.
Logical Expression: sun red red |
*** Error while evaluating: Unbalanced expression: 'sun red red |'.
Logical Expression:

C:\Python26>



Find the source code here.

Download all SMBC Comics

Simple regex-based bruteforce program to save all comics from http://www.smbc-comics.com/. You'll need http://commons.apache.org/io/ and my source code.

Google Cheat Sheet 0.11

Wrote a Google Cheat Sheet: http://rapidshare.com/files/280485137/gcs.pdf

It's simple and contains every working function in Google Search, Groups, News, Calculator. What's missing? Query suggestions...

Poor Networks, Neurons and Lookaheads

Syntactic networks bear similarities to biological networks since their levels are scale-free, i.e. the distribution of nodes and edges follow a power law (e.g. social networks), and small-world, i.e. most nodes can be reached by a relatively small number of steps (e.g. social networks):

From Wikipedia [EN] [ES]

A group of researchers at the Institute of Applied Linguistics in Beijing, China tried to find similarities between semantic and syntactic networks via a statistical approach and a treebank with semantic roles. Both networks are represented by small-world and scale-free graphs but differ in hierarchical structure, k-Nearest-Neighbour correlation and semantic networks tend to create longer paths, which makes it a poorer hierarchy in comparison to syntactic networks: Statistical properties of Chinese semantic networks


Temporal fluctations in speech are easily corrected by our brain. For decades this mechanism was a mystery. Two researches of the Hebrew University of Jerusalem, Israel described how neurons adjust to decode distorted sound perfectly. Although I don't understand this very technical paper, it'll perhaps provide new algorithms for speech processing: Time-Warp-Invariant Neuronal Processing

Another improvement for speech recognition and production was achieved by the Max Plank Society which developed a new mathematical model. It's based on the look-ahead assumption, i.e. our brain tries to estimate the most probable sound-sequence based on previous information, e.g. 'hot su...' = 'sun' > 'supper': Recognizing Sequences of Sequences

These little annoying and surprising things...

...concerning Python as language of "very clear syntax which emphasizes code readability" (Wikipedia):

A = Annoying == Anti-Python

1. The naming conventions of...:

a) ...package-files/magic members: __init__.py, def __del__, __name__
b) ...visibility modifiers: _protected and __private

So _ and __ in general. Really, why did Guido do this? Is there an explanation? Perhaps it's inherited from another language?

2. The verbose...:

a) ...object inheritance declaration of each class: class Standard(object)
b) ..."self"-reference of each class-value/-constructor/-function just to indicate that it's non-static: def compute(self, number), self.Radius, def __init__(self)


(3. Multiple inheritance: It's no coincidence that most languages don't support multiple inheritance. Normally, you don't need it and it is a trap which makes debugging almost impossible. It is definitely not a feature for a language which emphasizes code readability and clear syntax.)




S = Surprising

(Powerful ability to handle and process strings in general.)

1. Lambda/Annonymous functions: (lambda x, y : x + y)
2. Managed Attributes: property([fget[, fset[, fdel[, doc]]]])
3. Great modification abilities due to magic members/methods and type-emulation.
4. List comprehension, generator expressions and yield.
5. Function decorations. Java has this one too.
6. Localization module. It's neat and easy to localize your programs.
7. Parallel computing module!
8. Awesome network protocol capabilities.
9. Unit tests.
10. The best documantation I've ever seen.

Blagh

1. Blagh:

• I read the Post "Crying" again and must say that Java is definitely my favourite programming language.
• I totally lost every knowledge of Python which's a bad thing since I'll have to use it in a exam in a few months.
• I got attached to Twitter. It's so convenient and you can watch it on the panel of my blog.
• I read Russell's Introduction to Mathematical Philosophy. Very interesting.
  

2. Pathfinder:

I had to write a small Java program that implements Dijkstra's shortest path algorithm in order to find the shortest path between two cities. You can download the source code here. You can add nodes and edges to the data.txt and the user interface is console-based.


3. Imageboardsave:

Currently, I'm writing a program which downloads every image and Rapidshare URL in a thread of an imageboard. The program works for AnonIB at the moment and the user can specify how many pages he want to search. The program scans the page for threads and download the content to:

/threadID/picturefilename.something


and the Rapidshare-URLs to:

/threadID/rapidshare.txt


Subthreads, i.e. more than a one-page thread, are considered as well. It even has a graphical user interface programmed in Java Swing. Actually, it runs pretty good right now, but I don't want to release it yet.

Language Guesser and OpenNLP Pipe

1. The first program I wrote estimates the language of a document, based on a simple statistical bigram model. It takes 5 arguments from commandline based on following syntax:

java Main trainfile_lang_1 trainfile_lang_2 trainfile_lang_3 trainfile_lang_4 testfile_lang

e.g.

java Main ./europarl/train/de/ep-01-de.train ./europarl/train/en/ep-01-en.train ./europarl/train/es/ep-01-es.train ./europarl/train/fr/ep-01-fr.train ./europarl/test/de/ep-01-de.test

and writes to the system standard output: "Die Sprache ist wahrscheinlich Deutsch." (The language is probably German.)

You see, this is very static and perhaps I'll make it more dynamic in the future. It was originally created to estimate the language of a protocol from the European parliament. You can download it here, but please be aware that the comments are in German.


2. The second program is more interesting. It takes a XML file with tags and everything and writes the sentences to a file in following format:

token TAB tag TAB chunk

e.g. for the sentence "Is this love?"

Is VBZ O
this DT B-NP
love NN O
? . O

It just takes the path to the XML file as commandline argument. To run the program you'll need 2 things. Ant and the OpenNLP models. You can download the program here

/*
* To ensure the functionality of the program, the models EnglishChunk.bin.gz,
* EnglishSD.bin.gz, EnglishTok.bin.gz, tag.bin.gz and tagdict.htm have to be
* in the models directory.
*
* IMPORTANT:
* The models have to be downloaded and placed in the models directory
* otherwise the program won't work. The download links can be found in
* ./model/readme.txt.
*
* Install:
*
* 1. Download the models at OpenNLP: http://opennlp.sourceforge.net/
* 2. Run Ant
* 3. Start the program with java -jar NLPipe.jar XMLfile
* 4. Optionally you can run the program with: ant -Dargs="XMLfile" run
* 5. Optionally you can archive the basedir with: ant tar
*/

Recap

This is going to be a very boring semester. Java is really interesting but also complicated for a beginner. Compared to Python, it feels like a mature language and you have to think (more) about what you're doing. Formal Syntax is complex and time-consuming, especially for me, since I'm not into Syntax. I'm more interested in semantics and therefore Logic is quite fancy - although sometimes it's as boring as Math. Acoustic phonetics hasn't started yet and Artificial Intelligence is fun but often too superficial - we aren't concerned with Natural Language Processing. Hence I plan to do a small pragmatic series on AI and to recap what I'll learn in the course. I also took two courses in English: Translation into German (boring as hell) and English to the 1700 century (boring lecturer), but they aren't worth to mention.

Finally, there's no post in my blogroll which could wake my interest. Except - well, in a not so positive way - for a news on Eureka Alert. This is one of the cases which I'd entitle 'the most unspectacular findings - that are no findings because everybody already knows - in science'. The study says that music is culturally independent when it comes to convey (certain) emotions. Well, everyone who's listened to a song in another language knows this. The study goes one step further and investigates the influence of music from fundamentally different cultures: Language of music really is universal, study finds

Points of Interest 16. March, 2009

1. Joint attention and the difference between we and I might be the key in order to understand language evolution.
My opinion is, that language evolved to set borders. The border of I; my person, my belongings, my needs and thoughts, my standing within society - in opposition to others.
The border of we; our tribe, our race, our territory, our hunting grounds, our ideals - in opposition to others.
Language is a cultural and psychological necessity to govern, identify, interact and define oneself if things are getting more complex. A biological necessity to define entities in time and space and to interact with them in a complex way on different planes. A way to optimize doing things, like hunting strategies, complex hierarchies, standings to other tribes: A Tale Without Episodes

2. A very strange article. As a computerlinguist I'm very interested in how they compute the evolution of a language. I can't imagine how this could work. There are several factors which seem to be just too random to be calculated. How did they trace the words? Did they use OCR to scan documents and match words? There is this particular paragraph, which I don't understand at all:

"Looking to the future, the less frequently certain words are used, the more likely they are to be replaced. Other simple rules have been uncovered - numerals evolve the slowest, then nouns, then verbs, then adjectives. Conjunctions and prepositions such as 'and', 'or', 'but' , 'on', 'over' and 'against' evolve the fastest, some as much as 100 times faster than numerals."

What does evolve mean here? Change? How can prepositions change? These things are bound by perception and are, in my opinion, as static as numerals: Scientists discover oldest words in the English language and predict which ones are likely to disappear in the future

3. I'm quite into morbid things; like mummies and anatomical stuff. Lately, Pink Tentacle wrote a post about monster mummies and living mummies - formerly known as living Buddhist monks. They've killed themselves (slowly) in a timespan of 3000 days and now are relics of a sort: Monster mummies of Japan

4. Does your language influence your preference in music? Language and music are associated: Why music sounds right - the hidden tones in our own speech

5. A very basic lecture about language held at Yale University. It covers fundamentals of linguistics - Pidgin & Creoles, language as human trait, language universals, (innate) language capacity, phonetics, morphology, syntax, semantics (in this order) and so on: How Do We Communicate?: Language in the Brain, Mouth and the Hands

Crying

Vacation! Last semester was very intense, no time for anything. Gosh, and now I'm trying to learn Java... It's far more complicated than imagined. Python was neat and easy - in comparison - but Java is far more potent, so they say. I don't quite understand why I've to write code which seems to be obsolete - at least for a beginner like me , e.g.

public class HelloWorld
{
 public static void main(String argv[])
 {
  System.out.println("Hello World!");
 }
}

is equivalent to

print "Hello World!"

in Python.

And next semester I'm going to die for sure... Here're my courses:

Formal Syntax: I'm more the Morphology, Phonology, Semantics type. Actually Syntax is the only thing which gives me problems.
Java: Well, it's going to be hard I'd say.
Logic: I like formal logic, really.
Artificial Intelligence: Very very interesting. Inference, neuronal networks, genetic algorithms and that stuff - you know...
Acoustic Phonetics: This sounds good: Reading spectrograms and get in touch with VoiceXML.

Points of Interest 17. February, 2009

1. 20 years prison or death sentence for translating the Qu'ran? Welcome to our illustrious humanistic and democratic circle, dear Afghanistan: The dangers of translation

2. Help to classify galaxies and work for science, now! You'll be shown pictures of galaxies and asked questions about their spiral arms and other features. A task which you can do better than a computer and will help astronomy: Galaxy Zoo 2

3. The 2009 Jōyō Kanji update is coming up and the two favourites are 俺 (ore, which means informal "I") and 誰 (dare, question pronoun "who?"). I think "dare" is quite common these days, even in formal context. Of course one can say donata which is more formal: Jōyō list to level up

4. Speech perception is much more than hearing sounds. There are several other senses than hearing involved: Read my lips: Using multiple senses in speech perception

5. Steven Pinker explains the critical points of his book "The Blank Slate":

Python Madness

My Night at 3 AM: Hacking Python code to learn the language. That's a life! Here's what I've done so far:

1. Decimal to dual conversion:

import sys

def bd(x):
 n = []
 if x < 0: 
  return "Positive integer required"
 elif x == 0:
  return [0]
 else:
  while x > 0:
   n.insert(0,x%2)
   x = x/2
   bd(x)
 return n

if __name__ == "__main__":
 try:
  number = int(raw_input("Number: "))
  print bd(number)
 except ValueError:
  sys.stderr.write("Integer required\n")

2. Basic truthtables:

def logicalAnd():
 for valueOne in range(2):
  for valueTwo in range(2):
   print "%d %d %d"%(valueOne, valueTwo, valueOne and valueTwo)

def logicalOr():
 for valueOne in range(2):
  for valueTwo in range(2):
   print "%d %d %d"%(valueOne, valueTwo, valueOne or valueTwo)

def logicalConditional():
 for valueOne in range(2):
  for valueTwo in range(2):
   print "%d %d %d"%(valueOne, valueTwo, not valueOne or valueTwo)

def logicalBiconditional():
 for valueOne in range(2):
  for valueTwo in range(2):
   print "%d %d %d"%(valueOne, valueTwo, valueOne is valueTwo)

if __name__ == "__main__":
 op = raw_input("Connective: ")
 if op == "and":
  logicalAnd()
 elif op == "or":
  logicalOr()
 elif op == "conditional":
  logicalConditional()
 elif op == "biconditional":
  logicalBiconditional()
 else:
  print "Connective not known"

3. ASCII table. First column is the ASCII value, second column is the local interpretation, third column is the raw UTF-8 interpretation, fourth column is the hexadecimal value:

for element in xrange(256):
 print "%s \t %s \t %s \t %s"%(element,%%
 chr(element), str(tuple(chr(element)))%%
 .strip("()'',"), chr(element).encode("hex"))

4. Perhaps a complicated dual to decimal program:

def reverseRange(input):
 n = []
 for i in range(len(input)-1,-1,-1):
  n.append(i)
 return n

def singleValues(input):
 m = []
 for  i in input:
  m.append(i)
 return m

if __name__ == "__main__":
 input = raw_input("Number: ")
 rR = reverseRange(input)
 sV = singleValues(input)
 dN = 0
 for i in range(len(sV)):
  dN += int(sV[i])*2**int(rR[i])
 print dN

This code works in 2.6.1

Ubuntu On Samsung NC10

Last month I bought Samsung's NC netbook and I'm astonished how cool it is. It's really handy if you travel a lot (I do!) and have a lot to code (I do!). Unfortunately, there are some issues which have to be solved first.

1. Touchpad problem: It totally sucks when you write something and your fat and overdimensioned nerdy hand (or what I like to call it: The Hand Of Code) gets even slightly over the touchpad. Therefore you totally need to disable the touchpad for a certain time. Fortunately, the gods of Ubuntu created a program called 'syndaemon' which exactly works like this. It's useful to put it to your autostart via System > Preferences > Sessions.

2. Excessive load cycle: It slowly kills your hard drive. So better follow these instructions to set the correct values. It seems that there are still issues even if you've changed the options.


For further information you should check out:

Ubuntu on the Samsung NC10
Linux on the Samsung NC10
The Ubuntu NC10 Community Documentation

Natural Language Processing Online Applications

I want to present an interesting link list with online and free to use interactive NLP related applications:

1. XLE Web Interface allows you to parse sentences of German, English, Norwegian, Welsh, Malagasy and Arabic. You'll get a very detailed parse tree and the functional structure of the sentence, for "This is madness!" you'd get:

2. Wortschatz Leipzig is a German application that crawls the web for a word and returns a detailed analysis of the word frequency, collocations and semantic relations. The word-graphs are most interesting, e.g. the graph for "Humbug" (German for "rubbish"):

3. WordNet is a large lexical database for English, e.g. "house" would show following interpretations:

4. Answerbus is a search engine like Google or Yahoo but with semantics! You can ask natural questions like "Who killed JFK?" and will (perhaps) get the answer "Oswald killed JFK". Perhaps... because the system actually sucks and you can easily outmaneuver it. Another search engine is START, which sucks too.

5. Wordfall is an awesome linguistic game! It's like Tetris but instead of blocks you have to match words to their constituents. Look:

6. Wortwarte is a German site about neologisms in the media. They are collected and sorted.

7. A cool German chatbot called ELBOT. It would definitely pass my Turing Test.

8. Think of a thing and 20Q will read your mind by asking 20 questions.

9. Machine Translation is one of the prime disciplines of NLP. Everyone knows Babelfish. It's not only a translator in the Hitchhiker's Guide but also an online translator like Google Translation.

10. TextCat is a language guesser based on an n-gram Perl script. Another and better one would be the XRCE language guesser.

N-Gram M-Adness

One of the main basic concepts of Natural Language Processing is the model of n-grams. It's the splitting of a sequence into n-subsequences, e.g.

(1) Now the lord once decided to set off for the mountain where the man lives

For n = 1 (unigram) the sentence is splitted into:

(n = 1) [ [Now] [the] [lord] [once] [decided] [to] [set] [off] [for] [the] [mountain] [where] [the] [man] [lives] ]

For n = 2 (bigram) the sentence is splitted into:

(n = 2) [ [Now the] [the lord] [lord once] [once decided] [decided to] [to set] [set off] [off for] [for the] [the mountain] [mountain where] [where the] [the man] [man lives] ]

For n = 3 (trigram) the sentence is splitted into:

(n = 3) [ [Now the lord] [the lord once] [lord once decided] [once decided to] [decided to set] [to set off] [set off for] [off for the] [for the mountain] [the mountain where] [mountain where the] [where the man] [the man lives] ]

Okay you get the idea. The sequence of words "w₁, ..., w_k" is splitted into "w_k and w_k-1" for bigrams, "w_k and w_k-1, w_k-2" for trigrams and "w_k and w_k-n+1, ... w_k-1" in general.

Here's the relevant Python code for making n-grams:

def makeNGrams(inpStr, n):
    token = inpStr.split()
    nGram = []
    for i in range(len(token)):
        if i+n > len(token):
            break
        nGram.append(token[i:n+i])
    return nGram


Or a bit more condense:

def makeNGrams(inpStr, n):
    inpStr = inpStr.split()
    return [inpStr[i:n+i] for i in range(len(inpStr)) if len(inpStr)>=i+n]


Why do you need this?

1. Machine Learning uses n-gram models to learn and induce rules from strings.
2. Probabilistic models use n-grams for spell checking and correcting misspelled words.
3. Compression of data.
4. Optical character recognition (OCR), Machine Translation (MT) and Intelligent Character Recognition (ICR) use n-grams to compute the probability of a word sequence or generally a pattern sequence.
5. Identify the language of a text (demo here)
6. Identify the species given a DNA sample.

For example you can compute the probability of a sequence by multipling all previous probabilities: P(w_k|w₁, ..., w_k-1) but if one of these previous sequences is zero, the whole expression will be zero too. This is a huge problem, since these long sequences are hardly ever seen in corpora, even if you take the internet, e.g. "The world, as we know it, will be changed by the pollution of the environment". Therefore we only take the direct predecessor by using an n-gram model and can estimate the probability. Another application for n-grams can be found in Part of Speech tagging and probabilistic disambiguation of tags, e.g. the probability of "book/NN the/DT flight/NN" versus the probability "book/VB the/DT flight/NN".

I wrote a very simple program to predict the next word given a sequence of words in a corpus, e.g. input: "I will eat"; output: "fish" you can find it here.

Another program concering n-grams, which I wrote, is available here. It extracts proper nouns, e.g. "New York City" from English texts.

Art of the State

Currently I'm very busy in learning the formal foundations of linguistics (Set Theory, Relations), programming (Python) and computational linguistics (Maximum Likelihood Estimation, Context Free Grammars).

I got an e-mail. Really. From a reader. By the way, it's my first; that's why I'm quite enthusiastic. He suggested to introduce my readers (do I have any?) to his blog Neuropolitics. Well, well, I read the first sentences and decided to mention it in this post. Form your own opinion.

Perhaps I'm going to write about the foundations of Natural Language Processing or upload some Python code which could be used to play with strings. Mostly harmless, not really meaningful code. I don't think that I'll have time for something else anyway.

Time's running, running out

Unfortunately, I don't have time to blog for the time being. I study natural language processing, which is very intense. So give me a week or two and I'll come back.