Тел.: (812) 643-77-67 | Mail: fit.herzen.conf@gmail.com

Поиск по сайту

Григорьев А. П.,
Храброва А. Н.,
Егоров В. С.

ГУАП, г. Санкт-Петербург

Моделирование процесса обучения с использованием теории автоматов


В статье предлагается рассмотреть теорию автоматов, как эффективный инструмент при моделировании процедуры контроля степени «обученности».

Grigoryev A. P.,
Khabrova A. N.,
Egorov V. S.

SUAI, St. Petersburg, Russia

Modeling the learning process using the theory of automata

The article proposes to consider the theory of automata as an effective tool in modeling the procedure for controlling the degree of «training».

Доказано, что при решении сложной задачи обучаемый ведет себя как вероятностный автомат (ВА) [1], осуществляющий ту или иную последовательность операций из некоторого множества O = {01, 02, ..., 0N}. Пусть решение всегда начинается с операции 1; последовательность 1 → 2 → 3 → N является правильной. Вероятность выбора операции 2 после 1 обозначим p1, выбора (i+1)-ой операции после i-ой – pi. Все операции ВА совершает безошибочно; если же он допускает ошибку, значит, выполняет какую-то другую операцию. Вероятность решения задачи с первой попытки равна произведению p1p2p3…pN. Если алгоритм решения известен, то pi = 1, и ВА ведет себя как детерминированный автомат, достигая результата за минимальное число шагов. В начале обучения вероятности pi правильного выполнения (i+1)-ой операции после i-ой операции малы и равны 0,1. Обучаемый приступает к решению s-ой задачи. При правильном выборе первой операции, он переходит ко второй и т. д. На каждый шаг затрачивается одинаковое время Δt. Допустим, он ошибся и продолжает двигаться по неправильному пути. Автомат совершает заданное количество шагов k (k > N), и, видя неверный результат, обращается к преподавателю, который в течение времени Δt проверяет решение и находит число j первых правильно выполненных операций. Он сообщает обучаемому, что операции 1, 2, 3, …, j выполнены правильно и подсказывает (j+1)-ую операцию. В результате этой подсказки соответствующие вероятности pi (i = 1, 2, 3, …, j, j+1) правильных переходов увеличиваются на a(1-pi). После этого обучаемый либо возвращается к операции 1, либо пытается закончить решение задачи, выполняя (j+1), (j+2) и последующие операции. В случае ошибки он снова обращается к преподавателю.

После того, как задача решена правильно, происходит запоминание алгоритма решения, и вероятности pi (i = 1, 2, …, N) выбора правильных действий увеличиваются на a(1-pi). Вычисляется вероятность решения задачи P = p1p2…pN, характеризующая степень «обученности». Затем он приступает к решению следующей задачи того же типа и все повторяется.

На рис. 1 и 2 представлены типичные результаты имитационного моделирования решения сложной задачи для двух стратегий поведения:
1) обучаемый после совершения и ошибки и подсказки преподавателя продолжает решать данную задачу (рис. 1);
2) обучаемый возвращается к началу решения задачи (рис 2).

Рассмотрим работу имитационной программы [1], при запуске которой осуществляется отрисовка ступенчатой кривой, показывающей, как изменяется номер выполняемой обучаемый операции. Данная программа строит график зависимости вероятности решения задачи данного типа от времени P = P(t). В случае ошибки программа ставит точку на уровне F (FALSE). Если задача решена правильно и до конца, то ставится точка на уровне T (TRUE). Видно, что в обоих случаях формирование навыка происходит в соответствии с логистической функцией, графиком зависимости P(t) является S-кривая. В первом случае формирование навыка происходит заметно быстрее, чем во втором. Это объясняется тем, что каждый раз возвращаясь к началу решения (стратегия 2), обучаемый сначала учится выполнять операции 1, 2, 3 и не может сразу приступить к выполнению операций 4, 5, 6, 7. В первом случае обучаемый одновременно усваивает все операции.

Рис. 1. Модель решения задачи обучаемым (стратегия 1)

Рис. 2. Модель решения задачи обучаемым (стратегия 2)

Абстрактная модель обучаемого представляющая собой вероятностный автомат Мура (АМУ) с двумя состояниями рассмотрена подробно в [2, 3].

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

Литература:
1. Майер Р. В. Задачи, алгоритмы, программы / Р. В. Майер [Электронный ресурс]. – Глазов: ГГПИ, 2012 // Web-site http://maier-rv.glazov.net
2. Григорьев А. П., Чернелевский А. О. Элементы дискретной математики при построении интеллектуальной навигационной тренажерно-обучающей системы. Шестьдесят девятая международная студенческая научная конференция ГУАП: Сб. докл.: В 2 ч. Ч. I. Технические науки / СПб.: ГУАП., 2016. 419 с.: ил. – С. 146-150
3. Григорьев А. П., Керн Е. С. Разработка модели содержания и усвоения учебного материала в автоматизированных обучающих системах. 66-я шестая научно-техническая конференция ГУАП. СПб.: ГУАП., 2013

Комментарии

  • 1. Здравствуйте Иван Владимирович Колбасин. Данная статья является обзорной и рассматривает моделирование на базе теории автоматов, в дальнейшем, возможно, мы рассмотрим и более современных эвристических методах и подходы к описанию модели обучаемого при обучении. Автоматы уже отработаны, как логически, так и практически, очень у многих в курсе обучения была теория автоматов, поэтому, данный строгий математический аппарат достаточно известен и достаточно долгое время имел право на «жизнь». Если наши объяснения были для Вас неубедительны и у Вас возникли еще вопросы для дискуссии просим Вас писать на электронный адрес « anatoliy.chernelevskiy@mail.ru », мы будем рады ответить на них. С уважением Чернелевский А. О. 2. Здравствуйте Мельников Фёдор Варламович. Классическая математика была применима ранее, применяется сейчас и будет применима в будущем (как минимум в инженерных задачах из-за обработанности и строгости). Как Вы правильно заметили сейчас «модно» применение ИНС, но их эксплуатация, реализации и интеграция в какие-то системы, пока намного более затратна (и сложна) по сравнению с более грубыми методами, которые позволяют хоть и упрощенно, формировать модель обучаемого, но доступны практически всем без исключения. Если наши объяснения были для Вас неубедительны и у Вас возникли еще вопросы для дискуссии просим Вас писать на электронный адрес « anatoliy.chernelevskiy@mail.ru », мы будем рады ответить на них. С уважением Чернелевский А. О.

  • В рамках теории автоматов достаточно сложно решать серьезные, полноразмерные прикладные задачи из-за сложности в отслеживании ошибок (отладка). Да, с одной стороны есть строгая математическая формализация, процесс работы автомата логичен и понят, подлежит формализации и достаточно визуализирован...А с другой стороны степень абстракции явно недостаточна, возникает вопрос об адекватности модели обучаемого на базе автомата...Стоит сосредоточиться на мой взгляд не на теории автоматов (разработана в 60-х годах 20 века), а на более современных эвристических методах и подходах к описанию модели обучаемого в целом и процесса обучения в частности

  • Полностью согласен с Вашим мнением по всем пунктам, в защиту автоматов могу сказать немного: отработанный математический аппарат, так как дискретная математика является "классической" и признаётся математическим и инженерным сообществом, в отличии от тех же эвристических (нестрогих подходов) которые Вы упомянули. С прикладной точки зрения актуальность применения теории автоматов оценить трудно, все те недостатки, что Вы озвучали - правомерны...Тем не менее данный курс читается во многих ВТУЗах, причем как в рамках курса "Дискретная математика", "Спец. разделы высшей математики", так и в рамках спец. дисциплин (Микропроцессорная техника, электроника, схемотехника и пр.)...В инженерии знаний (раздел кибернетики) теория автоматов рассматривается для построения упрощенных (идеальных "лабораторных") моделей ответа обучаемого. Я и мои магистранты используем вероятностный автомат Мура для моделирования обучаемого, который угадывает и/ или пытается угадывать правильные ответы при прохождении тестирования закрытого типа (требуется выбрать правильный вариант ответ из предложенного списка), тем самым, появляется возможность отследить характерные законы распределения данных "случайных" ответов по достоточно полноразмерной статистике и в конечном счёте учесть данные риски при выставлении окончательной оценки, тем самым повысив ещё достоверность. Также появляется возможность модернизировать тестовые задания таким образом, чтобы максимально снизить вероятность угадывания...Использование для этих задач автомата Мура предпочтительнее, по сравнению с организацией натурного эксперимента, так как "отпадает" необходимость в сборе и анализе статистики, нет необходимости в привлечении реальных учебных групп, что позволяет в конечном счёте существенно "выиграть время".

  • Действительно, дискретная математика считается «классической», но классическая не означает полноценную применимость в реалиях современного мира. Сейчас модно везде использовать технологию нейронных сетей, которые самообучаясь (при наличие минимальной (от 1000) статистики, желательно разнообразной и самообновляемой) достигает грандиозных результатов. Применение автоматов позволило Вам сымитировать примитивную модель обучаемого, она настолько примитивна, что в теории обработки и оценке достоверности уже давно считается не применимой, иногда даже ложно усложненной. Поэтому в качестве модели обучаемого требуется использовать аппараты адаптивного формирования модели обучаемого. Да, нужна статистика, время, но без этого выходные данные не применимы для дальнейшего использования.

  • Здравствуйте, уважаемый Федор Варламович, спасибо большое за емкую и содержательную реплику! Считаю, что это скорее тема для очной дискуссии, так как с нейросетями все не так просто и однозначно. Так исторически сложилось, что я написал кандидатскую по данной тематике, в соавторстве с научным руководителем в рамках работы над учебником по интеллектуальным обучающим системам был автором глав по эвристическим подходам (нейронные сети, нечеткая логика), да и вообще с 2007 года активно разрабатываю ИНС различного вида…и неплохо прочувствовал их «на вкус»… Об их плюсах – писали многие и много…Вы тоже назвали данные подходы модными, хотя серьезных научных трудов по ИНС (докторские диссертации) уже не встретишь, более того ряд компетентных ученых в сфере систем автоматического управления (институт проблем управления имени В.А. Трапезникова РАН) – «чистым» нейросетям в науке отводят – 3-5 лет – не более…На них становится все сложнее защититься…А вот комбинированные аппараты - ИНС+ГА, ИНС+НЛ и пр… все более завоевывают популярность…Впрочем это тезис дискуссионный… Тем не менее, у ИНС существует ряд серьезных недостатков (опять же, по лично моему мнению, так как не все мои коллеги согласятся с полным списком): 1) Проблема выбора оптимальной (или хотя бы квазиоптимальной) топологии (архитектуры). До сих пор нет строгих подходов к выбору, есть лишь рекомендации. Как следствие требуется разработка симуляторов для подбора топологий или же многоитерационный научный поиск и эксперимент. 2) Проблема выбора оптимального алгоритма обучения (или хотя бы квазиоптимального). Либо выбираете из стандартных градиентных и квазиньютоновских, либо идете по пути модификации существующих под свои цели (для более быстрого обучения, более высокой достоверности). В этом же пункте можно упомянуть и о проблеме выбора начальных условий обучения (обычно идут стандартным путем и считают, что они задаются случайным образом – то есть сеть инициализирована, значения весов и смещений - случайное). Но, согласно ряду работ, «грамотный» выбор начальных условий – не только сокращает время обучения, но и способствует повышению качества – на 10-15% (по работе сталкивался со статьями и диссертациями на эту тему, пишут их в основном «Математики») 3) Логика принятия решения сетью – скрыта от эксперта, то есть решить обратную задачу и по весам сети и/или ее выходу восстановить алгоритм принятия решения – не получится!!! И тут-то научное сообщество радостно и вполне оправданно называет полученные результаты - «шаманством» и разжигает костер на центральной площади. 4) Согласно теоремам А.Н. Колмогорова и А.Н. Горбаня, ну или опираясь на теоретические выкладки С. Хайкина (кому как проще и больше нравится) с одной стороны - любая сложная задача может быть формализована для решения нейросетью и это плюс, то есть это вроде бы универсальный аппарат для решения широкого круга прикладных задач, второе - любую сложную зависимость или в частном случае непрерывную функцию нескольких переменных можно с любой точностью реализовать с помощью двухслойной нейросети с достаточным количеством нейронов и нелинейной активационной функцией в скрытом слое. Но с другой стороны отсюда, же и следует, что нельзя разработать универсальную нейросеть сколь угодно большого «размера» и «мощи»!!! Для решения каждой из задач – потребуется проектировать и обучать отдельную сеть!!! В своих задачах при проектировании обучающих комплексов я использую 3-5 типов нейросетей, каждая своей размерности и для своей специализированной задачи! Да, каждая из них работает отлично (с достоверностью 0,92-0,96), но все же данный подход нельзя считать универсальным и как следствие каноническим! 5) Статистика для обучения – напрямую влияет на его качество…Повторю стандартную фразу всех специалистов в данной области: «Она должна эффективно охватывать изменчивость и богатство естественных данных, чтобы обучить ИНС работе в реальных условиях. При этом собрать, обработать и грамотно подготовить статистику для обучения – могут далеко не все разработчики…Это без преувеличения – искусство!!! Вы очень политкорректно указали размер статистики от 1000 и выше, я Вам как практик скажу, если вы хотите получить достоверность от 0,8 – более 3 тысяч, для 0,9 – более 5 тысяч, если более 0,9 (то что и заявляется многими авторами, из серии достоверность классификации сети, или достоверность распознавания – 0,96…иногда указывают в %) – требуется уже более 7000!!! Ну и конечно же чем больше – тем лучше, если есть время, силы и ресурсы… Опять же к слову об объеме статистики – в реальной ситуации она еще немного возрастет – за счет того, что всю ее придется поделить на 3 независимые части – обучающая, контрольная, тестовая. На первой сеть обучается, на второй идет отладка, третья – тестовая нужна для того чтобы окончательно проверить сеть на переобученность и убедиться, что в процессе обучения веса «зафиксировались» не на первом же по счету локальном оптимуме…Так как от этого напрямую зависит достоверность! Опять же если брать реальную статистику по обучаемым (а это предпочтительнее по сравнению с использованием смоделированной), то на это потребуется не один год! Тем не менее, ИНС позволяет быстрее получить результаты по сравнению со статистическими методами, за счет того, что сеть можно постепенно «дообучать», не дожидаясь полного сбора статистики. Исходя из проблем 1 и 2 – доказать научному сообществу или хотя бы обосновать «правильный» выбор топологии – затруднительно, тоже самое и с алгоритмом обучения…требуется выбрать либо критерий его отбора, либо хотя бы показатель и обосновать его по серии многократно повторяющихся экспериментов. Конечно, в науке нет авторитетов, если лишь опыт и доказательство, тем не менее, пренебрегать действующей парадигмой и бездоказательно уходить от классических и канонических подходов к эвристическим – рискованно. Таким образом, резюмируя, для инженерных, «не особо ответственных» и «не военных» прикладных задач, ИНС – прекрасно подходят…В научных и военных кругах к ним относятся с некоторым недоверием. Как, человек, работающий в Ракетно-космической и авиационной отросли – скажу однозначно – на борт ВП МО никогда такие вещи не поставит, потому как автономные системы, о которых я уже говорил, должны функционировать взаимооднозначно, строго, предсказуемо, на базе жесткого и прогнозируемого алгоритма…В задачах обучения – ИНС применяется повсеместно, в интеллектуальной обработке данных различного вида сети также нашли активное применение…Тем не менее все равно это не панацея и хоронить раньше времени классическую математику с ее широкоуниверсальным аппаратом – не стоит!

Оставьте свой комментарий