The Foundations of Tokenization: Statistical and Computational Concerns

• URL: http://arxiv.org/abs/2407.11606v3
• Date: Mon, 4 Nov 2024 22:42:38 GMT
• Title: The Foundations of Tokenization: Statistical and Computational Concerns
• Authors: Juan Luis Gastaldi, John Terilla, Luca Malagutti, Brian DuSell, Tim Vieira, Ryan Cotterell,
• Abstract summary: Tokenization is a critical step in the NLP pipeline. Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood. The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models.
• Score: 51.370165245628975
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tokenization - the practice of converting strings of characters from an alphabet into sequences of tokens over a vocabulary - is a critical step in the NLP pipeline. The use of token representations is widely credited with increased model performance but is also the source of many undesirable behaviors, such as spurious ambiguity or inconsistency. Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood. In particular, the impact of tokenization on statistical estimation has been investigated mostly through empirical means. The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models. Based on the category of stochastic maps, this framework enables us to establish general conditions for a principled use of tokenizers, and most importantly, the necessary and sufficient conditions for a tokenizer model to preserve the consistency of statistical estimators. Additionally, we discuss statistical and computational concerns crucial for designing and implementing tokenizer models, such as inconsistency, ambiguity, tractability, and boundedness. The framework and results advanced in this paper contribute to building robust theoretical foundations for representations in neural language modeling that can inform future empirical research.

Related papers

• I Bet You Did Not Mean That: Testing Semantic Importance via Betting [8.909843275476264]
  We formalize the global (i.e., over a population) and local (i.e. for a sample) statistical importance of semantic concepts for the predictions of opaque models by means of conditional independence. We use recent ideas of sequential kernelized independence testing to induce a rank of importance across concepts, and showcase the effectiveness and flexibility of our framework.
  arXiv  Detail & Related papers  (2024-05-29T14:51:41Z)
• Prototype-based Aleatoric Uncertainty Quantification for Cross-modal Retrieval [139.21955930418815]
  Cross-modal Retrieval methods build similarity relations between vision and language modalities by jointly learning a common representation space. However, the predictions are often unreliable due to the Aleatoric uncertainty, which is induced by low-quality data, e.g., corrupt images, fast-paced videos, and non-detailed texts. We propose a novel Prototype-based Aleatoric Uncertainty Quantification (PAU) framework to provide trustworthy predictions by quantifying the uncertainty arisen from the inherent data ambiguity.
  arXiv  Detail & Related papers  (2023-09-29T09:41:19Z)
• Advancing Counterfactual Inference through Nonlinear Quantile Regression [77.28323341329461]
  We propose a framework for efficient and effective counterfactual inference implemented with neural networks. The proposed approach enhances the capacity to generalize estimated counterfactual outcomes to unseen data. Empirical results conducted on multiple datasets offer compelling support for our theoretical assertions.
  arXiv  Detail & Related papers  (2023-06-09T08:30:51Z)
• Logical Satisfiability of Counterfactuals for Faithful Explanations in NLI [60.142926537264714]
  We introduce the methodology of Faithfulness-through-Counterfactuals. It generates a counterfactual hypothesis based on the logical predicates expressed in the explanation. It then evaluates if the model's prediction on the counterfactual is consistent with that expressed logic.
  arXiv  Detail & Related papers  (2022-05-25T03:40:59Z)
• Logic Constraints to Feature Importances [17.234442722611803]
  "Black box" nature of AI models is often a limit for a reliable application in high-stakes fields like diagnostic techniques, autonomous guide, etc. Recent works have shown that an adequate level of interpretability could enforce the more general concept of model trustworthiness. The basic idea of this paper is to exploit the human prior knowledge of the features' importance for a specific task, in order to coherently aid the phase of the model's fitting.
  arXiv  Detail & Related papers  (2021-10-13T09:28:38Z)
• Learning Topic Models: Identifiability and Finite-Sample Analysis [6.181048261489101]
  We propose a maximum likelihood estimator (MLE) of latent topics based on a specific integrated likelihood. We conclude with empirical studies on both simulated and real datasets.
  arXiv  Detail & Related papers  (2021-10-08T16:35:42Z)
• Instance-Based Neural Dependency Parsing [56.63500180843504]
  We develop neural models that possess an interpretable inference process for dependency parsing. Our models adopt instance-based inference, where dependency edges are extracted and labeled by comparing them to edges in a training set.
  arXiv  Detail & Related papers  (2021-09-28T05:30:52Z)
• A practical introduction to the Rational Speech Act modeling framework [2.1485350418225244]
  Recent advances in computational cognitive science paved the way for significant progress in formal, implementable models of pragmatics. This paper provides a practical introduction to and critical assessment of the Bayesian Rational Speech Act modeling framework.
  arXiv  Detail & Related papers  (2021-05-20T16:08:04Z)
• Generative Counterfactuals for Neural Networks via Attribute-Informed Perturbation [51.29486247405601]
  We design a framework to generate counterfactuals for raw data instances with the proposed Attribute-Informed Perturbation (AIP) By utilizing generative models conditioned with different attributes, counterfactuals with desired labels can be obtained effectively and efficiently. Experimental results on real-world texts and images demonstrate the effectiveness, sample quality as well as efficiency of our designed framework.
  arXiv  Detail & Related papers  (2021-01-18T08:37:13Z)

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.