From lattices to logic: Adapting the InClose algorithm for efficient canonical basis computation

This paper extends the efficient InClose algorithm from lattice generation to computing the canonical basis of implications. We present InClose-Imp, a new method that integrates pseudo-intent checking into InClose’s incremental framework, providing a competitive alternative to traditional algorithms.

Keywords

InClose, InClose-Imp, Canonical basis, Duquenne-Guigues, Pseudo-intents, NextClosure, LinCbO

The InClose algorithm is a state-of-the-art method for concept lattice construction, prized for its efficiency stemming from incremental closure computation. However, its applicability has so far been limited to lattice generation. This paper extends the InClose paradigm to the problem of computing the Duquenne-Guigues (canonical) basis of implications. We address the central challenge of adapting InClose’s incremental approach, which avoids computing full closures, to the needs of pseudo-intent identification, which traditionally relies on them. We present InClose-Imp, a modified algorithm that integrates pseudo-intent checking within the incremental CbO framework. We prove its correctness and demonstrate through benchmarks that InClose-Imp offers a competitive alternative to existing algorithms like NextClosure and LinCbO, particularly in contexts where InClose’s incremental strategy excels.

Introduction

Computing the canonical basis of implications is a central but computationally hard problem in FCA. While algorithms like NextClosure provide a foundation, and LinCbO has adapted the CbO strategy for this task, there is still room for improvement. The InClose algorithm has shown superior performance for lattice construction by avoiding the repeated computation of full extents. This raises a natural question: can the efficiency of InClose’s incremental strategy be ported to the task of computing implications?

The main obstacle is that identifying a pseudo-intent—the premise of a canonical implication—traditionally requires checking if it is a meet of meet-irreducible concepts, a process that seems to require knowledge of full closures.

This paper overcomes this obstacle. Our contributions are:

1. A theoretical analysis of how pseudo-intents can be identified using only the partial, incremental information available within the InClose algorithm’s search tree.
2. The InClose-Imp algorithm, a novel adaptation of InClose specifically designed for canonical basis computation.
3. An empirical evaluation comparing InClose-Imp with LinCbO and NextClosure, identifying the types of contexts where our new approach is most effective.

Methodology and expected theoretical results

Theoretical challenge

The core of InClose is that it computes closures incrementally: to compute $(A \cup \{y\})^+$, it uses information from the computation of $A^+$. LinCbO, a FastCbO variant, computes the full closure at each node to prune the search for pseudo-intents. Our challenge is to achieve similar pruning without the full closure.

Proposed solution

Our strategy will be to modify the canonicity test within InClose. The test that determines whether a new node in the search tree should be created will be augmented. It will not only check if the concept is canonical (to build the lattice) but also simultaneously check a condition related to it being a pseudo-intent. * Main theoretical result: We will formulate and prove a theorem stating that a set $P$ is a pseudo-intent if and only if it satisfies a specific condition that can be checked “locally” during the incremental traversal of the InClose search tree. This condition will likely involve checking closures of subsets of $P$ against previously discovered intents.

The InClose-Imp algorithm

The algorithm will follow the InClose structure, but at each step where a new candidate intent $C$ is generated, it will: 1. Perform the standard InClose canonicity test. 2. If canonical, perform the new “pseudo-intent test.” 3. If the test is positive, add the implication $P \to (P^{++} \setminus P)$ to the basis, where $P$ is the corresponding pseudo-intent derived from $C$.

Work plan

• Months 1-4: Develop the theory and prove the local pseudo-intent checking theorem. This is the main theoretical hurdle and will be the focus of collaboration with Prof. Simon Andrews.
• Months 5-7: Implement the InClose-Imp algorithm.
• Months 8-10: Conduct extensive benchmarks comparing InClose-Imp, LinCbO, and NextClosure.
• Months 11-12: Write the manuscript.

Potential target journals

1. Information Sciences (Q1): An excellent venue for a new, high-performance algorithm for a core FCA task.
2. Annals of Mathematics and Artificial Intelligence (Q2): A good fit for the paper’s blend of algorithmic design and theoretical computer science.
3. ICFCA Conference (CORE B): The ideal place to debut the algorithm and get expert feedback.

Minimum viable article (MVA) strategy

The MVA is the algorithm for the classical binary case. The fuzzy extension is a natural follow-up.

• Paper 1 (The MVA - binary InClose-Imp):
  • Scope: Introduce the InClose-Imp algorithm for binary contexts. Provide the correctness proof and a solid empirical comparison against state-of-the-art competitors.
  • Goal: To establish a new, competitive algorithm for canonical basis computation.
  • Target venue: ICFCA Conference, followed by a journal submission to Information Sciences.
• Paper 2 (Fuzzy InClose-Imp):
  • Scope: Extend the entire framework to L-FCA. This requires defining a fuzzy pseudo-intent test that works with the incremental fuzzy InClose algorithm. This is a significant theoretical and algorithmic step.
  • Goal: To provide the first CbO-style incremental algorithm for fuzzy canonical basis computation.
  • Target venue: Fuzzy Sets and Systems or IEEE Transactions on Fuzzy Systems.