Максимизация коэффициента однозначности. Маршрутизация на объектах с непрямым управлением и вложенной структурой08.05.2024 04:30

Трактовать изложенное в статье можно следующим образом:

1. На диаграммах состояний UML, как сами состояния, так и направленные ребра, могут быть выражены векторами.

2. Эти вектора именуются как в обучении с подкреплением RL: state, action.

3. Такие графы могут быть как гиперграфами, так и мультиграфами.

4. Графы, которые максимизированы по коэффициенту однозначности, являются объектами.

5. Такие объекты могут вступать в отношения управления и иерархии.

Наблюдаемый объект не всегда полностью виден. Обусловлено не только тем, что возможны перерывы в наблюдении, как 17-я или 40-я записи в данных таб. 1, но также присутствуют неразличимые значения отдельных признаков по всему периоду наблюдения. Возникает, разумеется, вопрос, что считать объектом. Им можно считать то, что предсказуемо. Просто на том основании, что такой подход дает возможность планировать, минимизируя ошибки. Необходимость такого подхода обоснована Эшби [с. 63–66, Введение в кибернетику]

Суть им изложенного в следующем:

1. Отказ от однозначности привел бы к невозможности предсказывать события.

2. Если модель неоднозначна, ее следует переопределить, рассмотрев другие переменные.

3. Иногда требуется однозначность самих вероятностей.

4. Мы и только мы определяем, что считать похожим на машину в кибернетическом смысле.

Если данные ниже дать обработать алгоритму, описанному в [1], то он найдет два таких объекта: (('t2',), ('f2',)) и (('f2',), ('f1',)).

Таблица 1. Данные

Ниже представлены соответствующие графы. Выражены словарем, где ключом является текущее состояние, а значением — список [следующие состояния, действие].

sa = ((('t2',), ('f2',)), [(1.0, 8)])
('53.0',) : [[[('54.0',)], ('44.0',)], [[('52.0',)], ('41.0',)]]
('54.0',) : [[[('54.0',)], ('45.0',)], [[('53.0',)], ('44.0',)], [[('52.0',)], ('41.0',)]]
('52.0',) : [[[('52.0',)], ('45.0',)], [[('53.0',)], ('44.0',)], [[('52.0',)], ('41.0',)]]

sa =  ((('f2',), ('f1',)), [(1.0, 9)])
('45.0',) : [[[('44.0',)], ('36.0',)], [[('45.0',)], ('34.0',)], [[('45.0',)], ('35.0',)]]
('44.0',) : [[[('45.0',)], ('35.0',)], [[('44.0',)], ('34.0',)], [[('41.0',)], ('36.0',)]]
('41.0',) : [[[('45.0',)], ('34.0',)], [[('44.0',)], ('36.0',)], [[('41.0',)], ('35.0',)]]

Состояния ('52',), ('54',), ('53',) объекта (('t2',), ('f2',)) изменяются в зависимости от выбранного действия ('45',), ('44',), ('41',). При этом коэффициент однозначности ku равен единице, а количество переходов — восемь. Состояния ('45',), ('44',), ('41',) объекта (('f2',), ('f1',)) изменяются в зависимости от выбранного действия ('36',), ('35',), ('34',). Коэффициент однозначности тоже равен единице, но количество переходов — девять. Что касается (('t0',), ('f0',)), то нахождение такого объекта сложнее

sa = ((('t0',), ('f0',)), [(1.0, 8)])
('14.0',) : [[[('15.0',)], ('32.0',)], [[('15.0',)], ('31.0',)]]
('t2',) : [[[('f2',)], ('32.0',)], [[('14.0',)], ('31.0',)]]
('f2',) : [[[('14.0',)], ('32.0',)], [[('t2',)], ('31.0',)]]
('15.0',) : [[[('14.0',)], ('32.0',)], [[('t2',)], ('31.0',)]]

В основной части данной статьи будет показано, как такой объект может быть найден. Сложность и новизна поиска в том, что объекты (('t2',), ('f2',)) и (('f2',), ('f1',)) вложены в (('t0',), ('f0',)). Вопросы маршрутизации и непрямого управления по таким объектам также будут рассмотрены.

Расчет коэффициента однозначности ku, как меры предсказуемости, приведен ниже.

#Связь понятий "свобода перехода"
#https://www.youtube.com/watch?v=RU2T0OFJJB4
#и "коэффициента однозначности"

g = {("how",): [[[("to",), ("do",), ("many",), ("long",), ("are",)], 
         ("action",)]], 
    ("many",): [[[("people",), ("times",), ("countries",), ("states",)], 
         ("action",)]],
    ("are",): [[[("you",)], 
         ("action",)]]}

import math

def get_ku(g):
    n=0; u=0; h=[] 

    for x in g:
        for y in g[x]:
            if y[0] != []:
                u += len(y[0]) -1
                h.append(round(math.log(len(y[0]), 2), 4))
                print("Свобода перехода: ", round(2**h[-1], 2))
                n +=1
    if n != 0:
        ku = round(n/(u+n),3 )
        print("h =", h, "#биты переходов с неопределенностью")
        print("n =", n, "#оценка познанной сложности (двойки: )")
        print("u+n =", u+n, "#количество переходов (тройки: )") 
        print("ku = n/(u+n) =", ku)
        print("ku == n/(sum([2**b for b in h]) - len(h) + n) is", \
              round(ku, 3) == \
              round(n/(sum([2**b for b in h]) - len(h) + n), 3)  ) 
        print()
        return (n, u, h)

i = 1
for g in [g]:
        print("\n     i =", i)
        r = get_ku(g)
        i +=1

''' Вывод:
     i = 1
Свобода перехода:  5.0
Свобода перехода:  4.0
Свобода перехода: 1
h = [2.3219, 2.0, 0] #биты переходов с неопределенностью
n = 3 #оценка познанной сложности (двойки: )
u+n = 10 #количество переходов (тройки: )
ku = n/(u+n) = 0.3
ku == n/(sum([2**b for b in h]) - len(h) + n) is True
'''

Основная часть

Первоначально ku=0.917 для (('t0',), ('f0',)) потому, что из состояния ('52',) при действии ('32',) следует либо состояние ('45',), либо состояние ('44',), что неоднозначно.

sa = (('t0',), ('f0',))  [(0.917, 12)] kс_per =  0
('14.0',) : [[[('15.0',)], ('32.0',)], [[('15.0',)], ('31.0',)]]
('54.0',) : [[[('44.0',)], ('32.0',)]]
('45.0',) : [[[('14.0',)], ('32.0',)]]
('52.0',) : [[[('45.0',), ('44.0',)], ('32.0',)], [[('14.0',)], ('31.0',)]]
('44.0',) : [[[('14.0',)], ('32.0',)], [[('54.0',)], ('31.0',)]]
('41.0',) : [[[('52.0',)], ('31.0',)]]
('15.0',) : [[[('14.0',)], ('32.0',)], [[('52.0',)], ('31.0',)]]

Поскольку конкурирующих гипотез (в отношении предсказуемости по состояниям) может быть много, а предпочтение при прочих равных следует отдавать гипотезам, которые не только максимальны по ku, но и минимальны по длине (по длине графа), введена переменная kc_per (процент по Колмогоровой сложности). В результате более длинные гипотезы с тем же ku, при наличии более короткой, отбрасываются.

В результате, сначала находятся (('t2',), ('f2',)), (('f2',), ('f1',)) и лишь затем (('t0',), ('f0',)).

В. Турчин в главе иерархические структуры [Феномен науки] пишет, что под понятием в кибернетическом смысле следует понимать множество ситуаций. Перефразируя можно сказать, что этим понятием-переменной и будет множество состояний объекта, сменяемых под влиянием действия.

В этом смысле: поскольку (('t2',), ('f2',)) однозначно, в (('t0',), ('f0',)) вместо состояний ('52',), ('54',), ('53',) подставляется ('t2',). Аналогично поступаем по отношению (('f2',), ('f1',)). Вместо ('41',), ('44',), ('45',) подставляется ('f2',) в (('t0',), ('f0',)). В результате не только ku увеличивается с ku=0.917 до ku=1, но и размер графа по количеству переходов уменьшается с 12 до 8.

sa = (('t0',), ('f0',))  [(1.0, 8)] kс_per =  100.0
('15.0',) : [[[('14.0',)], ('32.0',)], [[('t2',)], ('31.0',)]]
('t2',) : [[[('f2',)], ('32.0',)], [[('14.0',)], ('31.0',)]]
('14.0',) : [[[('15.0',)], ('32.0',)], [[('15.0',)], ('31.0',)]]
('f2',) : [[[('14.0',)], ('32.0',)], [[('t2',)], ('31.0',)]]

Итак, по выявленным объектам:

1. Все три имеют ku=1, т.е. 100\% однозначны.

2. (('f2',), ('f1',)) управляет (('t2',), ('f2',)).

3. Оба объекта вложены в (('t0',), ('f0',)).

4. Можно прокладывать маршруты

Пусть требуется проложить маршрут в (('t0',), ('f0',)) от состояния ('15',) к состоянию ('54',). И есть права на изменение действий ('f0',), ('f1',).

Если использовать, например, обход в глубину для (('t0',), ('f0',)), то состояние ('54',) там не окажется. Объясняется тем, что объект (('t2',), ('f2',)) находится в состоянии ('52',). Это видно по последней строчке из фрейма данных.

Изменять же состояния объекта (('t2',), ('f2',)) может только объект (('f2',), ('f1',)) в силу того, что ('f2',) является одновременно как действием объекта (('t2',), ('f2',)), так и состоянием объекта (('f2',), ('f1',)).

Учитывая вышесказанное, псевдокод по маршрутизации будет выглядеть следующим образом:

1. Определяем принадлежность целевого состояния, перебирая вложенные объекты. Для примера с данными — это (('t2',), ('f2',)).

2. Прокладываем оптимальный маршрут от текущего состояния ('52',) в (('t2',), ('f2',)) к целевому состоянию ('54',). В программе используется алгоритм обучения с подкреплением с той лишь разностью, что на этапе разведки берется не случайное направление, а выбор с памятью и, следовательно, берется направление, которое было исследовано менее всего. Результатом будет [('52',), ('53',) ('54',)].

3. Зная маршрут в (('t2',), ('f2',)), вычисляются необходимые действия. Им соответствует последовательность [('44',), ('44',)].

4. Поскольку (('t2',), ('f2',)) управляется (('f2',), ('f1',)), то повторяется тот же алгоритм из пункта 2 для объекта (('f2',), ('f1',)) с текущим состоянием ('41',).

5. Далее, т.к. (('f2',), ('f1',)) вложен в (('t0',), ('f0',)), то прокладывается маршрут в (('t0',), ('f0',)) от ('15',) к ('f2',).

6. Полный маршрут для изменения состояния задан. И как только текущим состоянием в (('t2',), ('f2',)) будет выбрано ('54',), можно уже будет прокладывать маршрут от ('15',) к ('54',) непосредственно в (('t0',), ('f0',)).

find_target
((('t0',), ('f0',)), [('15.0',), ('t2',), ('f2',)], [('31.0',), ('32.0',)])
((('f2',), ('f1',)), [('41.0',), ('44.0',), ('44.0',)], [('36.0',), ('34.0',)])
((('t2',), ('f2',)), [('52.0',), ('53.0',), ('54.0',)], [('44.0',), ('44.0',)])

Пример выше — пример учебный. На реальных данных основной проблемой будет синхронизация действий между объектами. Решение облегчается, если объекты имеют устойчивые состояния [Введение в кибернетику, c. 110]. Таковым для объекта (('t2',), ('f2',)) является равновесное состояние ('52',) при действии ('41',), например.

В заключение стоить отметить: не обязательно знать все возможные состояния, действия объектов, чтобы их идентифицировать. Достаточно, чтобы последующие наблюдения не увеличивали неопределенность по ним. В противном случае будем наблюдать не многообразие объектов, а только одно — хаос. Как следствие, чтобы идентифицировать сложно составленный объект, достаточно отследить несколько переходов сложно составленного, где его состояния определятся несколькими (не всеми) переходами уже вложенных объектов. Так образуются короткие пути в принятии решении по различным слоям.

Выводы

В машинном обучении существует направление обучения без учителя. Здесь этим неявным учителем является то, что сопротивляется энтропии входного потока данных, максимизируя коэффициент однозначности. Выявленные при этом объекты (подмножества признаков с высокой предсказуемостью) позволяют осуществлять планирование. Расчет маршрутов по таким объектам, включая вложенные, может проводиться средствами обучения с подкреплением. Или более общим взглядом: механизмом самосборки с усложнением является поиск новизны с высокой предсказуемостью из существующего разнообразия/

PS [1] Статья является продолжением статьи: Максимизация коэффициента однозначности для объектов, состоящих из множества признаков. //Вестник ДонНУ. Серия Г: Технические науки. — 2022. №4

© Habrahabr.ru