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

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

doi:10.17759/mda.2025150109

Моделирование и анализ данных
2025. Том 15. № 1. С. 158–167
doi:10.17759/mda.2025150109
ISSN: 2219-3758 / 2311-9454 (online)

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

4

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

Аннотация

В статье рассматривается задача поиска стратегии тестируемого при прохождении ограниченного по времени теста. За каждое задание теста начисляется определенное количество баллов. Критерием выступает среднее число набранных за тест баллов. Случайными факторами, учитываемыми в модели, является время решения тестируемым каждого задания и правильность его решения, моделируемая случайной величиной с распределением Бернулли. Задача формулируется в терминах стохастического линейного программирования с вероятностными ограничениями и критерием качества в виде математического ожидания числа набранных за тест баллов. Приводятся алгоритм решения, результаты численного эксперимента и их сравнительный анализ с ранее полученными авторами результатами решения подобной задачи с другими критериями качества.

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

Ключевые слова: тест, линейное программирование, вероятностное моделирование

Рубрика издания: Математическое моделирование

Тип материала: научная статья

DOI: https://doi.org/10.17759/mda.2025150109

Получена: 13.01.2025

Принята в печать: 25.02.2025

Для цитаты: Степанов А.Е. Максимизация среднего числа набранных баллов в ограниченном по времени тесте // Моделирование и анализ данных. 2025. Том 15. № 1. С. 158–167. 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], где аналогичная задача решалась с квантильным критерием и критерием максимизации вероятности преодоления набранным за тест числом баллов некоторого фиксированного уровня. Полученные в работе результаты согласуются с найденными ранее результатами с использованием других критериев оптимизации. Совокупный анализ тестируемым всех стратегий, оптимальных по различным критерием, позволяет ему сделать осмысленный выбор поведения при прохождении ограниченного по времени теста.

Литература

Van der Linden W. J., Scrams D. J., Schnipke D. L., et al. Using Response-Time Constraints to Control for Differential Speededness in Computerized Adaptive Testing // Applied Psychological Measurement. 1999. Vol. 23. No. 3. P. 195–210. DOI: 10.1177/01466219922031329.
Rasch G. Probabilistic models for some intelligence and attainment tests. – Chicago: The University of Chicago Press, 1980. 199 p.
Dumin P.N. and Kuravsky L.S. Studying Testing Effectiveness Dynamics in Training Operators of Complex Technical Systems // International Journal of Advanced Research in Engineering and Technology (IJARET). 2020. Vol.11. № 5, P. 133-140. DOI: 10.34218/IJARET.11.5.2020.0 15.
Pominov D.A., Kuravsky L.S., Dumin P.N. and Yuryev G.A. Adaptive Trainer for Preparing Students for Mathematical Exams // International Journal of Advanced Research in Engineering and Technology (IJARET). 2020. Vol. 11. № 11. 260-268. DOI 10.34218/IJARET.11.11.2020.022.
Kuravsky L. S., Margolis A. A., Marmalyuk P. A., Panfilova A. S., Yuryev G. A., Dumin P. N. A Probabilistic Model of Adaptive Training // Applied Mathematical Sciences, 2016. Vol. 10. №. 48. P. 2369–2380. http://dx.doi.org/10.12988/ams.2016.65168.
Босов А.В., Мартюшова Я.Г., Наумов А.В., Сапунова А.П. Байесовский подход к построению индивидуальной траектории пользователя в системе дистанционного обучения // Информатика и ее применения. 2020. Том 14. № 3. С. 86-93. DOI:14357/19922264200313.
Босов А.В., Мхитарян Г.А., Наумов А.В., Сапунова А.П. Использование гамма-распределения в задаче формирования ограниченного по времени теста, Информатика и ее применение, 2019. Том 13. №4. С.12-18. DOI: 10.14357/19922264190402.
Наумов А.В., Мхитарян Г.А., Черыгова Е.Е. Стохастическая постановка задачи формирования теста заданного уровня сложности с минимизацией квантили времени выполнения // Вестн. компьют. и информ. технологий. 2019. № 2. С. 37–46. DOI: 10.14489/vkit.2019.02.pp.037-046.
Шамсутдинова Т.М. Формирование индивидуальной образовательной траектории в адаптивных системах управления обучением // Открытое образование. 2021. № 25(6). С. 36-44. https://doi.org/10.21686/1818-4243-2021-6-36-44.
Наумов А.В., Устинов А. Э., Степанов А.Е. О задаче максимизации вероятности успешного прохождения ограниченного по времени теста // Автоматика и Телемеханика. 2024. № 1. С.97-108. DOI: 10.31857/S0005231024010061.
Мартюшова Я.Г., Наумов А.В., Степанов А.Е. Оптимизация прохождения ограниченного по времени теста по квантильному критерию // Информатика и ее применения. 2024, т. №4. C. 37-44. DOI: 10.14357/19922264240406.
Charnes A., Cooper W.W. Chance-Constrained Programming // Management Sci. 1959. № 5. P. 73–79. http://dx.doi.org/10.1287/mnsc.6.1.73.
Charnes A., Cooper W.W. Deterministic Equivalents for Optimizing and Satisficing under Chance-Constraints // Oper. Res. 1963. № 11. P. 18–39. DOI: 10.1287/opre.11.1.18.
Кан Ю.С., Кибзун А.И. Задачи стохастического программирования с вероятностными критериями. М.: Физматлит, 2009. ISBN 978-5-9221-1148-5.
Кибзун А.И., Наумов А.В., Норкин В.И. О сведении задачи квантильной оптимизации с дискретным распределением к задаче смешанного целочисленного программирования // Автоматика и Телемеханика. 2013. № 6. С. 66–86. DOI: https://doi.org/10.1134/S0005117913060064.
Наумов А. В., Джумурат А. С., Иноземцев А. О. Система дистанционного обучения математическим дисциплинам CLASS.NET // Вестник компьютерных и информационных технологий, 2014. № 10. С. 36–40. DOI: 10.14489/vkit.2014.010.pp.036-044.

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

Степанов Алексей Евгеньевич, аспирант, кафедра теории вероятностей и компьютерного моделирования, Московский Авиационный Институт (национальный исследовательский университет) (МАИ), Москва, Российская Федерация, e-mail: stepanoffalsey@gmail.com

Метрики

Просмотров web

За все время: 21
В прошлом месяце: 0
В текущем месяце: 21

Скачиваний PDF

За все время: 4
В прошлом месяце: 0
В текущем месяце: 4

Всего

За все время: 25
В прошлом месяце: 0
В текущем месяце: 25

PlumX

Метрики публикации