The people of the world speak about 6,900 different languages. Open-source off-the-shelf natural language processing (NLP) toolboxes like OpenNLP and CoreNLP cover only 6–7 languages, and we have sufficient labeled training data for inducing models for about 20–30 languages. In other words, supervised sequence learning algorithms are not sufficient to induce POS models for but a small minority of the world's languages.What can we do for all the languages for which no training data is available? Unsupervised POS induction algorithms have methodological problems (in-sample evaluation, community-wide hyper-parameter tuning, etc.), and performance is prohibitive of downstream applications. Some work on unsupervised POS tagging has assumed other resources such as tag dictionaries BIBREF0 , but such resources are also only available for a limited number of languages. In our experiments, we assume that no training data or tag dictionaries are available. Our only assumption is a bit of text translated into multiple languages, specifically, fragments of the Bible. We will use Bible data for annotation projection, as well as for learning cross-lingual word embeddings (§3).Unsupervised learning with typologically informed priors BIBREF1 is an interesting approach to unsupervised POS induction that is more applicable to low-resource languages. Our work is related to this work, but we learn informed priors rather than stipulate them and combine these priors with annotation projection (learning from noisy labels) rather than unsupervised learning.Annotation projection refers to transferring annotation from one or more source languages to the target language (for which no labeled data is otherwise available), typically through word alignments. In our experiments below, we use an unsupervised word alignment algorithm to align $15\times 12$ language pairs. For 15 languages, we have predicted POS tags for each word in our multi-parallel corpus. For each word in one of our 12 target language training datasets, we thus have up to 15 votes for each word token, possibly weighted by the confidence of the word alignment algorithm. In this paper, we simply use the majority votes. This is the set-up assumed throughout in this paper (see §3 for more details):We will apply empirical Gaussian priors to linear-chain conditional random fields (CRFs; BIBREF3 ) and averaged structured perceptrons BIBREF4 . Linear-chain CRFs are trained by maximising the conditional log-likelihood of labeled sequences $LL(\mathbf {w},\mathcal {D})=\sum _{\langle \mathbf {x},\mathbf {y}\rangle \in \mathcal {D}}\log P(\mathbf {y}|\mathbf {x})$ with $\mathbf {w}\in \mathbb {R}^m$ and $\mathcal {D}$ a dataset consisting of sequences of discrete input symbols $\mathbf {x}=x_1,\ldots ,x_n$ associated with sequences of discrete labels $\mathbf {y}=y_1,\ldots ,y_n$ . L $k$ -regularized CRFs maximize $LL(\mathbf {w},\mathcal {D})-|\mathbf {w}|^k$ with typically $k\in \lbrace 0,1,2,\infty \rbrace $ , which all introduce costant-width, zero-mean regularizers. We refer to L $k$ -regularized CRFs as L2-CRF. L $k$ regularizers are parametric priors where the only parameter is the width of the bounding shape. The L2-regularizer is a Gaussian prior with zero mean, for example. The regularised log-likelihood with a Gaussian prior is $\mathbf {w}\in \mathbb {R}^m$0 . For practical reasons, hyper-parameters $\mathbf {w}\in \mathbb {R}^m$1 and $\mathbf {w}\in \mathbb {R}^m$2 are typically assumed to be constant for all values of $\mathbf {w}\in \mathbb {R}^m$3 . This also holds for recent work on parametric noise injection, e.g., BIBREF5 . If these parameters are assumed to be constant, the above objective becomes equivalent to L2-regularization. However, you can also try to learn these parameters. In empirical Bayes BIBREF6 , the parameters are learned from $\mathbf {w}\in \mathbb {R}^m$4 itself. BIBREF7 suggest learning the parameters from a validation set. In our set-up, we do not assume that we can learn the priors from training data (which is noisy) or validation data (which is generally not available in cross-lingual learning scenarios). Instead we estimate these parameters directly from source language models.When we estimate Gaussian priors from source language models, we will learn which features are invariant across languages, and which are not. We thereby introduce an ellipsoid regularizer whose centre is the average source model. In our experiments, we consider both the case where variance is assumed to be constant – which we call L2-regularization with priors (L2-Prior) — and the case where both variances and means are learned – which we call empirical Gaussian priors (EmpGauss). L2-Prior is the L2-CRF objective with $\sigma ^2_j=C$ with $C$ a regularization parameter, and $\mu _j=\hat{\mu _j}$ the average value of the corresponding parameter in the observed source models. EmpGauss replaces the above objective with $LL(\lambda )+\sum _j\log \frac{1}{\sigma \sqrt{2\pi }}e^{-\frac{(\lambda _j-\mu _j)^2}{2\sigma ^2}}$ , which, assuming model parameters are mutually independent, is the same as jointly optimising model probability and likelihood of the data. Note that minimizing the squared weights is equivalent to maximizing the log probability of the weights under a zero-mean Gaussian prior, and in the same way, this is equivalent to minimising the above objective with empirically estimated parameters $\hat{\mu _j}$ and $\sigma {\mu _j}$ . In other words, empirical Gaussian priors are bounding ellipsoids on the hypothesis space with learned widths and centres. Also, note that in single-source cross-lingual transfer learning, observed variance is zero, and we therefore replace this with a regularization parameter $C$ shared with the baseline. In the single-source set-up, L2-Prior is thus equivalent to EmpGauss. We use L-BFGS to maximize our baseline L2-regularized objectives, as well as our empirical Gaussian prior objectives.We also introduce a drop-out variant of empirical Gaussian priors. Our point of departure is average structured perceptron. We implement empirical Gaussian noise injection with Gaussians $\langle (\mu _1,\sigma _1),\ldots , (\mu _m,\sigma _m)\rangle $ for $m$ features as follows. We initialise our model parameters with the means $\mu _j$ . For every instance we pass over, we draw a corruption vector $\mathbf {g}$ of random values $v_i$ from the corresponding Gaussians $(1,\sigma _i)$ . We inject the noise in $\mathbf {g}$ by taking pairwise multiplications of $\mathbf {g}$ and our feature representations of the input sequence with the relevant label sequences. Note that this drop-out algorithm is parameter-free, but of course we could easily throw in a hyper-parameter controlling the degree of regularization. We give the algorithm in Algorithm 1.[1] $T=\lbrace  \langle \mathbf {x}^1,\mathbf {y}^1\rangle ,\ldots ,\langle \mathbf {x}_n,\mathbf {y}_n\rangle \rbrace \text{~w.~}\mathbf {x}_i=\langle v_1,\ldots \rangle \text{ and }v_k=\langle f_1,\ldots ,f_m\rangle , \mathbf {w}^0=\langle w_1:\hat{\mu _1},\ldots , w_m:\hat{\mu _m}\rangle $ $i\le I\times |T|$ $j\le n$ $\mathbf {g}\leftarrow \mathbf {sample}(\mathcal {N}(1,\sigma _1),\ldots ,\mathcal {N}(1,\sigma _m))$ $\hat{\mathbf {y}}\leftarrow \arg \max _{\mathbf {y}}\mathbf {w}^i \cdot \mathbf {g}$ $\mathbf {w}^{i+1}\leftarrow \mathbf {w}^i+\Phi (\mathbf {x}_j,\mathbf {y}_j)\cdot \mathbf {g}-\Phi (\mathbf {x}_j,\hat{\mathbf {y}})\cdot \mathbf {g}$ Averaged structured perceptron with empirical Gaussian noise We make the following additional observations: (i) Following the procedure in BIBREF11 , we can compute the Rademacher complexity of our models, i.e., their ability to learn noise in the labels (overfit). Sampling POS tags randomly from a uniform distribution, chance complexity is 0.083. With small sample sizes, L2-CRFs actually begin to learn patterns with Rademacher complexity rising to 0.086, whereas both L2-Prior and EmpGauss never learn a better fit than chance. (ii) BIBREF2 present a simple approach to explicitly studying bias-variance trade-offs during learning. They draw subsamples of $l< m$ training data points $\mathcal {D}_1, \ldots , \mathcal {D}_k$ and use a validation dataset of $m^{\prime }$ data points to define the integrated variance of our methods. Again, we see that using empirical Gaussian priors lead to less integrated variance. (iii) An empirical Gaussian prior effectively limits us to hypotheses in $\mathcal {H}$ in a ellipsoid around the average source model. When inference is exact, and our loss function is convex, we learn the model with the smallest loss on the training data within this ellipsoid. Model interpolation of (some weighting of) the average source model and the unregularized target model can potentially result in the same model, but since model interpolation is limited to the hyperplane connecting the two models, the probability of this to happen is infinitely small ( $\frac{1}{\infty }$ ). Since for any effective regularization parameter value (such that the regularized model is different from the unregularized model), the empirical Gaussian prior can be expected to have the same Rademacher complexity as model interpolation, we conclude that using empirical Gaussian priors is superior to model interpolation (and data concatenation).

Q: What languages did they experiment with?