Назад

ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ В ИССЛЕДОВАНИИ ПРОЦЕССОВ АВТОМАТИЗИРОВАННОГО ОБУЧЕНИЯ

А.В. Соловов, А.А. Меньшикова

Самарский государственный аэрокосмический университет

(Статья опубликована в журнале "Информационные технологии", 2001, № 12 - с.32-36 Educational Technology & Society 4(2) 2001, ISSN 1436-4522, pp. 205-210 (http://ifets.ieee.org/russian/depository/v4_i2/html/3.html))

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

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

DISCRETE MATHEMATICAL MODELS IN RESEARCH OF AUTOMATED TUTORING PROCESSES
A.V. Solovov, A.A. Menschikova (Samara state aerospace university)

The summary. It is offered to simulate processes of automated tutoring with the help of weighted digraphs. For realization of this approach the computing algorithms are constructed and the computer programs are developed. The examples of the elementary models of automated tutoring and some outcomes of their research are indicated. The developed algorithms and programs can be used for a research, designing and intellectualization of automated learning systems and as means of a pedagogical training on information technologies of tutoring.

Key word. Simulation, weighted digraphs, automated tutoring, intellectualization of learning systems, pedagogical training.

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

Взвешенные орграфы как модели процессов АО. Рассмотрим пример простейшей модели функционирования АОС (рис. 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. Пример более сложной модели

Импульсный процесс. Для более глубокого анализа моделей АО в виде взвешенных орграфов необходимо построить алгоритм влияния изменений значения одной вершины на величины других вершин. В основу этого алгоритма положим идею импульсного процесса, предложенную в [3]. Суть ее заключается в том, что в некоторую вершину анализируемого графа вносится внешнее возмущение (увеличивается или уменьшается ее величина). Например, в вершину В (см. рис. 1-3) добавляется некоторое количество упражнений. Далее рассматривается распространение этого начального импульса и определяются значения вершин УО и П.
Рассмотрим орграф, вершины которого представлены совокупностью u1,u2,...,un. Предположим, что каждая вершина ui в ходе импульсного процесса принимает значение vi(t) в дискретные моменты времени t = 0,1,2,.... Будем считать, что значение vi(t+1) определяется значением vi(t) и информацией о том, увеличили или уменьшили свои значения другие вершины uj, смежные с ui, в момент времени t. Для определения значений вершин будем использовать следующую формулу:
vi(t+1) = vi(t) + Sx(ui, ui) pj(t),
где x(uj, ui) - вес дуги из вершины uj в вершину uj (x(uj, ui) = 0, если дуга (uj, ui) отсутствует);
pj(t) - изменение в вершине uj в момент времени t.

Суммирование осуществляется по j (от 1 до n). В соответствии с этой формулой, если имеется дуга из uj в ui с весом x и значение вершины uj возрастает в момент времени t на некое число z, то значение вершины ui в момент времени t+1 возрастает на величину z*x.
Будем различать понятие исходного 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), (1)
где I - единичная матрица размером n*n;
A - матрица смежности орграфа размером n*n;
T - означает транспонирование, а t - степень.

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


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

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

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

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

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


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

Интерпретация этих результатов достаточно проста: в соответствии с данной моделью выполнение 5 упражнений ведет к увеличению уровня обученности от 0 до 1,2 и уменьшению требуемой помощи от 1 до 0. Причем достигнутый уровень обученности на левом графике УО>1, что противоречит физическому смыслу (УО Î [0,1]). Это означает, что выполнение пяти упражнений избыточно для достижения предельного уровня обученности. Если же, например, выполняются 3 упражнения, что соответствует вектору внешнего возмущения P(0)=(3,0,0), то для данной модели графики импульсного процесса выйдут на уровень УО=0,7 и П=0,4.

Методика построения моделей. Рассмотренные выше примеры моделей (см. рис. 1-3) конечно же не охватывают всего многообразия сценарных схем АОС. Основное назначение этих примеров - иллюстрация предлагаемого подхода к моделированию процессов АО. Для построения моделей различных сценариев АО можно рекомендовать следующую методику.
1. Определение наиболее значимых факторов моделируемого сценария, которые в модели будут вершинами орграфа.
2. Выявление взаимных связей между этими факторами с отображением их в виде ориентированных ребер (дуг) орграфа.
3. Назначение численных диапазонов весов дуг орграфа на основе эвристических соображений о степени взаимного влияния факторов АО друг на друга.
4. Оптимизация величин весов дуг построенного орграфа для достижения устойчивости и хорошей сходимости импульсного процесса (1).
5. Проверка достоверности модели в ходе педагогических экспериментов на конкретной АОС.
6. Корректировка модели (пп. 1-4) по результатам педагогических экспериментов.

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

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

Сведения об авторах
1. Соловов Александр Васильевич - научный руководитель ЦНИТ СГАУ, доцент, кандидат технических наук, действительный член Российской академии информатизации образования; телефон (846-2) 34-72-78/факс, 67-44-40; адрес 443100, Самара, Первомайская 27-А, кв. 92.
2. Меньшикова Анастасия Александровна - аспирант СГАУ; e-mail: nastyam@mail.ru