線形言語のある部分言語族に対する質問を用いた確率的近似学習
スポンサーリンク
概要
- 論文の詳細を見る
本研究において,線形言語のある部分言語族に対する確率的な学習可能性を示す.形式言語の学習において,質問による学習の能力に関する研究は多く存在するが,確率的な学習に関する結果は少ない.確率的な学習のモデルにおいてPAC学習(確率的近似学習)は最も重要で多くの結果が得られているモデルの一つである.質問による学習における等価性質問は,PAC学習基準において多項式個のランダムサンプルに置き換えられることが示されている.しかし,それ以外の質問についてPAC学習との関連を示した結果は少ない.以前,我々は単純決定性言語について,所属性質問と代表部分集合と呼ばれる特殊なサンプルから多項式時間厳密学習可能であることを示し,代表部分集合をランダムサンプルから構成できる十分条件を示した.本研究において,強決定性線形言語と呼ばれる線形言語の部分言語族を定義し,この言語族が所属性質問を用いて多項式時間で確率的に学習可能であることを示す.これは,同言語族に対する厳密学習アルゴリズムを示し,そこから導かれる結果である.
- 2009-02-23
著者
-
但馬 康宏
東京農工大学共生科学技術研究院先端情報科学部門
-
小谷 善行
東京農工大学共生科学技術研究院先端情報科学部門
-
小谷 善行
東京農工大学大学院工学府
-
但馬 康宏
東京農工大学大学院工学府
-
但馬 康宏
電気通信大学電気通信学研究科電子情報学専攻
-
小谷 善行
東京農工大
-
但馬 康宏
東京農工大学 工学部 情報工学科
関連論文
- 系列パターンを利用した決定木による自然言語における選択ルール獲得(学習・系列解析・構文解析)
- SVMを用いたリズム感のモデル化とドラムパターンの自動生成(音楽生成)
- パケットの直接的な読み書きによるインターネットプロトコル学習システム( 遠隔教育/一般)
- 枝分かれ同時確率モデルを用いた「AのB」の意味分類(語彙・意味)
- すご@ぷろ : 双六をモチーフとしたビジュアルプログラミング言語
- 対話システムにおける顔文字の学習
- 特許明細書における多項請求項の自動構造化に関する研究(解析,分析)
- 構造解析を利用した機械学習による演奏表情の解析と付与(表情付け・分析)
- 枝分かれ同時確率モデルを用いた対象-属性-属性値関係の抽出(翻訳・要約・抽出)
- HMMとテキスト分類器による対話の段落分割
- 発話を出力単位とするHMMによる対話に対する話題分割
- 発話を出力単位とするHMMによる対話に対する話題分割(対話)
- Web資源からの決定木学習によるWebページに対するキーワード付与
- 枝分かれ構造を持つ同時確率モデルによる形態素解析
- 枝分かれモデルによるbi-gramからのtri-gram推定を用いたHMM形態素解析システム
- 枝分かれ構造をもつ同時確率モデルによる形態素解析
- GMDHニューラルネットワークを利用した自然言語の区切り位置予測の研究
- 単語長を考慮した最長しりとり問題の実験的考察
- 単語間情報とランダム性を利用した創造性を有する概念ネットワークの自動生成(概念・連想)
- 単語間情報とランダム性を利用した創造性を有する概念ネットワークの自動生成
- 文字数最大しりとり問題の解法
- 単語の結束度と文の表層情報を組み合わせたテキストセグメンテーション(セグメンテーション・要約)
- 相互情報量を用いた話題語集合による対話の応答選択(対話)
- 最大長しりとり問題の解法
- 言語クラスEMGを用いた不完全なシーケンスからの構造推定手法
- MTD(f)の改良と評価
- 「名詞と表層格」パターンに対する深層格対応の推測
- 隠れマルコフモデルを用いた曲構造を持つ音符列の生成
- 音楽記述文法EMGによる楽曲受理処理系の試作(セッション7 : モデルと文法)
- Hexゲームを解く
- パターンを使った構文解析
- 品詞列に基づく構文解析
- 発話の働きとキーワードから応答生成を行う事例ベース自由対話系
- 文節区切りのための品詞列統計情報の調査
- 将棋におけるDual Credit探索
- 将棋におけるプロの指し手とそれ以外の手の判別分析
- 対戦相手に合わせた評価関数の学習システム
- プロの棋譜を用いたTD法による将棋の評価関数の学習
- TD(λ,μ) : 未来の観測状態を考慮したTD法
- 未来の観測状態を考慮したTD法について
- 将棋プログラムにおける指し手の種類別探索深さの調整
- 将棋におけるゲーム木探索アルゴリズムの比較
- 1N-4 将棋におけるcost functionを用いた評価関数の調整
- 日本語アクセントの認識実験とメロディー自動生成
- 日本語アクセント生成システム
- 決定木学習による代名詞「自分」の照応解析(解析・言語資源)
- 5U-4 決定木学習を用いた人名情報抽出のための規則生成(情報抽出,学生セッション,人工知能と認知科学)
- 決定木を用いた中国語の疑問文の訳語選択ルールの生成(翻訳・多言語化)
- ニューラルネットワークを用いたコーパスからの共起強度の抽出
- コード進行と転回形の推移特徴に基づく伴奏生成
- メロディーに関連づけたアドリブの生成
- 線形言語のある部分言語族に対する質問を用いた確率的近似学習
- 先読みを教師とした兄弟局面の比較に基づく評価関数の学習(学習2 並列探索)
- 評価関数の強化学習における学習高速化手法(学習2 並列探索)
- 並列局面探索における待ち行列の負荷分散(学習2 並列探索)
- UCTアルゴリズムにおける確率的な試行回数削減方法
- 異なるレーティング・データの接合とコンピュータ将棋の強さ予測
- 5X-4 隠れマルコフモデルを用いた変奏の伴う楽曲の自動生成(音楽情報科学(4)表情付け・認知,学生セッション,人工知能と認知科学)
- モンテカルロシミュレーションを用いた強化学習法の提案
- 状態をもった内部表現でプログラムを保持するプログラミング教育環境の有効性の検討(情報教育/一般)
- コンピュータ将棋(思考ゲーム)
- ナップザック問題における解法拡張可能性の分析
- 枝分かれ同時確率モデルを用いた対象-属性-属性値関係の抽出(翻訳・要約・抽出)
- 枝分かれ同時確率モデルを用いた「AのB」の意味分類(語彙・意味)
- 決定木を用いた敬語の選択ルールの獲得
- 構造解析を利用した機械学習による演奏表情の解析と付与(表情付け・分析)
- IP Telephonyにおけるクライアント依存性を排除した多者間通話サービス(グループウェア)
- 曲の構造情報から表情付けを行う自動演奏
- 曲構造とメロディーのリズム解析による自動編曲
- 自動作曲システムにおけるリズムの生成法
- 曲構造中のモチーフ変形パターンに注目した自動作曲
- 1. コンピュータ将棋の歴史的瞬間 : プロ棋士に角落ちで勝利 : ついにプロの強さが射程範囲に(コンピュータが将棋を制する日)
- 飛車落ちのプロに勝ったコンピュータ将棋
- 6合目まできたコンピュータ将棋の実力
- 小中学校における情報教育向け電子教材開発環境の提案
- 高等学校教科「情報」向け電子教材の設計
- 5X-6 情報教育のための教育基本ソフトウェア・電子教材・教育支援プロジェクト
- Nested Monte-Carlo探索のAMAFを用いた探索数調整による改良
- 虫食い算の非探索的解決と問題作成への応用
- 押し相撲ゲームの分析と創造性教育への応用
- コンピュータ将棋の実力とその将来予測
- Dodgemゲームのレトログレード解析による解明
- ゲーム情報学の教育における意義 : 「情報技術が教育をどう変えるか?」へのゲームのかかわり
- 音高と音価の隠れマルコフモデルを用いた自動副旋律生成
- HMM とテキスト分類器による対話の段落分割
- Heptamond問題の全解数推定
- 勝率に近似させた評価関数の性能について
- 引き分けの証明向きのGHI問題対処法とその3x4将棋への応用(知識処理)
- 制限のあるサンプル分布における文脈自由文法の学習可能性
- 単語の偏りを表すネットワークを用いたウェブページに対するキーワード付け(語と慣用句)
- ニューラルネットワークを用いた多人数対話での対話の繋がり抽出(翻訳,対話)
- 隠れマルコフモデルを用いた副旋律推定
- 質問と反例による単純決定性言語の多項式時間学習を可能とさせる十分条件
- 単純決定性言語の学習におけるサンプル分布のある制限と学習可能性
- 線形言語のある部分言語族に対する多項式時間PAC学習可能性
- 線形言語のある部分言語族に対する質問と特徴的なサンプルによる多項式時間学習アルゴリズム (計算機科学基礎理論の新展開)
- 質問による文法推論アルゴリズムにおける等価性判定問題の一応用
- M-44 エージェントベースアクティブノードアーキテクチャの提案(アドホックネットワーク,M.ネットワーク・モバイルコンピューティング)
- SIPを用いた音声通話に対するNAT通過手法の提案とその実装(ネットワークプロトコル)
- SIPを利用した音声認識機能付きボイスメールシステム(セッション5B マルチメディア)