В этом посте я приведу очень простой пример предметной области и алгоритм анализатора экспериментов, указанного в схеме к прошлому посту. Вообще, лог экспериментов - это аналог последовательности команд на языке ассемблера. Поэтому в нём могут быть скрыты условные переходы и циклы за логикой примитивных операций. В данном посте я не рассматриваю варианты поиска циклов и условных переходов в логе экспериментов. Для упрощения понимания сути работы анализатора он будет искать одну единственную каноническую конструкцию - простую последовательность операций. Операция в данном случае означает действие ИИ на объект исследования, выполняемое в ходе эксперимента.
Предметная область
Существует единственный объект исследования, состояние которого описывается набором дискретных параметров. Каждый параметр представляет собой флаг, т.е. может принимать только значения 0 и 1. Для этого объекта допустимо несколько примитивных действий, каждое из которых определённым образом меняет состояние объекта. Изменение состояния объекта имеет внутреннюю логику и недоступно извне. Т.е. объект исследования является для нас "чёрным ящиком". Однако, каждое примитивное воздействие всегда оказывает однозначный простой эффект. Кроме того, существует несколько фиксированных последовательностей команд, которые оказывают на объект новые эффекты. Эти эффекты меняют параметры состояния объекта отлично от примитивных действий.
Над объектом исследования проводится большое количество экспериментов, каждый из которых состоит в применении случайного примитивного действия к объекту и записи в лог его нового состояния.
Цель и задача
Анализатор просматривает лог экспериментов и пытается обнаружить все последовательности команд и новые эффекты, которые они оказывают на объект. Полученные наборы действий являются новыми стратегиями поведения ИИ, что есть результат его обучения. Требуется определить все эти наборы действий.
Модель данных
A - это множество примитивных действий, допустимых для объекта исследования.
A = { a1, ..., ax }.
C - это эксперименты, т.е. последовательность наших действий, применяемых к объекту.
C = { c1, ..., cn }, где ci принадлежит множеству действий A.
S - состояние системы после каждого эксперимента. Каждое состояние объекта состоит из m флагов.
S = { s1, ..., sm }, где si может быть 0 или 1.
Если проанализировать последовательности C и S, то можно выявить удачные блоки, приводящие к новым эффектам на множестве S. E = { e1, ..., el } - это искомые последовательности действий, где ei принадлежит множеству команд A = { a1, ..., ax }.
Алгоритм анализа экспериментов
Для начала необходимо сопоставить каждому действию ci эффект, который оно оказывает на объект исследования. Эффект воздействия - это изменение переменных состояния из множества S. Для того чтобы собрать эту информацию введём хранилище эффектов воздействий и обозначим его множеством D.
D = { d1, ..., dx }, где di = { ds1, ..., dsn };
Каждый эффект - это изменение параметров состояния объекта, которое хранится во множестве S и меняется после каждого эксперимента. Обозначим изменение каждого параметра из множества S структурой ds:
dsi = { S[i][j-1], S[i][j] }.
Как видно из формулы, эта структура хранит два состояния параметра S[i] - до эксперимента под номером j и после. Здесь j - номер эксперимента, который лежит в интервале от 1 до n.
Для построения множества D можно использовать следующий простой алгоритм.
PHP:
j = 2
while (j<=n && LEN(D) < x)
{
c = C[j]
a = A[c]
if (D[a] == NULL)
{
d = {}
for (i=1; i<=m; i++)
{
ds = { S[i][j-1], S[i][j] }
d[i] = ds
}
D[a] = d
}
j++
}
font>
Этот алгоритм будет правильно работать при условии, что каждое примитивное воздействие всегда оказывает однозначный простой эффект. Это указано в описании предметной области. Если же эффект от примитивного воздействия будет разным, то потребуется учитывать также вероятности этих эффектов в дополнение к множеству D. В этом посте я ограничусь описанием самого простого случая.
Теперь можно анализировать весь лог экспериментов C, чтобы найти в нём последовательности действий приводящие к неожиданным эффектам. Для этого предлагается просматривать лог до появления неожиданного изменения состояния и когда оно будет замечено, сохранить несколько предыдущих экспериментов, привязав их к этому эффекту. В данном случае мы будем запоминать 10 предыдущих экспериментов в список T. Далее продолжаем просматривать лог C и при обнаружении уже запомненного эффекта добавляем ему в соответствие новые 10 предыдущих экспериментов. Делаем так до тех пор, пока для каждого эффекта не накопится достаточно количество появлений и соответствующих экспериментов. В данном случае мы ограничимся 3-мя появлениями каждого эффекта. Три эффекта будем считать уже закономерностью. Теперь для каждого эффекта сравниваем группы экспериментов и, если среди них есть одинаковые последовательности команд, добавляем эти команды в искомое множество E. В целом, псевдокод алгоритма построения множества E выглядит следующим образом.
PHP:
T = {} // список неожиданных эффектов
j = 1
while (j<=n) // анализируем эксперименты
{
c = C[j]
a = A[c]
d = {}
for (i=1; i<=m; i++) // формируем d
{
ds = { S[i][j-1], S[i][j] }
d[i] = ds
}
if (D[a] != d) // неожиданный эффект
{
f = d // запоминаем эффект в другой переменной
t = []
i = j
while (i>=2 && i>=j-10) // находим 10 предыдущих действий
{
c = C[i]
a = A[c]
d = {}
for (k=1; k<=m; k++) // формируем d
{
ds = { S[k][i-1], S[k][i] }
d[i] = ds
}
// запоминаем в список t действие a и его эффект d
t[LEN(t) + 1] = { a, d }
i--
}
// сохраняем 10 предыдущих действий для эффекта f
T[f][LEN(T[f]) + 1] = t
}
j++
}
// формируем множество E
for (f, Z) in T // f - ключ, Z - значение в коллекции T
{
if (LEN(Z) >= 3) // является ли это закономерностью?
{
e = [] // элемент искомого множества E
o = Z[1] // эталонный образец последовательности, приводящей к эффекту f
// ищем, где заканчивается одинаковая последовательность действий
for (j=2; j<=LEN(Z); j++)
{
t = Z[j]
i = LEN(t)
do
{
a = t[i].a // действие
d = t[i].d // изменение состояния
if (a == o[i].a && d == o[i].d)
{
if (e[LEN(e) + 1] == NULL)
e[LEN(e) + 1] = a
}
else
break
i++
}
while(i <= LEN(t))
}
E[f] = e // добавляем новую стратегию в множество E по ключу f
}
}
font>
Вот и всё, множество E построено. Оно содержит последовательности действий, которые приводят новым эффектам. Обратите внимание, что множество E представлено в псевдокоде ассоциативным массивом. В этом массиве каждому ключу f (сам эффект) сопоставлены последовательности действий из множества A, которые приводят к этому эффекту. Таким образом, элементы из множества E можно использовать в качестве новых, теперь уже составных, действий. Эти составные действия можно применять к объекту исследования чтобы добиться какого-либо эффекта f.
Прошу понять, что данный псевдокод может содержать мелкие логические ошибки и в целом я не делал такой реализации. Всё это лишь алгоритмические выкладки, которые являются основой для дальнейшего исследования и совершенствования ИИ. Это именно основа, база, потому что рассмотренная предметная область очень проста и не соответствует реальным задачам. Однако этот пример позволяет понять принцип работы анализатора экспериментов и генерации новых стратегий для ИИ.
Если Вы нашли логические ошибки в псевдокоде или у Вас есть другие ценные мысли по ИИ, прошу писать в комментарии. Спасибо.