Поиск оптимальной регулярки для бинарной классификации строк

[melnikoff]

Всем привет!
Имеется, скажем, 10 строк и частота их встречаемости в логах. Я хочу отобрать из них только те, в которых подразумевается отдых/путешествие по городам России. А точнее, я хочу получить регулярку, которая с высокой точностью сможет повторить за мной (я предварительно сам размечаю строки классами) бинарную классификацию строк. На самом деле строк очень много – сотни и тысячи. Но я хочу отобрать топ-10/топ-100 строк, руками их разметить и на этих размеченных данный получить нужную мне регулярку, а затем натравить её на все остальные строки.
Рассмотрим пример из 10 строк. Я подобрал руками регулярку, которая хорошо приближает результат к желаемому:

regexp = '(?i)(?=.*(путешеств|отдых))(?=.*(росси|алтае|сочи))'

$TP = 200 + 15000 + 800 + 700 = 16700$
$FP = 500$
$FN = 0$
$precision = TP / (TP + FP) = 0.97$
$recall = TP / (TP + FN) = 1$
Вопросы знающей аудитории:
1) Существуют алгоритмы поиска оптимальных регулярок на размеченных данных? В какую сторону рыть?
2) Если регулярку не ограничивать в размерах, то она просто переобучится (на размеченных данных будет работать идеально, а на тестовой выборке – нет). Как это контролировать?
3) Хочется, чтобы регулярка обучалась на словах, а не на пунктуации или спец. символах.

[mihaild]

Скорее всего что-то "оптимальное" в смысле длины получится очень плохим.

А принципиально именно регулярку? Думаю даже w2v справится сильно лучше. А если задача чисто прикладная - то современная LLM скорее всего даже предварительной разметки не потребует.

[Mihaylo]

melnikoff в сообщении #1679599 писал(а):

Существуют алгоритмы поиска оптимальных регулярок на размеченных данных?

Использовать регулярное выражение просто, но обучать сложно, лучше отказаться. В вашем случае обучение с учителем не получается, только обучение с подкреплением, а это печально, да и подкрепление это так тяжело рассчитывается... Мне кажется, нужно ограничить регулярное выражение некоторой научно обоснованной формой (допустим той, которую придумали вы) и ... хз что дальше.
Регулярное выражение - это такая хрень, в которой интеллекту нечего делать. По моему определению, интеллект успешен только там, где есть избыток почти однородных преимущественно гладких и тому подобных данных и желательно учитель... Тексты, с которыми вы пытаетесь работать - норм, но правила регулярных выражений образуют целый мир, с которым трудно работать интеллекту. Один символ поменял - получил кардинальное изменение выхода... Это порождает очень большое количество глубочайших локальных минимумов при отсутствии ориентира (подкрепление может быть получено только после расчёта по всем строкам). Эти два фактора будут причинами неуспеха проекта.

[melnikoff]

mihaild в сообщении #1679607 писал(а):

Скорее всего что-то "оптимальное" в смысле длины получится очень плохим.

А принципиально именно регулярку? Думаю даже w2v справится сильно лучше. А если задача чисто прикладная - то современная LLM скорее всего даже предварительной разметки не потребует.

Да, если не контроллировать по длине, то регулярка просто переобучится за счёт длины.
Регулярку иметь принципиально, поскольку она передаётся на вход системе, которая работает только с ними.

[Mihaylo]

Ключевые слова! Найдите их и этого достаточно.

[Sonic86]

melnikoff в сообщении #1679599 писал(а):

Я хочу отобрать из них только те, в которых подразумевается отдых/путешествие по городам России. А точнее, я хочу получить регулярку, которая с высокой точностью сможет повторить за мной (я предварительно сам размечаю строки классами) бинарную классификацию строк. На самом деле строк очень много – сотни и тысячи. Но я хочу отобрать топ-10/топ-100 строк, руками их разметить и на этих размеченных данный получить нужную мне регулярку, а затем натравить её на все остальные строки.

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

(росси|алтае|сочи)

В общем виде $(c_1|c_2|...|c_k)$
Кусочков слов здесь м.б. довольно много. Пусть $N$ - размер датасета, $c_j$ - кусочек текста, фичи $x_j = \{c_j\text{встречается в тексте}\}$. Тогда текст матчится регуляркой $\Leftrightarrow x_1+x_2+...+x_k \geqslant 1$ - это у нас классификация. Если $n_j$ - кол-во примеров с $x_j=1$, то у нас будет задачка $\sum\limits_{j=1}^k |c_j| \to\min$. Если предположить, что $n_1\geqslant n_2 \geqslant ... \geqslant n_k$, то жадный алгоритм нашел бы регулярку $(c_1|c_2|...|c_s)$ для какого-то $s<k$. Т.е. уже тут надо балансировать между длиной регулярки и ее точностью/precision/recall. В более сложном виде получится, что мы учим какую-то булеву функцию (КНФ) на фичах $x_j$, но тут только перебор или еще какие-нибудь эвристики. Например, тоже взять $n_1\geqslant n_2 \geqslant ... \geqslant n_k$ и по каждой фиче дополнять регулярку, пока мы не упремся в ограничение по длине регулярки.