Educational Technology & Society 4(2) 2001
ISSN 1436-4522
pp. 205-210

Дискретные математические модели в исследовании процессов автоматизированного обучения

А.В. Соловов
научный руководитель ЦНИТ СГАУ
действительный член Российской академии информатизации образования
solovov@ssau.ru

А.А. Меньшикова
СГАУ
nastya@webmercs.com

АННОТАЦИЯ
Предлагается моделировать процессы автоматизированного обучения с помощью взвешенных ориентированных графов. Для реализации этого подхода построены вычислительные алгоритмы и разработаны компьютерные программы. Приведены примеры простейших моделей автоматизированного обучения и некоторые результаты их исследования. Разработанные алгоритмы и программы могут быть использованы для исследования, проектирования и интеллектуализации автоматизированных обучающих систем и как средства педагогического тренинга при подготовке и переподготовке преподавательских кадров в сфере информационных технологий обучения.

Ключевые слова
Моделирование, взвешенные ориентированные графы, автоматизированное обучение, интеллектуализация обучающих систем, педагогический тренинг.

 

Предварительные замечания

Обычная схема функционирования автоматизированных обучающих систем (АОС) включает последовательность шагов, каждый из которых направлен на усвоение учащимися определенной порции учебного материала. Каждый шаг содержит три основных функциональных компонента: предъявление порции теоретической информации, подлежащей усвоению; выполнение упражнений для осмысления и закрепления теории; оказание помощи учащемуся при выполнении упражнений.
Порядок работы учащихся в условиях автоматизированного обучения определяется либо жестким сценарием, заданным разработчиком АОС, либо выбирается каждым учащимся из набора типовых сценарных схем, либо соответствует определенному адаптивному алгоритму. В последнем случае говорят об интеллектуализации АОС, которая предполагает адаптацию к индивидуальным особенностям учащихся и выбор оптимальных параметров учебного материала - последовательности предъявления и объемов порций учебной информации, количества и типа упражнений, видов помощи и т.п. Оптимизация этих параметров должна приводить либо к минимизации времени обучения при фиксированном уровне обученности, либо к максимизации уровня обученности при фиксированном времени обучения.
Интеллектуализация АОС опирается на модели предметной области, обучаемого и процесса обучения [Холдинг Д., Голдстейн Н., Эбертс Р., 1991]. Исследования в сфере моделирования автоматизированного обучения (АО) пока еще не вышли из стадии эксперимента. Не останавливаясь на их обзоре, сошлемся на работу [Растригин Л.А., Эренштейн М.Х., 1988], в которой приведено краткое описание многих разработок.
В данной работе рассматривается новый подход к моделированию процессов АО с помощью взвешенных ориентированных графов (орграфов), уже нашедших применение в исследованиях социальных, биологических и экологических систем [Робертс Ф.С., 1986].

Взвешенные орграфы как модели процессов АО

Рассмотрим пример простейшей модели функционирования АОС (рис.1). В этом примере вершина графа В - это количество вопросов или упражнений, которые получает учащийся в диалоге с АОС для усвоения какой-либо порции учебной информации.

Рис.1. Простейшая графовая модель функционирования АОС и ее матрица смежности.

Вершина УО - это уровень обученности. Его обычно вычисляют как УО = ПО/В, где ПО - количество правильных ответов-решений. Очевидно, что УО О [0,1].
Вершина П - это уровень помощи, оказываемой учащемуся в ходе выполнения упражнений. Это может быть подсказка, намек, теоретическая информация или полный ответ на вопрос (полное описание процесса решения упражнения). В зависимости от степени полноты помощи величину П удобно представлять в интервале [0,1]. Здесь 0 - это отсутствие помощи; 1 - полное решение упражнения.
Ребра данного графа, кроме ориентации, характеризуются числовыми параметрами дуг хk (к = 1,2,..,6). В дальнейшем будем говорить о векторе параметров орграфа (для данного примера Х = (х1, х2, ...х6)).
Суть параметров хk можно пояснить на примере так называемого знакового ориентированного графа (рис. 2). Дуга, связывающая вершину В с вершиной УО, имеет знак +. Это означает, что увеличение количества вопросов-упражнений ведет к увеличению уровня обученности, а уменьшение В - к уменьшению УО. Дуга, связывающая УО с В имеет знак -. Это означает, что увеличение УО ведет к уменьшению В, а уменьшение УО - к увеличению В. Знаковый граф является частным случаем взвешенного ориентированного графа, когда параметры хk целочисленны и принимают значения +1 или -1, что отображается в матрице смежности.

Рис.2. Пример знакового орграфа и его матрицы смежности.

Таким образом, на начальном этапе построения модели эксперт или группа экспертов могут установить, хотя бы на качественном уровне, связи между различными характеристиками исследуемого процесса.
Более сложная модель функционирования АОС показана на рис. 3. В нее включены такие дополнительные факторы (вершины), как объем изучаемой порции учебного материала (ОМ), сложность материала (СМ), уровень способностей учащихся (УС). Их величины, характеризующие исходные показатели моделируемого процесса, также можно нормировать к интервалу [0,1]. В данной модели они оказывают влияние лишь на вершины В, УО и П, но обратных связей от них не имеют. Влияние друг на друга вершины ОМ, СМ, УС также не оказывают. Простейший анализ позволяет предсказать знаки ребер х7, х8 ...х15: х7+, х8+, х9-, х10-, х11-, х12+, х13+, х14+, х15-.

Рис. 3. Пример более сложной модели.

Импульсный процесс

Для более глубокого анализа моделей АО в виде взвешенных орграфов необходимо построить алгоритм влияния изменений значения одной вершины на величины других вершин. В основу этого алгоритма положим идею импульсного процесса, предложенную в [Робертс Ф.С., 1986]. Суть ее заключается в том, что в некоторую вершину анализируемого графа вносится внешнее возмущение (увеличивается или уменьшается ее величина). Например, в вершину В (см. рис. 1-3) добавляется некоторое количество упражнений. Далее, рассматривается распространение этого начального импульса и определяются значения вершин УО и П.
Рассмотрим орграф, вершины которого представлены совокупностью u1, u2,...un. Предположим, что каждая вершина ui в ходе импульсного процесса принимает значение vi(t) в дискретные моменты времени t = 0,1,2,... Будем считать, что значение vi(t+1) определяется значением vi(t) и информацией о том увеличили или уменьшили свои значения другие вершины uj, смежные с ui, в момент времени t. Для определения значений вершин будем использовать следующую формулу:
      где w(uj, ui) - вес дуги из вершины uj в вершину ui (w(uj, ui) = 0, если дуга (uj, ui) отсутствует);
      pj(t) - изменение в вершине uj в момент времени t.
      В соответствии с этой формулой, если имеется дуга из uj в ui с весом w и значение вершины uj возрастает в момент времени t на некое число z, то значение вершины ui в момент времени t+1 возрастает на величину z*w.
      Будем различать понятие исходного vi(исх.) и начального vi(0) значений в каждой вершине ui.
      vi(0) = vi(исх.) + pi(0),
      где pi(0) - начальный импульс (изменение в момент времени t = 0) вершины ui.
      Введем векторные обозначения:
      V(исх.) = (v1(исх.), v2(исх.),... vn(исх.)) - вектор исходных значений вершин;
      P(0) = (p1(0), p2(0),... pn(0)) - вектор начальных импульсов;
      V(t) = (v1(t), v2(t),... vn(t)) - вектор значений вершин в момент времени t.
      С учетом этих обозначений алгоритм развития импульсного процесса можно представить следующей матричной формулой:
      V(t) = V(исх) + (I + A + A2 + ... + At)TP(0),
      где I - единичная матрица размером n*n;
      A - матрица смежности орграфа размером n*n;
      T - означает транспонирование, а t - степень.

Устойчивость импульсного процесса

Импульсный процесс, реализующий описанный выше алгоритм, может быть устойчивым и неустойчивым. В неустойчивых импульсных процессах возмущение, вносимое в одну из вершин, приводит либо к возрастающим колебаниям величин вершин орграфа, либо к неограниченному увеличению (или уменьшению) этих величин. Устойчивый импульсный процесс характеризуется асимптотическим приближением значений вершин к некоторым фиксированным величинам. При этом сходимость может сильно различаться. Все эти различия определяются параметрами вектора Х - знаками и числовыми значениями дуг орграфа.
В качестве примера на рис. 4 показаны графики развития импульсного процесса относительно вершин УО и П в орграфе (см. рис. 1) с параметрами X= (0.25, -1, 0.3, 0.1, -1, 1), V(исх) = (0, 0, 1), P(0) = (5, 0, 0).

Рис. 4. Графики неустойчивого импульсного процесса .

Исследования параметров (весов дуг) орграфов, представляющих собой модели процессов АО (см. примеры на рис. 1, 3), показали, что подобрать эти параметры так, чтобы орграф был импульсно устойчив и имел хорошую сходимость, чрезвычайно затруднительно даже опытному эксперту.
В работе [Робертс Ф.С., 1986] было установлено и строго доказано, что импульсный процесс в орграфе будет устойчивым, если каждое собственное значение матрицы смежности орграфа по абсолютной величине не превосходит единицу. Поэтому можно применить машинную оптимизацию параметров дуг орграфа.

Формулировка задачи оптимизации

Вектор проектных переменных - это вектор параметров орграфа Х = (х1, х2, ..., хk, ..., хm). На вес каждой дуги графа наложим ограничения хk О [ck, dk]. Структуру графа будем задавать матрицей смежности А размером (n*n). Кроме варьируемых весов хk в матрице могут присутствовать и фиксированные веса дуг.
Собственные значения матрицы А представим в виде вектора l = (l1, l2, …, li, …, ln) ,
где li = ai +bii, т.е. li может быть действительным или комплексным числом. Абсолютное значение l'i вычислятся как корень квадратный из суммы квадратов ai и bi.
Функция цели f(x) = max (l'1, l'2, …, l'i, …, l'n) .
С учетом введенных обозначений сформулируем задачу оптимизации - минимизировать f(x) при ограничениях хk О [ck, dk].

Алгоритм оптимизации

Для компьютерной реализации выбран метод Монте-Карло с улучшением, суть которого - последовательный анализ случайно выбранных точек в области допустимых проектных переменных. Улучшение сводится к разделению поиска на этапы с постепенным уменьшением области случайного поиска. Поэтапная реализация метода Монте-Карло существенно уменьшает вычислительные затраты, но превращает алгоритм статистических испытаний из метода глобального поиска в метод локальной оптимизации. Компьютерная программа оптимизации, разработанная совместно с И.Н. Спасеновым, управляется пользователем: ряд ее параметров (величина ребра гиперкуба поиска, исходный вектор Х, ограничения на параметры хk, количество случайных проб на этапе) назначаются в диалоге и могут меняться пользователем в процессе оптимизации. Каждая случайная проба требует вычисления собственных значений матрицы смежности А, для чего выбран приближенный алгоритм Якоби с понижением нормы для действительных матриц [Уилкинсон, Райнш, 1976].
Эффективность компьютерной реализации алгоритма характеризует следующие данные: поиск оптимальных параметров для орграфа с размером вектора Х m=15 и размером матрицы А n=6 (см. рис. 3) требует примерно 10 минут работы компьютера Pentium 233. При этом количество случайных проб в ходе поиска составляет 7-8 тысяч.

Результаты исследований

В ходе проверки работоспособности и достоверности разработанных алгоритмов и программ были проведены вычислительные эксперименты на моделях, показанных на рис. 1-3. Они показали, что функция цели f(x) является многоэкстремальной, обладает большим количеством локальных минимумов. Попадание в тот или иной локальный минимум определяется исходными значениями параметров вектора Х и ограничениями на эти параметры, т.е. роль эксперта-пользователя, назначающего эти величины, по-прежнему весьма существенна. В качестве примера на рис.5 показаны графики развития импульсного процесса в орграфе (см. рис. 1) с V(исх) = (0, 0, 1), P(0) = (5, 0, 0) и вектором параметров в одном из локальных оптимумов Х = (0.2, -0.5, -0.1, -0.1, -0.5, -0.2).

Рис. 5. Сходимость импульсного процесса для орграфа с оптимальными параметрами.

Сферы применения

Предлагаемый подход, реализующие его алгоритмы и компьютерные программы нуждаются в дальнейшем исследовании. Сделаны лишь первые шаги. Но и они позволяют наметить ряд направлений для применения результатов данной работы.
Предлагаемые здесь модели могут рассматриваться как прескриптивные и дескриптивные. Прескриптивные модели описывают, каким должен быть процесс АО. Они могут быть полезны при разработке АОС. Исследование таких моделей, экспертный анализ и оптимизация их параметров позволяют более обоснованно подходить к проектированию сценариев учебной работы, планированию различных видов помощи, формулировке требований к структуре учебного материала, определению количества и типов упражнений для его усвоения.
Дескриптивные модели описывают уже существующие процессы АО и могут использоваться, например, для анализа их эффективности.
Графовые модели процессов АО могут встраиваться непосредственно в АОС и использоваться как средства интеллектуального управления. Так в модели, показанной на рис.3, величины вершин ОМ, СМ можно задавать как характеристики конкретной порции учебного материала, а величины УС и исходное значение УО определять на предварительном тестировании каждого учащегося. Исходная величина П - это возможный максимум помощи. Все эти величины, как уже отмечалось ранее, нормируются в пределах [0, 1]. Задав все эти данные, можно определить минимально необходимое количество упражнений для достижения требуемого уровня обученности по каждой порции учебной информации, спрогнозировать время для освоения всего объема учебного материала каждым учащимся.
Важно также подчеркнуть, что процесс построения моделей АО - определение наиболее значимых факторов (вершин орграфа и связей между ними), выбор исходных параметров модели и ограничений на их величины, исследование устойчивости и оптимизация параметров - вся эта деятельность не только требует высокой дидактической квалификации, но и способствует ее интенсивному росту. Следовательно, разработанные алгоритмы и программы могут использоваться не только как средства исследования, проектирования и управления АОС, но и как средства своеобразного педагогического тренинга при подготовке и переподготовке преподавательских кадров в сфере информационных технологий обучения.

Литература

[Растригин Л.А., Эренштейн М.Х., 1988]. Растригин Л.А., Эренштейн М.Х. Адаптивное обучение с моделью обучаемого. - Рига: Зинатне, 1988. - 160 с.
[Робертс Ф.С., 1986]. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам: Пер. с англ. - М.: Наука. Гл. ред. физ.-мат. лит., 1986. - 496 с.
[Уилкинсон, Райнш, 1976]. Уилкинсон, Райнш Справочник алгоритмов и программ на языке Алгол. Линейная алгебра: Пер. с англ. - М.: Машиностроение, 1976. - 590 с.
[Холдинг Д., Голдстейн Н., Эбертс Р., 1991]. Человеческий фактор. В 6 т. Т. 3. Моделирование деятельности, профессиональное обучение и отбор операторов: Пер. с англ./ Холдинг Д., Голдстейн Н., Эбертс Р. и др. (Часть 2. Профессиональное обучение и отбор операторов). - М.: Мир, 1991. - 302 с.