[recovery mode] Прогнозирование
Я уже писал, зачем нужно такое прогнозирование — Создание искусственного интеллекта.
Здесь же я буду описывать только алгоритм прогнозирования, без лишней лирики.
Рассматривать буду прогнозирование последовательности байтов или же текста UTF-8. Прогнозирование последовательности дробных чисел — графиков — во многом подобно, только нужно значения сравнивать не на равенство, а на принадлежность окрестностям.
Пусть будет поток байтов (или скажем текст UTF-8) — входящие прогнозируемые данные. Поступающие данные сохраняем во множество сохраненной истории. Каждое очередное поступающее значение учитываем в структуре для накопления статистики:
struct Stat {
uint value; // прогнозируемое значение
uint count; // количество прошедших таких значений
// функция index используется шаблонным классом Index - ключ для rb-дерева
static uint index(const Stat& s) { return s.value; }
Ptrn* owner;
double probability() const { return (double)count/(double)owner->sum_count_of_stat; }
};
// шаблонный класс Index это rb-дерево,
// первый параметр шаблона — тип значения по которому происходит сортировка,
// второй, это класс сохраняемых значений в узлах. Этот класс должен содержать
// функцию index.
struct Ptrn {
// узел, подсчитывающий, какое распределение вероятностей будет
// следовать за значением value
uint value;
Index index_of_stat; // распределение вероятностей
uint sum_count_of_stat;
// путем добавления к текущему value еще в лево
// будут образовываться паттерны
Index index_of_prev;
static uint index(const Ptrn& s) { return s.value; }
Ptrn* owner; // owner->index_of_prev->find(value) == this,
// для root этот owner равен nullptr
};
Ptrn root;
В узле root считаем статистику всех прошедших значений. Вероятность каждого из значений будет количество этого значения делить на количество всех значений. Сумма вероятностей Stat находящихся в root равна единице — распределение вероятностей значений во входящем потоке. Выбрав Stat из root с наибольшей вероятностью, получаем первый прогноз — очередной символ на входе в наш алгоритм скорее всего будет именно этот, с вероятностью посчитанной в этом узле Stat.
Поступает на вход очередное значение. Его сначала добавим в статистику узла root. После, для сохраненного входящего значения предыдущего шага, находим или создаем в root в index_of_prev узел Ptrn соответствующий предыдущему значению, и в этот узел так же добавляем в статистику текущее значение.
Узел root будем называть нулевым уровнем прогнозирования. Множество index_of_prev в root будем называть первым уровнем прогнозирования.
Первый уровень содержит более точные прогнозы, чем нулевой — вероятности прогнозирования значений, при условии что предыдущее значение было таким-то. Но сумма вероятностей в каждом узле все равно остается единицей.
Когда в каком-либо узле первого уровня накапливается достаточно статистики, что бы можно было утверждать, что дальнейшее накопление в этом узле не приведет к сильному изменению распределения прогноза, то этот узел дает ветви в index_of_prev — для этого узла создается второй уровень. По сохраненной истории сразу считаем статистику для этих ветвей, для тех, которые уже прошли и были сохранены в истории.
И так будем ветвить от root через index_of_prev. Каждый Ptrn идентифицирует паттерн — цепочка последовательных значений складываемая от текущего Ptrn до root через свойство owner, и распределение вероятностей значений прогноза следующего за этим паттерном.
Чем длинее паттерн, тем больше определенности, что именно за ним последует. Но чем длиннее паттерн, тем реже он встречается, и может не набраться достаточно статистики по конкретному паттерну. Т.е. какой-то паттерн в накопленной истории встретился всего три раза — вряд ли замер из трех случаев будет показательным, какое значение последует за ним, и нужно использовать более короткий паттерн, имеющий большую определенность, но более размытое распределение прогноза, пока более длинный не накопит достаточно статистики.
Некоторые паттерны, которые имеют уже достаточную статистику, они имеют точный прогноз — из ста случаев нахождения этого паттерна, за ним всегда следовало одно и то же значение. Для таких паттернов не нужно строить более длинные паттерны — для более длинных результат распределения будет такой же. Хотя при детальном рассмотрении последующих усложнений, такие ветви все же понадобятся.
Дальше оговорюсь, что я в этом описании опускаю многие детали, которые только усложнят описание, и будут мешать формулированию общей сути. Одна из таких деталей, что точный прогноз скажем сто из ста случаев, является на самом деле не точным, а приближенным — стопроцентных вероятностей в прогнозировании не бывает. И в процессе дальнейшего накопления статистики по этому паттерну когда-нибудь все равно встретится отличное значение. Пока считаем, что он не будет меняться.
Разделим накопленные статистики на определившиеся и не определившиеся. Скажем, если sum_count_of_stat в Ptrn становится больше ста, то его начинаем считать определившимся, и по нему начинаем считать подветви index_of_prev. (Хотя не для всех случаев необходимо накапливать до ста).
Те, которые определившиеся, разделим на точные (с точным прогнозом), и не точные.
В общем, накапливаем дерево паттернов, и подсчитываем прогнозы для ситуаций которые они идентифицируют.
Теперь будем считать подобия прогноза. Для тех паттернов, для которых из-за недостаточности или отсутствия статистики не можем определить прогноз, но по каким-либо признакам, можем определить, что его прогноз будет подобен прогнозу другого паттерна, который уже определен, и будем брать прогноз из подобного.
У каждого определившегося паттерна есть множество подветвей в index_of_prev. Что бы понимать, что такое подветвь, вот алгоритм ее получения от паттерна:
// к паттерну ptrn добавляем слева паттерн sub_branch,
// и если такой получающийся паттерн уже определен в дереве паттернов,
// то возвращаем его, иначе nullptr
Ptrn* get_sub_branch(Ptrn* ptrn, Ptrn* sub_branch) {
if (sub_branch->owner == nullptr) return ptrn;
Ptrn* lev = get_sub_branch(ptrn, sub_branch->owner);
if (lev == nullptr) return nullptr;
return lev->index_of_prev.find(sub_branch->value);
}
Можно группировать паттерны в группы по подобию их ветвей. Другими словами классифицировать множество накопленных паттернов.
Но подобие должно быть не наличия подветвей, а распределения прогноза в них. Т.е. если считаем для двух паттернов подобие их подветвей, то считаем как коррелирует распределение прогноза среди подветвей, которые у этих паттернов общие.
Если накопили некую группу паттернов, для которых некая часть подветвей у них подобна по прогнозу, то для всякого нового паттерна, для которого убедились, что он входит в эту группу, для всех его подветвей, в том числе еще недоопределенных, прогнозы будут подобны тем, что в группе.
Обращаю внимание, что подобна лишь часть подветвей. Так, что бы было подобно все множество подветвей — это очень редкий случай подобия.
Как определяем для новых паттернов, для которых статистика по подветвям еще не определилась, что они принадлежат ли какой-либо группе:
Если у паттерна определились хотя бы парочка подветвей, по которым считалось подобие в группе принадлежность к которой тестируем, и эта пара подветвей подобна по прогнозу тем, что в группе, то смотрим, достаточно ли этих двух подветвей что бы идентифицировать принадлежность этой группе.
Для этого находим все паттерны, для которых именно эти две подветви подобны. И для всех найденных паттернов, смотрим, все ли они принадлежат тестируемой группе. Если какие-то из найденных не принадлежат группе, по причине, что какая-то их подветвь не подобна соответствующей подветви в группе, и у этого не принадлежного, эта подветвь имеет определившуюся статистику, то значит тех двух определившихся подветвей недостаточно для однозначной идентификации принадлежности к группе.
В каких-то случаях будет достаточно двух идентификационных подветвей, в каких-то трех или более.
Дальше можно было бы описывать, какими формулами и алгоритмами считать эти подобия, но скажу сразу, что решать эту задачу в лоб, в том виде как я ее описал выше — невозможно из-за большого количества расчетов.
И поэтому будем считать только наиболее значимую часть — сравнивать подобия только по ветвям с точным прогнозом. Если у двух паттернов, есть одинаковая подветвь, в обоих случаях у них точный прогноз (т.е. распределение состоит из одного значения), и этот прогноз равен, то эти ветви подобны. Если в одном из случаев прогноз не точен, то ветви не подобны. Т.е. ноль или один. Случаи, где оба прогноза не точны, не рассматриваем, т.к. группировать будем в группы с точным прогнозом, а все прочие отбрасывать.
Для каждого нового паттерна, когда его прогноз становится определенным, и если он точен, то включаем его в группу Group, в объект postfix_root (этот класс отделен, потому что чуть позже это будет деревом):
struct Postfix {
List list_of_ptrn; // сюда добавляется паттерн с точным прогнозом
uint count_on_prev_calc_similarity;
// это для алгоритма ветвления — чуть позже
uint value; // значение откушенного постфикса
Index index_of_next;
static uint index(const Postfix& s) { return s.value; }
Postfix* owner; // для postfix_root это равно nullptr
};
struct Group {
uint value; // значение точного прогноза
Postfix postfix_root;
static uint index(const Group& s) { return s.value; }
};
Index index_of_groups;
При накоплении в группе некого минимального количества паттернов, скажем сто штук, будем запускать алгоритм пересчета подобий (про который дальше). А так же, при дальнейшем накоплении паттернов в группе, при достижении количества в два раза большего, чем было при прошлом расчете (сохраняем в count_on_prev_calc_similarity), так же запускаем пересчет.
Из чего состоит алгоритм поиска подобий.
Вот в одной из групп в postfix_root накопилось множество паттернов — для них для всех прогноз точен и одинаков. Из postfix_root создаем следующий уровень Postfix — для каждого паттерна, берем его крайнее левое значение, и по нему создаем в postfix_root→index_of_next соответствующий Postfix, в который добавляем тот паттерн, от которого взяли крайний левый символ. Только добавляем без этого левого символа.
Получилось, что расщепили множество list_of_ptrn на подмножества, по крайнему левому значению, убрав из новых множеств это левое значение. И так рекурсивно расщепляем все, для которых в образовывающихся Postfix количество list_of_ptrn больше ста. Паттерны в этих множествах при этом от уровня к уровню становятся меньше — отщепляются крайние левые, и если паттер уперся в root — длина после откусываний стала нулевой, то такой паттерн на следующий уровень не пойдет.
Тем самым получаем, сгруппированные множества паттернов, для которых хотя бы одна ветвь подобна.
Дальше, для каждого множества в Postfix, от получившегося множества, начинаем сканировать возможные ветви от паттернов, по всем, за исключением той ветви, по которой был получен обратным ходом от Group текущий Postfix. Перебираем ветви виртуального дерева, состоящего из объединения ветвей входящих во множество паттернов:
struct ScanItem {
Ptrn* ptrn_of_postfix; // исходный взятый из postfix паттерн
Ptrn* ptrn_of_scan; // а это образованный от исходного добавлением сканируемого
};
struct Scan {
uint value;
List list_of_items;
Index index_of_next;
static uint index(const Scan& s) { return s.value; }
Scan* owner;
};
// в класс Postfix добавляем объект:
Scan scan_root;
Получающиеся множества паттернов при этом группируем по их прогнозу — если у них есть точный прогноз, и тогда подгруппа сгруппированная по точному прогнозу от множества в Postfix это будет множество паттернов, имеющих уже две подобные ветви.
Дальше, от множества паттернов с двумя подобными ветвями, дальше сканируем и расщепляем на подмножества с тремя, четырьмя, и т.д. подобными. Причем, в момент, когда найденное количество ветвей подобий становится достаточным для идентификации, то дальше множество уже не будет расщепляться, а новые находимые ветви подобий будут скорее подтверждаться для всего оставшегося множества.
Общая схема получилась такой:
Было одно большое множество всех паттернов, из них выделили множество имеющих точный прогноз, разделили на подмножества по значению прогноза, после разделяем по первой ветви подобия и оставшемуся откусанному паттерну, и это множество паттернов, с одной подобной ветвью начинаем сканировать и делить на прочие подобные ветви.
При сканировании могут находится дубли — сначала обратным ходом прошли по ветви А, а после при сканировании получили Б. Затем, обратным ходом начали от Б, и пришли к А. Дублирования сканировать нет смысла и их нужно отсекать.
До этого описывал подобия для прогноза следующего непосредственно за группой и назвал это отсечением постфиксов. Теперь нужен такой же принцип, но отсекаться будет префикс.
Зачем это: это будет искать группы паттернов, для которых прогноз одинаков. Он может быть разным для разных префиксов, но в пределах одного он одинаков. И если для такой группы нашли новый префикс, для которого удостоверились по признакам идентификации, что он работает, то уже не обязательно дожидаться определившейся статистики для всей группы. Приводить описание класса и алгоритма не буду, достаточно сказать, что симметричен поиску постфиксов.
Когда мы искали постфиксы, мы выводили дистанции на которых действует одна и та же функция: паттерн Х однозначно отображался на прогноз У для всех дистанций в группе. Когда мы ищем префиксы, мы ищем подобия не дистанций, а значений — множество значений, для которых прогноз одинаков.
Когда мы находим очередное отображение Х→У по постфиксам, то в результате накапливаются типизированные множества Х и У. Способ вывода границ значений этих множеств, которые не прилегают к дистанции, пока еще под вопросом. И пока скажу без него. Среди множеств находимых функций, некоторые будут иметь одинаковое множество Х. Тогда значение Х становится объектом, имеющим несколько свойств — каждая функция это отдельное свойство. При этом подобные дистанции для получения какой-либо из этих функций становятся способами получения свойств этого объекта. По сути, это есть базовый принцип преобразования текста (или другого типа информации) в базу данных — в таблички с их свойствами.
Прогнозировать можно не только значение, но и группу значений (группу подобных дистанций или подобных значений). Т.е. до этого прогнозом было значение входящего потока. Когда алгоритм поглотил и отнес это значение к какой-либо группе, то дальше мы можем составить статистику аналогичную прогнозированию значения, является ли анализируемое значение элементом группы. И тогда, для новых поступающих значений, мы заранее не накапливая по ним вообще никакой статистики, можем отнести их к группе и использовать. На таком принципе происходит в мозгу идентификация новых слов в тексте — по окружению мы вычисляем, это существительное, или это прилагательное, и прочие разные свойства — при том, что само слово видим в первый раз.
Еще могу упомянуть, что постфикс и префикс у групп не являются строго либо то, либо другое. При сканировании подобий более полным будет алгоритм, который перебирает их вместе — с каждым постфиксом проверять все префиксы, и наоборот, с каждым префиксом все постфиксы. И при обратном и при прямом сканировании.
Описанные принципы, это лишь кусочек от полной картины, какие подобия нужно искать:
Нужно сделать сканирование последовательно нескольких групп подобий — когда группы подобий располагаются в сканируемых ветвях текущей тестируемой группы — тут свои правила суммирования множеств. А так же сканирование вложенных групп.
Нужно сделать квантификаторные множества — определение значений не по конкретному запомненному паттерну, а запоминаем шаблон, что-то вроде регулярного выражения.
Нужно сделать, что бы сканер ветвей мог переходить не от символа к символу, а по разметкам групп, и при этом не обязательно только в одном направлении, а скажем прыгаем через группу, разворачиваемся, и начинаем сканировать элемент группы посимвольно, но с другого конца.
Потом еще работа со множествами, на предмет непрерывностей и упорядочивания.
И т.д и т.п….
И наверняка есть еще куча свойств, про которые я не задумывался.
На описанный алгоритм с постфиксами у меня уже есть исходники на С++, но они не подготовлены как конечный результат и требуют некоторой доработки — сейчас на это нет времени, потому не прилагаю. Но если будут особо желающие разбирать не подготовленные и не упорядоченные исходники — могу скинуть лично. (под QT x64 — памяти жрут немерено, но работает быстро). Применяя его к тексту, можно видеть, что он выделяет зависимости окончаний и группы существительных по родам, прилагательных и глаголов. Что бы выделить первые зависимости слов, у меня не хватило оперативки — нужно переделывать под базу данных на диске.
Если есть где статьи по описываемой мной теме, или существуют развивающиеся проекты, скиньте пожалуйста ссылку.
Так же интересно было бы финансирование моей деятельности в этом направлении, что бы эта деятельность из области увлечения превратилась в основной род занятий и начала продвигаться быстрее. Если найдутся такие люди или организации — пишите в личные сообщения или на скайп указанный в профиле.
