Frank-Wolfe Lexicon Induction for Romanized Code-Mixed Text

People who mix Hindi, Nepali or Tamil with English online usually type the non-English words in Latin letters, and they spell them however they like: yaar, yar and yr are the same word. Multilingual language models were pre-trained mostly on native-script text such as Devanagari, so this Romanized input reaches them as fragmented, unfamiliar subwords. The usual fix is back-transliteration, which rewrites each Romanized word in its native script before the model sees it. That fix needs either a supervised transliteration model or a hand-built tool. Such resources are weak exactly where spellings are most informal. The off-the-shelf indic-trans library reaches only 63.56% accuracy on Xlit-Crowd, while a domain-trained model reaches 78.6% (Parikh and Solorio). For language pairs with no parallel spelling data, neither is available.

We propose to learn the Romanized-to-native mapping without supervision. The mapping is a sparse "transport plan": each Romanized word type is a row, and it spreads its mass over native-script words plus one "leave it as is" slot for English. We choose the plan by trading off two signals. One is sound similarity, meaning how closely the characters of the Romanized string match a phonetic romanization of the native word. The other is distributional agreement, meaning that words used in similar contexts should map to words used in similar contexts. We solve this with the Frank-Wolfe method, which uses no projections and moves toward whichever single feasible point best agrees with the current gradient. Because both signals are inner products of embeddings, that single best point is found by a nearest-neighbour search over the entire native vocabulary. The plan is never stored densely, and there is no need to guess a short list of candidates in advance. The central bet is this: heavily abbreviated spellings like yr or bht are exactly the words that heuristic candidate lists miss, and a search that is free to reach the full vocabulary will recover them.

Core Claim

Let $X \in \mathbb{R}^{n \times d}$ hold distributional embeddings of the $n$ Romanized word types, trained on code-mixed social media text. Let $Y \in \mathbb{R}^{m \times d}$ hold embeddings of the $m$ native-script word types, trained on native text such as Glot500-c. Let $\Phi$ and $\Psi$ hold character n-gram embeddings: $\Phi$ for the Romanized strings, $\Psi$ for the Uroman romanizations of the native words. The plan $P$ has $n$ rows, one per Romanized type, and $m+1$ columns, the last being the leave-as-is slot. Each row of $P$ is a probability vector, so the feasible set is a product of $n$ simplices. We minimize

$$ f(P) = -\langle \Phi \Psi^\top, P \rangle \;-\; \alpha \,\| X^\top P Y \|_F^2 \;+\; \beta \sum_j \big(\textstyle\sum_i P_{ij} - q_j\big)_+^2 . $$

Here $\alpha$ and $\beta$ are weights, and $q_j$ is a soft capacity for native word $j$, proportional to its corpus frequency. The first term rewards spelling-sound matches. The second is a Gromov-Wasserstein-style structural term that rewards maps preserving within-language similarity, in the spirit of Alvarez-Melis and Jaakkola, written with inner-product similarities. The third keeps a common native word from absorbing everything, while still letting yaar, yar and yr all map to the same word.

The key structural fact is about the gradient. The gradient of $f$ in row $i$ is an inner product between a query built from $\phi_i$ and $M^\top x_i$, where $M = X^\top P Y$ is a $d \times d$ matrix, and a key built from $\psi_j$, $y_j$ and a per-column capacity scalar. The Frank-Wolfe linear subproblem on row $i$ is therefore one maximum-inner-product search against all $m$ native words. It can be run exactly as chunked GPU matrix products. Each iterate is a convex combination of a few vertices, so it stays sparse, and $M$ can be updated incrementally.

The objective is nonconvex because the structural term is concave. We therefore claim only convergence to stationary points, certified by the Frank-Wolfe gap, as in the nonconvex guarantees of Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization. We make no claim of linear rates.

Relation to Prior Work

Three lines of work motivate the proposal. Pipelines built on transliteration tools or trained models lose accuracy when their components fail. Vyas et al. show POS accuracy falling from 79.02% with gold normalization to 65.39% fully automatic. Parikh and Solorio show that generic tools fail on noisy text. Gupta et al. show that preserving the language mix through transliteration beats translating to English: 58.4% versus 39.1% at top-1 on code-mixed QA. That result is why we normalize the script rather than translate.

Breaking the Script Barrier aligns scripts by fine-tuning the model on Uroman transliterations. It reports that phonetic romanization collapses distinct words into the same Latin string and calls for direct embedding-level alignment. We take that call literally, but at the level of the word inventory rather than the model's weights.

The method comes from the optimal transport and Frank-Wolfe literatures. Alvarez-Melis and Jaakkola align word embedding spaces with Gromov-Wasserstein distances solved by entropic Sinkhorn iterations. Their plans are dense, their vocabularies are limited, and they evaluate only on European languages with no phonetic signal. Our problem is many-to-one, unbalanced through the leave-as-is slot, and too large for dense plans. The structure of the feasible set follows Iommazzo et al., who study Frank-Wolfe with away steps over products of polytopes. An away step removes weight from a vertex already in use; we use such steps to prune bad candidates from each row. We cite their conditioning results only for intuition, since our objective is not convex. Row-block updates follow block-coordinate conditional gradient for structured prediction (Efficient Training of Structured SVMs via Soft Constraints Efficient Training of Structured SVMs via Soft Constraints), and the step-size rules follow Beyond Short Steps in Frank-Wolfe Algorithms.

We do not claim that Frank-Wolfe is new for Gromov-Wasserstein problems in general. The contribution is a formulation in which the Frank-Wolfe subproblem becomes a search over the full vocabulary, applied to a normalization problem where heuristic candidate lists are the known weak point.

Research Program

We will build the solver and embeddings for Hindi-English first, where supervision exists to evaluate against. We will then apply the unchanged recipe to Nepali-English from LinCE, where it does not. The Romanized embeddings come from the training portions of LinCE, GLUECoS, SemEval-2020 Task 9 and the Vyas et al. Facebook corpus. The native embeddings come from Glot500-c text.

Type-level plans are ambiguous in context. For example, main can be English or Hindi मैं. For downstream use we therefore combine each type's plan row, used as a prior, with the masked-language-model score of each candidate under a native-script multilingual model. The token is then rewritten with the best-scoring candidate.

We will analyse where the gains come from. We split evaluation words by how far their spelling is from the phonetic romanization of the gold native word, so that abbreviations, dropped vowels and ordinary variants are reported separately. We also track Frank-Wolfe gaps, the sparsity of the plan, and wall-clock time against vocabulary size.

Baselines

The naive reference point feeds raw Romanized text to mBERT and XLM-R. On LinCE, mBERT reports an average accuracy of 82.93% (Aguilar et al.). On GLUECoS code-switched NLI, a modified mBERT reports 63.1% (Khanuja et al.). We rerun both under our own fine-tuning protocol rather than quoting them.

The tool-pipeline baselines put indic-trans or Uroman in front of the same downstream model. The Google-transliteration pipeline of Kumar et al. reports 0.707 F1 on SemEval-2020 Hinglish sentiment. That number includes their ensemble architecture, so we reproduce only the transliteration step on our shared downstream model.

The strongest supervised reference is the Parikh and Solorio normalization-plus-syllable-mapping pipeline, at 78.6% on Xlit-Crowd. We treat it as a ceiling that uses supervision, not as a competitor we must beat. Matching it within a few points with zero parallel data would count as success. For Nepali it cannot be trained at all, which is the point.

The strongest unsupervised competitor is entropic fused Gromov-Wasserstein in the style of Alvarez-Melis and Jaakkola. Because dense plans are infeasible, we restrict its support to the union of each word's top-K phonetic neighbours and top-K distributional neighbours, then round the plan. We also run exact sparse optimal transport and projected gradient descent on the same restricted support. All of these use the same embeddings, objective weights, tuning budget and GPU hours as our solver.

Two ablations isolate the proposal's ingredients. The first is our Frank-Wolfe solver confined to the same restricted support. It tests whether the full-vocabulary search, rather than the objective, drives any gain. The second removes the structural term, which reduces the method to phonetic nearest neighbours. We will also drop the leave-as-is slot and the away steps. Beating a baseline means higher top-1 back-transliteration accuracy with paired bootstrap significance, and higher downstream scores averaged over five seeds.

Why not just…?

Why not just use a trained transliteration model or API? Where Hindi supervision exists this is a real option, and we report it as a ceiling. However, the file shows generic tools at 63.56% on Xlit-Crowd (Parikh and Solorio), and pipeline errors compound downstream (Vyas et al.). Supervised models also do not exist for most code-mixed pairs. The Nepali experiment settles whether an unsupervised plan is useful where no such model can be trained.

Why not just run Sinkhorn or exact transport on a pruned candidate list? This is the most serious threat. If the union-support baseline matches us, the Frank-Wolfe machinery is only an engineering convenience, and we will say so. The claim is falsifiable: we measure how often the gold native word falls outside the union of candidate lists, and whether our gains concentrate on exactly those words. If the candidate lists already have near-perfect recall, the idea reduces to that baseline.

Why not just fine-tune the multilingual model on Romanized or Uroman text, as in PPA? Breaking the Script Barrier does this and reports roughly 20% average gains in cross-script sentence retrieval. It still leaves the homograph collisions it acknowledges. We run its alignment recipe on the same model and data. We also run it combined with our normalization, to test whether the two are complementary rather than competing.

Why not just use phonetic string similarity alone? That is our ablation with the structural term removed. We expect it to fail precisely on abbreviations like yr and bht, whose Latin letters carry little of the pronunciation. If it does not fail there, the distributional term is unnecessary.

Proposed Experiments

For intrinsic evaluation we measure top-1 and top-5 back-transliteration accuracy on Xlit-Crowd. We also evaluate noisy-to-native pairs built by chaining hinglishNorm normalizations with Xlit-Crowd targets, and the normalization annotations of the Vyas et al. corpus. For Nepali we annotate a small set of about a thousand Romanized types, because no gold lexicon is available on Lacuna. No reported result was found on Lacuna for unsupervised Romanized-to-Devanagari lexicon induction.

For extrinsic evaluation we use LinCE HIN-ENG and NEP-ENG POS, NER and sentiment, GLUECoS Hindi-English NLI and QA, and SemEval-2020 Hinglish sentiment, all on a fixed XLM-R model. The scaling study varies the native vocabulary from 20k to 200k types and reports time and memory for our solver against the restricted-support baselines.

Three outcomes are decisive. First, the ablation that confines our solver to the restricted support must lose accuracy, concentrated on words outside the candidate lists. If it does not, the full-vocabulary search contributes nothing. Second, on Nepali, where the supervised pipeline cannot be built, the induced lexicon must improve downstream scores over raw Romanized input. Third, gains on Hindi must survive when the PPA alignment is also applied.