akrish

For those of you who don’t know, I just finished applying to grad schools and am currently in the process of deciding where I want to spend the next 4-n years of my like (where n >=4). I’m applying for a Ph. D. in computer science and my research interests are in Machine Learning and Computational Biology. During the whole process I got a lot of help from Philip Guo and Jean Yang, so I thought I would do a brain dump of my thoughts on the subject.

Naturally, a lot of this will be about me (for example this post will be about why I decided to go to grad school) but maybe some of that will be useful to you. To get some other data points about it, read what Philip and Jean have to say. Ok here we go…

In a nutshell, I’m going to grad school because I like to do research. I figured out that I like doing research by, well, doing research. As an undergrad I’ve been researching for a couple of years with David Wagner and I also got to spend some time working with Ron Shamir. Before starting to work with Professor Wagner, I really didn’t think I’d be interested in research, and honestly, I didn’t really know much about the academic environment and research at all. I was really excited about entrepreneurship and wanted to start a company, but one of my goals in college was to try a lot of different things, so I figured I’d give research a shot.

Another reason why I got involved in research in my sophomore year was that I didn’t like the internship I did the summer before. I worked for a fairly small company (~300 people) but I felt like I wasn’t doing anything important and I wasn’t really doing work that I found interesting. After my internship, I thought that maybe industry wasn’t for me, and the other natural thing to try was research.

So I got involved in research and discovered that I liked it for several reasons. (1) I get to work on really cool problems, (2) I get to think very hard about all sorts of possible solutions, and (3) I have the time to find and work with the best possible ones. Also, (4) I get to be (fairly) independent and (mostly) in charge of my work, and (5) I (for the most part) don’t have to do things that I don’t feel are important. In my internships, a lot of these factors weren’t there, although I do think that this may have been a product of my specific internships. I know people who do really exciting work at all sorts of companies, I just personally haven’t experienced that.

Given that I like research, the best place to go is graduate school. So by the end of my junior year, I knew that was what I wanted to do. I somewhat arbitrarily decided that I wanted to research in compbio and machine learning. A big factor in this decision was my summer research in computational biology. I got to design and implement really cool algorithms and I realized/discovered that there were tons of super-interesting problems in biology that could only be solved by computational methods. I got to read a ton of papers about these problems and found that often times there were elegant solutions to them. Moreover, I was part of a great group that involved me in their projects and told me about the awesome work they were doing. All of these things influenced my decision to go to grad school and helped me decide on computational biology as a research field.

I applied to many (9) schools. This is in many cases more than a lot of other people I’ve talked to. The two reasons for this were that (a) I didn’t have any existing job offers and (b) I didn’t think I would be happy in industry. I personally would have preferred to go to top-20 grad school over getting a job in industry, and this is reflected in the number of schools that I applied to. I know a lot of people who only apply to 2-4 schools and also look for real jobs.

And that’s basically it. After deciding to apply and where I would apply, the next steps were to get my applications together, write some essays, and wait to hear back.

My algorithms professor used to tell his students (including me) this story to motivate studying NP-complete problems and reductions. The story goes something like this: say you’re working as a software developer and your boss gives you this project where you need to come up with a efficient way to do some computation. You go to your desk and think about for awhile and then suspect that there is no efficient way to do the computation. So you can’t just go back to your boss and say, “I think this problem is NP-Hard, so I give up,” you need to show your boss that it’s NP-Hard and this motivates the studying of reductions. It further motivates the study of approximation algorithms and other techniques to cope with NP-Completeness.

I’ve heard this story a couple of times from my professor, but I never really felt like this is something that would happen. How often is it that you are given a problem that doesn’t look intractable immediately, and how much convincing will your boss really need? For that matter how often, in a typical job, do you encounter intractable problems? Like how often does this really happen at a typically development job? Now I haven’t spent too much time in industry and really in my time I never ran into NP-Hard problems so I don’t really know. Although the story was motivational for an algorithms course, the situation used to seem implausible to me. That is until I was challenged to do this myself

This summer, I’m working in a computational genomics lab refining some algorithms for analyzing gene expression data. The core problem we are working on is NP-Hard, but in my refinements, I ran into another NP-Hard problem that I did not immediately see as intractable. I guess this story may be a little bit skewed because I am basically doing algorithms research but I still thought it was pretty cool.

My work deals with finding connected components in a large gene network (an undirected graph). To simplify things, we have a scoring function and want to find connected components with good scores and because of the scoring function this turns out to be NP-Hard, read this for the exact problem and why it’s NP-Hard (The exact problem is a generalization of set cover). Anyway, the basic way we do this is to pick a vertex with a “good” score (called the “seed”) and then expand the module from that node.

In our experimentation, we decided to see what would happen if we allowed seeds to be multiple disconnected nodes and grew our modules from these multi-node seeds. Basically, here you choose k nodes to be your seed and you grow the module out from these seeds, but it is not a requirement that the result is a connected component, in this case it is ok if the resulting module consists of k connected components. The motivation was that from a biological perspective, a disease may affect two or more gene pathways and we wanted our algorithms to be able to account for that, hence allowing multiple connected components.

I set out to implement this feature and was thinking about ways to create these multi-node seeds. I started out by filtering away all of the “bad” vertices and was left with a set of 30-50 good vertices but it was (and still is) not clear what’s a good way to combine these single seeds into multi-node seeds.

My first approach was to simply enumerate all of the combinations and then choose the ones where the individual vertices had good scores. This approach besides having exponential time complexity was bad in that the seeds we selected were all very similar. This was because the individual nodes that were very good were in all of the multi-node seeds we selected. Thus this approach was not satisfactory. Another problem with this approach was that we typically did not see disjoint connected components in the resulting solutions.

To remedy the last problem, we decided on a new approach where we select multi-node seeds where each individual vertex is far from the rest. We compute this by looking at the neighborhoods (typically only 1 level of breadth first search) around each seed and computing the intersection of these neighborhoods. So this seemed like a good approach and we were hopeful this would produce disjoint connected components in the results so I set out to implement this.

Lets restate the problem: Given a set of vertices in a graph, where each vertex has an associated set of elements from some universe U. The goal is to find k vertices that minimizes the intersection of the sets, or such that the intersection of these sets is the empty set.

I thought about this problem for awhile and was quite confident that it was intractable. Before talking to the grad student I’m working with about it, I wanted to have at least a sketch of a reduction in mind. My first reaction was that I should be able to reduce set cover to this problem, possibly by “negating” all of the sets or something. I messed with this for awhile and I didn’t really get anywhere.

I mentioned this problem to some other people in my lab and we all thought about it for awhile. Eventually one guy found that he could reduce independent set to this problem quite easily. If you instead go back to the gene network graph and consider each of the “elements of the universe” as neighbors of the vertices in the graph, then you immediately see that this is the independent set problem. If you treat each neighborhood as a node in a graph, and there is a edge between two neighborhoods if they share an element in common, then you can solve this problem by running an independent set solver on this graph. Conversely, given a graph, you can define a universe of elements and a set to each vertex such that vertices that are not connected share no elements and vertices that are connected share some elements. Then you can look for multi-node seeds and solve independent set. The way I explained the problem above, and the way that I thought about it made it difficult to see that it was independent set, but if you go back to the original problem, it’s easier to see.

Now that I new the problem was NP-Hard, I started thinking about ways to get good enough multi-node seeds and eventually settled on a greedy algorithm that grows the seed sets by adding the node with minimal intersection. The resulting seeds are decent and we did start seeing solutions with multiple disjoint components which is exactly what we were looking for. Despite being faced with a “challenging” problem, we did end up finding a good working solution that gave us the results that we wanted.

This little anecdote, although quite silly in retrospect (because the reduction was pretty straightforward), really showed me that what I learned about reductions and NP-Completeness is important from a practical perspective. It also showed me that my professors story was actually quite plausible. Plus it was another situation where I got to apply things that I learned, and I always find that really cool.

I’m continuing to learn Haskell in my free time and as I like to learn by doing, I’ve been implementing common algorithms in the language. Last week I tackled depth first search and found it to be surprisingly challenging and consequently really educational. Today, I decided to try my hand at dynamic programming. I chose dynamic programming because these algorithms hinge on memoization, and I wanted to figure out how to do that in a purely functional way. Also, I thought that I could do some performance analysis, as implementing recursive, un-memoized algorithms to solve these problems seemed to be quite easy.

The first algorithm I tried to implement was the standard edit distance algorithm. It’s a classic DP algorithm and although no longer used much in practice, it is the basis for several modern techniques used in sequence alignment, so I figured it would be an interesting exercise. I spent an hour or so thinking about how to approach this and even started programming a solution, but I quickly got bogged down in maintaining a matrix of subproblem solutions. I found implementing all of these matrix operations to be quite mundane and decided to start with something a bit less tedious.

So I chose another classic DP problem, Longest Increasing Subsequence. Briefly, the problem formulation is: Given a list of (lets say) positive, unique integers, find the length of the longest subsequence such that the subsequence is strictly increasing. For example, given [1, 4, 2, 3, 9], the longest increasing subsequence would be [1, 2, 3, 9]. Read the wikipedia article for more details. I chose this problem because you don’t have to maintain a matrix of subproblem solutions, but rather a list, and the problem is quite a bit simpler, allowing me to focus on the algorithmic elements.

So, I started out by implementing a naive un-memoized algorithm, then went on to implement the dynamic programming algorithm that’s based on the one on the wikipedia page, but in Haskell it doesn’t really look the same at all. I implemented both so that I could do run some performance metrics which I’ll discuss about after presenting my code. First some auxiliary stuff:

I admit I should have used arrays for this but I kind of started using lists before having to implement these and was too lazy to change it. I would change it now but I’m worried about breaking things right before posting and since I’m probably (read definitely) never going to look at this again it really doesn’t matter to me.

Anyway, so we have three functions that are all pretty straightforward. One essentially treats a list as an array and gets the i-th element from the array. Another does the reverse, it gets the index of an item in the array. Finally the third computes the max over a list.

My first algorithm is a naive approach that is just recursive with no memoization:

Ok so longestIncreasingSubsequence is a bit confusing and the comment is kind of inaccurate. If you call it with i == 0, then it’ll return a list where each j-th element is the value of the longest increasing subsequence that starts from and contains the jth item of lst. It basically computes the solution to all of the subproblems, but it doesn’t compute them by memoization. It’s similar if you start with i != 0 but the list only has a suffix of the subproblems. It computes these results by following the standard recursive formula: look at each j>i such that l[i]

This was a good exercise but not really what I wanted to do. So I tested that a bit and made sure it was correct, and proceeded to think about the dynamic programming algorithm. I found it a bit difficult to actually memoize the solutions, but here's what I came up with:

So I hope the functions make sense. dplis just does lookups in the array parameter to compute the longest increasing subsequence starting at and including i. getDPScores builds the array of subproblem solutions, starting from the smallest subproblems and relying on dplis. Finally lis is just a wrapper for calling getDPScores with the right parameters.

One noteworthy thing is the flow of the program. It’s tail recursive. So the first thing we do is get to the bottom of the recursion of getDPScores, then we really do our computation as we work our way out of that recursion stack. Each call to getDPScores after returning from recursion still has to call dplis. Of course there are a lot of tail recursive algorithm, but I didn’t really expect dynamic programming to naturally flow like this. Typically dynamic programming is done iteratively, but I suppose we can’t do that here.

So those are my two implementation, now on to performance stuff. I decided to experiment with this just to see how amazing dynamic programming really is. If you notice the first algorithm I implemented is definitely exponential (in the worst case, imagine a ascending list of length n, then each call has to spawn O(n) smaller calls). I think it’s O(n^n) but I haven’t thought too much about it so please correct me if I’m wrong. Anyway, the second algorithm is O(n^2), you just recurse straight down and pop all the way back up. At each recursive call you may have to look at O(n) neighbors and there are only n recursive calls.

Given the asymptotic running times, I expect the second algorithm to be far superior to the first in actual running time. Just for fun I decided to run this experiment and plot my results. I generated random lists of sizes ranging from 5 to 70 in increments of 5 and ran each algorithm on the same lists. Here are the results:

exponential vs quadratic times

They are pretty much what I expected. Notice that the y axis is log-scaled, so that for input length 70, the exponential algorithm took around 10 minutes (600 seconds) where the dynamic programming one takes well under a second. Really amazing how dynamic programming helps that much. I had originally intended to run on larger input sizes but I simply couldn’t as the exponential algorithm wouldn’t terminate.

As I did in my last Haskell post, I did a quick search for other people who had looked at dynamic programming in Haskell. I found this article which walks through an implementation of the knapsack algorithm and it appears to be much more elegant than mine. Of course you should remember that this I’m still a Haskell newbie so I don’t have mastery over most of the features and I really don’t expect myself to be able to implement elegant solutions. However, he does mention that dynamic programming is quite natural in functional languages and that you can take advantage of lazy evaluation, which I can understand. Also the knapsack algorithm uses a matrix of subproblems, so it’s slightly different and more interesting.

I also found this article that implements the Needleman/Wunsch algorithm for global sequence alignment, another classic dynamic programming algorithm. This was also an interesting read, and he used some language features that I haven’t used and barely knew existed so it was definitely educational. Also, this algorithm also uses a matrix of subproblem solutions so I’m thinking that my next experiment will be with more one of these dynamic programming algorithms.

So, In conclusion, I’m feeling more confident in my functional thinking and my Haskell programming. In my previous post, Jedai commented that I shouldn’t consider arrays as cheating, and so I have adopted them into my repertoire here. Further, as proof of the importance of algorithm design and asymptotic efficiency, I generated some performance numbers to show how essential it is to have efficient algorithms.

Anyway… there’s a leak in my ceiling and water is dripping all over the place so, until next time!

A couple of months ago, I suddenly had this desire to learn Haskell. I was working on my compilers project (obviously) and randomly thought it would be cool to know and use a purely functional language for whatever reason. Plus, I’ve been reading about Haskell a bit on blogs and stuff and one of my friends uses it pretty regularly so I figured I’d give it a shot.

Why learn Haskell? I’m not sure if I’d ever really need to use it, but of course I may have a job where I program in a purely functional language and then it would certainly help. But more importantly, I wanted to challenging myself to thinking in a new way, and of course it’s good to have another tool in our tool belt. For more general reasons to learn Haskell, check this out.

Anyway, about 2 months ago, I went to the Haskell website, downloaded GHC and started reading this as a tutorial. I knew some of the basic stuff, like that Haskell is purely functional and whatnot but that’s a good document to read to learn about some of the design decisions and of course it serves as a tutorial. I didn’t get very far in the tutorial due to school and other responsibilities

That was 2 months ago. Last night, I decided to re-start my foray into Haskell and went through several chapters of the tutorial. I’m not done with it, but I hate learning by reading and decided that I’d learn by doing. So I set out to implement some “simple” algorithms in Haskell and see how/why they are different from the traditional implementations. Now of course my code isn’t the best written Haskell (because I’ve been writing for less than a day), and I’m pretty sure there are better ways to implement these algorithms, but it was definitely a good learning experience.

Note: I didn’t want to use some of the more advanced Haskell features like monads largely because I don’t really understand them yet, and also because I wanted to keep my algorithms really pure and functional. I don’t yet buy that monads are within the rules of haskell’s purely functional-ness, but I’m sure I’ll understand that later on.

One of the algorithms I especially struggled with was Depth First Graph Search. At first, I didn’t expect it to be very challenging because DFS is naturally recursive and that’s pretty much the common way to write algorithms in Haskell anyway. So I started out with some data type definitions and some functions to manipulate the data.

So hopefully that is relatively straightforward. My basic graph structure is a list of Nodes, and each Node is a just a tuple containing an index and a list of neighboring node indices. And how concise is that makeNode function… I love it! There’s also a function to make a graph out of a list of edges, and it basically just calls makeNode a bunch of times.

Ok then my first approach was to try and implement a standard DFS. It looked something like this:

So yes this is unnecessarily complicated, (you don’t need the last map because depthFirstSearch takes integers anyway. It’s like applying a function, then applying the inverse right away.) However, the whole routine is wrong and I introduced the complication as I thought about how to fix it. It’s wrong because in a nested call to depthFirstSearch you have no idea what nodes you’ve visited. And using this approach, at best you can know the nodes that are on the path from the current node to the root, but you cannot know about the other nodes that you’ve already visited.

For example, supposed I have edges = (1, 2), (1, 3), (2, 3) and I call depthFirstSearch (makeGraph 3 edges) 1. What happens? Well, we “visit” node one, and then call depthFirstSearch (makeGraph 3 edges) 2. This obviously calls depthFirstSearch (makeGraph 3 edges) 1 and so on ad infinitum.

Ok so we can quickly fix this infinite recursion problem. By removing the current node from the graph before we recurse. But this still doesn’t fix all of our problems. Now while visiting node 2, we recurse to node 3, then we back up to node 1 and visit node 3 again. At the top level, we have know way of knowing that we already visited node 3 earlier.

So if we’re doing tree search, the above algorithm (with the “remove current node” adjustment) should work. Actually there are some minor adjustments: Here’s my final Depth First Search for Tree Search:

So a good detour but not really what I was after. Figuring out how to get DFS graph-search to work wasn’t trivial for me. After a couple of hours here’s what I came up with:

So, let’s look quickly at how this works. Basically, depthFirstSearch immediately calls dfsIterateOverNeighbors (which is probably not well named but whatever) and this function does some magic. Actually, all it really does is maintain a stack of nodes to visit, and visit them in stack order. Each time you visit a node, you also remove it from the graph for subsequent “iterations” to know that you’ve visited the node. Finally, I’m careful about what nodes get put on the stack, not allowing nodes that I’ve visited already and cleaning up the backside of the stack with nodes that I figured out I’ll visit sooner than I had previously thought.

So, in thinking about this. I realize this is basically an iterative DFS algorithm. A lot of “state” is maintained as function arguments, and the whole thing works tail-recursively. You do a bunch of work, then tell the next guy to do some stuff, which seems a lot like imperative programming. But it is pretty interesting that to make a “simple” recursive algorithm work in a functional setting, I essentially made it more imperative.

So I was relatively happy with this solution and decided to check my answers. I looked at what other people have done online and found a couple of interesting things. Most notable was this paper that uses mutable Arrays to implement Depth First Search in linear time. However, immutable arrays are “cheating” by my standard so these guys don’t have a solution to my problem.

I also ran across this thread that is loosely related. Actually I only really found the first two posts related but essentially it seems that it is quite challenging to implement DFS in linear time without using some mutable state. In looking at my algorithm, I’m pretty sure it’s quadratic (O(|V| calls to dfsIterateOverNeighbors and in each call you have to walk across toVisit which is also O(|V|)). However, I could not find a “better” way to implement Depth First Search under my somewhat arbitrary restrictions.

In conclusion, my first experience with Haskell was kind of cool, I had to think really hard about something that is usually pretty trivial but I did come up with a decent solution and learned a bunch of language features along the way. I think I will keep trying to implement various algorithms in Haskell whenever I get free time and maybe I’ll write about it too.

With my senior year of college looming forbodingly on the horizon, I realized that I’m almost at that point where I have to make one of the biggest decisions of my life: I need to decide what I’m going to do after I graduate.

If I were Israeli this wouldn’t be a problem yet. I’d just be getting out the army, I’d go travel for a year or two, then I’d have to make the decision as I prepare to start college. Of course I only know this because I’m here, and
everyone around me is starting their undergrad at the ripe, young age of 22. I wish I could procrastinate it for at least a year longer.

Alas, this is probably not possible. I’ve procrastinated for too long already. However, this is not a lost cause. I’ve made huge strides in deciding that I want to pursue a Ph.D. in computer science, which I guess I decided sometime during this last school year. To read about why I want to pursue research, read this. There are still many questions to be answered, the most important of which is: What area of computer science do I want to devote the next 4-6 years (and possibly the rest) of my life to?

For some people this isn’t a challenge at all. Some people take a class, love it, start research in that area and that’s it. Sometimes, I wish I were like those people, but things didn’t work like that for me. I’ve really enjoyed almost all of the computer science class I’ve taken, and although I’ve only done research in a couple of areas, I can see myself doing research on a variety of different topics. I really enjoy reading about the research being conducted in areas as broad as operating systems, distributed computing, databases, programming languages, algorithms, theory of computation, security, network security, artificial intelligence, machine learning, and computational biology.

Aside: Actually, I’ve know about this problem for a long time. Whenever some asks me what I’m interested in I generally say “almost everything.” Most people think this is a good thing and I for the most part agree. It’s only if you plan on devoting yourself to one specific area, that it becomes “bad.”

That by the way is a list of candidate fields that I’m considering. There are two observations from this list: the first is that many of the areas are quite related. Like operating systems, distributed computing, and databases are “similar” in that they are often lumped together under the term “systems.” Same with algorithms and theory of computation and of course AI, ML, and Bioinformatics are very closely related. The second observation is that I could work on two of these things. For example, one of my current research projects would probably be classified under programming language security. This is a definite possibility, and something that I currently feel will probably end up happening.

On sort of another related side note: It doesn’t really matter what decision I have to make soon, it’s more of the fact that I HAVE to make a decision soon. Seriously, I’m not even 21 yet. How am I supposed to know what I want to do with my life? This is one of the things that really scares me about graduating (and there are many, many more, but living on my own in Israel is really preparing me to face some of them, and making things a lot less scary in general).

So how do I deal with it? How do I decide what to do in grad school, in my limited time frame of say 3 months?

My research experience has been largely in security, and I’ve been working in bioinformatics for 3 weeks now (oh my god only six more weeks in israel!). I really like both areas, so even between these two it’s very hard to decide. It’s
not something I can directly compare because my experience in each area has been very different. Even with experience, I can’t tell which one I like better, so who’s to say that I won’t like some other area that I haven’t tried equally or more? I don’t have time to get a feel for research in every thing I’m interested in.

So I’ve been stressing out about this for the past week or so, since my parents kindly reminded me that I need to start thinking about grad school. In my opinion, the next best thing to actually conducting research is to read about research, so I’ve compiled lists of papers for each area that I plan to read over the next couple of weeks. It’s going to be a lot of reading but from what I’ve already done I think it will really help me make this decision.