Alignment via Mutual Information (2023)

Abstract: Many language learning tasks require learners to infer correspondences between data in two modalities. Often, these alignments are many-to-many and context-sensitive. For example, translating into morphologically rich languages requires learning not just how words, but morphemes, should be translated; words and morphemes may have different meanings (or groundings) depending on the context in which they are used. We describe an information-theoretic approach to context-sensitive, many-to-many alignment. Our approach first trains a masked sequence model to place distributions over missing spans in (source, target) sequences. Next, it uses this model to compute pointwise mutual information between source and target spans conditional on context. Finally, it aligns spans with high mutual information. We apply this approach to two learning problems: character-based word translation (using alignments for joint morphological segmentation and lexicon learning) and visually grounded reference resolution (using alignments to jointly localize referents and learn word meanings). In both cases, our proposed approach outperforms both structured and neural baselines, showing that conditional mutual information offers an effective framework for formalizing alignment problems in general domains.

## introduction natural language is compositional: meanings of complex utterances can be constructed by combining the meanings of their atomic constituents @xcite . as a consequence, many canonical language learning problems, from machine translation to grounded word learning, require learners to infer what these constituents are, and how they align across modalities (e.g. between english and spanish, or english and the visual world). fig. 1 shows an example: in order to translate discography into spanish, it is necessary to know that the morpheme graph should be translated into graf, the affix y into ía, etc. formally, given paired data (x, y) (e.g. sentences and translations) an alignment algorithm must return a collection of span pairs {(x i , y i )} where each x i and y i are contiguous sub-sequences of x and y respectively, and have the same meaning. most alignment algorithms assume that both x and y are sequences pre-segmented into words or word pieces (e.g. @xcite , and that phrase-level alignments are ultimately reducible to word-level ones. but this assumption is quite restrictive: it limits these algorithms' applicability in languages with complex morphology or where segmentation is otherwise more complex. more importantly, it means that these algorithms cannot be applied to problems involving non-linguistic (e.g. visual) data, in which it is possible that every observed fragment of an input will consist of a unique observation (e.g. set of pixel values). indeed, we are not aware of any existing alignment algorithms that can be applied agnostically in both settings. many alignment also make strong context-independence assumptions-for example, that each word in a sentence is translated or interpreted independently. this assumption can make it difficult to infer alignments in problems where language use is highly contextual (e.g. in the presence of polysemy, @xcite . how might we formulate the alignment problem in a way that accommodates unknown segment boundaries, context-dependence, and both linguistic and non-linguistic data? in this paper, we offer an information-theoretic framing of alignment: segments x i and y i are aligned if they have high pointwise mutual information (pmi) in the contexts where they occur. this approach avoids assumptions about data modality and segmentation (as pmi is straightforward to calculate for arbitrary spans in inputs of arbitrary types), and about con- figure 1 : infoalign: deriving alignments from conditional pointwise mutual information (pmi) using masked language models. we first train neural sequence models to reconstruct masked portions of paired sequences (e.g. characters forming words). this model is trained to assign probabilities to pairs of masked regions jointly and marginally (as in the two bottom terms on the right side of the figure). finally, these models are used to compute conditional pmi between arbitrary span pairs. we use these scores to extract bilingual lexicons and resolve references in grounded tasks. our approach, which we call infoalign, first trains masked sequence models to compute joint and marginal probabilities of sub-spans of x and y in context, then uses these models to compute mutual information between spans. using this spanscoring procedure, we define algorithms for extracting flat or hierarchical correspondences between modalities. we use these extracted alignments for two tasks: learning a morpheme-level lexicon to support zero-shot word translation in a low-data setting, and learning grounded representations of word meaning in a pragmatic reference task. in both settings, infoalign outperforms both neural and structured appraoches to learning many-tomany alignments. ## background and related work at an intuitive level, given joint distribution over pairs of sequences (x, y), alignment algorithms seek to find correspondences between "pieces" of x and y. depending on the nature of the task, the granularity of these pieces may or may not be known. for instance, word or character level alignments operate over well-defined units. morpheme or phrase alignments, on the other hand, often require joint induction of alignments and the units themselves. generative alignment models some of the earliest alignment models came from the machine translation literature (e.g. @xcite , which define generative models of sentences in a source language given sentences in a target language mediated by latent alignments, sometimes constrained to be tree-structured @xcite . models infer these alignments jointly with a translation lexicon. however, they make strong conditional independence assumptions about the meanings of source tokens, and provide only one-to-many mappings between source and target tokens. while these word alignments may be used as a starting point for phrase-level extraction @xcite , they generally cannot be used when tokens are individually meaningless and non-alignable. most relevant to the current work, faruqui and dyer (2013) perform bilingual lexicon induction using parallel corpora by searching for words that share high mutual information. the approach we describe shares similar intuition but leverages general-purpose sequence models to enable context-sensitive alignment without requiring word-level correspondences. ## approach what do the various appraoches to alignment described above have in common? in general, we expect a span x i to be aligned to a span y i if the two spans contain information about each other. in fig. 1 , it becomes easier to predict that one of the masked segments is graph knowing that the other masked segment is graf, and vice-versa. in fact, (graph, graf ) is one of only a small number of pairs for which this is true: if we had instead masked (graph, disco), knowing the contents of one gap would not have made it any easier to predict the other one, because all requisite information would already be available in the context. intuitively, graph and graf contain information about each other, while graph and disco do not. this intuition can be formalized in terms of pointwise mutual information (pmi) @xcite . given random variables x i and y i , the pmi between two outcomes x i and y i is defined as: via eq. ( 2 ), pmi may be understood as quantifying how much our confidence in the outcome x i increases after observing y i . this definition can also be extended to the conditional setting: given some other random variable z, we may write: in the context of alignment, if x i and y i are spans, and z is the context in which they occur, x i and y i should be aligned precisely when their pmi (conditioned on z) is large. infoalign operationalizes this notion by first building a probabilistic model of source and target sequences, using this model to score spans based on conditional pmi, then uses scores to find the highest-scoring span alignments. below, we describe each of these steps in more detail. ## experiments: translation our first set of experiments focuses on learning to translate words (at the character level) by learning a morphological lexicon. in this task, models are trained set of inflected word pairs in source and target languages, and evaluated on their ability to translate novel word forms. generalization of this kind is only possible with a correct model of the internal morphological structure of words: ## experiments: reference resolution our other experiments focus on a grounded reference resolution task. in this task, referring expressions are generated in a highly ambiguous perceptual context; at training time, learners must jointly infer word meanings and their context-dependent referents; at evaluation time, learners must resolve references for new inputs. ## limitations one major limitation of the proposed approach is runtime. applying this method to extract a structured lexicon, as in section 3.3, is computationally costly, especially in the presence of deeper structures than investigated here. extracting these correspondences requires more effort than inspecting the behavior of a (quadratic-time) attention mechanism. additionally, pmi can only be computed if we have the ability to assign a normalized probability to a masked sequence. outside of language domains, many of today's most sophisticated generative models (including gans and diffusion models) define intractable probability distributions, meaning that additional modeling work will be required to scale infoalign to these more complex domains (e.g. images). ## conclusion we have presented infoalign, an informationtheoretic approach to alignment that can identify context-dependent, span level correspondences between inputs in multiple modalities. infoalign outperforms both classical unit discovery and neural sequence modeling approaches in both word translation and reference resolution domains. more broadly, infoalign offers a new approach for thinking about what an alignment is in domains where the primitive elements of alignment (analogous to words in machine translation) are unknown, and complete @xmath0. by deriving alignments from information-theoretic measures, we can use the modern neural sequence modeling toolkit to obtain meaningful correspondences between data of diverse types.