EPD Python on Ubuntu

Enthought Python Distribution or EPD as it is popularly known as is a Python distribution with lot of libraries already available in it. Whats good about it? The libraries are in their latests version available (or may be one or two versions lower). Ubuntu repositories also have these libraries so one can install them from there. But, the problem with Ubuntu repositories is that they contain pretty old versions of the library. For example the current version of Networkx available in Natty repositories is 1.1 while that current stable version of Networkx is 1.5.

EPD is installed using the shell script installer enthought provides. I have installed it in the home directory. So by typing ‘python’ in terminal I do not have access to EPD python. What I did is the following – I made a link named it ‘pythoEPD’ and copies the link to ‘/usr/bin’. This way I will be able to access EPD python from anywhere on terminal by typing ‘pythonEPD’.

Although EPD has a good collection of libraries it might not have all that you need. I have not been very successful in installing downloaded libraries to the EPD library list. So it will be good to install them from ubuntu repositories using the awesome ‘apt-get’ command. But, these will not be available to EPD python. To make them available to the EPD python distribution one needs to add the standard python path to the EPD python path. To do that open terminal.

  1. Run python by typing – python.
  2. import sys; sys.path
  3. The above command will show you the standard python path. copy the entire list to clipboard.
  4. Open another terminal run – pythonEPD (to run EPD python).
  5. paste the list to a variable, say x.
  6. iterate over its entries and append it to the EPD python path.

Wikipedia’s Participation Challenge

On June 28, ICDM 2011 announced the ICDM contest for this year. The contest is called the “Wikipedia’s Participation Challenge“, the cometition details are available at kaggle. The aim of the project is to predict the number of edits a user will make in a 5 month period.

I have downloaded the dataset. This will be my first experience with a dataset this large and machine learning algorithms in practice.  Lets see how it goes.

List of data sets

Here I will keep a list of various datasets that are available to public for research in machine learning and related areas.

  1. Movielens dataset:  This is a movies rating dataset.
  2. Yahoo! Music: This is music rating dataset.
  3. Heritage Health Prize: The goal of the prize is to develop a predictive algorithm that can identify patients who will be admitted to the hospital within the next year, using historical claims data.

Above I have just mentioned a few data sets. A lot of data sets are available from the website infochimps. Kaggle is one website dedicated to host large dataset competitions.

Ralink rt5390 wi-fi driver on ubuntu 11.04

UPDATE (7-Feb-2012): Marko has created a PPA for the Ralink drivers. I should make our live much easier. Take a look at his blog (http://www.techytalk.info/ralink-wireless/).

I have HP pavilion dm1z laptop and it took me quite some time to install the linux wi-fi driver on ubuntu. In this post I tell how to install the Ralink’s RT5390 wi-fi driver on Ubuntu Natty Narwhal. The main source of the post is Ubuntu forums. So here it goes.

  1. Download the linux driver (RT5390PCIe) from Ralink.
  2. Extract it.  The files will be extracted to 2010_1216_RT5390_LinuxSTA_V2.4.0.4_WiFiBTCombo_DPO folder.
  3. Download all the patches except the x64_86 patch, assuming you have a 32-bit system, from opensuse website.
  4. Copy the patches to the folder – 2010_1216_RT5390_LinuxSTA_V2.4.0.4_WiFiBTCombo_DPO
  5. Goto the folder.
  6. Make the following change in  /os/linux/config.mk file – HAS_ANTENNA_DIVERSITY_SUPPORT=y (originally was n)
  7. Now run the following commands in terminal:
    patch -p0 < rt5390sta-
    patch -p0 < rt5390sta-
    patch -p0 < rt5390sta-
    patch -p0 < rt5390sta-
    patch -p0 < rt5390sta-
    patch -p0 < rt5390sta-
    sudo su
    cp RT2860STA.dat RT5390STA.dat
    mkdir -p /etc/Wireless/RT5390STA
    cp RT5390STA.dat /etc/Wireless/RT5390STA
    make clean
    make install
    modprobe rt5390sta

Link to the original posts on ubuntu forum: Points 3 and 7 are from Chilli555’s post #24, while others are from Akshay’s post.

UPDATE: It has been pointed out by Weldon in the comment section that the above method does not work for Kernels >=2.6.39. To know your kernel version you can type the following in terminal:
uname -r

UPDATE (5-Aug-2011):

  1. kpbotbot has confirmed that he can run wireless on kernel >=2.6.39 using an arch Linux fix available here.
  2. Ralink has changed the driver available. I old driver can got from here.
  3. The opensuse link above now points to new set patches. The old ones can be downloaded from here. You can try using the new version but I have not used it so cannot say much about it.

UPDATE (2-Sep-2011):

  1. kpbobot has pointed out in the comment section that the drivers are already a part of Linux 3.x kernel.


100km Cycling Day

Cycling in Mumbai is a pain in the ass because of the traffic. We generally go for cycling early in the morning. Although, there have been times when I have gone for cycling in the afternoons. 6:00 am is the preferred time. We are kind of limited by the number of routes here in south mumbai and wanted to try some new longer routes. Thats when we decided to cycle all the way to Kashid. I wanted it to be a 2 day trip but others (Gugan and Rakesh) wanted to comeback on the same day. I was not very sure if I would be able to finish both the trips on the same day. We decided to come back on the same day.

The cycling trip to Kashid happened on 9-Apr-2011. We were suppose to get up early in the morning so that we take the first boat from Gateway of India to Mandwa. Gugan did not get up at the right time. In fact I went to his room in the morning at 6:00 to wake him up. Clearly we had missed the first boat. Both Rakesh and I waited for him downstairs. We reached Gateway of India at around 6:45. We took the 7:00 am boat to Mandwa. We had got three tickets for ourselves and were suppose to pay for the bikes on the boat. It took more than and hour to reach Mandwa. Once there we planned to have breakfast. We had idlis and wada pav.

At 9:00am we started from Mandwa port. We were to go to Kashid via Alibagh, Nagaon and Revdanda. Right at the beginning there was a bit of a climb. And there itself I was wondering if I will be able to finish even one side of the trip or not? We went on. I cycled slower than Gugan and Rakesh. They reached Alibagh (about 17km from Mandwa) some 10 mins before me. They waited there for me but as soon I reached there I ate some biscuits and then they started to move on. I had hardly got some rest. I also started with them there was no point in waiting. Some 3km from Alibagh we are suppose to take a right turn. Gugan and Rakesh missed it. I asked directions to a policeman at the junction, he told me that two guys before me went straight. I called them and they came back. I waited for them at the junction (this was my resting time). Then we moved on. After cycling for a few kilometers that road became bumpy. Although all of us had firefox mountain bikes it was not of much help there. Also the there were a lot of turns at short distances. The others were ahead of me. My hands started to become numb. If fact the tip of my fingers are still numb. But we went on. After Revdanda not only did the trip became more scenic but it also introduces many climbs. We were now cycling on the hills. By this time I was quite exhausted and every kilometer seemed much longer. I was told by some of the people on the way that the climb just before Kashid is pretty long. Every climb I can to I hoped that it was the last climb. At last when it did come I cycled for a while and after that was not able to pull so I got down from the bike and started walking. After a while I saw Gugan resting under a tree. He was exhausted too. We had some energy drinks there. After a while started again. We soon came to a steep downhill slope which brought us back to the sea level and we were at Kashid.

It was a very clean and beautiful beach. The first thing we did was to look for Rakesh who had reached before us. My cell phone was not working as there was no airtel network in Kashid. But we managed to find Rakesh. He was happily having kanda poha on a hammock. We were hungry too and ordered some poha. It was the best poha I had ever eaten (I do not like poha). Then we were off to the water. We went on the banana flip ride. It was great.

After two hours at the beach we ready to go back as the last ferry to Gateway was at 7:00pm. I started first while the others setteled the bills of what we had eaten at the beach. I was happy to go downhill on the long stretch we had to climb while coming. It was pretty hot and sunny now. It was very tiring. My hands were getting numb, neck and buttocks were paining. Some how I managed to reach the port in time. We had vada pav, cold drinks and peda that Rakesh had bought from Alibaugh. We tooks the boat and reached Gateway by 8:00pm. After that we were in no mood to mount on the bikes for the last 3 to 4 km to reach TIFR.

Change of line

I have recently changed my area of research. Till now I have been working in Quantum information theory but, now I will be working in machine learning.

The books that I am reading now are:

  1. Pattern Recognition and Machine Learning – Bishop
  2. The Elements of Statistical Learning – Hastie, Tibshirani, Friedman

Save Paper

I have printer which allows duplex printing. But, I forgot to enable duplex printing and a lot of paper was wasted today. I plan to write a program that will prevent you from doing the mistake. It will warn you from printing one side if your printer supports both side printing.

The problem is I do not know how to go about it. Hence, I have posted a question on stackoverflow.

Impossibility of Quantum Bit Commitment

I learnt about the quantum bit commitment protocol today and found it very interesting and it will be the subject of this post.

The Situation: Alice and Bob (a very influential person) like to bet on the outcome of a cricket match between India and Pakistan. Alice would like to place the bet on one of the outcomes:

  1. India wins
  2. India loses

If she wins Bob has to pay her a certain amount of money. She does not want Bob to know on what outcome she has placed the bet, as being an influential person Bob can affect the result of the match in his favour. Bob wants that she should not be able to change the bet once she has placed it.

We will now see how we can achieve the above conditions in a quantum setting. We will be using an electron spin for placing the bet.

The protocol:

  1. Alice takes an electron in the state {|\psi\rangle}.
  2. She does the following:
    • If she wants to place the bet that India wins then she will measure her system with the observable {\sigma_z}.\displaystyle \sigma_{z}=\left( \begin{array}{cc} 1 & 0\\ 0 & -1 \end{array} \right);
      \displaystyle |\psi_{-z}\rangle=\left( \begin{array}{c} 0\\ 1 \end{array} \right) ,
      \displaystyle |\psi_{z}\rangle=\left( \begin{array}{c} 1\\ 0 \end{array} \right)
    • If she wants to place the bet that India loses then she will measure her system with the observable {\sigma_x}.\displaystyle \sigma_{x}=\left( \begin{array} {cc} 0 & 1 \\ 1 & 0 \end{array} \right)
      \displaystyle |\psi_{x}\rangle=\frac{1}{\sqrt{2}}\left( \begin{array}{c} 1\\ 1 \end{array} \right)
      \displaystyle |\psi_{-x}\rangle=\frac{1}{\sqrt{2}}\left( \begin{array}{c} 1\\ -1 \end{array} \right)
  3. She notes the outcome of her measurement and then gives the resultant qubit to Bob.
  4. After the match she announces the outcome of her measurement and what observable she had used to do the measurement.
  5. Bob performs the measurement with the same observable if he gets the same result as Alice then she is telling the truth.

Why it works:

  1. In the first case when Alice measures the system with {\sigma_z} the resulting state of the qubit will be {\frac{1}{2}|\psi_z\rangle \langle\psi_z| + \frac{1}{2}|\psi_{-z}\rangle \langle \psi_{-z}|}.
  2. In the case when Alice measures the system with {\sigma_x} the resulting state of the qubit will be {\frac{1}{2}|\psi_x\rangle \langle\psi_x| + \frac{1}{2}|\psi_{-x}\rangle \langle \psi_{-x}|}.We see that in both cases when Bob has not been told the result of the measurement, the qubit is in the same mixed state {\frac{I}{2}}. Bob has no way of knowing how it was prepared. We have now made sure that Bob has not way of doing any cheating.
  3. Lets see what will happen if Alice tries to cheat. If Alice tries to cheat she will have to tell that she measured with the other observable and will have to give a random outcome of the measurement. There is 50{\%} chance that Bob also gets the same output when he measures. To reduce this probability we can start with many copies of {|\psi\rangle}. Alice is suppose to measure all of them with the same observable and then send them to Bob. The rest of the protocol remains the same. By doing this we will have reduced the probability of Alice winning by cheating very very small. Any outcome which does not match to what Alice says will mean that she has cheated.

It looks like that we are done. Have we achieved a perfect bit commitment protocol? The answer is no. We have made an assumption that the only way Alice can affect the qubit is when she has it. Is it possible that she can in some way affect the qubit with a remote of some sort? Yes, it is possible by using entangled qubits.

Lets see how it is possible. Suppose Alice prepares all the qubits in the following state {\frac{1}{2}(|00\rangle + |11\rangle)}. She gives one of the qubits to Bob. Bob, now holds a qubit which for him is in the state \frac{I}{2}. But, since she will have the other entangled qubit she will be the able to change the state of the qubit with Bob by measuring her qubit.

Quantum Computing Measurement Postulate

Quantum computation and information is based on the postulates of Quantum Mechanics. They are:

  1. State: Each state is represented by a unit vector in a Hilbert space.
  2. Evolutions: The state evolves only by unitary matrices.
  3. Measurement Postulate: Quantum measurements are described by a collection {\{M_m\}} of measurement operators. These are operators acting on the state space of the system being measured.The measurement operators satisfy the completeness eqaution, i.e.,

    \displaystyle \sum_m M_m^\dagger M_m=I.

    The index {m} in {\{M_m\}} refers to the measurement outcome that may occur in the experiment. If {|\psi \rangle} is the state then the probability of outcome {m} is given by

    \displaystyle p(m)=\langle \psi|M_m^\dagger M_m|\psi\rangle.

    The state of after the measurement is given by

    \displaystyle \frac{M_m|\psi\rangle}{\sqrt{\langle \psi|M_m^\dagger M_m|\psi\rangle}}.

Let us take an example here. Let {|\psi \rangle} represent the following picture.

Handwritten 'S'

Now, we want to perfrom an experiment to determine what the picture represents. So, first we need to decide what measurement operators (i.e. to decide what type of output we want) to use. If we think that {|\psi \rangle} is a digit then we might want to use the measurement operators say, {\{N_n\}}, that gives an output from the following set: \{0, 1, 2, 3, … ,9\}. If we think that {|\psi \rangle} is an English alphabet then we use measurement operators say, {\{L_l\}}, that gives an output from the following set:\{a, b, c,…,z\}. The thing to note here is that we can two different set of operators to measure a quantum state, and based on the operators used the results might be different. If we use the former set of operators we are most likely to get the result {\mathbf{5}}. Instead, if we used the set of operators which produces the result in the alphabet we are most likely to the output {\mathbf{S}}. Until now everything looks good, we wanted to find out what the image represented and we can do it using the set of operators described above. This is exactly what an Optical Character Recognition (OCR) system would have done then what’s the difference?

Well, from here onwards the quantum system would behave differently, in the classical system the picture would remain the same but if the picture were really described by a quantum state, {|\psi\rangle}, it will change to some other state {|\phi\rangle}, say. Consider the set of operators {\{N_n\}}. If we think of 0, 1, .., 9 to be orthogonal vectors, then the operators can be the projectors on the respective spaces. In this case if we performed a measurement using {\{N_n\}} and the output was {\mathbf{5}} then resulting vector {|\phi\rangle} will lie in the subspace of {\mathbf{5}}.

On Channel Capacity

In this post I will discuss about channel capacity. The question I am going to address here is at what rate can data be transmitted through a channel. Channel is defined as a probability map {P_{Y|X}(y|x)}. That is given an input with what probability can it produce different output. Here, X is our input and Y is the output of the channel. Let us take an example.

The Noisy Typewriter: Let us take this funny typewriter which behaves in the following manner. When you press the key A it might write a letter A on the paper with probability 1/2 or it might write B with probability 1/2. When you press the key B it might write a letter B on the paper with probability 1/2 or it might write C with probability 1/2, and so on for each of the letters as shown in the figure below (for Z it will write letter A with probability 1/2).

Consider the following problem: Alice wants to send a message to Bob (who has the knowledge of the channel characteristics, i.e. {P_{Y|X}(y|x)}). Alice types the message on a sheet of paper using the funny typewriter described above. Bob is now given the sheet of paper on which the message was typed. Can he determine what letters were typed to produce the message? Clearly, if Alice used all the 26 keys to write the message, then, Bob cannot determine what key strokes (input) produced the result on the paper. For example, if the alphabet on the paper is ‘B’ then it could have been created by typing an ‘A’ or ‘B’. We now ask the following question: Is there a way in which Alice can use this typewriter in such a manner that Bob can determine the message that was typed without any error? What if, Alice now restricts to typing a message using the letters in the following set {\chi = \{A, C, E, . . . ., Y\}}. If Bob is given a message produced from the keys in the set {\chi} then he can tell which keys were used to produce the message, as, now each output symbol is mapped to a single input. The same is true for the set {\chi^{c}=\{B, D, ... , Z\}}. By restricting the set of input characters, Alice has made the set of outputs disjoint. That is its only letter A that can cause the output A and B (see the above figure). No other letter when typed from the set {\chi} can cause these outputs.

In ‘information theory’ information is generally represented in bits. 13 alphabets can be represented by {log_{2}13} bits. As bits representing the letters from the set {\chi} can be sent without error in decoding the message. We say that Alice can communicate with Bob at a rate {log_{2}13} bits per second (bps). Shannon answered this question in his paper – “A mathematical Theory of Communication”.

Let us look at the problem in a more general setting. Alice wants to send some message to Bob.

  1. Alice uses the input alphabet {\mathcal{X}}.
  2. Bob receives the output from the output alphabet {\mathcal{Y}}.
  3. Both Alice and Bob know about the channel charecteristics.

At what rate can Alice send information to Bob so that Bob can decode the message without any error. For devising such a coding scheme Alice now has to use those set of codewords (strings of the alphabet {\mathcal{X}}) so that Bob can map back each output that he gets to one single input. This means the rate at which Alice can transmit information is {log_{2}C}. Here, {C} is the number of codewords that Alice can create from alphabet {\mathcal{X}} so that the output which Bob gets are disjoint for all codewords.