CS336, лекции 13–14: данные — откуда берутся и как их чистить

Перевод исполняемых лекций Перси Ляна (весна 2025): история датасетов для претрейна от BooksCorpus и Common Crawl до FineWeb, DCLM и Nemotron-CC, авторское право, данные для mid- и post-training; затем механика — фильтрация через KenLM, fastText и DSIR, определение языка, фильтры качества и токсичности, дедупликация хешами, фильтром Блума, MinHash и LSH.

Полный переводс языка: английский

Оригинал: Stanford CS336 (Spring 2025) — Lecture 13: Data (sources, datasets); Lecture 14: Data (filtering, deduplication) · исполняемые лекции на Python (lecture_13.py, lecture_14.py) и видео на YouTube · весна 2025
Автор: Перси Лян (Percy Liang), Stanford University
Лицензия оригинала: MIT (© 2025 Stanford University)

Текст оригинала переведён целиком, его лицензия это разрешает.

К урокам курса

Обе лекции — исполняемые программы: lecture_13.py и lecture_14.py. Текст переведён по порядку, код — с русскими комментариями, значения переменных — из трасс выполнения в репозитории (комментарии # → …). Картинки (схемы и таблицы из статей) не копируем: описываем их в квадратных скобках. В лекции 14 есть пример токсичного комментария из датасета Jigsaw — мы приводим его в смягчённом пересказе. Пояснения, которых нет в оригинале, помечены «Примечание переводчика». Видео — в плейлисте 2025 года, лекции 13 и 14.

Как читать вместе с курсом

Лекция 13 — «энциклопедия» датасетов. В курсе ей соответствует урок 5.1.2 «Данные для претрейна»; здесь гораздо больше подробностей о каждом датасете и разбор авторского права. Раздел о данных для SFT — к уроку 6.1.2, о длинном контексте — к 5.5.1.
Лекция 14 — механика: классификаторы качества, определение языка, дедупликация. Всё это вы будете реализовывать в задании 4 CS336, см. путеводитель по заданию 4.
Хешированием, n-граммами и вероятностями вы уже пользовались (модули 1.3 и 4.1); MinHash и LSH здесь объяснены с нуля.

Лекция 13. Данные: источники и датасеты

Прошлые лекции: как обучать модель при данных. Следующие две лекции: на каких данных обучать?

Введение

Смелое утверждение: данные — самое важное, что нужно сделать правильно при обучении языковых моделей.

Одно обоснование: посмотрим, что раскрывают компании. У моделей с открытыми весами (например, Llama 3) полная прозрачность архитектуры и даже процедуры обучения… но про данные почти ничего. [Снимок раздела статьи Llama 3 о данных: несколько общих фраз без конкретики.]

Причины секретности: (1) конкуренция и (2) риски, связанные с авторским правом.

До фундаментальных моделей работа с данными означала масштабную разметку для обучения с учителем.
Сейчас разметки меньше, но по-прежнему много отбора и чистки.
Данные — по сути задача «длинного хвоста», которая масштабируется человеческим трудом (в отличие от архитектур и систем).

Стадии обучения:

Претрейн (pre-training): обучение на сыром тексте (например, на документах из интернета).
Mid-training (промежуточное обучение): дообучение на данных высокого качества для усиления способностей.
Пост-трейнинг (post-training): дообучение на данных следования инструкциям (или RL) для следования инструкциям.

На практике границы размыты и стадий может быть больше… но базовая идея: от [большого количества данных невысокого качества] к [малому количеству данных высокого качества].

Терминология:

Базовая модель (base model): после претрейна + mid-training.
Instruct/chat-модель: после пост-трейнинга.

Пример — OLMo от AI2:

Претрейн [таблица OLMo 2: смесь DCLM-Baseline, StarCoder, peS2o, arXiv, OpenWebMath, Wikipedia — около 3,9 трлн токенов].
Mid-training [таблица Dolmino: отфильтрованный по качеству веб, FLAN, Wikipedia, математика, синтетика].
Пост-трейнинг (Tülu 3) [таблица SFT-смеси: инструкции, математика, код, безопасность].

Что это за датасеты? Как их выбирают и обрабатывают?

В файле лекции есть и функция framework() (в 2025 году её не вызывали): виды объектов данных — живой сервис (Reddit), сырой снимок (краулинг, API, дампы), обработанный текст, агрегированные датасеты (Dolma, The Pile); источники — разметчики, реальные пользователи (ShareGPT), отобранное из Common Crawl, дистилляция из более сильной модели, самодистилляция; добавляемые способности — решение задач, следование инструкциям, длинный контекст, заполнение пропусков, предметные области (код, математика, медицина), безопасность (отказы), рассуждения.

Претрейн

Заглянем в данные нескольких популярных моделей.

BERT (2019)

Статья. Данные BERT — это:

BooksCorpus. Smashwords основан в 2008 году и позволяет кому угодно самостоятельно издать электронную книгу; в 2024 году — 150 тыс. авторов, 500 тыс. книг. BooksCorpus (статья): бесплатные (по цене 0 долл.) самиздат-книги, собранные со Smashwords; 7 тыс. книг, 985 млн слов. Удалён, потому что нарушал условия использования Smashwords (Википедия).

Википедия — бесплатная онлайн-энциклопедия (случайная статья).

Основана в 2001 году.
В 2024 году — 62 млн статей в 329 языковых разделах (чаще всего английский, испанский, немецкий, французский).

Что в неё входит?

Нет оригинальных мыслей (мнений, рекламы, личных страниц и т. п.) (правило).
Статьи включаются по значимости (существенное освещение в надёжных источниках) (правило).

Кто пишет?

Редактировать может кто угодно в интернете, вандализм откатывают администраторы.
Небольшое число википедистов делает бо́льшую часть правок (например, Стивен Прюитт — 5 млн правок).
Периодические дампы раз в несколько недель (дампы).

Отступление: атаки отравления данных (статья).

Уязвимость: можно внести вредоносные правки прямо перед периодическим дампом, до того как их откатят.
Эксплойт: внедрить примеры, из-за которых модель будет приписывать негативную окраску фразам-триггерам (например, iPhone) (статья).
Вывод: даже качественные источники могут содержать плохой контент.

Важно: последовательности — это документы, а не предложения. Контраст: 1 Billion Word Benchmark [Chelba et al., 2013] — предложения из машинного перевода.

GPT-2: WebText (2019)

WebText — датасет для обучения GPT-2:

страницы по исходящим ссылкам из постов Reddit с карма ≥ 3 (заменитель качества);
8 млн страниц, 40 ГБ текста.

OpenWebTextCorpus — открытая репликация WebText:

извлекли все URL из датасета публикаций Reddit;
fastText от Facebook отфильтровал неанглийский текст;
удалили почти-дубликаты.

Common Crawl

Common Crawl — некоммерческая организация, основана в 2007 году.

Статистика:

примерно раз в месяц проводится обход веба (краулинг);
с 2008 по 2025 год — около 100 обходов;
в 2016 году обход занимал 10–12 дней на 100 машинах;
последний обход — апрель 2025 года;
обходы частично пересекаются, но стараются быть разнообразными.

Краулинг: используется Apache Nutch. [Схема веб-краулера.]

Начинает с набора начальных URL (как минимум сотни миллионов).
Скачивает страницы из очереди и добавляет найденные ссылки в очередь.

Политики:

политика выбора: какие страницы скачивать?
политика вежливости: соблюдать robots.txt, не перегружать сервер;
политика повторного посещения: как часто проверять изменения страниц;
трудность: URL динамические, множество URL ведут на практически одинаковое содержимое.

Два формата:

WARC: сырой ответ HTTP (например, HTML);
WET: преобразованный в текст (с потерями).

HTML в текст: инструменты trafilatura, resiliparse. Статья DCLM показывает, что способ преобразования влияет на точность на прикладных задачах. [Таблица: модели, обученные на тексте из resiliparse или trafilatura, заметно лучше, чем на WET-файлах Common Crawl.]

CCNet (2019)

Статья.

Цель: автоматический способ строить большие качественные датасеты для претрейна.
Особенно интересовало получение данных для малоресурсных языков (например, урду).

Компоненты:

дедупликация: удаление дублирующихся абзацев после лёгкой нормализации;
определение языка: классификатор языка на fastText; оставляем только целевой язык (например, английский);
фильтр качества: оставляем документы, которые похожи на Википедию с точки зрения 5-граммной модели KenLM.

Результаты: обучили модели BERT — CCNet (из Common Crawl) лучше Википедии. CCNet — это и инструмент с открытым кодом, и датасет из статьи.

T5: C4 (2019)

Colossal Clean Crawled Corpus (C4) (статья). Статья больше известна моделью Text-to-Text Transfer Transformer (T5), которая продвигает идею свести все задачи NLP к одному формату [схема: «translate English to German: …», «summarize: …» → текстовый ответ]… но важным вкладом был и датасет C4.

Наблюдение: Common Crawl в основном — не полезный естественный язык. Начали с одного снимка Common Crawl (апрель 2019, 1,4 трлн токенов).

Ручные эвристики:

оставлять строки, которые заканчиваются знаком препинания и содержат ≥ 5 слов;
удалять страницы, где меньше 3 предложений;
удалять страницы, где есть хоть одно «плохое слово» (список);
удалять страницы, содержащие { (никакого кода), «lorem ipsum», «terms of use» и т. п.;
отфильтровать неанглийский текст через langdetect (английский с вероятностью 0,99).

Итог: 806 ГБ текста (156 млрд токенов).

Анализ C4 (статья). [Диаграмма самых частых доменов C4: patents.google.com, en.wikipedia.org, nytimes.com и т. д.] Опубликовали сам датасет (а не только скрипты).

Бонус: датасет в духе WebText.

Отфильтровали страницы по ссылкам OpenWebText (ссылки в постах Reddit с карма ≥ 3).
По 12 дампам получили 17 ГБ текста (WebText был 40 ГБ — значит, Common Crawl неполон).
Это улучшило результаты на разных бенчмарках NLP (GLUE, SQuAD и др.).

GPT-3 (2020)

Датасет GPT-3 (статья, раздел 2.2):

Common Crawl (обработанный);
WebText2 (WebText, расширенный новыми ссылками);
(загадочные) книжные корпуса из интернета (Books1, Books2);
Википедия.

Итог: 570 ГБ (400 млрд токенов).

Обработка Common Crawl:

обучили классификатор качества отличать {WebText, Википедия, Books1, Books2} от остального;
нечёткая дедупликация документов (включая WebText и бенчмарки).

The Pile (2021)

Статья.

Ответ на GPT-3, часть усилий по созданию открытых языковых моделей.
Низовая инициатива: множество волонтёров координировались в Discord.
Собрали 22 качественных домена. [Таблица и диаграмма состава: Pile-CC, PubMed Central, Books3, OpenWebText2, arXiv, GitHub, FreeLaw, Stack Exchange и др.]
825 ГБ текста (около 275 млрд токенов).
Pile-CC: Common Crawl, берут WARC и конвертируют в текст через jusText (лучше, чем WET).
PubMed Central: 5 млн статей; работы, финансируемые NIH, обязаны быть открытыми.
arXiv: препринты научных статей с 1991 года (используется LaTeX).
Письма Enron: 500 тыс. писем 150 пользователей из высшего руководства Enron, опубликованы во время расследования (2002) (источник).

Project Gutenberg (сайт):

начат в 1971 году Майклом Хартом, который хотел расширить доступ к литературе;
в 2025 году — около 75 тыс. книг, в основном на английском;
включаются только книги, прошедшие проверку авторских прав (в основном общественное достояние);
PG-19: книги из Project Gutenberg до 2019 года (репозиторий).

Books3 [Presser, 2020]:

196 тыс. книг из теневой библиотеки Bibliotik;
содержал книги известных авторов (например, Стивена Кинга, Мин Джин Ли, Зэди Смит);
удалён из-за нарушения авторских прав и исков.

Теневые библиотеки (Википедия):

примеры: Library Genesis (LibGen), Z-Library, Anna’s Archive, Sci-Hub;
игнорируют авторское право и обходят платный доступ (например, Elsevier);
получали требования удаления, иски, блокировки в разных странах, но ограничения обычно обходят, серверы — в разных странах;
некоторые считают, что так становится свободным то, что и должно быть свободным;
в LibGen около 4 млн книг (2019), в Sci-Hub — около 88 млн статей (2022).

Meta обучала модели на LibGen (статья Forbes).

Stack Exchange:

набор сайтов вопросов и ответов, написанных пользователями;
начался со StackOverflow в 2008 году, разросся до других тем (математика, литература…) (сайты);
очки репутации и значки мотивируют участвовать;
формат «вопрос–ответ» близок к instruction tuning и реальному применению;
есть метаданные (пользователи, голоса, комментарии, значки, теги) для фильтрации;
дампы в XML (анонимизированы, с метаданными) (архив).

GitHub:

код полезен для задач программирования, а также (по фольклору) для рассуждений;
GitHub запущен в 2008 году, куплен Microsoft в 2018-м;
в 2018 году — как минимум 28 млн публичных репозиториев;
содержимое репозитория — это папка, не всё в ней код;
метаданные: пользователи, issues, история коммитов, комментарии к PR и т. д.;
много дубликатов (скопированный код, форки и т. д.).

GH Archive: почасовые снимки событий GitHub (коммиты, форки, тикеты, комментарии), есть и в Google BigQuery.

The Stack (статья):

взяли имена репозиториев из GH Archive (2015–2022);
git clone 137 млн репозиториев, 51 млрд файлов (уникальных — 5 млрд!);
оставили только файлы под разрешительными лицензиями (MIT, Apache) с помощью go-license-detector;
удалили почти-дубликаты через minhash и сходство Жаккара;
итог: 3,1 ТБ кода.

Gopher: MassiveText (2021)

Датасет MassiveText для обучения Gopher. Модель Gopher поглотила Chinchilla (обе так и не выпустили), но описание данных хорошее.

Компоненты: MassiveWeb (подробнее ниже); C4; книги, новости, GitHub, Википедия — без подробностей.

Фильтрация MassiveWeb:

оставляем английский, дедупликация, удаление пересечений с тестом;
фильтр качества по ручным правилам (не классификатором) — например, 80% слов должны содержать хотя бы одну букву;
Google SafeSearch для токсичности (а не списки слов).

Итог: 10,5 ТБ текста (хотя Gopher обучался только на 300 млрд токенов — 12%).

LLaMA (2022)

Датасет LLaMA (статья):

Common Crawl, обработанный CCNet; классификатор «похоже ли на страницы, на которые ссылается Википедия»;
C4 (разнообразнее; напомним: фильтрация по правилам);
GitHub: разрешительные лицензии, фильтрация по ручным правилам;
Википедия: июнь–август 2022, 20 языков, ручная фильтрация;
Project Gutenberg и Books3 (из The Pile);
arXiv: удалены комментарии, раскрыты макросы, удалена библиография;
Stack Exchange: 28 крупнейших сайтов, ответы отсортированы по рейтингу.

Итог: 1,2 трлн токенов.

Воспроизведён в RedPajama v1 от Together (датасет). SlimPajama от Cerebras: подмножество RedPajama v1 на 627 млрд токенов после дедупликации (MinHashLSH). Другое дело — RedPajama v2: 30 трлн токенов из 84 снимков Common Crawl, минимальная фильтрация, много сигналов качества (репозиторий).

RefinedWeb (2023) и FineWeb

RefinedWeb (статья):

тезис: веб-данных достаточно;
trafilatura для HTML → текст, извлечение содержимого (WARC вместо WET);
фильтрация: правила Gopher, без ML-фильтров, чтобы избежать смещений;
нечёткая дедупликация через MinHash по 5-граммам;
опубликовали 600 млрд (из 5 трлн) токенов.

FineWeb (датасет):

начинался как репликация RefinedWeb, но улучшил её;
95 дампов Common Crawl;
фильтрация URL, определение языка (оставляем, если $p(en) > 0{,}65$ );
фильтрация: правила Gopher, C4 и другие ручные правила;
нечёткая дедупликация через MinHash;
анонимизация email и публичных IP-адресов (персональные данные);
итог: 15 трлн токенов.

Dolma (2024)

Статья. [Диаграмма состава Dolma.]

Reddit: из проекта Pushshift (2005–2023), публикации и комментарии отдельно;
peS2o: 40 млн научных статей из Semantic Scholar;
C4, Project Gutenberg, Wikipedia/Wikibooks.

Обработка Common Crawl:

определение языка (классификатор fastText), оставляем английский;
фильтр качества (правила Gopher, C4), без фильтров на моделях;
фильтр токсичности: правила и классификатор Jigsaw;
дедупликация фильтрами Блума.

Итог: 3 трлн токенов.

DataComp-LM (2024)

Статья.

Цель: задать стандартный датасет, чтобы пробовать разные алгоритмы обработки данных.
Обработали Common Crawl и получили DCLM-pool (240 трлн токенов).
DCLM-baseline: DCLM-pool, отфильтрованный классификатором качества. [Схема воронки: от 240 трлн через эвристики, дедупликацию и классификатор к нескольким триллионам.]

Фильтрация на модели. Положительные примеры (200 тыс.):

OpenHermes-2.5 — в основном инструкции, сгенерированные GPT-4;
ELI5 — сабреддит с вопросами из любопытства и ответами «объясни как пятилетнему».

Отрицательные примеры (200 тыс.): RefinedWeb.

Итог: 3,8 трлн токенов. Обучили классификатор fastText и прогнали его по всему DCLM-pool. Этот классификатор качества лучше других методов фильтрации. [Таблица сравнения фильтров.]

Nemotron-CC (2024)

Статья.

FineWeb-Edu и DCLM фильтруют слишком агрессивно (удаляют 90% данных).
Нужно больше токенов (но с сохранением качества).
Для HTML → текст использовали jusText (не trafilatura), потому что он давал больше токенов.

Ансамбль классификаторов:

просим Nemotron-340B-instruct оценить документы FineWeb по образовательной ценности, дистиллируем в более быструю модель;
классификатор DCLM.

Перефразирование синтетикой:

данные низкого качества — переписываем языковой моделью;
данные высокого качества — генерируем по ним задания (пары «вопрос–ответ», извлечение ключевой информации и т. д.).

Итог: 6,3 трлн токенов (качественное подмножество — 1,1 трлн). Для сравнения, Llama 3 обучалась на 15 трлн, Qwen3 — на 36 трлн. [Таблица результатов.]

Авторское право

Вокруг генеративного ИИ много исков, в основном об авторском праве (трекер дел).

Право интеллектуальной собственности.

Цель: стимулировать создание интеллектуальных благ.
Виды: авторское право, патенты, товарные знаки, коммерческая тайна.

Авторское право.

Восходит к 1709 году в Англии (Статут королевы Анны) — впервые регулируется государством и судами.
В США последний закон — Copyright Act 1976 года.
Охраняются «оригинальные произведения авторства, зафиксированные на любом материальном носителе, известном сейчас или созданном позже, с которого их можно воспринимать, воспроизводить или иначе передавать непосредственно или с помощью машины или устройства».
Только оригинальные произведения, поэтому сборники (например, телефонные справочники) не охраняются, если в отборе или расположении нет творчества.
Охраняется выражение, а не идеи (например, quicksort).
Сфера расширилась с «опубликованного» (1909) до «зафиксированного» (1976).
Регистрация для охраны не нужна (в отличие от патентов).
Порог охраны крайне низок (например, ваш сайт охраняется авторским правом).
Регистрация нужна, прежде чем автор сможет подать иск о нарушении; стоит 65 долл.
Действует 75 лет, затем произведение переходит в общественное достояние (Шекспир, Бетховен, большая часть Project Gutenberg и т. д.).

Итог: большая часть интернета на самом деле охраняется авторским правом.

Как использовать охраняемое произведение:

Получить лицензию.
Сослаться на добросовестное использование (fair use).

Лицензии.

Лицензию (из договорного права) лицензиар выдаёт лицензиату.
По сути, «лицензия — это обещание не подавать в суд».
Лицензии Creative Commons позволяют свободно распространять охраняемые произведения.
Примеры: Википедия, Open Courseware, Khan Academy, Free Music Archive, 307 млн изображений с Flickr, 39 млн изображений с MusicBrainz, 10 млн видео с YouTube и т. д.
Созданы Лессигом и Элдредом в 2001 году как мост между общественным достоянием и действующим авторским правом.

Многие разработчики моделей лицензируют данные для обучения: Google и Reddit; OpenAI и Shutterstock; OpenAI и StackExchange.

Добросовестное использование (раздел 107). Четыре фактора:

Цель и характер использования (образовательное предпочтительнее коммерческого, преобразующее — воспроизводящего).
Природа произведения (фактическое предпочтительнее художественного, нетворческое — творческого).
Объём и существенность использованной части (фрагмент предпочтительнее целого).
Влияние на рынок (или потенциальный рынок) оригинала.

Примеры добросовестного использования:

посмотреть фильм и написать его краткое содержание;
заново реализовать алгоритм (идею), а не копировать код (выражение);
Google Books индексирует книги и показывает фрагменты (Authors Guild v. Google, 2002–2013).

Авторское право — не о дословном запоминании:

сюжеты и персонажи (например, Гарри Поттер) могут охраняться;
пародия, скорее всего, добросовестна.

Авторское право — о смысле (и экономике).

Соображения для фундаментальных моделей:

копирование данных (первый шаг обучения) — уже нарушение, даже если вы с ними ничего не делаете;
обучение ML-модели — преобразующее использование (далеко от копирования);
ML-системе интересна идея (например, знак «стоп»), а не конкретное выражение (художественные решения конкретного изображения знака).

Проблема: языковые модели определённо могут влиять на рынок (писателей, художников) — независимо от авторского права.

Условия использования. Даже если у вас есть лицензия или вы можете сослаться на добросовестное использование, условия использования сервиса могут накладывать дополнительные ограничения. Пример: условия YouTube запрещают скачивать видео, даже если они под лицензией Creative Commons.

Что почитать: конспекты CS324; Fair learning Lemley & Casey; Foundation models and fair use; The Files are in the Computer.

Mid-training и пост-трейнинг

Сосредоточимся на конкретных способностях.

Длинный контекст

Спрос на длинный контекст (хочется задавать вопросы по книгам):

DeepSeek-V3 — 128 тыс. токенов;
Claude 3.5 Sonnet — 200 тыс.;
Gemini 1.5 Pro — 1,5 млн.

Трансформеры масштабируются квадратично по длине последовательности. Претрейн на длинном контексте неэффективен — длинный контекст хочется добавлять позже.

LongLoRA (статья):

расширяет контекст Llama 2 7B с 4 тыс. до 100 тыс. токенов;
использует сдвинутое разреженное внимание (рисунок 2) и позиционную интерполяцию [Chen et al., 2023];
обучается на длинных документах: PG-19 (книги) и Proof-Pile (математика).

Задачи

Коротко: превращаем множество существующих NLP-датасетов в промпты.

Super-Natural Instructions (статья):

датасет: 1600+ задач (датасет);
дообучают T5 на k-shot (Tk-instruct);
задачи присылало сообщество (через GitHub);
примеры каждой задачи взяты из существующих датасетов и переведены в шаблонные промпты;
обходит InstructGPT, будучи гораздо меньше (?).

Flan 2022 (статья):

датасет: 1800+ задач (датасет);
дообучают T5 на zero-shot, few-shot и chain-of-thought версиях датасета (рисунок 7).

Инструкции и чат

Коротко: более открытые инструкции, активное использование синтетических данных.

Alpaca: датасет из 52 тыс. примеров от text-davinci-003 методом self-instruct (статья); дообучение LLaMA 7B.
Vicuna (пост): LLaMA, дообученная на 70 тыс. диалогов из ShareGPT (пользователи делились своими диалогами с ChatGPT; сейчас закрыт).
Baize (статья): датасет (111,5 тыс. примеров), сгенерированный GPT-3.5 в режиме «самочата» (затравки — вопросы с Quora и StackOverflow); дообучение LLaMA.
WizardLM (статья): датасет Evol-Instruct (вопросы «эволюционируют», чтобы увеличить охват и сложность); дообучение LLaMA.
MAmmoTH2 (статья): собрали WebInstruct — 10 млн инструкций из Common Crawl; фильтр — классификатор fastText, обученный на сайтах с тестами; извлечение пар «вопрос–ответ» через GPT-4 и Mixtral; дообучение Mistral 7B; заметно улучшает математику.
OpenHermes 2.5: собрание многих датасетов (датасет); Mistral 7B, дообученная на 1 млн примеров от GPT-4 (модель).
Llama 2 chat (статья): 27 540 примеров качественных инструкций от подрядчиков по разметке; по словам авторов, это лучше, чем миллионы примеров из открытых датасетов; можно было разметить меньше и сэкономить силы на сбор данных для RLHF.
Llama-Nemotron post-training data (NVIDIA): промпты из открытых датасетов (например, WildChat) или синтетические, затем отфильтрованные; синтетические ответы от Llama, Mixtral, DeepSeek-R1, Qwen (их можно использовать коммерчески, в отличие от GPT-4); включены трассы рассуждений.

Итоги

Главный урок: данные не падают с неба. Их приходится добывать.
Живой сервис ⇒ сырые данные ⇒ обработанные данные (конвертация, фильтрация, дедупликация).
Данные — ключевой ингредиент, отличающий языковые модели друг от друга.
Правовые и этические вопросы (например, авторское право и приватность).
Большая часть этого конвейера эвристична — много возможностей для улучшений!

Лекция 14. Данные: фильтрация и дедупликация

Прошлая лекция: обзор датасетов для обучения языковых моделей.

Живой сервис (GitHub) → дамп/краулинг (GH Archive) → обработанные данные (The Stack).
Обработка: HTML в текст, фильтрация по языку, качеству, токсичности, дедупликация.

Эта лекция: подробно о механике.

Алгоритмы фильтрации (например, классификаторы).
Применения фильтрации (язык, качество, токсичность).
Дедупликация (фильтры Блума, MinHash, LSH).

Алгоритмы фильтрации

Алгоритмический строительный блок: даны целевые данные T и много сырых данных R; найти подмножество T′ из R, похожее на T. [Схема: маленький круг T, огромный R, внутри R — область T′.]

Пожелания к алгоритму фильтрации:

обобщать с целевых данных (мы хотим, чтобы T и T′ различались);
работать чрезвычайно быстро (его надо прогнать по R, а R огромен).

n-граммная модель KenLM

n-граммная модель со сглаживанием Кнезера–Нея (Википедия).

KenLM: быстрая реализация, изначально для машинного перевода (код).
Распространённая языковая модель для фильтрации данных.
Чрезвычайно простая и быстрая — просто считаем и нормируем.

Оценка максимального правдоподобия n-граммной модели: при $n = 3$ $p(\text{in} \mid \text{the cat}) = \frac{\text{count(the cat in)}}{\text{count(the cat)}}$ .

Проблема: разреженные счётчики (при большом $n$ у многих n-грамм счётчик 0). Решение: сглаживание Кнезера–Нея для невиданных n-грамм — $p(\text{in} \mid \text{the cat})$ зависит и от $p(\text{in} \mid \text{cat})$ .

# Скачиваем модель KenLM, обученную на английской Википедии
model_url = "https://huggingface.co/edugp/kenlm/resolve/main/wikipedia/en.arpa.bin"
model_path = "var/en.arpa.bin"
download_file(model_url, model_path)
model = kenlm.Model(model_path)

# Используем языковую модель
def compute(content: str):
    # Грубая предобработка
    content = "<s> " + content.replace(",", " ,").replace(".", " .") + " </s>"
    # log p(content)
    score = model.score(content)
    # Перплексия нормирует на число токенов, чтобы не поощрять короткие документы
    num_tokens = len(list(model.full_scores(content)))
    perplexity = math.exp(-score / num_tokens)
    return score, perplexity

compute("Stanford University was founded in 1885 by Leland and Jane Stanford as a tribute to the memory of their only child, Leland Stanford Jr.")
# → score = -151.73, perplexity = 187.2
compute("If you believe that the course staff made an objective error in grading, you may submit a regrade request on Gradescope within 3 days after the grades are released.")
# → score = -180.82, perplexity = 204.0
compute("asdf asdf asdf asdf asdf")
# → score = -44.85, perplexity = 272.1
compute("the the the the the the the the the the the the the the the the")
# → score = -78.60, perplexity = 62.6

CCNet (статья):

элементы — абзацы текста;
сортируем абзацы по возрастанию перплексии;
оставляем верхнюю треть;
использовалось в LLaMA.

Итог: n-граммные модели Кнезера–Нея (в реализации KenLM) быстрые, но грубые.

Классификатор fastText

fastText (статья):

задача: классификация текста (например, тональности);
цель — обучить быстрый классификатор текста;
оказалось, что он не хуже гораздо более медленных нейросетевых классификаторов.

# Базовый вариант: мешок слов (это не то, что сделали авторы)
L = 32                              # Длина входа
V = 8192                            # Размер словаря
K = 64                              # Число классов
W = nn.Embedding(V, K)              # Параметры эмбеддингов (V x K)
x = torch.randint(V, (L,))          # Входные токены (L), например ["the", "cat", "in", "the", "hat"]
y = softmax(W(x).mean(dim=0))       # Выходные вероятности (K)
# Проблема: V*K параметров (может быть огромным)

# Классификатор fastText: мешок эмбеддингов слов
H = 16                              # Скрытая размерность
W = nn.Embedding(V, H)              # Параметры эмбеддингов (V x H)
U = nn.Linear(H, K)                 # Параметры головы (H x K)
y = softmax(U(W(x).mean(dim=0)))    # Выходные вероятности (K)
# Всего H*(V + K) параметров

Реализация: параллельный асинхронный SGD; learning rate линейно убывает от некоторого значения до 0.

Мешок n-грамм:

x = ["the cat", "cat in", "in the", "the hat"]
# Проблема: число биграмм может быть большим (и даже неограниченным)
# Решение: трюк с хешированием
num_bins = 8  # На практике — 10 млн корзин
hashed_x = [mmh3.hash(bigram) % num_bins for bigram in x]  # → [2, 1, 6, 4]

Для фильтра качества у нас $K = 2$ класса (хороший или плохой).
В этом случае fastText — просто линейный классификатор ( $H = K = 2$ ).

В общем случае можно использовать любой классификатор (например, BERT, Llama) — он просто медленнее.

DSIR: отбор данных через перевзвешивание по важности

Data Selection for Language Models via Importance Resampling (DSIR) (статья). [Схема: сырые данные, целевые данные, хешированные n-граммы, веса важности, перевыборка.]

Сначала само перевзвешивание по важности. Постановка: целевое распределение $p$ (хотим из него сэмплы), распределение предложений $q$ (из него сэмплы есть).

vocabulary = [0, 1, 2, 3]
p = [0.1, 0.2, 0.3, 0.4]
q = [0.4, 0.3, 0.2, 0.1]

# 1. Сэмплируем из q
n = 100
samples = np.random.choice(vocabulary, p=q, size=n)
# → в основном нули и единицы: [0 2 0 2 1 1 0 1 0 1 0 0 0 0 1 1 0 3 ...]

# 2. Считаем веса сэмплов (w пропорционально p/q)
w = [p[x] / q[x] for x in samples]  # → [0.25, 1.5, 0.25, 1.5, 0.667, ...]
z = sum(w)                          # → 90.42
w = [w_i / z for w_i in w]

# 3. Перевыборка
samples = np.random.choice(samples, p=w, size=n)
# → теперь в основном двойки и тройки: [2 2 1 3 3 2 0 3 3 2 1 0 3 ...]

Постановка DSIR: целевой датасет $D_p$ (маленький), датасет предложений (сырой) $D_q$ (большой).

Попытка 1:

подогнать целевое распределение $p$ к $D_p$ ;
подогнать распределение предложений $q$ к $D_q$ ;
перевзвесить по важности с $p$ , $q$ и сырыми сэмплами $D_q$ .

Проблема: целевых данных $D_p$ слишком мало, чтобы оценить хорошую модель.

Попытка 2: использовать хешированные n-граммы.

training_text = "the cat in the hat"

# Хешируем n-граммы
num_bins = 4
def get_hashed_ngrams(text: str):
    ngrams = text.split(" ")  # Пока униграммы
    return [mmh3.hash(ngram) % num_bins for ngram in ngrams]

training_hashed_ngrams = get_hashed_ngrams(training_text)  # → [3, 1, 1, 3, 3]

# Обучаем униграммную модель
probs = [count(training_hashed_ngrams, x) / len(training_hashed_ngrams) for x in range(num_bins)]
# → [0.0, 0.4, 0.0, 0.6]

# Вероятность любого предложения
hashed_ngrams = get_hashed_ngrams("the text")       # → [3, 0]
prob = np.prod([probs[x] for x in hashed_ngrams])  # → 0.0

Результат: DSIR немного лучше эвристической классификации (fastText) на бенчмарке GLUE. [Таблица результатов.]

Сравнение с fastText:

моделирование распределений — более принципиальный подход, учитывающий разнообразие;
похожая вычислительная сложность;
оба можно улучшить лучшим моделированием.

Итоги по фильтрации

Реализации: KenLM, fastText, DSIR. Обзорная статья об отборе данных.

Общая схема. Даны цель T и сырые данные R, найти подмножество R, похожее на T:

Оценить модель по R и T и вывести функцию оценки.
Оставить примеры из R по их оценке.

Варианты схемы:

Генеративная модель T (KenLM): $\text{score}(x) = p_T(x)$ ; оставляем $x$ с оценкой не ниже порога (стохастически).
Дискриминативный классификатор (fastText): $\text{score}(x) = p(T \mid x)$ ; оставляем $x$ с оценкой не ниже порога (стохастически).
Перевзвешивание по важности (DSIR): $\text{score}(x) = \frac{p_T(x)}{p_R(x)}$ ; перевыбираем $x$ с вероятностью, пропорциональной оценке.

Применения фильтрации

Одна и та же машинерия фильтрации годится для разных задач.

Определение языка

Определение языка: найти текст на конкретном языке (например, английском).

Почему бы просто не сделать модель многоязычной?

Данные: трудно отбирать и обрабатывать качественные данные на каждом языке.
Вычисления: в режиме ограниченных вычислений на каждый язык приходится меньше вычислений/токенов.

Модели различаются по многоязычности:

английский был лишь 30% данных BLOOM (недообучена), и качество на английском пострадало (статья);
большинство фронтирных моделей (GPT-4, Claude, Gemini, Llama, Qwen) сильно многоязычны (и достаточно обучены).

Определение языка в fastText (документация):

готовый классификатор;
поддерживает 176 языков;
обучен на многоязычных сайтах: Википедия, Tatoeba (сайт переводов) и SETimes (новости Юго-Восточной Европы).

Пример: Dolma оставляет страницы с $p(\text{English}) \ge 0{,}5$ .

# Скачиваем модель
model_url = "https://dl.fbaipublicfiles.com/fasttext/supervised-models/lid.176.bin"
model_path = "var/lid.176.bin"
download_file(model_url, model_path)
model = fasttext.load_model(model_path)

# Предсказания
model.predict(["The quick brown fox jumps over the lazy dog."])        # английский   → en, 0.716
model.predict(["The quick brown fox jumps over the lazy dog. The quick brown fox jumps over the lazy dog."])  # дубль → en, 0.719
model.predict(["OMG that movie was 🔥🔥! So dope 😎🤘!"])               # разговорный английский → en, 0.992
model.predict(["Auf dem Wasser zu singen"])                            # немецкий     → de, 0.975
model.predict(["The quadratic formula is $x = \\frac{-b \\pm \\sqrt{b^2 - 4ac}}{2a}$."])  # LaTeX → en, 0.489
model.predict(["for (int i = 0; i < 10; i++)"])                        # C++          → ru (!), 0.248
model.predict(["Hello!"])                                              # английский   → it (!), 0.440
model.predict(["Bonjour!"])                                            # французский  → fr, 0.867
model.predict(["Feliz Navidad / Próspero año y felicidad / I wanna wish you a Merry Christmas"])  # испанский + английский → es, 0.935

Оговорки:

трудно для коротких последовательностей;
трудно для малоресурсных языков;
можно случайно отфильтровать диалекты английского;
трудно для похожих языков (малайский и индонезийский);
плохо определено для смешения языков (например, испанский + английский).

OpenWebMath (статья):

цель: собрать большой корпус математических текстов из Common Crawl;
фильтр по правилам (например, есть команды LaTeX);
KenLM, обученный на ProofPile, — оставляем, если перплексия меньше 15 000;
классификатор fastText, предсказывающий математический текст: порог 0,17, если есть математика, и 0,8, если нет.

Итог: 14,7 млрд токенов; модели на 1,4B, обученные на них, лучше моделей, обученных на в 20 раз большем объёме данных.

Фильтр качества

Одни намеренно не используют фильтры на моделях (C4, Gopher, RefinedWeb, FineWeb, Dolma).
Другие используют (GPT-3, LLaMA, DCLM) [это становится нормой].

GPT-3 (статья, приложение A):

положительные: сэмплы из {Wikipedia, WebText2, Books1, Books2};
отрицательные: сэмплы из Common Crawl.

Обучаем линейный классификатор на признаках слов. Документы оставляем стохастически по оценке [график плотности распределения Парето]:

def keep_document(score: float) -> bool:
    return np.random.pareto(9) > 1 - score

LLaMA / RedPajama (статья):

положительные: сэмплы страниц, на которые ссылается Википедия;
отрицательные: сэмплы из Common Crawl;
оставляем документы, классифицированные как положительные.

phi-1 (статья). Философия: данные очень высокого качества (учебники), чтобы обучить маленькую модель (1,5B). Включает синтетические данные от GPT-3.5 (позже — GPT-4) и отфильтрованные данные.

R = "Python-подмножество The Stack"   # Сырые данные
prompt = "determine its educational value for a student whose goal is to learn basic coding concepts"
#        («оцени образовательную ценность для студента, который хочет выучить основы программирования»)
T = "GPT-4 с этим промптом размечает подмножество R из 100 тыс. примеров — получаем положительные примеры"

Обучаем классификатор «случайный лес» на T, используя выходные эмбеддинги предобученной модели codegen. Отбираем из R данные, которые классификатор считает положительными.

Результат на HumanEval:

модель 1,3B на Python-подмножестве The Stack: 12,19% после 96 тыс. шагов;
модель 1,3B на новом отфильтрованном подмножестве: 17,68% после 36 тыс. шагов — лучше!

Фильтр токсичности

Фильтр токсичности в Dolma. Датасет: Jigsaw Toxic Comments (2018) (датасет).

Цель проекта: помочь людям вести более качественные обсуждения в сети.
Данные: комментарии на страницах обсуждения Википедии с метками {toxic, severe_toxic, obscene, threat, insult, identity_hate}.

Обучили 2 классификатора fastText:

hate: положительные = {без метки, obscene}, отрицательные = всё остальное;
NSFW: положительные = {obscene}, отрицательные = всё остальное.

# Примеры из датасета (метка obscene, текст)
train_examples = [
    Example(label=0, text="Are you threatening me for disputing neutrality? I know in your country it's quite common to bully your way through a discussion and push outcomes you want. But this is not Russia."),
    Example(label=1, text="<грубое оскорбление с нецензурной бранью и пожеланием смерти — в оригинале дословно>"),
]

model_url = "https://dolma-artifacts.org/fasttext_models/jigsaw_fasttext_bigrams_20230515/jigsaw_fasttext_bigrams_nsfw_final.bin"
model_path = "var/jigsaw_fasttext_bigrams_nsfw_final.bin"
download_file(model_url, model_path)
model = fasttext.load_model(model_path)

model.predict([train_examples[0].text])  # → non-nsfw, 0.99995
model.predict([train_examples[1].text])  # → nsfw, 1.0
model.predict(["I love strawberries"])   # → non-nsfw, 1.0
model.predict(["I hate strawberries"])   # → non-nsfw, 1.0

Дедупликация

Два вида дубликатов:

точные дубликаты (зеркала сайтов, форки на GitHub) (зеркала Gutenberg);
почти-дубликаты: один и тот же текст, отличающийся несколькими токенами.

Примеры почти-дубликатов:

условия использования и лицензии (лицензия MIT);
шаблонные тексты (скопированные или сгенерированные по шаблону) [таблица примеров из статьи];
мелкие различия форматирования при копировании.

Описание товара, повторённое в C4 61 036 раз: «“by combining fantastic ideas, interesting arrangements, and follow the current trends in the field of that make you more inspired and give artistic touches. We’d be honored if you can apply some or all of these design in your wedding. believe me, brilliant ideas would be perfect if it can be applied in real and make the people around you amazed!» (страница-пример). [Корявый рекламный текст о свадебном дизайне — почему-то на странице противогаза.]

Дедупликация обучающих данных делает языковые модели лучше (статья):

обучение эффективнее (меньше токенов);
меньше запоминания (это смягчает проблемы авторского права и приватности).

Пространство решений:

Что считать элементом (предложение, абзац, документ)?
Как сопоставлять (точное совпадение, наличие общего подэлемента, доля общих подэлементов)?
Что делать (удалить все, удалить все, кроме одного)?

Ключевая трудность: дедупликация по сути сравнивает элементы друг с другом, а для масштаба нужны алгоритмы линейного времени.

Хеш-функции

Хеш-функция $h$ отображает элемент в хеш-значение (целое число или строку).
Хеш-значение гораздо меньше элемента.
Коллизия: $h(x) = h(y)$ при $x \ne y$ .

Компромисс между скоростью и стойкостью к коллизиям:

криптографические хеш-функции (SHA-256): стойкие к коллизиям, медленные (используются в биткоине);
DJB2, MurmurHash, CityHash: не стойкие к коллизиям, быстрые (для хеш-таблиц).

Будем использовать MurmurHash: mmh3.hash("hello") → 613153351.

Точная дедупликация

Простой пример: элемент — строка; сопоставление — точное совпадение; действие — удалить все, кроме одного.

# Исходные элементы
items = ["Hello!", "hello", "hello there", "hello", "hi", "bye"]
# Хеш -> список элементов с этим хешем
hash_items = itertools.groupby(sorted(items, key=mmh3.hash), key=mmh3.hash)
# Из каждой группы оставляем один элемент
deduped_items = [next(group) for h, group in hash_items]
# → ["hi", "bye", "hello", "hello there", "Hello!"]

Плюс: просто, ясная семантика, высокая точность.
Минус: не удаляет почти-дубликаты.
Код написан в стиле MapReduce — легко распараллелить и масштабировать.

C4: элемент — отрезки из 3 предложений; сопоставление — точное совпадение; действие — удалить все, кроме одного. Предупреждение: если отрезок из 3 предложений удалён из середины документа, документ может стать бессвязным.

Фильтр Блума

Цель: эффективная приближённая структура данных для проверки принадлежности множеству.

Свойства фильтров Блума:

экономны по памяти;
можно добавлять, но нельзя удалять;
если ответ «нет», то точно «нет»;
если ответ «да», то скорее всего «да», но с малой вероятностью «нет»;
долю ложных срабатываний можно уменьшать экспоненциально, тратя больше времени и вычислений.

def build_table(items: list[str], num_bins: int):
    """Строим таблицу фильтра Блума размера num_bins и вставляем в неё items."""
    table = bitarray(num_bins)
    for item in items:
        h = mmh3.hash(item) % num_bins
        table[h] = 1
    return table

def query_table(table: bitarray, item: str, num_bins: int, seed: int = 0):
    """Есть ли item в таблице?"""
    h = mmh3.hash(item, seed) % num_bins
    return table[h]

items = ["the", "cat", "in", "the", "hat"]
non_items = ["what", "who", "why", "when", "where", "which", "how"]

# Сначала сделаем диапазон хеш-функции маленьким (мало корзин)
m = 8  # Число корзин
table = build_table(items, m)   # → bitarray('01101001')
result = {item: query_table(table, item, m) for item in non_items}
# → {"what": 1, "who": 1, "why": 0, "when": 0, "where": 1, "which": 1, "how": 0}
num_mistakes = 4
false_positive_rate = num_mistakes / (len(items) + num_mistakes)  # → 0.444

Проблема: ложные срабатывания при малом числе корзин. Наивное решение: увеличить число корзин — вероятность ошибки $O(1/\text{num\_bins})$ , убывает полиномиально с памятью. Лучшее решение: использовать больше хеш-функций.

def build_table_k(items: list[str], num_bins: int, k: int):
    """Строим таблицу фильтра Блума размера num_bins с k хеш-функциями."""
    table = bitarray(num_bins)
    for item in items:
        for seed in range(k):             # для каждой из k функций
            h = mmh3.hash(item, seed) % num_bins
            table[h] = 1
    return table

def query_table_k(table: bitarray, item: str, num_bins: int, k: int):
    """1, если для всех k хеш-функций в таблице стоит 1."""
    return int(all(query_table(table, item, num_bins, seed) for seed in range(k)))

k = 2  # Число хеш-функций
table = build_table_k(items, m, k)
result = {item: query_table_k(table, item, m, k) for item in non_items}
# → {"what": 1, "who": 0, "why": 0, "when": 0, "where": 1, "which": 1, "how": 0}
num_mistakes = 3
false_positive_rate = 3 / (5 + 3)  # → 0.375

Доля ложных срабатываний уменьшилась!

Анализ доли ложных срабатываний. Предположим независимость хеш-функций и элементов (Википедия).

m = 1000   # Число корзин
k = 10     # Число хеш-функций
n = 100    # Число вставляемых элементов

# Рассмотрим тестовый элемент (не из множества), который хешируется в некоторую корзину i.
# Вставляем элементы в фильтр и смотрим, попадут ли они в i.

# Вставили 1 элемент — стала ли корзина B(i) равна 1?
# B: [0 0 1 0 0 0 0 0 0 0] — нужно 1 раз промахнуться
f = 1 / m                          # P[B(i) = 1 после 1 вставки с 1 хеш-функцией]  → 0.001
# B: [0 0 1 0 0 1 0 1 0 0] — нужно k раз промахнуться
f = 1 - (1 - 1 / m) ** k           # P[B(i) = 1 после 1 вставки с k хеш-функциями]  → 0.00996
# Вставили n элементов — нужно промахнуться k*n раз
f = 1 - (1 - 1 / m) ** (k * n)     # P[B(i) = 1 после n вставок]  → 0.632
# У тестового элемента k шансов промахнуться (он тоже хешируется k раз)
f = f ** k                         # P[ложное срабатывание]  → 0.0102

# Оптимальное k (при фиксированном отношении m / n) [даёт f ~ 0.5]
k = math.log(2) * m / n            # → 6.93
# Итоговая доля ложных срабатываний (улучшенная)
f = 0.5 ** k                       # → 0.0082

Компромисс между вычислениями ( $k$ ), памятью ( $m$ ) и долей ложных срабатываний ( $f$ ) (конспект).

Пример — Dolma: доля ложных срабатываний задана $10^{-15}$ ; элементы — абзацы.

Сходство Жаккара и MinHash

Теперь — приближённое сравнение множеств. Сначала нужна мера сходства.

Сходство Жаккара. Определение: $\text{Jaccard}(A, B) = \frac{|A \cap B|}{|A \cup B|}$ .

A = {"1", "2", "3", "4"}
B = {"1", "2", "3", "5"}

def compute_jaccard(A, B):
    intersection = len(A & B)  # → 3
    union = len(A | B)         # → 5
    return intersection / union

jaccard = compute_jaccard(A, B)  # → 0.6

Определение: два документа — почти-дубликаты, если их сходство Жаккара не ниже порога. Алгоритмическая задача: найти почти-дубликаты за линейное время.

MinHash: случайная хеш-функция $h$ , для которой $\Pr[h(A) = h(B)] = \text{Jaccard}(A, B)$ . Обычно хочется, чтобы разные элементы получали разные хеши… а здесь хочется, чтобы вероятность коллизии зависела от сходства.

def minhash(S: set[str], seed: int):
    return min(mmh3.hash(x, seed) for x in S)

Представление характеристической матрицей:

item | A | B
1    | 1 | 1
2    | 1 | 1
3    | 1 | 1
4    | 1 | 0
5    | 0 | 1

Случайная хеш-функция задаёт перестановку элементов. Смотрим, какой элемент первый в A и какой первый в B. У каждого элемента одинаковая вероятность оказаться первым (минимальным):

если первым оказался 1, 2 или 3, то первый в A = первый в B;
если первым оказался 4 или 5, то первый в A ≠ первый в B.

# Проверяем, что MinHash приближает Жаккара, как обещано
n = 100  # Сгенерируем столько случайных хеш-функций
matches = [minhash(A, seed) == minhash(B, seed) for seed in range(n)]
estimated_jaccard = count(matches, True) / len(matches)  # → 0.6
assert abs(estimated_jaccard - jaccard) < 0.01

Теперь мы можем хешировать элементы, но коллизия ещё не говорит, что $\text{Jaccard}(A, B)$ выше порога.

Хеширование, чувствительное к близости (LSH)

Locality sensitive hashing (LSH) (глава книги MMDS).

Пусть мы хешируем примеры всего одной функцией MinHash: $P[\text{A и B столкнутся}] = \text{Jaccard}(A, B)$ . В среднем более похожие элементы будут сталкиваться, но очень случайно… Цель: чтобы A и B сталкивались, если $\text{Jaccard}(A, B)$ выше порога. Вероятности надо как-то «заострить».

Решение: использовать $n$ хеш-функций, разбитых на $b$ полос по $r$ функций в каждой ( $n = b \cdot r$ ). Например, $n = 12$ , $b = 3$ , $r = 4$ :

h1 h2 h3 h4  |  h5 h6 h7 h8  |  h9 h10 h11 h12

Ключ: A и B сталкиваются, если в какой-нибудь полосе все её хеш-функции дают одинаковые значения. Как мы увидим, структура «И внутри полосы, ИЛИ между полосами» заостряет порог.

def get_prob_collision(sim, b, r):
    prob_match = sim ** r                        # Вероятность совпадения одной фиксированной полосы
    prob_collision = 1 - (1 - prob_match) ** b   # Вероятность, что совпадёт хоть одна полоса
    return prob_collision

get_prob_collision(sim=0.8, b=5, r=10)  # → 0.433

[График: вероятность коллизии от сходства — S-образная кривая.]

Сходство	0,7	0,75	0,8	0,85	0,9	0,95	0,98
$b = 10$ , $r = 10$	0,249	0,440	0,679	0,888	0,986	1,000	1,000
$b = 10$ , $r = 20$	0,008	0,031	0,109	0,327	0,726	0,988	1,000
$b = 20$ , $r = 20$	0,016	0,062	0,207	0,546	0,925	1,000	1,000

Рост $r$ заостряет порог и сдвигает кривую вправо (совпасть труднее).
Рост $b$ сдвигает кривую влево (совпасть легче).

[График нескольких S-образных кривых.]

Пример настроек (статья о дедупликации): $n = 9000$ , $b = 20$ , $r = 450$ .

b = 20
r = 450
# Где порог (где происходит фазовый переход)?
threshold = (1 / b) ** (1 / r)         # → 0.9934
# Вероятность совпадения фиксированной полосы:
prob_match = (1 / b)                   # → 0.05
# Вероятность, что A и B столкнутся (≈ 1 - 1/e):
prob_collision = 1 - (1 - 1 / b) ** b  # → 0.642

Итоги

Алгоритмические инструменты: n-граммные модели (KenLM), классификаторы (fastText), перевзвешивание по важности (DSIR).
Применения: определение языка, фильтр качества, фильтр токсичности.
Дедупликация: хеширование масштабируется на большие датасеты для нечёткого сопоставления.
Теперь у вас есть инструменты (механика) — осталось провести время с данными (интуиции).

Что сделать руками

Определение языка для русского и китайского. Установите fasttext, скачайте lid.176.bin (около 130 МБ — это не датасет, а небольшая модель) и проверьте её на коротких и длинных русских и китайских фразах, на смеси русского с английским и на коде. Где она ошибается?
MinHash + LSH своими руками. Реализуйте дедупликацию по шинглам из 5 слов для 1000 абзацев русской Википедии (или любых своих текстов), подставив $b$ и $r$ под порог 0,8. Проверьте, что почти-дубликаты (тот же абзац с парой изменённых слов) находятся, а разные абзацы — нет.
Фильтр Блума. Посчитайте, сколько памяти нужно фильтру Блума для 1 млрд абзацев при доле ложных срабатываний $10^{-15}$ , как в Dolma (подсказка: $m/n \approx -\log_2 f / \ln 2$ бит на элемент).
Перплексия как фильтр. Повторите пример с KenLM на своём тексте и найдите «плохой» текст с низкой перплексией (как повтор «the»). Придумайте простую эвристику, которая его отсеет.

Словарик

EN	RU
pre-training, mid-training, post-training	претрейн, промежуточное обучение, пост-трейнинг
base model, instruct/chat model	базовая модель, instruct/chat-модель
web crawl, WARC, WET	обход веба (краулинг), сырой HTTP-архив, извлечённый текст
data poisoning	отравление данных
language identification	определение языка
quality filtering, toxicity filtering	фильтр качества, фильтр токсичности
n-gram model, Kneser-Ney smoothing	n-граммная модель, сглаживание Кнезера–Нея
hashing trick	трюк с хешированием
importance resampling (DSIR)	перевзвешивание (перевыборка) по важности
synthetic data, rephrasing	синтетические данные, перефразирование
copyright, fair use, license, terms of service	авторское право, добросовестное использование, лицензия, условия использования
public domain, shadow library	общественное достояние, теневая библиотека
exact / near duplicates	точные дубликаты / почти-дубликаты
hash function, collision	хеш-функция, коллизия
Bloom filter, false positive rate	фильтр Блума, доля ложных срабатываний
Jaccard similarity, MinHash	сходство Жаккара, MinHash
locality sensitive hashing (LSH), bands	хеширование, чувствительное к близости, полосы

Перевод выполнен по лицензии оригинала (MIT (© 2025 Stanford University)); автор оригинала — Перси Лян (Percy Liang), Stanford University. Нашли неточность — сверяйтесь с оригиналом по ссылке выше. · обновлено 2026-10-04