Omnibase: Uniform Access to Heterogeneous Data for Question Answering

Boris Katz, Sue Felshin, Deniz Yuret, Ali Ibrahim, Jimmy J. Lin, Gregory Marton, Alton Jerome McFarland, Baris Temelkuran. In Birger Andersson, Maria Bergholtz, Paul Johannesson (Eds.): Natural Language Processing and Information Systems, 6th International Conference on Applications of Natural Language to Information Systems, NLDB 2002, Stockholm, Sweden, June 27-28, 2002, Revised Papers. Lecture Notes in Computer Science 2553 Springer 2002, ISBN 3-540-00307-X.

Abstract: Although the World Wide Web contains a tremendous amount of information, the lack of uniform structure makes finding the right knowledge difficult. A solution is to turn the Web into a virtual database and to access it through natural language. We built Omnibase, a system that integrates heterogeneous data sources using an object-property-value model. With the help of Omnibase, our Start natural language system can now access numerous heterogeneous data sources on the Web in a uniform manner, and answers millions of user questions with high precision.

Download PDF.

Full post... Related link

Alpha-beta-conspiracy search

David McAllester and Deniz Yuret. ICGA Journal Vol. 25, No. 1 - March 2002 (PDF)

Abstract: We introduce a variant of α-β search in which each node is associated with two depths rather than one. The purpose of α-β search is to find strategies for each player that together establish a value for the root position. A max strategy establishes a lower bound and the min strategy establishes an upper bound. It has long been observed that forced moves should be searched more deeply. Here we make the observation that in the max strategy we are only concerned with the forcedness of max moves and in the min strategy we are only concerned with the forcedness of min moves. This leads to two measures of depth --- one for each strategy --- and to a two-depth variant of α-β called ABC search. The two-depth approach can be formally derived from conspiracy theory and the structure of the ABC procedure is justified by two theorems relating ABC search and conspiracy numbers.

Full post... Related link

Discovery of Linguistic Relations Using Lexical Attraction

Deniz Yuret, PhD Thesis, MIT, May 1998. (HTML, PDF, PS.GZ, Slides, Summary paper)

Abstract
This work has been motivated by two long term goals: to understand how humans learn language and to build programs that can understand language. Using a representation that makes the relevant features explicit is a prerequisite for successful learning and understanding. Therefore, I chose to represent relations between individual words explicitly in my model. Lexical attraction is defined as the likelihood of such relations. I introduce a new class of probabilistic language models named lexical attraction models which can represent long distance relations between words and I formalize this new class of models using information theory.

Within the framework of lexical attraction, I developed an unsupervised language acquisition program that learns to identify linguistic relations in a given sentence. The only explicitly represented linguistic knowledge in the program is lexical attraction. There is no initial grammar or lexicon built in and the only input is raw text. Learning and processing are interdigitated. The processor uses the regularities detected by the learner to impose structure on the input. This structure enables the learner to detect higher level regularities. Using this bootstrapping procedure, the program was trained on 100 million words of Associated Press material and was able to achieve 60% precision and 50% recall in finding relations between content-words. Using knowledge of lexical attraction, the program can identify the correct relations in syntactically ambiguous sentences such as ``I saw the Statue of Liberty flying over New York.''

Full post...

From genetic algorithms to efficient optimization

Yuret, D. (1994) MS Thesis. Massachusetts Institute of Technology. A.I. Technical Report No. 1569 (PDF,HTML)

I developed an optimization algorithm known as Dynamic Hill Climbing (DHC) with Michael de la Maza, which is the subject of my MS Thesis, also AI Technical Report 1569. Below is the abstract and a list of papers on DHC.

Abstract: The work described in this thesis began as an inquiry into the nature and use of optimization programs based on ``genetic algorithms.'' That inquiry led, eventually, to three powerful heuristics that are broadly applicable in gradient-ascent programs: First, remember the locations of local maxima and restart the optimization program at a place distant from previously located local maxima. Second, adjust the size of probing steps to suit the local nature of the terrain, shrinking when probes do poorly and growing when probes do well. And third, keep track of the directions of recent successes, so as to probe preferentially in the direction of most rapid ascent.
These algorithms lie at the core of a novel optimization program that illustrates the power to be had from deploying them together. The efficacy of this program is demonstrated on several test problems selected from a variety of fields, including De Jong's famous test-problem suite, the traveling salesman problem, the problem of coordinate registration for image guided surgery, the energy minimization problem for determining the shape of organic molecules, and the problem of assessing the structure of sedimentary deposits using seismic data.

Related publications:

• Michael de la Maza and Deniz Yuret (1995) Seeing clearly: Medical imaging now and tomorrow. In Clifford A. Pickover, editor, Future Health: Computers and Medicine in the 21st Century. St. Martin's Press.
• Michael de la Maza and Deniz Yuret (1994) Dynamic hill climbing. AI Expert.
• Deniz Yuret and Michael de la Maza (1993) Dynamic hill climbing: Overcoming the limitations of optimization techniques. In The Second Turkish Symposium on Artificial Intelligence and Neural Networks.

Full post...