Concept and Attribute Reduction Based on Rectangle Theory of Formal Concept

• URL: http://arxiv.org/abs/2111.00005v1
• Date: Fri, 29 Oct 2021 02:10:08 GMT
• Title: Concept and Attribute Reduction Based on Rectangle Theory of Formal Concept
• Authors: Jianqin Zhou, Sichun Yang, Xifeng Wang and Wanquan Liu
• Abstract summary: It is known that there are three types of formal concepts: core concepts, relative necessary concepts and unnecessary concepts. We present the new judgment results for relative necessary concepts and unnecessary concepts. A fast algorithm for reducing attributes while preserving the extensions for a set of formal concepts is proposed.
• Score: 5.657202839641533
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Based on rectangle theory of formal concept and set covering theory, the concept reduction preserving binary relations is investigated in this paper. It is known that there are three types of formal concepts: core concepts, relative necessary concepts and unnecessary concepts. First, we present the new judgment results for relative necessary concepts and unnecessary concepts. Second, we derive the bounds for both the maximum number of relative necessary concepts and the maximum number of unnecessary concepts and it is a difficult problem as either in concept reduction preserving binary relations or attribute reduction of decision formal contexts, the computation of formal contexts from formal concepts is a challenging problem. Third, based on rectangle theory of formal concept, a fast algorithm for reducing attributes while preserving the extensions for a set of formal concepts is proposed using the extension bit-array technique, which allows multiple context cells to be processed by a single 32-bit or 64-bit operator. Technically, the new algorithm could store both formal context and extent of a concept as bit-arrays, and we can use bit-operations to process set operations "or" as well as "and". One more merit is that the new algorithm does not need to consider other concepts in the concept lattice, thus the algorithm is explicit to understand and fast. Experiments demonstrate that the new algorithm is effective in the computation of attribute reductions.

Related papers

• Discover-then-Name: Task-Agnostic Concept Bottlenecks via Automated Concept Discovery [52.498055901649025]
  Concept Bottleneck Models (CBMs) have been proposed to address the 'black-box' problem of deep neural networks. We propose a novel CBM approach -- called Discover-then-Name-CBM (DN-CBM) -- that inverts the typical paradigm. Our concept extraction strategy is efficient, since it is agnostic to the downstream task, and uses concepts already known to the model.
  arXiv  Detail & Related papers  (2024-07-19T17:50:11Z)
• Incorporating Expert Rules into Neural Networks in the Framework of Concept-Based Learning [2.9370710299422598]
  It is proposed how to combine logical rules and neural networks predicting the concept probabilities. We provide several approaches for solving the stated problem and for training neural networks. The code of proposed algorithms is publicly available.
  arXiv  Detail & Related papers  (2024-02-22T17:33:49Z)
• An Axiomatic Approach to Model-Agnostic Concept Explanations [67.84000759813435]
  We propose an approach to concept explanations that satisfy three natural axioms: linearity, recursivity, and similarity. We then establish connections with previous concept explanation methods, offering insight into their varying semantic meanings.
  arXiv  Detail & Related papers  (2024-01-12T20:53:35Z)
• Implicit Concept Removal of Diffusion Models [92.55152501707995]
  Text-to-image (T2I) diffusion models often inadvertently generate unwanted concepts such as watermarks and unsafe images. We present the Geom-Erasing, a novel concept removal method based on the geometric-driven control.
  arXiv  Detail & Related papers  (2023-10-09T17:13:10Z)
• Coarse-to-Fine Concept Bottleneck Models [9.910980079138206]
  This work targets ante hoc interpretability, and specifically Concept Bottleneck Models (CBMs) Our goal is to design a framework that admits a highly interpretable decision making process with respect to human understandable concepts, on two levels of granularity. Within this framework, concept information does not solely rely on the similarity between the whole image and general unstructured concepts; instead, we introduce the notion of concept hierarchy to uncover and exploit more granular concept information residing in patch-specific regions of the image scene.
  arXiv  Detail & Related papers  (2023-10-03T14:57:31Z)
• Interpretable Neural-Symbolic Concept Reasoning [7.1904050674791185]
  Concept-based models aim to address this issue by learning tasks based on a set of human-understandable concepts. We propose the Deep Concept Reasoner (DCR), the first interpretable concept-based model that builds upon concept embeddings.
  arXiv  Detail & Related papers  (2023-04-27T09:58:15Z)
• Multi-dimensional concept discovery (MCD): A unifying framework with completeness guarantees [1.9465727478912072]
  We propose Multi-dimensional Concept Discovery (MCD) as an extension of previous approaches that fulfills a completeness relation on the level of concepts. We empirically demonstrate the superiority of MCD against more constrained concept definitions.
  arXiv  Detail & Related papers  (2023-01-27T18:53:19Z)
• Concept Gradient: Concept-based Interpretation Without Linear Assumption [77.96338722483226]
  Concept Activation Vector (CAV) relies on learning a linear relation between some latent representation of a given model and concepts. We proposed Concept Gradient (CG), extending concept-based interpretation beyond linear concept functions. We demonstrated CG outperforms CAV in both toy examples and real world datasets.
  arXiv  Detail & Related papers  (2022-08-31T17:06:46Z)
• Kernelized Concept Erasure [108.65038124096907]
  We propose a kernelization of a linear minimax game for concept erasure. It is possible to prevent specific non-linear adversaries from predicting the concept. However, the protection does not transfer to different nonlinear adversaries.
  arXiv  Detail & Related papers  (2022-01-28T15:45:13Z)
• Formal context reduction in deriving concept hierarchies from corpora using adaptive evolutionary clustering algorithm star [15.154538450706474]
  The process of deriving concept hierarchies from corpora is typically a time-consuming and resource-intensive process. The resulting lattice of formal context is evaluated to the standard one using concept lattice-invariants. The results show that adaptive ECA* performs concept lattice faster than other mentioned competitive techniques in different fill ratios.
  arXiv  Detail & Related papers  (2021-07-10T07:18:03Z)
• Formalising Concepts as Grounded Abstractions [68.24080871981869]
  This report shows how representation learning can be used to induce concepts from raw data. The main technical goal of this report is to show how techniques from representation learning can be married with a lattice-theoretic formulation of conceptual spaces.
  arXiv  Detail & Related papers  (2021-01-13T15:22:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.