Improving Gboard language models via private federated analytics

Google’s keyboard application, Gboard, leverages language models (LMs) to improve users’ typing experience via features like next word prediction, autocorrection, smart compose, slide to type, and proofread. Our researchers prioritize developing responsible approaches that uphold the highest privacy standards while improving Gboard’s LM performance. We have made substantial progress in recent years, including providing data usage disclosures and configuration controls to our users and using federated learning to train Gboard's LMs with differential privacy (DP) to provide a quantifiable and rigorous measure of data anonymization.

Gboard’s LMs are designed to work with a predefined list of frequently-used words, referred to as vocabulary. The performance of LMs depends on the quality of this vocabulary, which could change over time. Words that are not part of the vocabulary are referred to as out-of-vocabulary (OOV) words. OOV words can occur in Gboard for several reasons. For example, the vocabulary for some languages is still under development in Gboard, so the fraction of OOV words can be higher. For languages where Gboard has a relatively complete vocabulary, such as English in the U.S., OOV words often appear due to newly emerged trending words, such as “COVID-19” and “Wordle”, atypical capitalization, such as “tuesday”, and unusual spelling due to users’ preferences, such as “cooool”, or even typos. OOV discovery is a challenging task due to the sensitive nature of information that users type on their keyboard.

Today, we are excited to share a number of approaches that improve the performance of LMs by enabling the discovery of new frequently-used words, while maintaining strong data minimization and DP guarantees. These research efforts include collaboration with linguists to surface novel OOV words, employment of privacy-preserving federated analytics and other DP algorithms, and use of trusted execution environments (TEEs).

For the Gboard use case, stronger privacy is desired as user inputs may come from a large set of possibilities that potentially contain sensitive information. For example, English language users may type words or phrases of arbitrary length with characters from the Latin alphabet, list of digits, or other special characters. These inputs could contain their personal information like usernames and credit card numbers. Because SecAggIBLT enables the discovery of such unique words, it depends on the server’s proper application of central DP after SecAgg to ensure user privacy. On its own, it doesn’t prevent a curious server from inspecting discovered OOV words and potentially accessing sensitive information. This required us to develop algorithms that discover frequent OOV words with stronger data minimization and DP guarantees.

To that end, we built on an existing line of work to develop LDP-TrieHH, which learns frequent words by iteratively building a trie (prefix tree) data structure. LDP-TrieHH provides strong data minimization and strict local DP (LDP) guarantees during the data collection process. When applying the LDP-TrieHH algorithm to a specific language, such as English spoken in the U.S. and Indonesian, each layer of the trie stores a set of common prefixes corresponding to the depth of that layer. The trie is built iteratively, starting from the root up to its maximum length, which is 15 for both English and Indonesian. At each layer, we collect responses from a group of users, who only contribute by indicating one character after a common prefix from the previous layer. For example, if “CO” is a common prefix that the algorithm learned in the previous layer, and a user types a word “COVID-19”, the user will only contribute their data by submitting a vote on “COV” instead of the entire word “COVID-19”, which reduces the amount of information that is revealed from the voting process.

On top of this, we further protect the privacy of user votes by minimizing users’ participation (each user participates in the voting phase of at most one layer), bounding the number of votes each user can contribute (an average of one word per day for a 60 day period), and adding local noise to user’s votes to provide a rigorous LDP guarantee (ε = 10.0 per word). For this, we use the privacy protection mechanism of Subset Selection, which offers the optimal utility-privacy tradeoff under LDP. At each layer, we collect votes from a large group of users (500K per layer) and the votes are aggregated and thresholded to filter out the infrequent prefixes. With this additional data processing step, through the analysis of privacy amplification via aggregation, LDP-TrieHH offers a central DP guarantee of (ε = 0.315, δ = 1e-10) per word with each user contributing at most 60 words in 60 days (i.e., an average of one word per day). To improve the coverage of discovered words, we sequentially run LDP-TrieHH multiple times to build several tries with disjoint sets of users. In later runs, we ask users to only contribute OOV words that have not been learned from previous runs to utilize each user’s contribution budget more efficiently. With LDP-TrieHH, we are able to discover words that account for 16.8% of the OOV words for English and 17.5% of the OOV words for Indonesian. More details are provided in this report.