Дерево (граф) решений

В данном разделе описывается модель алгоритмов вычислений, выполняемых над моделью предметной области, представляемая в виде дерева (графа) решений.
Данный раздел соответствует пакетам its.model.nodes и its.model.expressions в коде.

Note

По-хорошему, фреймворк Compprehensive ITS, должен работать с направленным ациклическим графом (Directed Acyclic Graph, DAG) решений, а не деревом - т.е. на один и тот же узел должны мочь ссылаться несколько узлов.
Так было не всегда - данная модель долгое время была просто деревом, поэтому название устоялось. Более того, даже сейчас в коде проектов its_* данная структура представлена именно деревом, без прямой поддержки DAG-структуры. Имитация DAG-структуры достигается путем дублирования узлов, имеющих несколько родительских узлов, во время экспорта из графического редактора - т.е., DAG преобразовывается в дерево.
Именно поэтому здесь и далее в этом разделе данная структура будет называется деревом.

Общие принципы

Прежде всего, необходимо понимать, что дерево решений представляет собой запись некого алгоритма. Понять данную модель можно примерно как обычное представление алгоритма в виде блок-схемы: каждый узел дерева представляет один шаг алгоритма, а переходы между узлами - возможные переходы между данными шагами.

Проще всего, наверное, рассмотреть на примере:
decision_tree_sample.png
Здесь изображен весьма простой и несерьезный пример дерева решений, представляющего алгоритм проверки, выбран ли хороший питомец (для своеобразного определения "хорошего питомца").

Note

Визуальное представление деревьев решений чаще всего реализуется с помощью графического редактора draw.io (он же diagrams.net) - либо просто в условном схематическом виде (т.е. просто как рисунок), либо с использованием дополнительного расширения (называемого далее просто "редактор"), позволяющего задавать дереву необходимые для его формального представления в коде данные, и впоследствии их экспортировать для использования в коде.
В данной вики стандарты визуального представления объясняться не будут, но будут использованы для удобства.
Проще говоря: про визуальное редактирование - не ко мне.

Так, дерево решений принимает некоторые входные данные (в примере - Питомец Х, и Пользователь U, обозначены прямоугольником в самом верху дерева), с которыми затем производятся различные действия и проверки, для того, чтобы получить некий результат (в примере - узнать, был ли выбран хороший питомец).
В этом смысле дерево решений, опять таки, является просто алгоритмом или функцией - принимает данные, выполняет операции, и выдает результат.

Данные, которыми оперирует дерево решений, определяются соответствующей моделью предметной области. Подробнее об этом - ниже.

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

Конкретные операции с данными, выполняемые в узлах, записываются в них особым формальным языком выражений. В зависимости от типа узла, данные выражения могут играть различную роль - описывать формально выполняемые проверки, определять отдельные категории объектов и прочее.
Подробнее про виды выражений читайте в соответствующей статье.

Переходы между узлами совершаются в зависимости от результата выполнения операции в узле. Конкретный способ определения перехода зависит от используемого типа узла.

В итоге прорешивания дерева (последовательного прохождения по его узлам и их выполнения) процесс завершается в одном из узлов-результатов, обозначенных на рисунке небольшими красными и зелеными прямоугольниками. Данные узлы, по сути, представляют собой ответ на вопрос, которым занимается дерево: "Выбран ли хороший питомец?" - "Да, верно, выбран." или "Нет, неверно, не выбран."

В коде деревья представлены классом DecisionTree.
Состав хранимой в нем информации:

  • Набор базовых входных переменных (DecisionTree.variables)
  • Набор вторичных входных переменных, вычисляемых на основе базовых (DecisionTree.implicitVariables)
  • Ветвь мысли, соответствующая основному "телу" дерева мысли (т.е. его основная часть, ответственная за вычисления) (DecisionTree.thoughtBranch)

Отдельные элементы дерева решений представлены наследниками класса DecisionTreeElement.
Состав базовой хранимой в нем информации:

  • Дерево решений, которому элемент принадлежит (DecisionTreeElement.decisionTree)
  • Родительский элемент (DecisionTreeElement.parent)
  • Метаданные данного элемента (DecisionTreeElement.metadata).

Виды деревьев решений

Алгоритмы, представляемые деревьями решений, можно разделить на два больших вида:

А. Алгоритмы, призванные найти (построить или выбрать) конкретный ответ на поставленную задачу. Например, "Какой тип значения возвращает данный вызов функции?". В этом случае дерево должно вернуть конкретный, подходящий к ситуации, ответ.
Такие деревья назвываются решающими (или "зелеными", т.к. их узлы-результаты имеют только корректные ответы, визуально отмечаемые зеленым цветом).

Б. Алгоритмы, призванные проверить ответ, уже данный на поставленную задачу. Например, "Возвращает ли данный вызов функции указанный тип Т?". В этом случае дерево должно вернуть результат данной проверки - правилен ли ответ, или нет.
Такие деревья называются проверяющими (или "красно-зелеными", т.к. в этом случае узлы-результаты обозначают как верные, так и неверные ответы, и могут обозначаться зеленым или красным цветом соответственно).

Данные виды деревьев отражают, в общем, два разных подхода к построению обучающих систем - model-tracing (буквально "прослеживание модели") для решающих деревьев, и constraint-based ("основанный на ограничениях") для проверяющих деревьев.
Их использование, соответственно, обусловлено различными необходимостями - так, например, решающие деревья хороши, когда необходимо научить студента самому решать конкретную задачу, а проверяющие - когда необходимо показать ему, какие законы (ограничения) предметной области нарушил его неправильный ответ, и научить самому проверять ответ.

По названным выше примерам задач также легко видеть, что решающие деревья, чей набор ответов конечен, могут быть преобразованы в перебор ответов и их проверку по проверяющим деревьям.

Warning

На данный момент код проекта поддерживает работу только с проверяющими деревьями - до сих пор на практике деревья использовались только в рамках индивидуальных тренажеров для студентов, при проверке их ответов на представленные вопросы. Поэтому в решающих деревьях просто не было необходимости.
В связи с этим здесь и далее речь ведется только о проверяющих деревьях.
Тем не менее, существенных различий в этих видах деревьев нет - за исключением выдаваемых ими результатов.

Связь с моделью предметной области

Для того, чтобы определить возможность тех или иных действий в дереве, оно должно быть связано с моделью предметной области - необходимо определить, какими классами объектов дерево оперирует, а следовательно и какие их свойства и отношения ему "известны".

Таким образом, дерево решений никогда не существует "в вакууме", а привязано к конкретной модели предметной области.

Для этого в коде существует класс DomainSolvingModel - он объединяет в себе следующие данные:

  • Модель предметной области (домена), общее для всех ситуаций применения (DomainSolvingModel.domainModel)
  • Части предметной области, специфичные для отдельных ситуаций применения (т.н. теги) (DomainSolvingModel.tagsData)
  • Деревья решений, описывающие решение задач данной в предметной области (DomainSolvingModel.decisionTrees)
    Подробнее о различных частях модели предметной области см. в "Составление модели из частей"

Стоит отметить, что при хранении данной модели речь идет только о статической (постоянной) части предметной области - т.е., объекты в данных моделях почти всегда отсутствуют, поскольку отражают "динамическую" часть предметной области, отличающейся для каждой конкретной задачи.

Валидация

Корректность записи дерева решений выражается в двух составляющих

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

Сама валидация дерева вызывается методом DecisionTreeElement.validate (для выбрасывания исключений) или DecisionTreeElement.validateAndGet (для получения всего списка ошибок).
Соответственно, корректность дерева обусловлена корректностью всех составляющих его элементов.

Наиболее общим методом валидации является метод DomainSolvingModel.validate, который проверяет корректность всех входящих в него моделей. Здесь учитывается следующее:

  • Все теговые части модели из DomainSolvingModel.tagsData проверяются на полную корректность, с учетом того, что при использовании они объединяются с общей моделью DomainSolvingModel.domainModel
  • Деревья решений из DomainSolvingModel.decisionTrees проверяются на корректность с учетом того, что при использовании они должны мочь работать с любой из объединенных теговых моделей (т.е. валидация происходит для всех тегов)

Построение деревьев в коде