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

А.Е. Степанов

doi:10.17759/mda.2025150109

Введение

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

Постановка задачи и алгоритм решения

Вектором случайных параметров задачи является вектор

Z = col (X^{T}, T^{T})

, состоящий из двух подвекторов

X

и

T

. Координаты вектора

X

моделируют правильность решения i-ого задания теста, состоящего из

n

заданий. Предполагается, что

X_{i}, i = 1, \dots, n

являются независимыми случайными величинами, имеющими распределение Бернулли, с параметрами

p_{i,} i = 1, \dots, n

, оцениваемыми частотой правильных ответов тестируемого на аналогичные задания

i

-ого типа в ходе подготовки к тестированию, или в процессе обучения. Равенство 1 случайной величины

X_{i}

моделирует правильность решения тестируемым

i

-ого задания, а равенство 0 – противоположное событие. Координаты вектора

T

моделируют время ответа пользователя на соответствующее задание теста. Случайные величины

T_{i}, i = 1, \dots, n

также предполагаются независимыми. Однако предполагать независимость между величинами

X

и

T

было бы опрометчиво, поэтому для каждого значения

X_{i}

(0 или 1) оценивается свое распределение случайной величины

T_{i}

также на базе статистики решения тестируемым заданий аналогичного типа. Непрерывные распределения времени ответа пользователя на задание (Ван дер Линдена [Van der Linden, 1999], Гамма-распределения [Шамсутдинова, 2021]) не позволяют найти точное решение задачи в вероятностной постановке, поэтому в работе используется дискретизированная модель времени ответа с тремя значениями, моделирующими ситуации быстрого решения, стандартного решения и решения с затруднениями. Таким образом, общий вектор случайных величин имеет дискретное распределение с числом реализаций

{D = 2}^{n} * 3^{n}

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

Требуется определить стратегию тестируемого при выполнении им ограниченного по времени теста из

n

заданий. Стратегия определяется вектором булевых переменных

u \in \{0,1 {\}}^{n}

, где

u_{i} ≜ {\begin{matrix} 1, \land если тестируемый пытается решать i - е задание теста, \\ 0, если тестируемый не пытается решать i - е задание теста . \end{matrix}

За каждое

i - е задание теста

начисляется

b_{i}

баллов. Время выполнения теста ограничено величиной

\bar{T}

.

Рассмотрим следующую оптимизационную задачу:

M

(1)

при ограничении:

P \{\underset{i = \bar{1, n}}{Σ} u_{i} T_{i} \leq \bar{T} \} \geq α .

(2)

В ней величина доверительной вероятности

α ⋹ (0,1)

играет роль параметра.

Данная задача является задачей стохастического программирования с критерием в форме математического ожидания, булевыми переменными и вероятностным ограничением, аналогичную классическим постановкам Чарнса и Купера [12,13]. Критерий представляет собой среднее значение набранного тестируемым за тест числа баллов, которое максимизируется. Ограничение обеспечивает с заданным уровнем доверительной вероятности

α

непревышение тестируемым фиксированного времени

\bar{T}

, выделяемого на тест.

Выбор в качестве критерия среднего числа набранных за тест баллов допускает также иную трактовку постановки задачи:

M {\underset{i = \bar{1, n}}{Σ} u_{i} X_{i} b_{i} | \underset{i = \bar{1, n}}{Σ} u_{i} T_{i} \leq \bar{T}} \to \max_{u \in \{0,1 {\}}^{n}}

(3)

В данном случае максимизируется условное математическое ожидание числа набранных баллов при условии удовлетворения тестируемым ограниничения на время выполнения теста. Сосредоточим далее усилия на решении задачи (1), (2).

Как уже было сказано выше, число всех возможных реализаций вектора случайных параметров

col (X^{T}, T^{T})

равно

{D = 2}^{n} * 3^{n} .

Рассмотрим вектор

δ \in \{0,1 {\}}^{D}

, каждая координата которого соответствует одной из реализаций вектора

col ({x^{ν}}^{T}, {t^{ν}}^{T})

вектора

col (X^{T}, T^{T})

и может принимать значения 0 или 1. Пусть

ϒ ≜ e^{T} b

, где

e =

, т.е.

ϒ = \underset{i = \bar{1, n}}{Σ} b_{i}

– максимальное количество баллов, которое можно набрать за тест. Пусть

p_{ν} = P (col (X^{T}, T^{T}) = col ({x^{ν}}^{T}, {t^{ν}}^{T})), ν = \bar{1, D}

. Тогда, на основании доверительного метода [Кан, 2009], с использованием предложенной в [Кибзун, 2013] методики, задача стохастического программирования (1), (2) может быть сведена к детерминированной задаче оптимизации с булевыми переменными.

Если предположить независимость случайных величин

X

и

T,

то эквивалентная задача будет иметь вид :

\underset{i = \bar{1, n}}{Σ} u_{i} p_{i} b_{i} \to \max_{u \in \{0,1 {\}}^{n}, δ \in \{0,1 {\}}^{D}}

(4)

при ограничениях:

{u^{T} t}^{ν} \leq δ_{ν} \bar{T} + (1 - δ_{ν}) T^{MAX}, ν = \bar{1, D},

(5)

\underset{ν = \bar{1, D}}{Σ} p_{ν} δ_{ν} \geq α

, (6)

где

T^{MAX}

- максимальное время, которое может потратить тестируемый на выполнение теста.

В общем случае зависимости случайных величин

X

и

T,

эквивалентная задача будет иметь вид :

\underset{ν = \bar{1, D}}{Σ} p_{ν} δ_{ν} \underset{i = \bar{1, n}}{Σ} u_{i} x_{i}^{ν} b_{i} \to \max_{u \in \{0,1 {\}}^{n}, δ \in \{0,1 {\}}^{D}}

(7)

при ограничениях:

{u^{T} t}^{ν} \leq δ_{ν} \bar{T} + (1 - δ_{ν}) T^{MAX}, ν = \bar{1, D},

(8)

\underset{ν = \bar{1, D}}{Σ} p_{ν} δ_{ν} \geq α

, (9)

Заметим, что указанная методика, в случае зависимости используемых в задаче случайных величин позволяет получить эквивалентную детерминированную оптимизационную задачу (6)-(8) в классе задач нелинейной булевой оптимизации, в то время как для независимых случайных параметров эквивалентная детерминированная задача приобретает вид задачи линейного программирования (ЗЛП) с булевыми переменными (3)-(5), что дарит надежду использовать специальные методы решения дискретных ЗЛП.

Если размерности задачи (4)-(6) и (7)-(9) допускают их решение стандартными процедурами из известных библиотек оптимизационных программ, то решение исходной задачи может быть найдено с их помощью. Однако, эти задачи содержат дополнительный вектор переменных оптимизации

δ \in \{0,1 {\}}^{D}

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

Предлагается следующий алгоритм решения исходной задачи (1),(2), являющийся модификацией алгоритмов, предложенных в коллективе авторов в [Наумов, 2024], [Мартюшова, 2024].

Алгоритм.

Шаг 0.

Положим

M^{} ≔ 0

, а

u^{} ϵ {0, 1}^{n}

равным нулевому вектору.

Шаг 1.

Исключим стратегии, которые не соответствуют допустимому суммарному времени даже в самом оптимистичном сценарии, где все выбранные задачи решены за минимально возможное время

T_{i}^{\min}

. Оно является наименьшим из всех возможных реализаций случайной величины

T_{i}, i = \bar{1, n}

.

Из всех

2^{n}

стратегий

u ϵ {0, 1}^{n}

выбираем

N

, образующих множество

\underset{̲}{U}

, для элементов которого выполнены условия:

\sum_{i = 1}^{n} u_{i} T^{\min} \leq \bar{T,}

Перенумеруем все элементы множества

\underset{̲}{U}

. Таким образом, число от 1 до

N

однозначно определяет элемент множества. Под

u^{m}

будем понимать

m

-й элемент множества

\underset{̲}{U}

. Положим

m ≔ 1.

На этом шаге инициируется внешний цикл перебора всех

N

выбранных стратегий оптимизации.

Шаг 2.

Если

m > N

то переходим к шагу 7. В противном случае полагаем

P_{m} ≔ 0

, где

P_{m}

– вспомогательный параметр для расчета вероятности выполнения ограничений.

Шаг 3.

Предположим, что вектор

u^{m}

содержит ровно

K

единиц. Предположим, что ненулевыми компонентами вектора

u^{m}

являются компоненты с номерами

i_{1}, i_{2}, \dots i_{K}

. Рассмотрим подвектор

col (X_{i_{1}}, X_{i_{2}}, \dots, X_{i_{K}})

случайного вектора

X

. Положим

J : = 2^{K}

, а

j : = 1

.

На этом шаге инициализируется цикл перебора всех возможных реализаций

col (x_{i_{1}}^{j}, x_{i_{2}}^{j}, \dots, x_{i_{K}}^{j}), j = \bar{1, 2^{K} .}

Шаг 4.

Если

j > J

, то переходим к шагу 6.

В противном случае, полагаем

L : = 3^{K}

, а

l : = 1

и переходим к шагу 5.

На этом шаге инициализируется цикл перебора всех возможных реализаций

col (t_{i_{1}}^{l}, t_{i_{2}}^{l}, \dots, t_{i_{K}}^{l}), l = \bar{1, 3^{K}}

подвектора

col (T_{i_{1}}, T_{i_{2}}, \dots, T_{i_{K}})

случайного вектора

T

.

Шаг 5.

Если

l > L

, то полагаем

j : = j + 1

, и переходим к шагу 4.

В противном случае, если для реализации

col (t_{i_{1}}^{l}, t_{i_{2}}^{l}, \dots, t_{i_{K}}^{l})

выполняется условие

\sum_{i ϵ {i_{1}, i_{2}, \dots, i_{K}}} u_{i}^{m} t_{i}^{l} \leq \bar{T,}

то полагаем

P_{m} ≔ P_{m} + \prod_{i ϵ {i_{1}, i_{2}, \dots, i_{K}}} P

l ≔ l + 1

и переходим к началу шага 5.

Шаг 6.

Полагаем

M : = \underset{i = \bar{1, n}}{Σ} u_{i} p_{i} b_{i}

.

Если величина

P_{m} \geq α

и

M > M^{}

, то полагаем

M^{} : = M, u^{} : = u^{m}, m : = m + 1

и переходим к шагу 2.

Если величина

P_{m} \geq α

и

M \leq M^{}

, то полагаем

m : = m + 1

и переходим к шагу 2.

Если величина

P_{m} < α

, то полагаем

m : = m + 1

и переходим к шагу 2.

Шаг 7.

Полагаем оптимальное значение критерия равным

M^{}

, а оптимальное значение стратегии равным

u^{}

. Равенство

M^{}

нулю соответствует отсутствию допустимого решения рассматриваемой задачи.

Результаты численного эксперимента

В целях сравнения и верификации результатов численного эксперимента исходные данные взяты из [Наумов, 2024], где они получены на основе анализа функционирования системы дистанционного обучения МАИ CLASS.NET [Наумов, 2014]. Будем предполагать число заданий в тесте

n = 10

.

Согласно данным, приведенным в [Наумов, 2024],

T^{\max} = 3830 с

. В результате работы предложенного алгоритма были получены следующие зависимости оптимальных решений от значений параметров задачи α и

\bar{T}

(см. табл. 1 и 2).

Таблица 1. Зависимость оптимального решения задачи от параметра α при

\bar{T} =

{0.6 T}^{\max}

	Оптимальная стратегия	Оптимальное значение критерия $M^{}$	Время расчета(сек)
0. $4$	[1. 1. 1. 1. 1. 1. 1. 1. 0. 1.]	10.43	66,1
0. $5$	[1. 1. 1. 1. 1. 1. 1. 0. 0. 1.]	8.93	66,2
0. $6$	[1. 1. 1. 1. 1. 1. 1. 0. 0. 1.]	8.93	66,7
0. $7$	[1. 1. 1. 1. 1. 0. 1. 1. 0. 1.]	8.83	65,6
0. $8$	[1. 1. 1. 1. 1. 0. 1. 1. 0. 1.]	8.83	65,2
0. $9$	[1. 1. 1. 1. 1. 0. 1. 1. 0. 1.]	8.83	65,8
0. $95$	[1. 1. 1. 0. 1. 0. 1. 1. 0. 1.]	8.06	65,8

Таблица 2. Зависимость оптимального решения задачи от параметра

\bar{T}

при

α = 0.8

	Оптимальная стратегия	Оптимальное значение критерия $M^{}$	Время расчета (сек.)
0. $4 T^{\max}$	[1. 1. 1. 1. 1. 0. 1. 0. 0. 0.]	6.43	32,9
0. $5 T^{\max}$	[1. 1. 1. 1. 1. 0. 1. 1. 0. 0.]	7.43	66,1
0. $6 T^{\max}$	[1. 1. 1. 1. 1. 0. 1. 1. 0. 1.]	8.83	66,2
0. $7 T^{\max}$	[1. 1. 1. 1. 1. 0. 1. 1. 1. 1.]	9.63	65,7
0. $8 T^{\max}$	[1. 1. 1. 1. 1. 1. 1. 1. 0. 1.]	10.43	65,2
0. $9 T^{\max}$	[1. 1. 1. 1. 1. 1. 1. 1. 1. 1.]	11.23	64,8

Результаты численного эксперимента логично демонстрируют, что с ростом уровня доверительной вероятности

α

, т.е. ужесточением ограничений в задаче, оптимальное значение критерия убывает, а ослабление ограничений путем увеличения времени, выделяемого на прохождение теста, приводит к росту оптимального значения критерия. При этом эффективность предложенного алгоритма решения подтверждается незначительным временем, затрачиваемым на решение задачи, по сравнению с результатами использования стандартных библиотечных процедур решения задач целочисленного линейного программирования аналогичных (4)-(6), использованных в [Наумов, 2024], [Мартюшова, 2024] для решения рассматриваемой задачи в близких вероятностных постановках.

Заключение

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

В работе используются исходные данные, приведенные ранее в статьях [10-11], где аналогичная задача решалась с квантильным критерием и критерием максимизации вероятности преодоления набранным за тест числом баллов некоторого фиксированного уровня. Полученные в работе результаты согласуются с найденными ранее результатами с использованием других критериев оптимизации. Совокупный анализ тестируемым всех стратегий, оптимальных по различным критерием, позволяет ему сделать осмысленный выбор поведения при прохождении ограниченного по времени теста.

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

Резюме

Общая информация

Полный текст

Введение

Постановка задачи и алгоритм решения

Заключение

Литература

Информация об авторах

Метрики

Просмотров web

Скачиваний PDF

Всего