PaperlayerView exact revision on arXiv

Source-linked AI summary

Interactive Error Correction in Implicative Theories

Sergei O. Kuznetsov, Artem Revenko

arXiv:1410.5215v1cs.AI

TL;DR

A single error in binary data can substantially alter an implicative theory, and later correct data may not repair the effect. The paper proposes two interactive FCA-based error-detection approaches; the closure approach avoids constructing an intractable canonical base. The proposed algorithm runs in polynomial time, and experiments report that it is faster in practice than implication-base generation.

  • Problem

    A single mistake in binary data can drastically change the resulting implicative theory, which may not recover even when further error-free data is added.

    Source: Motivation · pp. 1–2

  • Method

    The paper proposes interactive FCA-based approaches that ask an expert about implications violated by a new object, including a closure approach that avoids computing the full implication base.

    Source: Contributions · p. 3, §4 · p. 6

  • Results

    The proposed algorithm runs in polynomial time and, in computer experiments, works much faster than the approach based on generating the implication base.

    Source: §4.1 · p. 9, §6 · p. 16

  • Takeaways & Limitations

    After checking maximal object descriptions by hand, the method can find all errors of the two considered types or establish their absence.

    Source: §6 · p. 16

    When no context object contains the inspected intent, its closure is the full attribute set and the resulting implication has empty support.

    Source: §4 · p. 7

Abstract

from arXiv · show

Errors in implicative theories coming from binary data are studied. First, two classes of errors that may affect implicative theories are singled out. Two approaches for finding errors of these classes are proposed, both of them based on methods of Formal Concept Analysis. The first approach uses the cardinality minimal (canonical or Duquenne-Guigues) implication base. The construction of such a base is computationally intractable. Using an alternative approach one checks possible errors on the fly in polynomial time via computing closures of subsets of attributes. Both approaches are interactive, based on questions about the validity of certain implications. Results of computer experiments are presented and discussed.

1 Introduction

Errors in binary data can make implicative theories unreliable, and adding later correct data does not necessarily repair their effects. The paper introduces two interactive FCA-based approaches for detecting and correcting errors, with a closure-based alternative to an intractable canonical-base approach.

1 Introduction

  • A single data mistake can drastically change an implicative theory, and later error-free data may not restore the affected dependencies.The paper therefore treats error correction as essential when errors cannot be ruled out in data gathered from multiple users.Source: Motivation · pp. 1–2
  • The paper introduces an interactive procedure that finds and eliminates errors in data-table rows to make the corresponding implicative theory error-free.In FCA terms, it targets errors in descriptions of new objects that affect the canonical implication base.Source: Contributions · p. 3
  • Two approaches detect and eliminate certain error classes: one inspects a canonical implication base, while the other avoids computing all implications.The approaches aim to restore dependencies from the data domain.Source: Contributions · p. 3
  • The canonical-base approach is computationally intractable, whereas the closure approach checks possible errors in polynomial time.The approaches are experimentally compared, but these passages do not report the comparison's outcome.Source: Contributions · p. 3

2 Main Definitions

The paper represents binary data as a formal context and uses derivation and closure operations to describe its structure. Implications encode attribute dependencies, and the canonical base provides a compact representation of valid implications.

2 Main Definitions

  • A formal context consists of objects G, attributes M, and a binary incidence relation I between them.It is written K := (G, M, I).Source: §2 · p. 4
  • Derivation maps object sets to their common attributes and attribute sets to the objects having them, forming a Galois connection.The double derivation is an extensive, monotone, idempotent closure operator.Source: §2 · p. 4
  • Negative attributes are represented by a dichotomized context, which adds complementary attributes to the original attribute set.The corresponding derivation operator is denoted by (·)δ.Source: §2 · p. 4
  • An implication A → B is valid when every object having A also has B; its premise and conclusion are attribute sets.Implications can be represented without loss of generality as unit implications with one attribute in the conclusion.Source: §2 · pp. 4–5
  • The canonical implication base is a cardinality-minimal set of implications, characterized by premises called pseudo-intents.Its implications have the form P → (P′′ \ P) for pseudo-intents P.Source: §2 · p. 5

3 Errors in Implicative Theories

The paper considers positive and negative attribute dependencies in binary data, while restricting their premises to positive attributes. It distinguishes errors in the data from false consequences caused by incomplete data and explains why erroneous rows can obstruct recovery of domain dependencies.

3 Errors in Implicative Theories

  • The considered dependencies have positive premises and may conclude either that an attribute is present or that it is absent.Negative attributes in premises are excluded from the stated setting.Source: §3 · p. 5
  • Negative premises could be modeled with a complementary context, but the resulting disjunction and negation yield full propositional logic, whose closure is not polynomial-time.The paper states that this prevents a polynomial solution for that extension.Source: §3 · pp. 5–6
  • Incomplete data may produce false consequences, but adding objects reduces them; an erroneous object can block deduction of valid domain dependencies even after later correct objects arrive.The paper guarantees that no valid dependencies are lost in the incomplete-data case it describes.Source: §3 · p. 6

4 Finding Errors

The paper presents two ways to find errors in new object intents: checking violated canonical-base implications, or computing crucial implications for the object without constructing the full base. The closure approach handles polynomially many implications, while the quadrangle examples illustrate its ability to detect errors that the base approach's unsupported questions can miss.

4 Finding Errors

  • The base approach asks an expert about canonical-base implications violated by the new intent, but constructing that base is intractable.The canonical base guarantees a minimal number of questions and covers dependencies of Class 1; known nonminimal bases do not guarantee the same question minimum.Source: §4 · p. 6

4.1 Crucial Implications

  • Class 2 errors can arise when an intent contains an attribute combination absent from the context; maximal intents may produce unsupported questions that the authors recommend checking by hand.When no context object contains A, its closure is all attributes, so the resulting implications have empty support.Source: §4 · p. 7, §4.1 · p. 10
  • Crucial implications capture every consequence with nonempty support, but the questions needed for multiple new objects can depend on their insertion order.Additional questions may be needed when new objects have maximal intents.Source: §4.1 · pp. 8–10
  • The closure approach computes object-specific crucial implications in O(|G|^2 × |M|) time, instead of checking exponentially many canonical-base implications.Its crucial implications suffice to deduce every consequence of context implications with nonempty support.Source: §4.1 · pp. 8–9

4.2 Example

  • In the quadrangle examples, closure asks fewer questions for Case2, combines implications for Case3, and detects Case4's Class 2 error where base questions have empty support.The suggested corrections include square for Case2, rectangular trapezium or square for Case3, and rhombus or a quadrangle with two equal legs and two equal angles for Case4.Source: §4.2 · pp. 12–13

5 Experiment

Experiments compare algorithm runtimes on synthetic contexts and assess error-finding quality across three UCI contexts, including how intent structure relates to outcomes.

  • Separate synthetic trials removed and re-added each object to test algorithm efficiency, not to find errors.Source: §5 · p. 13
  • With 50 objects per synthetic context, the runtime gap between the two algorithms grows with attribute count and context density.Source: §5 · p. 13, Figure 3 · p. 14
  • Running the method on original and complementary contexts levels the shift between intent sizes and improves results, but produces no implications mixing positive and negative attributes.The modification addresses the fact that dependencies between negative attributes are not reflected in the implication base.Source: §5 · pp. 13–14
  • Quality trials introduced one to three errors into sampled objects from SPECT, house-votes-84, and kr-vs-kp, counting success only when one implication grouped all erroneous attributes.Each context contributed 1,000 object selections, with possible repetitions.Source: §5 · p. 14
  • More objects improve performance; SPECT’s diverse intents yield a low found-error ratio, while kr-vs-kp performs better for two- and three-error cases.SPECT has 5.78 irreducible objects per attribute on average; kr-vs-kp has more objects per attribute.Source: §5 · pp. 14, 16
  • House-votes-84’s more similar intents yield more questions per object; its found-error ratio is high for one error but drops as errors increase.The passage attributes the drop to the small number of irreducible objects.Source: §5 · p. 16

6 Conclusion

The paper presents an FCA-based method for finding errors in implicative theories, with a polynomial-time alternative to canonical-base generation and favorable runtime experiments.

  • The proposed algorithm terminates in polynomial time, unlike the computationally intractable construction of a canonical implication base.Source: §6 · p. 16
  • Checking maximal object descriptions by hand can find all errors of the two considered types or prove their absence.Source: §6 · p. 16
  • Computer experiments show the proposed method is much faster in practice than generation of the implication base.Source: §6 · p. 16
Loading 1410.5215v1…