論文の概要: Exact learning and test theory

• arxiv url: http://arxiv.org/abs/2201.04506v1
• Date: Wed, 12 Jan 2022 15:10:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-13 15:18:40.701819
• Title: Exact learning and test theory
• 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 and test theory, we study arbitrary infinite binary information systems each of which consists of an infinite set of elements and an infinite set of two-valued functions (attributes) defined on the set of elements. We consider the notion of a problem over information system, which is described by a finite number of attributes: for a given element, we should recognize values of these attributes. As algorithms for problem solving, we consider decision trees of two types: (i) using only proper hypotheses (an analog of proper equivalence queries from exact learning), and (ii) using both attributes and proper hypotheses. As time complexity, we study the depth of decision trees. In the worst case, with the growth of the number of attributes in the problem description, the minimum depth of decision trees of both types either is bounded from above by a constant or grows as a logarithm, or linearly. Based on these results and results obtained earlier for attributes and arbitrary hypotheses, we divide the set of all infinite binary information systems into seven complexity classes.
• Abstract（参考訳）: 本稿では、厳密な学習とテスト理論の結果に基づいて、各要素の無限集合と要素集合上に定義される2値関数(属性)の無限集合からなる任意の無限二元情報システムについて研究する。 我々は,情報システム上の問題の概念を有限個の属性によって記述する: 与えられた要素に対して,これらの属性の値を認識する必要がある。 問題解決のアルゴリズムとして,2種類の決定木を考える。 (i)適切な仮説(正確な学習からの適切な同値クエリの類似)のみを使用すること、及び (二)属性と適切な仮説の両方を用いる。 時間的複雑さとして、決定木の深さを研究する。 最悪の場合、問題記述における属性数の増加に伴い、両方のタイプの決定木の最小深さは、上から定数で区切られるか、対数として成長するか、あるいは線形に成長する。 これらの結果と、より早く得られた属性と任意の仮説に基づいて、無限のバイナリ情報システムの集合を7つの複雑性クラスに分割する。

関連論文リスト

• Greedy Algorithm for Inference of Decision Trees from Decision Rule Systems [0.0]
  決定木と決定ルールシステムは属性、知識表現ツール、アルゴリズムとして重要な役割を果たす。 本稿では,逆変換問題について考察する。 本研究は,決定木全体を構築する代わりに,与えられた属性に対する決定木の操作をシミュレートする欲求時間アルゴリズムに焦点を当てる。
  論文  参考訳（メタデータ） (2024-01-08T09:28:55Z)
• The Computational Complexity of Concise Hypersphere Classification [49.57441416941195]
  本稿では,二元データに対する超球分類問題の複雑性理論による最初の研究である。 パラメータ化複雑性のパラダイムを用いて、入力データに存在する可能性のある構造特性の影響を分析する。
  論文  参考訳（メタデータ） (2023-12-12T09:33:03Z)
• Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions [93.40614719648386]
  大規模言語モデル(LLM)は、知識集約的な複雑な質問にチェーン・オブ・シント(CoT)推論で答えることができる。 最近の研究は、CoT推論を強化するための外部知識の回収に向けられている。 確率的ツリー・オブ・シント推論(ProbTree)という新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2023-11-23T12:52:37Z)
• Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering [83.74210749046551]
  ヘテロジニアス知識統合のための質問分解手法を提案する。 階層的質問分解木(RoHT)を用いた新しい2段階XQAフレームワークを提案する。 複雑なQAデータセットKQA ProとMusiqueの実験は、我々のフレームワークがSOTAメソッドを著しく上回っていることを示している。
  論文  参考訳（メタデータ） (2023-05-24T11:45:59Z)
• Construction of Decision Trees and Acyclic Decision Graphs from Decision Rule Systems [0.0]
  本稿では,決定木を構成する複雑さと決定木を表す非周期決定グラフについて考察する。 決定木全体を構築しない可能性について論じるが、与えられた入力に対して、この木で計算経路を記述する。
  論文  参考訳（メタデータ） (2023-05-02T18:40:48Z)
• Regularized impurity reduction: Accurate decision trees with complexity guarantees [20.170305081348328]
  本稿では,木複雑性の対数近似を保証する木推論アルゴリズムを提案する。 改良されたアルゴリズムは予測精度と木の複雑さのバランスが良好である。
  論文  参考訳（メタデータ） (2022-08-23T13:15:19Z)
• Improved Quantum Query Upper Bounds Based on Classical Decision Trees [0.0]
  古典的なクエリアルゴリズムが決定木として与えられると、古典的なクエリアルゴリズムよりも高速な量子クエリアルゴリズムはいつ存在するのか? 我々は、下層の決定木の構造に基づく一般的な構成を提供し、これが上から四進的な量子スピードアップをもたらすことを証明している。
  論文  参考訳（メタデータ） (2022-03-06T14:04:06Z)
• Exact learning for infinite families of concepts [0.0]
  無限個の要素の集合とこの集合の無限個の部分集合からなる概念の任意の無限族について研究する。 有限個の要素によって記述される概念の族に対する問題の概念を考える。
  論文  参考訳（メタデータ） (2022-01-13T07:32:47Z)
• The Causal Neural Connection: Expressiveness, Learnability, and Inference [125.57815987218756]
  構造因果モデル (Structuor causal model, SCM) と呼ばれるオブジェクトは、調査中のシステムのランダムな変動のメカニズムと源の集合を表す。 本稿では, 因果的階層定理 (Thm. 1, Bareinboim et al., 2020) がまだニューラルモデルに対して成り立っていることを示す。 我々はニューラル因果モデル(NCM)と呼ばれる特殊なタイプのSCMを導入し、因果推論に必要な構造的制約をエンコードする新しいタイプの帰納バイアスを定式化する。
  論文  参考訳（メタデータ） (2021-07-02T01:55:18Z)
• Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
  我々は、本質的にすべての実数値論理をカバーするためにパラメータ化できる、音と強完全公理化を与える。 文のクラスは非常に豊かであり、各クラスは実数値論理の式の集合に対して可能な実値の集合を記述する。
  論文  参考訳（メタデータ） (2020-08-06T02:13:11Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。