論文の概要: Exact learning for infinite families of concepts
- arxiv url: http://arxiv.org/abs/2201.08225v1
- Date: Thu, 13 Jan 2022 07:32:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-23 17:57:33.253587
- Title: Exact learning for infinite families of concepts
- Title（参考訳）: 無限の概念族に対する厳密な学習
- Authors: Mikhail Moshkov
- Abstract要約: 無限個の要素の集合とこの集合の無限個の部分集合からなる概念の任意の無限族について研究する。
有限個の要素によって記述される概念の族に対する問題の概念を考える。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, based on results of exact learning, test theory, and rough set
theory, we study arbitrary infinite families of concepts each of which consists
of an infinite set of elements and an infinite set of subsets of this set
called concepts. We consider the notion of a problem over a family of concepts
that is described by a finite number of elements: for a given concept, we
should recognize which of the elements under consideration belong to this
concept. As algorithms for problem solving, we consider decision trees of five
types: (i) using membership queries, (ii) using equivalence queries, (iii)
using both membership and equivalence queries, (iv) using proper equivalence
queries, and (v) using both membership and proper equivalence queries. As time
complexity, we study the depth of decision trees. In the worst case, with the
growth of the number of elements in the problem description, the minimum depth
of decision trees of the first type either grows as a logarithm or linearly,
and the minimum depth of decision trees of each of the other types either is
bounded from above by a constant or grows as a logarithm, or linearly. The
obtained results allow us to distinguish seven complexity classes of infinite
families of concepts.
- Abstract（参考訳）: 本稿では、厳密な学習、テスト理論、粗い集合論の結果に基づいて、各概念の任意の無限族について、無限個の元からなる集合と、この集合の無限個の部分集合からなる集合を概念と呼ぶ。
有限個の要素によって記述される概念の族に対する問題の概念を考える: 与えられた概念に対して、検討中の要素のどれがこの概念に属するかを認識するべきである。
問題解決のアルゴリズムとして,5種類の決定木を考える。
(i)会員クエリーの使用。
(ii)同値クエリの使用。
(iii)会員資格問合せと等価性問合せの両方を用いて
(iv)適切な同値クエリの使用、及び
(v) メンバシップと適切な等価クエリの両方を使用する。
時間的複雑さとして、決定木の深さを研究する。
最悪の場合、問題記述の要素数の増加に伴い、第1のタイプの決定木の最小深さは対数として、あるいは線形に成長し、他の各タイプの決定木の最小深さは、上から定数で、あるいは対数として、あるいは線形にバインドされる。
得られた結果は、概念の無限族からなる7つの複雑性クラスを区別することができる。
関連論文リスト
- Properly Learning Decision Trees with Queries Is NP-Hard [5.117810469621253]
PACがクエリで決定木を適切に学習することはNPハードであることを証明する。
我々は、決定木最小化の異なる問題に対して、最もよく知られた下界を単純化し、強化する。
論文 参考訳（メタデータ） (2023-07-09T04:29:43Z) - Enriching Disentanglement: From Logical Definitions to Quantitative Metrics [59.12308034729482]
複雑なデータにおける説明的要素を遠ざけることは、データ効率の表現学習にとって有望なアプローチである。
論理的定義と量的指標の関連性を確立し, 理論的に根ざした絡み合いの指標を導出する。
本研究では,非交叉表現の異なる側面を分離することにより,提案手法の有効性を実証的に実証する。
論文 参考訳（メタデータ） (2023-05-19T08:22:23Z) - A Category-theoretical Meta-analysis of Definitions of Disentanglement [97.34033555407403]
データの変化の要因を識別することは、機械学習の基本的な概念である。
本稿では,既存の乱れの定義をメタ分析する。
論文 参考訳（メタデータ） (2023-05-11T15:24:20Z) - Logic for Explainable AI [11.358487655918676]
説明可能なAIにおける中心的な探求は、(学習された)分類器による決定を理解することである。
本チュートリアルでは,これらの次元に沿った説明可能性に関する包括的・意味的・計算的理論について論じる。
論文 参考訳（メタデータ） (2023-05-09T04:53:57Z) - Synergies between Disentanglement and Sparsity: Generalization and
Identifiability in Multi-Task Learning [79.83792914684985]
我々は,最大スパース基底予測器が不整合表現をもたらす条件を提供する新しい識別可能性の結果を証明した。
この理論的な結果から,両レベル最適化問題に基づくアンタングル表現学習の実践的アプローチを提案する。
論文 参考訳（メタデータ） (2022-11-26T21:02:09Z) - Regularized impurity reduction: Accurate decision trees with complexity
guarantees [20.170305081348328]
本稿では,木複雑性の対数近似を保証する木推論アルゴリズムを提案する。
改良されたアルゴリズムは予測精度と木の複雑さのバランスが良好である。
論文 参考訳（メタデータ） (2022-08-23T13:15:19Z) - Joint Abductive and Inductive Neural Logical Reasoning [44.36651614420507]
結合誘導型および誘導型ニューラル論理推論(AI-NLR)の問題点を定式化する。
まず、概念の源を提供するために、記述論理に基づく存在論的公理を組み込む。
そして、概念とクエリをファジィ集合として表現し、すなわち、要素がメンバシップの度合いを持つ集合を概念とクエリをエンティティでブリッジする。
論文 参考訳（メタデータ） (2022-05-29T07:41:50Z) - Improved Quantum Query Upper Bounds Based on Classical Decision Trees [0.0]
古典的なクエリアルゴリズムが決定木として与えられると、古典的なクエリアルゴリズムよりも高速な量子クエリアルゴリズムはいつ存在するのか?
我々は、下層の決定木の構造に基づく一般的な構成を提供し、これが上から四進的な量子スピードアップをもたらすことを証明している。
論文 参考訳（メタデータ） (2022-03-06T14:04:06Z) - Exact learning and test theory [0.0]
任意の無限二元情報システムについて検討し、そのそれぞれが無限個の要素からなる。
本稿では,有限個の属性によって記述される情報システムに関する問題について考察する。
論文 参考訳（メタデータ） (2022-01-12T15:10:22Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
我々は、本質的にすべての実数値論理をカバーするためにパラメータ化できる、音と強完全公理化を与える。
文のクラスは非常に豊かであり、各クラスは実数値論理の式の集合に対して可能な実値の集合を記述する。
論文 参考訳（メタデータ） (2020-08-06T02:13:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。