Автореферат (Разработка математических методов и комплекса программных средств имитационного тестирования знаний на основе семантических моделей), страница 3

При каждом получении свидетельства повторяем шаги 2 – 4 алгоритма.Рекуррентная формула (3) из алгоритма 1 соответствует формуле (2) изутверждения 1.8Далее строится рекуррентный алгоритм оценивания всех параметровбайесовской сети с булевыми случайными элементами, структурой которой являетсяориентированное дерево.Пусть проведен ряд наблюдений, в которых некоторые переменные сетипринимали значения 1 или 0; N X(1) и N X(0) — число наблюдений, в которыхпеременная X сети принимала значение 1 и 0, соответственно; xi(1) и xi(0) — числотех наблюдений, в которых переменная X принимала значение 1, из первых iнаблюдений, в которых переменная pa( X ) (родитель узла X ) принимала значение 1и 0, соответственно; ri — число тех наблюдений, в которых переменная R(корневой узел) принимала значение 1, из первых i наблюдений, в которыхполучено свидетельство о значении корневого узла.Оценки параметров сети по формуле аддитивного сглаживания будут иметьвид:r , i  0,, N R(1)  N R(0) ,(4) p R i  ii  2x (1)(1)(5) pX  j  jj  2 , j  0,, Npa(1)( X ) ,xk(0)  (0)(6) pX k  k  2 , k  0,, Npa(0() X ) ,где  — произвольный коэффициент сглаживания.Предлагаются рекуррентные формулы: pˆ  (i  1  2 )   ER i, i  1,..., N R(1)  N R(0) ,(7) pˆ R 0  0.5,  pˆ R i  R i1i  2 pˆ X(1)  j1 ( j  1  2 )   EX  j(1)(1)(8), j  1,..., N pa(1)( X ) , pˆ X 0  0.5,  pˆ X  j j  2pˆ X(0)  (k  1  2 )   E X k(0)(0)k 1(9), k  1,..., N pa(0() X ) , pˆ X 0  0.5,  pˆ X k k  2где  ER i равно значению переменной R в i -м наблюдении;  EX  j равно значению EX  j   pˆ X(1)  j 1 , если в j -м наблюдениине получено;  E X k равно значению переменной X впеременной X в j -м наблюдении илисвидетельства о значении Xk -м наблюдении или EX k   pˆ X(0) k 1 ,если в k -м наблюдении свидетельства означении X не получено.Далее доказывается утверждение 2 и предлагается алгоритм 2.Утверждение 2 (о рекуррентном оценивании параметров байесовской сети).Прилюбомчисленаблюдений pˆ R i   pR i , i  0,, N R(1)  N R(0) , pˆ    p  , j  0,, N(1)Xj(1)Xj(1)pa( X )и pˆ    p (0)Xk(0)Xk9, k  0,, N pa( 0)( X ) , т.е.

оценки порекуррентным формулам (7), (8) и (9) совпадают с соответствующими оценками (4),(5) и (6) по формуле аддитивного сглаживания.Алгоритм 2. Рекуррентное оценивание параметров байесовской сети с булевымислучайными элементами, структурой которой является ориентированное дерево.1. Для каждого из узлов сети устанавливаем счетчики свидетельств N X(1)  0и N X(0)  0 . Для корневого узла задаем начальное значение параметраpR  0.5 . Для каждого из остальных узлов задаем начальные значенияпараметров p X(1)  0.5 и p X(0)  0.5 .2.

При поступлении порции свидетельств о значениях некоторыхпеременных сети, каждой переменной X , в отношении которой полученосвидетельство о том, что она приняла значение 1 или 0, ставим всоответствие величину EX : 1 (или EX : 0 , соответственно).3. Если на шаге 2 задана величина ER для корневого узла, инкрементируемсчётчик свидетельств N R( ER ) : N R( ER )  1 и обновляем значение параметраpR по формуле:pR ( N R(1)  N R(0)  1  2 )  ER.(10)pR :N R(1)  N R(0)  24. Для каждого дочернего узла X рассмотренных на предыдущем шагеузлов, если на шаге 2 задана величина E X для узла X , инкрементируемсчётчик свидетельств N X( EX ) : N X( EX )  1 и, если на шаге 2 задана величинаEP для родительского узла P , обновляем значение параметра p X( EP ) поформуле:p X( EP ) ( N P( EP )  1  2 )  E X( EP ).(11)p X :N P( EP )  25.

Повторяем шаг 4, пока не обойдем рекурсивно все узлыориентированного дерева.6. Повторяем шаги 2–5 при каждом поступлении очередной порциисвидетельств о значениях переменных сети.Рекуррентные формулы (10) и (11) из алгоритма 2 соответствуют формулам(7), (8) и (9) из утверждения 2.Критерием окончания работы алгоритма 2 является стабилизация значенийоценок параметров или прекращение поступления свидетельств. Результатомработы алгоритма 2 является набор установленных значений оценок всехпараметров байесовской сети. Фактически, байесовская сеть обучается системеоценивания знаний конкретного преподавателя.Ставится задача тестирования знаний — построить оценки владения темами,обладания компетенциями, умения выполнять тестовые задания.

В предложенноймодели на основе байесовской сети в качестве таких оценок могут выступатьусловные вероятности для каждой из переменных T1 ,..., TN , C1 ,..., CM и Q1 ,..., QK приполученных значениях переменных S1,..., S L .10Рассматривается разработанный для случая байесовской сети, имеющейдревовидную структуру, с дискретными переменными, принимающими nвозможных значений, эффективный механизм вероятностного вывода, линейный повремени и памяти (Pearl, 1988). Этот алгоритм основан на том, что в каждый моментвремени каждый узел сети имеет всю информацию, необходимую для вычисленияусловной вероятности соответствующей переменной, а при получениисвидетельства о значении какого-либо узла этот узел отправляет векторныесообщения об этом изменении соседним узлам.

Далее эта информация передается поцепочке и в каждом узле пересчитываются условные вероятности.Предлагается модификация этого алгоритма для случая байесовской сетис булевыми случайными элементами, структурой которой является ориентированноедерево. Оказывается, что в этом случае все векторные сообщения являютсядвумерными, а часть из них можно заменить скалярами.Пусть X — узел сети, имеющий единственного родителя U и являющийсяродителем m других узлов Y1 ,..., Ym . Пусть получен набор E свидетельств означениях переменных сети и для каждого узла X сети заданы параметры p X(1) иp X(0) .Пусть каждый узел X сети передает двумерное векторное сообщение X(1)U X (u )   (0)  своему родителю U и скалярные сообщения  X Y j каждому из X U своих детей Y1 ,..., Ym , т.е.

каждый узел X сети получает сообщение  U  X от своего Y(1)j  X родителя U и сообщения  (0)  от каждого из своих детей Y1 ,..., Ym . Y  X  j Далее доказывается утверждение 3 и предлагается алгоритм 3.Утверждение 3 (о вероятностном выводе в байесовской сети с булевымислучайными элементами, структурой которой является ориентированное дерево).X(1) XУсловная вероятность для узла X равна P( X | E )  (1), гдеX  X  X(0) (1   X ) X(1)   Y(1) X j X   U  X p X(1)  (1   U  X ) p X(0) и  (0) , а отправляемые узлом X(0)XYXjjj X  Y(1) Xk  p   (1  p ) k jсообщения равны . и(1)(0)(1)p(1p)XYk  XXYk  X(1)X(1)X(1)X(0)X(0)X(0)X(1)X(0)Xk jk jАлгоритм 3.

Вероятностный вывод в байесовской сети с булевыми случайнымиэлементами, структурой которой является ориентированное дерево.Пусть сеть проинициализирована, т.е. заданы все параметры: pR длякорневого узла R , а также p X(1) и p X(0) для каждого узла X из остальных. Пусть E11— набор полученных свидетельств о значениях переменных сети.1. Каждому узлу X , в отношении которого получено свидетельство о том,что соответствующая переменная X приняла значение 1 или 0, ставим всоответствие величины  X(1)  1 и  X(0)  0(или X(1)  0 и  X(0)  1 ,соответственно). Каждому листу X ордерева, не получившемусвидетельство, ставим в соответствие величины  X(1)  1 и  X(0)  1 .2. Каждый узел X , для которого на предыдущем шаге получены величины X(1) и  X(0) , посылает своему родителю U сообщение: X(1)U  X(1) p X(1)  X(0) (1  p X(1) ) .(12) (0)(1) (0)(0)(0) p(1p)XXXX X U3. Для каждого узла X , который на предыдущем шаге получил сообщение, Y(1)j  X если он к этому моменту получил сообщения  (0)  от всех своих детей Y  X  j Y1 ,..., Ym , вычисляем величины: X(1)   Y(1)j  X j(13) (0).(0)Yj  X  XjЕсли на этом шаге не были вычислены величины R(1) и R(0) для корневогоузла, то возвращаемся к шагу 2.4.

Корневому узлу R ставим в соответствие величину  R  pR . Кроме того,вычисляем для него значение условной вероятности:P( R | E ) R(1) R.R(1) R  R(0) (1   R )(14)5. Каждый узел X , для которого на предыдущем шаге получена величина X , посылает каждому из своих детей Y1 ,..., Ym сообщения: X Y j X  Y(1) Xk jk X  Y(1) X  (1   X ) Y(0) Xk jkk j.(15)k6.

Для каждого узла X , который на предыдущем шаге получил сообщение U  X от своего родителя U , если в отношении X не полученосвидетельство, вычисляем величину: X   U  X p X(1)  (1   U  X ) p X(0) ,(16)а также вычисляем значение условной вероятности:P( X | E ) X(1) X.X(1) X  X(0) (1   X )(17)Если на этом шаге не были вычислены условные вероятности для всехлистьев ордерева, не получивших свидетельство, то возвращаемся к шагу 5.12Формулы (12), (13), (14), (15), (16) и (17) в алгоритме 3 выводятся в процесседоказательства утверждения 3.Результатом работы алгоритма 3 является набор значений условныхвероятностей P( X | E ) , вычисленных для каждого узла байесовской сети, неполучившего свидетельство. Дополнительные вероятности вычисляются из условиянормировки: P( X | E )  1  P( X | E) .В процессе тестирования в систему постепенно поступают свидетельства означениях наблюдаемых переменных (семантических элементов S1,..., S L ).Алгоритм 3 позволяет на каждом шаге тестирования обновлять условныевероятности в сети в соответствии с полученными данными и формироватьвероятностную картину, характеризующую скрытые переменные байесовской сети(умение решать задачи, обладание компетенциями и владение темами) длятестируемого студента.Следует отметить, что условные вероятности переменных, полученные впроцессе тестирования с использованием предложенной модели, нельзя трактоватьнепосредственно как вероятности владения студентом соответствующимисовокупностями знаний.