Category Archives: Artificial Intelligence

Urdu Sentiment Lexicon

With the increasing number of “opinion-dispensing apps” which enable Urdu users to write in Unicode out there on the web, there is (or will soon be) a need for getting some meaningful statistics out of the ever-present sentiment of the masses (or at least the web-savvy subset). This calls for resources which enable automatic processing of sentiment, one of which is a sentiment lexicon for Urdu. (For people uninitiated in computational linguistics, a lexicon is just a list of words).  Since I couldn’t find any sentiment lexicon available for for Urdu on the tubes, I decided to put in some effort and create a new one.

Click here to check out the Urdu Sentiment Lexicon

image

The Urdu Sentiment Lexicon is a list of 2,607 positive and 4,728 negative sentiment/opinion words for Urdu. It is based on a similar list for English available here. The English words have been translated to Urdu automatically using a dictionary lookup. All resulting Urdu synonyms have been included as well. The lexicon has also been manually inspected (but very quickly) and any irrelevant words have been deleted.

To test things out, I’ve also developed a simple javascript application which changes the color of the sentiment words according to their polarity. It also calculates the background color of the whole text using the total polarity score of the text (+1 for positive, –1 for negative). A screentshot is given above. Like all sentiment lexica, this won’t be perfect. But I am hoping this will give my fellow researchers who work on Urdu sentiment analysis a starting point and save some time.

 

Click here to check out the Urdu Sentiment Lexicon

LDA based topic modelling in javascript

Topic modelling means detecting “abstract” topics from a collection of text documents. The most common text book technique to do that is using Latent Dirichlet Allocation. Simply put, LDA is a statistical algorithm which takes documents as input and produces a list of topics. One catch is that you have to tell it how many topics you want. There’s much more to it but since this is not a tutorial post, I will stop here. (If you are interested in how it works, read the references given on the wiki page.)

I was playing around with tweets and topics yesterday. Unfortunately, I couldn’t find any javascript based LDA implementation. So I wrote one. Or to be more accurate, I converted an existing simple one-class implementation to javascript. To check how it works on real data, I need a tool with some documents. So I wrote that too.

Here’s twopicate, the output of about half a weekend of intermittent coding. You enter a search term, tell it how many topics you want, and press the button. It pulls tweets about that term from twitter and extracts topics for them. Each topic is represented as a word cloud (visible on the right). The larger a word, the more weight it has in the topic. The source tweets are on the left. Each tweet has a bar which shows the percentage distribution of topics for that tweet. You can try it yourself by clicking below.

try twopicate

 

Since it’s a javascript only solution, it runs in your browser and is consequently a bit slow. You might have to wait a minute after pressing the button. 

image

 

Oh, and you can use the source.

observing infinities

 

infinities

Making a copy of WEKA Instances

imageThis ‘thing’ took about 30 minutes to figure out. According to the WEKA documentation, if  you add a new Instance to an existing Instances object, String values are not transferred ! In case you are working on copying a dataset with a string attribute, you need to transfer the string manually. The code segment below copies the i^th instance from source to dest where the first attribute (at index 0) is a string attribute.


dest.add(source.instance(i));
dest.instance(dest.numInstances()-1)
.setValue(0,source.instance(i).toString(0));

This should come in handy for text classification using WEKA (and hopefully save your time).

Google as a Question Answering System

A Question Answering (QA) system is an Information Retrieval system which gives the answer to a question posed in natural language. For example, if you ask it Who wrote Hamlet?, it should answer Shakespeare. A few years ago (don’t ask me how many), search engines did not focus on language queries. Recently [sic], Google has started incorporating some NLP (Natural Language Processing) in their results. You can try it out by typing the same question in the search box yourself ( or clicking here ).

image

During my M.Phil. course, one of the tasks was to build a basic QA system and extend it however we liked. We used the TREC 8 dataset for evaluations. While building the system, I evaluated how current search engines (read Google) performed on this task. For this, I just queried the exact question and used the summaries of the top five results as answers. Evaluating at that time (2008), I got a Mean Reciprocal Rank (MRR) score of 0.212 over 198 questions. 156 questions had no answers found in top 5 responses.

This term, I am demonstrating for the same task. Demonstrators are usually PhD students who provide help and guidance to junior students. For pure geek fun and lack of better things to do while taking a break, I decided to quickly jolt down a JavaScript (read  JQuery ) based QA system. This time,  the resulting MRR score over 198 questions was 0.384 while only 79 questions had no answers found in top 5 responses.

The results show clearly that during the last two years, Google has significantly improved on answering NLP queries. In fact (IIRC), my baseline system back in 2008 (based on RMRS based matching of sentences from the top 100 documents returned by an IR system) could only achieve an MRR score of approximately 0.290, showing that the current results are much better than that baseline. I hope this decade sees some more developments/improvements in QA systems and I can ask a system What do you get if you multiply six by nine?

I’ve always said there was something fundamentally wrong with the universe. ~Arthur Dent

How to get formants of phones from sound files

This tutorial is mostly for people (esp. my AI students) who want to find formants of any sounds sample. So here are the things/software you will need.

  1. a good mic (recommended but not necessary)
  2. a quite room
  3. any software which can cut and save wav files. I use Praat.
  4. the console version of Praat, called PraatCon. This will be used to extract the formants from wav files.
  5. about 30 mins.

Once you have all these things, here is what you do for recording the phone sounds

  1. Start Praat. You will see two windows. You can close the other window but keep the one titled Praat Objects open.
  2. In the menu, select New/Record mono sound. Select sampling frequency to 16000 Hz, press Record and start speaking in the mic. When you are through, press Stop. Speak all the phones you want in a single go but with silence in between. In the screenshot below, AA (as in father) is spoken multiple times.
  3. Press Save to list and then Close. You should now an entry in the Objects listbox. Make sure the entry is select and then press Edit.
  4. Select the phone for which you want to extract the formants by pressing the mouse button on the start of the phone and dragging it to the point right before it finishes. Please note that we will be using the mean formant value for a phone so it is essential that only the middle part of the phone is selected to ensure accuracy and no other noise or silence is present. The selected area will be highlighted.
  5. From the File menu, select Write selected sound to WAV file, enter the name of the wav file and save.
  6. Repeat step 4 and 5 for all the phones you want to save.

Saving WAV in Praat

That’s it for the recording part. Alternately, if you already have a collection of sound files with a single phone, you can use that. You can download one such collection here. The zip file has 40 files where 2 speakers have spoken AA (as in father) and II (as in been) 10 times each.

Click here to download script and sound files.

Although you can use the GUI based Praat to find out the formant values for each phone, we want to automate the task. To do so, we will use the console version of Praat called PraatCon, and run a script to extract the formants. The small Praat script written below takes the name of a phone file as argument and outputs the first two formats F1 and F2 to the console.

form Display mean F1 and F2
   sentence filename
endform
filename_noext$ = replace$ (filename$, ".wav", "", 0)

Read from file... 'filename$'
select Sound 'filename_noext$'
To Formant (burg)... 0 5 5500 0.025 50
f1 = Get mean... 1 0 0 Hertz
f2 = Get mean... 2 0 0 Hertz
clearinfo
print 'filename$' 'f1''tab$''f2''newline$'

 

This script along with a small batch file (run.bat) which runs this script for all wav files present in the current directory, can be downloaded with all the sound files by clicking on the link below. To get this running, extract all files in a directory and place your downloaded copy of PraatCon in the same directory. The just click on the run.bat icon and watch the magic!

Click here to download script and sound files.

Output of the formanter script

The sound files in the archive give this nice little graph when their F1 and F2 values are plotted as an XY scatter graph shown below. All this was done to construct a linearly separable dataset which can be given to students for training a perceptron to distinguish between two phones. Any suggestion/comments are welcome.

F1 and F2 scatter plot of AA and II

Click here to download script and sound files.

River Crossing and State Space Search

image

I made a small 10 min demo to simulate the classic river crossing puzzle for teaching state space search in my AI class. I did exercise my right to be creative by changing the characters a bit. Jerry, Tom and Spike have to cross a river, going from the right side to left, in a boat. While you are in the boat, they behave. But as soon as you leave Tom with Jerry or Tom with Spike on one side WITHOUT the boat, they start fighting. Being a peace loving person, you don’t want that. The goal is to move them across the river with no fights. (as you may have noticed, there is no eating/killing involved in my version)

Here, we can represent each object by a Boolean variable and draw the states accordingly. The picture above can be represented by 1 0 1 0 where the left most 1 represents that the boat is on the left bank and the zero after that tells that Jerry is on right one. Similarly the next 1 and 0 denote Tom on the left bank and Spike on the right one respectively.Here is a link to the executable in case anyone wants to play it or give it to a kid to figure out. Drop me an email if you want the source code (C#). The executable requires an installation of the Microsoft .NET framework 3.5.

Download River Crossing Puzzle

Microsoft .NET framework 3.5

Solving the 8 Queens Problem

I will be teaching a course in Artificial Intelligence this summer. For some parts of the course, I plan to show implemented demos along with the course material. Looking from the students’ point of view, such tools not only decrease the learning time while in the class room, but also give enough material to play around at home in case you want to repeat what was taught. (I can empathise because I was once, and will be again (hopefully soon), a student).

While preparing the first few lectures, I realized I needed a simulation of the 8 Queens Problem using Breadth First Search and Depth First Search. While there are many solutions on the Internet, I couldn’t find any program which lets me step through the algorithm. Besides, it had been a long time since  I did any programming in Windows.Forms so my code deprived fingers needed a sink.

8queens

So here’s my version of the 8 queens problem solver. Each board state is represented by a string. The string represent the columns starting from the left most column and the number in that position tells the row in which a queen is present.  The screenshot above thus represents the state 03142. The state 0314 would represent an empty column 4. You can download the compiled binary by clicking on the link below. I will try to upload the source once the assignment deadline has passed The source code is available for download below. Keep in mind that it’s hacky and badly written and should not be used in assignments. If you want a ready-made assignment, search elsewhere (or still better, drop out and do something you really love => ). It was developed in C# so you might have to install Microsoft .NET framework 3.5 to run this program. Comments/Suggestions/Bug Reports are welcome.

Download the 8 Queen Problem Solver     [ Code ]