After returning from Europe with my brother, I packed up my belongings and headed to Los Angeles to start graduate school at UCLA in Computer Science. I arrived well before the term started, and Joann and I moved into a two bedroom, two bathroom apartment on the corner of Santa Monica and Barrington. It was a really nice apartment for $800 per month, which was a lot more than I had been paying in Berkeley, but it was inexpensive for the area and I was now splitting rent with Joann. Due to my experience in Stuart Russell's lab at Berkeley, I got a job for the remainder of the summer working with Rich Korf on another selective-search algorithm. This time, I implemented Rich's best-first minimax search on the game of Othello.

In the fall I started rowing the single out of the UCLA boathouse. I had rowed in a single a small handful of times while I was at Cal just for fun, but I had never spent any serious effort with it. I figured that it would be good to learn how to row the single given that I was not rowing with a team and given that I wanted to stay in the sport. I also started running with a group of UCLA faculty and staff that went out every day at lunch for about an hour, and I began to play ultimate frisbee a couple times a week with some graduate students. I had played ultimate a number of times when I was a kid, but I had never played competitively.

Living in Los Angeles was a lot of fun. Except during the summer, the weather is optimal for me: sunny and in the seventies almost every day. Joann and I would frequently drive to the beach (about three miles away) and watch the sunset and/or go boogie-boarding. There was also a bus that stopped right next to our apartment that went straight into Santa Monica, and we would often take it to a comedy club on the weekends.

For my first quarter of graduate school, I took three courses: Judea Pearl's Bayesian-networks class, a course on neural networks, and an undergraduate course on network protocols. The Bayesian-networks class turned out to be a life-changing experience for me. I loved the class for a number of reasons, and I have continued to do research in the area ever since. I also met David Heckerman who was sitting in on the class, and who had just been hired into the Computer Science department. David and I started working together almost immediately; we were both really excited about a recent UAI paper by Cooper and Herskovitz on learning Bayesian networks from data.

Joann had a friend in the Chemistry department who played bridge, and he invited us to play with his group, which was named "Santa Monica Eclectic Gaming Masters Association" or SMEGMA. It turns out that the members came up with the acronym first, and then found a name to fit. We would play bridge a couple times a month on Thursday evenings, always taking a half-hour break to watch the latest episode of The Simpsons. The bridge was competitive but not too serious, and Joann and I look back fondly on the experience.

By the end of my first quarter, it was clear to me that I would be working with David Heckerman on some sort of Bayesian-network learning problem. One day early in the Winter quarter, David dropped a bombshell: he was leaving UCLA to start a group in Microsoft Research. I was disappointed, but we decided that we would try to continue to work together and that I would apply for a position as an intern that summer.

I continued to take classes my second quarter at UCLA: I took Rich Korf's AI search class and Judea Pearl's current-topics-in-Bayes-nets class. I believe I also took a class on natural-language processing by Michael Dyer, but that might have been another quarter. My term project for the Bayes-net class was a divide-and-conquer algorithm for learning Bayesian networks, using the Cooper and Herskovitz Bayesian score to guide the search. For the search class, I derived a hybrid algorithm that combined alpha-beta search with Rich's best-first minimax search; the idea was to perform a "normal" alpha-beta search to a particular depth, and then to extend the leaves of the search tree using selective search. The hybrid algorithm turned out to be superior to both individual algorithms.

Although I was not receiving any coaching, I was starting to become reasonably competent at rowing the single. By "reasonably competent", I mean that I could get a good workout without falling in. I was getting up early two or three times a week and heading to the UCLA boathouse in Marina del Rey, where I would take the single out for my standard loop: I would start by rowing to the end of the marina, then I would turn around and head to the breakwater and do a hard stretch down the racecourse and back (where I was technically not supposed to be rowing). If I went at a strong pace, the workout took just over an hour.

I really enjoyed the running group, and I decided to run the Los Angeles marathon in March. I had never run more than about ten miles in a row before the race, and on the big day the temperature got to 87. It ended up taking me over four hours to complete the run, which is a really long time to be running when its that warm. Evidently I looked really bad at the end; I remember during the last couple miles that spectators would be smiling and clapping, but when they looked at me they would suddenly look concerned and say something on the order of "you can make it". After the race was over, I was determined to get in better running shape for the next year.

When summer rolled around, I headed up to Redmond, Washington to work with David at Microsoft. David had started the Decision Theory Group with Eric Horvitz and Jack Breese, and I was really looking forward to the experience. I moved in with Barry and Gina, who are friends of mine who lived reasonably close to Microsoft. (I first met Barry in 1983 when he worked with my mom.) The summer was a lot of fun. I shared an office with Dan Geiger, and we worked on a lot of cool problems. I did a lot of development work in addition to research. I also started playing pickup ultimate frisbee with a group that would eventually turn into Vince.

I returned to Los Angeles in the Fall, and I continued to take classes to prepare for the dreaded Major Field Exam in artificial intelligence. This test covered what UCLA deemed the core competencies in AI, of which only a small handful I had any interest. I enjoyed the mathematical rigor of Bayesian networks and heuristic search, but I had absolutely no interest in fuzzy make-computers-act-like-humans-in-toy-domains research. Fortunately I had a lot of interesting problems on which I continued to work with David. I continued rowing, running and playing frisbee with a vengeance. On Tuesdays and Thursdays (when there were frisbee games in the evenings), I would participate in all three: rowing in the early morning, running at noon, and then frisbee in the evening.

On January 17, 1994, at the beginning of the Winter quarter, Joann and I were woken up in the middle of the night by the Northridge earthquake. We had both been in Berkeley in 1989 when the larger (7.0 as opposed to 6.7) Loma Prieta Earthquake hit, but for me this second one was much more frightening. When I woke up the apartment was shaking so violently that I thought we were going to die, so I quickly rolled over and hugged Joann so that we would be together in the end. The experience did some serious psychological damage, and I was terrified by the aftershocks that persisted for weeks.

In March, Joann and I celebrated our five-year "dating anniversary" by heading up to Big Bear for a weekend of skiing. We were joined by Joann's parents and some friends of ours from UCLA.

In the Spring of 1994, I passed the Major Field Exam, and as a result I had earned a Master's degree in computer science. Many of my peers in the Ph.D. program passed this milestone without much fanfare, but I decided that I wanted to participate in the graduation ceremony. My mom agreed to come up from the Bay Area for the festivities, and on the afternoon of June 17, I got on 405 south to pick her up at the airport. Coincidentally, this happened to be the same time that OJ Simpson and Al Cowlings were heading north on 405 during the famous "slow speed chase" after the police issued a warrant for Simpson's arrest. The freeway came to a complete stop, and people got out of their cars in anticipation of seeing the chaos coming in the other direction. There was an overpass about a quarter mile ahead of where I was stopped (I stayed in the car), and to my amazement it was packed with crazy people waving and displaying signs for the fugitives to see. When the white Bronco finally passed by (followed by an armada of police cars), traffic started moving again and I was only about a half hour late to the airport.

After graduation, I headed back up to Redmond for another summer at Microsoft. Once again, Barry and Gina took me into their home. I spent a good portion of the summer working on a proof that learning Bayesian networks from data is NP hard. It took until mid fall (after I had returned to UCLA) to get the details of the proof ironed out, but the summer was productive. That summer, I rejoined my ultimate friends who had officially started the Grandma's Hammer team.

When I returned to UCLA in the fall of 1994, I was done with classes and was free to pursue my research agenda. As previously mentioned, I was working on a complexity proof, but I was also trying to prove a property about Bayesian-network equivalence that was important for a paper that I was writing with David Heckerman and Dan Geiger. I made great progress that quarter. I came up with a proof about equivalence that led me to lots of other interesting problems. The main proof and some consequences appear in a UAI paper from the following summer. In the middle of the night some time in November, I woke up and had the missing piece to the NP-hard proof I had been working on. The final proof is published here.

I continued my workout ritual that fall, although I started to take the running a little more seriously. I would often break off from the group to go on longer runs, trying to get in better running shape for the LA marathon. I also started to play ultimate frisbee more competitively. There was a team that played at UCLA on the weekends, and I traveled with them to some local tournaments a few times. I also picked up with a league team that played in the evenings, and I continued to play pickup with the graduate students.

In January 1995, I headed to Ft Lauderdale, FL, for the AI and Statistics workshop to present a paper about search algorithms and an initial version of my complexity result. This was my first "real" talk, and it was very intimidating.

In March 1995, I ran the LA marathon for the second time. I did much better than the previous year, finishing in 3:08 and feeling pretty good afterwards. I was determined to break 3 hours the next time.

I spent the remainder of the academic year continuing my research and working on papers for that summer. I also became obsessed with proving a conjecture about equivalence classes of Bayesian networks that, if true, had some pretty important consequences.

When the summer came, I returned to Redmond for my last stay with Barry and Gina. I spent a lot of my work time trying to prove the conjecture. This was by far the most frustrating research effort for me. I spent what seemed like endless hours on the problem, and at the end of the summer I was no closer to a proof than when I had arrived. I got a lot of other useful work done, so the summer was by no means a loss, but I was very disappointed. I decided to stop working on the problem because it had been such a drain of time. (Six years later I finally managed to prove the conjecture!).

That summer I played a lot of ultimate, both with Grandma's Hammer and in the many pickup games at Microsoft. I also started rowing with the Microsoft Crew ("Where do you want to row today?"). The rowing team was training to race in the Head of the Charles, which I was not going to be able to attend, but they had not solidified a lineup so I was able to work out with them twice a week. This was great fun for me as I had not rowed seriously in an eight since college. I had to get up at 4:45 am to make practices, and so I went to bed around 8:30 almost every night. As a result, I almost never saw Barry and Gina!

When I returned to UCLA that fall, I was ready to give my oral proposal to my doctoral committee. Judea Pearl and Rich Korf were the co-chairs, with David Heckerman, Stott Parker, and Jan DeLeeuw serving as the other members. My plan was to present what I had done to this point, with the hopes that they would agree with me that I had done enough work and I could start writing my dissertation. I had an offer from Microsoft, and I wanted to start work as soon as possible. Everyone was happy with the proposal, except that Rich wanted me to do some more work with heuristic-search methods for learning Bayesian networks. Although I was unhappy at the time, the extra work ended up being very interesting and it made my dissertation much better.

Joann and I moved out of our Barrington Ave apartment into a much nicer place on Westholme Ave. The new apartment was adjacent to a real neighborhood with houses, and we would often go on walks in the evening. We were about the same distance from campus.

On December 3, 1995 I ran the Culver City marathon in 2:52 and surprisingly I won my age group. I was very happy about my time, and I was excited to run the Los Angeles marathon the following March. In the interim, I increased my mileage significantly. I would go on really long runs, occasionally up to 30 miles, about once a week. Running experts will tell you that its not a good idea to do this, but for me it was (psychologically) critical that 26 miles did not seem like an abnormally long run. The training paid off, and on March 3, 1996, I completed the marathon in 2:47.

I spent the rest of the academic year working on heuristic search and writing my dissertation. Some of my research from this time ended up in a UAI paper the following summer, but the results were for the most part negative (simple search algorithms were very hard to beat in this space), and the majority of the results were only presented in my dissertation.

On May 10, 1996 at 2pm, I gave my defense. Although there was little chance that I would fail, it was still a very stressful event. Happily I passed without getting too much grief from my committee. In June I filed my dissertation and was officially done with school! I went through graduation ceremonies, and Joann threw a great party for me.

 

 

 

 

All About Max

Los Angeles, California: 1992-1996