Federated Learning of N-Gram Language Models

Proceedings of the 23rd Conference on Computational Natural Language Learning, pages 121–130 Hong Kong, China, November 3-4, 2019. c⃝2019 Association for Computational Linguistics 121 Federated Learning of N-gram Language Models Mingqing Chen, Ananda Theertha Suresh, Rajiv Mathews, Adeline Wong, Cyril Allauzen, Franc¸oise Beaufays, Michael Riley Google, Inc. {mingqing,theertha,mathews,adelinew,allauzen,fsb,riley} @google.com Abstract We propose algorithms to train production- quality n-gram language models using feder- ated learning. Federated learning is a dis- tributed computation platform that can be used to train global models for portable devices such as smart phones. Federated learning is especially relevant for applications handling privacy-sensitive data, such as virtual key- boards, because training is performed with- out the users’ data ever leaving their devices. While the principles of federated learning are fairly generic, its methodology assumes that the underlying models are neural networks. However, virtual keyboards are typically pow- ered by n-gram language models for latency reasons. We propose to train a recurrent neural net- work language model using the decentral- ized FederatedAveraging algorithm and to approximate this federated model server- side with an n-gram model that can be de- ployed to devices for fast inference. Our technical contributions include ways of han- dling large vocabularies, algorithms to cor- rect capitalization errors in user data, and effi- cient finite state transducer algorithms to con- vert word language models to word-piece lan- guage models and vice versa. The n-gram lan- guage models trained with federated learning are compared to n-grams trained with tradi- tional server-based algorithms using A/B tests on tens of millions of users of a virtual key- board. Results are presented for two lan- guages, American English and Brazilian Por- tuguese. This work demonstrates that high- quality n-gram language models can be trained directly on client mobile devices without sen- sitive training data ever leaving the devices. Figure 1: Glide trails are shown for two spatially- similar words: “Vampire” (in red) and “Value” (in or- ange). Viable decoding candidates are proposed based on context and language model scores. 1 Introduction 1.1 Virtual keyboard applications Virtual keyboards for mobile devices provide a host of functionalities from decoding noisy spatial signals from tap and glide typing inputs to provid- ing auto-corrections, word completions, and next- word predictions. These features must fit within tight RAM and CPU budgets, and operate under strict latency constraints. A key press should re- sult in visible feedback within about 20 millisec- onds (Ouyang et al., 2017; Alsharif et al., 2015). Weighted finite-state transducers have been used successfully to decode keyboard spatial signals us- ing a combination of spatial and language mod- els (Ouyang et al., 2017; Hellsten et al., 2017). Figure 1 shows the glide trails of two spatially- similar words. Because of the similarity of the two trails, the decoder must rely on the language model to discriminate between viable candidates. For memory and latency reasons, especially on low-end devices, the language models are typi- cally based on n-grams and do not exceed ten megabytes. A language model (LM) is a prob- abilistic model …

Content truncated to 500 words