토큰화: 난해성과 이중 기준 근사 알고리즘
Tokenization: Hardness and Bicriteria Approximation Algorithms
한국어 초록
우리는 이진 토큰화를 연구한다. 이는 $\{0,1\}$ 위의 이진 문자열 코퍼스와 어휘 예산 $K$가 주어졌을 때, 코퍼스를 표현하는 데 필요한 전체 토큰 수를 최소화하도록 최대 $K$개의 부분 문자열(어휘)을 선택하는 문제이다. 기본 기호 $0$과 $1$은 항상 사용할 수 있으며, 각 문서는 별도로 분할되어야 한다. $n$을 전체 코퍼스 길이, $M$을 최대 문서 길이라 할 때, 모든 고정된 $\varepsilon\in(0,1)$에 대해 $\mathsf{P}=\mathsf{NP}$가 아닌 한 이진 토큰화 문제에는 다항 시간 $n^{1-\varepsilon}$-근사 알고리즘이 존재하지 않음을 증명한다. 이 난해성 결과를 보완하기 위해 $\gamma = \sqrt{M}\log n$인 다항 시간 $(\gamma,\gamma)$-이중 기준 알고리즘을 제시한다. 이 알고리즘은 크기가 최대 $\gamma K$인 어휘를 출력하며 토큰 수는 최대 $\gamma {\rm OPT}_K$이다. 여기서 ${\rm OPT}_K$는 원래 예산 $K$ 하에서의 최적 토큰 수이다. 또한 선택된 부분 문자열 길이의 합이 $B$로 제한되는 저장 예산 변형도 연구한다. $2\le B<n$에 대해 $(O(\log n\log B),O(\log n\log B))$-이중 기준 근사 알고리즘을 얻는다.
원문 초록
We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(\gamma,\gamma)$-bicriteria algorithm, with $\gamma = \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $\gamma K$ with number of tokens at most $\gamma {\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.