Thoughts and experiences on various topics: puzzles, games, AI, collaboration, music, politics, and whatever else is on my mind

GTE Laboratories (1985-1996)

In July of 1985, I started work at GTE Laboratories in Waltham, MA.  I was a Senior Member of Technical Staff in the Self-Improving Systems (Machine Learning) department of the Fundamental Research Lab.  Our mission was to do long-term basic research in machine learning.  This was exactly the environment I wanted to be in – I had stimulating colleagues who shared my interest in machine learning (many of them were PhD’s), and the opportunity to “think deeply about simple things”, i.e. perform basic research.

This was the ideal environment in which to continue my research on “discovery of macro-operators in problem-solving”.  I had begun thinking about this topic back at CMU, when reflecting on how I learned to solve the Rubik’s Cube.  Rich Korf did his Ph.D. thesis on an algorithm for filling in a table of macro-operators to solve certain types of puzzles, such as Rubik’s Cube and the 15-puzzle.  I was thinking about a more general and more heuristic approach where macros would be proposed and then evaluated on the basis of their contribution to improved problem-solving performance.  I continued thinking about this, and began writing some programs to encode my ideas, while teaching at Hampshire.  I wrote and published a paper in IJCAI-85 describing my initial ideas and results.  Because this paper was submitted near the end of my time at Hampshire, and because I anticipated starting work at MITRE, I listed MITRE as my affiliation in the title of the paper.  This turned out to be ironic, when I ended up working at GTE Labs instead.   I was happy that GTE supported my attending IJCAI in Los Angeles that year.  It was my first conference paper and presentation.

The basic idea of my work was based on the informal observation from Rubik’s Cube solving, that it was necessary to (temporarily) undo progress, i.e. subgoals achieved, in order to achieve new subgoals, and ultimately solve the puzzle.  The idea of a macro-operator is a sequence of moves that can transform the puzzle state in a predictable way.  One simple example is to permute the positions of 3 cubies (1x1x1 puzzle elements) but leave everything else unchanged.  Lots of other things get changed (messed up) during the macro, but when the sequence is complete and the dust (mess) has cleared, everything is back where it was except for the 3 cubies that played “musical chairs” (changed their positions).  The learning problem that interested me was how these macros could be discovered  by a program.  My basic approach was to use a heuristic evaluation function  to count the number of subgoals achieved.   My program examined sequences of moves along paths down the search tree, and looked at the values of this heuristic function for each puzzle state encountered along the paths.  Typically, in puzzles like Rubik’s cube, there would be peaks and valleys along the path.  Peaks were where more subgoals were satisfied than in the states before and after.  The valleys corresponded to undoing subgoals, and it seemed natural that the sequence of moves spanning a valley (extending from one peak to the next peak) would be a good candidate for a macro, especially if the 2nd peak was “higher” than the first (meaning that overall progress had been made).

I also made a representational commitment to having macros be described in the same format as primitive problem-solving operators (e.g. the basic twists of Rubik’s cube).   I represented all operators (both primitives and macros) in terms of the change of state they entailed – specifically, in terms of a before and after state.  These were actually partial states, since they could have some parts of the state specified as not relevant (I called them “don’t cares”).  The principal advantage of this representational commitment is that the problem solver does not require modification in order to use additional macros!  The problem-solver (performance system) simply used a set of available operators, and if new macros were found, they could be added to the operator-set and could then get used like any other operator.  The main performance gain  resulting from learning macros is that the search can take larger steps in the problem space, since each macro actually involves multiple primitive steps.

I like to think of this as a chunking model of skill acquisition, with macros being larger chunks defined in terms of simpler chunks.  Chunking is a well-known and well-studied psychological phenomenon, and is the source (imho) of human ability to deal with complexity.   In order to represent my macros in the same format as primitive operators, I needed to compile a sequence  of steps into a single step, which involved analyzing the before and after states spanned by the sequence.  In addition, this compilation process produced a macro-definition or expansion, which could allow any solution found in terms of macros to be expanded into a solution using only primitive operators.  Primitive operators were distinguished and recognized by the fact that their definition (expansion) was empty (NIL).   In fact, macros could be learned in terms of other macros leading to a definitional hierarchy.  One final advantage in my approach was that learning could take place during problem-solving, even before a solution was found.  My first program only learned macros from analyzing a completed solution path, but I later generalized this so that macros could be learned from any path in the search tree, even before a solution was discovered.

I continued to work on this heuristic macro-learning project while employed at GTE Labs.   My work led to the publication, in the prestigious Machine Learning Journal in 1989, of my paper “A heuristic approach to the discovery of macro-operators”.  I am indebted to my friend and editor, Pat Langley, as well as my GTE Labs colleague, Oliver Selfridge, for invaluable help in finishing and publishing this paper.

Sadly, the ideal research environment I experienced at GTE Labs was time-limited.  After my first year there, GTE decided to eliminate the Fundamental Research Lab, and focus on more “applied research”.  This presented a challenge to all of us in the Machine Learning department. Fortunately, we kept our jobs, but the department was moved into a more applied  “Computer and Intelligent Systems Lab”.  We continued to work on machine learning, but there was much greater pressure to apply it to GTE telephone or other operations.

There were (at least) 3 different machine-learning projects within our group, and they had been pursued fairly independently by 3 different researchers.  We were directed to work on ways to integrate these disparate learning approaches (Decision-tree Induction,  Rule-based Learning, and Macro Learning) into a unified project.  We struggled with how to do this, but in the end we succeeded in creating the ILS (Integrated Learning System), in which each learning method both proposed actions to take (performance system) and tried to improve it’s own behavior (using it’s individual learning system).  The integration involved a TLC  (guess who proposed that acronym?) which I called The Learning Coordinator.  The TLC would collect action proposals from each sub-system, and distribute all the proposals to each sub-system.  Then each sub-system would give a rating to each proposal, according to how well it thought the proposed action would work out if actually performed.  These ratings (numerically weighted votes) were collected and averaged, and the highest rated action would be performed.   The results of the action (the next state of the world or environment) would be made available to each sub-system for use in its own learning.  This seemed to me like a fairly simple idea, and it was the only one we implemented – it was actually a fallback from discussions and proposals we had for much more complex systems, but we never got agreement or traction on implementing the more ambitious proposals.

I thought this ILS framework was an interesting idea that merited further develop, and quantitative analysis.  I proposed experiments I thought we should do to see how much benefit arose from the collaboration of the different systems.  I was already a fan of collaboration from my ESG experiences at MIT.   There are careful and (to me) obvious experiments that could be done to measure and compare the learning of each sub-system (in isolation) with its learning in the context of joint collaboration.  It’s not clear whether the ILS would outperform the individual systems working alone, but there are at least 2 reasons for hope:

1.   With 3 alternate actions to choose from, one hopes that the action chosen would often be better than that proposed by any single sub-system.  This is simply a performance issue, and does not rely on learning.

2.   Each sub-system (agent) would likely see actions taken that were different from its own proposal, and this should expand its learning opportunities.

My proposed experimental framework was fairly simple:

a.  Define a performance metric to  evaluate performance (on a simulated, thus repeatable, world)

b.  Use the performance metric to evaluate Agents, and the ILS as a whole, with all learning turned off.  These provide the baselines

c..  Have each Agent perform and learn in isolation, and also have the ILS system as a whole perform and learn.

d.  Finally evaluate the performance of each individual Agent, and the whole ILS, again with learning turned off.

The interesting questions to me are:

1. How much learning occurred within individual agents?

2.  Did the ILS ensemble learn more than the individual agents on their own?

Learning would be “measured” as the difference in performance scores.

It saddened me that my colleagues resisted doing these experiments.  I understood this to be for “political reasons” – the expressed concern was that failure (if the system didn’t learn well) was viewed as much more dangerous than any success.   I hated this attitude – which strikes me as unscientific (“I’d rather not find out at all, than find out I was wrong”?).   In case you haven’t figured this out about me,  I deplore politics, especially when it impedes progress.   I still think these experiments would be interesting to perform (perhaps using different agents), and maybe I’ll get back to them someday …

Oh yeah – one other ironic note:   Our team was nominated for and received a prestigious corporate award for our work!  It makes a great resume entry under Awards and Honors:

      GTE’s Leslie H. Warner Technical Achievement Award, May, 1992, for work on the Integrated Learning System. The Warner Award is GTE’s highest technical achievement award.

We got a chunk of money to divide up, and an all-expenses paid trip to New York City for the award ceremony (presented by the CEO of GTE).  We also got several publications out of the work.  But sadly, I don’t think it has had much impact on the world – unless someone read our papers and found a way to use the work.  My colleagues, being risk-averse, would not consider trying to deploy the system anywhere within GTE – the dangers of failure outweighing any possible benefits.

This all strikes me as Dilbert-esque.  Maybe there’s a good reason – Scott Adams worked at PacTel (another telephone company), which provided him with experiences that feed into his Dilbert comic strip.  GTE exhibited nearly all the craziness on display in Dilbert, and sadly there is more truth behind it than you’d expect!   At GTE we had frequent reorganizations, during which little work got done.  We had management that seemed to hinder, rather than support our work.  There was a tendency to avoid doing things that could lead to “visibility” and/or “perceived failure” (no such thing as a successful negative result – in science finding out that something didn’t work can be a step of progress toward finding something that does work – but at GTE, if it didn’t work, you were a failure, so better not to try things).

My career at GTE Labs came to a crashing halt in 1996 when our entire 4-person team was laid off.   We had the option of seeking other positions, but most of us ended up leaving for other jobs.  GTE had been my “work home” for 11 years, and I was sad to leave.   On reflection, I feel that I (and we) could have done much better work given more supportive and encouraging circumstances.  My colleagues were all extremely smart, and I consider them long-term friends to this day.   I have come to believe that large corporations are often impediments to progress (scientific, technological, and social).  More on that another time, perhaps.

Marriage and Parenthood

While working at GTE, things got better in my marriage.  We had economic stability, a house we had purchased and fixed up, and our son, Aaron.   I loved being a father, and have fond memories of interacting & playing with him,  reading to (and later with) him, and playing video games.  The next major highlight of these years was the birth of our 2nd son, David …

Our Family Grows!  (David born July 7, 1987)

My wife and I welcomed our 2nd son, David, into our family in July of 1987.  This was a very happy time for all of us.  Aaron seemed to adapt well to his role as “big brother”, and we added a 2nd bedroom to the small ranch house we lived in.  I have very fond memories (and some favorite pictures) of carrying David around on my shoulder when he was an infant.

Interestingly,  David arrived at 2:06am, and our home address at the time was 206 Concord Ave.  Coincidence?  Probably!   Interesting?  I love it!

Around 1989 we sold our house in order to purchase and move to a larger residence, still in Lexington, MA.  Moving is always stressful, but we got through it.   I remember my father coming up from PA to help out with packing and moving (interesting side note:  for all my life I’ve lived in the MA and PA states ! ).   We moved in January 1990, I think, and I remember we had a horrible ice storm the day of the move — the driveway of the new place was a sheet of ice!   Despite the challenges, we got everything unloaded, and started to settle into our new house, which had much larger space (3 bedrooms).  Within a year, our family was to grow yet again!

Birth of a daughter!  (Rachel arrives Dec. 2, 1991)

On the first day of Hannukah, our family grew once again with the arrival of our 1st daughter, Rachel!  My wife and I, as much as we enjoyed our 2 boys, were grateful to have a daughter, too!  All 3 kids have been a special blessing, and I feel it has been my privilege and honor to be their father.   When I look back on my life,  being a parent (and, if I do say so myself, a rather good one) is my proudest accomplishment (of course it’s not done yet — I’m still their parent, and hopefully can still contribute a bit to their growth and development – and they all continue to contribute to mine, as well!).

I think I’ll end this note on that upbeat note !

Next time:  career transitions:  researcher -> software developer -> free-lance puzzle designer

… to be continued

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Tag Cloud

%d bloggers like this: