Вопрос или проблема
Я хотел бы протестировать экспериментальный алгоритм для классификации строк. Более точно, набор данных должен быть разделен на множество GOOD хороших строк и множество BAD плохих строк. Алгоритм должен обучить модель, согласующуюся с набором данных, в том смысле, что выходная модель всегда отвечает «Да» для строк из GOOD, «Нет» для строк из BAD. Алгоритм может вести себя произвольно для строк, которые не входят ни в GOOD, ни в BAD.
Обратите внимание, что я не заинтересован в прогнозировании для строк, не входящих в набор данных. Единственное важное – это получить модель, которая будет соответствовать данному набору данных. Что делает проблему интересной, так это то, что модель может быть значительно меньше, чем набор данных. Например, если модель – это автомат, то в некоторых случаях можно найти автоматы, которые в экспоненциальной степени меньше, чем количество бит, необходимое для представления набора данных.
Я хотел бы протестировать наши эвристики по сравнению с известными алгоритмами/наборами данных.
- Какие стандартные наборы данных используются для тестирования новых экспериментальных эвристик в этой области?
- Какие стандартные инструменты используются для таких задач классификации строк?
Примечание: Цель состоит в том, чтобы классифицировать строки, а не большие тексты. В частности, типичный размер рассматриваемых строк – 1000 символов (максимум). Кроме того, можно предположить, что эти строки имеют одинаковую длину.
Ваше описание соответствует общей проблеме грамматической индукции (или грамматической индукции): в отличие от статистических моделей, цель состоит в том, чтобы выучить точный язык, представленный в виде формальной грамматики. Важно, что это символическое обучение, т.е. нет понятия минимизации ошибок, потому что ошибки совершенно недопустимы.
Насколько я знаю, эта область довольно теоретическая, в отличие от статистического машинного обучения: формально доказывается, что некоторые классы языков могут или не могут быть выучены при определенных ограничениях. Один из типов учебных рамок, который раньше изучался в этом контексте (не уверен, что он все еще активен) – это идентификация языка на пределе. Совершенно другая рамка – это вероятно, приблизительно корректное обучение (PAC), но это более общее и не строго связано с грамматической индукцией (насколько я знаю).
Поэтому я не знаю ни одного реального набора данных: в общем, произвольные наборы данных не имеют таких формальных ограничений, которые актуальны для этой проблемы. Но возможно, что некоторые части литературы содержат по крайней мере искусственные наборы данных.
Ответ или решение
Наборы данных для классификации строк
Классификация строк представляет собой интересную задачу в области машинного обучения и теоретической информатики. Специфика вашей задачи заключается в необходимости разделения строк на два множества: GOOD (хорошие строки) и BAD (плохие строки). Ваша цель – разработать алгоритм, который сможет строить модель, соответствующую этим наборам, предоставляя однозначные ответы о принадлежности строк к каждому из классов.
1. Стандартные наборы данных
В контексте вашего запроса, несколько наборов данных могут быть полезными для тестирования алгоритмов и эвристик в области классификации строк. Однако, следует отметить, что большинство стандартных наборов данных для задач машинного обучения в основном ориентированы на другие типы данных (например, изображения или табличные данные). Вот несколько вариантов, которые могут подойти для вашей задачи:
-
NIST Handwritten Signature Database: Этот набор данных содержит подписи, которые можно интерпретировать как строки, представляющие собой определенные модели, что может быть полезно для изучения алгоритмов обработки и классификации.
-
Text standard datasets: Используйте наборы данных, которые состоят из строк текста, где каждая строка может быть определена как GOOD или BAD. Примеры включают наборы данных для фильтрации спама или классификации отзывов (например, IMDB или Amazon Customer Reviews).
-
Real-world Code Samples: Существуют наборы данных с фрагментами исходного кода, которые могут быть классифицированы по типу (например, GOOD – код без ошибок, BAD – код с ошибками).
Имейте в виду, что для таких наборов данных может потребоваться предварительная обработка с целью маркировки GOOD и BAD согласно вашему критерию.
2. Инструменты для классификации строк
Для выполнения данной задачи существует несколько стандартных инструментов и библиотек, которые могут помочь в обучении и тестировании ваших алгоритмов строковой классификации:
-
Automata Libraries: Библиотеки, такие как JFLAP, позволяют исследовать автоматы и грамматики, что может существенно упростить изучение моделей для классификации строк.
-
Python Libraries: Использование библиотек Python, таких как scikit-learn, предоставляет возможности для создания моделей и тестирования с использованием различных алгоритмов классификации, что полезно при работе с вашими данными.
-
Grammatical Inference Tools: Инструменты для индукции грамматик, такие как GIGI (Grammatical Inference Generator), могут быть полезны для создания моделей, соответствующих вашим требованиям, адаптируя их под задачи классификации строк.
Заключение
Вопрос классификации строк открывает новые горизонты в области машинного обучения, требуя точности и строгости в построении моделей. Ваша задача уникальна в том смысле, что требует строгой согласованности с заданными наборами для достижения успеха. Применяемые инструменты и наборы данных должны быть адаптированы к вашей специфике, что создаст прочную основу для тестирования ваших гипотез и разработки новых эвристик.
Для дальнейшего изучения рекомендую обратить внимание на литературу по теории автоматов и индукции грамматик, чтобы глубже понять теоретические основы данной области.