Волновой поиск пути в тексте
Алексей Тарасов @AtarКак работает поиск пути у животных
Для поиска пути на местности животные используют нейроны, называемые "клетки места". Эти нейроны активируются только, когда животное находится в определённых местах. Каждый нейрон "прикреплён" к конкретному месту на карте. Нейроны создают связи с топологически ближайшими соседями, формируя неориентированный плоский граф.
Для поиска пути по карте из текущей точки S к некоторой удалённой точки E используется механизм "волны огня". Начинается всё с активной клетки места, соответствующей текущему положению животного. Она передаёт активность связанным с ней клеткам, после чего на некоторое время переходит в неактивное, "выгоревшее" состояние. Активированные клетки делают тоже самое, при этом запоминая по каким связям к ним пришло возбуждение. Таким образом по графу прокатывается волна активности, на фронте которой происходит ориентирование задействованных связей.
Распространение прямой волны прекращается, как только активность достигает точки назначения. В этот момент из конечной точки запускается обратная волна, движущаяся против ориентированных связей (на рис. обратный пусть выделен жирными линиями).
Обратный путь может раздвоиться, но как только обратная активность достигнет начальной точки, будет выбрана клетка ближайшего пути. Животное перемещается в соответствующее этой клетке место и процесс повторяется заново.
Волновой поиск пути в тексте
"Путь в тексте" — это (моё) условное название для механизма генерации последовательности слов из некоторого заданного объема текста. От описанного выше механизма берутся следующие элементы: ориентированный граф и пускаемая по нему волна.
Из текста строится ориентированный граф, в котором вершинам соответствуют слова. Рёбра графа связывают слово с контекстными словами из некоторой постоянной окрестности, окна этого слова.
Вначале выбираем одно или несколько начальных, стартовых слов — это вершины, с которых начнётся движение волны.
Cуммируем у стартовых вершин их контекстные слова ("контекстное поле выбора") и отбираем оттуда TOP-n высокочастотных слов, на которые переходит активность. Получаем аналогичное движение волны по графу как и в поиске пути на местности, но с отличием в том, что может отсутствовать конечная точка. Тогда процесс заканчивается, когда у волны не остаётся дальнейших путей распространения.
Последовательность активаций вершин будет генерируемой, выходной последовательностью слов.
В качестве примера привожу цепочку слов, полученную на рассказе Милна.
Размер контекстного окна слева и справа от слова равен трём символам. Стартовые слова ("пух", "пятачок").
Результирующая последовательность:
сказал он и в что не я а потом на с ним за все это очень ты как раз еще немножко совсем никого было бы если мы его то кто нибудь чем о том дело спросил иа робин кристофер но только они когда она сказала сова вот ну да кролик был тигра ру крошка кенга где там нет у него про себя конечно меня есть или по моему так же тут ему голову пришла пуху винни пуха пятачка к дому из них для того после размышления долгого лучшая слышал ничего говорил потому ведь будет тогда лучше гораздо сегодня день рождения днем поздравляю тебя заметят шариком под себе нос ворча довольно пожалуй придется мне нужно сделать вид грустный такой м т ы н е ой мама кричал помогите закричал выходит здорово правда землю сел жжжжжжж громко повторил мед мог никак даже быстрее всех изо сил уперся спину им теперь всегда будем делать нечего совершенно зря бля вля написала надпись посмотрел вслед спускается видите очередь свою которая была такая штука которую можно тоже может быть хорошо медведем ура одиннадцать часов утром завтра до пор тех пока наконец понял сразу снова заговорил время последнее утрам делает эта мысль хорошая погода никакого слонопотама поймать решили пятачком глупым каким ореховым кустом далее плясать веселиться потерев могут тигры любят всего хорошего желаю много счастья этот момент тот случай всякий просто ай спасите полезу назад немного спустя полчаса через плечо кристоферу робину своему другу друг друга своего дома возле запруды речке экспедиция искпедиция глупенький мишка мой дорогой обедать пошел гости пятачку чтобы показать стараясь говорить сперва всей от бом тирлим скажите будьте обратно опять какой шум загадочный услышал минуту вышел лесу нас никто знал уходит стал объяснять стала откуда туда куда медленно плавно вдаль интересом искпедицию отправляемся дальше пошли домой побежал рысцой пустился
Видно, что некоторые закономерности в виде часто употребляемых словосочетаний такой алгоритм находит и пытается собрать в цепочку. Некоторые пары слов идут в обратном порядке, так как алгоритм не отслеживает с какой стороны находится контекстное слово (до или после центрального).
Ниже список отдельных кусков текста с правильным порядком, из которых сгенерирована эта последовательность.
кристофер робин
ему пришла в голову
тут пришла
винни-пуха к дому пятачка
после долгого размышления
не заметят под шариком тебя
поздравляю тебя с днем рождения
сегодня день рождения
с довольно важным видом, ворча себе под нос
пожалуй, придется
нужно сделать
такой грустный вид
кричал: "мама!", кричал: "помогите!"
ой, мама!
здорово, правда
здорово выходит
сел на землю
повторил пятачок очень громко
мед,- повторил
изо всех сил уперся в спину
теперь всегда тут будем
делать нечего
совершенно зря
надпись. - я тут написала
посмотрел ей вслед
спускается по лестнице вслед
свою очередь
такая штука, которую
хорошо быть медведем, ура!
завтра утром
одиннадцать часов
до тех пор, пока, наконец
сразу понял
снова заговорил
делает по утрам в последнее время
хорошая мысль
хорошая погода
решили поймать слонопотама
ореховым кустом
потерев нос. - веселиться. петь, плясать
тигры любят
всего хорошего
желаю много счастья
тот момент
этот момент
на всякий случай
ай спасите
полезу назад
спустя полчаса
кристоферу робину через плечо
своему другу
друг другу
своего друга
возле дома
в речке возле запруды
глупенький мишка
дорогой мой
пошел обедать
пошёл в гости к пятачку
стараясь не показать
услышал загадочный шум
стала объяснять
стал объяснять
отправляемся в искпедицию
пошли домой
пошли дальше
побежал домой
побежал рысцой
пустился рысцой домой
И ещё пара наблюдений. Всего слов в исходном тексте — 6524. Волна же в примере вовлекла 298 из них. Охват контекста в начале очень широк, более двух тысяч слов, затем быстро спадает и остаётся в постоянном диапазоне от десятков до сотни слов.
Причина первоначального всплеска — это результат попадания в очень высокочастотное по всему тексту слово — "сказал" (животные в рассказе любят поговорить), оно является хабом в графе. Хаб — это вершина, у которой число связей много выше среднего. Это приводит к тому, что большинство слов-вершин оказываются связаны друг с другом через общие хабы. Поэтому начало сгенерированной последовательности — это практически, пряжки по хабам с широкими контекстными полями.
А последующее "устаканивание" говорит о том, что фронт волны стабилен, нет комбинаторного взрыва, похоже скорее на ровное горение дров.
Ну и можно задавать конечное слово, по достижению которого будет останавливаться волна.