O(log n)長の単調単項式の負例学習について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
冗長な変数を多量に含むデータを解析し, その最も簡潔な表現式を導出するアルゴリズムの研究は, 機械学習論の分野で盛んに行われてきた.本論文では, n-bitの負例集合が与えられたとき, それらと無矛盾なO(log n)長の単調単項式を(そのような仮説が存在しない場合はその事実を)発見する問題を考察する.この問題はβ_2と呼ばれる計算量クラスに属する.本論文では, 目標関数の変数が等分割ブロックに均等に出現するように問題を制限したとき, この問題がO(log^2 n)個の入力変数をもつ深さ3のII^0_3回路の充足解発見問題と対数領域還元について同値であることを示す.したがって, P-POLYLOG-SPACE≠φであるならば, この問題はβ_2-完全ではない.一方, NP≠DTIME(2^O(√<n>))であれば, この問題を多項式時間で学習することもできない.このように, 最悪の場合, O(log n)長の単調多項式の負例集合は学習困難であると考えられる.そこで, 一様ランダムにサンプルされた負例集合の多項式時間での学習可能性について議論する.
- 社団法人電子情報通信学会の論文
- 2001-01-01
著者
関連論文
- 量子オラクルを用いた唯一最短格子ベクトル問題の効率的解法
- 平面グラフの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
- Learning DNF by Approximating Inclusion-Exclusion Formulae (Models of Computation and Algorithms)
- 和集合のサイズの近似評価を用いたDNF式の学習について
- オンライン投資問題 (計算機科学基礎理論の新展開)
- On the Depth of Randomly Generated Circuits
- 回路計算量における和算と乗算のある違いについて