Constructing a BPE Tokenization DFA

• URL: http://arxiv.org/abs/2405.07671v1
• Date: Mon, 13 May 2024 11:59:24 GMT
• Title: Constructing a BPE Tokenization DFA
• Authors: Martin Berglund, Willeke Martens, Brink van der Merwe,
• Abstract summary: Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. We give and analyze an algorithm for the efficient construction of deterministic finite automata designed to operate directly on tokenizations produced by the popular byte pair encoding technique.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. In this paper, we give and analyze an algorithm for the efficient construction of deterministic finite automata designed to operate directly on tokenizations produced by the popular byte pair encoding technique. This makes it possible to apply many existing techniques and algorithms to the tokenized case, such as pattern matching, equivalence checking of tokenization dictionaries, and composing tokenized languages in various ways.

Related papers

• Tokenization as Finite-State Transduction [24.19959327497118]
  We introduce a finite-state framework which can efficiently encode all possible tokenizations of a regular language. We show that Byte-Pair. Match (BPE) and MaxPiece (WordPiece) fit within this framework. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern.
  arXiv  Detail & Related papers  (2024-10-21T07:10:07Z)
• Batching BPE Tokenization Merges [55.2480439325792]
  BatchBPE is an open-source pure Python implementation of the Byte Pair algorithm. It is used to train a high quality tokenizer on a basic laptop.
  arXiv  Detail & Related papers  (2024-08-05T09:37:21Z)
• Identifying and Analyzing Task-Encoding Tokens in Large Language Models [55.03191279766383]
  In this paper, we identify and analyze task-encoding tokens on whose representations the task performance depends. We show that template and stopword tokens are the most prone to be task-encoding. Our work sheds light on how large language models (LLMs) learn to perform a task from demonstrations, deepens our understanding of the varied roles different types of tokens play in LLMs, and provides insights for avoiding instability from improperly utilizing task-encoding tokens.
  arXiv  Detail & Related papers  (2024-01-20T20:55:21Z)
• Analyzing Cognitive Plausibility of Subword Tokenization [9.510439539246846]
  Subword tokenization has become the de-facto standard for tokenization. We present a new evaluation paradigm that focuses on the cognitive plausibility of subword tokenization.
  arXiv  Detail & Related papers  (2023-10-20T08:25:37Z)
• Tokenization with Factorized Subword Encoding [2.538209532048867]
  We propose a novel tokenization method that factorizes subwords onto discrete triplets using a VQ-VAE model. Results indicate that this method is more appropriate and robust for morphological tasks than the commonly used byte-pair encoding (BPE) tokenization algorithm.
  arXiv  Detail & Related papers  (2023-06-13T13:27:34Z)
• Prompting Language Models for Linguistic Structure [73.11488464916668]
  We present a structured prompting approach for linguistic structured prediction tasks. We evaluate this approach on part-of-speech tagging, named entity recognition, and sentence chunking. We find that while PLMs contain significant prior knowledge of task labels due to task leakage into the pretraining corpus, structured prompting can also retrieve linguistic structure with arbitrary labels.
  arXiv  Detail & Related papers  (2022-11-15T01:13:39Z)
• Better Than Whitespace: Information Retrieval for Languages without Custom Tokenizers [48.036317742487796]
  We propose a new approach to tokenization for lexical matching retrieval algorithms. We use the WordPiece tokenizer, which can be built automatically from unsupervised data. Results show that the mBERT tokenizer provides strong relevance signals for retrieval "out of the box", outperforming whitespace tokenization on most languages.
  arXiv  Detail & Related papers  (2022-10-11T14:32:46Z)
• Improving Tokenisation by Alternative Treatment of Spaces [7.596737214110957]
  We experiment with an alternative tokenisation approach where spaces are always treated as individual tokens. We find that our modified algorithms lead to improved performance on downstream NLP tasks.
  arXiv  Detail & Related papers  (2022-04-08T13:22:30Z)
• Evaluating the Morphosyntactic Well-formedness of Generated Texts [88.20502652494521]
  We propose L'AMBRE -- a metric to evaluate the morphosyntactic well-formedness of text. We show the effectiveness of our metric on the task of machine translation through a diachronic study of systems translating into morphologically-rich languages.
  arXiv  Detail & Related papers  (2021-03-30T18:02:58Z)
• Byte Pair Encoding is Suboptimal for Language Model Pretraining [49.30780227162387]
  We analyze differences between unigram LM tokenization and byte-pair encoding (BPE) We find that the unigram LM tokenization method matches or outperforms BPE across downstream tasks and two languages. We hope that developers of future pretrained LMs will consider adopting the unigram LM method over the more prevalent BPE.
  arXiv  Detail & Related papers  (2020-04-07T21:21:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.