Learnability of Translations from Positive Examples

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.