Boosting the Learning for Ranking Patterns

In plain words

Pattern mining tools can find very many rules in a dataset, but which ones matter depends on the person looking at them. Each rule gets scores from several generic "interestingness" measures, and no single measure matches what a particular user finds useful. The usual fix is to learn a personal scoring formula from the user's feedback, but that normally takes many examples and a lot of computing time.

This paper treats the choice of measures as a small decision problem. The user ranks a handful of patterns. The method checks, for each measure, how closely its ordering agrees with the user's ordering, and then compares the measures with each other in pairs. Those pairwise comparisons go into a standard decision-making method (the Analytic Hierarchy Process) that turns them into a weight per measure. The final score is a weighted sum of the measures.

A second mode asks the user about pairs of patterns instead of full rankings. It chooses pairs where two patterns score about the same overall but differ a lot on the individual measures, because an answer about such a pair teaches the most about the weights. In the authors' experiments this mode is more accurate than an SVM-based learner and waits far less between questions; in the full-ranking mode the same method is less accurate than that learner.

TL;DR

• Learns a user-specific ranking as a weighted sum of interestingness measures §4.1 eq. 4 eq. 6.
• Measure weights come from AHP over pairwise gaps in how well each measure agrees with user rankings §4.1 alg. 1.
• Passive mode learns from given rankings; active mode asks pairwise questions chosen by a sensitivity heuristic alg. 2 §4.3.1.
• Author-reported on association rules with five FIMI datasets: much faster than an SVM baseline, less accurate in passive mode, more accurate in active mode §6.6 §6.7.

Problem

Interestingness measures are fixed formulas that do not know the user, and learning a user-specific ranking from feedback is costly. Earlier SVM and logistic-regression approaches get slower as the number of pattern-measure pairs grows §1 §2. The paper proposes learning the weights of a linear aggregation with a multi-criteria method, which it says stays fast on large pattern sets §1 §2. The stated assumption is that the user's ranking can be approximated by a weighted combination of the given measures §4.1.

Method

Setup. Patterns P come from a language L. There are m measures M_i, and a linear aggregation f_w(P) = sum_i w_i M_i(P) is the target §4.1 eq. 4. The user supplies total orders (rankings) S over small sets of patterns §4.1.

Step 1: agreement of each measure with a user ranking. For a measure M_i and a ranking S of n patterns, compute a Kendall-W-style coefficient K_i(S) in [0, 1] §4.1. The paper's formula sums two ranks per pattern: R_l = rank_{M_i}(P_l) + rank_u(P_l), with alpha = sum over l of (R_l minus the mean R)^2, and K_i(S) = 12 alpha / (n^3 - n) eq. 5 §4.1.

Step 2: pairwise gaps between measures. For two measures i and j, the gap is Delta_{i,j}(S) = K_i(S) minus K_j(S). A positive gap means M_i agrees more with the user §4.1. With several rankings the paper averages the gaps: Delta_{i,j} = (1/n) sum over k of Delta_{i,j}(S_k) §4.1.

Step 3: AHP matrix. Build an m-by-m reciprocal matrix A with ones on the diagonal. Each gap is scaled to the AHP range, and the matrix holds the scaled value on one side and its reciprocal on the other alg. 1. The algorithm writes A[j,i] = |Delta| and A[i,j] = 1/|Delta| when the gap is negative, and the reverse otherwise alg. 1. The worked example shows the scaling of the gap values in eq. 8 and the resulting matrix in eq. 9 §5.

Step 4: weights. Solve A w = lambda_max w with the weights summing to 1 and each weight positive, using the eigenvector method alg. 1 eq. 1 §3.2.

Step 5: score. For a pattern P, scale each measure to [0, 1] and take the weighted sum: g_w(P) = sum_i w_i scale(M_i(P)) eq. 6 §4.2.

# learnWeights  [alg. 1]
# Input:  measures M (m items); user ranking S (n patterns, best first)
# Output: weight vector w (m,), positive, sums to 1
def learn_weights(measures, ranking):
    # Start with an all-ones reciprocal matrix  [alg. 1]
    ahp = ones(m, m)
    # Agreement of each measure with the ranking  [§4.1] [eq. 5]
    agreement = [kendall_w(measure, ranking) for measure in measures]
    for i < j:
        # Gap between two measures  [§4.1]
        delta = agreement[i] - agreement[j]
        # Scale the gap to the AHP range (rule not stated)  [§5] [eq. 8]
        strength = scale_to_ahp(abs(delta))
        if delta < 0:
            ahp[j, i] = strength
            ahp[i, j] = 1 / strength
        else:
            ahp[i, j] = strength
            ahp[j, i] = 1 / strength
    # Principal eigenvector, normalised to sum 1  [alg. 1] [eq. 1]
    return principal_eigenvector(ahp)

# AHPRank  [alg. 2]
# Input:  measures M; patterns P; sample size theta; iterations T;
#         optional list of user rankings (passive mode when given)
# Output: weight vector w
def ahp_rank(measures, patterns, theta, T, rankings=None):
    # Passive: learn from each ranking; keep the last result  [alg. 2]
    if rankings is not None:
        for ranking in rankings:
            weights = learn_weights(measures, ranking)
        return weights
    # Active mode starts from equal weights  [alg. 2]
    weights = ones(len(measures))
    for t in range(T):
        # Draw a random sample of theta patterns  [alg. 2] [§6.7 A]
        sample = random_sample(patterns, theta)
        # Pick a pair to ask about  [§4.3.1]
        pair = sensitivity_pair(sample, weights, measures)
        # The user ranks the pair  [alg. 2]
        ranking = ask_user(pair)
        # Relearn the weights from this answer  [alg. 2]
        weights = learn_weights(measures, ranking)
    return weights

# Sensitivity-based pair selection  [§4.3.1] [eq. 7]
# Input:  sample of patterns; weights w; measures M
# Output: the adjacent pair with the smallest sensitivity
def sensitivity_pair(sample, weights, measures):
    # Order the sample by predicted score g_w  [§4.3.1]
    ordered = sort_by_score(sample, weights)
    best_pair = None
    best_sigma = infinity
    for p, q in adjacent_pairs(ordered):
        # Predicted-score gap over the summed measure gap  [§4.3.1] [eq. 7]
        sigma = abs(
            (score(p, weights) - score(q, weights))
            / sum(measure(p) - measure(q) for measure in measures)
        )
        if sigma < best_sigma:
            best_sigma = sigma
            best_pair = (p, q)
    return best_pair

Passive mode runs learn_weights once per given ranking and returns the last result alg. 2 §4.3. In the experiments the passive input is a single large ranking §4.4.

Active mode starts from equal weights, draws a random sample of patterns, picks a pair with the sensitivity heuristic, asks the user, and relearns alg. 2 §4.3. The stopping rule is either a custom criterion or a fixed number T of iterations §4.3. The heuristic is defined in §4.3.1 eq. 7.

Complexity. The paper claims O(n k) for passive mode and O(n) for active mode, with a bounded number of measures (m at most 9 is assumed) §4.4. The claim depends on m being fixed.

Hyperparameters

Measures used

The seven measures and their short labels in the tables tab. 4 §6.1:

The chi-squared emulator is defined as chi^2(X -> Y) = (freq(X->Y) minus freq(X) freq(Y) / N)^2 divided by freq(X) freq(Y) / N, with N the number of transactions eq. 10 §6.2.

Results

Author-reported. Setup: association rules mined from five FIMI datasets tab. 3 with a standard rule miner §6.5; three simulated users (Rand-Emu, Lex-Emu, Chi-Emu) §6.2; Spearman rho, recall at 10% and 1%, and CPU time §6.4.2. Baseline: SVM-based ranking (RankingSVM) in passive and active modes §6.4.1.

Correlation of single measures with simulated users tab. 4. Values are Spearman rho. The last column is the best single measure per dataset (the paper's "virtual best measure"):

tab. 4. The text reports a mean VBM of 91% §6.6 A.

Passive learning, AHP vs SVM tab. 5. Values are rho, R@10%, R@1%, and time in seconds (5-fold). SVM finished only on Hepatitis within the one-hour limit ("TO" elsewhere).

tab. 5 §6.6 B. The text states that SVM is more accurate on every emulator on Hepatitis, and that AHP is faster §6.6 B. Figures 1 and 2 show the accuracy and CPU time against training size for Chi-Emu fig. 1 fig. 2; the text reports that the accuracy gap is about 5% up to 1K rules and above 10% in favour of AHP at 10K and 100K, and that SVM takes over 26 minutes at 100K rules, while AHP takes up to 24.86 s §6.6 C.

Active learning, AHP vs SVM tab. 7. Spearman rho; rows (1) SVM, (2) AHP. Recall and latency are in the source table.

tab. 7 §6.7 B. The source table's latency row ("t") gives 0 s for SVM at 10 queries and 0 to 10 s at 50 and 100 queries; the AHP latency row is commented out in the source, and the text gives under 0.1 s tab. 7 §6.7 B. The text reports that SVM waits more than 10 seconds between queries on Retail §6.7 B. Figure 3 compares random and sensitivity-based query generation fig. 3. The Wilcoxon test rejects the null for every metric except SVM recall at 10%, which the paper does not treat as significant tab. 6 §6.7 A.

Interactive learning §6.8 fig. 4 fig. 5. With 20 queries and simulated answer errors of 0 to 40% on Chi-Emu, AHP keeps rho at about 77% without errors and about 70% at 40% errors; SVM drops from about 71% to 54% §6.8. Latency is at most 0.02 s for AHP, against 6 to 12 s for SVM §6.8. On a switch from Lex-Emu to Rand-Emu halfway through, AHP stays stable and SVM loses about 44% of its rho §6.8. The text says AHP is about 50 times faster in CPU time than SVM in this setting §6.8.

Running example tab. 1 eq. 8 eq. 9. With 10 patterns and 5 measures, the learned weights are (0.24, 0.24, 0.065, 0.065, 0.39) §5. The text reports 91% ranking accuracy §5.

Paper vs code

No official code.

The paper names github.com/lirmm/AHPRank as its implementation §6.4.1. That URL returns "Repository not found" when cloned, so it could not be used.

Searches made: (1) the paper's link, above; (2) GitHub repository search for "AHPRank", which found only ACodeSubmissions/AHPRank2021, an account not tied to the authors, so not used; (3) GitHub organisation search for lirmm, no repositories; (4) GitHub user search for "Belmecheri", seven accounts, none tied to the first author; (5) repository search for "ranking patterns AHP interestingness", no results. No project page was linked.

Pitfalls

• Pseudocode and the text disagree on Delta. The text says the pairwise gaps are averaged over the user rankings, and that Delta is "incrementally updated" §4.2. The live line of the algorithm sets each Delta_{i,j} to the gap for the current ranking only alg. 1. The averaging update is commented out in the source. The card follows the live algorithm. An implementer should decide which one they mean and test it on the running example.
• Gap-to-scale rule is not stated. Eq. 8 scales gaps of 0.42, 0.43, 0.20, 0.25, 0.28 and 0.55, 0.60 to 4, 4, 2, 3, 3 and 6, 6. This fits rounding 10 × |gap| and clipping to 1..9, but the paper does not say so. A gap of 0 becomes 1 (equal) eq. 8 alg. 1.
• Kendall W formula. Eq. 5 sums two ranks per pattern (measure rank plus user rank). It has no term for the number of rankers, which is part of the usual definition. The paper cites Kendall (1939) but does not show the reduction. Implement eq. 5 as printed, and note that it is the paper's formulation.
• Consistency check is missing from the algorithms. Section 3.2 says weights are reliable when CR < 0.1 §3.2. The algorithms never compute CR, and the RI table is not given §3.2 alg. 1.
• Weights do not sum to 1 as printed. The running example's weights sum to 0.99 (rounding) §5. Normalise after the eigenvector solve.
• Eigenvector method. The paper uses EVM and says distance-based methods are harder to solve §3.2. The positivity constraint on w is stated in the solve step alg. 1 but no check is given.
• Running example accuracy. The text says 91% and that the first five patterns, the seventh and the tenth are correct §5. That is 7 of 10 in the table, which is 70%. The paper does not reconcile this.
• Mean VBM. The 15 VBM cells in tab. 4 average 0.88, not the 91% stated in the text §6.6 A tab. 4. This is a computed check, not an author claim.
• Measure labels. Table 2 bolds Yule's Q, Cosine, Laplace, phi coefficient, Goodman-Kruskal, Interest factor and certainty factor. The experiments use YulesY, Cosine, Laplace, Leverage, Lambda, IF and certainty factor tab. 2 tab. 4. Leverage and Lambda are not the bold picks in groups 4 and 5.
• Connect results. The active comparison shows AHP rho at 0.10 on Connect for all query budgets, below SVM at 50 and 100 queries. The text reports AHP as better overall and does not mention Connect tab. 7 §6.7 B. The constant 0.10 may be a copy error; check the source if you use it.
• Passive accuracy is worse than SVM. The paper says so §6.6 B. The headline claim is speed, not passive accuracy.
• Only Hepatitis has an SVM passive baseline. The other datasets show SVM as timed out, so passive comparisons beyond Hepatitis are AHP-only tab. 5.
• Ambiguous wording in the abstract. The abstract says AHP is used "to elicit weights ... based on user preference" [abstract]. The user never compares measures directly. The user ranks patterns, and the measure comparisons are derived from those rankings §4.1.
• Complexity claim. The proof assumes a fixed number of measures (m at most 9) and does not include the sort inside the sensitivity heuristic §4.4 alg. 2 §4.3.1. "Linear" holds under those assumptions only.
• Simulated users only. The three emulators are synthetic §6.2. The active error experiment is the only robustness test, and it uses Chi-Emu on all datasets with 20 queries §6.8.
• Errors are simulated flips. A queried preference is reversed with a fixed probability; real user noise may differ §6.8.
• Association rules only. All experiments use association rules and seven measures from one study §6.1. Generalisation to other pattern types is claimed in the conclusion, not tested §7.

Lineage

• Builds on: the passive version of this approach, published by the same group in RNTI. That paper has no arXiv id in the bibliography §1.
• Compared against: SVM-based ranking of patterns from Dzyuba et al. (2013 and 2017), used as RankingSVM passive and active baselines §2 §6.4.1.
• Related but not compared: Boley et al. (logistic model with stochastic coordinate descent) §1 §2; Xin et al. (2006) §2; Bhuiyan et al. (PRIIME) §2.
• Superseded by: not known from this wiki.