Towards Continuous Consistency Axiom

• URL: http://arxiv.org/abs/2202.06015v1
• Date: Sat, 12 Feb 2022 08:25:01 GMT
• Title: Towards Continuous Consistency Axiom
• Abstract summary: Development of new algorithms in the area of machine learning, especially clustering, requires availability of labeled data sets. We propose an alternative axiomatic system, in which Kleinberg's inner consistency axiom is replaced by a centric consistency axiom. We demonstrate that the new system is satisfiable for a hierarchical version of $k$-means with auto-adjusted $k$, hence it is not contradictory.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Development of new algorithms in the area of machine learning, especially clustering, comparative studies of such algorithms as well as testing according to software engineering principles requires availability of labeled data sets. While standard benchmarks are made available, a broader range of such data sets is necessary in order to avoid the problem of overfitting. In this context, theoretical works on axiomatization of clustering algorithms, especially axioms on clustering preserving transformations are quite a cheap way to produce labeled data sets from existing ones. However, the frequently cited axiomatic system of Kleinberg:2002, as we show in this paper, is not applicable for finite dimensional Euclidean spaces, in which many algorithms like $k$-means, operate. In particular, the so-called outer-consistency axiom fails upon making small changes in datapoint positions and inner-consistency axiom is valid only for identity transformation in general settings. Hence we propose an alternative axiomatic system, in which Kleinberg's inner consistency axiom is replaced by a centric consistency axiom and outer consistency axiom is replaced by motion consistency axiom. We demonstrate that the new system is satisfiable for a hierarchical version of $k$-means with auto-adjusted $k$, hence it is not contradictory. Additionally, as $k$-means creates convex clusters only, we demonstrate that it is possible to create a version detecting concave clusters and still the axiomatic system can be satisfied. The practical application area of such an axiomatic system may be the generation of new labeled test data from existent ones for clustering algorithm testing. %We propose the gravitational consistency as a replacement which does not have this deficiency.

Related papers

• S2MAM: Semi-supervised Meta Additive Model for Robust Estimation and Variable Selection [37.9993096742594]
  This paper proposes a new Semi-Supervised Meta Additive Model (S$2$MAM)<n>Based on a bilevel optimization scheme that automatically identifies informative variables, updates the similarity matrix, and simultaneously achieves interpretable predictions.<n> Experimental assessments across 4 synthetic and 12 real-world datasets, with varying levels and categories of corruption, validate the robustness and interpretability of the proposed approach.
  arXiv  Detail & Related papers  (2026-04-21T04:27:12Z)
• Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model [48.989531198582704]
  We show that DCBM inference can be reformulated as a constrained nonnegative matrix factorization problem.<n>Our approach is to any specific network structure and applies to graphs with any structure representable by a DCBM.<n> Experiments on synthetic and real benchmark networks show that our method detects communities comparable to those found by DCBM inference.
  arXiv  Detail & Related papers  (2026-01-09T19:16:29Z)
• Topological Mixed States: Phases of Matter from Axiomatic Approaches [15.433292838001103]
  In closed quantum systems, topological orders are understood through the equivalence classes of ground states of gapped local Hamiltonians.<n>Here, we fill this gap by proposing an approach based on three axioms: ($i$) local recoverability, ($ii$) absence of long-range correlations, and ($iii$) spatial uniformity.<n>From these axioms, a rich set of topological data naturally emerges; importantly, these data are robust under relaxation of axioms.
  arXiv  Detail & Related papers  (2025-06-04T17:58:45Z)
• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) aims to classify both base and novel images using labeled base data. Current approaches inadequately address the intrinsic optimization of the co-occurrence matrix $barA$ based on cosine similarity. We propose a Non-Negative Generalized Category Discovery (NN-GCD) framework to address these deficiencies.
  arXiv  Detail & Related papers  (2024-10-29T07:24:11Z)
• Wide Gaps and Clustering Axioms [0.0]
  k-means is in conflict with Kleinberg's axiomatic system for distance based clustering algorithms. We introduce two new clusterability properties, variational k-separability and residual k-separability. We reconcile k-means with Kleinberg's axiomatic framework in Euclidean and non-Euclidean settings.
  arXiv  Detail & Related papers  (2023-08-07T10:43:48Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability. IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Semi-supervised Community Detection via Structural Similarity Metrics [0.0]
  We study a semi-supervised community detection problem in which the objective is to estimate the community label of a new node. We propose an algorithm that computes a structural similarity metric' between the new node and each of the $K$ communities. Our findings highlight, to the best of our knowledge, the first semi-supervised community detection algorithm that offers theoretical guarantees.
  arXiv  Detail & Related papers  (2023-06-01T19:02:50Z)
• Can Evolutionary Clustering Have Theoretical Guarantees? [21.343803954998915]
  Evolutionary clustering has found many successful applications, but all the results are empirical, lacking theoretical support. This paper fills this gap by proving that the approximation performance of the GSEMO can be theoretically guaranteed.
  arXiv  Detail & Related papers  (2022-12-04T09:00:35Z)
• Parametric Classification for Generalized Category Discovery: A Baseline Study [70.73212959385387]
  Generalized Category Discovery (GCD) aims to discover novel categories in unlabelled datasets using knowledge learned from labelled samples. We investigate the failure of parametric classifiers, verify the effectiveness of previous design choices when high-quality supervision is available, and identify unreliable pseudo-labels as a key problem. We propose a simple yet effective parametric classification method that benefits from entropy regularisation, achieves state-of-the-art performance on multiple GCD benchmarks and shows strong robustness to unknown class numbers.
  arXiv  Detail & Related papers  (2022-11-21T18:47:11Z)
• Normalised clustering accuracy: An asymmetric external cluster validity measure [2.900810893770134]
  Clustering algorithms are traditionally evaluated using either internal or external validity measures. In this paper, we argue that the commonly used classical partition similarity scores miss some desirable properties. We propose and analyse a new measure: a version of the optimal set-matching accuracy.
  arXiv  Detail & Related papers  (2022-09-07T05:08:34Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• High-dimensional separability for one- and few-shot learning [58.8599521537]
  This work is driven by a practical question, corrections of Artificial Intelligence (AI) errors. Special external devices, correctors, are developed. They should provide quick and non-iterative system fix without modification of a legacy AI system. New multi-correctors of AI systems are presented and illustrated with examples of predicting errors and learning new classes of objects by a deep convolutional neural network.
  arXiv  Detail & Related papers  (2021-06-28T14:58:14Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation [73.44809425486767]
  This paper theoretically derives a unified form of JMMD that is easy to optimize. From the revealed unified JMMD, we illustrate that JMMD degrades the feature-label dependence that benefits to classification. We propose a novel MMD matrix to promote the dependence, and devise a novel label kernel that is robust to label distribution shift.
  arXiv  Detail & Related papers  (2021-01-25T09:46:14Z)
• Algebraic Ground Truth Inference: Non-Parametric Estimation of Sample Errors by AI Algorithms [0.0]
  Non-parametric estimators of performance are an attractive solution in autonomous settings. We show that the accuracy estimators in the experiments where we have ground truth are better than one part in a hundred. The practical utility of the method is illustrated on a real-world dataset from an online advertising campaign and a sample of common classification benchmarks.
  arXiv  Detail & Related papers  (2020-06-15T12:04:47Z)

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.