Yesterday, I finished my semester project for my randomized algorithms course.  I started the project almost a month in advance since I knew there was going to be a significant amount of research and reading to do. The original plan was to create a mathematica module for processing Exponential Random Graph simulations.  The concept is this:

You have some observed social network, collected from data or in the field.  You want to know things about the relationships of people in the network, like, how likely are people to form connections randomly or do they form connections based on other sociological things. For example, if Alice is connected to both Bob and Eve, is there likely going to be a relationship between Bob and Eve? In other words, do they complete the triangle?  Standard random graph models can’t test for this but we can use exponential random graphs. The output of the algorithm is a set of values that indicate how strong various network structures are.

My presentation went alright. In the mathematical sciences (engineering, math, etc) proofs are the only method you can use to show something is true. In the applied sciences (communications, sociology, statistics) the only method you can use to prove something is statistical inference. So, explaining inference to engineers is difficult since they don’t encounter it (I think they should!). Explaining math to social scientists is challenging since they’re not familiar with proof techniques (what is the contrapositive again?)

I haven’t finished the paper yet (almost done) and I will post the results here shortly. In the mean time, I’ve compiled some of my thoughts about approaching this topic in the future. This is what I want to study (using computer science theory in other fields) so I am noting this for posterity.

• Use more visualizations to explain inference.  Mathematicians love proofs and it is ok to use math on your slides. However, when talking about statistical inference, you’re looking at how something observed fits something hypothesized.  The best way to do this, I suspect, is to plaster a N(0,1) curve on the slides and point to where things fit.
• For social networks stuff, use examples! I used a couple examples in my slides and people found it helpful and interesting.  There are so many great visualization tools for social networks, so I should use them more.
• Take a course on econometrics.  I’m doing this next year.  Econometrics is using statistical inference to reach economic conclusions. There has to be some good techniques they use.
• Write the slides AFTER you write the paper. In this case, I was so worried about the presentation, I did it before I wrote the paper and ended up rushing the paper.  Next time, I’ll flip it and spend time worrying more about visualizations and teaching people than plastering equations on slides.

I took a few minutes away from studying today to attend a talk in the business school at Northwestern given by Bruce Bueno de Mesquita (BdM). I first read about him a few years ago in an article in GOOD Magazine.  He’s an important guy, I guess.  He has a wikipedia page, a TED talk, was on the Daily Show, and has published a few books and papers. By modern standards he fits those qualifications for importance. He’s also a professor at NYU and consults various “top-secret” high level government entities (I roll my eyes when people talk about that kind of stuff). I was able to find a few interesting papers [1][2] he had published previously but it looks like he only really works with mass-market writing and consulting these days.

Some of what I study here is game theory, in fact, the theme of my next quarter is game theory: two courses on game theory and one that will probably be about game theory on networks.  I knew a little bit about his work beforehand and I know various game theoretic models so I was hoping he would talk more quantitatively.  Unfortunately, any slide with numbers or equations on it, he quickly skipped in lieu of talking about his quantitative ability and giving his thoughts on international politics.  Not that it was not interesting, he is a very captivating speaker and I find international politics interesting.

However, I left the talk asking myself if I learned anything really new or valuable from the talk. I don’t think I did. I left with the following take-aways:

• BdM and his team are good at making predictions about global international conflict.   They are right 90% of the time. Some journalists and the government says so.
• He uses game theory to do this.
• Many of his models are super complicated and he gets hired by Uncle Sam and big corporations alike.
• He has talented undergrads working with some of his models.

I was hoping that he would share more insight into how those who do theory (like me) can apply models to the real world. How can we leverage cooperative game theory and economics to make claims about international politics? What kinds of models does he use? How does he use the work of guys like Myerson?  Does he use any algorithmic game theory? If so, what algorithms are important? As students and those who study game theory, what kinds of research should we consider doing?

There were some very pre-eminant game theorists in the audience and I was disappointed they didn’t ask any questions at the end. Rather, he had a couple softball questions about his thoughts on current global situations.  I regret not asking questions like those above.  Lesson learned.

Hello blog-world. I haven’t blogged in a while. I’ve been working on some pretty cool research, including a Mathematica implementation of the Metropolis Algorithm for social network (ERGM) analysis. I will add it to the site when I complete it.  You should be excited.  Anyway, for the sake of record-keeping, here are the courses I am looking forward to taking next term here at Northwestern.

• Applied Math 495 – Dynamical Processes on Networks – This is an applied math course, so I expect it to be pretty challenging. However, it is on my research specialty, social networks.  I’m taking this course with an undergrad friend of mine who really knows his stuff, so this should be a great course. It’s taught by Dirk Brockman, who has done some cool research.
• Economics 410-3 – This is the third series in the dreaded PhD level economics sequence. The theme for next quarter is game theory.  The theme this semester was general equilibrium theory. So, yeah. I’m happy to be moving on to game theory, something I’m more comfortable with.  The course is taught by Michael Whinston, the guy that co-wrote the infamous Mas-Collell (MWG) textbook.  I’m looking forward to this course but I’m also terrified.
• Computer Science 495 – Algorithmic Mechanism Design – One of my co-advisers, Jason Hartline is teaching this course. His research speciality is mechanism design and his last few papers have been focused around bayesian and prior-free settings. I expect this course to be rigorous mathematically but have lots of applied uses in research, especially since I started at NU wanting to do computational mechanism design work.
• I’m also auditing a course taught by Uri Wilinsky on NetLogo, a really cool agent-based modeling software that I used for a while when I was at Michigan. The course is a 300-level, so if the workload isn’t too bad, I may take it for credit. Otherwise, I will just audit it and work at getting better at the software which can be used in a lot of simulation settings, especially when plugged into Mathematica.

Anyway, my final project for the randomized algorithms course is due in a few weeks, so once I complete it, I will post the assignment and the mathematica plugin on my website. So far, it seems like it may be a helpful overview of the research into exponential random graph models (ERGM) for those interested in algorithms.

Today is the Sunday before my finals week. I actually only have two finals; a large micro-economics final and a take home probabilistic method final. I’ve already spent about 5 hours working on the take-home final and I’m terrified about the micro final on Wednesday night. Friday was the last day of classes, so I’ve had a few days to compile my thoughts about my first quarter.  I have to admit that I didn’t do a very good job following my own advice but I will be following it next quarter.

The below list can also be titled, “How I am going to do better next quarter”

• Study Early, Study Often. This sounds really cliche but it is the most important thing you can do. Do *all* readings, buy all the books required for the course, and after every session, go through and type up your notes. The coursework on the PhD level is so much more intense than a Masters or Bachelors program. I’ve had some course sessions where they covered an entire undergrad quarter in a single session.
• Type up your Notes. See the above comments. I plan on doing this for all of my courses next time. For every hour of notes, you’ll have to spend at least 30-45 minutes reviewing and typing them up.
• Study on Saturday Nights. This sounds terrifying, I know. The nice thing about Saturday nights is that you’ll be the only one studying, so you can get a lot done. I consider this the price of getting a PhD.  I prefer to go out on Friday nights and spend Saturday and Sunday nights studying.
• Try Not to TA Your First Quarter. This may be unavoidable for some but I’d suggest not TAing your first quarter. It can be very time consuming, especially if you’re not totally familiar with the material yourself (or you’re rusty from not having taken the class in a long time).  I had to drop my third class in lieu of my TA position, since I couldn’t handle all of the workload.  However, being a TA is generally a positive experience, so I do suggest doing it at some point.
• Spend Time Outside of the Office. Not all PhD students get an office but those of you that do; don’t spend too much time in your office talking to people. It can be easy to spend an entire workday (9-5) in your office talking to colleagues, professors, etc. If you can get out of your office and go to a cafe or the library, you’ll have more time to focus on the material.
• Walk Everywhere. Being a PhD student means that the only free-time you have will be at times when nobody else in the world is awake (3am, usually). It’s really hard to get a decent workout at 3am – most gyms are closed and you’re probably burned out.  The best way I found to stay in moderately healthy shape was to walk everywhere – from my apartment a mile from campus, to campus, to town, etc.  Also, the food that you’ll eat on campus is probably terrible for you; so you’ll have to work off the extra calories.
• Go to Office Hours. After you type up the material, you’ll probably have a dozen questions that you didn’t ask during class. Go to office hours; it’s a good chance to network with colleagues (other PhD students) and helps with the material.
• Read the Book First. If possible, try to read the course text before the class starts. This sounds unreasonable, but will help immensely and spreading out the work later on.

This quarter (they’re quarters, not semesters here at Northwestern), I was a TA for EECS310 – Discrete Mathematics. It is a 10 week course, divided into sections: proofs, binary relations, graph theory, counting, combinatorics, and probability. Today is their last quiz, so I’ve compiled a list of my thoughts about TAing and things I will do different next time:

• Be more prepared: I went into this course with not very much discrete math experience. I had encountered most of the material at one time or another through my academic career but I was very new to many of the concepts (especially the formality of writing good proofs). I wish I could have worked through some of the course material, ahead of time, so I could have done a better job answering student questions.
• Don’t be afraid to say “I don’t know”: I felt pressure to give students precise or exact answers to problems.  Mostly, in the classes that I’ve taken, if I’ve asked the TA a question they’ve been able to give me precise answers. So, I felt bad when I couldn’t help them as well as I’d liked to. There were a few times this quarter where I was asked a question and tried to figure it out on the spot but tanked. I learned that sometimes, you have to say “I don’t know” and get back to the student.  It’s okay to defer some questions to other TAs or the professor.
• Be fair when grading problem sets. Don’t be harsh with penalizing for mistakes but reward students who do particularly well.  If I take points off, I try to provide some reasoning to the student, i.e. “You didn’t do this well.”, “You are close but not quite there..”, and so on. If you’re too harsh, students complain and if you’re too easy, they don’t learn from their mistakes.
• Talk to the class about their problem sets. This is something that I didn’t do that I wish I had done, the best TAs that I’ve had have done this.  In the future, after I grade problem sets, I’m going to go in front of the class and talk about what they did: give suggestions for improvement, talk about general proof writing techniques, and make suggestions for future assignments.

That’s all the suggestions that come off of the top of my head.

Well, I’m not actually registered for these courses yet, so hopefully I won’t encounter any waitlist issues. Apparently, I need to get some shots first, since they put a “health hold” on my account. Whoops.

• Applied Social Networks Analysis – This course is taught by Nosh Contractor, who is one of the pre-eminent social networks researchers. I have taken a similar course to this before, at Michigan, so hopefully I should be able to do really well in this course. I’m looking for ideas and things I can put into a dissertation (in a few years), so any class like this should help.
• Algorithms – This course is taught by one of the professors in our division (the theory dept). I’ve been told this is a really great course by the undergrads that have taken it. It’s technically an undergrad course (3xx level) but the graduate school lets me take it because of the difficulty.
• Microeconomics Sequence (part 2) – This is just the second part of the PhD Micro Sequence. I’m (hopefully) going to pass the first part, and they’ll let me stick around. I’m pretty sure the topic of this sequence is general equilibrium theory (woo). The goal is to make it through this part, so I can get to the game theory in part 3.

With the end of the semester coming up soon, I’ve been thinking about my plans for the holidays. Obviously, I’m going to spend some time back in Michigan with my family, around the holidays and especially the week of Christmas. Other than that, I’m going to have a lot of free time around here. I’m looking forward to coming into the office, when campus is empty and doing some work on my pet projects:

• Working on a paper for publication in the Journal of Quantitative Analysis in Sports . I have my fantasy football algorithm, which I’ve been revising over the past few years. The model is pretty simplistic but I’ve been able to isolate more than 50% of the variance in individual player performance (which is pretty good). I think I can formalize the model more, add in some more analysis techniques and submit for publication.
• Working on some research with my adviser, Nicole Immorlica.

In general, I’m starting to feel really good about the direction that I’m going in. For the first couple months, I had a hard time adjusting to the program here. It was dramatically different from my undergraduate and masters programs. I still don’t quite have the math chops to be able to keep up with my colleagues yet but I think after this and next term, I should be caught up. It’s like moving to another country without knowing the language and just picking it up from constant exposure.  It is terrifying at first, but as you adjust things get easier.

On a cool note, it looks like I may be going to KDD2010 this year.  The coolest part of the KDD conference is the annual KDD Cup competition they hold. You are given a dataset and asked to mine it. They’ve done all sorts of cool sets in the past: { website clicks, biomedical data, proteins, particle physics, and netflix }  I’d like to go to EC2010 this year too, it’s in Boston right across the street from the STOC CS convention.  The only problem is that it is during the week of finals here, so I’m not sure if that is going to happen this year.

At Northwestern, every two years, they award a prize in economics and mathematics, the Nemmer Prize. This year’s economics prize winner is Paul Milgrom. Milgrom has done a significant amount of work in auction theory and FCC spectrum auction design. At Michigan, I had to read quite a few of his papers and books. Auction theory is one of my favorite research areas: the theory is pretty straightforward, there is tons data, many real-life applications of the theory, opportunities for simulation, and a lot of activity and current research.

There is a panel discussion today with Al Roth, Susan Athey, Preston McAfee and Paul Milgrom – all really big names in the auction theory field. The research I’ve been doing lately builds on the models developed by all four of these people. I’m consistently amazed by the quality of speakers Northwestern can attract.

At one point, Preston McAfee displayed Yahoo!’s “objective function” for bid ranking on his slides. I wish I had caught a picture of it. I would have liked to run some simulations on his model.

Conclusion of the panel: Computer scientists (me) need to catch up with economists. In other words, I should take more economics courses.