Автор:  (1) Брэндон Т. Уиллард, Нормальные вычисления;  (2) Реми Луф, Нормальные вычисления.  Таблица ссылок   Аннотация и введение   Выборка LLM и управляемая генерация   Итеративная обработка и индексирование конечного автомата   Расширения итеративного анализа   Обсуждение, ссылки и благодарности  3. Итеративная обработка и индексирование конечного автомата.   Точнее, мы рассматриваем регулярные выражения в 5-кратной конечно-автоматной форме [Sipser, 1996, Определение 1.5]:    (конечный автомат).  Определение 1 Конечный автомат или конечный автомат задается формулой (Q, Σ, δ, q0, F), где Q — конечное множество состояний, Σ — конечный алфавит, δ : Q × Σ → Q — функция перехода, q0 ∈ Q — стартовое состояние, а F ⊆ Q — множество состояний принятия.  Символы, составляющие строки в V, взяты из Σ: т.е. V ⊂ P(Σ). Везде состояния автомата Q для простоты будут представлены целыми значениями.      Пример 1. На рисунке 1 мы иллюстрируем процесс выборки автомата для регулярного выражения ([0-9]*)?\.?[0-9]*, которое можно использовать для генерации чисел с плавающей запятой. Для простоты пусть словарь V состоит только из строк: «A», «.», «42», «.2» и «1».   Когда начинается генерация, автомат находится в состоянии 0, поэтому наш алгоритм маскирует строку «А», поскольку она не будет принята автоматом. В этом случае мы можем выбирать только «.», «42», «.2» и «1».     Если мы выбираем «.2», мы переводим автомат в состояние 3. В этом случае только «42» и «1» являются допустимыми завершениями, поэтому мы маскируем другие значения перед выборкой. Если вместо этого мы выбираем «1», мы переводим автомат в состояние 1, и в этом случае «.», «.42», «.2» и «1» являются допустимыми завершениями, а маска остается неизменной.  Перебор словаря для определения допустимых следующих токенов по-прежнему остается самой большой проблемой. Для этого мы предварительно обрабатываем словарь, используя автомат регулярного выражения, и строим индекс. Важная часть заключается в том, что мы рассматриваем возможность запуска в каждом жизнеспособном состоянии автомата, поскольку строки в словаре могут соответствовать произвольным частям регулярного выражения, и эти части неявно являются состояниями автомата.  Процедура создания совпадений, начиная с любой точки автомата, приведена в алгоритме 3. Результатом является список подпоследовательностей, подробно описывающих состояния, через которые будет проходить автомат при принятии предоставленной строки.   Сопоставляя начальные состояния этих подпоследовательностей с последним состоянием автомата, достигнутым за один шаг цикла в алгоритме 2, мы можем эффективно индексировать словарь с помощью карты σ : Q → P(V), соединяющей состояния автомата. и наборы элементов словаря, которые будут приняты ФШМ в этих штатах.  Алгоритм 4 описывает построение σ.  Использование хеш-карты для σ может привести к тому, что шаг m в алгоритме 2 будет стоить в среднем всего O(1). Более того, поскольку σ создается вне процедуры выборки маркеров, ее стоимость во время выполнения фактически не имеет значения, хотя теоретически она требует памяти, равной количеству состояний в автомате (т. е. |Q|). К счастью, для непатологических комбинаций регулярных выражений и словарей не каждая строка в словаре будет принята автоматом, и не каждое состояние автомата будет представлено строкой в V.   3.1 Примеры  В этом разделе мы используем GPT2-среду (355M параметров), чтобы проиллюстрировать, как на практике работает генерация на основе регулярных выражений. Для их генерации мы используем библиотеку Outlines:   Листинг 3.1 (продолжение)   Листинг 3.3 (продолжение)   3.2 Сравнение с современными методами  Чтобы проиллюстрировать эффективность подхода индексирования, описанного здесь и реализованного в Outlines, мы проведем простое сравнение с библиотекой Guidance. На момент написания этой статьи библиотека Guidance использует частичное сопоставление регулярных выражений (применяется каждый раз с начала выборочной последовательности) и должна перебирать словарь LLM (N = 50, 257) на каждом шаге.  Код руководства и подсказка, используемые для этого сравнения, следующие:   Листинг 3.4 (продолжение)   Соответствующий код Outlines выглядит следующим образом:   Листинг 3.5 (продолжение)   Значение max_tokens варьируется, а время записывается с помощью timeit для одного цикла и одного значения повторения (т. е. для каждого значения max_tokens собирается только одна выборка). Результаты представлены в разделе 3.2.  За исключением каких-либо упущений в конфигурации, которые могут привести к значительному несоответствию во время выполнения, наблюдаемое масштабирование максимального количества выбранных токенов поразительно и указывает на растущую вычислительную проблему, подразумеваемую этим подходом.   Этот документ   под лицензией CC 4.0. доступен на arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

AI Models on HackerNoon

Этот звук создан на языке оригинала истории!

Слишком долго; Читать

Make resilience your competitive advantage

Эффективная управляемая генерация для больших языковых моделей: итеративная обработка и индексирование конечного автомата

About Author

КОММЕНТАРИИ

БИРКИ

ЭТА СТАТЬЯ БЫЛА ПРЕДСТАВЛЕНА В

Related Stories

Цифровые кочевники слушают: что нужно знать о новой визе DTV в Таиланде

Рост криптовалют: создание эффективных образов пользователей

Valhalla Флоки станет ассоциированным спонсором индийского тура по Шри-Ланке

Как улучшить ваш рабочий процесс в 10 раз: 17 основных приложений

Цифровые кочевники слушают: что нужно знать о новой визе DTV в Таиланде

Рост криптовалют: создание эффективных образов пользователей

Valhalla Флоки станет ассоциированным спонсором индийского тура по Шри-Ланке

Как улучшить ваш рабочий процесс в 10 раз: 17 основных приложений

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps