Absolutely No Machete Juggling

Rod Hilton's rants about stuff he cares about way too much...

PhD Status Report

It's been a long time since I posted about how school is going, and I figured the folks who read my blog (all two of you, hi Mom!) might be curious.

Since the end of my Spring 2013 semester, I've been in "Research Phase". This means I'm finished with classwork and have been working on my research project. It's been a little over two years now, so here's what has happened.

Picking a Project

About two years ago, I started working with my advisor trying to figure out what area my research would be in. I've always had a fascination with Genetic Algorithms and Metaheuristics, so I knew I wanted to do something involving that subfield. Two of my projects at school utilized Genetic Algorithms, and I had a lot of experience in the area.

I went back to school to primarily focus on CS Theory & Algorithms, but I knew my biggest strength was Software Engineering. In other words, I like theory, but I'm not sure I'm a real theoretician, and I wanted to play to my strengths a bit. This meant I wanted to be writing real, working code, rather than proofs. If I wound up proving anything interesting, that'd be great, but I didn't want that to be part of my critical path to completing my PhD. Lots of CS PhD's go off with a white board and paper and output some amazing results, but I knew that wasn't going to be me.

My first idea was to build some kind of framework for comparing different metaheuristics. I've worked extensively with Genetic Algorithms but that's just one of an entire class of Metaheuristics. I had no experience with things like Swarm algorithms, Ant Colony System optimization, Tabu search, Simulated Anealing, and so on. I thought it would be interesting to pick some known optimization problems like Traveling Salesman using TSPLIB, code various 'solvers' using different techniques, and compare their performances.

I started building out the project, codenaming it judy (because it was like a judge, ha ha. My advisor hated this name and told me to change it.) Unfortunately, while doing a literature review in this area I discovered that it's more or less accepted that all metaheuristics have a similar level of effectiveness.

The more I researched, the more I realized that this would probably not be a valuable contribution to the the field. It was becoming very clear that this project wasn't well-formulated, and wasn't going to be successful. I hadn't spent very long on it, building out some parts of Judy but not much more. I needed to pick a different project, but I was still very interested in Metaheuristics, so I knew I wanted it to be closely related.

Course Correction: Picking a Similar But Different Project

I had already built out some parts of Judy by this point and had some pretty promising software. In fact the metaheuristics-engine I had been building was a pretty nifty generic simulator for metaheuristic algorithms. I'd used my skills as a software engineer to build a few interfaces that were easy to implement and then dump directly into a simulator that would scale out for however many processors were on a machine, handle as much of the metaheuristic algorithm in parallel as possible, and do various neat things like safe-journaling results (so that an interrupted simulation could resume). Thus, writing new metaheuristic implementations to search problem spaces would be really easy and fun.

I wanted to use this software because I enjoyed building it, and I thought it would be cool to enhance the capabilities of my metaheuristic engine as a side-artifact of my research. I had also started building out a taxonomy of metaheuristics and how they were related in terms of object-oriented relationships (for example, a GeneticAlgorithm was a type of EvolutionaryAlgorithm in a formally-defined way, because one extended the other polymorphically).

I went to another professor, the one who taught the classes where my projects utilized Genetic Algorithms. I knew she had a whole bag of interesting problems to solve, and I wondered if I could use my simulator to find solutions.

Basically all of her problems were existence questions. Things like, does there exist a graph $$G$$ such that $$Y$$, with $$Y$$ being a variety of different restrictions. She'd posed a similar problem before, which was the motivator behind my project in her Graph Theory class.

Most of these graphs would have their existence proven not by formal proof, but by construction. Meaning, if I could construct a particular kind of graph, that graph itself would be the interesting result (and not necessarily how I derived it). My idea was, for each of her problems, I would figure out a way to randomly generate potential solutions, a way to score solutions in terms of how close they are to the ideal, and a way to mutate or perform crossover mutation with candidate solutions. I'd write code for the problems, use/enhance my simulator, and then run the simulation on our ultrapowerful university computer across hundreds of threads.

When I took on this project, I knew that it was high-risk/high-reward. For every problem I was working on, it was entirely possible that the solution I was looking for does not exist (remember, the only proofs possible are via construction). I also knew it was possible that even if it exists, my strategy might not find it, or that my approach might get stuck in local optima. In other words - I was essentially applying a technique intended for discovering SUBOPTIMAL results to optimization problems, hoping that that the threshold for optimality would be low enough that the technique could work.

It's been two years since I started this project. In that time, I have been working on three different particular problems, growing my metaheuristics solution engine, and heavily taxing the resources on the university parallel computation platform.

The first problem I worked on has been running for the longest time. Since this was a continuation of my project in my advisor's Graph Theory class, I simply adapted it to used my new and improved simulator, and put it up on our university multiprocessor machine. I'm not going to bore you with the details but basically I've been trying to find a particular graph configuration with certain restrictions, to see if a complete graph of a certain size exists. Since I'm looking for a complete graph, the 'fitness' criteria is simply, how many edges my best solution has, out of a possible $$\frac{n(n-1)}{2}$$ edges. About a year ago (after running for a year), my software managed to get ONE edge away from the desired answer. As of this writing, it is still one edge away from the solution I'm trying to discover, which seems to be the best it can do (205,949,225 generations). Unfortunately this is not an interesting or publishable result unless I can uncover that one missing edge. It's always possible that the software will find the correct solution tomorrow, but I think at this point I need to admit this is a dead-end.

I've worked on two other problems but of those, I've spent about 95% of my time on just one of them. This particular problem (again, I'll spare the details) is one that's been plaguing my advisor herself for over twenty years. I vividly recall one day in Algorithms class when she told the class that, if someone can discover particular graph with a specific set of properties, "I'll give you a PhD right there." It was this problem I chose to work on for most of these last two years.

Again, this too was a high-risk/high-reward project. My advisor and I joked that the entire publication that results from this effort would be a couple pages about the background and the reason for wanting to know if this graph exists, and the entire results section would be a single page - a listing and rendering of the graph. If I had found a result, there's no question that a paper about it would be accepted in virtually any CS journal I sent it to.

But once again, I've been working on this project for a little over two years now. I recognize that it seems early to ``give up'' given that it's been plaguing my professor for decades, but she's been trying to construct the graph by hand and my goal was to use the metaheuristics to perform a guided search of the solution space computationally. In the end though, I've become convinced after two years of working on this that either the solution doesn't exist, or that it does exist but my technique will not discover it.

Walking Away

This past semester my wife and I found out that we were going to be having a baby girl in April. Very suddenly, I started to evaluate the relative importance of my degree. It started to feel very stupid to be working on a series of high-risk/high-reward research projects where nothing had panned out in two years. These problems were unbounded in every sense - my simulations might discover a solution after a day, a week, a year, ten years, a thousand years, or never. I started to become increasingly uncomfortable with the notion of continuing down a path of research so open-ended, with the possibility that I was programmatically searching for solutions that may not even exist.

When I first decided to go back to school, I did it for fun. I enjoyed my Master's research and wanted to continue learning and educating myself, and I liked the idea of pursuing a Doctorate. At the time, I told myself and my wife that, since I was doing it for fun and not for any professional reason, that I'd stop the instant it stopped being fun. Well, after two years of research that wasn't panning out, school had certainly stopped being fun for me. In fact, it's been a source of constant stress and irritation. I've been working very hard and building some really cool software, but I have no interesting results to show for it.

The analogy I used to describe how I was feeling to my wife was, it was as if I saw people mountain climbing and I thought it looked really fun, and I wanted to do it as well. So I spent a great deal of time and money taking mountainclimbing classes. Then I began researching mountainclimbing gear and spending a great deal of money on equipment. I planned and scheduled flights to various mountain ranges. Then I finally started climbing mountains and realized "you know what? This sucks. I'm really cold, and this isn't fun at all." But because I'd spent so much time and money on it, I felt like I had to keep going even though I hated it it, falling victim to the sunk cost fallacy.

After a great deal of thought I decided I would walk away from the PhD altogether. This was not an easy decision, given how much work I'd put into things like the GREs, classes (straight A's), and passing my preliminary exams. But after two years and nothing publishable to show for all my research work, with a baby on the way, I felt like I needed to re-prioritize and know when to fold 'em, so to speak.

...Or Not?

I scheduled a meeting with my advisor to discuss my departure from the program. I was all set to walk away, and in fact had written the entire above portion of this blog post. I had basically accepted that I was done, I killed the processes on the university supercomputer, and moved a ton of books and articles out of my to-read list on Goodreads. Washing my hands of the project and admitting I was no longer pursuing it was extremely liberating - I felt like a huge burden had been lifted simply by shutting down the effort.

But then I realized something. My main motivator for coming back to school was how much I enjoyed my Master's Thesis research, and that I wanted to do more. I had thought that I must love research, and wanted to continue it. The past two years made me realize I didn't actually enjoy research as much as I thought - a fact that I had trouble coalescing with how much I enjoyed my Master's research.

A few weeks ago, the author of Beyond Legacy Code contacted me to say he referenced my Master's thesis in his book. He praised my effort, talking about how much he enjoyed it and how he felt it was one of the better entries he's come across. It made me look back at my thesis and remember how much I enjoyed working on it.

Then it dawned on me. Was it possible that it wasn't the research I enjoyed at the time, but the actual subject? If it was the subject, then would a research project more inline with my Master's appeal to me more? I had come back to school for Theory & Algorithms, and I was so laser-focused on those subjects that it hadn't occured to me that I might enjoy classes in these topics but not research. Would I enjoy a research project if it were focused on Software Engineering, like my Master's?

Pondering this for a few more days, I suddenly had a new idea for a research project. This was something much more Software Engineering-focused than what I had been working on - in fact it wasn't related to CS Theory at all. It was more of a natural continuation of my Master's work, and I was stunned by how excited I was by the idea. I once again felt the passion of wanting to complete my PhD, reinvigorated by this new project. My wife commented that she hadn't seen me this excited about research in the entire two years I'd been working on my metaheuristics project.

Of course, there have been some logistical issues. Since I went back to school primarily to focus on Theory, nearly every class I've taken has been theory-heavy. Due to this, every single professor I've met or worked with has been a theory professor, not a single one of them is experienced, or even interested in Software Engineering research.

The meeting with my advisor, which I had originally scheduled to tell her I was dropping out of the program, went very differently. I had come up with the new project and done some publication searching all between scheduling the advising meeting and actually having it. So when I walked into her office, I presented her with my new project idea.

I expected her to hate the idea since it's so unrelated to theory. Instead, her reaction was basically, if I'm passionate about the project she'll help in any way she can. She doesn't have a lot of experience with Software Engineering but I don't think I need a lot of help with the topic - this is what I know best.

So that's my status update. Baby on the way, feeling a strong desire/pressure to finish this PhD quickly, and basically starting over entirely in the research. Reading it back, it seems downright idiotic, but I feel extremely excited about my new project, and for some reason I don't feel worried.

I still feel the same way about the program - this is something I'm doing for fun, and the instant I'm miserable in the program I will walk away. But if there's any path that ends with me actually completing this degree, I feel like I'm finally on it.

The next update about school will either be announcing that I've completed my dissertation and am graduating, or that I've decided to walk away from the program for good.

TL;DR

Too rambly but you still sort of care? Here it is in a nutshell:

I decided the research project I've been working on for two years was a dead-end. I almost decided to walk away from the program entirely, but instead have started over with a radically different project to give it one last shot before calling it quits.

comments powered by Disqus