A Spectral Approach to Item Response Theory
Authors: Duc Nguyen
Anderson Ye Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: item response theory
education testing
recommendation systems
Rasch model
spectral method

Abstract: The Rasch model is one of the most fundamental models in item response theory and has wide-ranging applications from education testing to recommendation systems. In a universe with $n$ users and $m$ items, the Rasch model assumes that the binary response $X_{li} \in \{0,1\}$ of a user $l$ with parameter $\theta^*_l$ to an item $i$ with parameter $\beta^*_i$ (e.g., a user likes a movie, a student correctly solves a problem) is distributed as $\mathbb{P}(X_{li}=1) = 1/(1 + \exp(-(\theta^*_l - \beta^*_i)))$. In this paper, we propose a new item estimation algorithm for this celebrated model (i.e., to estimate $\beta^*$). The core of our algorithm is the computation of the stationary distribution of a Markov chain defined on an item-item graph. We complement our algorithmic contributions with finite-sample error guarantees, the first of their kind in the literature, showing that our algorithm is consistent and enjoys favorable optimality properties. We discuss practical modifications to accelerate and robustify the algorithm that practitioners can adopt. Experiments on synthetic and real-life datasets, ranging from small education testing datasets to large recommendation systems datasets show that our algorithm is scalable, accurate, and competitive with the most commonly used methods in the literature.

A Spectral Approach to Item Response Theory
Duc Nguyen
Anderson Y. Zhang
Department of Computer and Information Science
Department of Statistics and Data Science
University of Pennsylvania
University of Pennsylvania
mdnguyenéseas upenn. edu
ayz@wharton. upenn. edu
Abstract
The Rasch model is one of the most fundamental models in item response theory and has wide-ranging applications from education testing to recommendation systems. In universe with users and m items, the Rasch model assumes that the binary response X E {0, 1} of user with parameter of to an item with parameter 3 (c.g., user likes movie, student correctly solves problem) is distributed as PXX;; = 1) = 1/(1 + exp (0, B)))). this paper, we propose new item estimation algorithm for this celebrated model (i.e., to estimate 3*)) ). The core of our algorithm the computation of the stationary distribution of a Markov chain defined contributions with finite-sample error guarantees, the first of their kind in the literature, showing that our algorithm consistent and enjoys favorable optimality properties. We discuss practical modifications to accelerate and robustify the algorithm that practitioners can adopt. Experiments datasets, ranging from small education testing datasets to large recommendation systems datasets show that our algorithm scalable, accurate, and competitive with the most commonly used methods in the literature.
item-item graph. We complement
algorithmic
synthetic and real-life
Introduction
Item response theory (IRT) is the study of the relationship between latent characteristics (a student's s ability versus test's difficulty or user's taste versus movie's features) and the manifestations of these characteristics (a student's 's performance on a test or a user's 's rating of movie). Originally developed by the psychometric community 45 item response theory has been applied diverse
settings such as education testing (37), crowdsourcing
[54] recommendation systems [2] finance
(50) and marketing research [10].
One of the most fundamental models in IRT is the Rasch model 45
models the binary response X E (0, 1) of user I with latent parameter of TR item i with latent parameter 37 E R by
P(X:
exp (- 3))
For example, in education testing, Of corresponds the ability of student I, 8r the difficulty of problem and X₁ = 1 if the student correctly solves the problem. Binary response data has grown abundantly in modern domains: Netflix famously switched from 5-star rating system binary like/dislike feedback system, data students' engagement and performance grows significantly as education moves online during the pandemic.
Traditionally, the goal of estimation under the Rasch model to recover the item parameters 3* In education testing, estimate of the item parameters can be used to calibrate scores across different
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

versions of a test. In recommendation systems, the item parameters can be used to produce a ranking over the items. In general, estimation is challenging under the Rasch model because for each user and item pair, we only get single observation or none in the case of missing data.
Joint maximum likelihood estimate (JMLE) is one of the earliest methods developed for the estimation problem [3 22 25 27|. It estimates both the user and item parameters by maximizing the joint likelihood function using an alternating maximization algorithm. While efficient, JMLE known to be inconsistent (that is, even as n + 20, JMLE does not recover 3²)) when the number of items is finite 3 2 (e.g., Figure Lap. Intuitively. this is because there are many nuisance user parameters to finite number of item parameters. As a result, JMLE is mostly used for prelimary parameter estimation and researchers have developed other solutions to address the inconsistency problem. broadly consisting of 3 approaches as follows.
The first approach is marginal maximum likelihood estimate (MMLE) 77.. The statistician first specifies a prior distribution over the user parameters. The objective of MMLE is to maximize the marignal likelihood function which integrates out the user parameters. In pratice, MMLE runs quite fast, handles missing data well and is reasonably accurate. However, its performance depends on the accuracy of the prior distribution. If misspecified, MMLE may produce inaccurate estimates (e.g.. Figure lbp. Model selection is thus a crucial procedure when applying MMLE to real data.
The second approach is conditional maximum likelihood estimate (CMLE) B 22 27.. CMLE builds on the fact that under the Rasch model the total number of positive responses St for each user I is sufficient statistic for the user parameter 07- Instead of the joint likelihood function, CMLE maximizes the likelihood conditioned on {=1]==1- Unlike JMLE, CMLE is statistically consistent without requiring any distribution assumptions about 0" For small datasets with no missing data, CMLE is quite accurate. However, it may incur high computational cost and numerical issues on large datasets with many items and missing entries. Practioners have observed that CMLE often produces inaccurate estimates [35| (6) in this regime (e.g., Figure Ic
The third approach, which our algorithm follows, uses pairwise information that can be extracted from binary responses. Intuitively. if a user responds to two items, one negatively and one positively, we learn that the later is 'better'. Following this intuition, previous authors 23 17 48) have designed spectral algorithms that first construct an item-item matrix and then compute its leading eigenvector. One common limitation of these methods is that the item-item matrix is assumed to be dense. Therefore, these methods aren't 't directly extendable to large scale datasets in applications such as recommendation systems where the item-item observation is sparse.
Furthermore, most theoretical guarantees for the above methods are asymptotic (n + oo). However, having finite sample error guarantees is useful in real-life applications. For example, when we only observe a handful of responses to a new item, it is important to have an accurate estimate of the error over the item parameter. Asymptotic guarantees, the other hand, are accurate mostly under large sample size regime, and can be inaccurate in the data-poor regime.
Our Contributions: Motivated by known limitations of the existing methods, we propose a new, theoretically grounded algorithm that addresses these limitations and performs competitively with the most commonly used methods in the literature. More specifically:
In Sections 2 and 4
describe the spectral algorithm and practical modifications an accelerated version of the original algorithm and a regularization strategy - that allow the algorithm to scale large real-life datasets with sparse observation patterns and alleviate numerical issues.
In Section 3. we present non-asymplotic error guarantees for the spectral method the Notably, under the regime where m grows, the spectral algorithm has optimal (up to constant factor) estimation error achievable by any unbiased estimator (Theorem 3.4p. Under the challenging regime where m is constant or grows very slowly we show that the spectral algorithm is, unlike JMLE, consistent (Corollary 3.2).
first of their kind in the literature - in Theorems 3.1 and 3.3
In Section 5
we present experiment results on a wide range of datasets, both synthetic and real, to show that our spectral algorithm is competitive with the most commonly used methods in the literature, works off-the-shely with minimal tuning and scalable on large datasets.
2

---

1.1 Notations and Problem Formulation
As briefly described before, in a universe of users and m items, each user / has a latent parameter of E IR and each item i has latent parameter 8 E R. The reader may recognize that there is fundamental identifiability issue associated with the Rasch model pertaining to translation. That is, {0* and {0r + n. 9 + mlm) describe the same model for any a E IR. For this reason, we impose normalization constraint the item parameters 3 1m = O. We consider the fixed range setting where 3 E [Bmin Smasl Vi E [m]] for some constants M maxx Similarly, we assume that
or E [0iing max for some constants mmin O D The observed data is X E (0, 1, * ] where denotes missing data and for entries where Xü * *, X is independently distributed per Equation (1) Let A E {0, 10,1 denote the assignment matrix where AG if user responds (either negatively
or positively) to item and O if user does not respond to item i (i.e., X = *). Define = A A.
i.e., Bij is the number of users who respond to both items j. The goal of item estimation is to
obtain an estimate from the observed data X and the metric of interest is the lg error, || 8 12-
2 The Spectral Estimator
In this section we describe our spectral algorithm which is summarized in Algorithm I At a high level, the algorithm constructs a Markov chain defined on graph whose vertices are the items and its transition probabilities are estimated using the observed user-item response data. The algorithm then computes the stationary distribution of this Markov chain and the estimate /3 is obtained following a simple transformation.
We first define, for each item pair i.j and fixed assignment A, a quantity which we term pairwise differential measurement:
YJJ
Σ An Aty X1,) Vi * E [m]. 1=1
(
Intuitively, Y,y is the number of users who respond and 0 to j. Given the pairwise differential measurements, consider Markov chain P [0, 1jmxx whose transition probabilities are defined as follows:
Y 11 E
i if=
Pig
where d is sufficiently large normalization factor chosen such that the resulting pairwise transition probability matrix does not contain any negative entries. Typically, d = Ommaxc{(m) Exzes B.x). The algorithm then computes the stationary distribution π of the Markov chain (c.g., using power iteration) and recover & using a post-processe proscesccnsing step. In real-life datasets, the constructed Markov chain is often sparse (not every pair of items has non zero pairwise differential measurements). Practicioners could take advantage of this sparsity speed up the computation of the stationary distribution such as by using sparse matrix-vector multiplication subroutines.
To understand the intuition behind our spectral algorithm, let consider the following idealized Markov chain where the state transition probabilities are exact:
for i + for i j
p
(4)
E
where Vij- = =E== Ari AR
X(y)]. For every pair i, j. given a sufficiently large number of users who respond to both items, YiJ will concentrate around Y.J- Then, under an appropriately large scaling factor d, Pij Re Pr, and the two Markov chains are 'close'. This means that the stationary distribution of P is also close that of pa, At the same time, the true item parameter 3 is directly related to the stationary distribution of Pa This relation is summarized by Proposition 2.1
Proposition 2.1. Consider the idealized Markov chain described in Equation The stationary distribution n" of P* satisfies x²- 8 EE 8i for E [m].
'The bounded range assumption is a common one in the literature on the Rasch model. Intuitively, it eliminates the presence of items that are always repsonded positively to (or negatively to) and users who only responds positively (or negatively) that leads to parameter unidentifiability [26].
3

---

Algorithm Spectral Estimator
Input: User-item binary response data E [0,1, [0,1,)]xx0) Output: An estimate of the item parameters [31....... 3m
1: Construct a Markov chain per Equation (
2: Compute the stationary distribution of P:
Initialize (0)) = mm -m..... ......,,. l
For f 1,2,.... until convergence, compute
T((-1)
T(0)T
[|((--)) Pll2
3: Compute = r/d and 3 = log(z)
4: Return the normalized item parameters, i.e., 3 = - 13-311 1/m
Essentially Proposition 2.1 states that x² is proportional to e Thus 8 can be recovered from .² up global normalization. Now, given sufficiently large number of users, the empirical stationary distribution æ will be close to n² and naturally the obtained estimate / is also close to S
Readers who are familiar with the ranking from pairwise comparison literature might recognize the similarity between the spectral algorithm and Rank Centrality 43 for parameter estimation under the Bradley-Terry-Luce model [38). Similarly to Rank Centrality, algorithm constructs a Markov chain on the item-item graph and recovers parameter estimate from its stationary distirbution. In both cases, the Markov chain interpretation motivated by the unique characteristies of the BTL and Rasch likelihood function. However, the specific construction differs between our algorithm and Rank Centrality and does the resulting analysis.
Theoretical Analysis
In this section, we present the main theoretical contributions of the paper. Specifically, we obtain in Section 3.1 two finite sample error bounds for two different regimes of where is constant or grows very slowly and where m grows at least logarithmically relative to n. In addition to our upper bounds, show in Section 3.2 Cramer- lower bound for the mean squared error of any unbiased estimator, establishing the optimality of the spectral algorithm under the the second regime. For the special case up to log factor.
show that the error rate obtained by the spectral algorithm is optimal
3.1 Finite Sample Error Guarantees
Sampling Model:
Let us consider a random sampling model where for each user E [n]], each item i [m] is independently shown to that user with probability (i.e., P(A 1) p). Once shown an item 1, the user responds with X₁; distributed according to Equation ①
Under this sampling model and the regime where m is constant or grows very slowly, we obtain the following upper bound on the estimation error of the spectral algorithm which is, the best of our knowledge, the first finite sample error guarantee for any consistent estimator under the Rasch model the literature.
Theorem 3.1. Consider the sampling model described above. Suppose that np² 2 C" log for sufficiently large constant C' then the output of the spectral algorithm statisfies
- 38 Cymax m, log np?
/ np
with probability at least 1 minfe-122 (myP)12 exp (-Cinp?), where C, C1 constants.
As alluded to before in our algorithm description, the proof of Theorem 3.1 uses Markov chain analysis and central object is the idealized Markov chain pa with its stationary distribution σ². The

---

proof is rather long and involved so we defer the details to the supplementary materials and describe here the main idea. The starting point is a Markov chain ppennpeeturbationn bound (see Lemma A.3)
|| (P' - P) -= P
|| 12 S
where y (PP) is the spectral gap of the idealized Markov chain. We then bound the numerator and the denominator separately. We will show under the setting of Theorem 3.1 that
10 - - PT = 22 (1
- - = o v max(m, log np²
and ||
dmvy npp
Combining these bounds with the following relation gives the desired error bound:
- 8- ( m |||TT x-" 11112)
As an immediate consequence of Theorem 3.1 we can also prove the consistency of the spectral algorithm under the constant m regime. As mentioned previously, JMLE, one of the most well known methods in the Rasch modeling literature, is inconsistent in this regime.
Corollary 3.2. Consider the setting of Theorem 3.1] For a fixed m and p = 1, the spectral algorithm is a consistent estimator of 8". That is, its output B satisfies lim P( ((11--811) 18112 <c) = =, 0.
Under the regime where m grows, we could sharpen the results of Theorem 3.1 Specifically, when the number of items shown each user is sufficiently large, we improve by a /p factor which can be significant when p is small. This is summarized by the following theorem.
Theorem 3.3. Consider the setting of Theorem 3.7 Assume further that mpp 2 C" log n for a sufficiently large constant C" then the output of the spectral algorithm statisfies
Cmvm
|| 18-181122
18
TTp
with probability at least 1 - exp (-C2np²) - 2n -9, where C*,, C² are constants.
The reader may wonder why there would be difference between the two regimes. Intuitively, when m is a small constant, the distribution the number of items shown to the users are not tightly concentrated. Some users are shown all of the items while some are shown only one. By design, our spectral algorithm uses pairwise differential measurements. This means that when a user responds only one item, that information is not fully used. On the other hand, when mpp = O(log n), the number of items shown to the users is concentrated (all users are shown approximately the same number of items) and more pairwise differential measurements are available. There is less information being under-utilized by the algorithm and it enjoys a tighter (in fact optimal) error rate.
3.2 Cramer-Rao Lower Bound
In this section, present complementary results to finite error guarantees obtained in the previous section. Notably, under the regime where m is allowed to grow with n, we show that the minimum mean squared error achievable by any unbiased estimator is no more than a constant factor smaller than the upper bound for the spectral algorithm established in Theorem 3.3 This optimality result summarized by the following theorem.
Theorem 3.4. Consider the sampling model described in in Section 3.1 Let T be any unbiased estimator for the item parameters. Then the mean squared error of such estimator lower bounded
( -
cm
np
where T(X) is the output of the estimator T when given data X and is constant.
Now note that under the settings of Theorem 3.3 the output of the spectral algorithm also statisfies ||B - 1 ( mp) To the best of our knowledge, this is the first non-asymptotic optimality result for any item estimation method under the Rasch model.
5

---

As noted before, when the number of items is constant. our error bound in Theorem 3.1 incurs an additional 1/ factor. We now argue that the upper bound obtained there may already be optimal in this challenging regime. Consider the special case when m = 2. Essentially, the goal is to estimate the difference of the two item parameters. For a particular user suppose that we have no information about her parameter 0r other than the bounded condition. If the user's responses consist of a single response (the response to one item is not observed) or that her responses to both items are identical (either both 0 or 1), then we learn little about the difference between the two items. We refer to these responses as 'bad' responses. The relative difference between the items is only revealed the user responds differently to the items. As noted in the description of our spectral algorithm, we refer to such information as pairwise differential measurements.
For the special case m 2, both CMLE and JMLE actually ignore 'bad' responses. This is because in both algorithms, it has been shown that including bad responses in the respective objective likelihood function leads to parameter unidentifiability [26]. As mentioned earlier, MMLE, requires an accurate prior distribution in order to obtain good estimate accuracy. This is not possible when we have no information about the user parameters. With the exception of MMLE, all estimation methods that we are aware of in the literature only use pairwise differential measurements.
With these points considered, if we restrict our attention to the class of algorithms that use pairwise differential measurements, then the spectral algorithm indeed achieves the best possible (up to a log factor) estimation eπror.
Theorem 3.5. Fix m. = 2 and consider the sampling model described in Section 3.1 Let T be any unbiased estimator for the item parameters that only uses pairwise differential measurements. Then the mean squared error of such estimator is lower bounded as
EII((X-- - 13 npp
where T(X) is the output of the estimator when given data X and d' is a constant.
As seen from Theorem 3.1, the estimate produced by the spectral algorithm satisfies ||3 - -3
Ō up ), establishing its near optimality.
4 Practical Implementation Aspects
In this section, we discuss two important practical aspects that practicioners may consider when applying the spectral algorithm real-life datasets of which observation pattern may not correspond exactly to the sampling model described in Section 3.1 Firstly, we identify slow convergence as a problem encountered by the spectral algorithm when the data is skewed in the sense that some items are highly responded to by users while some items are rarely responded to. To address this issue, we propose an accelerated spectral algorithm that enjoys the same error guarantees as the original spectral algorithm but runs significantly faster in practice and suffers from fewer numerical issues. Secondly, we discuss regularization strategy when the spectral algorithm is applied to datasets with sparse observation patterns.
Accelerating the Spectral Algorithm: Recall that in the original spectral Algorithm I we use a common normalization constant d that generally scales as (max, Ex B.x). In practice, the distribution of the user-item assignment could be skewed such that some items are rarely responded to while some elicit many user responses. In such cases, the items with few responses will have few pairwise differential measurements & d. The induced Markov chain will contain large self-loops for these items. We observe that these large self-loops lead to a slower convergence when computing the stationary distribution and more numerical issues. This observation was also noted in 2 and we propose a similar solution to climinate large self-loops that is to use different normalizing factor for each vertex. Consider the following modified Markov chain:
if }
P.
ij 2. Ene Yo
(S)
if
where Yı defined in Equation and (d are appropriately chosen normalization factors such that the resulting transition probability matrix does not contain any negative entries. In our

---

experiments, we choose d, = O(Exz Bsx). The accelerated spectral algorithm computes the stationary distribution of the above modified Markov chain, and recovers the item parameters via post-processing step. The algorithm summarized in Algorithm
Algorithm 2 Accelerated Spectral Estimator
Input: User-item binary response data X E 10, p Output:
estimate of the item parameters
[......, Pm]
1: Construct a modified Markov chain P per Equation (
2: Compute the stationary distribution of P
3: Compute = Dー and / = log(z) where D = diag (iaggd),....... dm)
4: Return the normalized item parameters, i.e., B =
1/m
Interestingly, the accelerated algorithm produces essentially the same estimate the original algo- rithm. Under some regularity conditions, there is direct one-to-one relation between the stationary distribution obtained using the original Markov chain in Algorithm| and the stationary distribution क the Markov chain parametrized by This result summarized in Theorem 4.1
Theorem 4.1. Consider the modified Markov chain P constructed per Equation 5 and the original
Markov chain P constructed per Equation (3). Suppose that both P and P admit unique stationary distributions क and n, respectively. Then
Tyd
Vi E [m],
Ek Rads
where d; are the normalization factors in the construction of the modified Markov chain P.
Assuming perfect numerical precision, the two versions of the spectral algorithm output the same estimates. Therefore the guarantees in Theorems 3.1 and 3.3 also apply to the accelerated spectral algorithm. However, in our experiments, we observe that the accelerated spectral algorithm converges much faster and suffers from fewer numerical issues than the original version on real-life datasets, leading to better performance overall. We thus use the accelerated version in our experiments.
Regularization for Sparse Datasets: some real-life datasets, observe that certain pairs of items have few pairwise differential measurements. Furthermore, the pairwise differential data is one-sided (e.g., users who respond to the two items always respond positively to one but negatively to the other). This could happen to pairs that have been shown to only few users. The existence of many such pairs may also introduce numerical issues and parameters unidentifiability. For example, when there is an item such that Yj+ O'A f i, the stationary probability correpsonding to this item will be 0 and the item parameter estimate will -a. As solution, we propose adding regularization in the construction of the Markov chain. Specifically, for every pair of items i, such that Bij > 0 redefine
YU = Σ AnAr X1,) X1,)+2 1=1
+
where v is small constant. In all of our experiments real-life datasets, use = 1 and find that the regularization parameter requires little tuning. Regularization also ensures the uniqueness of the stationary distribution. So long as the graph underlying the Markov chain is connected, adding regularization ensures that no pairwise transition probability is 0. This makes the constructed Markoy chain ergodic and there is unique stationary distribution 47
Experiments
In this section, we present empirical findings which support the practical value of our spectral algorithm. Our baselines are the most commonly used estimation algorithms in the literature: conditional maximum likelihood estimate (CMLE), marginal maxinum likelihood estimate (MMLE) and joint maximum marginal likelihood (JMLE). Their open source implementation can be found online [49]. We include the python implementation of our spectral algorithm in the supplementary materials.

---

m
10.
1.0 (MMLE with correct prior)
10,
1.0 (MMLE with misspecified prior)
Spectral
12
Spectral
MMLE
MMLE
10
CMLE
CMLE
MMLE
08
JMLE
04-
5000
(a) When the number of items is small, JMLE
When the MMLE prior distribution is mis- specified, its performance could degrade.
(b)
is known to produce inconsistent estimate.
100, 0.1 (MMLE with correct prior)
100, 1.0 (MMLE with correct prior)
Spectral
Spectral MMLE
MMLE
Inference time (s)
CMLE
JMLE
JMLE
18
5-
0-
(c) larger datasets with missing data, CMLE's performance could degrade.
(d) The spectral method comparatively seal- able.
(Synthetic Data Experiments.) The spectral method performs consistently well (both in terms of & егтоr and time complexity) across range of settings while CMLE, MMLE and JMLE could underperform unfavorable settings. Presented results have been averaged over 100 trials.
Figure 1:
Synthetic Data:
We generate the item parameters 8 from standard normal distribution and user parameters 8" from (0, o²) where 0² varies for different model settings. Recall that MMLE requires the statistician to specify the prior distribution over the user parameters and for synthetic experiments, we specify this prior distribution to be the standard normal distribution. Subfigures (a)-(c) of Figure Show [|8 - 8 against n for all 4 algorithms under 3 differen! model settings while Subfigure (d) shows inference time. When there is no missing data and MMLE's prior distribution correctly specified (o 1). CMLE, MMLE and the spectral algorithm perform equally well. However, when MMLE's prior distribution is misspecified (o 2). it produces inconsistent estimates. As mentioned before, JMLE is known to produce inconsistent estimate when m is small relative to n. On the other hand, CMLE's performance degrades under moderately sized dataset with missing data. The spectral algorithm, however, consistently performs well across all of these settings and comparatively scalable.
We perform experiments on wide range of real-life datasets from education testing datasets to book and movie ratings datasets for recommendation systems. In order to transform ratings data to binary response data, follow the procedures in previous works 33 19). Specifically, for each user, we convert all ratings higher than the average to 0 and otherwise (so that items with a higher parameter value is 'better'). Since real-life datasets do not come with true 3* parameters, we compare the algorithms on four metrics: area under the ROC curve (denoted AUC) on heldout test data; log- likelloodoo on heldout test data; inference time and top-K accuracy where the reference top-K K set is determined by average ratings. We have also followed the standard procedure in the recommendation systems literature remove items that have few (S 10) ratings from the reference top- set. In our experiments, we consider K E {10, 25, 50). We defer extra experiment results where we include additional algorithms such as Bayesian estimation [42] and pairwise likelihood estimation to the supplementary materials. We mention here a few notable datasets: RIIID I
Real Data:
(m 6h;, n = 23k, education testing dataset), MI-20M 28
(m 27k, n = 138k),
31 (m 10k, n 350k).
8

---

AFCC
Tup-[10 g
swamey
Teal
Dataset
Speciaal
Chiz
INLZ
Syectral
NNLE
INLE
Spocial
JNLE
Spectnii
NNLLE
DALE
0.00
6,007
0.702
-0
-0.50
455
N0A
0.004
0.100
0000
OCt
0.43
0.900
0.583
0.983
-0.67
-0.995
-0882
-1.06
30
30A
30A
39A
0.03
0L00
0,000
CHADES
9382
0,502
0332
03322
-0 109
-0.90
-0891
-0.97
NA
NA
NA
0.001
0191
0.900
0000
RIND
0.733
NIA
0.73
-0.45
X0A
-3.45
80A
N0A
101
01.2
ML-1008
0182
-0843
-088
-1.9
-0185
04748790
10/708/00
48//0/00 /10
1300
16.2
MI
066
6.001
0.863
02
-0.85
-032
-000
36/00/330
6570042000
0.00
19.0
863
1558
EACH MOONEE
0.72
15755
10522
-4833
-03135
-1340
-1884
g 21052
164 (3:88-1100 1666
11.5
121
2214
1.54
15M
0711
0.716
NiA
0.10
-0607
-0310
3IA
-3638
65.0512077
NIA
60/0.35
631
238
NIA
6.53
SI.-2M
0.72
0.71
NIA
0.55
-0533
-0319
N0A
22/044/00
N0A
612/44654
13sk
5.94
4-2
9.549
28.0035207
032022001
5058
03/2322
02/0212
Table 1: (Real Data Experiments.) ) The spectral method (1st column under each metric) is competitive with the baselines (best results are shaded) especially in terms of ranking metries The spectral method is generally the fastest method large datasets. It works off-the-shelf with minimal tuning and comparatively accurate.
Table summarizes the performance of the four methods in our experiments. Note that the first four datasets are education testing datasets and thus there are no top- K ranking metrics being measured. For tuning the prior distribution for MMLE, we select the prior distribution that admits the highest liglliilidood on validation set. On the other hand, CMLE, JMLE and the spectral method requires minimal model tuning. For small scale education datasets (LSAT, UCI, 3GRADES), there missing responses and all methods perform very similarly to one another. For large scale ratings datasets, the spectral method remains competitive with the baselines in terms of AUC and log-like ligliikl but tends to outperforms in top-K accuracy and is significantly more efficient.
In large scale ratings datasets, we observe that the competitor methods tend to assign large parameter value to items that receive only few but very high ratings (so after data processing, all of the responses to such items are 0) and these items are not included in the reference top-K set. The spectral method, because it operates on pairwise differentials, is less susceptible to these noisy responses and thus more accurately recovers the items in the reference top-K set.
Related Works
The Rasch modeling literature is quite broad and we refer the interested reader to recent surveys Since its original formulation to model psychological tests outcome (45). the model has been extended to account for more complicated response patterns such as numerical ratings and ordinal responses
6 46)
4 5 55 39 Higher-order models that incorporates bias variables such as the 2PL and 3PL model 9 and multivariate models [2I] remain active areas of research where machine learning techniques have recently been applied with substantial success [8]. The Rasch inference problem also closely connected to the 1-bit matrix completion problem in machine learning where we observe a sparse n x m binary matrix with underlying entrywise probability f(M) where f a mapping function (e.g., logistic) and M is a real-valued matrix. There, the goal is obtain an estimate of M. commonly proposed approaches for 1-bit matrix completion based on alternating optimization exactly joint maximum likelihood estimate [5] 14].
7 Ethical Considerations
Our work proposes an algorithm of which real-life applications very often involve actual human data with sensitive information. For example, the Rasch model is often studied in the context of education testing and psychological testing where the subjects of studies are students and patients. Therefore, deploying our algorithm (or any algorithms in this context) needs to be accompanied by thoughtful and thorough ethical considerations. In this work, we provide the algorithmic tool that lays the foundation for our algorithm and its theoretical guarantee. We believe that a socially
2 As noted before, CMLE has been observed to underperform on large datasets with missing data. In some of our experiments, CMLE fails due to numerical errors or does not converge. The results for CMLE are marked 'N/A' for these experiments.

---

constructive application of our algorithm should always be accompanied by detailed explanation of its fundamental limitations, assumptions and decision makers need take into account these aspects when interpreting the results returned by the algorithm.
8 Conclusion
We propose new spectral algorithm for the item estimation problem under the celebrated Rasch model. Our algorithm is theoretically well-founded, practically performant and should be added to the statistician's quiver of estimation methods when analyzing binary response data. Extending our algorithm to more expressive IRT models such 2PL or 3PL and response types is open avenue. In the future, we also hope to generalize the method to more complicated response data types such as ordinal or rating data, well as incorporating ancillary information (user and item features).
9
Acknowledgement
The authors would like to thank William Zhang for proofreading and leaving helpful comments on earlier drafts of this paper. We would also like to thank the anonymous reviewers for their thoughtful suggestions that have been incorporated to improve this paper. D.N. and A.Z. are supported by NSF Grant DMS-21 21 12988. A.Z. acknowledges financial support from the Alfred H. Williams Faculty Scholar award. Any opinions expressed in this paper are those the author and do not necessarily reflect the views of the National Science Foundation.
References
[1] Riidd answer
correctness prediction. riiid-test-and teste-ssweer--eeeeee wwnswer-prediceee preppiciiinnnrr Accessed: 2022-05-11.
httpss://www..kgg// com/ c/
[2] Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. In International Conference on Machine Learning, pages 70-79. PMLR, 2018.
[3] Erling B Andersen. Conditional inference for multiple-choice questionnaires. British Journal of Mathematical and Statistical Psychology. 26(1):31 1973.
[4] Erling Andersen. Sufficient statisties and latent trait models. Psychometrika, 42(1):69-81, 1977.
[5] David Andrich. A rating formulation for ordered response categories. Psychometrika, 43(4):561- 573, 1978.
[6] Vahid Aryadoust, Li Ying Ng. and Hiroki Sayama. A comprehensive review of rasch measure- ment in language assessment: Recommendations and guidelines for research. Language Testing, 38(1):6-40, 2021.
[7] Debabrata Basu. On the elimination of nuisance parameters. In Selected Works of Debabrata Basu, pages 279 279-290. Springer, 2011.
[8] Yoav Bergner, Stefan Droschler, Gerd Kortemeyer, Saif Rayyan, Daniel Scaton, and David Pritchard. Model-basee collaborative filtering analysis of student response data: Machine- learning item response theory. International Educational Data Mining Society, 2012.
[9] A Lord Birbaum. Some latent trait models and their use in inferring an examinee's 's ability. Statistical theories of mental test scores, 1968.
[10] Justyna Brzezińska et al. Latent variable modelling and item response theory analyses in marketing research. Folia Oeconomica Stetinensia, 16(2):163-11) 174, 2016.
[11] Iván Cantador, Peter Brusilovsky, and Tsvi Kuflik. 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec 2011). In Proceedings of the 5th ACM conference on Recommender systems, RecSys 2011 I, New York, NY, USA, 2011. ACM.
[12] Chih-Ming Chen, Hahn-Ming Lee, and Ya-Hui Chen. Personalized e-learning system using item response theory. Computers & Education, 44(3):237-255, 2005,
10

---

[13] Pinhan Chen, Chao Gao, and Anderson Y Zhang. Partial recovery for top- ranking: Optimality of mle and sub-optimality of spectral method. arXiv preprint arXiv:2006.16645 2020.
[14] Yunxiao Chen, Chengcheng Li, and Gongjun Xu, A note on statistical inference for noisy incomplete 1-bit matrix. arXiv preprini arXiv:2105.0177 2021.
[15] Yunxiao Chen, Xiaoou Li, and Siliang Zhang. Joint maximum likelihood estimation for high-dimensional exploratory item factor analysis. Psychometrika, 84(1):124-146, 2019.
[16] Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang. Spectral method and regularized mle are both optimal for top-k ranking. Annals of statistics, 47(4))2204, 2019.
[17] Bruce Choppin. A fully conditional estimation procedure for rasch model parameters. 1982.
[18] Paulo Cortez and Alice Maria Gonçalves Silva. Using data mining to predict secondary school student performance. 2008.
[19] Mark A Davenport, Yaniv Plan, Ewout Van Den Berg, and Mary Wootters. 1-bit matrix completion. Information and Inference: A Journal of the IMA, 383):189-223 2014.
[20] Persi Diaconis and Laurent Saloff-Cosse Comparison theorems for reversible markov chains. The Annals of Applied Probability, (3):669-770,, 1993.
[21] Susan Embretson. A general latent trait model for response processes. Psychometrika, 49(2):175- 186, 1984.
[22] Gerhard H Fischer. On the existence and uniqueness of maximun-likelihood estimates in the rasch model. Psychometrika, 46(1):59-77, 1981.
[23] Mary Garner Jr. An eigenvector method for estimating item parameters of the dichotomous and polytomous rasch models. Journal of Applied Measurement, 3(2):107-128, 2002.
[24] Malay Ghosh. Inconsistent maximum likelihood estimators for the rasch model. Statistics & Probability Letters, 2352):1651170, 1995.
[25] Shelby J Haberman. Maximum likelihood estimates in exponential response models. The annals of statistics, 5(5):815 (55)815-841, 1977.
[26] Shelby Haberman. Joint and conditional maximum likelihood estimation for the rasch model for binary responses. ETS Research Report Series, 2004 (1 63:, 2004.
[27] Ronald K Hambleton, Hariharan Swaminathan, and H Jane Rogers. Fundamentals of item response theory, volume 2. Sage, 1991.
[28] Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm Iransactions interactive intelligent systems (fiis, 5(4):1-19, 2015.
[29] David R Hunter and Kenneth Lange. A tutorial on mm algorithms. The American Statistician, 58(1):30-37, 2004.
[30] Sadiq Hussain, Neama Abdulaziz Dahan, Fadl Mutaher Ba-Alwib, and Najoua Ribata. Edu- cational data mining and analysis of students' academic performance using weka. Indonesian Journal of Electrical Engineering and Computer Science, 9(2):477-455 2018.
[31] Denis Kotkov, Alan Medlar, Alexandr Maslov, Umesh Raj Satyal, Mats Neovius, and Dorota Glowacka. The tag genome dataset for books. In Proceedings of the 2022 ACM SIGIR Conference on Human Information Interaction and Retrieval (CHIRR'2) 22), volume 5, 2022.
[32] John P Lalor, Hao Wu, and Hong Yu. Learning latent parameters without human response patterns: Item response theory with artificial crowds. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. 2019.
[33] Andrew Lan, Mung Chiang, and Christoph Studer. An estimation and analysis framework for the rasch model. In International Conference on Machine Learning, pages 2883-2891. PMIR, 2018.
11

---

[34] Erich L Lehmann and George Casella. Theory of point estimation. Springer Science & Business Media, 2006.
[35] John Michael Linacre. Conditional maximum likelihood estimation.
[36] John Michael Linacre. Estimation methods: Jmle, prox, wmle, cmle, pmle, amle.
[37] Frederie M Lord. Applications of item response theory to practical testing problems. Routledge, 2012.
[38] Duncan Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2012.
[39] Geoff N Masters. A rasch model for partial credit scoring. Psychometrika, 47(2):149-174, 1982.
[40] Lucas Maystre. Choix: Inference algorithms for models based on luce's choice axiom. https 7/gi dggtthu.er comm//ucaasmasstrr//cooii 2015.
[41] Roderick P McDonald. Test theory: unified treatment. psychology press, 2013.
[42] Prathiba Natesan, Ratna Nandakumar, Tom Minka, and Jonathan D Rubright. Bayesian prior choice in irt estimation using meme and variational bayes. Frontiers in psychology, 7: 7:1422, 2016.
[43] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65(1):266-287, 2017.
[44] James Norris and James Robert Norris. Markoy chains. Number 2. Cambridge university press, 1998.
[45] Georg Rasch. Studies in mathematical psychology: probabilistic models for some intelligence and attainment tests. 1960.
[46] Alexander Robitzsch. A comprehensive simulation study of estimation methods for the rasch model. Stats, 4(4):814 13-8864,,,,,,, 2021.
[47] Pedro Rodriguez, Joe Barrow, Alexander Miserlis Hoyle, John P Lalor, Robin Jia, and Jordan Graber. Evaluation examples are not equally informative: How should that change nlp leaderboards? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Pupers), pages 4486-4503, 2021.
[48] Roseanna W Saaty. The analytic hierarchy process what it is and how it is used. Mathematical modelling, 933-5::111-17,, 1987.
[49] Ryan Sanchez. GIRTH: G. Item Response Theory, 11 2021.
[50] Carolin Schellhor and Rajneesh Sharma. Using the rasch model to rank firms by managerial ability. Managerial Finance, 2013.
[51] Wim Van der Linden and RK Hambleton. Handbook of item response theory. Taylor & Francis Group. Citado na pág, 1(7):8, 1997.
[52] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[53] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E, A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SeiPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272 2020.
12

---

[54] Jacob Whitehill, Ting-fan Wu, Jacob Bergsma, Javier Movellan, and Paul Ruvolo. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. Advances in neural information processing systems, 22, 2009.
[55]
Benjamin D Wright and Geofferey N Masters. Rating scale analysis. MESA press, 1982.
[56] Cai-Nicolas Ziegler, Sean M McNee, Joseph A Konstan, and Georg Lausen. Improving recommendation lists through topic diversification. In Proceedings of the 14th international conference World Wide Web, pages 22-32, 2005.
[57] Acilko H Zwinderman. Pairwise parameter estimation in rasch models. Applied Psychological Measurement, 19(4)339-3775 1995.
13


Reviews:
[{"review_id": "iCZm8ZowkZR", "reviewer": "Reviewer_L9zk", "summary": "This paper proposes a spectral estimation algorithm for item parameters in the 1PL item response (aka Rasch) model. The authors conducted theoretical analyses of the proposed algorithm in several scaling regimes, proposes a variant of their algorithm under practical constraints, and conducted experiments on real data to show that their method is on-par with existing algorithms in terms of estimation accuracy while being more computationally efficient. ", "questions": "1. Main concern: experiments. The experimental settings and results (on real data) are really underdiscussed, even in the supplementary material. The overall takeaway is a solid one - the proposed spectral algorithm is on-par with existing algorithms in terms of accuracy and is much faster, which is perfectly fine. However, some details give me a sense that some baselines are not properly treated. Some things that the authors can do to help are:\n- at least discuss what Bayesian estimation methods would do; more accurate when the prior is right? Too inefficient on large real world datasets? A simulation study where you know the real item parameter prior or experiments on one real world dataset would certainly help. \n- many datasets are not discussed (LSAT, UCI, 3GRADES) where the number of items is very very small. Here, AUC is the same for all methods. The experimental results are not thoroughly discussed; I'm a little unsure about the huge variation in terms of ranking performance since after all, these are different algorithms for the same underlying statistical model. The 0.0 results for top-K accuracy for some methods are a bit suspicious; it's not totally surprising, but more discussion is definitely needed. Otherwise, it's just really hard to properly evaluate how beneficial the proposed algorithm is in practice. \n- AUC scores for most methods are pretty close on most datasets, which makes perfect sense. However, the proposed method is obviously worse on BX; why?\n\n2. Some minor aspects of the presentation could be improved:\n- in the abstract, it's probably more accurate to call the proposed algorithm \"item parameter estimation\" instead of \"item estimation\"\n- line 32 \"educational testing\"\n- line 37JMLE does not really have to use an alternating maximization algorithm, right? The problem is jointly convex in the item and ability parameters\n- I would like to see Theorem 3.1 and 3.3 written with ||beta - beta*||_2/sqrt(m) on the left hand side - this quantity makes more sense in practice\n- Need to zoom into the small n regions in Figure 1. Lines are overalpping at times and it's hard to tell which is which. ", "limitations": "This field is not really applicable to this paper", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- Although spectral estimation has been thoroughly studied, its application to the Rasch model is novel\n- I liked the fact that the authors provided a version of their algorithm in practice where one can use a different normalization factor d for every item. This is important and likely helps a lot in terms of Markov chain convergence - a uniform d can be really bad for some items on real world datasets\n- I have not checked the proofs but the theoretical results and discussions seem sound\n\nWeaknesses:\n- ML is only one family of estimation methods but there are others, say posterior mean etc. I get that the proposed methods may be better than M/J/CMLE, which have their own problems for sure, but how would its accuracy/runtime compares to Bayesian methods is not clear. See below. \n- The experimental settings and results are not clear. See below. \n- The presentation could be improved in several places. See below. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "czKBB9agFID", "reviewer": "Reviewer_d3YA", "summary": "The paper proposes an inference algorithm based on a spectral estimation approach for estimation of the item parameter in the IRT model with finite-sample guarantees. The authors provide detailed convergence analyses and demonstrate the utility of the proposed estimator via both simulated and real-world datasets, on which the proposed approach achieves performance comparable to other estimators (e.g., MLE) at a fraction of the computational cost.", "questions": "Will and how does the algorithm generalize to settings in which student/user parameters need be estimated instead of sampled from a prior?", "limitations": "It seems that the proposed approach is applicable to only 1PL IRT model (Rasch model). Although still widely used, there are other, potentially more power, variants of the IRT models (e.g., 2 or 3 PL IRT models) and it is not quite clear whether or how the proposed algorithm generalizes to other IRT variants. This is a potential limitation, although not a main concern.\n\nThe proposed approach relies on prior distribution on the student parameter, i.e., the student parameters are not estimated. For applications where only item parameter estimations are needed, the proposed approach might be sufficient. In other, also common, settings where the student parameters also need be estimated, it is unclear how the proposed approach would be applicable.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper makes interesting theoretical contributions to the inference algorithm for IRT model. The algorithm is simple to implement and has finite-sample guarantees. The analyses are sound and the experiments corroborate with the analytical results. The proposed method is also competitive with other inference algorithms. I do not find major weaknesses; some suggestions are outlined in the \"limitations\" part.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cvCM9-W1LV3", "reviewer": "Reviewer_LyYF", "summary": "This paper develops a spectral algorithm for estimating the item parameters in the Rasch item response model.\n\nThe authors show that the proposed estimator is consistent, and they provide finite-sample error bounds that are (near-)optimal.\n\nEmpirically, the authors show that their approach performs favorably in comparison to existing estimators: Predictive performance is on par or better, and the algorithms typically runs faster than competing approaches.", "questions": "- Why is the MMLE so bad in the Top-K case, depsite achieving good AUC and log-likelihood? (I don't understand the caption of Table 1).\n- Can you comment to what extent the proofs of Thms 3.1 and 3.2. mirror the proofs in Rank Centrality paper for the BTL model?", "limitations": "Limitations are adequately addressed.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The Rasch model is widely used, and the problem addressed by this paper is very relevant to the NeurIPS community.\n- The theoretical contributions are comprehensive and address a number of important questions that remain mostly open for other estimators for the Rasch model: consistency, finite-sample error, optimality.\n- In practice, the algorithm is simple to understand and to implement, and performs favorably. As such, the paper's contributions also relevant to practitioners.\n- Beyond the specific results presented by the author, this paper also provides a bridge between the literature on spectral algorithms for the Bradley-Terry model and the Rasch model. I expect this paper to unlock further research on the topic.\n- The experimental evaluation is excellent. The illustration of failure cases (Fig. 1) for various estimators is helpful in understanding the trade-offs that different methods have. The real-data experiments are thorough, and also include datasets and metrics where there is not necessarily a clear advantage for their proposal, giving a balanced picture of the empirical benefits.\n- The paper is well-written and easy to follow. Throughout the paper, the authors strike a good balance between building intuition and formalizing their claims.\n\nAltogether, the combination of these strengths make for a significant contribution that will have impact on ML researchers and practioners.\n\nWeaknesses\n\n- Theorems 3.5 and 3.6 appear to be missing something. Clearly setting $\\beta^* = 0$ and $T(X) = 0$ achieves zero error (and satisfies the unbiasedness assumption). Perhaps $\\beta^*$ needs to be bound, e.g., by taking the supremum over a certain range. Similarly, it is not clear what the expectation is over (I read it to be over $X$ but this could be made explicit).\n- There is no discussion about the existence and uniqueness of the estimator, i.e., of the stationary distribution of (3). This needs to be formalized more rigorously. Under what conditions on `X` does the spectral estimate exist? How do Algorithms 1 & 2 handle cases where this condition is not satisfied?\n- The similarities and differences to existing pairwise & spectral approaches for the Rasch model should be emphasized in the main text. Reading through Appendix D, it is apparent that the differences are major, but this was not clear in the main text (beyond the brief comment in the introduction about dense vs. sparse matrices). I strongly suggest making use of any additional space to move parts of Appendix D to the main text. Finally, statements like that of line 135, \"our algorithm instantiates the general spectral approach [...]\" are slightly misleading, given prior work.\n\nThese weaknesses are relatively minor and I believe they can be addressed in a camera-ready version.\n\nSmall comments:\n\n- I am surprised that Agarwal et al. [2] is not cited in Section 4, \"accelerating the spectral algorithm\".\n- Paragraph starting on line 50: an explicit expression for the CMLE would be helpful; it is hard to understand what the \"likelihood conditioned on $\\{ s_l \\} $\" looks like.\n- l. 60: later -> latter\n- l.116 and 204: practicioners -> practitioners", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QyiB-XjL4pi", "reviewer": "Reviewer_evfB", "summary": "UPDATE: I increased my score based on the authors' response for noted in my counter-response.\n\nThe paper presents a novel representation of the statistical correlation between items in a 1PL (Rasch) IRT model that allows faster and (empirically) more accurate estimation of the underlying item difficulties (beta).  By embedding the items in a Markov Chain and calculating its stationary distribution, the authors are able to prove finite sample complexity bounds, which I believe is a first for such a method.  They provide extensions that speed up learning by using different normalization constants for each item and also add a regularization term to handle sparsity in real datasets.  Their empirical results show either parity or improvement against existing methods with an order-of-magnitude speedup against the most-accurate competitor.", "questions": "From the review, how does the new approach expand our capabilities in the 2PL/3PL or MIRT case?  \n\nThe authors cite several other spectral methods but do not make clear if any of the theoretical results come from those papers. Is Proposition 2.1 specific to the current paper or was it proved in one of the earlier works?\n\nFor Theorem 3.3 (where m grows) the authors need to describe to this audience why JMLE fails in this case and what is different about their algorithm that makes it succeed.\n\nIn accordance with Neurips guidelines on AI ethics, the authors should provide in their response a more detailed description of potential biases in this method compared to existing IRT approaches and clearly spell out possible negative societal impacts.", "limitations": "Beyond the missing extensions above I do think a discussion of ethics is necessary for this paper to be published, given Neurips's dedication to the topic.  I understand the work here is purely theoretical so I didn't flag it for ethics review below, but the application domain for this IRT method is evaluating children.  So any systematic errors or biases in the new approach need to be spelled out much more clearly.  The authors should provide in their response a more detailed description of potential biases in this method compared to existing IRT approaches and clearly spell out possible negative societal impacts.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides a very thorough analysis of the spectral approach in the Rasch model case.  I have some questions below about the differentiation to other spectral methods and some terms and definitions but overall those are minor and I think the analysis in the Rasch case is first rate.  The theorems look correct to my reading and exploring the connection between a MC's  stationary distribution and the overall item difficulty parameters is a clever choice.  I also liked the real-world practitioner extensions with variable normalization and regularization which make the algorithm truly applicable to the always-way-to-sparse item response data.\n\n However, I was disappointed that the authors did not mention or attempt to extend their approach to more modern IRT models including 3PL (where items have 3 axes of rating, not just difficulty) or multivariate IRT (where there are multiple thetas, for instance a student’s ability adding fractions and their ability to calculate percentages).  These more modern models are often calibrated using machine learning techniques (see below) and have far more intense computational burdens than Rasch so it is disappointing to not see at least a proposed extension to those cases.\n\nMore specifically, if we move to just 2-PL, how would the edges in the spectral embedding (the probability of transitions) represent both item parameters?  Could this be done using a factored Markov chain or some other more complicated graphical model?  Or is the spectral approach limited to only a single item-difficulty parameter? \n\nIn the case of MIRT, we have seen recent successes of machine learning methods that use pairwise item comparisons to advance the very difficult problem of calibrating IRT models, see:\n“Multidimensional Item Response Theory in the Style of Collaborative Filtering” (https://link.springer.com/article/10.1007/s11336-021-09788-9) as an example.  Since computational burdens are much larger with MIRT I would like to know if the computational advances in the Rasch have repercussions in that space?\n\nReturning to the Rasch case and the results in the paper, I found the spectral embedding clever and a unique statistical approach for solving this problem.  I very much appreciate the finite-sample complexity bounds in the paper.  There are, however, are several places where I would like to see clarifications:\n\nThe authors cite several other spectral methods but do not make clear if any of the theoretical results come from those papers. Is Proposition 2.1 specific to the current paper or was it proved in one of the earlier works?\n\nFor Theorem 3.3 (where m grows) the authors need to describe to this audience why JMLE fails in this case and what is different about their algorithm that makes it succeed.\n\nTable 1 needs to be reformatted to fit the margins.  Also, the authors should make a bigger deal about the speedup compared to MMLE.  It’s not just faster, the new method is an order of magnitude quicker.\n\nI found Section 6 unhelpful and it seemed to be trying to justify why this paper fits at NeurIps by describing tangentially related problems.  I know there are connections to general logistic regression problems here but this section would be better used describing more complex IRT models like MIRT and how the approach could be used there.  In terms of fit at Neurips, I think the paper is ok as a statistical learning theory approach that models a psychological phenomenon although ultimately this result belongs in a Psychometrics journal to be really picked up by practitioners.\n \nMinor points:\n\nLines 29 and 30: citations needed for these claims\n\nLine 31: “Traditionally, the goal of estimation under the Rasch model is to recover the item parameters” … No, the goal is to assess the mastery parameters theta – at the end of the day we want to know whether students have certain skills or not.  Calculating beta values are a means to that end but they are not the goal.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept