確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究

Slides:



Advertisements
Similar presentations
1 再帰型神経回路網による 単語クラスタリングに関する研 究 兵藤 大輔 2002 / 2 / 18 北陸先端科学技術大学院大学 知識科学研究科 知識システム構築論講 座.
Advertisements

大規模コーパスから獲得した 名詞の出現パターンを用いた 事態名詞の項構造解析
遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
高度情報演習1A “テーマC” 実践 画像処理プログラミング 〜画像認識とCGによる画像生成〜 第四回 演習課題 画像中からの物体抽出処理(背景情報を手がかりとして) 芝浦工業大学 工学部 情報工学科 青木 義満 2006/05/15.
ラベル付き区間グラフを列挙するBDDとその応用
国内線で新千歳空港を利用している航空会社はどこですか?
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
ソシオン理論における 三者関係のシミュレーション
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
時空間データからのオブジェクトベース知識発見
遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
雑音重み推定と音声 GMMを用いた雑音除去
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
湘南工科大学 2013年12月10日 プログラミング基礎1 湘南工科大学情報工学科 准教授 小林 学.
ベイズ基準によるHSMM音声合成の評価 ◎橋本佳,南角吉彦,徳田恵一 (名工大).
発表日:平成15年4月25日 担当者:時田 陽一 担当箇所:第3章 誤差評価に基づく学習 3.1 Widrow-Hoffの学習規則
プログラム実行履歴を用いたトランザクションファンクション抽出手法
プログラム実行時情報を用いたトランザクションファンクション抽出手法
パターン認識とニューラルネットワーク 栗田多喜夫 2018/11/8 早稲田大学大学院理工学研究科講義.
サポートベクターマシン によるパターン認識
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
Bottom-UpとTop-Down アプローチの統合による 単眼画像からの人体3次元姿勢推定
決定木とランダムフォレスト 和田 俊和.
奈良女子大集中講義 バイオインフォマティクス (9) 相互作用推定
確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究
人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅.
音高による音色変化に着目した音源同定に関する研究
あらまし アンサンブル学習の大きな特徴として,多数決などで生徒を組み合わせることにより,単一の生徒では表現できない入出力関係を実現できることがあげられる.その意味で,教師が生徒のモデル空間内にない場合のアンサンブル学習の解析は非常に興味深い.そこで本研究では,教師がコミティマシンであり生徒が単純パーセプトロンである場合のアンサンブル学習を統計力学的なオンライン学習の枠組みで議論する.メトロポリス法により汎化誤差を計算した結果,ヘブ学習ではすべての生徒は教師中間層の中央に漸近すること,パーセプトロン学習では
第14章 モデルの結合 修士2年 山川佳洋.
WWW上の効率的な ハブ探索法の提案と実装
独立成分分析 5 アルゴリズムの安定性と効率 2007/10/24   名雪 勲.
構造情報に基づく特徴量を用いた グラフマッチングによる物体識別 情報工学科 藤吉研究室  EP02086 永橋知行.
深層学習を用いた音声認識システム 工学部 電気電子工学科 白井研究室 T213069 林健吉.
Introduction to Soft Computing (第11回目)
予測に用いる数学 2004/05/07 ide.
Data Clustering: A Review
15K1117 下窪 聖人 15K1013 坂本 倖輝 15K1112 黒川 晶太 15K1015 関根 修斗
分子生物情報学(3) 確率モデル(隠れマルコフモデル)に 基づく配列解析
計算の理論 II 前期の復習 -有限オートマトン-
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
顔特徴点移動量・点間距離変化量の組み合わせに基づく顔表情認識
論文紹介: “Joint Embedding of Words and Labels for Text Classification”
知識科学研究科 知識システム構築論講座 林研究室 佛明 智
ベイジアンネットワーク概説 Loopy Belief Propagation 茨城大学工学部 佐々木稔
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
第4章 識別部の設計 4-5 識別部の最適化 発表日:2003年5月16日 発表者:時田 陽一
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
Bottom-UpとTop-Down アプローチの組み合わせによる 単眼画像からの人体3次元姿勢推定
文法と言語 ー文脈自由文法とLR構文解析ー
「ICAによる顔画像特徴量抽出とSVMを用いた表情認識」
構造的類似性を持つ半構造化文書における頻度分析
ベイズ基準による 隠れセミマルコフモデルに基づく音声合成
パターン認識 ークラスタリングとEMアルゴリズムー 担当:和田 俊和 部屋 A513
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
人工知能特論II 第8回 二宮 崇.
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
1ーQー18 音声特徴量抽出のための音素部分空間統合法の検討
パターン認識特論 ADA Boosting.
誤差逆伝播法による ニューラルネットワーク (BackPropagation Neural Network, BPNN)
わかりやすいパターン認識 第3章 誤差評価に基づく学習 3.3 誤差逆伝播法.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
パターン認識特論 ADA Boosting.
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年8月1日 3.2 競合学習
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
教師がコミティマシンの場合のアンサンブル学習 三好 誠司(神戸高専) 原 一之(都立高専) 岡田 真人(東大,理研,さきがけ)
Presentation transcript:

確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究 北陸先端科学技術大学院大学 知識科学研究科 知識システム構築論講座 林研究室 近藤 雅之

発表の流れ 背景・目的 確率的学習アルゴリズム 単純再帰型回路網への適用 実験・結果 考察・まとめ

背景1 ニューラルネットワークの記号処理への応用 単純再帰型回路網(SRN)で単純なFSAの学習を行った (Schreiber et al.[1989]) 隠れ層の活性化パターンのクラスタが、FSAの各状態を表わしていると主張 2次結合の再帰型神経回路網(RNN)を用いて正規言語同定問題(Giles et al.[1992]) いくつかの場合にFSAの獲得に失敗している

背景2 SRNは正規言語を(条件付きで)学習できる 隠れ層の状態から、ネットワークがどのようなFSAを獲得したかわかる ネットワークを構成する素子の出力関数にシグモイド関数を用いている 活性値が連続値 → FSAの抽出困難

背景3 そこで線形閾値素子を用いる 線形閾値素子を用いた学習アルゴリズムが存在しなかった 活性値が離散値 → FSAの抽出容易 離散値であるために微分ができない  → BP法が適用できない しかし

背景4 確率的学習アルゴリズム(S-MLP)が提案される[櫻井,2001] 素子の出力が離散値である回路網を学習できる特徴に着目 線形閾値素子を用いている 大域的な収束性かつ高速 解が離散値で表現される → 解釈が容易 素子の出力が離散値である回路網を学習できる特徴に着目

研究の目的 S-MLPをSRNに適用し、実際にFSAを学習できるかどうかを調べる

確率的学習アルゴリズム 線形閾値素子からなる多層神経回路網(MLP)を対象とした学習アルゴリズム データ提示のたびに素子を確率的に選択 選択された素子への結合荷重をRosenblattのパーセプトロン・アルゴリズムに従い更新 本研究では、S-MLPを改良したPS-MLPを用いた

学習アルゴリズム I H O x1 x2 x3 y (yt) 0.5 w1 w2 w3 0.5 0.1 0.2

単純再帰型回路網(SRN) Elmanによって提案される。 RNNのもっとも単純なものの一つ。 一時刻前の隠れ層の出力をそのまま文脈層にコピーする。 過去の情報を持つ文脈層を入力に加えることにより、時系列のパターンを学習することができる。

モデル T=t+1 出力層 フィードバック 隠れ層 T=t 入力層 文脈層 図1 SRN:本研究もこのモデルを扱った

数値実験 初期値設定 正規文法の一例である富田文法を用いた 入力に対し、現在の状態が受理状態にあるか非受理状態にあるかを教示 結合荷重の初期値は-2.0~2.0の整数値をランダムに設定 文脈層の初期値は全て1.0と設定 正規文法の一例である富田文法を用いた 入力に対し、現在の状態が受理状態にあるか非受理状態にあるかを教示

数値実験2 富田文法の学習 以下の4種類について実験を行った 1. 奇数個の1の後に奇数個の0が続かない 2. 0が3つ以上連続しない 数値実験2 富田文法の学習 以下の4種類について実験を行った 1. 奇数個の1の後に奇数個の0が続かない 2. 0が3つ以上連続しない 3. 1と0の個数の差が3の倍数である 4. 0*1*0*1*

実験1 100回の試行中何回学習が収束するか 長さ3~6の文を40個、ランダムに生成 データ提示回数と平均収束時間を計測 隠れ層の素子数を変えて実験 表1 入力データの例:1 input 1 teacher

結果 実験1 全ての文法が、全ての試行で学習できた hidden units 3 4 5 data ave. 7877 4892 3836 結果 実験1 全ての文法が、全ての試行で学習できた 表2 1の実験結果 hidden units 3 4 5 data ave. 7877 4892 3836 max. 42449 30016 36645 min. 219 69 62 time ave. 1.92s 3.16s 1.01s right/wrong 30/10

実験2 長さ3~5までの全てのbitパターンを網羅したデータ 隠れ層の素子数を変えて実験 隠れ層の状態からFSAを抽出 3 ・・・ 5 表3 入力データと教師信号の例:1 length 3 ・・・ 5 input 000 001 010 11101 11110 11111 teacher 111 110 11100

結果 実験2 (1) 1、2、4の文法では最小状態数のFSAが得られた場合があった hidden units 3 4 5 結果 実験2 (1) 1、2、4の文法では最小状態数のFSAが得られた場合があった 表4 1の実験結果 hidden units 3 4 5 state Ave. 6.3 7.6 8.0 state min. 6 right/wrong 43/13

結果 実験2 (3) 初期状態 1入力の遷移 0入力の遷移 受理状態 非受理状態 図2 隠れ素子数3、4個の時の最小状態数のFSA

結果 実験2 (4) 初期状態 1入力の遷移 0入力の遷移 受理状態 非受理状態 図3 隠れ素子数5個の時の最小状態数のFSA

考察 S-MLP(PS-MLP)を用いたSRNはFSAを学習できる → S-MLPをSRNに適用できる 状態数が最小でも正解でない場合もあった 隠れ層の素子数が多い(自由度が高い)ほうが収束が速い 最小状態数のFSAを得にくいが、比較的少ない状態数に落ち着く

今後の課題 より複雑なFSAの学習について調べる 学習後のネットワークを用いて長い文でテストを行う 状態数の多いもの 学習後のネットワークを用いて長い文でテストを行う 言語学習の一般的な教示方法を用いてみる(文法獲得の可能性の調査) 文法的に正しい文の次単語を予測 各文が文か非文かを教示する S-MLPに関する課題 どのような確率分布を与えると最適か?

SRNへの適用(アルゴリズム) 各文にラベルを持たせる(収束か未収束) 各文の1入力毎にもラベルを持たせる アルゴリズム ランダムに文を選び、文の最初から計算する 文の途中で教師信号と異なる信号を出力したら、荷重更新をおこない、またその文の最初から計算をおこなう。また、全ての文を未収束とラベル付けする。 その文に関して、最後まで教師信号と同じ出力であれば、その文は収束したと見なし、収束のラベル付けを行う 以上を全ての文について行う。

学習アルゴリズム ラベル Data[1] 000000 satisfied unsatisfied ・・・ Data[x] 001001 110010 satisfied ・・・ Data[n] 111111 satisfied