系列パターンマイニングを用いた有効な素性の組み合わせの発見

Slides:



Advertisements
Similar presentations
言語情報を利用したテキストマイニ ング 奈良先端科学技術大学院大学 情報科学研究科 工藤 拓 山本 薫 坪井 裕太 松本 裕治.
Advertisements

言語情報を利用したテキストマイニ ング 奈良先端科学技術大学院大学 情報科学研究科 工藤 拓 山本 薫 坪井 裕太 松本 裕治.
だい六か – クリスマスとお正月 ぶんぽう. て form review ► Group 1 Verbs ► Have two or more ひらがな in the verb stem AND ► The final sound of the verb stem is from the い row.
第 5 章 2 次元モデル Chapter 5 2-dimensional model. Contents 1.2 次元モデル 2-dimensional model 2. 弱形式 Weak form 3.FEM 近似 FEM approximation 4. まとめ Summary.
Essay writing rules for Japanese!!. * First ・ There are two directions you can write. ・よこがき / 横書き (same as we write English) ・たてがき / 縦書き (from right to.
大規模コーパスから獲得した 名詞の出現パターンを用いた 事態名詞の項構造解析
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
テキストデータベースからの 構文構造のマイニング
Building text features for object image classification
人工知能特論 8.教師あり学習と教師なし学習
シーケンシャルパターンマイニングに基づくオブジェクト指向プログラムのための 欠陥検出手法
半構造化テキストの分類のための ブースティングアルゴリズム
Support Vector Machine による日本語係り受け解析
部分木に基づくマルコフ確率場と言語解析への適用
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
Object Group ANalizer Graduate School of Information Science and Technology, Osaka University OGAN visualizes representative interactions between a pair.
Paper from PVLDB vol.7 (To appear in VLDB 2014)
先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning
部分木を素性とする Decision Stumps と Boosting Algorithm の適用
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
日本大学 文理学部 情報システム解析学科 谷研究室 益田真太郎
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
日本語解析済みコーパス管理ツール 「茶器」
動詞の共起パターンを用いた 動作性名詞の述語項構造解析
静的情報と動的情報を用いた プログラムスライス計算法
The Syntax of Participants シンタックスの中の話者と聞き手
識別子の命名支援を目的とした動詞-目的語関係の辞書構築
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
正規分布における ベーテ近似の解析解と数値解 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
オブジェクト指向プログラムにおける エイリアス解析手法の提案と実現
人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅.
音高による音色変化に着目した音源同定に関する研究
雑音環境下における 非負値行列因子分解を用いた声質変換
音響伝達特性を用いた単一マイクロホンによる話者の頭部方向の推定
Macro Tree Transducer の 型検査アルゴリズム
コードクローン検出ツールを用いた ソースコード分析システムの試作と プログラミング演習への適用
動的データ依存関係解析を用いた Javaプログラムスライス手法
2018/9/10 ACL読み会 名古屋大学大学院 M2 佐藤・松崎研 土居裕典.
分子生物情報学(2) 配列のマルチプルアライメント法
類似度を用いた WWW のリンク構造の解析 谷 研究室    栗原 伸行.
系列ラベリングのための前向き後ろ向きアルゴリズムの一般化
GPGPUによる 飽和高価値 アイテム集合マイニング
不確実データベースからの 負の相関ルールの抽出
データ圧縮技術による文字列照合処理の高速化に関する研究
22 物理パラメータに陽に依存する補償器を用いた低剛性二慣性系の速度制御実験 高山誠 指導教員 小林泰秀
顔特徴点移動量・点間距離変化量の組み合わせに基づく顔表情認識
Number of random matrices
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
北大MMCセミナー 第62回 附属社会創造数学センター主催 Date: 2016年11月4日(金) 16:30~18:00
サポートベクターマシン Support Vector Machine SVM
「ICAによる顔画像特徴量抽出とSVMを用いた表情認識」
Created by L. Whittingham
北大MMCセミナー 第16回 Date:2013年11月8日(金)16:30~18:00
A02 計算理論的設計による知識抽出モデルに関する研究
PROGRAMMING IN HASKELL
ICML読む会資料 (鹿島担当) 教師ナシ の 構造→構造 マッピング 読んだ論文: Discriminative Unsupervised Learning of Structured Predictors Linli Xu (U. Waterloo) , … , Dale Schuurmans.
並列構造に着目した係り受け解析の改善に関する研究
PROGRAMMING IN HASKELL
モデルの微分による非線形モデルの解釈 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
Webページタイプによるクラスタ リングを用いた検索支援システム
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
ガウシアングラフィカルモデルにおける一般化された確率伝搬法
識別子の読解を目的とした名詞辞書の作成方法の一試案
グラフ-ベクトル変換を用いたグラフ構造表現による一般物体認識
Normalized Web Distanceを用いた音声認識の誤り訂正法 301-4in
アノテーションガイドラインの管理を行う アノテーションシステムの提案
FSE/ASE勉強会 A10:Software Maintenance II
Presentation transcript:

系列パターンマイニングを用いた有効な素性の組み合わせの発見 奈良先端科学技術大学院大学 情報科学研究科 工藤 拓 松本 裕治

背景 SVM をはじめとする Kernel Method のめざましい進展 自然言語処理も例外ではない テキストチャンキング 固有名詞抽出 構文解析 Kernel Method は万能なのか?

Kernel Method の問題点 有効な素性の分析が困難 分類の計算量が大きい GOAL: この2つの問題の克服 素性空間が陰に表現される 有効な素性(事例の部分構造)は我々の知らない一種の知識 (マイニング) 分類の計算量が大きい Kernel Method に基づくチャンカーや構文解析器は大規模テキストデータの解析に不向き GOAL: この2つの問題の克服

ケーススタディ(日本語係り受け) SVM に基づく日本語係り受け解析システム「南瓜」 新聞記事数年分を解析するのに 数週間 2000年 Perl + C++ プロトタイプ 2-3秒/文 2001年 春 C++ で再実装 0.4秒/文 2001年 夏 データ構造の工夫 0.3秒/文 新聞記事数年分を解析するのに 数週間 ちなみに.. 形態素解析 0.0001秒/文 SVMの分類アルゴリズムを改良しない限り、これ以上の高速化は無理

本発表の流れ Kernel Method Power Set Kernel Power Set Kernel の高速化手法 PSKB (ベースライン) PSKI (提案手法 1) PSKE (提案手法 2) 日本語係り受けタスクにおける実験 考察、今後の課題

本発表の流れ Kernel Method Power Set Kernel Power Set Kernel の高速化手法 PSKB (ベースライン) PSKI (提案手法 1) PSKE (提案手法 2) 日本語係り受けタスクにおける実験 考察、今後の課題

Kernel Method 事例間の内積を与える Kernel 関数のみ定義 陽に表現された素性ベクトルは不要 事例 x の構造に基づく Kernel の設計   (集合, ベクトル, 系列, 木, グラフのノード    グラフ…)

Kernel Method の問題点 分類に O(L・m) の計算量 (m は K(・,・)の計算量) 素性空間が陰に表現されてしまい, 有効な素性の   提示が困難

本発表の流れ Kernel Method Power Set Kernel Power Set Kernel の高速化手法 PSKB (ベースライン) PSKI (提案手法 1) PSKE (提案手法 2) 日本語係り受けタスクにおける実験 考察、今後の課題

Power Set 集合のすべての部分集合の集まりをべき集合(Power Set)とよぶ 集合 X の Power Set を P(X)と記す 例 X={a,b,c} P(X)={φ,{a},{b},{c},{a,b},{a,c}, {b,c},{a,b,c}}

(Special) Power Set Kernel X, Z は集合 X の要素数を |X|と記す K(X, Z) = | P(X) ∩ P(Z) |=2 |X∩Z| 例 X = {a,b,c}, Z={a,b,d} P(X) = {φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} P(Z) = {φ,{a},{b},{d},{a,b},{a,d},{b,d},{a,b,d}} P(X)∩P(Z)={φ,{a},{b},{a,b}} K(X,Z) = |P(X) ∩ P(Z)| = 4

Power Set Kernel (PSK) (部分集合重み) (例) X = {a,b,c}, Z={a,b,d}, C0=2, C1=3, C2=1, C3=0 P(X) = {φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} P(Z) = {φ,{a},{b},{d},{a,b},{a,d},{b,d},{a,b,d}} P(X)∩P(Z)={φ,{a},{b},{a,b}} K(X,Z) = 2・1+ 3・2 + 1・1 + 0・0 = 9

PSK の周辺定理 X,Zを任意の集合, を正の整数とするとき, は PSK となる X,Zを任意の集合,  を n階微分可能でかつ となる関数とするとき,   はPSKとなる すべての PSK K(X,Z) は, |X∩Z|の多項式で表現できる Cr が事前に分かる場合, PSK を設計できる

多項式Kernel 定理2を満たし, Power Set Kernel 例 d=2 のとき C0 = 1, C1=3, C2=2 d=3 のとき C0 = 1, C1=7, C2=12, C3 = 6 一般に d=k のとき

RBF Kernel |X|=|Z|=定数 (要素数は一定) ならば 定理2を満たし, Power Set Kernel

本発表の流れ Kernel Method Power Set Kernel Power Set Kernel の高速化手法 PSKB (ベースライン) PSKI (提案手法 1) PSKE (提案手法 2) 日本語係り受けタスクにおける実験 考察、今後の課題

Power Set Kernel の高速化 PSKB PSKI (Inverted representation) 通常の分類手法(ベースライン) PSKI (Inverted representation) 事例 の集合を転置した形で表現 PSKE (Expanded representation) 事例を Power Set の空間で分類

PSKB (ベースライン) K(X,Z) = (|X∩Z|+1) α X {a, b, c} {a, b, d} {b, c, d} 1 2 3 K(X,Z) = (|X∩Z|+1) α X サポート ベクター {a, b, c} {a, b, d} {b, c, d} K(X,Z) 1 2 3 1 0.5 -2 分類したい事例 Z={a,c,e} 3 3 3 f(Z)=1・(2+1) + 0.5・(1+1) - 2 (1+1) = 15 計算量は常に O(L・|Z|)

PSKI (Inverted Representation) 3 K(X,Z) = (|X∩Z|+1) α X Inverted Representation 分類したい事例 Z= {a, c, e} a b c d {1,2} {1,2,3} {1,3} {2,3} {a, b, c} {a, b, d} {b, c, d} 1 2 3 1 0.5 -2 3 3 3 f(Z)=1・(2+1) + 0.5・(1+1) - 2 (1+1) = 15 計算量は, 最悪 O(L・|Z|) 集合要素が疎な時に有効(自然言語処理など)

PSKE (Expanded Representation) (1/2) PSK における は, 集合 X を, Power Set の 空間に部分集合重み付きで写像するような関数 w をあらかじめ計算しておき, 高次元空間空間 (Power Set 空間)での内積を直接計算 [磯崎 2002] と考え方は同じ

PSKE (Expanded Representation) (2/2) C w 展開テーブル 3 K(X,Z) = (|X∩Z|+1) φ {a} {b} {c} {d} {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} {a,b,c} {a,b,d} {a,c,d} {b,c,d} 1 -0.5 10.5 -3.5 -7 -10.5 12 6 -12 -18 -24 3 分類したい事例 Z={a,c,e} 7 Cr の算出 α X 12 P(Z)={{φ},{a},{c}, {e},{a,c},{a,e}, {c,e},{a,c,e}} 展開 {a, b, c} {a, b, d} {b, c, d} 1 2 3 1 0.5 -2 6 F(z)=-0.5+10.5-7+12 =15 計算量は O(|P(Z)|), 事例数に依存しない 事例数が大きいときに有効 d次の多項式 Kernel → d個の部分集合のみ

PSKEの実際 展開テーブル の作成 展開テーブル の保持 素性の d個の組み合わせを全展開するのは非常に困難 (係り受けの素性は 4万程度) [磯崎2002]は 2個の組み合わせだけに限定 |w|は, その部分集合の分類寄与度を与える. |w|の小さい部分集合は考えない(近似) データマイニングアルゴリズムの適用 展開テーブル の保持 そのままでは冗長なので TRIE を作成

マイニング問題としての定式化 |w|≧σ となるような部分集合を もれなく 効率よく 列挙せよ 例 σ=10 C w φ {a} {b} {d} {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} {a,b,c} {a,b,d} {a,c,d} {b,c,d} 1 -0.5 10.5 -3.5 -7 -10.5 12 6 -12 -18 -24 3 7 C w {a} {d} {a,b} {a,c} {b,c} {b,d} {c,d} {b,c,d} 10.5 -10.5 12 -12 -18 -24 7 σ=10 12 12 6 6

部分集合のマイニング(1/3) αは実数で, 単純な頻度とみなせない 正例,負例の数には偏りがある 正例(α≧0),負例(α<0)の事例に分けてそれぞれ独立にマイニング 部分集合 p の重み w は (正例の頻度)-(負例の頻度) となる 正例,負例の数には偏りがある σを正負例の数に応じて線形分配し, 正負別々の最小サポート値を与える サイズ r の部分集合の頻度は Cr 倍される 最悪の状況 Cmax=max(C0,C1,..,C|x|) を考え, 事例の頻度を Cmax倍しておく マイニング後, パターンp の頻度を C|p|/ Cmax 倍

部分集合のマイニング (3/3) σ=15 α X K(X,Z)= (|X∩Z|+1) |Cmax・α|を C0=1, C1=7,C2=12 部分集合のマイニング (3/3) 3 バスケットマイニング (Apriori, PrefixSpan) K(X,Z)= (|X∩Z|+1) |Cmax・α|を 頻度とみなす C0=1, C1=7,C2=12 C3=6, Cmax=12 φ 18 {a} 18 {b} 18 {c} 12 {a,b} 18 {a,c} 12 {b,c} 12 merge 頻度 X 正例 {a} 10.5 {b} –10.5 {a,b} 12 {a,c} 12 {b,c} -12 {b,d} -18 {c,d} -24 {b,c,d} -12 σ=15 σ正例=10 σ負例=5 1 2 12 6 {a, b, c} {a, b, d} Minsup=10 α X φ 24 {b} 24 {c} 24 {d} 24 {b,c} 24 {b,d} 24 {c,d} 24 {b,c,d} 24 負例 頻度 X 1 2 3 1 0.5 -2 {a, b, c} {a, b, d} {b, c, d} w= (f正例-f負例)・ C|p|/Cmax 3 24 {b, c, d} (例) {b} の重み W=(18-24)*7/12=10.5 Minsup=5

TRIEによる表現 共通 Prefix の圧縮 TRIE の実装にはダブル配列を用いた root a b c d b c c d d d w {a,c} {b,c} {b,d} {c,d} {b,c,d} 10.5 -10.5 12 -12 -18 -24 a b c d 10.5 -10.5 b c c d d -24 12 12 -12 -18 d -12 共通 Prefix の圧縮 TRIE の実装にはダブル配列を用いた

本発表の流れ Kernel Method Power Set Kernel Power Set Kernel の高速化手法 PSKB (ベースライン) PSKI (提案手法 1) PSKE (提案手法 2) 日本語係り受けタスクにおける実験 考察, 今後の課題

実験 日本語係り受け解析[工藤,松本2002] 3次の多項式 Kernel マイニング→PrefixSpan [Peiら 2000] 学習データ数 110,355 SV数(正例/負例) 34,996(17,528/17,468) 集合要素の異なり数 43,637 事例あたりの平均集合要素数 17.64 * XEON 2.4GHz, Linux, C++ による実装

素性 B A C 彼の1 友人は2 この本を3 持っている4 女性を5 探している6 静的素性 係り元/係り先 係るかどうかの判定? B A C 彼の1 友人は2  この本を3  持っている4 女性を5 探している6 係り元 係り先 静的素性 係り元/係り先 主辞/機能語: (表層、品詞、品詞再分類、活用型、活用形、括弧の有無、疑問符の有無、句読点の有無、位置) 間: 距離(離散値)、括弧の有無、句読点の有無、疑問符の有無 動的素性 [工藤, 松本 2000] A,B : 機能語の静的素性 C: 主辞の静的素性 Now we'd like to consider the features for dependency analysis. We use two kinds of features, Static features, and dynamic features. For static features, we take the gramatical features in modifer and mofier. For example, surfece POS, POS-subcategory, inflection-type inflection form of head and functional word in segment . , and whether head and functional word contains brackets, quoatations qunctionations. We also use the distance, case-particles, brackets .quoateions, and punctioations between two segments. Japanese dependency relations are heavily constrained by such static features, However, when a sentence is long and there are more than one possible dependents, static features by themselves cannot determine the correct dependency. To improve the accuracy, we proposed a new type of features, called ‘dynamic-features’ before. When we call the SVMs to check whether 2nd modiier depends on 4th modifer, the dependency of segments of A B and C are already identified because we build dependency relation with bottom-up process. The idea of dynamic features is to use these segments, which are already identified, as new features. In our experiments, we use Functional representation as dynamic features for Segments type A and B, and POS of head word for segments type C. I would like to note that the parsing cost does not change even using dynamic features, because the cascaded chunking model parses a sentence deterministically.

実験結果 σ 解析時間 (秒/文) 正解率(%) 部分集合数(k個) PSKB - 0.2848 89.29 PSKI 0.0811 TRIEのサイズ(MB) PSKB - 0.2848 89.29 PSKI 0.0811 PSKE 0.1 0.0013 82.02 7 1.8 0.05 0.0020 86.27 30 3.1 0.01 0.0050 88.91 739 37.2 0.005 0.0067 89.05 1,924 93.4 0.001 0.0092 89.26 6,686 317.5 0.0005 0.0097 8,262 391.1 0.0001 0.0101 9,846 464.9

考察 PSKI が 約3倍, PSKEが 30倍程度 高速 σ=0.0005のときの部分集合のサイズは 826万, TRIEのサイズは 391MB 頻度によるフィルタリング 部分集合のそれぞれに対し、事例集合中の出現頻度がξ(=1,2,3..)以上の部分集合を残し, 残りを削除 頻出部分集合も バスケットマイニングアルゴリズムを用い効率よく列挙する σ=0.0005に固定し, ξを変化させる

頻度によるフィルタリング結果 フィルタリングにより、サイズを約1/3に 若干ながら精度向上→頻度の小さい例外的事例の排除 ξ 解析時間 (秒/文) 正解率(%) 部分集合数(k個) TRIEのサイズ(MB) PSKB - 0.2848 89.29 PSKI 0.0810 PSKE σ=0.005 1 0.0097 82.29 8,262 391.1 2 0.0074 89.34 2,450 118.0 3 0.0069 89.31 1,360 66.4 4 0.0065 89.25 945 46.8 フィルタリングにより、サイズを約1/3に 若干ながら精度向上→頻度の小さい例外的事例の排除

PSKEにおいて実際に抽出された 3つ組み素性 ● {係り元-主辞-品詞細分類-普通名詞,   係り元-機能語-表層-と, 係り先-主辞-品詞細分類-普通名詞} 「普通名詞 と 普通名詞」      並列構造 ● {係り元-機能語-表層-を,  係り先-主辞-表層-中心,    係り先-機能語-表層-に} 「~を 中心に」     頻出言い回し, 一般 名詞が「を格」をとる特殊なパターン ● {係り元-機能語-表層-から,    係り元-機能語-品詞-助詞,   係り先-機能語-表層-まで} 「~から ~まで」     頻出言い回し

まとめ Power Set Kernel の定式化と分析 Power Set Kernel の高速化 PSKI (事例集合を転置した形で表現) PSKE (Power Set の空間で分類) PSKI が 3倍程度、PSKE が 30倍程度の高速化に成功

今後の課題 部分集合重み Cr の分析 Cr の適当な推定 → Crに即した Kernel 頻度によるフィルタリングの詳細な分析 係り受け以外のデータセットでの実験

おまけ PSK のより詳細な分析は、次回のアクティブマイニング研究会で発表いたします PSKI は拙作の 汎用 チャンカー YamCha と, 係り受け解析プログラム CaboCha に使われています PSKE に基づくチャンカー, 係り受け解析プログラムの公開 (まだモデルが大きすぎる?)