Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Feature Engineering and Constraints <s> We present an effective training algorithm for linearly-scored dependency parsers that implements online large-margin multi-class training (Crammer and Singer, 2003; Crammer et al., 2003) on top of efficient parsing techniques for dependency trees (Eisner, 1996). The trained parsers achieve a competitive dependency accuracy for both English and Czech with no language specific enhancements. <s> BIB001 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Feature Engineering and Constraints <s> It has been established that incorporating word cluster features derived from large unlabeled corpora can significantly improve prediction of linguistic structure. While previous work has focused primarily on English, we extend these results to other languages along two dimensions. First, we show that these results hold true for a number of languages across families. Second, and more interestingly, we provide an algorithm for inducing cross-lingual clusters and we show that features derived from these clusters significantly improve the accuracy of cross-lingual structure prediction. Specifically, we show that by augmenting direct-transfer systems with cross-lingual cluster features, the relative error of delexicalized dependency parsers, trained on English treebanks and transferred to foreign languages, can be reduced by up to 13%. When applying the same method to direct transfer of named-entity recognizers, we observe relative improvements of up to 26%. <s> BIB002 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Feature Engineering and Constraints <s> We present a novel algorithm for multilingual dependency parsing that uses annotations from a diverse set of source languages to parse a new unannotated language. Our motivation is to broaden the advantages of multilingual learning to languages that exhibit significant differences from existing resource-rich languages. The algorithm learns which aspects of the source languages are relevant for the target language and ties model parameters accordingly. The model factorizes the process of generating a dependency tree into two steps: selection of syntactic dependents and their ordering. Being largely language-universal, the selection component is learned in a supervised fashion from all the training languages. In contrast, the ordering decisions are only influenced by languages with similar properties. We systematically model this cross-lingual sharing using typological features. In our experiments, the model consistently outperforms a state-of-the-art multi-lingual parser. The largest improvement is achieved on the non Indo-European languages yielding a gain of 14.4%. <s> BIB003 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Feature Engineering and Constraints <s> Accurate multilingual transfer parsing typically relies on careful feature engineering. In this paper, we propose a hierarchical tensor-based approach for this task. This approach induces a compact feature representation by combining atomic features. However, unlike traditional tensor models, it enables us to incorporate prior knowledge about desired feature interactions, eliminating invalid feature combinations. To this end, we use a hierarchical structure that uses intermediate embeddings to capture desired feature combinations. Algebraically, this hierarchical tensor is equivalent to the sum of traditional tensors with shared components, and thus can be effectively trained with standard online algorithms. In both unsupervised and semi-supervised transfer scenarios, our hierarchical tensor consistently improves UAS and LAS over state-of-theart multilingual transfer parsers and the traditional tensor model across 10 different languages. 1 <s> BIB004
The most common usage of typological features in NLP is in feature engineering and constraint design for machine learning algorithms. Two popular approaches we consider here are language transfer with selective sharing, where the parameters of languages with similar typological features are tied together ( § 5.2.1), and joint multilingual learning, where typological information is used in order to bias models to reflect the properties of specific languages (see § 5.2.2). and was subsequently adopted by BIB002 and BIB004 . It aims at parsing sentences in a language transfer setting (see § 3.1) where there are multiple source languages and a single unobserved target language. It assumes that head-modifier relations between PoS pairs are universal, but the order of parts of speech within a sentence is language-specific. For instance, adjectives always modify nouns, but in Igbo (Niger-Congo) they linearly precede nouns, and in Nihali (isolate) they follow nouns. Leveraging this intuition, selective sharing models learn dependency relations from all source languages, while ordering is learned from typologically related languages only. Selective sharing was originally implemented in a generative framework, factorizing the recursive generation of dependency tree fragments into two steps BIB003 . The first one is universal: The algorithm selects an unordered (possibly empty) set of modifiers {M} given a head h with probability P({M}|h), where both the head and the modifiers are characterized by their PoS tags. The second step is language-specific: Each dependent m is assigned a direction d (left or right) with respect to h based on the language l, with probability P(d|m, h, l). Dependents in the same direction are eventually ordered with a probability drawn from a uniform distribution over their possible unique permutations. The total probability is then defined as follows: In Equation (1), the first step is expressed as two factors: the estimation of the number n of modifiers, parametrized by θ 1 , and the actual selection of modifiers, parametrized by θ 2 , with the softmax function σ converting the n values into probabilities. The second step, overseeing the assignment of a direction to the dependencies, is parametrized by w, which multiplies a feature function g(), whose arguments include a typology feature vector f l . The values of all the parameters are estimated by maximizing the likelihood of the observations. BIB002 proposed a discriminative version of the model, in order to amend the alleged limitations of the original generative variant. In particular, they dispose of the strong independence assumptions (e.g., between choice and ordering of modifiers) and invalid feature combinations. For instance, the WALS feature "Order of Subject, Verb, and Object" (81A) should be taken into account only when the head under consideration is a verb and the dependent is a noun, but in the generative model this feature was fed to g() regardless of the head-dependency pair. The method of Täckström, McDonald, and Nivre is a delexicalized, first-order, graph-based parser, based on a carefully selected feature set. From the set proposed by BIB001 , they keep only (universal) features describing selectional preferences and dependency length. Moreover, they introduce (languagespecific) features for the directionality of dependents, based on combinations of the PoS tags of the head and modifiers with corresponding WALS values. This approach was further extended to tensor-based models by BIB004 , in order to avoid the shortcomings of manual feature selection. They induce a compact hidden representation of features and languages by factorizing a tensor constructed from their combination. The prior knowledge from the typological database enables the model to forbid the invalid interactions, by generating intermediate feature embeddings in a hierarchical structure. In particular, given n words and l dependency relations, each arc h → m is encoded as the tensor product of three feature vectors for heads Φ h ∈ R n , modifiers Φ m ∈ R n , and the arcs Φ h→m ∈ R l . A score is obtained through the inner product of these and the corresponding r rank-1 dense parameter matrices for heads H ∈ R n×r , dependents M ∈ R n×r , and arcs M ∈ R l×r . The resulting embedding is subsequently constrained through a summation with the typological features T u φ t u : 582 Equation (2) shows how the overall score of a labeled dependency is enriched (by element-wise product) with (1) the features and parameters for arc labels Lφ l constrained by the typological vector T l φ t l ; and (2) features and parameters for head contexts H c φ h c and dependent contexts M c φ m c . This loss is optimized within a maximum soft-margin objective through online passive-aggressive updates. The different approaches to selective sharing presented here explicitly deal with cases where the typological features do not match any of the source languages, which may lead learning astray. BIB003 propose a variant of their algorithm where the typological features are not observed (in WALS), treating them as latent variables, and where model parameters are learned in an unsupervised fashion with the Expectation Maximization algorithm  . BIB002 tackle the same problem from the side of ambiguous learning. The discriminative model on the target language is trained on sets of automatically predicted ambiguous labels y. Finally, BIB004 utilize semi-supervised techniques, where only a handful of annotated examples from the target language is available.