In this paper we apply ideas from collaborative ltering to the problem of building dynamic Bayesian network (DBN) models for planning. We demonstrate that item-based collaborative ltering can be used to construct dynamic Bayesian networks for use in large, factored domains with sparse data. Such Bayesian networks can model the transition function for decision-theoretic planning. We demonstrate the feasibility and effectiveness of this technique on an academic advising domain, based on student grades in computer science and related courses at the University of Kentucky.
Collaborative ltering (CF) algorithms are designed to aggregate the opinions or preferences of a large number of users to extrapolate information about unnamed preferences for new and existing users. Recommendation systems are constructed using CF techniques to locate items in a database which a target user is likely to prefer. Preferences are typically de ned by grades that the user provides either explicitly (by the user providing grades for items that have already seen) or implicitly (often indicated by patterns of behavior such as browsing habits). These grades can be represented in a number of ways, but are often numerical in nature; most recommender systems ask for a numerical
This material is based upon work supported by the National Science Foundation under Grant No. 1049360. grade (1{5) or a grade based on letters or \stars" which is easily mapped to numerical grade (for instance 1{5 stars, or a letter grade of A{E).
CF algorithms can be roughly divided into
modelbased and memory-based algorithms. Model-based
algorithms involve generating a predictive model based
on the data and using it to make preference-related
predictions. One formalism that has seen success in
model-based CF is the Bayesian network [
Reasoning in the domain of undergraduate academic advising is often approached as a deterministic process. Short and long-term decision making is based on the assumption that a student's actions (i.e., taking one or more courses) will succeed. This doesn't capture the nuances and complexity of the real world. The outcome of taking a course can not always be predicted with certainty; even a student who makes consistent A's may perform poorly at some point.
Given the stochastic nature of grade prediction, it may be desirable to construct statistics-based models of student performance from real world data. Students leave behind tangible evidence of progress in the form of transcript data. Universities amass a wealth of data with which to make predictions about grades. From this we can construct probabilistic predictive models. The Dynamic Bayesian Network (DBN) formalism has a number of features which make it ideal for this sort of modeling.
A DBN model consists of a directed acyclic graph with
links representing temporal, probabilistic relationships
between variables and conditional probability tables
(CPTs) that specify those relationships quantitatively
[
The structural restrictions imposed on 2-slice DBNs make them a potentially compact representation for decision theoretic planning. For this reason we limit our attention to 2-slice DBNs.
In the case of discrete-valued variables, each child node in the DBN has an associated conditional probability table (CPT) which gives a probability distribution over possible values for every possible assignment to parent variables (incoming edges in the graph) at a previous time-step. Because all possible assignments to parent variables may need to be enumerated explicitly, CPT size is exponential in the number of parent variables. For example, a CPT for a single course with 5 parents, each of which has 6 possible values (A{D, Failure, and NOT TAKEN) will have 65 = 7; 776 rows, each containing a probability distribution over the 6 possible outcomes.
For modern computers, tables of this size are unlikely to cause representational issues. However the need for enough data to populate a table's 66 = 46; 656 probabilities makes seemingly abundant data seem rather sparse. Popular or required courses may be taken by hundreds or even thousands of students within the span of several years, but even this is insu cient to derive realistic probability distributions from straight statistical analysis. This problem is worse for most courses (and for smaller colleges and universities) where enrollment over several years may reach only hundreds of students or fewer.
In order to deal with the problem of prediction when
data is sparse, we turn to techniques from collaborative
ltering to aggregate the data that is available.
Collaborative ltering algorithms are commonly used to
narrow down choices based on a user's preferences and
the preferences of current and past users. A common
example application is predicting preferences over
unseen items (movies, music, groceries) based on grades
given for other items [
The problem of grade prediction very closely resembles the problem of grade prediction in collaborative ltering: make predictions about a student's grades in untaken courses, given their past grades and the transcript data from many past students. Letter \grades" can map directly to integers where A=1 and Failure=5.
In this paper we present a simple collaborative ltering algorithm, and demonstrate how it is used to generate a valid DBN model of state transitions in the advising domain. We use real-world data from the Computer Science Department at our university as a testbed for our model generation techniques. 3 3.1
A Bayesian network is a directed acyclic graph G = hV; Ei, where each vertex v 2 V is a variable with domain dom(v). Each v 2 V has an associated probability distribution over values in dom(v), conditioned on the values of P av V , the parents of v. These conditional probability distributions are usually enumerated in tabular form as conditional probability tables (CPTs) for each variable.
Learning of Bayesian networks is often divided into structure learning and parameter learning. Structure learning is the problem of learning the graphical structure E by discovering predictive or causal dependencies between variables. Parameter learning is the problem of learning the conditional probability distributions for a given network structure.
Because the space of all possible networks is very large,
structure learning is usually approached as a heuristic
search problem or an exact search of a constrained
version of the search space (see [
Unlike most Bayesian network learning algorithms, our DISC INUM LTC validation is based on the quality of predictions rather than of inference. In other words, our work looks forward in time rather than backward. We conjecture that good learned probabilistic planning models may actually di er from probabilistic inference models learned from the same data. 3.2
Bayesian networks have been demonstrated to be useful for inference in a number of domains, however the standard framework does not have an explicit notion of time. A dynamic Bayesian network builds upon the Bayesian network idea, incorporating temporal or sequential aspects of data into its structure. Variables at one time-step may in uence the value of variables at future time-steps (or at the same time-step). We are interested in a special case of dynamic Bayesian networks, the 2-slice dynamic Bayesian network. A 2slice dynamic Bayesian network is a Bayesian network with V = V; V 0, representing variables at time t and t + 1, and edges from V to V 0 (and sometimes between vertices in V 0). In DBNs of this form, V and V 0 may be visualized as two separate columns representing, respectively, the variables at time t and t + 1. This structural formulation implies two theoretical assumptions under which we operate. These are a stationary assumption where models are not timedependant and a Markov assumption where there is no memory of past states; future values are conditioned only over the current system state.
Figure 1 gives the structure of an example of a 2-slice
DBN which could be used for planning in an academic
domain. This DBN structure shows that the expected
grade in Logic and Theory of Computing (LTC) is
conditioned over the grades obtained in Introduction to
Programming (INTR), Discrete Mathematics (DISC),
and Introduction to Numerical Methods (INUM).
Rather than selecting a single ideal structural size we
choose to make structure size a parameter of our
algorithm. Since we are considering models for the
purpose of planning, we must consider the tradeo
between accuracy of the representation and tractability
of planning. Our goal is to be able to generate DBNs
of di erent sizes for di erent purposes. We examine
how our algorithm fares as a function of structure size
in Section 5. At this point we are left with the question
of how to select n parent nodes for each node.
Goldenberg et al. approached a similar problem of
learning Bayesian network structures from sparse data
using frequent set mining [
Rather than using co-occurance we make the assumption that similar variables make better predictors than dissimilar variables. We examine the use of pairwise item similarity in selecting parent nodes. Item similarity is commonly used in collaborative ltering and other data mining applications to determine which items hold the most predictive power for a target item, allowing for better predictions to be made.
One of the most common approaches for collaborative
ltering is to use the database of user grades to
determine item-item similarity. For each pair of items in
the database a vector of grades is created (retaining
only grades where users voted for both items) [
Collaborative ltering recommendation algorithms
typically fall into one of two general categories:
modelbased algorithms and memory-based algorithms [
The collaborative ltering algorithm that we used in
this paper is an item-based algorithm presented by
Sarwar et al. [
Pall similar items;N (si;N
P all similar items;N(jsi;N j)
Ru;N ) : (1) Here, pu;i is the predicted grade that user u might give item i, si;N is the similarity between items i and N , and Ru;N is the grade that u provided for item N . Equation 1 produces a single, most likely grade for the given user and item. Because a DBN requires a probability distribution over all possible grades, we are not yet ready to encode our DBNs. 4
The CF algorithm based on the function pu;i described in Section 3.4 de nes a deterministic version of the DBN CPTs that we want to generate. We use these predictions and the data from past students' transcripts to generate probability distributions over possible grades to produce full CPTs. Algorithm 1 describes the process of turning deterministic predictions from pu;i into CPTs.
In this algorithm we make the assumption that deviation from predictions in past data will produce a distribution which is a reasonable approximation of the probability distribution.
Given the predictions from the CF function described in 4, we build a distribution table, grade distribution, for the set of items with rows and columns indexed by predicted and actual grades. If G1 and G2 are possible grades, then the grade distribution[G1][G2] entry in the table is the number of transcripts for which the CF algorithm predicted G1 and the student received G2 for the class in question.
After we construct grade distribution we normalize each row of the table to form probability distributions. For a grade g, row grade distribution[g] is now a probability distribution over actual grades when R predicts g.
Input: Past Users - a database of past user grades. Output: CPT - A set of CPTs for each course foreach user in Past Users do foreach item in user's graded items do p = puser;item; actual = actual grade for item; grade distribution[p][actual]++; end end normalize rows of grade distribution; foreach item do
T = create prediction table for item; foreach row in T do u* = temporary user using grade assignments in row; p = puser;item; add distribution from grade distribution[p] to current row of T; end
CPT(course) = T; end Algorithm 1: Generate DBNs from CF predictions The second half of our algorithm constructs a set of prediction tables for each course. A prediction table T for a course c re ects the overall structure of a nal CPT for c; each row of T contains a set of values for parent variables (de ned by and our distance metric). For each row of T , we ll in the probability distribution over grades using the appropriate row of grade distribution.
Each row of the prediction table T implies a hypothetical user transcript as an assignment over past grades. Using R we can make a prediction p for each row. We select a probability distribution from grade distribution[p], adding probability distributions over grades to each row of T .
After completion, CP T is a set of CPTs for each course, where CP T (c) is the CP T for course c. 5
In this section we describe the tests we run on the academic advising data. We evaluate the two variants of the item-based collaborative ltering algorithm on this dataset. We also generate two baseline DBN models and two collaborative ltering based models, and analyze their performance on this dataset. Models are generated from the transcript data for approximately 4760 undergraduate students who enrolled during the 2000{2003 academic years. These anonymized data are a time-stamped (semester and year) series of transactions labeled with course and instructor information and grade outcomes. Because we have meta-data from computer science courses, we restricted our attention to students who took computer science courses during their academic careers. Our analysis is broken down into two steps: collaborative ltering evaluation and DBN evaluation. We chose to evaluate the item-based collaborative ltering algorithm rst to give a measurement of the algorithm's performance on an academic dataset. Testing of both collaborative ltering and DBNs is performed using 10-fold cross validation (partitioned randomly). We are looking at two methods for evaluating the itembased collaborative ltering algorithm on this dataset: mean absolute error and the percent of misclassi ed predictions. Together, these statistics give us an indication of how far predictions are from actual grades and how often predictions are misclassi ed, respectively. We selected these statistics because they are fairly straightforward to interpret, and because mean absolute error has been used in the past for collaborative ltering evaluation, allowing comparison to performance on other datasets.
As a baseline for comparison of our 2-slice DBNs we
generated baseline DBNs using more standard
techniques. Baseline DBN structures were found through
exhaustive search of the network structure space,
using Bayesian information criterion (BIC) [
Figure 3 shows how the percent of misclassi ed predictions changes as neighborhood size increases. At rst there is an abrupt jump in this percent, however afterward this curve resembles the curve for mean absolute error, with an apparent ideal neighborhood size of about 15 neighbors. In terms of minimizing loss (Figure 4), the maximumlikelihood, Pearson, and cosine models show similar performance. At a neighborhood size of 2, these models have a log-likelihood loss tightly clustered around 1.14{1.16. Loss shows a steady decrease as the neighborhood size increases. However, the Bayesian model appears unable to cope with increasing neighborhood size, showing an increasing loss. This is likely due to the sparsity of data, and the increase in the possible number of con gurations that corresponds with an increased neighborhood size.
Classi cation accuracy (Figure 4) shows steady
improvement as neighborhood size increases across all
models, with collaborative ltering models showing
much better accuracy than Bayes and
maximumlikelihood models at all neighborhood sizes. At a
neighborhood size of only one the Pearson and
cosine models show comparable accuracy (48.74-49.45%
misclassi ed respectively) to the ML model Bayesian
model at a neighborhood size of 5 (49.52%
misclassied) and 7 (49.47% misclassi ed), respectively. At a
neighborhood size of 10, the Pearson model shows the
lowest misclassi cation rate at approximately 42.18%.
Comparing Figures 3 and 5, we nd that at 6-7 parent
variables, our baseline DBNs outperformed the
itembased collaborative ltering algorithm. This is
consistent with other experiments that demonstrated that
Bayesian methods of classi cation showed better
results than the standard item-based algorithm [
6 Neighborhood size 8 10 grades deviated from actual grades on a per-item basis (as we did with CPT generation in algorithm 1) one may be able to construct a better collaborative ltering algorithm.
Across all tests the Pearson model showed a slight advantage over the cosine model. This indicates that improvements in the item-based collaborative ltering used to generate DBNs may lead to improvements in resulting DBN models. 6
Our goal is to develop DBN transition models for the purpose of decision-theoretic planning. In this paper we have presented a novel approach for generating DBN planning models from sparse data. We used academic advising data to show the validity of our method. One of the bene ts of this method is the exibility regarding the use of collaborative ltering recommendation algorithms. Our models were constructed using a generic item-based collaborative ltering algorithm. Any similar item-based collaborative ltering algorithm can be used in its place, giving us a wide variety of algorithms which can be employed using o -the-shelf software packages.
We are also investigating methods for modeling utility in this and similar domains, as well as decisiontheoretic planning algorithms that can run on domains of the size and complexity presented here, and larger.
We thank the University's SSTARS lab consultants for assistance with statistical analysis. We also thank Nick Mattei, Robert Crawford, Daniel Michler and other members of our lab for their contributions to this and related projects.