Искусственный Интеллект

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » Искусственный Интеллект » Макеты и реализации » Задача. Поиск сложного в сложном.


Задача. Поиск сложного в сложном.

Сообщений 1 страница 11 из 11

1

Есть выражение и еще база выражений, нужно из базы выбрать похожие.
Напоминает поиск регэкспа (regular expression), но не в тексте как обычно, а в базе регэкспов.

В начале было слово. Длиной 10-1000 букв. Потом слов стало много, 10-100 слов. Их проанализировали, выделили в них общее и описали всю группу одним выражением. Потом выражений тоже стало много, 1000000. Возник вопрос как искать новое выражение в этой базе.

Набор строк собирается в одно выражение с помощью скобок и операторов *?&|,
например выражение А,((Б&В)|(?Г,Д)) это образ для набора строк АГД, АД, АБВ, АВБ,

*n означает любые символы длиной до n
? перед символом означает что он может быть или не быть
, означает что разделяемые им символы идут в указанном порядке и оба нужны, задает порядок следования
| означает либо то что слева либо то-что-справа, задает множество вариантов
& означает оба символа в любом порядке, прямом или обратном, задает множество всех перестановок

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

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

Наиболее ценный образ должен выдаваться как можно быстрее, за ним все остальные.

0

2

Эта задача много где встречается кроме распознавания рукописного текста. Например Яндекс находит текст по словам, хотя не все слова могут присутствовать.
В общем-то все можно сделать прямо, но проблема в эффективности. Желательно как-то базу индексировать. Можно просто распаковать все выражения в строки из букв не содержащие операторов, проиндексировать это все (кстати индекс тоже похож на образ). Потом аналогично распаковать запрос и поискать все его варианты. Получится множество выборок, которые собрать (опять таки группу результатов тоже можно собирать в один образ).

Образы многозначные, наверняка потом будет выполняться перебор вариантов под некоторые условия. При поиске тоже возможен перебор вариантов при поиске унифицирующей два образа строки. Хорошо бы совместить эти два перебора, то есть указывать дополнительные условия при поиске. Например в запросе будет не один образ, а цепочка или дерево образов от более абстрактных и общих к конкретным и разным. Это так же реализует контекстное управление. Группа образов сама является образом, характеризующим некие тематику, стиль или что-то в этом роде. Желательно быстро перестраивать или фильтровать индекс с этими приоритетами.

Скорость проще получить как раз  за счет конкретности запроса. Просто выбираем самый уникальный элемент и сразу отбираем по нему небольшую часть базы.

0

3

Вместо "образа" я сначала думал "сигнатура", но оно сильно обобщилось и сейчас условно "образ", т.к. смысл его не до конца определен. Немного напоминает типизированную переменную, грамматику, шаблон.

Пока в виде дерева, без внутренней логики. А в принципе у такого еще могут быть правила вроде "если в этом ИЛИ-элементе из множества выбран такой вариант, то вот в этом нужно синхронно выбирать такой". Такие условия можно будет задавать списком образов, а пока не нужно.

0

4

три ассоциации возникло...
1. а почему не марковские цепи? они все-таки более понятны, чем регулярные выражения
2. регулярные выражения валидируют слово, но не продуцируют его, для открытого словаря мы всегда будет иметь проблему перестраивания...
3. непонятно в чем будет "выгода"... индекс по словам будет быстрее и удобнее индека по регулярным выражениям...

0

5

1. Марковские цепи - если вместо имен сделать ссылки получим то же самое дерево. Там просто уровни явно обозначены и рекурсия красиво делается, тут рекурсию не нужно. Можно и так. Особенно если какой-то оператор будет не удобным, придется разорвать выражение на группу выражений без этого оператора, а связывать их символами.
2. По регэкспам можно генерировать, только этого обычно не делают. Регэкспы переводят в конечный автомат и прогоняют через него текст. А можно просто случайно двигаться по автомату и выдавать по какой ветви пошли, если двигаться только по существующим ребрам получим только допустимые слова.
3. Я думал не про сами слова, а про признаки от препроцессинга, в которые перекодируется и картинка и словарь. А потом ищем одно в другом и вот такая работа получается. Признаков чем больше тем лучше, да еще комбинаторика, думаю просто "словами" их будет слишком много.

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

0

6

да, согласен, это похожие вещи, собственно, слово-продуцирующее дерево, о котором ты писал как самом простом варинте
- это тоже самое... наверное, все варианты имеют плюсы и минусы...
тогда непонятно - в именно заключается задача... :) :)

0

7

хочется чтобы все было быстро и красиво :)

0

8

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

0

9

Для разных языков будут разные деревья.
Т.е. это грамматика. Т.е. не семантика.

0

10

Конечно можно разные языки приводить к одному смыслу. Но тут вроде смысл один, это сами строки в раскодированном виде. Их слишком много.
Тут я пока тольком не представляю даже как сделать какую-нибудь "каноническую форму", чтобы два выражения с совпадающим смыслом обязательно выглядели в ней одинаково.

0

11

Множество точек из евклидового пространства описывается уравнениями. Нахождение точек, соответствующие двум уравнениями, называется решением системы уравнений.
Тут тоже пространство, но строк, совсем не евклидово. Два регэкспа типа уравнений, задают какие-то подпространства строк. Нужно найти все общие строки, или хотя бы одну, или самую значимую. В общем решить систему. 10000 раз при распознавании одной страницы.

0


Вы здесь » Искусственный Интеллект » Макеты и реализации » Задача. Поиск сложного в сложном.


Создать форум. Создать магазин