A Bounded Ability Estimation for Computerized Adaptive Testing
Authors: Yan Zhuang
Qi Liu
GuanHao Zhao
Zhenya Huang
Weizhe Huang
Zachary Pardos
Enhong Chen
Jinze Wu
Xin Li
Venue: NeurIPS 2023 poster (2023)
Keywords: adaptive learning
computerized adaptive testing
educational measurement
cognitive diagnosis
TL;DR: This paper optimizes question selection in CAT to achieve an upper-bounded ability estimation error.

Abstract: Computerized adaptive testing (CAT), as a tool that can efficiently measure student's ability, has been widely used in various standardized tests (e.g., GMAT and GRE). The adaptivity of CAT refers to the selection of the most informative questions for each student, reducing test length. Existing CAT methods do not explicitly target ability estimation accuracy since there is no student's true ability as ground truth; therefore, these methods cannot be guaranteed to make the estimate converge to the true with such limited responses. In this paper, we analyze the statistical properties of estimation and find a theoretical approximation of the true ability: the ability estimated by full responses to question bank. Based on this, a Bounded Ability Estimation framework for CAT (BECAT) is proposed in a data-summary manner, which selects a question subset that closely matches the gradient of the full responses. Thus, we develop an expected gradient difference approximation to design a simple greedy selection algorithm, and show the rigorous theoretical and error upper-bound guarantees of its ability estimate. Experiments on both real-world and synthetic datasets, show that it can reach the same estimation accuracy using 15\% less questions on average, significantly reducing test length.

A Bounded Ability Estimation for Computerized Adaptive Testing
Yan Zhuang!2 Qi Liu 12; GuanHao Zhao!?2 Zhenya Huang
Weizhe Huang Zachary A. Pardos' Enhong Chen 12, Jiize Wu Xin L
I: Anhui Province Key Laboratory of Big Data Analysis and Application,
University of Science and Technology of China
2: State Key Laboratory of Cognitive Intelligence
3: University of California, Berkeley
4: iFLYTEK Co., Ltd
{zykb, ghh {qiliuql, huangzhy, cheneh, leexin] @ustc. edu. cn, pardos@berkeley.coo edu
hwtpsi/www1i9.88 hxwjz)/maill ust.. edu..eddu.cco
Abstract
Computerized adaptive testing (CAT), tool that can efficiently measure stu- dent's ability, has been widely used in various standardized tests (e.g.. GMAT and GRE). The adaptivity of CAT refers to the selection of the most informative ques- tions for each student, reducing test length. Existing CAT methods do not explicitly target ability estimation accuracy since there is no student's s true ability as ground truth; therefore, these methods cannot be guaranteed to make the estimate converge to the true with such limited responses. In this paper, we analyze the statistical properties of estimation and find theoretical approximation of the true ability: the ability estimated by full responses to question bank. Based on this, a Bounded Ability Estimation framework for CAT (BECAT) is proposed in data- summary manner, which selects a question subset that closely matches the gradient of the full responses. Thus, we develop expected gradient difference approximation to design simple greedy selection algorithm, and show the rigorous theoretical and error upper-bound guarantees of its ability estimate. Experiments both real- world and synthetic datasets, show that it can reach the same estimation accuracy using 15% less questions on average, significantly reducing test length.
Introduction
As the landscape of education is changing rapidly, especially after COVID-19, many schools and institutions move from in-class to online platforms, providing individualized education, such as edu- cational measurement and recommendation. They are looking to "right-size" the learning experience of students according to their ability level 21. To this end, Computerized Adaptive Testing (CAT) 3 becomes indispensable tool to efficiently measure student's 's ability in the areas of standardized testing, computer tutoring, and online courses, through automatically selecting best-suited questions for individual students. Compared with the time-consen time-consuming and burdensome paper-and- and-peneil tests, CAT has been proven to require fewer questions to reach the same measurement accuracy [4] 22
A typical CAT system is shown in Figure At test step I, the Cognitive Diagnosis Model, e.g., Item Response Theory (IRT), as the user model based on psychology. first uses student's previous item answer responses to estimate his/her current ability 0*. IRT family has been used for ability estimation in several state assessments, such as OECD/PISA Project 6). Next, the selection algorithm selects the next item from the entire question bank according to some criteria 7 g 9 Most of them are
Corresponding Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

4c+1
Cognitive
Question Bank
Selection A Algorithm
steps of question selection
Final ability estimate OT
Diagnosis Model
X/V
(c.g., IRT)
ec An illustration of the CAT system: At test step t [1. [..... T]. the selection algorithm uses the current ability estimate 6* to select the next question 9t-1 from the question bank. When the test stops, the HT (i.e., the final estimate of his/her true ability 80) will be output.
Test Stops
Figure I:
informativeness metries such selecting the question with difficulty closest to his/her current ability estimate 0', i.e., the student's probability of answering it correctly is closest to 50% 7 Obviously, the selection algorithm the core component realize CAT's adaptivity and seeks to answer the following question about accuracy and efficiency: Can we estimate student's 's true ability by asking him/her few questions as possible, with negligible estimation error?
From the perspective of machine learning, CAT can be viewed as parameter estimation problem with the least cost: it is essentially to select the fewest data samples (questions to be answered) sequentially from the whole unlabeled data (question bank), so that after obtaining their labels (correct/wrong responses), model's hidden parameters (student true ability 0b) can be accurately estimated. Unfortunately, the exact true ability of student is unknown even to the students themselves, thus it is impossible find such ground truth datasets to design/train selection algorithms. As result, most selection algorithms are not designed explicitly with the goal of accurate and efficient estimation. Existing approaches either select representaaivee/dierss items solely from question feature space [9] (deviating from the goal of ability estimation). or require additional training overhead (e.g.. Although these implicit methods achieve good results in experiments, the theoretical guarantee on approximating student's 's true ability is also critical for reliable CAT systems especially in standardized tests.
Reinforcement Learning-bei -ased methods [I 12 [3)
Obviously, the biggest challenge of designing reliable explicit methods is: student's true ability 0g is unknown. Therefore, in this work, we propose general (upper-) )Bounded Ability Estimation CAT framework (BECAT), which explicitly targets the accuracy and efficiency of ability estimation. Due to the unknown Og. we first find its theoretical approximation 0" the alternative: the ability estimated by his/her full responses on the entire question bank. Hence, our key idea is to select questions such that the estimate can best approximate the ability estimated by full responses. Specifically, we propose an expected gradient difference approximation method based on recent data efficiency/summarry technique [14 [ [6), and design a practical greedy selection algorithm in submodular function, which essentially finds representative items to approximate the gradient of full responses. We further provide the theoretical analysis about its upper- upper-bound bound of ability estimation error.
To validate BECAT's effectiveness, we conduct experiments on three real-world datasets from different educational platforms. Empirical results show that this simple greedy selection achieves state-of-the-art performance compared with other implicit methods. The main contributions are:
To better estimate the unknown l, we find its theoretical approximation as the new target for designing explicit selection algorithm. Based on this, we formally redefine and transform CAT into an adaptive subset selection problem in data summary manner for the first time.
An effective expected gradient-basee selection algorithm proposed to select appropriate items, which exactly minimizes the estimation error term, therefore admitting theoretical guarantees on ability estimation in CAT systems.
We show the generality of BECAT - it can be applied to any gradient-based method, including IRT and neural network methods. We observe that BECAT outperforms existing CAT methods at reducing test length, requiring 10%-20% less questions to reach the same estimation accuracy.
2 Problem Definitions of CAT
For accurate and efficient assessment, CAT needs to sequentially select best-fitting questions for each student from the question bank Q; then uses the corresponding responses for ability estimation.

---

When the test stops, the final estimate is output as the result/score of this test. The goal of CAT is to accurately estimate examinee's 's true ability 6,, while minimizing the number of questions asked [77.
2.1 Preliminaries
Specifically, at test step E TT, given the student's previous t responses S {(91.8 (101.81).-00 v1...... (q. yt),, where {q: 19.);=n Q are selected sequentially by the selection algorithm and y is the binary outcomes of correct or incorrect; student's s current ability can be estimated by minimizing the empirical risk (e.g., binary cross-entropy) from the whole ability space O:
g arg min BEG
Σ ((0)) arg min log (o V:), iES,
(1)
dEG
VE
where Pa(g: V.) represents the probability of the response (q.. y:) towards a student with 8, and the specific form of po is determined by IRT. Since the size of S, small, Standard Gradient Descent
[8 19 is sufficient to minimize [p. and requires the computations of Zies. (4((0) - sum of
the gradients over the previous / response data. It takes repeated steps in the opposite direction of the gradient, thus leading to a minimum of the empirical risk in [I.
Next. the selection algorithm selects the next question 4t+1 from bank Q according various criteria 7 12 13].
The above process will be repeated for T times i.e., |S| = T (T' < 20 in most tests 13) ensuring the final step estimate 6 close to the true og. I.e.,
Definition (Traditional Definition of CAT)). At each step t, it will select the most suit- ablc/informative question, according to student's current ability 0'. When the test ends (t = T), the final ability estimate 0 arg millage Lies (:()) can approximate the true ability:
min ||0" -oll-
(2)
[S|=T
Unfortunately, directly solving the above optimization problem is infeasible. Because the ground truth ability du cannot be obtained and, even students themselves cannot know the exact value. As result, traditional informativeness- based methods 7 g use asymptotic statistical properties of Maximum Likelihood Estimation to reduce estimation uncertainty, e.g., selecting the one whose difficulty is closest to student's current ability 0'; but they are all IRT-specific, i.e., they can not be applied into recent neural networks methods. Although recent active learning-based [9] and reinforcement learning- based 112 13 methods achieve good experimental results, there is no evidence that they can theoretically guarantee that estimate efficiently approach fg which is unacceptable for CAT systems applied in standardized tests. Testing reliability requires not only satisfactory experimental results, but also good theoretical guarantees
2.2 New Definition of CAT
Given that there is no such ground truth 6g in the dataset, thus, for designing explicit selection algorithms, find its approximation as the new target.
Proposition 1. The student's 's one ability estimate 8", estimated by his/her full responses to the entire question bank Q an approximation of his/her true ability Oo that is,
Oo
(3)
Proof. When use consistent estimation approaches, such as Maximum Likelihood Estimation (cross-entropy loss) in Eq. D) we have lim p (10t - 0o! 2 c) = 0, where t is the number of responses t-o00 (steps) for ability estimation. The size of CAT's question bank is finite (i.c., E [o, (Ql) and 0" lim 0f, thus 0* xe lim Of ss Oo i.e., 0* can be regarded an approximation of 0o. t+
Since this proposition exploits estimator's ss asymptotic property and may make the approximation not perfect. For example, both the bank size Q and various perturbations in student's response
In this paper. we only consider the most common Exed-length tests (I' = 20), and the effect of test length be found in Appendix B
3

---

14
Without Perturbations 5%, Slip:
Moan Squar (MSE)
Guess: 25% Slip:
WLLD
0.6
Bank 2
207
000
1600
Bank Size
(a)
(b)
Figure 2: (a) Simulation experiments about Proposition using MSE: E[|00 - 01.l3). In addition to the normal situation (blue), we also show the MSE under different perturbations, for example: Slip5% means that the label has a 5% probability of changing from 1 to O; Guess25% means that the label changes from 0 to with 25%. (b) The illustration of the optimization problem: selecting subset to cover the whole response data on Q. The rectangles represent a student's full responses to the bank Q, and ji measures the similarity of response pair (i,
can impact this proposition. Thus, we also conduct simulation experiments further verify it: we randomly sample 100 Og from θ as groundtruth, using the smallest EXAM dataset (IQ) = 1650) in Section 4 then use IRT with these By to simulate the response behavior (correct/wrong) of 100 students. Figure 2 a) shows that when the bank size exceeds 300 (> [Q /5), the estimated 6* = 0 (blue). Even if some extreme perturbations (e.g., guess and slip factors 133 are added, their MSE will not exceed 0.1. Therefore, it is reasonable to replace Oo with 0" as the ground truth in optimization.
In this way, the selection algorithm aim to approach 6 instead of the unknown Og We can design explicit selection algorithms: Select a subset of questions S from the bank Q, so that the student's s ability is estimated only on the subset while still (approximately) converging to the optimal solution Or (i.e., the estimate that would be obtained if optimizing on the full responses to Q). As mentioned in Preliminaries, the ability estimation usually adopts cross-entropy loss with gradient computations, and denote the full gradient of the loss w.r.t. ability parameters by EieQ (l) sum of the gradients over full responses. Thus,
Definition 2 (New Definition of CAT). It will adaptively find subset S of size T and the corre- sponding weight {r}, that approximates the full gradient: minimizing their difference for all the possible ability values of the optimization parameter 0 E θ
min 110T - 0011= -
min max
Σ 75 VI)
VI(O))-
(4)
=|=T BEB
JES
SEQ
Since we know nothing about the range of student's ability when optimizing, we consider the worst- case approximation error (maxege) instead of particular 9. After finding such S and the associated weights {r}5, the gradient updates on S will be similar to the gradient on Q regardless of the value 0f 9. thus making the estimate close the target 0" In this way, CAT can be regarded as subset selection optimization problem in a dfta-efficiency manner. Also, we find that it is consistent with recent Coreset techniques 20 15 21, which approximate the gradients of the full data, that the model is trained only on the subset while still (approximately) converging to the optimal solution (i.e., the model parameters that would be obtained if training on the full data).
However, compared with the traditional Coreset problem, the biggest technical challenge is: the gradients on bank CieQ (l)( cannot be calculated without labels. Only the few questions that have been answered in previous steps (i.e., S,) have the corresponding labels. Thus, to simplify the problem, we assume for the moment that student's 's full responses are available. In Section 3.1 we will further propose an expected approximate method to address this.

---

3 The BECAT framework
In this section, to solve the above optimization problem Eq. 4). we design a simple greedy algorithm in submodular functions. More importantly, we provide an upper bound on the expected error of the ability estimate when using our method.
Optimization. The above subset selection problem is NP-hard, thus, we transform it based on the recent Coreset method. proves that the subset S that minimizes the error of estimating the full gradient is upper- boeeded by submodular facility location function that has been used in various Thus
summarization applications 22 23..
min max ||=T DEG
(O) V4(0)1I
min max |s|=T deG
minjes -V,(0))
jES
TEQ
sEQ
max I
maxjes w(i.j),
(5)
E
where j) _ d - maxage Vl, (O)( is the gradient similarity between response pair
i (q., 814 and j [gg, M3) for this student. The associated weight of the response j. Y Eieo 1 = arg max.es wii s)], is the number of responses in Q that are most similar to E S.
Given subset S. Eieq maxjes w(i, j) in Eq. 5 quamtifies the coverage of the whole response data on Q, by summing the similarities w between every i E Q and its closest item j E S. The semantics of this optimization problem is shown in Figure (()). The larger the value of ji,, the smaller their gradient difference in ability estimation for all the possible ability E O which means these two the student's ability estimation. Thus, the
responses and have similar importaace/iiffuunce transformed problem in Eq is equivalent to selecting the most representative responses to form the subset S, which shares the same idea (i.e., selecting "representative" items) with previous selection algorithms 12 9,
active learning methods 24 25 and unsupervised learning (26 27
Define monotone nen-decragiing submodular function the facility location function F 2 - R:
F(S)= = Eie maxjes j). The submodular optimization provides near-optimal solution with a (1 1/ee approximmaion bound (28), with simple greedy algorithm for selecting the (-th question:
qe = arg wag.max(caom (g.)) ((g. y) S1-1).
(6)
where A((g, y) S) = F(1 v) U S. F(S.-1) and S is the set of previous / responses of this student in CAT.
3.1 Expected Gradient Difference Approximation
However, the above selection algorithm is impractical in CAT. Because we cannot get student's full responses to bank Q, as result, the gradient difference (4) - (l)( in w(i,)) can not be calculated without related answer correctness labels. Actually, step t, only the responses of previous t steps (i.c., St-1) can be obtained. Therefore, we propose an expected gradient difference approximation method to replace the original measure their similarity, then the new similarity function (ii.j) j) is:
@(i - d max E PoP [IIV (O)I, OE0
where the normed gradient difference calculated as an expectation Eg-p,, over the possible labelings, since student's ' response labels y to the candidate questions are unknown in the selection step. Moreover, for more accurate approximation and to make full use of the available previous - 1 responses, in 77. the expectation is determined by the current estimate 0'. This method can be regarded as a gradient difference approximation based on "soft pscudo-labels" Thus, the selection of the next question qi no longer requires the student's 's real answer correctness labels:
a arg max max,E nEQUS, A(g
(8)
where A(g)S,-1) = F(1g) U S F(S.-1), and F(S) Eieo max w(i,)). Also, uncover some important conclusions about this simple expected approximation:
5

---

Algorithm 1: The BECAT framework
Require: -question bank, f- IRT or neural network methods.
Initialize: Initialize the responses data So <-
for t= to do
Select question Ør based on w(i,j): ai f arg r.
Get student's related answer correctness label yr: S. t S U f(:. v.)}.
Update the weights {7y ( " + -EieQ 1Dj = arg max,es, sii,
Update student's 's ability estimate: Ht +- arg mingee Eies, (4).
Output: The student's final ability estimate 0T.
Lemma 1. When we replace the original gradient difference in 5)( with w(t,j), the correspond- ing designed selection algorithm using submodular function is actually approximately solving the following optimization problem:
min max Ey
75 Vl, V4(0))
(9)
s== AEe
jES
iEQ
Based the conclusion in Lemma we assume that, after optimization, the preconditioned expected gradient can be approximated by an eтror of at most e: E, "; (1) - Eieq VI,(O)I] <. Then we find the theoretical guarantees for abil- ity estimation when applying gradient-based estimation method to the subset S found by it:
Theorem (Expected estimation eπror bound). Assume that the loss function for ability estimation a-strongly convex (e.g.. IRT). Let S be weighted subset obtained by the proposed method. Then with learning rate 2.e ability estimation in gradient descent applied to the subsets has the following expected estimation error bound:
2eDx + of t20 E -
0011 S
(10)
a²
where Hp'0", E(g.))pps
(11)
Pa- (g. v)
where 0* is the optimal estimate using full responses, o is upper bound on the norm of the gradients, and D maxg |0 0" 1)
All the proofs can be found in Appendix. The above theorem shows that despite not being able to obtain student's full response, such simple expected gradient difference approximation can make the estimate error upper bounded at each step. This theorem is attainable for the case where the loss is strongly convex, such as the cross-entrops loss of the classic ..-rreguarr IRT [29]. We will further verify the performance of other cases (e.g., neural network-based methods) in experiments.
Theorem D also suggests that, to minimize the expected error bound, the CAT systems should try to minimize (0' 00") that can be regarded
type of statistical distance: measuring how probability distribution Pa: is different from pg-. Moreover, we find that with the help of the consistency estimation (i.c., binary cross-entropy) at each step, Hp, 0*) can reach its theoretical minimum:
Theorem 2. Assume that 0', estimated by the cross-entropy loss in Eq. D. can minimize the empirical risk i.e. Eies, 4(00) O. Then H, (0, 8*) can take its minimum when 0*, that is
(0', 0*) < (,,000") e
(12)
Therefore, the ability estimation methods commonly used in CAT can actually help minimize this upper bound. The proofs and related experiments can found the Appendix C and
Complexity Analysis of BECAT. Algorithm I presents the pseudo-code of our BECAT framework.
naive implementation of our selection algorithm in E (8) has the complexity of (() because at each step we have to: (1) find the question from the bank (O(IQ)) that (2) maximizes

---

the marginal gain (
with complexity (( To make BECAT faster and more scalable from the above two aspects, we adopt two speed-up tricks: lazy evaluations 30 31 and multifaceted estimation 32 (See Appendix D for implementation details).
Also, we compare the time (second) spent on question selection by different methods in Appendix H
4 Experiments
Evaluation Method. The goal of CAT is to estimate the student's ability accurately with the fewest steps. Therefore, there are usually two tasks to verify the performance of different CAT methods following prior works 9 12: (1) Student Score Prediction: To evaluate the ability estimate output by CAT, the estimate can be used for predicting the student's binary response (correct/wrong) on the questions he/she has answered in the held-out response data. Thus, Prediction Accuracy (ACC) and AUC are used for evaluations [33]; (2) Simulation of Ability Estimation: This is CAT's traditional evaluation methods. Since the ground truth of student ability &g is not available, we artificially use Mean
generate the 8 and further simulate sudent--uestion interaction process. Thus, Square Error (MSE) metric. See Appendix for the details of these two evaluation methods.
Datasets. We conduct experiments on three educational benchmark datasets, namely ASSIST, NIPS-EDU, and EXAM. ASSIST 30 is collected from an online educational system ASSISTments and consists of students' practice logs on mathematics. NIPS-EDU 335 refers to the large-scale dataset in NeurIPS 2020 Education Challenge, which is collected from students' answers to questions from Eedi (an educational platformm. The EXAM dataset was supplied by iFLYTEK Co., Ltd., which collected the records of junior high school students on mathematical exams. The statistics of the datasets are shown in appendix. The code can be found in the github: https: htt::/ggttttt thub. com/ bi caattaaussc/Edduoa
Compared Approaches. To verify the generality of BECAT, in addition to the traditional IRT, we also compare the neural network-based model NeuralCDM 36: : It can cover many IRT and cognitive diagnosis models, such as MIRT 37 and MF mainly use the following SOTA algorithms baselines: Random: The random selection strategy is a benchmark to quantify the improvement of other methods; FSI 7 and KLI [8] select the question with the maximum that a question carries about the unknown parameter 0. They are specially designed for IRT. MAAT (9] utilizes Active Learning
38 39 For the selection algorithm, we
information, which measures the amount of information
40 measure the uncertainty caused by each candidate question. BOBCAT [22] and NCAT [13] recast CAT as a bilevel optimization and Reinforcement Learning problem respectively, and train a data-driven selection algorithm from student response data.
4.1 Results and Discussion
In this section, we compare the performance on two classic CAT tasks introduced above to evaluate the effectiveness and efficiency of our proposed BECAT framework. Also, we conduct qualitative investigation of the characteristics of the selected questions, and gain deeper insights on why BECAT leads to more accurate ability estimation.
Task1:
Student Score Prediction. Following prior work [3]. we also fix the max length T = 20 and calculate the ACC and AUC at step 5, 10 and 20 on three datasets for Student Score Prediction task and the results are shown in Table We find that:
(I) The explicit BECAT framework achieves the best overall performances on the three datasets. performs significantly better than all the other methods, where the relative performance improvements are as least 1.5% with respect to ACC 20 and 1.1% with respect to AUC@ 20 on average on ASSIST. This result indicates that BECAT can provide accurate ability estimates at the end of the exam. Also, it even surpasses the implicit selection algorithms based on deep learning, such as NCAT and BOBCAT. This phenomenon shows that compared focusing modeling complex student-question interactions, targeting the accuracy of estimation indeed achieves amazing results.
(2) BECAT's performance on large-scale datasets (e.g., NIPS-EDUS is better. From Table on NIPS- EDU dataset (the bank size 27613), BECAT can achieve 2.48% AUC gain (on average) above the famous FSI bascline. On the other two datasets ASSIST and EXAM, the average improvement is only
7

---

Table 1:
The performance of different methods Student Score Prediction with ACC and AUC metrics. "_" indicates the pegrmattionunneetaintt--y selection algorithms (e.g., FSI) cannot be applied to the deep learning method. The boldfaced indicates the statistically significant improvements (p-value < 0.01) over the best baseline.
(a) Performances ASSIST
CDM
IRT
NeuralCDM
Step
ACC/AUCeS
ACC/AUC@10
ACC/AUC@20
ACC/AUCES
ACC/AUC@10
ACCIAUC
Random
71.01/70.68
72.2V/1.91
73.07/2611
71.52/7119
72.66/22.66
72.67/7283
FSI
71.77/71.33
72.94/22.48
73.24/73.54
KL.I
71.93/71.38
72.73/72.52
73.17/73.57
72.2071.54
73.22/73.08
72.36/70.98
72.52/72.33
71.74/12.27
BOBCAT
72.31/71.68
72.3672.28
73.70/73.39
72.69/7148
72.89/7.84
73.87/72.84
NCAT
72.28/71.53
72.55/72.31
73.81/73.50
72.28/71.9
72.63/7.337
73,90/73.59
BECAT
71.92/71.44
73.01/72.73
73.96/73.61
72.30/1160
(b) Performances on NIPS-EDU
NeuralCDM
Step
ACC/AUC@5
ACC/AUC@10
ACC/AUC@20
ACC/AUC@5
ACC/AUC@ 1O
2CC/AUC@20
Random
66.45/69.05
68.23/71.66
70.23/74.82
67.19/69.32
68.44/71.56
70.57/74.99
67.70/70.60
69.62/73.62
71.03/76.24
KLI
67.09/69.79
69.27/73.30
70.42/75.73
MAAT
66.70/70.32
69.13/72.41
69.07/74.46
67.86/70.12
70.07/72.58
70.66/75.83
BOBCAT
69.51/74.42
70.94/75.73
71.73/76.58
71.13/76.00
12.52/77.87
13.47/79.00
NCAT
67.30/72.11
70.68/75.88 80
71.91/76.66
70,47/74,0
72.81/77.99
73.47/79. 12
BECAT
66.98/73.15
7161/75.87
72.00/76.82
71.33/76.30
73,09/78.34
73.58/79.36
(c) Performances on EXAM
CDM
IKT
NeuralCDM
MetrieSStep ACC/AUCES
ACC/AUC@10 10
ACC/AUC@20
ACCIAUCES
ACC/AUC@10
ACCIAUC
Random
77.58/0.334
78.59/71.9 91
80.40/74.22
79.80/72.58
79.80/74.81
79.80/88.40
77.37/70557
78.79/72.21
81.01/74.89
KLI
77.37/70.57
78.79/72.21
81.01/74.70
MAAT
76.97/70.38
78.79/72.12
80.61/74.65
82.82/70.32
82.83/74.11 11
83 83.82/99.44
BOBCAT
80.81/68.11
78.19/81
78.18/79.49
NCAT
80.92/70.72
83.99/2.77
84.02/74.29
82.30/78.77
83.19/81.00
81.53/79.49
BECAT
80.99/70.74
83.85/72.88
84.29/75.00
82.84/78.75
83.22/81.49
84.77/79.70
0.32%. This finding inspires BECAT is more adaptable to practical large-scale testing situations, and can retrieve the most suitable questions from the massive candidate questions. However, it cannot be ignored that the BECAT cannot surpass all other methody the beginning of the exam. For example, on NIPS-EDU dataset, it is about 2.53% behind BOBCAT on ACC@5. This is because the student's response data available in the initial stage of exam is limited, and the data-driven methods (c.g., BOBCAT and NCAT) can be pre-trained on large-scale student response datasets to learn the interaction patterns, thus addressing this cold-start problem [4]. Thus, adapting the proposed explicit algorithm to data-driven frameworks is a very promising future work.
Task 2: Simulation of Ability Estimation. The goal of practical CAT system is to accurately estimate student's ability. We conduct the Simulation of Ability Estimation experiment on the EXAM dataset using the mean square error 0| - loll between the ability estimate 6* and the true ability lg at each step. Figure a) reports the results of different methods on IRT. As the number of questions selected increases, we find that the BECAT method can always achieve much lower estimation errors, especially in the middle stage. Some implicit methods that do not aim estimation accuracy perform better in the initial stage (e.g.. NCAT), but the final accuracy still lags behind BECAT framework. Also, compared with the widely used FSI, the proposed BECAT can reach the same estimation error using up to 20% less questions. On average, it can reach the same estimation accuracy using 15% less questions, which demonstrates its efficiency in ability estimation, i.e., reducing test length.
The Characteristics of the Selected Questions. To gain deeper insights on why BECAT leads to more accurate estimation, take a close look at the characteristics of the selected questions. First, for IRT, we output the difficulty and discrimination parameters the selected questions and draw scatter chart in Figure B). We find that it tends to choose those questions with high discrimination.

---

A/12
FSI
1.2
Difficulty Purameter
0.9
Mean Square Eror 20
KLJ
0.8
MAAT
0.7
FSI
KLJI
BOBCAT
64
NCAT
NCAT
04
82
BECAT
BECAT
FSt
KLI
MAAT
BOBCAT
NCAT
BECAT
0.3
Test Step
Discrimination Parameter
(a)
(b)
Figure 3: (a) The error of ability estimation on EXAM dataset. (b) The characteristics (i.e., discrim- ination and difficulty) of the questions selected for 10 students IRT, where grey dots represent all the questions in the bank, and the ** represent the ones selected by BECAT. (c) The Jaccard similarity coefficient of the selected questions.
and their difficulty is scattered and roughly concentrated the middle difficulty area, which may be caused by the fact that most of the students of middle-ability [42). Second, for NeuralCDM, to gain a better insight into the knowledge concepts (e.g., Geometry in mathematics) covered by the selected questions, and the association between BECAT and other methods. Figure e)) shows the Jaccard similarity coefficient of questions' concepts. Questions selected by the same type of method have a high overlap knowledge concepts, such as FSI and KLI, BOBCAT and NCAT. MAAT and FSI have the highest similarity scores with BECAT: 1) Although BECAT does not directly adopt the concept features in the selection, has high score to MAAT that directly targets knowledge concept coverage/diversity. thus making the measurement more comprehensive. 2) The high similarity (with FSI) proves that BECAT is not only general but also capable of selecting informative items.
5 Related Works
Computerized Adaptive Testing Computerized Adaptive Testing (CAT) technology has been widely used in many standardized tests, such as GMAT, and the multistage testing in GRE also its special case of CAT [17]. J. It is an iterative procedure, mainly including Item Response Theory and question selection algorithm. The following reviews these two components separately:
(I) Item Response Theory (IRT). It is built on psychometric theory and has become popular in educational assessment provide more individualized feedback about a student's latent ability
43 [44) It assumes that the examinee's s ability is unchanged throughout a test, thus the ability can estimated using his/her previous response on questions in gradient- based optimization (32). The classic form is the two-parameter logistic (2PL): p(the response to question j is correct) = represent each question's discrimination and difficulty respectively that are pre-calibrated before testing [29), and 0 E IR is student's 's ability to be estimated. Recently, many studies (36 45 46 combine cognitive diagnosis and utilize neural networks model
sigmoid(a,,( (0 6,)). where aj. by
such student-queet qqestion interaction (e.g., NeuralCDM [36)).
(2) Selection Algorithms. The selection algorithm is the core component realize CAT's adaptivity accurately estimating student's s ability with the fewest test steps. Traditional algorithms are based on some uncertainty or information metrics, e.g., the famous Fisher Information (FSI). Based on many have been proposed to introduce additional information in selection. Since they are not general and not applicable to recent neural network methods, MAAT 9 uses active learning to select diverse and representative items in question's 's feature space. Recently, BOBCAT [12] and NCAT [K regard CAT Reinforcement Learning (RL) problem and train selection algorithms directly from scage student response data. Due to the unknown of the fg. their goal to minimize the student performance prediction loss of the estimate on the held-out responses data, which is also implicit and prone to biases in training data. In this paper, BECAT is general and explicitly targets the accuracy and efficiency of ability estimation. Compared with previous implicit methods, we find that it exhibits superior performance both theoretically and experimentally. However, various biases, such as those introduced test item design and respondent pool selection, affect the validity of estimating student's 's true ability [50]. While our approach seeks to improve
methods 88 47 48 49

---

the efficiency with which student ability is estimated, it does not diminish the need for test designers mitigate sources of bias introduced outside of the model fitting process.
Data Efficiency. Another closely related literature is data efficiency (or data summary) [1 15
52 To alleviate various costs (computational [53] [4] or labeling costs [40]), data efficiency
is used to carefully select generate some samples from dataset on par with the full data. Its
specific implementation methods include Coreset [5 21 16 20), Active Learning 40 55 56]. Data Distillation [57]], etc. For example, recent Coreset approaches [15] 21 20] try to find a subset that closely approximates the full gradient, i.e., the sum of the gradients of the whole training samples. In this paper, Coreset helps transform optimization problem in Section 2.2 but the gradient calculation requires labels, which obviously not applicable to the CAT scenario (student's 's response labels cannot be obtained before the question selection). Therefore, expected gradient difference approximation method and provide good upper-bound guarantees to the optimal solution, which is one of the main contributions of this paper.
improve it and design an
Conclusion
This paper focuses on the explicit approach for accurate and efficient estimation of student's true ability Og- Given that the ground truth 0p unavailable, we find its theoretical approximation: the ability estimated by the full responses to the question bank, and use it as the optimization goal to design Bounded Ability Estimation CAT framework (BECAT). For practical use in CAT scenario, propose simple but effective expected gradient difference approximation in the greedy selection algorithm. We further analyze its theoretical properties and prove the error upper-bound of the ability estimation questions found by BECAT. Through extensive experiments three real- world education datasets, we demonstrate that BECAT can achieve the best estimation accuracy and outperform existing CAT methods reducing test length.
Acknowledgments and Disclosure of Funding
This research was partially supported by grants from the National Key Research and Development Program of China (No. 20219FF0901003 the National Natural Science Foundation of China (Grants No. U20A20229, No. 62106244), and UC Berkeley MicroGrant from the Vice Provost of Undergraduate Education.
References
[1] Zachary A Pardos. Big data in education and the models that love them. Current opinion in behavioral sciences, 18:107-113 2017.
[2] Jill-Jénn Vie, Fabrice Popineau, Éric Bruillard, and Yolaine Bourda. A review of recent advances in adaptive assessment. Learning analytics: fundaments, applications, and trends, pages 113-142, 2017.
[3] Wim Van der Linden and Peter Pashley. Item selection and ability estimation in adaptive testing. In Computerized adaptive testing: Theory and practice pages 1-25. Springer 2000.
[4] Andrew S Lan, Andrew E Waters, Christoph Studer, and Richard G Baraniuk. Sparse factor analysis for learning and content analytics. Journal of Machine Learning Research (JMLR), 2014.
[5] Wynne Harlen. The Assessment of Scientific Literacy the OECD/PISA Project, pages 49-60. Springer Netherlands, Dordrecht, 2001.
[6] Zheng Zhang, Qi Liu, Hao liang, Fei Wang. Yan Zhuang, Le Wu, Weibo Gao, and Enhong Chen. Fairlisa: Fair user modeling with limited sensitive attributes information. Advances in Neural Information Processing Systems, 2023.
[7] Frederic M Lord, Applications of item response theory to practical testing problems. Routledge, 2012.
10

---

[8] Hua-Hua Chang and Zhiliang Ying. A global information approach to computerized adaptive testing. Applied Psychological Measurement, 20(3)211-229, 1996.
[9] Haoyang Bi, Haiping Ma, Zhenya Huang, Yu Yin, Qi Liu, Enhong Chen, Yu Su, and Shijin Wang. Quality meets diversity: A model-agnostic framework for computerized adaptive testing. In 2020 IEEE International Conference on Data Mining (ICDM), pages 42-51. IEEE, 2020.
[10] Darkhan Nurakhmetov. Reinforcement learning applied to adaptive classification testing. In Theoretical and Practical Advances in Computer-base Educational Measurement, pages 325-336. Springer, Cham, 2019.
[11] Xiao Li, Hanchen Xu, Jinming Zhang, and Hua-hua Chang. Deep reinforcement learning for adaptive learning systems. arXiv preprint arXiv:2004.084/1 08400, 2020.
[12] Aritra Ghosh and Andrew Lan. Bobeat: Bilevel ciliiization-based computerized adaptive testing. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelli- gence, IJCAI-21, pages 2410-2417. International Joint Conferences on Artificial Intelligence Organization, 2021.
[13] Yan Zhuang, Qi Liu, Zhenya Huang, Zhi Li, Shuanghong Shen, and Haiping Ma. Fully adaptive framework:
Neural computerized adaptive testing for online education. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4):473444742, Jun. 2022.
[14] Dan Feldman. Introduction to core-sets: updated survey. CoRR, abs/2011.09384, 2020.
[15] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In Proceedings of the 37th International Conference on Machine Learning, (0. JMLR.org, 2020.
[16] Zixiu Wang, Yiwen Guo, and Hu Ding. Robust and fully-dynamic coreset for continuous-and- bounded learning (with outliers) problems. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14319-14331. Curran Associates, Inc., 2021.
[17] Hua-Hus Chang. Psychometrics behind computerized adaptive testing. Psychometrika, 80(1):1- 20, 2015,
[18) Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157 1994.
[19] Rainer Gemulla, Erik Nijkamp, Peter J. Haas, and Yannis Sismanis. Large-scale matrix factorization with distributed stochastic gradient descent. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '11, page 69-77. New York, NY. USA, 2011. Association for Computing Machinery.
[20] Omead Pooladzandi, David Davini, and Baharan Mirzasoleiman. Adaptive second order coresets for data-cfficient machine learning. In Kamalika Chaudhuri. Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 17848-17888 17869. PMLR, 17-23 Jul 2022.
[21] Krishnateja Killamsetty, Durga S, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad- match:
Gradient matching based data subset selection for efficient deep model training. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5464-5474. PMLR, 18-24 Jul 2021.
[22] H. Lin, J. Bilmes, and S. Xie. Graph-based submodular selection for extractive summarization. In IEEE Automatic Speech Recognition and Understanding Workshop. 2009.
[23] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submod- ular maximization: Data summarization with privacy and fairness constraints. International conference machine learning, pages 2544-2553. PMLR, 2018.

---

[24] Sheng-jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples. In J. Lafferty, C. Williams, J. Shawe-Taylor, Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
[25] Zheng Wang and Jieping Ye. Querying discriminative and representative samples for batch mode active learning. ACM Truns. Knowl. Discov. Data, 9(3), feb 2015.
[26] Christos Boutsidis, Petros Drineas, and Michael W Mahoney. Unsupervised feature selection for the k-means clustering problem. In Y. Bengio, D. Schuurmans, Lafferty, C. Williams, and A. Culotta, editors, Advunces in Neural Information Processing Systems, volume 22, Curran Associates, Inc., 2009.
[27] Qi Liu, Biao Xiang, Enhong Chen, Hui Xiong, Fangshuang Tang, and Jeffrey Xu Yu. Influence maximization over large-scale social networks: A bounded linear approach. In Proceedings of the 23rd ACM international conference on conference on information and knowledge manage- ment, pages 171-180, 2014.
[28] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of approximations for maximizing submodular set functions. CORE Discussion Papers RP, 1978.
[29] Susan E Embretson and Steven P Reise. Item response theory. Psychology Press, 2013.
[30] Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In
J. Stoer, editor, Optimization Techniques, pages 344-243, Berlin, Heidelberg, 1978. Springer Berlin Heidelberg.
[31] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '07, page 420 429, New York, NY, USA, 2007. Association for Computing Machinery.
[32] Yan Zhuang, Qi Liu, Zhenya Huang. Zhi Li, Binbin Jin, Haoyang Bi, Enhong Chen, and Shijin Wang. A robust computerized adaptive testing approach in educational question retrieval. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '22, page 416-426, New York, NY, USA, 2022. Association for Computing Machinery.
[33] Qi Liu, Zhenya Huang, Yu Yin. Enhong Chen, Hui Xiong, Yu Su, and Guoping Hu. Ekt: Exercise-aware knowledge tracing for student performance prediction. IEEE Transactions on Knowledge and Data Engineering, 33(1):100-111 2019.
[34] Zachary A Pardos. Ryan SJD Baker, Maria OCZ San Pedro. Sujith M Gowda, and Supreeth M Gowda. Affective states and state tests: Investigating how affect throughout the school year predicts end of year learning outcomes. In Proceedings of the third international conference on learning analytics and knowledge, pages 117-124, 2013.
[35] Zichao Wang, Angus Lamb, Evgeny Saveliev, Pashmina Cameron, Yordan Zaykov, José Miguel Hernandez-Lobato, Richard E Turner, Richard G Baraniuk, Craig Barton, Simon Peyton Jones, Simon Woodhead, and Cheng Zhang. Diagnostic questions: The neurips 2020 education challenge. arXiv preprint arXiv:2007. /2061, 2020.
[36] Fei Wang, Qi Liu, Enhong Chen, Zhenya Huang, Yuying Chen, Yu Yin, Zai Huang, and Shijin Wang. Neural cognitive diagnosis for intelligent education systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6153-6161, 2020.
[37] Mark D. Reckase. Multidimensional Item Response Theory Models, pages 79-112. Springer New York, New York, NY, 2009.
[38] Andreas Tscher. Collaborative filtering applied to educational data mining. Journal of Machine Learning Research, 2010.
[39] Michel C. Desmarais. Mapping question items to skills with non-negative matrix factorization.
SIGKDD Explor. Newsl,, 13(2):30-36, may 2012.
12

---

[40] Anita Krishnakumar. Active learning literature survey. 07 2007.
[41] Maksims Volkovs, Guangwei Yu, and Tomi Poutanen. Dropoutnet: Addressing cold start in recommender systems. In Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[42] Ucik Fitri Handayani, Cholis Sa' dijah, Sisworo Sisworo, Mukhtamilatus Sa diyah, and Lathiful Anwar. Mathematical creative thinking skill of middle-ability students in solving contextual problems. volume 2215, page 060007, 04 2020.
[43] Zhemin Zhu, David Arthur, and Hua-Hua Chang. new person-fit method based on machine learning in cdm in education. British Journal of Mathematical and Statistical Psychology, 75(3):616-66 637, 2022.
[44] Duc Nguyen and Anderson Ye Zhang. A spectral approach to item response theory. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 38818 8-38830. Curran Associates, Inc., 2022.
[45] Xinping Wang, Caidie Huang, Jinfang Cai, and Liangyu Chen. Using knowledge concept aggregation towards accurate cognitive diagnosis. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2010-2019, 2021.
[46] Weibo Gao. Qi Liu, Zhenya Huang, Yu Yin, Haoyang Bi, Mu-Chun Wang, Jianhui Ma, Shijin Wang, and Yu Su. Red: Relation map driven cognitive diagnosis for intelligent education systems. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 501-510, 2021.
[47] Lawrence M Rudner. An examination meeting of the American Educational Research Association, 2002.
-heeory adaptive testing procedures. annual
[48] Wim van der Linden. Bayesian item selection criteria for adaptive testing. Psychometrika, 63(2):201-216, 1998.
[49] Wim JJ Veerkamp and Martijn PF Berger. Some new item selection criteria for adaptive testing. Journal of Educational and Behavioral Statistics, 22(2):203-226, 1997.
[50] Ronald L Flaugher. The many definitions of test bias. American Psychologist, 33(7):671, 1978.
[51] Amina Adadi. A survey on data-efficient algorithms in big data era. Journal of Big Data, 8(1):24, Jan 2021.
[52] Baharan Mirzasoleiman, Kaidi Cao, and Jure Leskovec. Coresets for robust training of deep neural networks against noisy labels. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1 1445--11477 Curran Associates, Inc., 2020.
[53] Sariel Paled and Soham Mazumdar. On coresets for k-means and k-median clustering, In Proceedings of the Thirty-Sixie Annual ACM Symposium on Theory of Computing, STOC '04, page 291-300 New York, NY, USA, 2004, Association for Computing Machinery.
[54] Hongbin Pei, Yang, Jiming Liu, and Kevin Chen-Chuan Chang. Active surveillance via group sparse bayesian learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1313)1133-1118. 2022.
[55] Yi-Fan Yan, Sheng-Jun Huang, Shaoyi Chen, Meng Liao, and Jin Xu. Active learning with query generation for cost-effective text classification. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04))6583-659) 6590, Apr. 2020.
[56) Wenbin Cai, Yexun Zhang. Ya Zhang, Siyuan Zhou, Wenquan Wang, Zhuoxiang Chen, and Chris Ding. Active learning for classification with maximum model change. ACM Trans. Inf. Syst., 36(2), aug 2017.
13

---

[57] Tongzhou Wang, Jun- Yan Zhu, Antonio Torralba, and Alexei A. Efros, Dataset distillation, 2018.
[58] Angelia Nedić and Dimitri Bertsekas. Convergence rate of incremental subgradient algorithms. In Stochastic optimization: algorithms and applications, pages 223-264. Springer, 2001.
[59] George B Arfken and Hans J Weber. Mathematical methods for physicists, 1999.
[60] Satoru Fujishige. Submodular systems and related topics. In Mathematical Programming Oberwolfach 11, pages 1 113-131. Springer, 1984.
[61] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
[62] Andrew P Bradley, The use of the area under the roc curve in the evaluation machine learning algorithms. Pattern recognition, 30(7):1 1997.
[63] Ying Cheng. When cognitive diagnosis meets computerized adaptive testing: Cd-cat. Psy- chometrika, 74(4):619-632, 2009.
14

---

A Proofs of Lemma
We first proof the following Lemma
Lemma 1, When we replace the original gradient difference in w(i.j) with w(t,j). the correspond- ing designed selection algorithm using submodular function is actually approximately solving the following optimization problem:
min max Ey [S] GEB
Σ 79 V4,
(13)
Proof. Following the theoretical analysis the recent Coreset method CRAIG [5]. we first define mapping function h from to to mapping function:Vi E Q2 S. It assign every response data point E Q to one of the elements j in S. Then, for any arbitrary ability parameter 0 E θ we can write
V4(0)= Σ (4) (0) + (l)()(00)
(14)
E
Σ [V)(0) VlA( + Σ V))
(15)
xEQ
jES
Subtracting and taking the expected norm of the both sides, we get an upper bound on the error. According to the triangle inequality, have
E
VI((0) IEQ
E
E [[VI(()) (h (0)]]- iEQ
(16)
When the mapping function h is to map each element in Q to the one in S that is closest to its expected gradient, the right side of incquality (16) minimized, or minimum expected distance
between the gradient: h(i) arg minjes E (0)) (l,(0) Therefore, the upper bound of the expected gradient difference can further constrained:
min [8 1T
Σ (L( EI,
min E (I (1, JES
(17)
IEQ
iES
:EQ
Next, define a similarity function ((i,j) which measures the expected gradient similarity between response pair and j: j) d maxæge E (0) (l)(. and d maxieq (0) (0) is the maximum pairwise gradient distance. Thus, the
optimization problem (Eq. (3)) can also be transformed as:
max IS =T
max ((i.j). Σ
(18)
JES
TEQ
Following the same way of origin problem, its corresponding submodular F(S) Eieq maXjes W(i,j), which is the same with our proposed method. Thus, the designed selec- tion algorithm the greedy algorithm the optimization problem (Eq.
B Proofs of Theorem
Theorem (Expected estimation error bound). Assume that the loss function for ability estimation is a-sttoogly convex (e.g.. IRT). Let S be weighted subset obtained by the proposed method. Then with learning rate 3. ability estimation in gradient descent applied to the subsets has the following expected estimation error bound:
2eDa + o7 + 20 DaH (0",
E [||00+1 0-122 <
(19)
a²
where Hp = B(gn))-o
(20)
Po- (g.
15

---

where 0t is the optimal estimate using full responses, a is an upper bound on the norm of the gradients, and D maNg ||0
8-
Proof. We now provide the expected estimation error bound for strongly convex functions building Let g¹ @ Σieq (L, Is Σ iES 7: (O"),, and normalize the
on the analysis of I5 58
subset weights at every iteration i.c., EEeS 7/- = 1. Let L(0) = Eies (0( be the weighted subset
training loss parameterized by ability parameters 0, and we have:
||@r+1
1²1 = 10 ng's 1¹11
10 8'1 2n(gs) T (6' - 8¹) + 1'''2'
S 10 0r 1/2 2n(L(0") - L(0*)] + +/11''111
10 0- 112 2n (03)) (0' 0*) + =0100 0-113)
+ 17 "1'ss (a strongly convex).
(21)
According to Sauchy-Schwarz inequality, have
((g5) (0' 0¹) S || 11
(22)
Thus
100 - 0-11 1 102 21 + 2n [llo3 I1| 001] nall00 0-1 112 + 17 11ss1
(23)
Taking expectation with respect to the randomness in the label (i.e., the correctness of response) decided by 8%, we have
[110++1 - [1]] s (1 7) E |1 - 0-]
+ 2yyE [| - 0']]] + 1 [|gss] 1²]
(24)
Assuming gradients have a bounded norm triangle inequality, we can write
[[]}(0)]| S oz and (f) S ay.- Thus, from reverse
E
[1os [7] =
| V(,(0011 oo
(25)
JES
From Lemma I we can assume that the subset S and corresponding per-element weights Yj can approximate the full gradient with an expected error at most e > 0, i...
Eyspor [I] EiEQ V4(0)= Eies 7, [I,(0)] S 6. Thus, from reverse triangle inequality B[[la] s ElllgI||| + and E|| [[]lg\1]]] can be further derived as follows:
B[lgg
E
S
Σ
((
[Q|
Q
iEQ
EEQ
E ty Pige
11 (-y, ys In fi( - (1 - y) In - f((0)))
QQ]
iEQ
||- - Vi
VS((0*) + 1 ys
E Byg-Poo
Q
Ji(0-)
f:(())
SEQ
f+(00))
Vi
1 -
fi(00)
1 fa(0~)
Σ
Po (giz y/3 = 8)
Q
Pa- (4i, Di = 31)
IEQ
Vf((0))) (gt.
Q
Po- (g:. v1.
S S0yBlax)>po
(26)
ppo- (g.v)
16

---

where Pe(g. y) is the response distribution of the student with the ability 6, and f((0) po(a, y: = 1)
the output of IRT. Also assuming that ||0 8* D, we have,
E [I ||0
00 II]
DElllg II] +]++6 cD
5 DE Dat
+
(27)
Po- (q.
Combining the Equation
24 26 and let 1j we have
2e Dax + of 20, B (
E [1 0r [|a]
a²
a
po- v)
2r Da + of DoH 10' 6*)
(28)
a²
where Hp(6".0% 8*) Bla [oo (orl
So we complete the proof.
C Proofs of Theorem 2
Theorem 2. Assume that 0r, estimated by the cross-entropy loss, can minimize the empirical risk i.e.
Eies, 41(0) = 0. Then Hp (,00) can take its minimum when 0 = 0", that is
Hp 0-) < H₂(0,0"), 4
(29)
Proof. When we use the binary cross-entropy (BCE) loss to estimate the ability and minimize the empirical risk at step ł, we have
0t arg min ((()
iES.
arg max
y/ log (((() + (1 y/) log(11 f((0))
iES;
arg max
log pe 9:)
iES:
2 arg max E (g.))~po log (g.
(30)
where f:(0) pa(gi, V/s 1) is the output of the IRT. We argue that the student's response to the question q is determined by the ability Og in the CAT process, i.e., yi arg max,, Pe, (gi, y). Therefore, when the above empirical risk achieves its minimum, i.e., Eies, ((*) = 0. ((g.))~pa log.lloPpooe Pe(g,, (:) y1) can reach the maximum O, and the real and predicted responses are the same:
Ymaz arg max po (4. v) arg max Po, Po, (q. v). Vq
(31)
and the predicted probability should approache 1: Po (q. yman) - 1.
Next, we discuss the minimization of the statistical distance H0' -0)) E pp [1/p-- (g. y)] term in the upper bound in Theorem [ In general, make now the simplifying assumption that distribution pa- (4, y) is smooth and has a global maximum probability Pmax. attained at a point (g, Mmaz) for question g, so that pppe- (g, u) has a global minimum the same Umaz- Obviously, can choose:
Po (q. v) d(y Mmax))
(32)
where 5 is the delta function [59], making ((g.))<oor [1/pe- (g. v)] to its minimum. Based on the above findings, in the CAT situation (binary classification), the optimal distribution pa. (minimizing the Hp in the upper bound) needs to: have the same classification result as Pg-, i.e., Ymaz arg maxy po (4, y) = arg maxy Po- (q, y) As arg max,, Pa, (g. y) and its corresponding probability is as large as possible, i.e., pos (q, Umaz) + 1. In this case, (, 0*) can takes its minimum. All of these findings are consistent with the conclusion that minimizing BCE loss for ability estimation in
Eq)30) and 31 So complete the proof.
17

---

max BEG,
/axx|v,,(0) - v1,
(1(
V4((0)
0f
0
0
Figure 4: The illustration of the distance measurements in similarity function iiii replace the entire ability space with the student's 's possible ability estimates θ2 = { 1 to reduce search space and speed up the selection.
D Implementation Details of BECAT
To improve its complexity, we provide two implementation tricks:
(1) Lazy Evaluations. By exploiting the submodularity, presented in [1] to speed up the selection process and make the running time faster in practice. At step f, the greedy selection algorithm must identify the question with maximum marginal gain ( Instead, this lazy method involves using a max-heap (O(1) lookup and (llog(n) insertion) to keep upper bound the gain of each question that comes from submodularity. i.e., the marginal benefits of any question E Q are monotonically nonincreasing during the selection:
the lazy evaluations approach
A (glS.-1) > A(q)S.) Vq E Q.
(33)
Instead of recomputing S1-) at each step for each element Q (requiring O(IQ)) compu- tations), the accelerated lazy algorithm maintains a list of upper bounds A' (initialized to oo) on the marginal gains sorted in decreasing order (max-heap order). Specifically, algorithm first selects the maximal from this ordered list, i.e., the top of the heap. It then updates this bound (q) + ((q)S-11) in the heap. As soon the A'(q) is still the top the heap, then submodularity Eq. (33) guarantees that ((1 2 (gg' Ss-1) for all d' # q, and therefore we do need evaluate any more items. If it does not satisfy this condition, we just insert it with A as the new upper bound and repeat the above procedure until the qualified question is selected. While the worst case the same, practice this method has enormous speedups over the standard greedy algorithm [60].
each step, the
(2) Reducing the Ability Space θ In our method, note that the similarity function (i. d maxØge Egy=p, (0) (O) requires finding the worst case over the entire ability parameter space θ, which too expensive for CAT systems. In fact, it only needs be calculated in each student's 's own possible ability space. In other words, we can find an ability subspace θ C O specialized to each student. We utilize novel MLE-based estimation approach [32], which models student's ' multifaceted nature and sequentially generates a set of possible abilities O = {0) at each step t:
0 = arg min 0,
Σ 4(0,) iES.
A - 110 -.11" for = 1...,, m.
(34)
where 0; is the average of previous i - estimates and the term ||,--0.| ensures the diversity of
abilities in {0t) ==1- 1- We refer the reader to [32 for more details about this estimation method. As
shown in Figure we replace the entire parameter space in the optimization problem with student's m
potential estimates O {0
The complexity can be reduced to O([Qi²m) and m << [0]. O
E Details of Experiment
The impact test length. We use simulation experiments to verify the choice of max length T: Due to the unknown of the true ability Op. artificially generate it and conduct the Simulation
18

---

Random
Mean Square Error (MSE)
14
Fisher
0.4
20
40
60
50 100
Test Step
Figure 5: Simulation experiments of ability estimation using MSE: E[] - -
of Ability Estimation experiment on the EXAM dataset using the mean square error Eil 0, l between the ability estimate I' at each step and the true ability 6g (Figure 5): The classic Fisher method can reduce the evaluation error quickly and is sufficient for the length of a typical adaptive test. Thus, we fix the max length T 20.
Experimental Implementation Details. As 20 sufficient for the length of typical test we also fix the max length 7' 20. We implement all the methods with PyTorch. We set batch size to 64 and the learning rate to 0.001, and optimize all the parameters using the Adam algorithm [6] on Tesla 2100-SXM2-32G1 GPU.
E.1 Statistics of the datasets
Table 2: Statistics the datasets
Dataset
ASSIST NIPS-EDU
EXAM
#Students
20,704
220,274
9,214
#Questions
15,071
27,613
1,650
#Response logs
1,768,253
19,181,192
133,398
#Response logs student
85.41
87.08
14.48
#Response logs per question
117.33
694.64
80.85
E.2 Detailed Evaluation Method
The goal of CAT is to estimate the student's s ability accurately with the fewest steps. However, since the true ability cannot be obtained as the ground truth, there are usually two tasks to verify the performance different CAT methods following previous works 9 12]: 1) Student Score Prediction and 2) Simulation of Ability Estimation:
Student Score Prediction. To evaluate the ability estimate output by the CAT system, this estimate can be used for predicting the student's scores (correct or wrong) on the questions he/she has answered in the held-out response data. This is an indirect evaluation method. Following the common strategy [12), we use 20%-10% students for training, validation, and testing respectively, and won't appear in training. The training set used for initializing some question's 's parameters in IRT (e.g., difficulty parameter in IRT), and the data-driven selection algorithm baselines (e.g., BOBCAT). the validation/testing, the responses of each student i are further divided into the candidate (Q:) and meta (M, question sets to simulate CAT procedure, following 12 Specifically, at each step, (1) different selection algorithms first select a question from Q:: (2) IRT then updates the ability estimate with his/her response to it; (3) evaluate this estimate's accuracy by predicting binary-valued responses (correct or wrong) on the held-out meta
the students validation/testing
set M. This task assumes that the more accurate the score prediction is, the more accurate the ability
19

---

20
MAAT
KI.I
BECAT w/ speedups
15-
BECAT w/o specdups
Time (sec)
10
Test Step
Figure 6: Comparison of the time consumed by different methods at the selection step. The imple- mentation tricks provide 2x to 3x speedup.
estimate is. This task considers that the accuracy score prediction can reflect the accuracy this ability estimates. Thus, from this binary classification perspective, we use Prediction Accuracy (ACC) 46 and Area Under ROC Curve (AUC) 622 for the evaluation of different selection algorithms.
2) Simulation of Ability Estimation. This is CAT's traditional evaluation method (2 Since the ground truth of student ability On not available, artificially generate their Og and further simulate student-quest qudeent-quesionn interaction process within CAT systems. For the rationality of the generated fg. we use all the students' responses in the dataset to estimate their ability {0}, 02 .... 0g as the ground truth 19 633 Also, the dataset is used to learn questions' parameters and fix them. Different from the first task, such settings can simulate students with On responding to any question in Q, thus the candidate question in selection is the entire bank Q. Specifically, (1) different selection algorithms first select a question from the entire bank Q: (2) IRT then updates the estimate with the response to it; (3) evaluate this estimate's 's accuracy by computing the difference between the estimated and the true ability. In this way, we can use Mean Square Error (MSE) evaluate the accuracy of estimation.
E.3 Implementation Tricks for Speedups
To solve the BECAT optimization problem, we need to calculate the gradients of all items in question bank, leading high computation requirements for large datasets/examiiations.. To this end, we consider two speed-up tricks: lazy evaluations and multifaceted estimation. Lazy evaluations take advantage of submodularity to avoid calculating the conditional gain Agq|S,-1 of all the candidate items. The multifaceted estimation method (32) can effectively reduce the ability space when calculating the similarity between two items, thus reducing the time to calculate (gg[S,-1) of each item. In Figure 6 we compare the time (second) spent on question selection by different methods and find that the proposed implement tricks give the average speedup xx, and achieve x to recent MAAT. And it is almost the same time as the traditional informativeness-base method KLI. This demonstrates that our greedy selection algorithm BECAT fast in practice.
E.4 BECAT Analysis
In this section, we will further analyze its selection time/latency, the effectiveness of Theorem and and the characteristics of questions selected by BECAT, respectively.
Upper Bound Analysis of Estimation In Theorem [ the most important component is H, 0*), which determines the upper bound on estimation error and the convergence behavior of the proposed BECAT method. Therefore, to verify the effectiveness and theoretical guarantees of our explicit selection algorithm, i.c., the estimation error bound conclusion in Theorem we compute H,, for each step the strongly convex loss function: the cross-entropy loss of the L2-regularized IRT. This experiment is still based on the simulation setting in Appendix E.2 and the results are shown in
'There is no comparison here of reinforcement learning methods, due to the extra training overhead they require.
20

---

0.193
Normalized Gradiem Difference
25000
0.188
20000
Hg 0*)
15000
BECKT KL1 BOBCAT
5000
0.178
RAND
20
Test Step
Test Step
(a)
(b)
Figure 7:
(a) The value of (0", )*) in the upper-bound of estimation. (b) Normed difference
between the full gradient on [ and the gradient of the question subset found by different methods.
In the first few steps, the H, 8*) can rapidly decrease to the minimum. the test progresses, the ability estimate tends to be accurate (Figure (a)), and the upper-bound Hp remains near the minimum, which reflects the good convergence behavior of BECAT. This demonstrates that our expected gradient difference approximation is reliable in practice.
Figure a):
Gradient Approximation. In Proposition 1 we show that f an approximation of student true ability. To approach the new target 0", an approximation to the full gradient of the bank Q is required. Figure demonstrates the norm the difference between the weighted gradient of the questions subset found by BECAT and the full gradient. This figure also compares the normed gradient difference of other subsets found by other methods where each response is weighted by QQI/SS] The gradient difference is calculated by sampling the full gradient at various points in the parameter space. Note that the gradient difference obtained by BECAT decreases significantly with the increase of t and it is much smaller than that of other methods, which proves that the expected gradient difference approximation method is accurate. Combining the experimental results on the two tasks in Experiments, the better the prediction/estimation performance of the method, the smaller the gradient difference. This demonstrates that the closeness to l" reflects the closeness to the true target.
ability lg which further proves the rationality of using 6*
21

---

Table 3: The variance results of different methods on ACC and AUC metrics.
(a) Variance results on ASSIST
CDM
IRT
NeuralCDM
Metric@Steep
AUC#
ACC/ 10C@10
ACC/ AUC#20
ACC/
ACC/ AUC
AUCE200
Random
0,0378/ 0.0462
0.0090/ 0.0226
0.0052 0.0142
0.0064/0.00
0.0042
0.0012
FSI
0,0446/ / 0.0257
0.0147 /0.0076
0.0066 0.0024
KLI
0.0163/ / 0,0058
0,0042/ 0.0037
0.0023 0.0019
MAAT
0.0121 / 0.0202
0.0082 0.0155
0.0162 0.0286
0.0123
0.0073
0.0083 0.0276
0.0253 0.0242
BOBCAT
0.0120/0
0.0057
0.0148
0.0054
/0.0066
0.0023
NCAT
0,0063 0.004]
0.0065 0.0055
0.0012/ 0.0007
0.0032 00.0031
0.0037 0.0029
0.0035 / 0.0020
BECAT
0.0100/0.0136
0.0062 0.0000
0.0055 0.0023
0.0022 0.0002
0.0019 0.0001
0.0012 / 0.0010
(b) Variance results on NIPS-ED EDU
CDM
IRT
NeuralCDM
Metrie@Step
ACC/AUCOR
ACC/AUC&
ACC/ AUC@20
ACC/AUC@S
ACC/ AUC@10
ACC/ AUC/0
Random
0.0185/ / 0.0406
0.0183 00.033000431
0.0182 0.0478
0.0185/0.008
0.0183/000431
0.0182 /0.0488
FSI
0.0270/ / 0.0350
0.0269 / 0.0357
0.0274 0.0401
KL.I
0.0231 / 0.0335
0.0218 0.0278
0.0196 0.0247
MAAT
0.0207 0.0347
0.0377
0.0256 0.0412
0.0192 /0.0298
0.0216 0.0306
0.0253 0.0363
BOBCAT
0,0203/ / 0.0311
0.0185 0.0267
0.0169 0.0247
0.0197
0.0315
0.0190 0.0289
0.0200 / 0.0310
NCAT
0.0178/ / 0.0246
0.01.5 0.0214
0.0142 / 0.0198
0.0176
010258
0.0163 / 0.0232
0.0169 / 0.0246
BECAT
0.0216/0.0294
0,0185 / 0.0248
0.0169 0.0225
0.0204 / 0,0304
0.0167 / 0.0251
0.0165 / 0.0225
Variance results EXAM
CDM
IRT
NeuralCDM
Metric@Step
ACCC AUCWS
ACC/ AUC/O
ACC/ AUC#20
ACC/ AUC#10
ACC/ ACC/AU@#20
Random
0.0171 0.0088
0.0114/ 0.013
0.0084 / 0.0086
0.0025 /0.0107
0.0071 /0.0102
0.0070 / 0.0090
FSI
0.0195 /0.01
0.0097
/0.099
0.0093 0.0069
KLI
0.0195/ 0.0112
0.0097 0.0099
0.0076 0.0098
MAAT
0.0193/ 0.01
0.0104 / 0.0094
0.0082 0.0065
0.0191 00.0112
0.0182 / 0.0099
0.0053 / 0.0062
BOBCAT
0.0036 / 0.0133
0.0070/ 0.0114
0.0086 / 010099
0.0142 / (1.0087
0.0095 / 0.0091
0.0012 / 0.0021
NCAT
0.0033 / 0.0146
0.0005 0.0004
0.0004 0.0004
0.0160 / 0.0120
0.0148 0.0090
0.0003 / 0.0003
BECAT
0.0196/0.00 0.0012
0.0022 0.0006
0.0020 0.0007
0.0172
0.0034
0.0063 0.0012
0.0090 / 0.0029
22


Reviews:
[{"review_id": "95YuhZA1sQ", "reviewer": "Reviewer_aSHy", "summary": "The authors advocate to propose a method to better estimate students ability by using as few questions as possible. They redefine Computer Adaptive Testing(CAT) as a adaptive subset selection of question to estimate students ability and propose a gradient based selection method to select items that minimizes the estimation error term. Through experiment results they show that their proposed method BECAT outperforms existing  CAT method at reducing test length by 10-20%.", "questions": "1. “For accurate and efficient assessment” : how is ground truth “ability” $\\theta_0$ defined mathematically? what is $\\Theta$ set mathematically?\n    \n2. How can the ability be estimated by minimizing the empirical loss? Can the authors provide a concrete example?\n    \n3. In line 82-83, what is “standard” gradient descent and under what ability space $\\Theta$ the gradient descent can minimize empirical risk\n    \n4. The student’s ability is defined to be fixed $\\theta_0$ in line 75, and in line 90 student current ability is said to be $\\theta^t$ which is an evolving parameter through time. How are these two definitions consistent?\n    \n5. “there is no such ground truth $\\theta_0$ in the dataset” what does a parameter being in a dataset even mean?", "limitations": "The cognitive model of student is over simplied.\n\n", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The author study an important problem of how to efficiently estimate the ability of student by adaptively asking them as small number of questions as possible. They propose a gradient based method to solve this problem and their empirical results suggest that their method perform superior to other CAT methods at reducing test length. Empirical results suggest that their method perform superior to other CAT methods at reducing test length.", "weaknesses": "1. The paper is poorly written and is not easy to follow.\n2. Important concepts and definitions like student’s “ability”, model of the student is not well defined. For more details refer to the question section.\n3. Even through the paper studies an important problem, the overall presentation and readability of the paper can be significantly improved. At this point I cannot propose to accept this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We understand that there might be room for improvement in terms of clarity. Regarding the questions you raised, we have carefully considered each point and have made following responses: \n\n> **Q1**: How is ground truth \"ability\" $\\theta_0$  and $\\Theta$ defined mathematically? Student’s “ability”, model of the student is not well defined. \n\n**A1**: In Item Response Theory (IRT), the student's ability parameter $\\theta$ refers to the latent trait being measured. It represents the underlying ability of the student that is not directly observable but influences their performance on the test items [1]. Therefore, $\\theta_0$ is a student's true ability parameter, which can be estimated by student's performance on the test items. As stated in line 36, you can simply think of it as a parameter estimation problem: $\\theta_0$ is the unknown truth value to be estimated, $\\Theta$ is the entire parameter space, and the student's performance is the observation $X$.\n\n> **Q2**: How can the ability be estimated by minimizing the empirical loss? Can the authors provide a concrete example?\n\n**A2**: In Item Response Theory (IRT), the ability of a student can be estimated by minimizing the empirical loss when using a probabilistic model such as the logistic model for binary responses. Minimizing the empirical loss involves finding the ability parameter $\\theta$ that best fits the observed response data [2]. To illustrate with a concrete example (line 300), let's consider a simplified version of the 1-parameter logistic (1PL) IRT model for binary responses. In this model, the probability of a correct response to item $i$ for a student with ability $\\theta$ is given by:\n\n$\nP(\\text{Correct response to item } i) = \\frac{1}{1 + e^{-(\\theta - b_i)}}.\n$\n\nwhere $b_i$ is the difficulty parameter for item $i$ (the ability level at which the item has a 50% chance of being answered correctly). Now, assume we have a dataset with binary responses (0 for incorrect, 1 for correct) for a set of items administered to multiple students. The empirical loss function, such as Binary Cross Entropy (BCE) loss, can be used to estimate the ability parameter $\\theta$. We can use optimization techniques like gradient descent or other numerical methods to find the minimum of the empirical loss function. The estimated $\\theta$ will be the ability parameter that best fits the observed data based on the IRT model.\n\n>  **Q3**: In line 82-83, what is “standard” gradient descent?\n\n**A3**: Standard Gradient Descent, also known as Batch or Deterministic Gradient Descent, is an optimization algorithm that use the **entire** training set. It process all the training examples simultaneously in a large batch [3]. This terminology can be somewhat confusing because the word “batch” is also often used to describe the minibatch used by minibatch stochastic gradient descent. Typically the term “standard/batch gradient descent” implies the use of the full training set, while the use of the term “batch” to describe a group of examples does not. Therefore, to prevent unnecessary misunderstandings caused by \"batch\" to readers, we use \"standard\" instead in this paper.\n\n> **Q4**: Under what ability space $\\Theta$ the gradient descent can minimize empirical risk?\n\n\n\n**A4**: From the perspective of optimization, it is not fundamentally different from general gradient descent problems, as it requires finding an optimal value $\\theta^*$ in the whole parameter space $\\Theta$.\n\n> **Q5**: The student’s ability is defined to be fixed $\\theta_0$ in line 75, and in line 90 student current ability is said to be $\\theta^t$ which is an evolving parameter through time. How are these two definitions consistent?\n\n**A5**: Since students do not receive correctness feedback during the test, the true value of the student's ability, $\\theta_0$, is **constant** and **unchanged** throughout the test. As mentioned in Section 1 of the paper, current ability $\\theta^t$ is an \"estimate\", and CAT needs to sequentially use student responses to keep this estimate $\\theta^t$ close to $\\theta_0$. Therefore, CAT is essentially an \"online\" parameter estimation problem, and our contribution is to design a reasonable question selection strategy for efficient estimation, when the groundtruth $\\theta_0$ is unknown.\n\n> **Q6**: \"there is no such ground truth $\\theta_0$ in the dataset\" what does a parameter being in a dataset even mean?\n\n**A6**: As stated in line 33 of the paper, CAT hopes that the question selection algorithm we designed can select the fewest suitable items to make the ability estimation more accurate. In essence, it is trying to solve the optimization problem in Definition 1: $\\mathop{\\mathrm{min}}\\limits_{|S|=T}\t\\Vert {\\theta^T}-\\theta_0 \\Vert$. However, this optimization problem **cannot** be solved explicitly due to the unknown of ground-truth $\\theta_0$ in the dataset. This is why we use $\\theta^*$ to approximate $\\theta_0$ and reformulate such problem (i.e., Definition 2).\n\n\n> **Q7**: The cognitive model of student is over simplied.\n\n**A7**: In fact, the student model in traditional CAT and psychometrics is such a \"simple\". The most widely used user model in CAT is IRT, which is usually a form of logistic regression. Meanwhile, the cross-entropy loss of the L2-regularized IRT is strongly convex, which is the assumption of Theorem 1. In recent years, more \"complex\" models have emerged, such as NeuralCDM, which uses neural networks to model students. Like optimization theory research, we cannot prove the effectiveness of Theorem on a black-box neural network, so we evaluate it in experiment part.\n\n\n\nReference:\n\n[1] Embretson, Susan E., and Steven P. Reise. Item response theory. Psychology Press, 2013.\n\n[2] Baker, Frank B., and Seock-Ho Kim, eds. Item response theory: Parameter estimation techniques. CRC press, 2004.\n\n[3] Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016."}, {"review_id": "1mcG30keGn", "reviewer": "Reviewer_KCbW", "summary": "This paper investigates the problem of effective question selection in Computerized Adaptive Testing (CAT), with the goal of designing a procedure that minimizes test length while maximizing  estimation accuracy of student ability. While student ability doesn’t have a known ground-truth, they use the student ability estimated using all questions (as opposed to a small subset) as the effective ground truth. To design a short test, they use literature on core set selection to pick a subset of questions that have the same gradient updates as if using the entire question bank.  This scheme is used in some real world experiments, demonstrating gains in shorter test lengths and better estimation accuracy.", "questions": "For the ability estimated by the responses to entire question bank to actually converge to the true ability (as shown by your synthetic experiments in Fig 2.) I believe you need the ability parameter to be static over time. If i remember correctly, the EEDI data is collected over a long period of time, so students likely (hopefully) are learning over time. Is there any way to address this issue?", "limitations": "Right now it sounds like one of the paper’s contributions is the idea of using the entire set of questions to represent the unknown student ability. However, this is something also explored in the BOBCAT paper. I would recommend citing them and carving out your contribution on top of this. For ex. “we are the first to propose a selection algorithm that explicitly targets this full sample estimate”. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "I generally like the results in this paper and I believe the CAT community would find this to be a valuable contribution.\n\n- As far as I am aware, the ideas in this paper are novel. It proposes a simple, computationally inexpensive approach to question selection. The work nicely combines existing literature in diverse areas of AI to solve a well-defined problem.\n\n- The results in this paper are compelling and compared against a thorough set of competitive models from recent literature. The paper’s approach is much more computationally simple than that of these competitors, and seems to empirically outperform them.", "weaknesses": "My biggest critique of this paper has to do with its writing and presentation, which I would say needs a lot of work. While I find the results interesting, the presented methodology is hard to follow and filled with errors and typos. Just a few examples: \n\n- What does the ⇒ in equation 5 mean? This is not a gramatically well-formed mathematical sentence.\n- In equation 5, what is $d$? I don’t think this is defined anywhere\n- In the simulation experiment, the paper simulates student abilities “using the smallest EXAM dataset”. What does that mean exactly? Do you also simulate the question parameters or estimate those first? I think this is explained in appendix E, but very confusing when you just read the main paper. Relatedly, in task 2, do you mean $\\theta^*$ instead of $\\theta_0$ (which is unknown)\n\nRelated to the writing, I found the math exposition in this paper to be extremely difficult to follow. Many of the steps are explained poorly, making them hard to verify (e.g. Lemma 1 in Appendix A).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude for your high appreciation of the contribution and novelty presented in our paper. Your positive feedback means a lot to us. We also appreciate your valuable suggestions regarding the refinement of certain technical aspects in the paper to enhance clarity. Following your advice, we will further emphasize the difference from other literature (e.g., BOBCAT), and on top of it, explicitly highlight our contribution in the paper.\nHere are the responses to each of your questions: \n\n\n> **Q1**: What does the \"$\\Rightarrow$\" in equation 5 mean? This is not a gramatically well-formed mathematical sentence.\n\n**A2**: The \"$\\Rightarrow$\" is used because we cannot directly solve the original problem in Equation 5 and need some approximation to it. For rigor, we use \"$\\Rightarrow$\" to indicate such transformations. Sorry to cause confusion to you, we will change it in the next version.\n\n\n> **Q2**: In equation 5, what is $d$? I don’t think this is defined anywhere.\n\n**A2**: Sorry for missing this definition in the main paper: $d=\\max_{i\\in Q,j\\in S}\\max_{\\theta\\in \\Theta} {\\Vert \\nabla l_i(\\theta) - \\nabla l_{j}(\\theta)\\Vert}$ is the maximum pairwise gradient distance.\n\n> **Q3**: In the simulation experiment, ...\"using the smallest EXAM dataset\". What does that mean exactly? Do you also simulate the question parameters or estimate those first? \n\n**A3**: Since the bank size $|Q|$ can impact Proposition 1 (the larger the $Q$, the better the approximation), we selected the smallest dataset EXAM (with smallest $Q$) to verify this proposition. We use the training set of real data to estimate the item parameters and fix them in the experiments. Due to space limits, we simplify this part in the main paper.\n\n\n> **Q4**: In task 2, do you mean $\\theta^*$ instead of $\\theta_0$ (which is unknown).\n\n**A4**: Task 2 is a simulation experiment, which needs to manually generate some $\\theta_0$s. In order to make these $\\theta_0$s conform to the students' ability distribution, we use all the students' responses in the dataset to estimate their ability $\\{\\theta_0^1,\\theta_0^2, ...,\\theta_0^N\\}$ as the ground truth $\\theta_0$ like [1][2].\n\n> **Q5**: Many of the steps are explained poorly, making them hard to verify (e.g. Lemma 1 in Appendix A).\n\n**A5**: Some steps are skipped is mainly because some of these proof steps (e.g., Lemma 1) are based on the other papers, which have been cited in the proofs. However, the proofs of the Theorem originally proposed in our paper such as Theorem 1 and 2 are detailed. \nThanks for your suggestion, we promise to provide a detailed proof of Lemma 1 in an improved version of the manuscript. (*Detailed proofs of Lemma 1 can now be found in the Global Rebuttal pane, for all reviewers to check.*)\n\n> **Q6**: For the ability estimated by the responses... I believe you need the ability parameter to be static over time. ...so students likely are learning over time. Is there any way to address this issue?\n\n**A6**: In fact, as you said, student abilities that are not static in most public datasets. However, these datasets look like \"session-based\", i.e., the time of response behavior in a session is compact (minutes or hours), and the interval between sessions is large (days or even months). In a session, students' ability will not change much, so a feasible method is: divide a student response sequence into different sections according to the time feature/session, and treat each section as a completely different student. In addition, we collected a student exam dataset EXAM in our paper, which collected the records of junior high school students on mathematical exams. We will make this dataset publicly available after the paper is accepted.\n\n\nReference:\n\n[1] Bi, Haoyang, et al. \"Quality meets diversity: A model-agnostic framework for computerized adaptive testing.\" 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 2020.\n\n[2] Cheng, Ying. \"When cognitive diagnosis meets computerized adaptive testing: CD-CAT.\" Psychometrika 74 (2009): 619-632.\n\n\n\n\n"}, {"review_id": "NxiKZ4nwS5", "reviewer": "Reviewer_TJRB", "summary": "This paper tries to answer a question in computerized adaptive testing: how to select a question suitable for student without knowing the ground-truth of his/her true ability. To this end, the authors find the theoretical approximation of the true ability and provide theoretical and experimental analysis to support their proposition. They further develop an expected gradient difference approximation to design a greedy selection algorithm, successfully bounding the estimation error. Extensive experimental results show the estimation efficiency and accuracy of the method compared with baseline systems.", "questions": "See above.", "limitations": "The limitations are clearly stated in this paper and its supplementary material.  It seems longer to train than traditional methods, but it adopts two speed-up tricks to improve the complexity.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "S1. An explicit question selection algorithm is proposed, which theoretically solves the dilemma that previous work can only approximate the truth ability implicitly. The solution is interesting: it finds a theoretical approximation of the true that is easily overlooked: the ability estimated by full responses to question bank. Moreover, this paper provides a convincing analysis of the plausibility of the approximation, both experimentally and theoretically.\n\nS2. In terms of technical implementation, this paper improves the Coreset methods and propose an expected gradient difference approximation for CAT scenario. The authors further design a simple but effective greedy selection algorithm, and prove the error upper-bound of the ability estimation on questions found by it.\n\nS3. Experiments on both real-world and synthetic datasets, show that it can reach the same estimation accuracy using 15% less questions on average, reducing test length.\n\nS4. This paper is easy to follow. The additional material covers the proof and almost all additional experiments, including the detailed experimental analysis of Theorem in the paper.", "weaknesses": "1. The expected gradient difference approximation proposed in this paper is general in my opinion, and should not be limited to the CAT scenario. The sample selection strategy design or the efficient learning in the parameter estimation scenario seems to be applicable. I suggest the authors to study the effectiveness of the method in more tasks/domains.\n\n2. As stated in the paper: \"BECAT cannot surpass all other methods at the beginning of the exam\". This is a cold start topic in an educational recommendation/testing. The reason is not explained in detail. Why the proposed method cannot surpass the RL/Meta learning methods to solve this cold start problem.\n\n3. I have some questions about Theorem 2: What does the H_p function measure? What is the relationship between it and the target in this paper (true ability) and the error upper bound in Theorem 1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your thoughtful insights and suggestions regarding the generality of the expected gradient difference approximation proposed in our paper. Your perspective on the broader applicability of this approach is indeed intriguing and aligns well with our intentions.\n\n> **Q1**: The expected gradient difference approximation proposed in this paper is general in my opinion, and should not be limited to the CAT scenario.... I suggest the authors to study the effectiveness of the method in more tasks/domains.\n\n**A1**: We agree with your viewpoint that the concept of minimizing gradient differences has the potential to extend beyond the realm of Computerized Adaptive Testing. The proposed sample selection strategy design and efficient learning techniques for parameter estimation scenarios hold promise for a wide range of applications. In light of your recommendation, we are excited to investigate the feasibility and effectiveness of our approach in diverse contexts. \n\n\n> **Q2**: As stated in the paper: \"BECAT cannot surpass ... Why the proposed method cannot surpass the RL/Meta learning methods to solve this cold start problem.\n\n**A2**: Thank you for your valuable feedback on our paper. The observed limitation in BECAT's early performance can be attributed to this key factor: CAT begins with no information about the student's abilities. Unless a fixed strategy is employed, the first question is usually chosen randomly, which can undoubtedly influence the information-based algorithms, like FSI, KLI and our BECAT. In contrast, RL/Meta learning methods have the potential to alleviate this challenge to a certain extent due to their ability to discern patterns by pre-training on large response dataset. Considering the training overhead in practice and the bias from dataset, we still choose information-based paradigm in this paper. By addressing this aspect, we aim to provide a more comprehensive analysis of BECAT's performance in different phases of an exam.\n\n> **Q3**: I have some questions about Theorem 2: What does the $H_p$ function measure? What is the relationship between it and the target in this paper (true ability) and the error upper bound in Theorem 1?\n\n**A3**: As stated in line 202 of the paper, $H_p(\\theta^{t},\\theta^*)$ can be regarded as a type of statistical distance: measuring how probability distribution $p_{\\theta^t}$ is different from $p_{\\theta^*}$. Moreover, with the help of the consistency estimation (i.e., binary cross-entropy) at each step, $H_p(\\theta^t,\\theta^*)$ can reach its theoretical minimum. Theorem 1 suggests that, to minimize the expected error bound, the CAT systems should try to minimize $H_p$. In this case, the estimate error upper bound in Theorem 1 can be as small as possible. In addition, we further provide experimental results in Appendix E.3, and it is found that $H_p$ can be maintained at a relatively small value.\n\n\n\n\n\n"}, {"review_id": "3FEYD5kEaL", "reviewer": "Reviewer_GvrK", "summary": "This paper proposes a method for computerized adaptive testing by selecting questions that have similar gradients in their expected responses to other questions in the question bank. Results show that this method works well on real-world datasets. ", "questions": "- Can you clarify the significance of your theoretical analysis? They seem to be quite standard for submodular optimization. Strongly convex loss functions may not be feasible, as the authors mentioned, for more complex student models other than IRT. I also find the assumptions in Theorem 2, i.e., the minimized loss is 0, to be achievable. I the only case when that happens is the estimated ability parameter going to infinity (BCE minimization without regularization, so the MLE does not exist)?\n- In my personal opinion, minimizing the gradient difference with other questions to select a most representative question is not that different than doing a training-test split, which does not make the proposed method significant different from existing work on using meta learning for CAT. Is the only reason about submodularity giving you a proof?\n- Can you discuss what happens if the question bank is skewed in question parameters? In that case an approximation, Section 3.1, may not work?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method seems sound. Experimental results suggest that it is effective", "weaknesses": "- The proposed method is largely unsurprising and I do not find it to be significantly different than existing active learning methods, except for a different application\n- The performance improvement compared to existing methods is minimal", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and questions regarding our manuscript. Please feel free to share any further insights or suggestions you might have.\n\n> **Q1**: The proposed method is largely unsurprising and I do not find it to be significantly different than existing active learning methods.\n\n**A1**: In my opinion, regardless of CAT, Active Learning, Coreset, and Data Distillation, they are all sample selection or generation strategies (using the fewest samples to obtain the maximum benefit). Technically, their boundaries are not so clear. For example, the classic FSI in CAT selects a question whose difficulty is close to the ability (50% probability of correct answer), which is consistent with the uncertainty method in active learning. Recently, some researchers apply active learning to CAT [1]. This is an open-ended question, and we welcome any ideas you may have for discussion. \n\n> **Q2**: The performance improvement is minimal.\n\n**A2**: Compared to deep learning based methods, Yes, the improvement of our method BECAT at the beginning of the exam is small (line 265). Because the method based on deep learning requires pre-training selection algorithms on large-scale response data. However, information-based methods do not require training, thus it is difficult to catch up with the deep learning method. Considering the overhead and the bias from dataset, we still choose information-based paradigm. In the future, we will try to adapt the proposed explicit algorithm to data-driven frameworks.\n\n> **Q3**: Can you clarify the significance of your theoretical analysis? \n\n**A3**: Sure. The focus of this paper is: how to design a reasonable question selection algorithm, accurately estimating ability, when ground-truth ability is unknown. The significance of our theoretical analysis stems from our approach to problem identification, approximation and transformation, wherein we reframe the original problem into submodular optimization. Furthermore, from a technical standpoint, our work builds upon submodular and propose a novel similarity measurement method ($\\widetilde{w}(i,j)$), which can be practically applied to CAT scenarios, and provide theoretical analysis (estimation error upper-bound).\n\n> **Q4**: Strongly convex loss functions may not be feasible, as the authors mentioned, ...other than IRT.\n\n**A4**: Yes, it is almost impossible to achieve strong convexity for a more complex user model. Luckily, IRT is the most widely used and most interpretable model in CAT. Recently, researchers use more complex cognitive diagnostic models (e.g. NeuralCDM) in CAT system. However, like related theory research, we cannot prove Theorem's effectiveness on a black-box neural network, so we only evaluate them in experiments as stated in line 200.\n\n> **Q5**: I also find the assumptions in Theorem 2, i.e., the minimized loss is 0, to be achievable when that happens is the estimated ability parameter going to infinity?\n\n**A5**: For all responses correct or all incorrect, no finite ML/BCE estimates exist [2] just as you said. Generally: given 2PL-IRT model: $p_j(\\theta) = sigmoid(a_j(\\theta-b_j))$, if a student correctly answers question A (with difficulty $b= 1.0$), but wrong answers question B (with difficulty $b= 3.0$), it seems that the ability estimate $\\hat{\\theta} = 2.0$ is a good choice. Moreover, the discrimination parameter $\\alpha$ will also affect such estimation: for a question with high $\\alpha$, the ability slightly greater than difficulty can make the probability approach 1 (loss=0). Then again, loss is 0 in Theorem 2 is relatively ideal. But its purpose is to illustrate that $H_p$ is small in upper bound (line 207). Therefore, we further provide experimental results in Appendix E.3, and it is found that $H_p$ can be maintained at a relatively small value. \n\n> **Q6**: In my personal opinion, minimizing the gradient difference...from existing work on using meta learning for CAT. Is the only reason about submodularity giving you a proof?\n\n**A6**: We understand your concern and we would like to emphasize that our method leverages the concept of minimizing gradient differences to identify a question that maximizes **information gain**. Moreover, compared with meta learning, this greedy question selection algorithm does not need to be pre-trained with large-scale response data. Regarding your question about submodularity, it is indeed an important factor in providing a rigorous proof. No theoretical guarantee is unacceptable for real-world standardized tests, which is why we propose an explicit selection algorithm (line99). But our contributions extend beyond this aspect, and the submodularity in the context of adaptive testing is novel and has the potential to advance the field by ensuring the optimality of question selection. \n\n> **Q7**: Can you discuss what happens if the question bank is skewed in question parameters? In that case an approximation, may not work?\n\n**A7**:  Item parameter estimation needs to be pre-calibrated before testing, which is crucial in CAT system, regardless of the selection algorithm. For example, when the difficulty parameter of a difficult question is wrongly estimated to be small, it will undoubtedly bring challenges to low-ability student. We acknowledge that if the question bank exhibits significant skewness, the approximation might face challenges in accurately estimating ability. To address this concern, we plan to extend our discussions and experiments to include a thorough analysis when dealing with skewed question parameter distributions. \n\nReference\n\n[1] Bi, Haoyang, et al. \"Quality meets diversity: A model-agnostic framework for computerized adaptive testing.\" 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 2020.\n\n[2] Van der Linden, Wim J., and Peter J. Pashley. \"Item selection and ability estimation in adaptive testing.\" Elements of adaptive testing. New York: Springer New York, 2009. 3-30.  "}, {"review_id": "R81BxdjHFu", "reviewer": "Reviewer_DatR", "summary": "This is a very interesting paper that proposes a coreset-based algorithm to evaluate students' ability to answer questions from a question bank. The main innovations are defining a true student's probability and proposing a coreset algorithms with pseudo labels. ", "questions": "Can you provide the variance of your experimental results? ", "limitations": "Please see the weakness section. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**originality**\\\nI didn't have direct experience in CAT; however, the application of the coreset finding in efficient ability estimation for CAT is promising.\n\n**quality**\\\nThe proposed algorithm logically makes sense to me, and the English writing is generally clear enough. \n\n**clarity**\\\nThe organization of the paper is good, which helps me understand the main content quickly. \n\n**significance**\\\nI am a bit concerned about the ethical side of the work. The corset finding is dependent on the test takers, which means different test takers would end up with different questions assigned. Although the approximation error to the true estimation is claimed and given, I think it may lead to the fairness concern of whether giving different questions to different test takers is fair. \n ", "weaknesses": "I have multiple concerns regarding the mathematic rigor in this paper.\n\n1. In proposition 1, the definition of question bank $Q$ is missing. Hence, how \"questions\" or samples are generated to increase $|Q|$ is unclear. In addition, I think the proof of Proposition 1 should add $\\forall \\epsilon>0$. \n\n2. Definition 2 seems correct. However, I think it is nontrivial to prove that optimizing a loss function with gradients equivalent to the original loss function is equivalent to optimizing the original loss function. \n\n3. The upper bound for (4) is skipped in line 148. It would be clearer to list the upper bound of the loss first and then give the solution (coreset) of this upper bound.\n\n4. lemma 1 actually does not say much useful for the approximation. If you want to say the algorithm is to approximately solve the problem, then an approximation error to measure the distance between the original function and the function approximation should be explicitly provided.\n\n5. The expectation writing in line 188 is problematic. What distribution does $Y$ come from? \n\n6. Why the ''probability distance'' $H_p(\\theta^t, \\theta^*)$ in (10) is not zero when $\\theta^t=\\theta^*$? \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback on our CAT paper. We appreciate the time and effort you have invested in reviewing our work. \n\nFor your concerns regarding the fairness of CAT itself, first of all, let me introduce the background of CAT: as stated in Section 1, CAT is a *personalized* question selection system, which can adaptively select suitable items for individuals, assessing their ability accurately and efficiently. The typical application of CAT is GRE exam: when a test-taker begins the GRE, the computer provides a question of medium difficulty. If the response is correct, the computer presents a slightly more challenging question. Conversely, if the response is incorrect, the following question will be slightly easier. That's why some candidates may perceive the test becoming progressively more difficult. \n\nTherefore, similar to the recommendation system (different users will be recommended different items), *CAT also has fairness issues of course*. But this is another interesting topic, which is not the focus of this paper. Following your and Ethics Reviewer xQDC's suggestion, in an improved version, we will give a brief overview of fairness issues in CAT itself. The following are the responses to your other questions:\n\n> **Q1**: In proposition 1, the definition of question bank $Q$ is missing. Hence, how \"questions\" or samples are generated to increase $|Q|$ is unclear. In addition, I think the proof of Proposition 1 should add $\\forall \\epsilon >0$.\n\n**A1**: The question bank $Q$ is defined in the beginning of Section 2. Proposition 1 tries to explain that as the bank size $|Q|$ increases, the approximation becomes more ideal, and increasing the question bank is obviously achievable in real scenarios. Regarding $\\epsilon$, generally in the mathematical theory of CAT, $\\epsilon$ is greater than 0 by default. Sorry to confuse you, we will make the derivation more detailed in the follow-up.\n\n> **Q2**: Definition 2 seems correct. However, I think it is nontrivial to prove that optimizing a loss function with gradients equivalent to the original loss function is equivalent to optimizing the original loss function.\n\n**A2**: The transformation in Definition 2 is intuitive and consistent with Coreset method: in an optimization problem, if you use different dataset for standard gradient descent, as long as their gradient sum ($\\sum_{j\\in S}{\\gamma_j \\nabla l_j(\\theta)}$ and $\\sum_{i\\in Q}{\\nabla l_i(\\theta)}$) and initial parameter point are guaranteed to be the same, then the final optimization result (${\\theta^T}$ and $\\theta^*$) will naturally be the same. If you have any other questions, please feel free to ask.\n\n> **Q3**: The upper bound for (4) is skipped in line 148. It would be clearer to list the upper bound of the loss first and then give the solution (coreset) of this upper bound.\n\n**A3**: Since this part is based on previous Coreset research (cited in the paper), and considering the space limit, this part of the derivation is skipped. In the subsequent revisions of the paper, we plan to provide a more detailed derivation of it in appendix.\n\n\n> **Q4**: Lemma 1 actually does not say much useful for the approximation...\n\n**A4**: The role of Lemma 1 is to tell readers 1) what is the essential optimization goal of the expected gradient difference method we proposed.  Because, in CAT scenarios, we cannot get the labels of all samples like the traditional coreset problem. 2) It is an important theoretical basis of Theorem 1 (line 188 in main paper). Like the previous CAT optimization works [1][2], the approximation of the problem itself is unable to provide an approximation error. Fortunately, the ultimate goal of the paper is to obtain a theoretically guaranteed ability estimate (i.e., Theorem 1), which provide detailed analysis of approximation error in appendix.\n\n\n> **Q5**: What distribution does $y$ come from?\n\n**A5**: As stated on line 173, \"the normed gradient difference is calculated as an expectation $\\mathbb{E}_{y \\sim p _{\\theta^t }}$ over the possible labelings, since student's response labels $y$ to the candidate questions are unknown in the selection step.\". The distribution $y$ determined by the current estimate $\\theta^t$. For clarity, we will hightlight this part in the next version.\n\n\n> **Q6**: Why the ''probability distance'' $H_p(\\theta^{t},\\theta^*)$ in (10) is not zero when $\\theta^{t}=\\theta^*$?\n\n**A6**: $H_p(\\theta^{t},\\theta^*)=E_{(q,y)\\sim p_{\\theta^t}}  [1/p_{\\theta^*}(q,y)]$ in the upper bound measures the distance between $p_{\\theta^t}$ and $p_{\\theta^*}$, but it is different from the traditional probability distance (such as KL): The probability $p_{\\theta}\\in[0,1] \\to  1/p_{\\theta} >=1$ which determines that the minimum value of $H_p$ cannot be 0 (its theoretical minimum value is 1. More details about $H_p$ can be found in Section C of Supplementary Material (it can be assumed that $p_{\\theta^t}$ is a delta function)\n\n> **Q7**: Can you provide the variance of your experimental results?\n\n**A7**: Sure. In our experiments, we repeated 10 times under different seeds. For deep learning methods (BOBCAT and NCAT), we trained 10 models under different seeds. Due to the space limit in this Rebuttal editor pane, we provide the variance results in the above global Rebuttal pane (pdf) for every reviewers to check. \n\n\nReference: \n\n[1] Ghosh, Aritra, and Andrew Lan. \"BOBCAT: Bilevel Optimization-Based Computerized Adaptive Testing.\" International Joint Conference on Artificial Intelligence. 2021\n\n[2] Zhuang, Yan, et al. \"Fully adaptive framework: Neural computerized adaptive testing for online education.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 4. 2022.\n\n\n\n\n"}]

Author rebuttal:
We appreciate all the reviewers' thorough assessment and valuable feedbacks. Their thoughtful evaluation has provided valuable insights that have significantly contributed to the improvement of the manuscript. The reviewers' positive comments encompassing different dimensions are truly encouraging:

- **Contribution**: 
"CAT community would find this to be a valuable contribution" (KCbW);
"the ideas in this paper are novel" (KCbW); 
"This is a very interesting paper/solution is interesting" (TJRB, DatR);
"The author study an important problem" (aSHy);

- **Presentation**: 
"This paper is easy to follow" (TJRB); 
"The proposed algorithm logically makes sense to me, and the English writing is generally clear enough" (DatR); 
"The organization of the paper is good, which helps me understand the main content quickly" (DatR); 


- **Method**: 
"It proposes a simple, computationally inexpensive approach" (KCbW); 
"this paper provides a convincing analysis of the plausibility of the approximation" (TJRB); 
"coreset finding in efficient ability estimation for CAT is promising" (DatR)


- **Experimental Results**: 
"their method perform superior to other CAT methods at reducing test length" (aSHy);
"The results are compelling and compared against a thorough set of competitive models" (KCbW);
"this method works well on real-world datasets" (GvrK)

Regarding the questions raised by each reviewer, we have carefully considered each point and have made detailed responses in the local rebuttal pane. 

---
**[Response to Ethics Reviewers]**

We deeply appreciate your thoughtful consideration of the ethical implications associated with CAT itself. Like recommendation system (different users will be recommended different items), CAT is also a **personalized** question in Education and has fairness issues of course, which is another interesting topic. You point out that the use of adaptive methods within the standardized testing is a topic of ongoing debate, with concerns about bias in original data and its potential amplification during the estimation process. We acknowledge the importance of addressing these concerns to ensure fairness and equity in educational assessments.

While our paper aimed to present a novel method for improving the **efficiency** of CAT, your feedback highlights the necessity of addressing the potential ethical pitfalls. In line with your recommendation, we will revise the paper to incorporate a dedicated subsection that discusses potential sources of bias in CAT itself and the datasets used. 

***

Several steps of Lemma 1 are skipped in the paper, because these steps are based on the other papers (which have been cited in the original proofs). Thanks for the suggestion from Reviewer KCbW, we now provide detailed proof of Lemma 1 for all reviewers to check:

**[Detailed proof of Lemma 1]**
> *Lemma1*: ...The corresponding designed selection algorithm using submodular function $\widetilde{F}$ is actually approximately solving the following optimization problem: $\min\limits_{|S|=T} \max\limits_{\theta\in \Theta} \mathbb{E}_y [\Vert  \sum _{j\in S}{\gamma_j \nabla l_j(\theta)} - \sum _{i\in Q}{\nabla l_i(\theta)}  \Vert ]$

 *Proof*:  We first define a mapping function $h$ from set $Q$ to $S$ to a mapping function:$\forall i \in Q, h(i)\in S$. It assign every response data point $i \in Q$ to one of the elements $j$ in $S$. Then, for any arbitrary ability parameter $\theta \in \Theta$ we can write
  $$ \sum_{i\in Q}{\nabla l_i(\theta)} =\sum_{i\in Q}{[\nabla l_i(\theta)- \nabla l_{h(i)}(\theta) +  \nabla l_{h(i)}(\theta)]} 
	=\sum_{i\in Q}{[\nabla l_i(\theta) - \nabla l_{h(i)}(\theta)]} + \sum_{j\in S}{\gamma_j \nabla l_j(\theta)}$$
Subtracting and taking the expected norm of the both sides, we get an upper bound on the error. According to the triangle inequality, we have $$\mathbb{E}\left[\Vert \sum_{i\in Q}{\nabla l_i(\theta)} -\sum_{i\in S}{\gamma_j \nabla l_j(\theta)} \Vert \right]\le \sum_{i\in Q}{\mathbb{E}\left[\Vert \nabla l_i(\theta) - \nabla l_{h'(i)}(\theta)\Vert \right]}.$$
When the mapping function $h$ is to map each element in $Q$ to the one in $S$ that is closest to its expected gradient, the right side of inequality is minimized, or minimum expected distance between the gradient: $h(i)= \arg\min_{j\in S} \mathbb{E}\left[\Vert \nabla l_i(\theta) - \nabla l_j(\theta)\Vert \right]$. Therefore, the upper bound of the expected gradient difference can be further constrained:
$$\min_{|S|=T}\mathbb{E}\left[\Vert \sum_{i\in Q}{\nabla l_i(\theta)} -\sum_{i\in S}{\gamma_j \nabla l_j(\theta)} \Vert \right]\le \sum_{i\in Q}{\mathop{\mathrm{min}}\limits_{j\in S}\mathbb{E}\left[\Vert \nabla l_i(\theta) - \nabla l_{j}(\theta)\Vert \right]}.$$
Next, define a similarity function $\widetilde{w}(i,j)$ which measures the expected gradient similarity between response pair $i$ and $j$: $ \widetilde{w}(i,j)=d-\max_{\theta\in \Theta} {\mathbb{E}\left[\Vert \nabla l_i(\theta) - \nabla l_{j}(\theta)\Vert \right]} $, and $d=\max_{i\in Q,j\in S}\max_{\theta\in \Theta} {\Vert \nabla l_i(\theta) - \nabla l_{j}(\theta)\Vert}$ is the maximum pairwise gradient distance. Thus, the optimization problem can also be transformed as:
$$\max\limits_{|S|=T} \sum_{i\in Q}{\mathop{\mathrm{max}}\limits_{j\in S} \widetilde{w}(i,j)}.$$
Following the same way of origin problem, its corresponding submodular $\widetilde{F}(S)=\sum_{i\in Q}{\max_{j\in S} \widetilde{w}(i,j)}$, which is the same with our proposed method. Thus, the designed selection algorithm is the greedy algorithm of the optimization problem.


***

**[Variance results]**

Pdf is the variance result asked by Reviewer DatR, for every reviewers to check.







Meta-review: The paper studies the problem of selecting informative questions in Computerized Adaptive Testing. The goal is to adaptively select a small number of questions for a student that will maximize the accuracy of estimating the student's ability. The proposed method, BECAT, is based on ideas from adaptive submodular optimization and operates by selecting a subset of questions that provides gradients similar to the entire set of questions. Extensive experimental evaluation on synthetic and real-world datasets showcases the effectiveness of the proposed method. The reviewers acknowledged that the paper considers an important problem setting in Computerized Adaptive Testing and that the proposed method has novel ideas with promising results. However, the reviewers and two Ethics reviewers raised several concerns and questions in their initial reviews. We want to thank the authors for their detailed responses and for actively engaging with the reviewers during the discussion phase. The reviewers appreciated the responses and have an overall positive assessment of the paper. The reviewers have provided detailed feedback in their reviews, and we strongly encourage the authors to incorporate this feedback as per the authors' responses. In particular, the authors should carefully incorporate the feedback from Ethics reviewers by adding a dedicated discussion subsection in the final version of the paper.
Decision: Accept (poster)