FOLD-TR: A Scalable and Efficient Inductive Learning Algorithm for Learning To Rank

Dramatic success of machine learning has led to a torrent of Artificial Intelligence (AI) applications. However, the effectiveness of these systems is limited by the machines’ current inability to explain their decisions and actions to human users. That’s mainly because the statistical machine learning methods produce models that are complex algebraic solutions to optimization problems such as risk minimization or geometric margin maximization. Lack of intuitive descriptions makes it hard for users to understand and verify the underlying rules that govern the model. Also, these methods cannot produce a justification for a prediction they arrive at for a new data sample.

The Explainable AI program (?) aims to create a suite of machine learning techniques that: a) Produce more explainable models, while maintaining a high level of prediction accuracy. b) Enable human users to understand, appropriately trust, and effectively manage the emerging generation of artificially intelligent partners. Inductive Logic Programming (ILP) (?) is one Machine Learning technique where the learned model is in the form of logic programming rules (Horn Clauses) that are comprehensible to humans. It allows the background knowledge to be incrementally extended without requiring the entire model to be re-learned. Meanwhile, the comprehensibility of symbolic rules makes it easier for users to understand and verify induced models and refine them.

The ILP learning problem can be regarded as a search problem for a set of clauses that deduce the training examples. The search is performed either top down or bottom-up. A bottom-up approach builds most-specific clauses from the training examples and searches the hypothesis space by using generalization. This approach is not applicable to large-scale datasets, nor it can incorporate negation-as-failure into the hypotheses. A survey of bottom-up ILP systems and their shortcomings can be found at (?). In contrast, top-down approach starts with the most general clause and then specializes it. A top-down algorithm guided by heuristics is better suited for large-scale and/or noisy datasets (?).

Learning To Rank (LTR) or Machine Learned Ranking (MLR) is a classical machine learning application that has been widely used in information retrieval systems, recommendation systems, and search engines. The training data for LTR is a set of items with explicit or implicit partial order specified between items. The goal of training a LTR model is to rank new items in the similar pattern from the training data. In practice, the LTR model retrieves a list of documents based on a given query. Generally, there are three approaches to build the LTR model: 1) Pointwise approach which assumes that each query-document pair has a numerical score. In this case, the LTR problem can be approximated by a regression problem. 2) Pairwise approach which employs binary classifiers to predict which is better in a given pair of documents based on the query. 3). Listwise approach which aim to optimize the result list directly based on the evaluation metrics.

The FOIL algorithm by Quinlan is a popular top-down inductive logic programming algorithm that learns a logic program. The FOLD algorithm by Shakerin et al is a novel top-down algorithm that learns default rules along with exception(s) that closely model human thinking, as explained by (?). It first learns default predicates that cover positive examples while avoiding covering negative examples. Then it swaps the covered positive examples and negative examples and calls itself recursively to learn the exception to the default. It repeats this process to learn exceptions to exceptions, exceptions to exceptions to exceptions, and so on. The FOLD-R++ algorithm by (?) is a new scalable ILP algorithm that builds upon the FOLD algorithm to deal with the efficiency and scalability issues of the FOLD and FOIL algorithms. It introduces the prefix sum computation and other optimizations to speed up the learning process while providing human-friendly explanation for its prediction.

To introduce explainability to the LTR tasks, we customizes the FOLD-R++ algorithm as the binary classifier in the Pairwise approach to build the comparison function for the training data based on the partial order specified between training items. We call this customized FOLD-R++ algorithm with the ranking framework as FOLD-TR algorithm. The new approach inherits the features of the FOLD-R++ algorithm, it is able to handle mixed type data directly without any data encoding. The new approach generates normal logic rule sets as explainable solutions and native explanation for its prediction.

The FOLD-R++ algorithm is summarized in Algorithm 1. The output of the FOLD-R++ algorithm is a set of default rules (?) coded as a normal logic program. An example implied by any rule in the set would be classified as positive. Therefore, the FOLD-R++ algorithm rules out the already covered positive examples at line 9 after learning a new rule. To learn a particular rule, the best literal would be repeatedly selected—and added to the default part of the rule’s body—based on information gain using the remaining training examples (line 17). Next, only the examples that can be covered by learned default literals would be used for further learning (specializing) of the current rule (line 20–21). When the information gain becomes zero or the number of negative examples drops below the ratio threshold, the learning of the default part is done. FOLD-R++ next learns exceptions after first learning default literals. This is done by swapping the residual positive and negative examples and calling itself recursively in line 26. The remaining positive and negative examples can be swapped again and exceptions to exceptions learned (and then swapped further to learn exceptions to exceptions of exceptions, and so on). The $ratio$ parameter in Algorithm 1 represents the ratio of training examples that are part of the exception to the examples implied by only the default conclusion part of the rule. It allows users to control the nesting level of exceptions.

B:  bird(X) :- penguin(X).
    bird(tweety).   bird(et).
    cat(kitty).     penguin(polly).
E+: fly(tweety).    fly(et).
E-: fly(kitty).     fly(polly).

The target predicate {fly(X) :- true.} is specified when calling the learn_rule function at line 4. The function selects the literal bird(X) as result and adds it to the clause $r$ = fly(X) :- bird(X) because it has the best information gain among {bird,penguin,cat}. Then, the training set gets updated to $E^{+}=\{tweety,et\}$, $E^{-}=\{polly\}$ in line 16-17. The negative example $polly$ is still implied by the generated clause and so is a false negative classification. The default learning of learn_rule function is finished because the best information gain of candidate literal is zero. Therefore, the FOLD-R++ function is called recursively with swapped positive and negative examples, $E^{+}=\{polly\}$, $E^{-}=\{tweety,et\}$, to learn exceptions. In this case, an abnormal predicate {ab0(X) :- penguin(X)} is generated and returned as the only exception to the previous learned clause as $r$ = fly(X) :- bird(X), ab0(X). The abnormal rule {ab0(X) :- penguin(X)} is added to the final rule set producing the program below:

In this section, we will present our experiment on several datasets. All the training processes have been run on a laptop with Intel i7-9750H CPU2.6GHz and 16 GB RAM. This ranking model is implemented with pairwise method, we use accuracy, precision, recall and F1 score to evaluate the result. We split each dataset into 80% as training data and 20% as test data. The training data used is sampled with normal distribution and plotted for each feature. We have randomly experimented on the reported datasets 5 times, and the scores are averaged.

In this paper we presented an efficient and highly scalable algorithm, FOLD-TR, to induce default theories represented as an answer set program. The resulting answer set program has good performance wrt prediction and justification for the ranking. In this new approach, unlike other methods, the encoding for data is not needed. We will perform comparison experiments with the other well-known similar models, DirectRanker, PRM, XGBoost and PolyRank. The results on Mean average precison, NDCG, PrecisonN and Mean reciprocal rank will be reported.

Authors gratefully acknowledge support from NSF grants IIS 1718945, IIS 1910131, IIP 1916206, and from Amazon Corp, Atos Corp and US DoD. Thanks to Farhad Shakerin for discussions. We are grateful to Joaquin Arias and the s(CASP) team for their work on providing facilities for generating the justification tree and English encoding of rules in s(CASP).