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
初めてのPostgreSQLメジャーバージョンアップ
kkato1
0
440
20250328_OpenAI製DeepResearchは既に一種のAGIだと思う話
doradora09
PRO
0
150
お問い合わせ対応の改善取り組みとその進め方
masartz
1
370
3/26 クラウド食堂LT #2 GenU案件を通して学んだ教訓 登壇資料
ymae
1
210
職種に名前が付く、ということ/The fact that a job title has a name
bitkey
1
250
アプリケーション固有の「ロジックの脆弱性」を防ぐ開発者のためのセキュリティ観点
flatt_security
32
12k
チームの性質によって変わる ADR との向き合い方と、生成 AI 時代のこれから / How to deal with ADR depends on the characteristics of the team
mh4gf
4
340
Go製のマイグレーションツールの git-schemalex の紹介と運用方法
shinnosuke_kishida
1
410
コード品質向上で得られる効果と実践的取り組み
ham0215
2
200
SaaSプロダクト開発におけるバグの早期検出のためのAcceptance testの取り組み
kworkdev
PRO
0
460
Enterprise AI in 2025?
pamelafox
0
100
OPENLOGI Company Profile for engineer
hr01
1
22k
Featured
See All Featured
Designing for humans not robots
tammielis
251
25k
Code Review Best Practice
trishagee
67
18k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
Agile that works and the tools we love
rasmusluckow
328
21k
How GitHub (no longer) Works
holman
314
140k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
46
2.4k
The Invisible Side of Design
smashingmag
299
50k
Designing Experiences People Love
moore
141
23k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
102
18k
A Modern Web Designer's Workflow
chriscoyier
693
190k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
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++είʔϓͷѻ͍͕ࣅ͍ͯΔͷͰɺείʔϓΨʔυͳ ͲͷΠσΟΦϜ͕ͦͷ··Ҡ২Ͱ͖Δ
͝ਗ਼ௌ͋Γ͕ͱ͏͍͟͝·ͨ͠