Вчерашняя дорожка про отсев боролась с заучиванием изнутри сети. Сегодня — с той же болезнью со стороны данных: если один и тот же текст встречается в обучающем корпусе сотни раз, модель запоминает его дословно, а проверочные вопросы, случайно попавшие в обучение, завышают оценку. Узкий вопрос дня: как в миллиардах документов найти почти одинаковые тексты, не сравнивая каждый с каждым, — шинглы, сходство Жаккара, подписи MinHash и полосы LSH. Все примеры ниже запускались на коробке; в роли корпуса — абзацы со старых страниц этого сайта. Цифры из чужих работ помечены как опубликованные, а не измеренные нами.
Все дорожки — /put. Прошлая — отсев нейронов.
Зачем это в работе. Любой корпус, собранный из интернета, полон повторов: одна новость перепечатана на десятке сайтов, страницы магазинов отличаются только названием товара, под каждой статьёй одна и та же подпись. Если такой текст попал в обучение сотни раз, модель видит его сотни раз и начинает воспроизводить дословно. Если же в обучение попали вопросы из проверочного набора, оценка качества становится завышенной: модель не решает задачу, а вспоминает ответ. Поэтому удаление повторов (дедупликация, deduplication) — обязательный шаг при подготовке данных и для предобучения, и для дообучения на своих текстах.
Как это устроено. Самый простой уровень — точные дубли. Для каждого документа считают хеш: короткое число фиксированной длины, которое функция (например, SHA-256) вычисляет из текста так, что одинаковые тексты дают одинаковый хеш, а разные — почти наверняка разный. Хеши складывают в таблицу, и документ с уже встречавшимся хешем выбрасывают. Это работает за один проход по корпусу и требует памяти только на хеши.
Ограничение: хеш меняется от любого символа. Лишний пробел, другой регистр, дефис вместо тире — и тексты для хеша уже разные. Частично помогает нормализация (normalization): перед хешированием приводят текст к нижнему регистру, выбрасывают пунктуацию и лишние пробелы. Но если отличается хотя бы одно слово — название города, дата, цена, — точное сравнение уже бессильно.
Отсюда второй уровень — почти-дубли (near-duplicates): тексты, которые совпадают в большей части, но не целиком. Их нельзя найти хешем целого текста, нужно мерить степень сходства. Этим заняты следующие три ступени. На практике оба уровня применяют вместе: сначала дешёвое точное удаление, потом поиск почти-дублей среди оставшегося.
Насколько это важно, показывает опубликованная работа Google (Lee и соавторы, «Deduplicating Training Data Makes Language Models Better», ACL 2022). Авторы сообщают: в корпусе C4 около 3% документов имели почти-дубль; модель на 1,5 млрд параметров, обученная на исходном корпусе, в тексте без подсказки выдавала больше 1% токенов, дословно скопированных из обучения, а после чистки — примерно в 10 раз меньше; 4,6% проверочных документов C4 имели почти-дубль в обучающей части. Это их измерения, мы их не повторяли.
Подробный пример. Четыре варианта одной фразы: оригинал, лишний пробел, другой регистр с дефисом и восклицательным знаком, и тот же текст с добавленной подписью. Считаем SHA-256 от сырого текста и от нормализованного (функция norm приведена во второй ступени).
import hashlib
from common import norm
docs = [
"Модель обучали на открытых данных. Подробности — в отчёте.",
"Модель обучали на открытых данных. Подробности — в отчёте.", # два пробела
"модель обучали на открытых данных. Подробности - в отчёте!", # регистр, дефис, знак
"Модель обучали на открытых данных. Подробности — в отчёте. Подписывайтесь на канал.",
]
for d in docs:
raw = hashlib.sha256(d.encode()).hexdigest()[:12]
nrm = hashlib.sha256(norm(d).encode()).hexdigest()[:12]
print(f"сырой {raw} нормализованный {nrm}")
У нас этот код напечатал:
сырой a3ad26f046ec нормализованный 723bcd1b4818
сырой e21088f0d04d нормализованный 723bcd1b4818
сырой b36eae32fa48 нормализованный 723bcd1b4818
сырой d5cad29a19f4 нормализованный bdbb5e784f59
Сырые хеши различаются у всех четырёх строк, хотя для читателя первые три одинаковы. После нормализации первые три совпали — их удалит обычная таблица хешей. Четвёртая отличается одной фразой в конце, и её хеш другой при любой нормализации: это уже почти-дубль, для которого нужен другой инструмент.
Где обычно ошибаются.
Словарь ступени.
Дедупликация (deduplication). Удаление повторяющихся документов или кусков из набора данных.
Хеш (hash). Короткое число, вычисленное из данных так, что одинаковые данные дают одинаковое число.
SHA-256. Распространённая хеш-функция с 256-битным результатом; совпадение хешей разных текстов на практике не встречается.
Нормализация текста (normalization). Приведение текста к единому виду перед сравнением: регистр, пробелы, пунктуация.
Точный дубль (exact duplicate). Документ, совпадающий с другим символ в символ, иногда после нормализации.
Почти-дубль (near-duplicate). Документ, совпадающий с другим в большей части, но отличающийся отдельными словами или кусками.
Запоминание (memorization). Способность модели воспроизводить куски обучающих текстов дословно.
Утечка проверочных данных (contamination). Попадание проверочных примеров или их почти-дублей в обучающий набор.
Зачем это в работе. Прежде чем искать почти-дубли быстро, нужно договориться, что такое «почти». Нужна мера, которая даёт 1 для одинаковых текстов, 0 для совсем разных и плавно падает с числом правок. От выбора этой меры зависит, что вы выбросите: перепечатку новости, страницу-шаблон или просто текст на ту же тему. Стандартный выбор в подготовке корпусов — сходство Жаккара по шинглам, и все быстрые методы следующих ступеней лишь приближённо считают именно его.
Как это устроено. Шаг первый: текст нормализуют и режут на слова. Шаг второй: выписывают все шинглы (shingles) — подряд идущие куски по k слов, сдвигая окно на одно слово. Из текста «модель читает текст слева направо» при k = 3 получатся три шингла: «модель читает текст», «читает текст слева», «текст слева направо». Шаг третий: каждый документ превращается в множество своих шинглов, повторы внутри одного документа не считаются. Чтобы не хранить строки, каждый шингл обычно сразу заменяют его хешем.
Шаг четвёртый: сходство Жаккара (Jaccard similarity) двух множеств — это размер их пересечения, делённый на размер объединения. Если у двух текстов 90 общих шинглов, а всего различных шинглов у обоих вместе 100, сходство 0,9. Мера симметрична и не зависит от порядка документов.
Выбор k — главное ограничение. При k = 1 (отдельные слова) два текста на одну тему уже похожи, потому что делят частые слова, а порядок слов вообще не учитывается. При большом k одна заменённая буква портит сразу k шинглов, и сходство резко падает от мелких правок. Опубликованная настройка корпуса FineWeb (Hugging Face, 2024) — шинглы по 5 слов.
Чем это отличается от соседей. Расстояние редактирования (edit distance) считает минимальное число вставок и замен символов — точнее, но требует сравнить два текста целиком, это дорого для длинных документов и не даёт быстрого поиска. Косинусное сходство эмбеддингов (векторов смысла, о них — дорожка про эмбеддинги) ловит пересказ другими словами, а Жаккар по шинглам ловит именно совпадение текста.
Подробный пример. Сначала общие функции, которые используются во всех примерах дня: нормализация, шинглы с хешем crc32 и сходство Жаккара. Функции make_perm и minhash понадобятся в третьей ступени.
import zlib, re, numpy as np
P = (1 << 31) - 1 # простое число 2^31 - 1
def norm(text):
# нижний регистр, без пунктуации, одиночные пробелы
return " ".join(re.findall(r"\w+", text.lower()))
def shingles(text, k=5):
w = norm(text).split()
return {zlib.crc32(" ".join(w[i:i+k]).encode()) % P for i in range(max(1, len(w)-k+1))}
def jaccard(a, b):
return len(a & b) / len(a | b)
def make_perm(n, seed=0):
rng = np.random.default_rng(seed)
return rng.integers(1, P, n), rng.integers(0, P, n)
def minhash(sh, A, B):
x = np.fromiter(sh, dtype=np.int64)
return ((np.outer(A, x) + B[:, None]) % P).min(axis=1)
Корпус — абзацы длиннее 60 слов со старых страниц дорожек этого сайта:
# Абзацы из старых страниц сайта как «настоящие» тексты
import re, html, glob
def paragraphs(min_words=60):
out = []
for f in sorted(glob.glob("/workspace/motomov-py/put-2026-1*.html")):
for p in re.findall(r"<p>(.*?)</p>", open(f).read(), flags=re.S):
t = html.unescape(re.sub(r"<[^>]+>", "", p))
if len(t.split()) >= min_words: out.append(t)
return out
Берём один абзац (73 слова) и сравниваем с его изменёнными версиями при k = 1, 3, 5 и 9. Заменённые слова заменяем словом-заглушкой «зпт».
import random
from common import shingles, jaccard, norm
from corpus import paragraphs
random.seed(1)
docs = paragraphs()
base = docs[100]; other = docs[200]
w = base.split()
def replace_words(words, n):
words = words[:]
for i in random.sample(range(len(words)), n): words[i] = "зпт"
return " ".join(words)
variants = {
"копия с другой пунктуацией": base.replace(",", "").upper(),
"заменено 1 слово из %d" % len(w): replace_words(w, 1),
"заменено 5 слов": replace_words(w, 5),
"добавлен хвост-подпись в 15 слов": base + " Подписывайтесь на наш канал и ставьте лайк, чтобы не пропустить новые выпуски про модели каждый день.",
"первая половина текста": " ".join(w[: len(w)//2]),
"чужой абзац с той же темы сайта": other,
}
print("слов в исходном абзаце:", len(w))
for name, v in variants.items():
row = [f"{jaccard(shingles(base, k), shingles(v, k)):.2f}" for k in (1, 3, 5, 9)]
print(f"{name:38s} k=1:{row[0]} k=3:{row[1]} k=5:{row[2]} k=9:{row[3]}")
У нас этот код напечатал:
слов в исходном абзаце: 73
копия с другой пунктуацией k=1:1.00 k=3:1.00 k=5:1.00 k=9:1.00
заменено 1 слово из 73 k=1:0.97 k=3:0.92 k=5:0.86 k=9:0.75
заменено 5 слов k=1:0.90 k=3:0.69 k=5:0.53 k=9:0.31
добавлен хвост-подпись в 15 слов k=1:0.84 k=3:0.81 k=5:0.81 k=9:0.80
первая половина текста k=1:0.55 k=3:0.50 k=5:0.49 k=9:0.45
чужой абзац с той же темы сайта k=1:0.06 k=3:0.00 k=5:0.00 k=9:0.00
Что видно. Пунктуация и регистр после нормализации не влияют вообще. Одно заменённое слово при k = 9 роняет сходство до 0,75, а при k = 1 почти не заметно. Пять замен на 73 слова при k = 5 дают 0,53 — порог 0,75 такой текст уже не пройдёт, хотя для человека это та же заметка. Добавленная подпись держит сходство около 0,8 при любом k. Чужой абзац на ту же тему похож по словам (0,06 при k = 1), но не имеет ни одного общего шингла при k ≥ 3: шинглы отделяют совпадение текста от совпадения темы.
Где обычно ошибаются.
Словарь ступени.
Шингл (shingle, n-грамма). Кусок из k подряд идущих слов (или символов) текста.
Размер шингла k. Сколько слов в одном куске; задаёт, насколько мера чувствительна к мелким правкам.
Множество шинглов. Все различные шинглы документа без учёта повторов и порядка.
Сходство Жаккара (Jaccard similarity). Размер пересечения двух множеств, делённый на размер их объединения, от 0 до 1.
crc32. Быстрая 32-битная контрольная сумма; здесь используется как дешёвый хеш шингла.
Расстояние редактирования (edit distance). Минимальное число вставок, удалений и замен, превращающих один текст в другой.
Порог сходства (threshold). Значение, начиная с которого пару считают дублем, например 0,75.
Зачем это в работе. У документа в несколько тысяч слов — тысячи шинглов. Хранить их множества для миллиардов документов и пересекать попарно невозможно ни по памяти, ни по времени. MinHash заменяет множество короткой подписью из, скажем, 112 чисел фиксированного размера, по которой сходство Жаккара оценивается простым подсчётом совпадающих позиций. Это делает возможной дедупликацию целых веб-корпусов, а библиотеки вроде datasketch и datatrove строят на этом свои инструменты.
Как это устроено. Возьмём одну случайную хеш-функцию h, которая каждому шинглу ставит в соответствие число, как будто перемешивая все возможные шинглы в случайном порядке. Минимальный хеш (minhash) документа — наименьшее значение h среди всех его шинглов, то есть «первый» шингл документа в этом случайном порядке.
Ключевое свойство: вероятность того, что у двух документов минимальные хеши совпадут, ровно равна их сходству Жаккара. Почему: посмотрим на все шинглы объединения двух множеств. Каждый из них с равной вероятностью окажется первым в случайном порядке. Минимумы совпадут тогда и только тогда, когда первым оказался шингл, который есть в обоих документах, — а доля таких шинглов в объединении и есть сходство Жаккара.
Одна функция даёт только «совпало или нет» — это слишком грубо. Поэтому берут n независимых функций и получают подпись (signature) из n минимумов. Доля совпавших позиций в двух подписях — оценка сходства. Её разброс (стандартное отклонение) равен корню из J·(1−J)/n: чтобы уменьшить ошибку вдвое, нужно вчетверо больше функций. В нашем коде функции имеют вид (a·x + b) mod p со случайными a и b и простым p = 2³¹ − 1 — это стандартное семейство, дающее приближённо случайный порядок.
Чем это отличается от соседей. Обычный хеш целого текста отвечает только «одинаково или нет». SimHash — другой метод почти-дублей: он строит один битовый отпечаток, и похожие тексты отличаются в немногих битах; он приближает косинусное сходство, а не Жаккара. MinHash же оценивает именно Жаккара, поэтому порог можно задавать в понятных единицах.
Подробный пример. Берём абзац из второй ступени и три его изменённые версии с известным точным сходством. Для подписей длиной 16, 64, 128 и 256 строим по 300 разных наборов хеш-функций и смотрим среднюю оценку и её разброс; рядом — разброс, предсказанный формулой.
import random, numpy as np
from common import shingles, jaccard, make_perm, minhash
from corpus import paragraphs
random.seed(1)
base = paragraphs()[100]; w = base.split()
def replace_words(words, n):
words = words[:]
for i in random.sample(range(len(words)), n): words[i] = "зпт"
return " ".join(words)
pairs = {"1 слово": replace_words(w, 1), "5 слов": replace_words(w, 5), "половина": " ".join(w[:len(w)//2])}
a = shingles(base)
for name, v in pairs.items():
b = shingles(v); J = jaccard(a, b)
print(f"{name}: точное сходство {J:.3f}")
for n in (16, 64, 128, 256):
est = []
for seed in range(300): # 300 разных наборов хеш-функций
A, B = make_perm(n, seed)
est.append(np.mean(minhash(a, A, B) == minhash(b, A, B)))
est = np.array(est)
print(f" n={n:3d}: среднее {est.mean():.3f}, разброс {est.std():.3f}, теория {np.sqrt(J*(1-J)/n):.3f}")
У нас этот код напечатал:
1 слово: точное сходство 0.863
n= 16: среднее 0.862, разброс 0.089, теория 0.086
n= 64: среднее 0.863, разброс 0.046, теория 0.043
n=128: среднее 0.863, разброс 0.032, теория 0.030
n=256: среднее 0.863, разброс 0.021, теория 0.021
5 слов: точное сходство 0.528
n= 16: среднее 0.530, разброс 0.115, теория 0.125
n= 64: среднее 0.524, разброс 0.059, теория 0.062
n=128: среднее 0.531, разброс 0.044, теория 0.044
n=256: среднее 0.529, разброс 0.032, теория 0.031
половина: точное сходство 0.485
n= 16: среднее 0.491, разброс 0.128, теория 0.125
n= 64: среднее 0.484, разброс 0.064, теория 0.062
n=128: среднее 0.486, разброс 0.045, теория 0.044
n=256: среднее 0.486, разброс 0.031, теория 0.031
Среднее по 300 наборам совпадает с точным сходством до тысячных при любой длине подписи — оценка несмещённая. Разброс совпал с формулой: при 16 функциях ошибка одной оценки около ±0,09–0,13, то есть пара со сходством 0,53 легко покажет 0,65; при 256 функциях — около ±0,02–0,03. Подпись из 112 чисел занимает 448 байт на документ при 32-битных числах и 896 байт при 64-битных — независимо от длины документа.
Где обычно ошибаются.
Словарь ступени.
MinHash. Метод, который сжимает множество в подпись из минимальных хешей так, что доля совпавших позиций оценивает сходство Жаккара.
Минимальный хеш (minhash). Наименьшее значение одной хеш-функции среди всех шинглов документа.
Подпись (signature). Набор из n минимальных хешей документа, по одному на каждую хеш-функцию.
Семейство хеш-функций (a·x + b) mod p. Простой способ получить много разных «случайных порядков» из двух случайных чисел a и b.
Несмещённая оценка (unbiased estimate). Оценка, которая в среднем по многим попыткам равна истинному значению.
Стандартное отклонение (standard deviation). Типичный размер отклонения оценки от среднего.
SimHash. Другой способ искать почти-дубли: один битовый отпечаток, близкие тексты отличаются в немногих битах.
datatrove. Открытая библиотека Hugging Face для обработки больших текстовых корпусов, в ней есть дедупликация MinHash.
Зачем это в работе. Подпись делает одно сравнение дешёвым, но число пар растёт как квадрат числа документов: для миллиарда документов это порядка 5·10¹⁷ пар, их не перебрать никаким кластером. Нужен способ сразу получить короткий список подозрительных пар (кандидатов) и проверять только их. Локально-чувствительное хеширование (locality-sensitive hashing, LSH) делает именно это, и от его настроек зависит, какие дубли вы поймаете, а какие пропустите.
Как это устроено. Шаг первый: подпись из n = b·r чисел режут на b полос (bands) по r чисел. Шаг второй: для каждой полосы документы раскладывают по корзинам (buckets) по содержимому этой полосы — фактически хешируют r чисел целиком. Шаг третий: два документа становятся кандидатами, если хотя бы в одной полосе попали в одну корзину, то есть все r чисел этой полосы у них совпали. Шаг четвёртый: кандидатов либо проверяют точным сходством, либо сразу объединяют в группы дублей и оставляют по одному документу из группы.
Почему это работает. Для пары со сходством s одна позиция подписи совпадает с вероятностью s, вся полоса из r позиций — с вероятностью sʳ, ни одна из b полос не совпадёт с вероятностью (1 − sʳ)ᵇ. Значит, вероятность стать кандидатом равна 1 − (1 − sʳ)ᵇ. Как функция от s это S-образная кривая: почти ноль для непохожих пар, почти единица для очень похожих и крутой подъём в середине. Где этот подъём, задают r и b: больше r — кривая сдвигается вправо (строже), больше b — влево (мягче).
Ограничение: это вероятностный метод. Пары чуть выше порога иногда пропускаются, пары чуть ниже — иногда попадают в кандидаты. Сделать кривую круче можно, только увеличив n, то есть длину подписи, память и время. Опубликованный выбор FineWeb — 112 функций, 14 полос по 8; авторы указывают вероятности совпадения 56%, 77%, 92% и 98,8% для сходства 0,70, 0,75, 0,80 и 0,85. Корпус RefinedWeb, по тем же опубликованным данным, использовал 9000 функций (450 полос по 20) — кривая гораздо круче, но и подписи в 80 раз длиннее.
Чем это отличается от соседей. Поиск ближайших соседей по эмбеддингам (векторный индекс) решает похожую задачу для векторов смысла, а LSH по MinHash — для множеств шинглов. Сортировка подписей или полное попарное сравнение дают точный ответ, но не масштабируются на миллиарды документов.
Подробный пример. Сначала считаем кривую для трёх разбиений 112 функций. Затем берём 716 абзацев сайта, подмешиваем к ним 150 испорченных копий (в каждой заменено от 0 до 12 слов), строим подписи и полосы 14 × 8 и сравниваем кандидатов с точным подсчётом сходства по всем парам.
import random, itertools, collections, numpy as np
from common import shingles, jaccard, make_perm, minhash
from corpus import paragraphs
random.seed(2)
print("вероятность стать кандидатом, b полос по r строк (n = b*r = 112)")
for s in (0.3, 0.5, 0.6, 0.7, 0.75, 0.8, 0.9):
row = " ".join(f"b={b:2d},r={r:2d}: {1-(1-s**r)**b:.3f}" for b, r in ((28, 4), (14, 8), (8, 14)))
print(f" s={s:.2f} {row}")
docs = paragraphs()
orig = len(docs)
for i in random.sample(range(orig), 150): # подмешиваем почти-дубли
w = docs[i].split()
for j in random.sample(range(len(w)), random.randint(0, 12)): w[j] = "зпт"
docs.append(" ".join(w))
sh = [shingles(d) for d in docs]
A, B = make_perm(112, seed=0)
sig = np.array([minhash(s, A, B) for s in sh])
b, r = 14, 8
cand = set()
for band in range(b):
buckets = collections.defaultdict(list)
for i, row in enumerate(sig[:, band*r:(band+1)*r]):
buckets[row.tobytes()].append(i)
for ids in buckets.values():
cand.update(itertools.combinations(ids, 2))
N = len(docs); total = N*(N-1)//2
true = {(i, j) for i, j in itertools.combinations(range(N), 2) if jaccard(sh[i], sh[j]) >= 0.75}
print(f"\nдокументов {N} (из них подмешанных почти-дублей {N-orig}), всех пар {total}")
print(f"кандидатов после LSH: {len(cand)} ({100*len(cand)/total:.3f}% всех пар)")
print(f"пар со сходством >= 0.75 по точному подсчёту: {len(true)}, найдено среди кандидатов: {len(true & cand)}")
missed = sorted(jaccard(sh[i], sh[j]) for i, j in true - cand)
print("сходство пропущенных пар:", [round(x, 2) for x in missed])
low = sum(jaccard(sh[i], sh[j]) < 0.5 for i, j in cand)
print(f"кандидатов со сходством < 0.5 (отсеет точная проверка): {low}")
inj = [(i, j) for i, j in true if i < orig and j < orig]
print(f"из них пар между исходными абзацами сайта (без подмешанных): {len(inj)}")
У нас этот код напечатал (весь запуск занял около двух секунд):
вероятность стать кандидатом, b полос по r строк (n = b*r = 112)
s=0.30 b=28,r= 4: 0.204 b=14,r= 8: 0.001 b= 8,r=14: 0.000
s=0.50 b=28,r= 4: 0.836 b=14,r= 8: 0.053 b= 8,r=14: 0.000
s=0.60 b=28,r= 4: 0.979 b=14,r= 8: 0.211 b= 8,r=14: 0.006
s=0.70 b=28,r= 4: 1.000 b=14,r= 8: 0.565 b= 8,r=14: 0.053
s=0.75 b=28,r= 4: 1.000 b=14,r= 8: 0.772 b= 8,r=14: 0.134
s=0.80 b=28,r= 4: 1.000 b=14,r= 8: 0.924 b= 8,r=14: 0.302
s=0.90 b=28,r= 4: 1.000 b=14,r= 8: 1.000 b= 8,r=14: 0.875
документов 866 (из них подмешанных почти-дублей 150), всех пар 374545
кандидатов после LSH: 58 (0.015% всех пар)
пар со сходством >= 0.75 по точному подсчёту: 47, найдено среди кандидатов: 46
сходство пропущенных пар: [0.87]
кандидатов со сходством < 0.5 (отсеет точная проверка): 1
из них пар между исходными абзацами сайта (без подмешанных): 0
Наша таблица для 14 × 8 совпала с опубликованными цифрами FineWeb (0,565; 0,772; 0,924 при сходстве 0,70; 0,75; 0,80). Разбиение 28 × 4 делает кандидатом почти любую пару со сходством от 0,5 — много лишней работы; 8 × 14 пропускает больше половины пар даже со сходством 0,8. На корпусе вместо 374 545 пар проверить пришлось 58 кандидатов. Из 47 пар со сходством от 0,75 найдено 46: одна пара со сходством 0,87 выпала по случайности — для неё вероятность пропуска меньше процента, но не ноль. Только один кандидат оказался непохожим (ниже 0,5) и отсеялся бы точной проверкой. Среди исходных абзацев сайта настоящих почти-дублей не нашлось: все найденные пары — подмешанные копии.
Где обычно ошибаются.
Словарь ступени.
Локально-чувствительное хеширование (LSH). Способ хешировать так, чтобы похожие объекты с большой вероятностью попадали в одну корзину.
Полоса (band). Кусок подписи из r чисел, по которому документы раскладывают по корзинам.
Корзина (bucket). Группа документов с одинаковым содержимым полосы.
Кандидат (candidate pair). Пара документов, совпавших хотя бы в одной полосе; её проверяют или сразу считают дублем.
S-образная кривая. График вероятности стать кандидатом в зависимости от сходства: ноль слева, единица справа, крутой подъём у порога.
FineWeb. Открытый веб-корпус Hugging Face (2024) для предобучения; его конвейер описан публично, включая настройки MinHash.
RefinedWeb. Веб-корпус, собранный для моделей Falcon; в опубликованном описании использовал MinHash с 9000 функций.
Зачем это в работе. Алгоритм из прошлых ступеней аккуратен только в среднем. На реальных данных он ошибается системно: склеивает разные документы в одну группу, принимает общий шаблон за совпадение содержания и не видит утечку проверочного вопроса, спрятанного внутри длинного документа. Эти ошибки не дают исключений в логах — они тихо выбрасывают хорошие данные или оставляют плохие, поэтому их нужно знать заранее.
Как это устроено. Цепочки. После LSH пары объединяют в группы: если A похож на B, а B на C, все трое считаются одной группой, и остаётся один документ. Такое объединение называют транзитивным замыканием (transitive closure); его обычно делают структурой «система непересекающихся множеств» (union-find). Опубликованное описание FineWeb прямо говорит о таком объединении. Проблема: A и C могут быть совсем непохожи, если правки накапливались по цепочке, — тогда из группы выпадает документ, который дублем никого не был.
Шаблоны. Меню сайта, подписи, предупреждения о куках, юридические сноски повторяются на тысячах страниц. У коротких документов такой шаблон занимает большую часть шинглов, и разные статьи с одним шаблоном выглядят дублями. Поэтому в конвейерах часто отдельно удаляют часто повторяющиеся строки (построчная дедупликация) до поиска почти-дублей по документам.
Утечки. Проверочный вопрос может быть небольшим куском длинного обучающего документа. Сходство Жаккара документов целиком тогда маленькое, потому что знаменатель — объединение всех шинглов. Для поиска утечек сравнивают не документы, а длинные совпадающие куски: например, в опубликованном отчёте о GPT-3 (Brown и соавторы, 2020) пересечение с проверочными наборами искали по совпадениям 13-словных кусков. Мера здесь другая — доля кусков вопроса, найденных в обучении, а не Жаккар.
Пересказы. Текст, переписанный другими словами или переведённый, не делит шинглов с оригиналом, и MinHash его не видит. Для этого есть смысловая дедупликация по эмбеддингам, например опубликованный метод SemDeDup (Meta, 2023), который удаляет близкие по вектору примеры. Она решает другую задачу и дороже: нужно прогнать каждый документ через модель-кодировщик.
Подробный пример. Три проверки на абзацах сайта. Первая — цепочка из девяти версий, где каждая следующая меняет два новых слова. Вторая — две разные новости длиной в одну фразу с общей подписью на 100 слов. Третья — проверочный «вопрос» (абзац из 63 слов), 35 слов которого вставлены в середину обучающего документа.
import random
from common import shingles, jaccard, norm
from corpus import paragraphs
random.seed(3)
docs = paragraphs()
# 1. Цепочка: каждый следующий текст правит 2 новых слова предыдущего
w = docs[50].split(); chain = [" ".join(w)]
pos = random.sample(range(len(w)), len(w))
for step in range(8):
for j in pos[step*2:(step+1)*2]: w[j] = "зпт"
chain.append(" ".join(w))
S = [shingles(t) for t in chain]
print("1) цепочка правок, сходство соседей:", [round(jaccard(S[i], S[i+1]), 2) for i in range(8)])
print(" сходство первого и последнего:", round(jaccard(S[0], S[-1]), 2))
# 2. Общий шаблон: два разных коротких текста с одинаковой длинной подписью
footer = docs[300]
a = "Цена токена у нового сервиса снизилась вдвое. " + footer
b = "Робот научился складывать бельё за минуту. " + footer
print("2) разные новости с общей подписью: сходство", round(jaccard(shingles(a), shingles(b)), 2))
# то же после вырезания повторяющихся строк-шаблонов
print(" после удаления подписи:", round(jaccard(shingles(a.replace(footer, "")), shingles(b.replace(footer, ""))), 2))
# 3. Утечка проверочного вопроса: совпадения по 13 словам
question = docs[400]
train_doc = docs[401] + " " + " ".join(question.split()[5:40]) + " " + docs[402]
def grams(t, n=13):
x = norm(t).split(); return {" ".join(x[i:i+n]) for i in range(len(x)-n+1)}
q, d = grams(question), grams(train_doc)
print(f"3) у вопроса {len(q)} 13-словных кусков, найдено в обучающем документе: {len(q & d)}")
print(" сходство Жаккара вопроса и документа целиком:", round(jaccard(shingles(question), shingles(train_doc)), 2))
У нас этот код напечатал:
1) цепочка правок, сходство соседей: [0.83, 0.76, 0.76, 0.83, 0.77, 0.76, 0.79, 0.76]
сходство первого и последнего: 0.17
2) разные новости с общей подписью: сходство 0.88
после удаления подписи: 0.0
3) у вопроса 49 13-словных кусков, найдено в обучающем документе: 22
сходство Жаккара вопроса и документа целиком: 0.13
Цепочка: каждые соседние версии похожи на 0,76–0,83 и при пороге 0,75 будут склеены в одну группу, хотя первая и последняя похожи всего на 0,17. Шаблон: две разные новости получили сходство 0,88 только за счёт общей подписи, а без неё — ноль. Утечка: Жаккар вопроса и документа 0,13, и документный поиск дублей её не заметит, но 22 из 49 13-словных кусков вопроса нашлись в документе — проверка кусками утечку видит сразу.
Где обычно ошибаются.
Словарь ступени.
Транзитивное замыкание (transitive closure). Объединение пар в группы по правилу «похож на похожего — значит, в той же группе».
Система непересекающихся множеств (union-find). Структура данных, которая быстро объединяет элементы в группы и отвечает, в одной ли они группе.
Построчная дедупликация (line-level deduplication). Удаление строк, которые повторяются на многих страницах, например меню и подписей.
Шаблонный текст (boilerplate). Повторяющиеся служебные куски страниц, не относящиеся к содержанию.
Проверка по 13-словным кускам. Поиск утечек по длинным совпадающим отрезкам текста, а не по сходству документов целиком.
Смысловая дедупликация (semantic deduplication). Удаление примеров, близких по смыслу, по расстоянию между их эмбеддингами.
SemDeDup. Опубликованный Meta в 2023 году метод смысловой дедупликации по эмбеддингам.
Словарь целиком — /slovar, новости — /novosti. Все дорожки — /put.