Comments 13
Было бы здорово обзор имеющихся техник для решения похожей задачи. Кажется вам нужно смотреть в тер. вер. и статистику, заодно прочтирать про Колмогоровскую сложность.
Исходя из постановки задачи скорее стоит прочитать про цепи Маркова и алгоритм Витерби.
Про алгоритм не слышал. Спасибо. Почитаю. Что касается цепей Маркова, то направление исследования иное.
Интересует прежде всего иерархическое обучение с подкреплением. Для этой парадигмы нужно уметь маштабировать. Какое либо состояние в пространстве состояний с высокой однозначностью может, в свою очередь, быть тоже пространством состояний.
У Вас две неоднородные цепи Маркова которые вы пытаетесь проверить на корреляцию между собой.
Вместо того, чтобы думать как прикрутить какой-нить коэффициент спирмана для оценки корреляции в идеале с O(n) - например ограничив глубину шагов используемых для корреляции, (исходя из описания "в лоб" явно будет O(n^2))
И постараться исходя из области реального применения впихнуть их в одну цепь с количеством состояний существенно меньше чем n^2, чтобы сложность опять же к квадрату не подскочила вы сразу играться в ML? Даже использование Витерби в вашем случае это заход с козырей .
Так что соглашусь с предыдущим оратором, выбор того, что почитать стоит начинать с его списка.
Вы бы хоть привели словесное описание алгоритма вычисления этого коэфициента.
Вроде по постановке задачи оно должно считаться для какой-то последовательности. Но код приведен только для НКА, который используется для генерации последовательности.
Вот НКА и генерирует эти последовательности (состояние, действие) (следующее состояние, какое-то действие) ...
Вопрос в том, что не знаем где состояние и где действие. Одна последовательность может характеризовать смену состояний. Другая - последовательность действий.
Чтобы проверить - строим граф. Вычисляем коэффициент get_ku.
В некотором смысле это похоже как собрать картину по пазлам. Если ku близко к единице, то такой граф (как собранная картинка) близок к детерминированному и можно составлять маршруты в таком графе.
Эти графы с высокой однозначностью уже могут участвовать в двух типах соединений. Что позволяет строить сложно иерархические их структуры.
ЗЫ если попробовать посчитать ku скажем двух последовательностей ( угол поворота листочка и цвет машины ) , то этот коэффициент примет маленькой значение. Поскольку одно на другое не влияет
Ну вы можете описать, как ваш коэффициент вычисляется? В идеале — математическую формулу привести. С некоторыми объяснениями, откуда оно взялось, хотя бы эвристически (типа, вот эта сумма по неравнеству Чебышева всегда меньше 1, но если все элементы равны, то и сумма равна 1. Поэтому при константной, а значит полностью однозначной последовательности, коэффициент будет равен 1 и чем последовательность случайнее, тем меньше коэффициент).
Может, я, например, питон не знаю. Или даже если и знаю, но разбираться в вашем недокоментированном коде не очень приятно. Что за get_yfx? Что мерджит merge? fORx?!
Без этого статья странная: Вот какой-то код, он что-то, названное "коэффициентом однозначности", считает. Вот график. В этом конкретном примере вроде как смысл этот коэффициент несет.
Ну вы можете описать, как ваш коэффициент вычисляется?
Отнесем количество переходов, как если бы все переходы были однозначны, к всем случившимся.
Пусть имеется множество {a, b, c, d}. Некоторые из элементов могут быть состояниями, некоторые действиями.
Предположим, что действиями будут {a, b}, состояниями {c, d}. Пусть имеем: с|d=a(c), с|d=b(c), c=a(d), с|d=b(d).
Здесь "|" означает "либо". Так с|d=b(d) означает: из состояния d при действии b следует либо c, либо d.
Попробуем иначе интерпретировать. Предполагаем: действия {a, c}, состояния {b, d}. Пусть имеем: b=a(b), b|d=c(b), d=a(d), b=c(d).
Разница, если ее оценить количественно, в более однозначном поведении второй гипотезы. В первом случае коэффициент однозначности, взятый как отношение как если бы все переходы были бы однозначны к всем случившимся переходам, будет равен 4/7. Во втором случае он будет равен 4/5. Или, другими словами, мы имеем почти детерминированное пространство состояний.
Что мерджит merge? fORx?!
merge - объединят два графа в один. Это нужно, так как оригинальный граф видим видим лишь частично в каждом наблюдении. По каждому наблюдению строим граф. И объединяем с предыдущими наблюдениями.
fORx - у нас же 2 последовательности. Вот и проверяем пары: (действие, состояние), (состояние, действие)
Вообще, все вертится вокруг базовой формулы: Y=F(Х), где Y - это next_X
Вопрос в том, что не знаем где состояние и где действие.В какой реальной ситуации такое встречается?
#Пусть имеется 4 последовательности.
#Вторая изменяет первую. Четвертая изменяет третью.
#Четвертая к первой - получим неоднозначть (из 3 при действии -1)
1 3 2 3 1
+1 -1 +1 -2 +1
1 2 1 2 1
+1 -1 +1 -1 +1Если заменить каждый из этих элементов. Например, 1 на F, +1 на C, -2 на Q и т.д, то как понять что действует на что? Вот максимизация коэффициента однозначности и будет тем ориентиром, к которому нужно стремится.
Применяться может везде, где необходимо выявить законы этого мира.
Пусть в незнакомой комнате имеются 2 люстры и 2 выключателя. Как определить какой выключатель к какой люстре относится? Пусть Вы наблюдатель, а два других человека в случайном порядке меняют положение выключателей. А Вы регистрируете как положение выключателей, так и горят ли люстры. В итоге должны определить что на что действует. Типичная исследовательская задача.
два других человека в случайном порядке меняют положение выключателей. А Вы регистрируете как положение выключателей, так и горят ли люстры.В таком случае для наблюдателя понятие «действие» отсутствует. Вы наблюдаете смену состояний некого чёрного ящика и ищите корреляцию между его параметрами, доступными для наблюдения.
Действия возникают только в том случае, когда наблюдатель перестаёт быть наблюдателем и вмешивается в процесс смены состояний объекта, начинает им управлять. Не кто-то неизвестный переключает выключатели, а этот самый «наблюдатель». В вашем же случае «действие» — это чисто условность, корреляция между параметрами, где одно событие следует перед другим.
«Неоднозначность» же возникает из-за того, что у вас марковская цепь, у неё нет памяти, а вы её пытаетесь перевести в конечный автомат снятием этой «неоднозначности».
Действия возникают только в том случае, когда наблюдатель перестаёт быть наблюдателем. Не кто-то неизвестный переключает выключатели, а этот самый «наблюдатель».
Не вижу смысла логику «привязывать» к наблюдателю. Не о людях ведь речь....
«Неоднозначность» же возникает из-за того, что у вас марковская цепь, у неё нет памяти, а вы её пытаетесь перевести в конечный автомат снятием этой «неоднозначности».
Не имеет значения какие последовательности берутся: марковские или нет. Вот пример не марковской: A A B B A B B A A B B A B B A B B A B B A A B B A B B A B A B A. Но последовательность все же неоднозначна. Коэффициент однозначности здесь равен 2/4
Коэффициент однозначности