MIME-Version: 1.0 Server: CERN/3.0 Date: Tuesday, 07-Jan-97 15:56:40 GMT Content-Type: text/html Content-Length: 24367 Last-Modified: Wednesday, 16-Oct-96 15:34:49 GMT
This paper reviews our recent work on applying inductive logic programming to the construction of natural language processing systems. We have developed a system, CHILL, that learns a parser from a training corpus of parsed sentences by inducing heuristics that control an initial overly-general shift-reduce parser. CHILL learns syntactic parsers as well as ones that translate English database queries directly into executable logical form. The ATIS corpus of airline information queries was used to test the acquisition of syntactic parsers, and CHILL performed competitively with recent statistical methods. English queries to a small database on U.S. geography were used to test the acquisition of a complete natural language interface, and the parser that CHILL acquired was more accurate than an existing hand-coded system. The paper also includes a discussion of several issues this work has raised regarding the capabilities and testing of ILP systems as well as a summary of our current research directions.
Proceedings of the 1996 Conference on Empirical Methods in
Natural Language Processing, pp. 82-91, Philadelphia, PA, May
1996..
This paper describes an experimental comparison of seven different learning
algorithms on the problem of learning to disambiguate the meaning of a word
from context. The algorithms tested include statistical, neural-network,
decision-tree, rule-based, and case-based classification techniques. The
specific problem tested involves disambiguating six senses of the word ``line''
using the words in the current and proceeding sentence as context. The
statistical and neural-network methods perform the best on this particular
problem and we discuss a potential reason for this observed difference. We
also discuss the role of bias in machine learning and its importance in
explaining performance differences observed on specific problems.
Proceedings of the Thirteenth National Conference on Aritificial Intelligence,
pp. 1050-1055, Portland, OR, August, 1996. (AAAI-96)
This paper presents recent work using the CHILL parser acquisition
system to automate the construction of a natural-language interface
for database queries. CHILL treats parser acquisition as the learning
of search-control rules within a logic program representing a
shift-reduce parser and uses techniques from Inductive Logic
Programming to learn relational control knowledge. Starting with a
general framework for constructing a suitable logical form, CHILL is
able to train on a corpus comprising sentences paired with database
queries and induce parsers that map subsequent sentences directly into
executable queries. Experimental results with a complete
database-query application for U.S. geography show that CHILL is able
to learn parsers that outperform a pre-existing, hand-crafted
counterpart. These results demonstrate the ability of a corpus-based
system to produce more than purely syntactic representations. They
also provide direct evidence of the utility of an empirical approach
at the level of a complete natural language application.
Technical Report, Artificial Intelligence Lab,
University of Texas at Austin, 1996.
This paper defines a new machine learning problem to which standard
machine learning algorithms cannot easily be applied. The problem
occurs in the domain of lexical acquisition. The ambiguous and
synonymous nature of words causes the difficulty of using standard
induction techniques to learn a lexicon. Additionally, negative
examples are typically unavailable or difficult to construct in this
domain. One approach to solve the lexical acquisition problem is
presented, along with preliminary experimental results on an
artificial corpus. Future work includes extending the algorithm and
performing tests on a more realistic corpus.
Submitted to the 34th Annual Meeting of the Association for Computational Linguistics (ACL-96).
We present a knowledge and context-based system for parsing natural language
and evaluate it on sentences from the Wall Street Journal.
Applying machine learning techniques, the system uses parse action examples
acquired under supervision to generate a deterministic shift-reduce parser
in the form of a decision structure. It relies heavily on context, as encoded
in features which describe the morpholgical, syntactical, semantical and
other aspects of a given parse state.
Ph.D. proposal, Department of Computer Sciences, University of Texas
at Austin, 1995.
Building accurate and efficient natural language processing (NLP)
systems is an important and difficult problem. There has been
increasing interest in automating this process. The lexicon, or the
mapping from words to meanings, is one component that is typically
difficult to update and that changes from one domain to the next.
Therefore, automating the acquisition of the lexicon is an important
task in automating the acquisition of NLP systems. This proposal
describes a system, WOLFIE (WOrd Learning From Interpreted Examples),
that learns a lexicon from input consisting of sentences paired with
representations of their meanings. Preliminary experimental results
show that this system can learn correct and useful mappings. The
correctness is evaluated by comparing a known lexicon to one learned
from the training input. The usefulness is evaluated by examining the
effect of using the lexicon learned by WOLFIE to assist a parser
acquisition system, where previously this lexicon had to be
hand-built. Future work in the form of extensions to the algorithm,
further evaluation, and possible applications is discussed.
Symbolic, Connectionist, and Statistical Approaches to Learning for Natural
Language Processing, S. Wermter, E. Riloff and G. Scheler, Eds,
Spring Verlag, 1996.
This paper presents results from recent experimenets with CHILL, a
corpus-based parser acquisition system. CHILL treats language
acquisition as the learning of search-control rules within a logic
program. Unlike many current corpus-based approaches that use
statistical learning algorithms, CHILL uses techniques from inductive
logic programming (ILP) to learn relational representations. CHILL is
a very flexible system and has been used to learn parsers that produce
syntactic parse trees, case-role analyses, and executable database
queries. The reported experiments compare CHILL's performance to that
of a more naive application of ILP to parser acquisition. The results
show that ILP techniques, as employed in CHILL, are a viable
alternative to statistical methods and that the control-rule framework
is fundamental to CHILL's success.
Symbolic, Connectionist, and Statistical Approaches to Learning for Natural
Language Processing, S. Wermter, E. Riloff and G. Scheler, Eds,
Spring Verlag, 1996.
This paper presents results on using a new inductive logic programming
method called FOIDL to learn the past tense of English verbs. The past
tense task has been widely studied in the context of the
symbolic/connectionist debate. Previous papers have presented results
using various neural-network and decision-tree learning methods. We
have developed a technique for learning a special type of Prolog
program called a first-order decision list, defined as an
ordered list of clauses each ending in a cut. FOIDL is based on FOIL
(Quinlan, 1990) but employs intensional background knowledge and
avoids the need for explicit negative examples. It is particularly
useful for problems that involve rules with specific exceptions, such
as the past-tense task. We present results showing that FOIDL learns
a more accurate past-tense generator from significantly fewer examples
than all other previous methods.
This dissertation details the architecture, implementation and
evaluation of CHILL a computer system for acquiring natural
language parsers by training over corpora of parsed text. CHILL
treats language acquisition as the learning of search-control rules
within a logic program that implements a shift-reduce parser. Control
rules are induced using a novel ILP algorithm which handles difficult
issues arising in the induction of search-control heuristics. Both
the control-rule framework and the induction algorithm are crucial to
CHILL's success.
The main advantage of CHILL over propositional counterparts is
its flexibility in handling varied representations. CHILL has
produced parsers for various analyses including case-role mapping,
detailed syntactic parse trees, and a logical form suitable for
expressing first-order database queries. All of these tasks are
accomplished within the same framework, using a single, general
learning method that can acquire new syntactic and semantic categories
for resolving ambiguities.
Experimental evidence from both aritificial and real-world corpora
demonstrate that CHILL learns parsers as well or better than
previous artificial neural network or probablistic approaches on
comparable tasks. In the database query domain, which goes beyond the
scope of previous empirical approaches, the learned parser outperforms
an existing hand-crafted system. These results support the claim that
ILP techniques as implemented in CHILL represent a viable
alternative with significant potential advantages over neural-network,
propositional, and probablistic approaches to empirical parser
construction.
Ph.D. Thesis, Deparment of Computer Sciences, University of Texas at Austin, August, 1995.
Designing computer systems to understand natural language input is a
difficult task. In recent years there has been considerable interest
in corpus-based methods for constructing natural language parsers.
These empirical approaches replace hand-crafted grammars with
linguistic models acquired through automated training over language
corpora. A common thread among such methods to date is the use of
propositional or probablistic representations for the learned
knowledge. This dissertation presents an alternative approach based
on techniques from a subfield of machine learning known as inductive
logic programming (ILP). ILP, which investigates the learning of
relational (first-order) rules, provides an empirical method for
acquiring knowledge within traditional, symbolic parsing frameworks.
A system, WOLFIE, that acquires a mapping of words to their semantic
representation is presented and a preliminary evaluation is performed.
Tree least general generalizations (TLGGs) of the representations of input
sentences are performed to assist in determining the representations
of individual words in the sentences. The best guess for a meaning
of a word is the TLGG which overlaps with the highest percentage of
sentence representations in which that word appears.
Some promising experimental results on a non-artificial data
set are presented.
Submitted to Computational Lingusitics
In recent years there has been considerable research into corpus-based
methods for parser construction. A common thread in this research has
been the use of propositional representations for learned knowledge.
This paper presents an alternative approach based on techniques from a
subfield of machine learning known as inductive logic programming
(ILP). ILP, which investigates the learning of relational
(first-order) rules, provides a way of using empricial methods to
acquire knowledge within traditional, symbolic parsing frameworks. We
describe a novel method for constructing deterministic Prolog parsers
from corpora of parsed sentences. We also discuss several advantages
of this approach compared to propositional alternatives and present
experimental results on learning complete parsers using several
corpora including the ATIS corpus from the Penn Treebank.
Working Notes of the IJCAI-95 Workshop on New Approaches to
Learning for Natural Language Processing, pp.79-86, Montreal,
Quebec, August, 1995.
This paper presents results from recent experiments with CHILL,
a corpus-based parser acquisition system. CHILL treats grammar
acquisition as the learning of search-control rules within a logic
program. Unlike many current corpus-based approaches that use
propositional or probabilistic learning algorithms, CHILL uses
techniques from inductive logic programming (ILP) to learn relational
representations. The reported experiments compare CHILL's
performance to that of a more naive application of ILP to parser
acquisition. The results show that ILP techniques, as employed in
CHILL, are a viable alternative to propositional methods and
that the control-rule framework is fundamental to CHILL's
success.
Proceedings of the Fifth International Workshop on Inductive Logic
Programming, Leuven, Belguim, Sepetember 1995. This paper presents a method for learning logic programs
without explicit negative examples by exploiting an assumption of
output completeness. A mode declaration is supplied for the
target predicate and each training input is assumed to be accompanied
by all of its legal outputs. Any other outputs generated by an
incomplete program implicitly represent negative examples; however,
large numbers of ground negative examples never need to be generated.
This method has been incorporated into two ILP systems, CHILLIN and
IFOIL, both of which use intensional background knowledge. Tests on
two natural language acquisition tasks, case-role mapping and
past-tense learning, illustrate the advantages of the approach.
Journal of Artificial Intelligence Research, 3 (1995) pp. 1-24.
This paper presents a method for inducing logic programs from examples that
learns a new class of concepts called first-order decision lists, defined
as ordered lists of clauses each ending in a cut. The method, called FOIDL,
is based on FOIL but employs intensional background knowledge and avoids
the need for explicit negative examples. It is particularly useful for
problems that involve rules with specific exceptions, such as learning the
past-tense of English verbs, a task widely studied in the context of the
symbolic/connectionist debate. FOIDL is able to learn concise, accurate
programs for this problem from significantly fewer examples than previous
methods (both connectionist and symbolic).
John M. Zelle and Raymond J. Mooney
Proceedings of the Twelfth National Conference on
AI, pp. 748-753, Seattle, WA, July 1994. (AAAI-94)
This paper presents a method for constructing deterministic, context-sensitive,
Prolog parsers from corpora of parsed sentences. Our approach uses recent
machine learning methods for inducing Prolog rules from examples (inductive
logic programming). We discuss several advantages of this method compared to
recent statistical methods and present results on learning complete parsers
from portions of the ATIS corpus.
John M. Zelle
Ph.D. proposal, Department of Computer Sciences, University of Texas
at Austin, 1993.
This paper presents a general framework, learning
search-control heuristics for logic programs, which can be used to
improve both the efficiency and accuracy of knowledge-based systems
expressed as definite-clause logic programs. The approach combines
techniques of explanation-based learning and recent advances in
inductive logic programming to learn clause-selection heuristics that
guide program execution. Two specific applications of this framework
are detailed: dynamic optimization of Prolog programs (improving
efficiency) and natural language acquisition (improving accuracy). In
the area of program optimization, a prototype system, DOLPHIN, is able
to transform some intractable specifications into polynomial-time
algorithms, and outperforms competing approaches in several benchmark
speedup domains. A prototype language acquisition system, CHILL, is
also described. It is capable of automatically acquiring semantic
grammars, which uniformly incorprate syntactic and semantic
constraints to parse sentences into case-role representations.
Initial experiments show that this approach is able to construct
accurate parsers which generalize well to novel sentences and
significantly outperform previous approaches to learning case-role
mapping based on connectionist techniques. Planned extensions of the
general framework and the specific applications as well as plans for
further evaluation are also discussed.
John M. Zelle and Raymond J. Mooney
Proceedings of the Eleventh National Conference of the American
Association for Artificial Intelligence, pp. 817-822,
Washington, D.C. July 1993 (AAAI-93).
Automating the construction of semantic grammars is a difficult and
interesting problem for machine learning. This paper shows how the
semantic-grammar acquisition problem can be viewed as the learning of
search-control heuristics in a logic program. Appropriate control
rules are learned using a new first-order induction algorithm that
automatically invents useful syntactic and semantic categories.
Empirical results show that the learned parsers generalize well to
novel sentences and out-perform previous approaches based on
connectionist techniques.