Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> In this paper we study a paradigm to generalize online classification algorithms for binary classification problems to multiclass problems. The particular hypotheses we investigate maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarity-score between each prototype and the input instance and sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this paper we introduce the notion of ultraconservativeness. Ultraconservative algorithms are algorithms that update only the prototypes attaining similarity-scores which are higher than the score of the correct label's prototype. We start by describing a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores. We then discuss a specific online algorithm that seeks a set of prototypes which have a small norm. The resulting algorithm, which we term MIRA (for Margin Infused Relaxed Algorithm) is ultraconservative as well. We derive mistake bounds for all the algorithms and provide further analysis of MIRA using a generalized notion of the margin for multiclass problems. We discuss the form the algorithms take in the binary case and show that all the algorithms from the first family reduce to the Perceptron algorithm while MIRA provides a new Perceptron-like algorithm with a margin-dependent learning rate. We then return to multiclass problems and describe an analogous multiplicative family of algorithms with corresponding mistake bounds. We end the formal part by deriving and analyzing a multiclass version of Li and Long's ROMMA algorithm. We conclude with a discussion of experimental results that demonstrate the merits of our algorithms. <s> BIB001 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> In typical classification tasks, we seek a function which assigns a label to a single object. Kernel-based approaches, such as support vector machines (SVMs), which maximize the margin of confidence of the classifier, are the method of choice for many such tasks. Their popularity stems both from the ability to use high-dimensional feature spaces, and from their strong theoretical guarantees. However, many real-world tasks involve sequential, spatial, or structured data, where multiple labels must be assigned. Existing kernel-based methods ignore structure in the problem, assigning labels independently to each object, losing much useful information. Conversely, probabilistic graphical models, such as Markov networks, can represent correlations between labels, by exploiting problem structure, but cannot handle high-dimensional feature spaces, and lack strong theoretical generalization guarantees. In this paper, we present a new framework that combines the advantages of both approaches: Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data. We present an efficient algorithm for learning M3 networks based on a compact quadratic program formulation. We provide a new theoretical bound for generalization in structured domains. Experiments on the task of handwritten character recognition and collective hypertext classification demonstrate very significant gains over previous approaches. <s> BIB002 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> Over the last few years, two of the main research directions in machine learning of natural language processing have been the study of semi-supervised learning algorithms as a way to train classiers when the labeled data is scarce, and the study of ways to exploit knowledge and global information in structured learning tasks. In this paper, we suggest a method for incorporating domain knowledge in semi-supervised learning algorithms. Our novel framework unies and can exploit several kinds of task specic constraints. The experimental results presented in the information extraction domain demonstrate that applying constraints helps the model to generate better feedback during learning, and hence the framework allows for high performance learning with significantly less training data than was possible before on these tasks. <s> BIB003 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> We present a novel message passing algorithm for approximating the MAP problem in graphical models. The algorithm is similar in structure to max-product but unlike max-product it always converges, and can be proven to find the exact MAP solution in various settings. The algorithm is derived via block coordinate descent in a dual of the LP relaxation of MAP, but does not require any tunable parameters such as step size or tree weights. We also describe a generalization of the method to cluster based potentials. The new method is tested on synthetic and real-world problems, and compares favorably with previous approaches. <s> BIB004 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> This paper presents a semi-supervised training method for linear-chain conditional random fields that makes use of labeled features rather than labeled instances. This is accomplished by using generalized expectation criteria to express a preference for parameter settings in which the model’s distribution on unlabeled data matches a target distribution. We induce target conditional probability distributions of labels given features from both annotated feature occurrences in context and adhoc feature majority label assignment. The use of generalized expectation criteria allows for a dramatic reduction in annotation time by shifting from traditional instance-labeling to feature-labeling, and the methods presented outperform traditional CRF training and other semi-supervised methods when limited human effort is available. <s> BIB005 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> We present posterior regularization, a probabilistic framework for structured, weakly supervised learning. Our framework efficiently incorporates indirect supervision via constraints on posterior distributions of probabilistic models with latent variables. Posterior regularization separates model complexity from the complexity of structural constraints it is desired to satisfy. By directly imposing decomposable regularization on the posterior moments of latent variables during learning, we retain the computational efficiency of the unconstrained model while ensuring desired constraints hold in expectation. We present an efficient algorithm for learning with posterior regularization and illustrate its versatility on a diverse set of structural constraints such as bijectivity, symmetry and group sparsity in several large scale experiments, including multi-view learning, cross-lingual dependency grammar induction, unsupervised part-of-speech induction, and bitext word alignment. <s> BIB006 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> We present an approach to grammar induction that utilizes syntactic universals to improve dependency parsing across a range of languages. Our method uses a single set of manually-specified language-independent rules that identify syntactic dependencies between pairs of syntactic categories that commonly occur across languages. During inference of the probabilistic model, we use posterior expectation constraints to require that a minimum proportion of the dependencies we infer be instances of these rules. We also automatically refine the syntactic categories given in our coarsely tagged input. Across six languages our approach outperforms state-of-the-art unsupervised methods by a significant margin. <s> BIB007 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> This paper introduces a new rigorous theoretical framework to address discrete MRF-based optimization in computer vision. Such a framework exploits the powerful technique of Dual Decomposition. It is based on a projected subgradient scheme that attempts to solve an MRF optimization problem by first decomposing it into a set of appropriately chosen subproblems, and then combining their solutions in a principled way. In order to determine the limits of this method, we analyze the conditions that these subproblems have to satisfy and demonstrate the extreme generality and flexibility of such an approach. We thus show that by appropriately choosing what subproblems to use, one can design novel and very powerful MRF optimization algorithms. For instance, in this manner we are able to derive algorithms that: 1) generalize and extend state-of-the-art message-passing methods, 2) optimize very tight LP-relaxations to MRF optimization, and 3) take full advantage of the special structure that may exist in particular MRFs, allowing the use of efficient inference techniques such as, e.g., graph-cut-based methods. Theoretical analysis on the bounds related with the different algorithms derived from our framework and experimental results/comparisons using synthetic and real data for a variety of tasks in computer vision demonstrate the extreme potentials of our approach. <s> BIB008 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> Vector space word representations are learned from distributional information of words in large corpora. Although such statistics are semantically informative, they disregard the valuable information that is contained in semantic lexicons such as WordNet, FrameNet, and the Paraphrase Database. This paper proposes a method for refining vector space representations using relational information from semantic lexicons by encouraging linked words to have similar vector representations, and it makes no assumptions about how the input vectors were constructed. Evaluated on a battery of standard lexical semantic evaluation tasks in several languages, we obtain substantial improvements starting with a variety of word vector models. Our refinement method outperforms prior techniques for incorporating semantic lexicons into word vector training algorithms. <s> BIB009 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> Combining deep neural networks with structured logic rules is desirable to harness flexibility and reduce uninterpretability of the neural models. We propose a general framework capable of enhancing various types of neural networks (e.g., CNNs and RNNs) with declarative first-order logic rules. Specifically, we develop an iterative distillation method that transfers the structured information of logic rules into the weights of neural networks. We deploy the framework on a CNN for sentiment analysis, and an RNN for named entity recognition. With a few highly intuitive rules, we obtain substantial improvements and achieve state-of-the-art or comparable results to previous best-performing systems. <s> BIB010 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> Canonical correlation analysis (CCA) is a method for reducing the dimension of data represented using two views. It has been previously used to derive word embeddings, where one view indicates a word, and the other view indicates its context. We describe a way to incorporate prior knowledge into CCA, give a theoretical justification for it, and test it by deriving word embeddings and evaluating them on a myriad of datasets. <s> BIB011 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> Morphologically rich languages accentuate two properties of distributional vector space models: 1) the difficulty of inducing accurate representations for low-frequency word forms; and 2) insensitivity to distinct lexical relations that have similar distributional signatures. These effects are detrimental for language understanding systems, which may infer that 'inexpensive' is a rephrasing for 'expensive' or may not associate 'acquire' with 'acquires'. In this work, we propose a novel morph-fitting procedure which moves past the use of curated semantic lexicons for improving distributional vector spaces. Instead, our method injects morphological constraints generated using simple language-specific rules, pulling inflectional forms of the same word close together and pushing derivational antonyms far apart. In intrinsic evaluation over four languages, we show that our approach: 1) improves low-frequency word estimates; and 2) boosts the semantic quality of the entire word vector collection. Finally, we show that morph-fitted vectors yield large gains in the downstream task of dialogue state tracking, highlighting the importance of morphology for tackling long-tail phenomena in language understanding tasks. <s> BIB012 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> In recent years great success has been achieved in sentiment classification for English, thanks in part to the availability of copious annotated resources. Unfortunately, most languages do not enjoy such an abundance of labeled data. To tackle the sentiment classification problem in low-resource languages without adequate annotated data, we propose an Adversarial Deep Averaging Network (ADAN) to transfer the knowledge learned from labeled data on a resource-rich source language to low-resource languages where only unlabeled data exists. ADAN has two discriminative branches: a sentiment classifier and an adversarial language discriminator. Both branches take input from a shared feature extractor to learn hidden representations that are simultaneously indicative for the classification task and invariant across languages. Experiments on Chinese and Arabic sentiment classification demonstrate that ADAN significantly outperforms state-of-the-art systems. <s> BIB013 </s> Modeling Language Variation and Universals: A Survey on Typological Linguistics for Natural Language Processing <s> Injecting Typological Information into Machine Learning Algorithms <s> Deep learning has emerged as a versatile tool for a wide range of NLP tasks, due to its superior capacity in representation learning. But its applicability is limited by the reliance on annotated examples, which are difficult to produce at scale. Indirect supervision has emerged as a promising direction to address this bottleneck, either by introducing labeling functions to automatically generate noisy examples from unlabeled text, or by imposing constraints over interdependent label decisions. A plethora of methods have been proposed, each with respective strengths and limitations. Probabilistic logic offers a unifying language to represent indirect supervision, but end-to-end modeling with probabilistic logic is often infeasible due to intractable inference and learning. In this paper, we propose deep probabilistic logic (DPL) as a general framework for indirect supervision, by composing probabilistic logic with deep learning. DPL models label decisions as latent variables, represents prior knowledge on their relations using weighted first-order logical formulas, and alternates between learning a deep neural network for the end task and refining uncertain formula weights for indirect supervision, using variational EM. This framework subsumes prior indirect supervision methods as special cases, and enables novel combination via infusion of rich domain and linguistic knowledge. Experiments on biomedical machine reading demonstrate the promise of this approach. <s> BIB014
In § 5, we discussed the potential of typological information to provide guidance to NLP methods, and surveyed approaches such as network design in Bayesian models  , selective sharing (Naseem, Barzilay, and Globerson 2012, inter alia) , and biasing of multilingual joint models (Ammar et al. 2016, inter alia) . However, many other frameworks (including those already mentioned in § 3) have been developed independently in order to allow the integration of expert and domain knowledge into traditional feature-based machine learning algorithms and neural networks. In this section we survey these frameworks and discuss their applicability to the integration of typological information into NLP models. Encoding cross-language variation and preferences into a machine learning model requires a mechanism that can bias the learning (i.e., training and parameter estimation) and inference (prediction) of the model toward some pre-defined knowledge. In practice, learning algorithms, both linear (e.g., structured perceptron  , MIRA BIB001 and structured support vector machine BIB002 ) and non-linear (deep neural models) iterate between an inference step and a step of parameter update with respect to a gold standard. The inference step is the natural place where external knowledge could be encoded through constraints. This step biases the prediction of the model to agree with the external knowledge which, in turn, affects both the training process and the final prediction of the model at test time. Information about cross-lingual variation, particularly when extracted empirically (see § 4), reflects tendencies rather than strict rules. As a consequence, soft, rather than hard constraints are a natural vehicle for their encoding. The goal of an inference algorithm is to predict the best output label according to the current state of the model parameters. 8 For this purpose, the algorithm searches the space of possible output labels in order to find the best one. Efficiency hence plays a key role in these algorithms. Introducing soft constraints into an inference algorithm, therefore, posits an algorithmic challenge: How can the output of the model be biased to agree with the constraints while the efficiency of the search procedure is kept? In this article we do not answer this question directly but rather survey a number of approaches that succeed in dealing with it. Because linear models have been prominent in NLP research for a much longer time, it is not surprising that frameworks for the integration of soft constraints into these models are much more developed. The approaches proposed for this purpose include posterior regularization (PR) BIB006 , generalized expectation (GE) BIB005 , constraint-driven learning (CODL) BIB003 , dual decomposition (DD) BIB004 BIB008 , and Bayesian modeling  . These techniques use different types of knowledge encoding-for example, PR uses expectation constraints on the posterior parameter distribution, GE prefers parameter settings where the model's distribution on unsupervised data matches a predefined target distribution, CODL enriches existing statistical models with Integer Linear Programming constraints, and in Bayesian modeling a prior distribution is defined on the model parameters. PR has already been used for incorporating universal linguistic knowledge into an unsupervised parsing model BIB007 ). In the future, it could be extended to typological knowledge, which is a good fit for soft constraints. As another option, Bayesian modeling sets prior probability distributions according to the relationships encoded in typological features  . Finally, DD has been applied to multi-task learning, which paves the way for typological knowledge encoding through a multi-task architecture in which one of the tasks is the actual NLP application and the other is the data-driven prediction of typological features. In fact, a modification of this architecture has already been applied to minimally supervised learning and domain adaptation with soft (non-typological) constraints Rush et al. 2012) . The same ideas could be exploited in deep learning algorithms. We have seen in § 3.2 that multilingual joint models combine both shared and language-dependent parameters in order to capture the universal properties and cross-lingual differences, respectively. In order to enforce this division of roles more efficiently, these models could be augmented with the auxiliary task of predicting typological features automatically. This auxiliary objective could update parameters of the language-specific component, or those of the shared component, in an adversarial fashion, similar to what BIB013 implemented by predicting language identity. Recently, BIB010  and BIB014 proposed frameworks that integrate deep neural models with manually specified or automatically induced constraints. Similar to CODL, the focus in BIB010 and BIB014 is on logical rules, while the ideas in  are related to PR. These frameworks provide a promising avenue for the integration of typological information and deep models. A particular non-linear deep learning domain where knowledge integration is already prominent is multilingual representation learning ( § 3.3). In this domain, a number of works BIB009 Rothe and Schütze 2015;  BIB011 have proposed means through which external knowledge sourced from linguistic resources (such as WordNet, BabelNet, or lists of morphemes) can be encoded in word embeddings. Among the state-of-the-art specialization methods ATTRACT-REPEL BIB012 ) pushes together or pulls apart vector pairs according to relational constraints, while preserving the relationship between words in the original space and possibly propagating the specialization knowledge to unseen words or transferring it to other languages ). The success of these works suggests that a more extensive integration of external linguistic knowledge in general, and typological knowledge in particular, is likely to play a key role in the future development of word representations.