Fugu-MT 論文翻訳(概要): The Computational Complexity of Concise Hypersphere Classification

論文の概要: The Computational Complexity of Concise Hypersphere Classification

arxiv url: http://arxiv.org/abs/2312.07103v1
Date: Tue, 12 Dec 2023 09:33:03 GMT
ステータス: 処理完了
システム内更新日: 2023-12-13 16:50:38.384178
Title: The Computational Complexity of Concise Hypersphere Classification
Title（参考訳）: 簡潔な超球面分類の計算複雑性
Authors: Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
Abstract要約: 本稿では,二元データに対する超球分類問題の複雑性理論による最初の研究である。パラメータ化複雑性のパラダイムを用いて、入力データに存在する可能性のある構造特性の影響を分析する。
参考スコア（独自算出の注目度）: 49.57441416941195
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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.
Abstract（参考訳）: ハイパースフィア分類(hypersphere classification)は、実数値データとバイナリデータの分類について簡単に説明できる古典的かつ基礎的な手法である。しかし、実数値データよりもバイナリデータを扱う場合、ハイパースフィア分類による(理想的には簡潔な)説明を得るのは難しい。本稿では,二元データに対する超球分類問題の複雑性理論による最初の研究を行う。我々は,細粒度パラメータ化複雑性パラダイムを用いて,入力データに現れる構造的特性の影響と潜在的簡潔さの制約を分析する。以上の結果から,バイナリデータの超球分分類のための新しい固定パラメータアルゴリズムや,より厳密で簡潔な説明が得られている。

関連論文リスト

A Perceptron-based Fine Approximation Technique for Linear Separation [0.0]
本稿では,正あるいは負のラベル付きデータポイント間でセパレータ超平面を見つけることを目的とした,新しいオンライン学習手法を提案する。人工ニューロンの重みとバイアスは、高次元空間の超平面と直接関連付けられる。実験結果から,Perceptronアルゴリズムよりも効率がよいことが示された。
論文参考訳（メタデータ） (2023-09-12T08:35:24Z)
DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
本稿では,データセットからのインスタンスのバッチを進化状態にエンコードするエネルギー制約拡散モデルを提案する。任意のインスタンス対間の対拡散強度に対する閉形式最適推定を示唆する厳密な理論を提供する。各種タスクにおいて優れた性能を有する汎用エンコーダバックボーンとして,本モデルの適用性を示す実験を行った。
論文参考訳（メタデータ） (2023-01-23T15:18:54Z)
Provably Accurate and Scalable Linear Classifiers in Hyperbolic Spaces [39.71927912296049]
スケーラブルで単純な双曲型線形分類器を学習するための統一的なフレームワークを提案する。我々のアプローチの要点は、ポアンカーの球体モデルに焦点を合わせ、接空間形式を用いて分類問題を定式化することである。 Poincarの2階と戦略的パーセプトロンの優れた性能は、提案フレームワークが双曲空間における一般的な機械学習問題にまで拡張可能であることを示している。
論文参考訳（メタデータ） (2022-03-07T21:36:21Z)
Riemannian classification of EEG signals with missing values [67.90148548467762]
本稿では脳波の分類に欠落したデータを扱うための2つの方法を提案する。第1のアプローチでは、インプットされたデータと$k$-nearestの隣人アルゴリズムとの共分散を推定し、第2のアプローチでは、期待最大化アルゴリズム内で観測データの可能性を活用することにより、観測データに依存する。その結果, 提案手法は観測データに基づく分類よりも優れており, 欠落したデータ比が増大しても高い精度を維持することができることがわかった。
論文参考訳（メタデータ） (2021-10-19T14:24:50Z)
Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
論文参考訳（メタデータ） (2021-10-03T05:38:49Z)
Highly Scalable and Provably Accurate Classification in Poincare Balls [40.82908295137667]
我々は、スケーラブルで単純な双曲型線形分類器を証明可能な性能保証で学習するための統一的なフレームワークを構築した。提案手法は,新しい双曲型および二階型パーセプトロンアルゴリズムと,双曲型サポートベクトルマシン分類器の効率的かつ高精度な凸最適化設定を含む。数百万の点からなる合成データセットと、シングルセルRNA-seq式測定、CIFAR10、Fashion-MNIST、mini-ImageNetのような複雑な実世界のデータセットの性能評価を行う。
論文参考訳（メタデータ） (2021-09-08T16:59:39Z)
Classify and Generate Reciprocally: Simultaneous Positive-Unlabelled Learning and Conditional Generation with Extra Data [77.31213472792088]
クラスラベルデータの不足は、多くの機械学習問題において、ユビキタスなボトルネックとなっている。本稿では, 正負ラベル付き(PU)分類と, 余分なラベル付きデータによる条件生成を活用することで, この問題に対処する。本稿では,PU分類と条件生成を併用した新たなトレーニングフレームワークを提案する。
論文参考訳（メタデータ） (2020-06-14T08:27:40Z)
A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文参考訳（メタデータ） (2020-06-07T14:47:07Z)
New advances in enumerative biclustering algorithms with online partitioning [80.22629846165306]
さらに、数値データセットの列に定数値を持つ最大二クラスタの効率的で完全で正しい非冗長列挙を実現できる二クラスタリングアルゴリズムであるRIn-Close_CVCを拡張した。改良されたアルゴリズムはRIn-Close_CVC3と呼ばれ、RIn-Close_CVCの魅力的な特性を保ちます。
論文参考訳（メタデータ） (2020-03-07T14:54:26Z)
Data Structures & Algorithms for Exact Inference in Hierarchical Clustering [41.24805506595378]
本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
論文参考訳（メタデータ） (2020-02-26T17:43:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。