On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms

Details On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms

1995-07-24

arxiv.org/abs/cmp-lg/9507010v2

Proc. of The 12th Int. Conf. on Machine Learning, 1995

Computer Science

Computation and Language

9 pages, uuencoded compressed postscript

Scientific paper

We consider the problem of learning a certain type of lexical semantic knowledge that can be expressed as a binary relation between words, such as the so-called sub-categorization of verbs (a verb-noun relation) and the compound noun phrase relation (a noun-noun relation). Specifically, we view this problem as an on-line learning problem in the sense of Littlestone's learning model in which the learner's goal is to minimize the total number of prediction mistakes. In the computational learning theory literature, Goldman, Rivest and Schapire and subsequently Goldman and Warmuth have considered the on-line learning problem for binary relations R : X * Y -> {0, 1} in which one of the domain sets X can be partitioned into a relatively small number of types, namely clusters consisting of behaviorally indistinguishable members of X. In this paper, we extend this model and suppose that both of the sets X, Y can be partitioned into a small number of types, and propose a host of prediction algorithms which are two-dimensional extensions of Goldman and Warmuth's weighted majority type algorithm proposed for the original model. We apply these algorithms to the learning problem for the `compound noun phrase' relation, in which a noun is related to another just in case they can form a noun phrase together. Our experimental results show that all of our algorithms out-perform Goldman and Warmuth's algorithm. We also theoretically analyze the performance of one of our algorithms, in the form of an upper bound on the worst case number of prediction mistakes it makes.

Affiliated with

Also associated with

No associations

Rating

On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-line Learning of Binary Lexical Relations Using Two-dimensional Weighted Majority Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-102961