FIELD

This application relates in general to prediction (classification and regression), and in particular to a system and method for relational time series learning with the aid of a digital computer.

BACKGROUND

Determining a classification associated with an entity, such as a person, an organization, an object, or an organization can have tremendous importance and numerous applications. For example, if upon admission to a hospital, a person can be classified as having certain risk factors for developing certain diseases, the risk factors can be used during diagnosis of that person's medical conditions. Of a similar value can be the prediction of the class label of an entity or an object in the future, with the knowledge of the future predicted class label to allow for the planning of the future (e.g., forecasting tasks). Such tasks are commonly accomplished by separate families of techniques. For example, traditional time series forecasting focuses on predicting the value of a future point in a time series. Similarly, one of the goals of relational learning, also known as statistical relational learning, is classifying an object based on the object's attributes and relations to other objects.

While the two families of techniques can be applied to data represented as a graph, the techniques have drawbacks that limit their usefulness. For instance, traditional time series forecasting techniques, such as those described in Box, G. E., G. M. Jenkins, and G. C. Reinsel. “Time Series Analysis: Forecasting and Control.” John Wiley & Sons (2013), the disclosure of which is incorporated by reference, only consider a single time series. In the context of data represented as a graph, such techniques consider only a single node of the graph, representing a single entity, without considering edges that represent the connections of that entity to other entities. In other words, these techniques assume independence among the time series. Multiple possible reasons exist for this approach, such as the amount of observed data being limited and only a single time series being available. Further, in many situations, the dependence between the time series is unknown or unobservable. For example, such dependence may not be observable when data points in a time series are collected independently from each other, such as when the data points represent distinct variables such as wind speed and temperature.

Likewise, traditional multivariate time series forecasting techniques, which account for interrelatedness of time series, also have limited use. Most of the existing models are based on a fundamental assumption that the time series being processed are pairwise dependent or strongly correlated with each other. Thus, these models assume that the each of the time series represents a node in a graph and each node has an edge to every other node in the graph, forming a clique of the size of the number of nodes in the graph. When the assumption is incorrect, the results produced by such techniques can be inaccurate.

On the other hand, statistical relational learning techniques, such as those described by Taskar, Ben, and Lise Getoor “Introduction to statistical relational learning,” MIT Press (2007) and Rossi, Ryan A., et al. “Transforming graph data for statistical relational learning.” Journal of Artificial Intelligence Research 45.1 (2012): 363-441, the disclosures of which are incorporated by reference, generally focus on static graphs, graphs representing connections between entities at a single time point and ignore any temporal relational information. Such techniques cannot predict a future classification of an entity represented by a node in a graph.

Accordingly, there is a need for a way to be able to assign a classification at multiple time points to a data item included as part of multiple type of graphs. There is a further need for improved ways to perform relational and non-relational classification of data items.

SUMMARY

Relational time series forecasting is a task at the intersection of traditional time series forecasting and relational learning, having the potential to allow predicting the classification of a data item at a plurality of time points. Unlike traditional time series forecasting models that are built for single time series data or multi-variate time series data and which assume either complete time series independence or complete dependence, the system and methods described below allow time series forecasting to be performed on multivariate time series represented as vertices in graphs with arbitrary structures as well as the prediction of a future class label for data points represented by vertices in a graph. The system and methods also utilize non-relational, relational, temporal data for classification, and allow using fast and parallel classification techniques with linear speedups. The system and methods are well-suited for processing data in a streaming or online setting and naturally handle training data with skewed or unbalanced class labels. In addition, the system and method can process both sparse and dense matrix data.

A class of (parallel) systems and methods for relational time series classification are provided. In one embodiment, a system for relational time series learning with the aid of a digital computer is provided. The system includes a database configured to store a plurality of training data items, each of the training data items associated with one of a plurality of labels; and at least one server including a plurality of processing units executed by one or more processors, each of the processing units associated with a private vector. The at least one server is configured to: receive an unlabeled data item; process the unlabeled data item using the plurality of processing units, each of the units associated with a private vector, including: initialize the private vectors; calculate in parallel by the processing units a similarity score between the unlabeled data item and one or more of the training data items using a similarity function and store each of the scores into the private vector associated with each of the processing units; sum the scores from all of the private vectors into a storage vector; and assign the label associated with the largest score as the label of the unlabeled data item.

In a further embodiment, a system for relational classification via maximum similarity with the aid of a digital computer is provided. The system includes a database configured to store a plurality of training data items, each of the training data items associated with one of a plurality of labels; and at least one server including a plurality of processing units executed by one or more processors, each of the processing units associated with a private vector. The at least one server is configured to: receive at least one unlabeled data item; create a graph comprising a plurality of vertices, wherein the unlabeled data item and each of the training data items are represented by one of the vertices; process the unlabeled data item using a plurality of processing units executed by one or more processors, each of the units associated with a private vector, including: identify those of the training data items whose representations in the graph are within k-hops of the representations of the unlabeled data item; initialize the private vectors; calculate in parallel by the processing units a similarity score between the unlabeled data item and each of the training data items using a similarity function and store each of the scores into the private vector associated with each of the processing units; weigh the similarity scores, wherein the similarity scores between the unlabeled data item and those of the training data items that are within the k-hops of that unlabeled data item are weighed heavier than the similarity scores between the unlabeled data item and those of the training data items that are not within the k-hops; sum the weighed scores from all of the private vectors into a storage vector; and assign the label associated with the largest score as the label of the unlabeled data item.

In a still further embodiment, a system for relational time series learning with the aid of a digital computer is provided. The system includes a database configured to store a plurality of training data items, each associated with data regarding attributes of that training data item and connections of that training data items at the plurality of the time points; and at least one server including a plurality of processing units executed by one or more processors, each of the processing units associated with a private vector, the at least one server configured to: receive at least one unlabeled data item associated with data regarding attributes of the unlabeled data items and connections of the unlabeled data items at a plurality of time points; obtain a plurality of adjacency matrices, each of the matrices representing a graph comprising a plurality of vertices connected by one or more edges, wherein the unlabeled data item and each of the training data items are represented by one of the vertices, each of the graphs further representing the connections between the training data items and the unlabeled data item at one of the time points; associate a weight with each of the edges of each of the graphs based on the time point associated with that graph and combine the representations of the graphs with the weighted edges to create a representation of a summary graph; smooth the attributes of the training data items and the unlabeled data items for all of the time points; identify those of the training data items whose representations are within k-hops of the representations of each of the data items in the summary graph; process the unlabeled data item using a plurality of processing units executed by one or more processors, each of the units associated with a private vector, including: initialize the private vectors; calculate in parallel by the processing units a similarity score between the unlabeled data item and one or more of the identified training data items using a similarity function and store each of the scores into the private vector associated with each of the processing units; weigh the similarity scores, wherein the similarity scores between that unlabeled data item and those of the training data items that are within the k-hops of that unlabeled data item are weighed heavier than the similarity scores between that unlabeled data item and those of that are training data items that are not within the k-hops; sum the weighted scores from all of the private vectors into a storage vector; and predict the label associated with the incoming data item based on the scores associated with the label at a future point of time.

Still other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is described embodiments of the invention by way of illustrating the best mode contemplated for carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the spirit and the scope of the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.

