From: Patrick Haluptzok (patrickh_at_windows.microsoft.com)
Date: Sun Dec 07 2003 - 10:41:43 PST
Paper Review #6 - by Patrick Haluptzok - CSE 573 Fall 2003
Paper title/Author: Proverb: The Probabilistic Cruciverbalist, By Greg Keim, Noam Shazeer, Michael Littman ...
One-line summary: Describes a method for solving crossword puzzles by combining scored word list proposals from a variety of expert modules to find the most likely assignment of words to solve the cross-word puzzle.
The (two) most important ideas in the paper, and why: One important idea was coming up with a system for combining the word lists from different experts based on the confidence and word list weighting each expert assigned. Many of the expert modules produced their word lists in very different ways, so normalizing the score they produce for each word proposed and taking into account the confidence each expert module had in the list provided was important to make the system successful. For each expert module there was a normalizing factor per letter, per word and a confidence value - (length-scale, scale, and spread) which were tuned via hill-climbing to integrate the information optimally.
Another important idea was assigning the words to the crossword puzzle to maximize the probability of the solution. The constraint satisfaction problem of assigning words to the puzzle is done as a search to find the most likely assignment of words given their likelihood assigned by the expert modules.
The one or two largest flaws in the paper: One flaw in my opinion was the great deal of intense manual construction of expert modules to solve the problem. It was a great deal of engineering, as opposed to an approach that learned how to harvest independent information sources - but that would be a much harder problem. It was a lot like Chess solutions, very problem specific and the method isn't easily transferable to a new problem domain.
The assignment to words to the crossword puzzle wasn't discussed in detail - I think I understand how they did it, but there may be tricks or optimizations to doing that efficiently, I assume it is an A* type algorithm, guaranteeing the best log prob score assignment from the lists proposed.
Identify two important, open research questions on the topic, and why they matter: The problem solution is really a giant probabilistic CSP that grinds out a solution with a lot of hand-code domain expertise applied. I would like to see if there is a way to present the problem, maybe even as a series of simpler problems with growing complexity with information sources where solutions can be learned automatically or induced, as opposed to hand-coding up the features and search directly. That is important because such an approach would be applicable to many other diverse problem domains.
From an NLP point of view I'm sure there probably could be more powerful expert modules that do more semantic analysis to give better word list guesses that could be explored.
Automated Theory Formation in Mathematics
By Douglas Lenat
Certainly 25 years later we have vastly more computational power and significant advances in the efficiency of the algorithms for solving CSP, planning problems and machine learning for much better pattern matching. But his problem was a search for finding math concepts and didn't really have a good heuristic to guide it, there wasn't a fitness function or a performance measure to tell it what it was learning was good, it seems like more computational power could send it farther off in strange areas finding concepts of dubious value - it seemed like it required too much human guidance and setup. In the very last part of the first section he discusses how people create theories, essentially by clustering their real life experience, looking for the simplest patterns that explain the most data observed - but it doesn't seem like that approach is then followed.
This archive was generated by hypermail 2.1.6 : Sun Dec 07 2003 - 10:41:52 PST