Maximal Ordinal Two-Factorizations

• URL: http://arxiv.org/abs/2304.03338v2
• Date: Tue, 20 Jun 2023 11:22:11 GMT
• Title: Maximal Ordinal Two-Factorizations
• Authors: Dominik D\"urrschnabel, Gerd Stumme
• Abstract summary: We show that deciding on the existence of two-factorizations of a given size is an NP-complete problem. We provide the algorithm Ord2Factor that allows us to compute large ordinal two-factorizations.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a formal context, an ordinal factor is a subset of its incidence relation that forms a chain in the concept lattice, i.e., a part of the dataset that corresponds to a linear order. To visualize the data in a formal context, Ganter and Glodeanu proposed a biplot based on two ordinal factors. For the biplot to be useful, it is important that these factors comprise as much data points as possible, i.e., that they cover a large part of the incidence relation. In this work, we investigate such ordinal two-factorizations. First, we investigate for formal contexts that omit ordinal two-factorizations the disjointness of the two factors. Then, we show that deciding on the existence of two-factorizations of a given size is an NP-complete problem which makes computing maximal factorizations computationally expensive. Finally, we provide the algorithm Ord2Factor that allows us to compute large ordinal two-factorizations.

Related papers

• Quantization of Large Language Models with an Overdetermined Basis [73.79368761182998]
  We introduce an algorithm for data quantization based on the principles of Kashin representation. Our findings demonstrate that Kashin Quantization achieves competitive or superior quality in model performance.
  arXiv  Detail & Related papers  (2024-04-15T12:38:46Z)
• Regularization-Based Methods for Ordinal Quantification [49.606912965922504]
  We study the ordinal case, i.e., the case in which a total order is defined on the set of n>2 classes. We propose a novel class of regularized OQ algorithms, which outperforms existing algorithms in our experiments.
  arXiv  Detail & Related papers  (2023-10-13T16:04:06Z)
• Integer Factorisation, Fermat & Machine Learning on a Classical Computer [0.0]
  We use Lawrence's extension of Fermat's factorisation algorithm to reduce the integer factorisation problem to a binary classification problem. To address the classification problem, based on the ease of generating large pseudo--random primes, a corpus of training data, as large as needed, is synthetically generated.
  arXiv  Detail & Related papers  (2023-07-16T22:39:00Z)
• Greedy Discovery of Ordinal Factors [0.0]
  In large datasets, it is hard to discover and analyze structure. An ordinal factor arranges a subset of the tags in a linear order based on their underlying structure. A complete ordinal factorization, which consists of such ordinal factors, precisely represents the original dataset.
  arXiv  Detail & Related papers  (2023-02-19T20:33:24Z)
• An Algebraic-Geometry Approach to Prime Factorization [0.0]
  New algorithms for prime factorization can have a practical impact on present implementations of cryptographic algorithms. We show that there are varieties whose points can be evaluated efficiently given a number of parameters not greater than n/2. In one case, we show that there are varieties whose points can be evaluated efficiently given a number of parameters not greater than n/2.
  arXiv  Detail & Related papers  (2022-09-23T15:31:07Z)
• Identifiability in Exact Multilayer Sparse Matrix Factorization [0.0]
  We prove that any matrix which is the product of L factors whose supports are exactly the so-called butterfly supports, admits a unique sparse factorization into L factors. This applies in particular to the Hadamard or the discrete Fourier transform matrix of size 2L.
  arXiv  Detail & Related papers  (2021-10-04T07:50:51Z)
• Sawtooth Factorial Topic Embeddings Guided Gamma Belief Network [49.458250193768826]
  We propose sawtooth factorial topic embedding guided GBN, a deep generative model of documents. Both the words and topics are represented as embedding vectors of the same dimension. Our models outperform other neural topic models on extracting deeper interpretable topics.
  arXiv  Detail & Related papers  (2021-06-30T10:14:57Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  We introduce a novel graph convolutional network (GCN) that explicitly disentangles intertwined relations encoded in a graph. FactorGCN takes a simple graph as input, and disentangles it into several factorized graphs. We evaluate the proposed FactorGCN both qualitatively and quantitatively on the synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-10-12T03:01:40Z)
• ClarQ: A large-scale and diverse dataset for Clarification Question Generation [67.1162903046619]
  We devise a novel bootstrapping framework that assists in the creation of a diverse, large-scale dataset of clarification questions based on postcomments extracted from stackexchange. We quantitatively demonstrate the utility of the newly created dataset by applying it to the downstream task of question-answering. We release this dataset in order to foster research into the field of clarification question generation with the larger goal of enhancing dialog and question answering systems.
  arXiv  Detail & Related papers  (2020-06-10T17:56:50Z)

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.