Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
自然言語処理を支える技術 〜要素技術とPerlの活用〜
Search
hide_o_55
August 31, 2014
Technology
4
3.3k
自然言語処理を支える技術 〜要素技術とPerlの活用〜
hide_o_55
August 31, 2014
Tweet
Share
Other Decks in Technology
See All in Technology
プロダクト活用度で見えた真実 ホリゾンタルSaaSでの顧客解像度の高め方
tadaken3
0
260
Platform Engineering for Software Developers and Architects
syntasso
1
530
rootlessコンテナのすゝめ - 研究室サーバーでもできる安全なコンテナ管理
kitsuya0828
3
390
データプロダクトの定義からはじめる、データコントラクト駆動なデータ基盤
chanyou0311
3
370
Introduction to Works of ML Engineer in LY Corporation
lycorp_recruit_jp
0
150
OS 標準のデザインシステムを超えて - より柔軟な Flutter テーマ管理 | FlutterKaigi 2024
ronnnnn
1
330
【Startup CTO of the Year 2024 / Audience Award】アセンド取締役CTO 丹羽健
niwatakeru
0
1.5k
強いチームと開発生産性
onk
PRO
36
12k
TypeScriptの次なる大進化なるか!? 条件型を返り値とする関数の型推論
uhyo
2
1.8k
100 名超が参加した日経グループ横断の競技型 AWS 学習イベント「Nikkei Group AWS GameDay」の紹介/mediajaws202411
nikkei_engineer_recruiting
1
180
Oracle Cloud Infrastructureデータベース・クラウド:各バージョンのサポート期間
oracle4engineer
PRO
29
13k
電話を切らさない技術 電話自動応答サービスを支える フロントエンド
barometrica
2
300
Featured
See All Featured
For a Future-Friendly Web
brad_frost
175
9.4k
The Pragmatic Product Professional
lauravandoore
31
6.3k
The Language of Interfaces
destraynor
154
24k
Site-Speed That Sticks
csswizardry
0
40
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
42
9.2k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
246
1.3M
jQuery: Nuts, Bolts and Bling
dougneiner
61
7.5k
Become a Pro
speakerdeck
PRO
25
5k
The Invisible Side of Design
smashingmag
298
50k
Gamification - CAS2011
davidbonilla
80
5k
Teambox: Starting and Learning
jrom
133
8.8k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
16
2.1k
Transcript
ࣗવݴޠॲཧΛࢧ͑Δٕज़ ʙཁૉٕज़ͱPerlͷ׆༻ʙ Hideaki Ohno
About me w)JEFBLJ0IOP w5XJUUFSIBUFOBOQNIJEF@P@ w(JU)VCIJEFP w1"64&)*%&",*0 w'BWPSJUF1SPHSBNJOH-BOHVBHF w$$ +BWB4DJSQU1FSM
None
Ͳ͏ΈͯNoderͰ͢ɻ ຊʹʢ͈́
Agenda •ࣗવݴޠॲཧͷ֓ཁ •ࣗવݴޠॲཧͷཁૉٕज़ •ΞϧΰϦζϜ •σʔλߏ •πʔϧ •ϥΠϒϥϦ
ఆରऀ • Perlʹ͍ͭͯCPANϞδϡʔϧΛ׆༻ͯ͠ɺΓ͍ͨ͜ͱΛ࣮ ݱͰ͖Δ • ࣗવݴޠॲཧʹ͍ͭͯڵຯ͋Δ͕ܦݧͳ͍
ࣗવݴޠॲཧ զʑ͕ීஈ͍ͬͯΔ ݴޠΛίϯϐϡʔλʹ ॲཧͤ͞Δٕज़
ࣗવݴޠॲཧ ͔ͳࣈม
ࣗવݴޠॲཧ ใݕࡧ
ࣗવݴޠॲཧ ػց༁
ࣗવݴޠॲཧ ใநग़
ࣗવݴޠॲཧ ࣗಈཁ
ࣗવݴޠॲཧ จষੜ
ࣗવݴޠॲཧ Իೝࣝ
ࣗવݴޠॲཧ จࣈೝࣝ
ࣗવݴޠॲཧ •ϧʔϧϕʔε •౷ܭతֶशϞσϧ
ϧʔϧϕʔε • ਓखͰϧʔϧΛఆٛͯ͠ॲཧ͢Δ • ʹΑͬͯݱࡏͰ౷ܭֶशϞσϧΑΓߴਫ਼ • ॴ • ਓखʹΑΔௐ͕Ͱ͖Δ •
ॴ • ϧʔϧͷϝϯςφϯείετ • ϧʔϧͷ࡞ʹઐ͕ࣝඞཁ • ྫ֎ͷଟ͍υϝΠϯͷద༻͕ۤख
౷ܭతֶशϞσϧ • ػցֶशʹΑΓϧʔϧΛಋ͖ग़͠ॲཧΛߦ͏ɻ • ॴ • ՃֶशʹΑΓ৽͍͠υϝΠϯͷద༻͕Մೳ • ॴ •
ύϥϝʔλͷௐ͕͍͠ • ֶशσʔλͷ࡞ίετ
ࣗવݴޠॲཧͷཁૉٕज़
ओʹςΩετղੳؔͷٕज़ Λհ
ܗଶૉղੳ
ܗଶૉղੳͱ •ࣗવݴޠจͷܗଶૉ(Morpheme)୯Ґʹׂ͠ɺࢺͳͲΛ༩͢Δ ॲཧ •ܗଶૉͱͦͷݴޠʹ͓͚Δ࠷খ୯Ґɻجຊతʹ୯ޠͩͱࢥͬͯྑ ͍ •ݱࡏɺར༻͞Ε͍ͯΔ࣮ͷଟ͘ࢺ͚ͩͰͳ͘ɺ׆༻ͷछྨɺ ݪܗɺಡΈͳͲͷ༩Λߦ͏Α͏ʹͳ͍ͬͯΔ •Ϟσϧ࣍ୈͰ୯ޠʹؔ࿈͢Δ༷ʑͳଐੑΛ༩Ͱ͖Δ •͜ͷॲཧΛߦ͏ϓϩάϥϜΛܗଶૉղੳث(Morphlogical Analyzer)ͱ͍͏
•Morphlogical Analyzer = Word Segmenter + POS Tagger + Lemmatizer + α
ܗଶૉղੳثͷΈ ܗଶૉղੳثͰར༻͞Ε͍ͯΔख๏(ίετ࠷খ๏)ͷ͓͓·͔ͳ Έ ! 1.୯ޠࣙॻΛ༻ҙ͢Δɻ୯ޠࣙॻʹ୯ޠͷੜىίετ(୯ޠͷग़ ݱ֬)ɺࢺͷใ͕֨ೲ͞Ε͍ͯΔɻ(ࣙॻʹ͍ͭͯޙड़) ! 2.୯ޠࣙॻΛར༻ͯ͠ɺೖྗจʹؚ·ΕΔ୯ޠީิΛྻڍ͢Δɻ
ܗଶૉղੳثͷΈ 3.ྻڍͨ͠୯ޠΛจ಄͔Βจ·Ͱฒͯɺ Έ߹Θͤͨߏ(Latticeߏ)Λ࡞͢Δɻ ࠷͔֬Β͍͠୯ޠ۠ΓͱࢺͷΈ߹ΘͤΛಘ͍ͨ
ܗଶૉղੳثͷΈ 4.͜͜ͰҎԼͷίετΛઃఆ͢Δɻ ୯ޠͷੜىίετ(୯ޠͷग़ݱ͕֬ߴ͍΄Ͳίετ) " Λ௨ Δίετ ࿈ίετ(ࢺͷྡ͕֬ߴ͍΄ͱίετ)ɹ" ลΛ௨Δίετ
ܗଶૉղੳثͷΈ 5.߹ܭίετ͕࠷খ͞ͳܦ࿏Λ୳ࡧ͢Δɻ ͔͠͠ ࣮ࡍͷॲཧͰΈ߹Θͤͷେ
ܗଶૉղੳثͷΈ ಈతܭը๏(DP)ͷग़൪
ܗଶૉղੳثͷΈ ViterbiΞϧΰϦζϜ •ಈతܭը๏ͷҰछ •ӅΕϚϧίϑϞσϧ(HMM)ʹجͮ͘ •؍ଌ͞ΕͨࣄܥྻΛग़ྗͨ͠Մೳੑ͕࠷ߴ ͍ঢ়ଶྻΛਪఆ͢Δ
ܗଶૉղੳثͷΈ 6.ViterbiΞϧΰϦζϜͰ୳ࡧͨ͠࠷ίετͷ͍୯ޠ ྻΛग़ྗ͢Δɻ ! ࣮ࡍ͜ΕʹՃ͑ͯɺࣙॻʹଘࡏ͠ͳ͍୯ޠ(ະޠ)Ͱ ͋ͬͯɺׂҐஔΛਪఆͰ͖ΔΑ͏ͳ͕ͳ͞Ε͍ͯ Δɻ(จࣈछʹجͮ͘ώϡʔϦεςΟοΫॲཧͳͲ)
ܗଶૉղੳث •Mecab •KyTEA •JUMAN •KAKASI ܗଶૉղੳثͷྫ
Mecab •͖݅֬(CRF)ʹجͮ͘ղੳ •ࣙॻʹμϒϧྻ(ޙड़)Λ༻ •Darts(Double-Array TRie System) •Ϣʔβࣙॻɺ෦ղੳػೳͰڥքఆΛΧελϚΠζՄೳ •PerlόΠϯσΟϯά(SWIGͰੜ)ଐ •Text::Mecab
ڥքఆͷิਖ਼͕ඞཁͳࣄྫ •ʮͳͷʯ •ॿࢺͳͲͱͯ͠ѻΘΕͯ͠·͏ •ຐ๏গঁΛݻ༗໊ࢺͱͯ͠ѻ͍͍ͨ •ʮϞʔχϯά່ɻʯɺʮ౻Ԭ߂ɺʯ •۟ಡͰׂ͞Εͯ͠·͏ ҰൠจίʔύεʹΑΔֶशͰѻ͍ͮΒ͍ͷ
JUMAN •1992ެ։ •ίετਓखͰ༩ •PerlόΠϯσΟϯά(SWIGͰੜ)ଐ
KyTea •จࣈ୯ҐͰͷׂҐஔɺλάਪఆ •SVMϩδεςΟοΫճؼʹΑΔਪఆ •෦ΞϊςʔγϣϯʹΑΔՃֶश •Text::KyTea
KAKASI •ࣈ"͔ͳ(ϩʔϚࣈ)มϓϩάϥϜ •୯ޠׂʹରԠ •Text::KAKASI
ࣙॻͰ༻͞ΕΔσʔλߏ
Trie • ॱং͖ߏͷҰछ • ߏ্ͷϊʔυͷҐஔͱΩʔ͕ରԠ͍ͯ͠Δ • ऴ·Ͱذͷͳ͍ϥϕϧΛTAILྻʹऩΊΔMinimal Prefix Trieɺ ذͷͳ͍ϊʔυͷϥϕϧΛ1ͭͷϊʔυ·ͱΊΔύτϦγΞTrieͳͲͷѥछ
͋Δ
Trieͷಛ •Ωʔͷݕࡧ͕ߴɻ͞ m ͷΩʔݕࡧ࠷ѱ Ͱ O(m) •ڞ௨͢Δ಄͕ࣙ·ͱΊΒΕΔͷѹॖޮՌ͕͋ Δ •ڞ௨͢Δ಄ࣙΛ࣋ͭΩʔͷྻڍ͕༰қ
TrieΛදݱ͢Δσʔλߏ
ιʔτࡁΈྻ •Trieͷ֤ϊʔυͷࢠϊʔυΛϥϕϧͰιʔτ •୳ࡧ࣌ࢠϊʔυΛೋ୳ࡧ •ݕࡧͷܭࢉྔO(log n)
μϒϧྻ • BaseͱCheckͷ2ͭͷྻͰTrieͷϊʔυؒͷભҠΛදݱɻ • αΠζ͕ίϯύΫτͰඇৗʹߴʹݕࡧͰ͖Δɻ • ݕࡧͷܭࢉྔO(1)ɻ࣮ࡍʹΩʔͷ͞ʹґଘɻ • Perl͔ΒText::Darts͕ར༻Ͱ͖Δ
LOUDS • TrieͷߏΛϏοτྻͰදݱ • ؆ܿϏοτϕΫτϧΛར༻͢Δ͜ͱͰαΠζΛѹॖͭͭ͠ߴͳΞΫηε͕Մೳ • ؆ܿϏοτϕΫτϧҎԼͷૢ࡞Λఏڙ͢Δ • access(i): ϏοτϕΫτϧͷi൪ͷΛฦ͢
• rank(i): ઌ಄͔Βi൪·Ͱͷ1(·ͨ0)ͷΛฦ͢ • select(i): i൪ʹग़ݱ͢Δ1(·ͨ0)ͷҐஔΛฦ͢ • ҰఆͷϒϩοΫຖʹ1ͷΛอ࣋ͨ͠rankࣙॻΛར༻͢Δ͜ͱͰrank(i) ఆ࣌ؒͰॲཧՄೳ • select(i)rankࣙॻͷೋ୳ࡧͰO(log n)ͰॲཧՄೳ • Perl͔ΒText::Tx(tx-trie), Text::Ux(ux-trie)ɺmarisa- trie(SWIG)͕ར༻Մೳ
Γड͚ղੳ
Γड͚ղੳͱ •֤୯ޠɾจઅؒͷΓड͚ߏΛൃݟ͢Δ •جຊతʹܗଶૉղੳثͷग़ྗΛೖྗͱ͢Δ •͜ͷॲཧΛߦ͏ϓϩάϥϜΛΓड͚ղੳثͱ ͍͏
Γड͚ղੳͷΈ •Shift-reduce •ࠨ͔Βӈᩦཉతʹղੳ •ߴɺগ͠ਫ਼͕͍ •શҬ •จશମͷΓड͚Λ࠷దԽ •ਫ਼͕গ͠ߴ͘ɺεϐʔυ͕গ͠མͪΔ •νϟϯΫಉఆͷஈ֊ద༻ •୯ޠΛ۟ʹνϟϯΩϯά •Λൃݟ
ɹͷ܁Γฦ͠
Shift-Reduce • ࠨ͔Βӈ୯ޠΛ̍ݸͣͭॲཧ • QueueͱStackΛར༻ͯ͠ॲཧ • Queue : ະॲཧͷ୯ޠΛ֨ೲ •
Stack : ॲཧதͷ୯ޠΛ֨ೲ • ֤࣌Ͱ 1 ͭͷಈ࡞Λબ • shift: 1 ୯ޠΛΩϡʔ͔ΒελοΫҠಈ • reduce ࠨ : ελοΫͷ̍୯ޠ̎୯ޠͷ • reduce ӈ : ελοΫͷ̍୯ޠ̎୯ޠͷ • ྨثΛͬͯͲͷಈ࡞ΛऔΔ͔Λֶश
શҬ •୯ޠΛͱͨ͠༗άϥϑΛ࡞Δ •άϥϑͷล͕Γड͚ •ػցֶशͨ͠σʔλΛݩʹ֤ลʹείΞΛ༩ •είΞ͕࠷େͱͳΔ͕Γड͚ߏΛද͢ߏ จͱͳΔ
νϟϯΫಉఆͷஈ֊ద༻ •จΛνϟϯΫʹׂɺΛӈͷ୯ޠʹ͢Δ •νϟϯΫׂ͕Ͱ͖ͳ͘ͳͬͨ࣌Ͱߏจ͕
Γड͚ղੳث •CaboCha •KNP •J.DepP
CaboCha •SVMʹجͮ͘ղੳ •ࣙॻʹμϒϧྻΛ༻ •ݻ༗දݱղੳ •ݻ༗໊ࢺ(৫ɺਓ໊ɺ໊ͳͲ)ɺදݱɺ࣌ؒදݱ ͳͲΛఆ •PerlόΠϯσΟϯάଐ(SWIG)
KNP •2003ʹެ։͞ΕͨΓड͚ղੳ/֨ղੳث •JUMANͷग़ྗΛೖྗͱ͢Δ •PerlόΠϯσΟϯάଐ(SWIG)
J.DepP •2009ʹެ։͞ΕͨຊޠΓड͚ղੳث •લड़ͷख๏ΛؚΊෳͷղੳख๏Λαϙʔτ •SVM, MaxEntͳͲෳͷֶशख๏Λαϙʔτ •OpalʹΑΔΦϯϥΠϯֶश •PerlόΠϯσΟϯάଐ(SWIG)
ҙຯղੳ-֨ղੳ • ֨ߏɿจͷҙຯߏΛ ಈࢺ-ਂ֨-໊ࢺ ͱ͍͏ؔͷू߹ͱͯ͠ั͑ͨͷ • ද֨ɿΨ֨ɼϮ֨ɼχ֨ • ਂ֨ɿಈ࡞ओ֨, ର֨,
ॴ֨, ࣌ؒ֨ͳͲ • KNP
ҙຯղੳ-ड़ޠ߲ߏղੳ •จষதͷ֤ड़ޠͷʮ߲ʯͱͳΔ໊ࢺ۟ͳͲΛ ͯΔ •ड़ޠͷಈ࡞ओମͱͳΔ໊ࢺͲΕ͔ •SynCha •Perl
ݴޠϞσϧ •ࣗવݴޠΒ͠͞Λ֬Ͱද͢Ϟσϧ •͔ͳࣈมػց༁ͳͲͰར༻͞ΕΔ •Α͘ར༻͞ΕΔͷ͕ N-gramݴޠϞσϧ
N-gramݴޠϞσϧ •Nݸͷ୯ޠྻ͕ग़ݱ͢Δ֬Λ֨ೲͨ͠Ϟσϧ •0-gram: ୯ޠͷੜى֬֬ •1-gram: ୯ޠͷग़ݱ֬ •2-gram: W_i-1ͷޙΖʹWi͕ग़ݱ͢Δ͖݅֬ •n-gram: n
୯ޠͱ n-1 ୯ޠ͔ΒͳΔจࣈྻͷ֬Λར༻ •wi−n+1…wi−1ͷޙΖʹW_i͕ग़ݱ͢Δ͖݅֬
N-gramݴޠϞσϧͷ՝ ݴޠϞσϧʹଘࡏ͠ͳ͍୯ޠ(ະޠ)͕ग़ݱ͢Δͱ֬ 0Ͱ͋ΔͨΊɺจͷείΞΛదʹࢉग़Ͱ͖ͳ͍ ! " ະޠΛؚΉN-gramʹԿΒ͔ͷ֬ΛׂΓͯΔ: εϜʔδϯά
εϜʔδϯά •ՃࢉεϜʔδϯά •શͯͷ֬ʹҰఆͷΛՃࢉͯ͠ɺ0ʹͳΒͳ ͍Α͏ʹ͢Δɻ •ਫ਼͕ѱ͍ •ઢܗิ๏ •N-1, N-2 … 1gramͱ͍ͬͨ࣍N-gramͷ
֬Λར༻ͯ͠N-gramͷ֬Λਪఆ͢Δ
εϜʔδϯά •Back-off •ֶशσʔλͰग़ݱ͢Δͱ͖άουνϡʔϦ ϯάͷਪఆΛͬͯɺग़ݱ͠ͳ͍ͱ͖ (1-શͯͷग़ݱ͢Δ߹ͷਪఆͷ)Λग़ݱ ͠ͳ͍୯ޠʹۉʹ֬Λ͢Δ
εϜʔδϯά •Kneeser-NeyεϜʔδϯά •ߴ •࣍N-gramͱલͷ୯ޠͷछྨΛ༻͍Δ •Modified Kneeser-NeyεϜʔδϯάɺ Interpolated Kneeser-NeyεϜʔδϯάͳͲੜ͋ Γ
ࣗવݴޠॲཧͰཱͭ PerlϞδϡʔϧ
Regexp::Assemble • ෳͷਖ਼نදݱʹϚον͢Δߴͳਖ਼نදݱΛੜ • ͲͷύλʔϯʹϚον͔ͨࣝ͠ผՄೳ
Parse::RecDescent •BNF-likeͳจ๏ఆ͔ٛΒ࠶ؼԼ߱ύʔαʔΛ ੜ
Data::Iterator::SlidingWindo w •࡞ •Slinding Window ΞϧΰϦζϜʹΑͬͯίϨ ΫγϣϯΛάϧʔϐϯάͯ͠ɺΠςϨʔλͰऔ Γग़͢͜ͱ͕Ͱ͖Δ •୯ޠͷN-GramੜͳͲʹར༻Ͱ͖Δ
Algorithm::NaiveBayes •Naive Bayes๏ʹΑΔྨث •গͳ͍܇࿅σʔλͰྨͷͨΊͷύϥϝʔλ ΛݟੵΔ͜ͱ͕Ͱ͖Δ
Algorithm::SVM •libsvmͷPerlόΠϯσΟϯά •libsvn • SVM(Support Vector Machine)ʹجͮ ͘ઢܗྨثͷ࣮
Algorithm::LibLinear •liblinearͷPerlόΠϯσΟϯά •liblinear •ઢܗྨث •libsvnΑΓߴ
Algorithm::AdaBoost •AdaBoost(Adaptive Boosting)ΞϧΰϦζ ϜͷPerl-XS࣮
Algorithm::AdaGrad •࡞ •ΦϯϥΠϯֶशΞϧΰϦζϜ AdaGrad(Adaptive Gradient)ͷPerl-XS ࣮
Algorithm::HyperLogLog •࡞ •ू߹ͷΧʔσΟφϦςΟΛਪఆ͢Δ HyperLogLog ΞϧΰϦζϜͷPerl-XS࣮ •ޡࠩΛؚΉ͕লϝϞϦͰू߹ͷΧʔσΟφϦςΟ ΛಘΔ͜ͱ͕Ͱ͖Δ
Algorithm::LBFGS •L-BFGS๏ͷ࣮ •লϝϞϦͰ४χϡʔτϯ๏ •ؔͷޯ͕0ʹͳΔͱ͍͏ҙຯͰͷؔͷෆ ಈΛݟ͚ͭΔ
WWW::Mechanize •ਓ͕ؒϒϥβͰߦ͏ૢ࡞ΛΤϛϡϨʔτ •Web্ͷใऩूʹศར
Web::Query •jQueryͬΆ͍ײ͡ͰεΫϨΠϐϯάͰ͖Δ
ࣗવݴޠॲཧʹ͓͚Δ Perlͷׂ •ॊೈͳςΩετॲཧೳྗΛ׆͔ͨ͠લॲཧɾޙॲཧ •֤छπʔϧͷೖྗɾग़ྗςΩετͷϑΥʔϚοτมͳͲ •εΫϨΠϐϯάʹΑΔݴޠϦιʔεͷऩू •ϓϩτλΠϐϯά •ࣗવݴޠॲཧπʔϧͷଟ͘C++ •PerlͱC++είʔϓͷѻ͍͕ࣅ͍ͯΔͷͰɺείʔϓΨʔυͳ ͲͷΠσΟΦϜ͕ͦͷ··Ҡ২Ͱ͖Δ
͝ਗ਼ௌ͋Γ͕ͱ͏͍͟͝·ͨ͠