Abstract
We introduce relational grams (r-grams). They upgrade n-grams for modeling relational sequences of atoms. As n-grams, r-grams are based on smoothed n-th order Markov chains. Smoothed distributions can be obtained by decreasing the order of the Markov chain as well as by relational generalization of the r-gram. To avoid sampling object identifiers in sequences, r-grams are generative models at the level of variablized sequences with local object identity constraints. These sequences define equivalence classes of ground sequences, in which elements are identical up to local identifier renaming. The proposed technique is evaluated in several domains, including mobile phone communication logs, Unix shell user modeling, and protein fold prediction based on secondary protein structure.
Introduction
Traditional sequence models, such as n-grams, are foundational to natural language processing. They predict the next symbol in a sequence based on a fixed history of $n-1$ symbols. However, these models struggle significantly with relational data. In domains like mobile phone logs or system traces, the specific identity of an object (e.g., a phone number or a process ID) often matters less than its relationship to other events in the sequence.
Standard n-grams treat every unique identifier as a distinct symbol. If a model encounters a new identifier during testing that was absent from the training set, it fails to generalize. Furthermore, n-grams are "flat" and cannot easily capture patterns like "calling the same person back" if the specific ID changes. To address this, we propose r-grams (Relational Grams), which extend n-grams using concepts from Inductive Logic Programming (ILP).
The r-gram Framework
r-grams upgrade the traditional alphabet of symbols to an alphabet of relational atoms, such as outcall(ID, status). By utilizing logical variables (e.g., $X, Y$) and unification, r-grams can define patterns that generalize across specific identifiers. For instance, a pattern like outtxt(X) ← outcall(X, fail) captures the behavior of texting a contact after a failed call, regardless of who the contact is.
Sequence Congruence and Generative Modeling
A core innovation of r-grams is the concept of sequence congruence. We treat sequences as equivalent if they are identical up to the renaming of identifiers. This prevents the model from overfitting to specific ground IDs and allows it to focus on the underlying "grammar" of interactions. The paper defines a formal generative process that samples these variablized sequences, ensuring the model is mathematically sound for classification and prediction tasks.
Logical Smoothing
In traditional n-grams, sparsity is handled by "smoothing"—dropping the order of the Markov chain (e.g., moving from a trigram to a bigram). r-grams introduce relational generalization as a more surgical smoothing technique. If a specific sequence like helix(right, alpha, short) is rare, the model can generalize to helix(X, alpha, Y), maintaining the essential structural type while abstracting away specific attributes.
Experimental Evaluation
We evaluated r-grams across three distinct real-world domains to test their versatility and accuracy:
- Unix Shell Logs: Traces from 168 users were used to classify users as "novice" or "non-programmer."
- Protein Fold Prediction: Sequences of secondary structures (helices and strands) were classified into one of five structural folds.
- Context Phone Data: Real-world Nokia smartphone logs were used for two tasks: distinguishing real logs from corrupted ones (Phone I) and identifying specific users based on communication patterns without knowing actual phone numbers (Phone II).
Key Results and Insights
r-grams demonstrated superior performance compared to traditional n-grams and competitive results against more complex specialized models.
- The ID Advantage: As shown in the comparative results, r-grams significantly outperformed n-grams that ignored identifiers (n-grams w/o IDs). This confirms that capturing the re-occurrence of identifiers within a local window is a crucial signal for behavioral modeling.
- Competitive Accuracy: In the Protein Folding task, r-grams achieved 83.3% accuracy, outperforming Logical Hidden Markov Models (LOHMMs) and matching specialized Fisher kernels. In Unix Shell modeling, r-grams reached 97.2% accuracy, beating k-Nearest Neighbor and C4.5 decision tree baselines.
- Efficiency: Despite the added logical complexity, training times remained low (ranging from 3 to 240 seconds), making r-grams practical for real-time AI applications.
Conclusion
r-grams provide a powerful framework for sequence modeling in relational domains. By abstracting specific identifiers into logical variables and employing relational smoothing, they overcome the data sparsity issues that plague traditional n-grams. Future work will explore more advanced back-off smoothing techniques and extending the framework to handle nested structured terms, further enhancing their utility for complex artificial intelligence tasks.
Summary updated