Approximate if you can do it in polytime!

The main idea behind approximation algorithms is as follows. When one has to solve a problem which is proved to be NP-Complete, one has two choices.

1. Use usual algorithm and get answer in non-polynomial time (most of the times exponential) and be ready to wait until eternity OR
2. Compromise on the quality of answer but get things done faster

As suggested by 2 above, approximation algorithms have the same aim. Instead of finding the correct, optimal, best possible solution to the given problem, they try to find an approximated one; but they guarantee to find it in polynomial time so that they run faster. Now the question  is - even if they are faster, how much does the quality of solution degrades? This is measured by Approximation factor or Approximation ratio.  This factor or ratio basically captures how far we are from doing the best i.e. from the optimal. Consider the optimization in terms of minimization. Suppose a minimization problem is NP-Complete and suppose the optimal solution has the value 5; then if any proposed approximation algorithm, that is the algorithm that solves the problem correctly in polynomial time gives the solution whose value is 7.5 then we will say that we have got 1.5 times more than the optimal one; i.e. we are doing 1.5 times worse. So, here the approximation factor = approximation ratio = 7.5/5 = 1.5. Note that in case of minimization problem, if we call OPT as value of optimal solution and V as value of approximate solution then V >= OPT always; i.e. V can be equal or worse (here more, being minimization problem) than OPT and thus approximation ratio for minimization problem is always greater than or equal to 1. Similarly for maximization problem, V <= OPT and thus approximation ratio is always less than or equal to 1.

Thus, one comes up with an (approximation) algorithm A such that

• It solves the problem in polynomial time
• One can give proof of correctness for A
• It does not degrade the quality of solution too much; i.e. one can come up with the reasonable approximation ratio for A and can prove that for the general case

There exists many ways to come up with approximation algorithms and to prove that the have a reasonable approximation ratio. One such recipe is as follows.

• Suppose it is the maximization problem so that the value V <= OPT where V is the value for the solution returned by any approximation algorithm. So we have to come up with a ratio k s.t. V is at most k times worse than OPT.
• In order to prove that V is at most k times worse than OPT, we have to know what is OPT which is not possible because that itself will take non-polynomial time in general case.
• Suppose we know some number M such that the optimal solution has maximum cost of M then OPT <= M considering all possible cases.
• Thus, if we can prove that V is at most k times worse than M, it is guaranteed that V is at most k times worse than OPT as well. Because, given that V >= k*M and M >= OPT, we get V >= k*OPT
• For example, if the OPT is 100, and we know that M is 120. Then suppose V is 80 (the best we can achieve with approximation algorithm) then k = V / M = 80 / 120 = 2/3 meaning we can achieve 2/3 rd of the maximum possible solution value. We note that V / OPT is 80 / 100 = 4/5 which is always more than 2/3. Thus considering the upper bound M is enough.
• For minimization problem as we shall see below, we have to consider lower bound.

I came across a nice lecture by Prof. Abhiram Ranade (IIT Bombay). In this lecture, in addition to introducing the basics of approximation algorithms and defining above mentioned notions, Sir also illustrates the approximation algorithms designed for two of the NP-Complete problems. One of them (my favorite and the easier one :D) is briefly explained below.

(Note: I have tried to explain the problem and its approximation algorithm the way I understood it, so it is recommended to go through the original lecture by Ranade Sir)

Metric TSP (Traveling Salesperson Problem)

Input: A graph G with N cities, a matrix D giving distance between a pair of cities s.t. D is a metric.

A distance D measure is a metric if

1. D[i,i] = 0 for all i
2. D[i,j] = D[j,i] for all i,j (D is Symmetric)
3. D[i,j] <= D[i,k] + D[k,j] for all i, j and k (D follows Triangle Inequality)

Output: A cycle in G that goes through every city exactly once and has shortest length (in terms of distance values in D)

Recipe:

This will follow the recipe mentioned above. This being the minimization problem, we will come up with a lower bound. For the given graph G, suppose we know the optimal tour and we remove an edge from it. As the required output is the cycle containing all vertexes in G, the edge_removed_tour is the spanning path in G (spanning = containing all vertexes). Thus this is the spanning tree of G because it contains all vertexes and no cycle. Consider the minimum spanning tree T in G which has cost M. Now as any other spanning tree in G is as expensive as T so the spanning tree that we came up with, by removing an edge from the optimal tour can have length no less than that of MST, which we called as M. So, length of edge_removed_tour >= M.

As, length of (optimal) tour > length of edge_removed_tour (obvious), so we get

length of (optimal) tour >= M
Here, LHS is nothing but OPT and thus M is the lower bound on OPT.

So, we come up with an algorithm that has solution with value V no more than twice of M i.e. V <= 2 * M.

The algorithm and its correctness is described in the lecture.  The main idea used is triangle inequality property of D being a metric.

Precision-recall trade off ~ misclassification cost

While I was reading Pattern recognition and ML by Bishop, I realized a beautiful relationship between misclassification cost and precision recall. This might be well-known of course, but it's important for me as I myself realized it. :)

We know that precision-recall concept comes from Information retrieval kind-of a setting while misclassification cost comes from decision theory problems. In IR, given a set of true results i.e. T, and a set of retrieved results say R, precision is simply the fraction of true results in the set R. i.e. precision = #intersection(R,T) / #R. For example, suppose we know *all* the web pages that exist in the Web; then the set of pages which should be retrieved by a search engine are say T of size |T|. The search engine may retrieve a set R with size |R|. Then, if only 10 of these |R| pages are in T, then R's precision is 10 / |R|. Intuitively, R is more precise / exact if it has less not_required results. One may think of |R| >> |T| and that R contains all pages from T and many more extra results. Here, one says that R could "recall" everything in T but at the same time, it also made lots of mistakes. It is like, it took many trials on a puzzle and solved a puzzle 100 times correct while num_trials were 1000+. But in general if it could retrieve 10 pages which are in T, we say that it's recall is 10 / |T| i.e. out of |T| correct pages, it could retrieve 10. This also shows that there is a trade off between precision and recall because as num_trials increase, recall improves at the cost of precision.

Little off-topic but relevant: It's said that "practice makes man perfect". If we consider practice being making many trials, then as num_trials increase, due to practice one gets better results.

While I was reading the book, on page 41, I came across the misclassification cost involved in the decision theory. It says- We account for the misclassification cost because we don't want to miss on important predictions. Like in the example given for the two-class classification about whether a person is healthy or has cancer, it's important that we make no mistakes when the true class is "cancer-patient" as the consequences of these mistakes are dangerous. It also says that misclassification costs are such that we don't mind if a healthy person is predicted to be having cancer in order to not miss any patient which has cancer in reality. This is basically a trade-off between decisions. By this, we are looking for more recall even though we lose the precision.

Ph.D. info

Well, this is a collection of articles / write ups etc. which I found / got from friends while gathering information about Ph.D. Hope this will be useful for others.

You and your research - Must read

The Ph.D. experience - Again, a must read

Another nice talk

Inserting into mysql table from Java code

This post gives sample implementation of an interface which will insert records in a given table.

Assumptions:
1. mysql_connector driver is in build path
2. List of records is built off line.
3. Database connection is already made.

Procedure:
As shown in the snippet of code, the method takes 5 parameters, as mentioned in the comment.

/**
* @param tableName name of the table
* @param numValues number of values to insert < = num columns
* @param dataTypes their datatypes (string, int etc)
* @param columnNames column names to add values for
* @param values actual values in same sequence
*/
public void insertIntoDb(String tableName,
int numValues,
ArrayList_of_String dataTypes,
ArrayList_of_String columnNames,
ArrayList_of_ArrayList_of_String values) {

One you have a list of column names, you can easuly concatenate them to form a string say,

String col = "(col1, col2, col3)";

Similarly, for values, using numValues, you can easily form a string say,

String val = "(?, ?, ?)";

Once this is done, make a query string like:

String query = "insert into " + tableName + " " + col + " values " + val + ";";

This will form a quert string similar to following:

"insert into myTable (name, id) values (?, ?);"

Then, write a loop which will iterate through the given ArrayList of values (actual records) and using PreparedStatement interface, fill in the values for '?' in the query string. Here you will use dataTypes provided; for example, if the corresponding data type is "string", write:

cs.setString(index_of_corresponding_?, current);

else for "integer", write:

cs.setInt(index_of_corresponding_?, Integer.parseInt(current));

where "current" is the current piece of text that you can get from ArrayList of records i.e. values.

You can verify whether your final prepared statement is correctly built, using toString() method for PreparedStatement interface. It will show something like:

"objectID1: insert into myTable (name, id) values ('abc', 1);"
"objectID2: insert into myTable (name, id) values ('xyz', 2);"

Then invoke executeQuery() method of the interface PreparedStatement which will actually insert these records in the table.

Easy!! No? :)

Select k records randomly from n records in Java

Assume a situation wherein you have an array of records, let them be anything varying from marks (integers), names (string), student information (user defined class object), or ANYTHING ARBITRARY which derives itself from Java's object. Suppose, you have such n records, each with an identifier say, 1 to n, such that you have then stored in array of any form in Java.

Now, suppose you want to chose k random records from this array, this is how you proceed.

Procedure:
Given n, generate a random permutation of {1, 2, ... n} as {1', 2', ... , n'} and pick first k numbers from the permuted array.
For example, say you want to pick 3 numbers randomly from 8, s.t. n = 8, k = 3.
1. {1, ... 8} ===> {2,3,1,7,6,4,8,5} ===> {2,3,1}
2. {1, ... 8} ===> {8,4,3,1,6,5,7,2} ===> {8,4,3}
Thus, once you have k such indexes, you just need to probe your original array with these indexes and get corresponding k random records.

The Java code snippet is as shown:






The output as expected is :

randomly selecting 3 out of them
1 a
7 g
5 e
randomly selecting 5 out of them
6 f
5 e
7 g
8 h
2 b

I needed this for:
I had to partition dataset containing some @1,000 records, for cross-validation. It is a method of training a classifier when you have small number of training records. In this, you will first decide how many folds of dataset you want to make, say 5-fold, then 1,000 records will be partitioned in the ration 4 : 1 such that every time 4/5 th of the data records will be used for training and remaining 1/5 th for testing (validating in this case). Thus, I needed to randomly pick 4/5 * 1000 of my records every time, for which I wrote above piece of code.

Note 1: Not listing the code, but adding image so that, whoever wants to try it, will actually type in the things, and thus they will never forget the trick! :)
Note 2: Reference - Weka software

Snoring

During lunch, my friend was telling about her roommate and was laughing on the fact that she snores. I also snore. Obviously I felt bad. She was indirectly laughing at me. Since childhood I have been observing my father snoring and always thought of finding out the reasons behind the same. I thought now is the time because I myself is facing the same problem. Google-d for some information and this is just the compilation of what I found.
Last few months, I have realized that I snore. I happens sometimes during deep sleep, sometimes just after I go to bed. Most of the time its winter or my throat has some problem, whenever i snore. Normally it happens that I myself awake after some time I have been snoring and then I realize that I was snoring. I also noticed that whenever I am awake after snoring, I am sleeping on my back. I have never noticed myself getting awake due to snoring, when I am sleeping on my side. All this made sense after I read Google-d results.
Main reasons of snoring are:

1. Throat weakness causing the throat to close during sleep
2. Mispositioned jaw, often caused by tension in muscles
3. Fat gathering in and around the throat (tonsil problems, may be)
   
4. Obstruction in the nasal passageway
5. Obesity

A very good article about snoring, its reasons and treatments can be found at http://www.hinduonnet.com/thehindu/mag/2004/11/07/stories/2004110700350600.htm

The reasons numbered 1 and 2 ask for sleeping at the side to prevent the tongue from blocking the throat. Thats the reason I notice myself awake after snoring when I am sleeping on my back more than when I am sleeping on my side. Reason 4 might focus on the case that during winter I notice myself snoring. Reason 5 is directly applicable to me!
Reason 1, 2 and 5 are applicable to my father as well, who snores.

As known effects of snoring can be told as restlessness, hypertension (which may lead to heart-attack in very few cases), increased day time sleep, depression. (I go through almost all of these!)

A huge and useful information can also be found at my favorite wikipedia.. http://en.wikipedia.org/wiki/Snoring

As said in Hindu article, Snoring is no longer a laughing matter. It may lead to serious disease.

carbon trading

I had heard this term.. of course without knowing the meaning.. During "Applied Economics" (!!) lecture, Sir explained it.. As follows:

Lets assume for a certain area, air pollution restrictions are laid.. in a sense.. no factory should emit (say) 100 units of carbon (carbon- in a sense, pollution causing element). Lets say in that area, there are 2 companies A and B.. A's factory is controlling its emission to say 80 units of carbon.. Then they are given a sort of "carbon saver" certificate, indication of "they are carbon savers" That certificate is considered of having a value. Because, if suppose company B's factory is not able to control their emission to 100, say they emit 120 amount of carbon.. they can acquire (may be, actually BUY) this "carbon saver" certificate from company A!! sort of license.. to emit higher amount of carbon.. So that total level of carbon in that area is kept constant (120 + 80) as well as because company A has saved carbon, they are given reward while company B which could not save carbon, is - in a sense - penalized.

Cool information.. isn't it?