和集合のサイズの近似評価を用いたDNF式の学習について
スポンサーリンク
概要
- 論文の詳細を見る
任意分布のもとでの多項式サイズDNF式の学習可能性およびその限界について論じる。この問題について、最近Bshooutyは2^O(√<n>(logn)^2)という学習時間アルゴリズムを設計した。本論文では、同様の学習時間が単純な仮説検索アルゴリズムによっても達成されることを示す。さらに、DNF式が未知変数を含むという仮定のもとで、2^Ω(√<n>(logn))という学習時間の下界も示す.これらの結果はいずれもLinialとNisanによる和集合のサイズの近似評価を応用することで導かれる.
- 社団法人電子情報通信学会の論文
- 1998-07-23
著者
-
築地 立家
名古屋大学大学院
-
築地 立家
名古屋大学人間情報学研究科
-
築地 立家
名古屋大学情報文化学部自然情報学科
-
築地 立家
名古屋大学人間情報学部
-
垂井 淳
電気通信大学情報通信工学科
-
垂井 淳
電気通信大学情報理工学研究科情報・通信工学専攻
-
垂井 淳
電気通信大学 情報理工学研究科 情報・通信工学専攻
-
垂井 淳
電気通信大学情報理工学研究科
関連論文
- 量子オラクルを用いた唯一最短格子ベクトル問題の効率的解法
- [チュートリアル講演]最小値独立置換族に関する最近の成果
- 最小値独立置換族に関する最近の成果
- 有限幾何を用いた線形サイズ4-制限最小値独立置換族の構成
- k-制限最小値独立置換族,その他k-wise独立性のサンプルサイズ下界
- 置換族とその独立性の解析
- 集中討論:DeolalikarのP≠NP論文をめぐって
- 否定数限定論理回路におけるマージングの複雑さ
- 平面グラフのC^^-_7彩色問題の計算複雑さ
- 平均次数の高いVC-PMの近似アルゴリズム (計算機科学基礎理論の新展開)
- 一様分布上での関係変数の量子学習
- 一般化された対称動作をするラングトンの蟻問題のPSPACE完全性
- 連続王手制限付き一般化チェス問題の指数時間完全性
- 唯一の必勝法を持つ二人ゲームの複雑さ
- 一般化詰将棋問題の指数時間完全性
- 手数制限付き一般化詰め将棋のPSPACE完全性について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- O(log n)長の単調単項式の負例学習について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 一般化詰将棋問題の指数時間完全性について
- 一般化詰め将棋のPSPACE困難性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 平均時計算量における2-tt還元とmany-one還元の違いについて (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- $O(\log n)$長の単調単項式の負例学習について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 一方向性関数の平均時間計算量解析
- A note on lower bounds on constant-depth modular circuits
- Negation-Limited Complexity of Parity and Inverters(Theory of Computer Science and Its Applications)
- Learning DNF by Approximating Inclusion-Exclusion Formulae (Models of Computation and Algorithms)
- 和集合のサイズの近似評価を用いたDNF式の学習について
- オンライン投資問題 (計算機科学基礎理論の新展開)
- On the Depth of Randomly Generated Circuits
- あるノイズモデルにおけるブール関数学習について
- フェイステル変換を用いた近似的k-対ランダム置換族の構成
- kトニックな0/1列に対する線形サイズ対数深さの否定数限定インバータ
- 回路計算量における和算と乗算のある違いについて
- ブール関数のsensitivity, block sensitivity, certificate complexity について
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 計算の複雑さと証明の複雑さ : 基調講演 (証明論と複雑性)