反例によるセルオートマトン上の決定リストの学習可能性
スポンサーリンク
概要
- 論文の詳細を見る
セルオートマトンにおいて連続する複数回の変換により得られる値は,変換規則を定める局所関数の合成関数によって与えられる.本論文では,決定リストを局所関数とする1次元セルオートマトン上の関数の多項式時間学習可能性,すなわち,決定リストの合成関数の多項式時間学習可能性を等価性質問によるExact学習モデルのもとで議論し,決定リストのある部分クラスの族が,リストの長さが定数のときに一様に学習可能であり,一方,リストの長さが入力の長さの多項式であるとき,NP≠Pの仮定のもとで一様には学習不可能であることを示す.
- 2002-04-01
著者
関連論文
- 反例によるセルオートマトン上の決定リストの学習可能性
- 直交F-ホーン式の学習アルゴリズム
- 単調DNF式の排他的論理和の学習可能性
- 読捨てコンテンツをいつ更新するべきか(アルゴリズム理論)
- 論理式における最小単調関数を変えない部分式の枝刈り(アルゴリズム)
- M-19 協調サーチエンジンにおける永続的キャッシュの実装(サービス・資源管理と応用(2),M.ネットワーク・モバイルコンピューティング)
- L-14 高スループット更新のパイプライン化Webロボット(Webシステム,L.インターネット)
- 協調サーチエンジンにおける永続的キャッシュ
- 最新情報の検索のための分散型サーチエンジン(マルチメディアコミュニケーションシステム)
- 弱制約最長共通部分配列問題
- 差異獲得を用いた弱PAC学習に十分な仮説クラス
- DNF式を用いた素朴なブースティングアルゴリズム
- PAC学習における差異獲得
- 協調サーチエンジン:最新情報の検索に適した分散型サーチエンジン
- LEARNING MONOTONE LOG-TERM DNF FORMULAS
- 単調O(log n)項DNF式の学習
- 最長共通部分配列計算における run 長の対数時間寄与 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 海草全単射の漸減構築 (アルゴリズムと計算理論の新展開)