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
分布で見る効果検証入門 / ai-distributional-effect
cyberagentdevelopers
PRO
4
700
【技術書典17】OpenFOAM(自宅で極める流体解析)2次元円柱まわりの流れ
kamakiri1225
0
220
Figma Dev Modeで進化するデザインとエンジニアリングの協働 / figma-with-engineering
cyberagentdevelopers
PRO
1
430
オーティファイ会社紹介資料 / Autify Company Deck
autifyhq
9
120k
Fargateを使った研修の話
takesection
0
120
ガバメントクラウド先行事業中間報告を読み解く
sugiim
1
1.4k
プロダクトチームへのSystem Risk Records導入・運用事例の紹介/Introduction and Case Studies on Implementing and Operating System Risk Records for Product Teams
taddy_919
1
170
独自ツール開発でスタジオ撮影をDX!「VLS(Virtual LED Studio)」 / dx-studio-vls
cyberagentdevelopers
PRO
1
180
君は隠しイベントを見つけれるか?
mujyun
0
300
Forget efficiency – Become more productive without the stress
ufried
0
150
신뢰할 수 있는 AI 검색 엔진을 만들기 위한 Liner의 여정
huffon
0
360
生成AIとAWS CDKで実現! 自社ブログレビューの効率化
ymae
2
330
Featured
See All Featured
Building Better People: How to give real-time feedback that sticks.
wjessup
363
19k
Into the Great Unknown - MozCon
thekraken
31
1.5k
Product Roadmaps are Hard
iamctodd
PRO
48
10k
Fireside Chat
paigeccino
32
3k
Fashionably flexible responsive web design (full day workshop)
malarkey
404
65k
Navigating Team Friction
lara
183
14k
Large-scale JavaScript Application Architecture
addyosmani
510
110k
Art, The Web, and Tiny UX
lynnandtonic
296
20k
The Art of Programming - Codeland 2020
erikaheidi
51
13k
Rebuilding a faster, lazier Slack
samanthasiow
79
8.6k
Faster Mobile Websites
deanohume
304
30k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
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++είʔϓͷѻ͍͕ࣅ͍ͯΔͷͰɺείʔϓΨʔυͳ ͲͷΠσΟΦϜ͕ͦͷ··Ҡ২Ͱ͖Δ
͝ਗ਼ௌ͋Γ͕ͱ͏͍͟͝·ͨ͠