順序付き二分法定グラフの学習可能性
スポンサーリンク
概要
- 論文の詳細を見る
順序付き二分決定グラフ(ordered binary decision diagrams, OBDD)は,プール関数を有向非巡回グラフで表現する.本論文では,このOBDDの学習可能性について議論する.まず,n変数全対称対称関数を表現するOBDDは,高々n+1回の等価性質問,もしくはちょうどn+1回の所属性質問を用いて多項式時間学習可能であることを示す.また,n変数のリテラルの連言,選言を表現するOBDDは,高々n回の等価性質問を用いて多項式時間学習可能であることを示す.したがって,これらはすべて多項式時間PAC学習可能となる.
- 社団法人電子情報通信学会の論文
- 1995-11-17
著者
-
平田 耕一
九州工業大学情報工学研究院
-
松本 哲志
東海大学理学部
-
篠原 歩
九州大学理学部基礎情報学研究施設
-
松本 哲志
九州大学理学部基礎情報学研究施設
-
篠原 歩
九大 大学院システム情報科学研究院
-
平田 耕一
九州工業大学
関連論文
- 人工知能基本問題研究会(SIG-FPAI)(研究会総覧)
- 九州大学における一般情報処理教育支援システムについて
- 繰り返し内部構造変数を持つ木パターンの有限和の質問学習
- 高さ制約変数を持つ順序木パターン言語の正データからの多項式時間帰納推論可能性について
- Polynomial Time Learnabilities of Tree Patterns with Internal Structured Variables from Queries (New Aspects of Theoretical Computer Science)
- Polynomial Time Inductive Inference of Ordered Term Trees with Contractible Variables from Positive Data (New Aspects of Theoretical Computer Science)
- Learning of Elementary Formal Systems with Two Clauses using Queries and Their Languages(New Trends in Theory of Computation and Algorithm)
- 帰納的実数値関数の帰納推論における論駁性と信頼性(アルゴリズム一般)
- 帰納的実数値関数の帰納推論における論駁性と信頼性
- ラベル無し順序木のqグラム距離
- 内部変数付き木パターン言語の有限和の質問学習
- 質問学習における学習可能性の統一的特徴づけ
- Learning pattern languages using queries
- Learnability of Subsequence Languages
- 順序付き二分法定グラフの学習可能性
- 反駁PAC学習可能性
- 類推機能をもった対話型シークェント計算証明システムの開発(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- 並列知識獲得システムBONSAI Garden
- 薬剤取り違え防止のための医薬品名類似性指標 (特集 「医療及び化学情報マイニング」および一般)
- 1変数文字列方程式の最小解の長さの上限
- 圧縮されたテキスト上のパターン照合 : データ圧縮とパターン照合の新展開
- 断片パターンマッチングの計算量的困難性と近似アルゴリズムについて
- 平衡直線的プログラムに対するパターン照合アルゴリズム
- 2G-2 圧縮テキストに対する文字列照合のための統一的枠組み
- 2G-1 データ圧縮による文字列照合の高速化
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- 直列エピソードから構成可能なエピソードのグラフ理論的性質 (特集 「ウェブマイニング」および一般)
- 人間指向型汎用類推証明システムの開発 (計算機科学基礎理論の新展開)
- 類推機能をもった対話型シークェント計算証明システムの開発 (計算機科学基礎理論の新展開)
- Pre-Checkingに基づく効率的スキーママッチングアルゴリズム(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- Pre-checkingを用いた効率的2階述語マッチングアルゴリズム (計算理論とアルゴリズムの新展開)
- スキーママッチングを用いたLK類推証明システムの開発
- スキーママッチングとその計算量
- スキーママッチングにおける計算の複雑さ (計算モデルとアルゴリズム)
- スキーママッチングの計算の複雑さ
- 古典的証明に基づく関数型言語の構築
- 正規パターン言語の和集合の質問学習
- A Catalog for Prediction-Preserving Reducibility with Membership Queries on Formal Languages (New Developments of Theory of Computation and Algorithms)
- ALT'96報告
- 無矛盾最小OBDD問題の近似困難性について
- ゲノムデータベース(5)配列データからの知識発見
- LZW圧縮テキストに対する高速文字列照合アルゴリズム
- コンピュ-タの推論による知識発見の支援(情報) (ゲノムサイエンス--生命の全体像の解明をめざして) -- (第1部 日本におけるヒト・ゲノム研究の最前線)
- 短縮記述された文字列上での多項式時間照合アルゴリズム
- ALT '94報告
- 石灰石球の熱分解における熱移動と CO_2 ガスの流れ
- 32 石灰石球の熱分解における熱及び物質の移動(製銑基礎・コークス, 製銑, 日本鉄鋼協会第 84 回(秋季)講演大会)
- 一階論理式の学習と帰納論理プログラミング (計算学習理論の進展と応用可能性)
- 決定可能な高階単一化問題に関する研究 (アルゴリズムと計算の理論)
- 単純型付きラムダ計算における証明文法
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- 型付ラムダ計算における証明文法
- 超辺の縮約を許した非巡回部分超グラフの効率よい列挙
- 木編集距離の研究動向(編集委員今年の抱負2013)
- PAC 学習 : 確率的で近似的に正しい学習 (計算的学習理論とその応用)