Learnability of Translations from Positive Examples

Author: Noriko Sugimoto

Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 169 - 178.

Abstract. One of the most important issues in machine translations is deducing unknown rules from pairs of input-output sentences. Since the translations are expressed by elementary formal systems (EFS's, for short), we formalize learning translations as the process of guessing an unknown EFS from pairs of input-output sentences. In this paper, we propose a class of EFS's called linearly-moded EFS's by introducing local variables and linear predicate inequalities based on mode information, which can express translations of context-sensitive languages. We show that, for a given input sentence, the set of all output sentences is finite and computable in a translation defined by a linearly-moded EFS. Finally, we show that the class of translations defined by linearly-moded EFS's is learnable under the condition that the number of clauses in an EFS and the length of the clause are bounded by some constant.

©Copyright 1998 Springer