LCS

Описание задачи

Longest Common Subsequence (LCS) / Самая длинная общая подпоследовательность — это алгоритмическая задача из BIG-bench. Данная задача состоит из пар строк на входе, языковые модели должны правильно предсказать длину самой длинной общей подпоследовательности между ними. Это пример задачи динамического программирования, позволяющий оценить способность моделей реализовать этот подход.

Мотивация

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

Описание датасета

Поля данных

instruction — строка, содержащая инструкцию для задачи и информацию о требованиях к формату вывода модели;
inputs — пример двух строк для сравнения;
outputs — строка, содержащая правильный ответ, размер самой длинной общей подпоследовательности;
meta — словарь, содержащий метаинформацию:
- id — целое число, обозначающее номер задания.

Пример данных

Ниже приведен пример из датасета:

{
      "instruction": "Даны две строки: \\"{inputs}\\"\\nОпределите длину их самой длинной общей подпоследовательности.",
      "inputs": "DFHFTUUZTMEGMHNEFPZ IFIGWCNVGEDBBTFDUNHLNNNIAJ",
      "outputs": "5",
      "meta": {
          "id": 186
      }
}

Разбиение данных

Датасет содержит 320 примеров в открытом тесте (train split) и 500 примеров в закрытом тесте (test split) .

Промпты

Для датасета было подготовлено 6 промптов различной сложности. Пример:

"Для двух строк: \\\\"{inputs}\\\\" найдите длину наибольшей общей подпоследовательности. Пересекающиеся символы должны идти в том же порядке, но могут быть разделены другими символами.".

Создание датасета

Для тестового набора были сгенерированы последовательности различной длины в диапазоне [4; 32) с помощью Python скрипта. Для открытого теста данных были взяты из соотвествующей задачи BIG-bench.

Открытые данные сгенерированы с тем же seed, что и их публичный аналог в Big-Bench.

Оценка

Метрики

Задача оценивается с помощью Accuracy.

Человеческая оценка

Человеческая оценка замерялась на подмножестве размера 100 (с аналогичным распределением как в исходном сете). Результат на этой задаче равен 0.56.

Задачи

LCS