The Computational Complexity of Concise Hypersphere Classification
Hypersphere classification is a classical and foundational method that can provide easy-to-process explanations for the classification of real-valued and binary data. However, obtaining an (ideally concise) explanation via hypersphere classification is much more difficult when dealing with binary data than real-valued data. In this paper, we perform the first complexity-theoretic study of the hypersphere classification problem for binary data. We use the fine-grained parameterized complexity paradigm to analyze the impact of structural properties that may be present in the input data as well as potential conciseness constraints. Our results include stronger lower bounds and new fixed-parameter algorithms for hypersphere classification of binary data, which can find an exact and concise explanation when one exists.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationSimilar Papers 제목 키워드 기반
Deep Learning Based Sphere Decoding
In this paper, a deep learning (DL)-based sphere decoding algorithm is proposed, where the radius of the decoding hypersphere is learned by a deep neural network (DNN). The performance achieved by the proposed algorithm …
Deep LearningDeep Learning-based List Sphere Decoding for Faster-than-Nyquist (FTN) Signaling Detection
Faster-than-Nyquist (FTN) signaling is a candidate non-orthonormal transmission technique to improve the spectral efficiency (SE) of future communication systems. However, such improvements of the SE are at the cost of a…
Machine Learning-based Signal Detection for PMH Signals in Load-modulated MIMO System
Phase Modulation on the Hypersphere (PMH) is a power efficient modulation scheme for the \textit{load-modulated} multiple-input multiple-output (MIMO) transmitters with central power amplifiers (CPA). However, it is diff…
BIG-bench Machine LearningClusteringFew-shot Classification with Hypersphere Modeling of Prototypes
Metric-based meta-learning is one of the de facto standards in few-shot learning. It composes of representation learning and metrics calculation designs. Previous works construct class representations in different ways, …
ClassificationFew-Shot LearningMeta-LearningRepresentation LearningHyP$^2$ Loss: Beyond Hypersphere Metric Space for Multi-label Image Retrieval
Image retrieval has become an increasingly appealing technique with broad multimedia application prospects, where deep hashing serves as the dominant branch towards low storage and efficient retrieval. In this paper, we …
Deep HashingImage RetrievalMetric LearningMulti-Label Image Retrieval+1