Automatick´a segmentace slov s pomoc´ı n´astroje Affisix Michal Hruˇseck´y, Jaroslava Hlav´aˇcov´a
[email protected],
[email protected]
Motivace Pˇri zpracov´an´ı pˇrirozen´eho jazyka nikdy nem˚ uˇzeme m´ıt ve slovn´ıku vˇsechna slova i o slovech, kter´a nezn´ame, chceme b´yt schopni nˇeco ˇr´ıct Jak vznikaj´ı slova? pˇrid´an´ım jin´e pˇredpony pˇrid´an´ım jin´e pˇr´ıpony ... Pˇredpony ˇcasto neovlivˇ nuj´ı mluvnick´e kategorie ⇒ mohlo by se hodit zn´at dˇelen´ı slova (budeme-li to umˇet automaticky) Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
2 / 26
Algoritmy
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
3 / 26
´ Uvodn´ ı definice nepotˇrebujeme opravdov´e lingvistick´e pˇredpony a pˇr´ıpony potˇrebujeme nˇeco, co se tak jen chov´a
Pˇredpony pˇredpona je spoleˇcn´y zaˇc´atek mnoha slov pˇredponu m˚ uˇzeme pˇripojit na zaˇc´atek slova a vznikne n´am slovo nov´e
Pˇr´ıpony pˇr´ıpona je spoleˇcn´y konec mnoha slov
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
4 / 26
Algoritmy: Metoda ˇctverc˚ u
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
5 / 26
ˇ Ctverec pˇredpony m˚ uˇzeme na zaˇc´atku slova zamˇen ˇovat pˇr´ıpony m˚ uˇzeme na konci slova zamˇen ˇovat
⇒ Definujeme ˇ ctverec: Nechˇt a,b,c,d jsou ˇretˇezce, Ω mnoˇzina slov z jazyka a :: znaˇc´ı operaci spojen´ı. Potom
tvoˇr´ı ˇctverec, pr´avˇe tehdy pokud: a::c je platn´e slovo (a::c ∈ Ω) a::d je platn´e slovo (a::d ∈ Ω) b::c je platn´e slovo (b::c ∈ Ω) b::d je platn´e slovo (b::d ∈ Ω)
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
6 / 26
ˇ Ctverec - pˇr´ıklad
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
7 / 26
Segmentace Obecnˇ e zkus´ıme rozdˇelit slovo spoˇc´ıt´ame, v kolika ˇctverc´ıch se obˇe ˇc´asti vyskytuj´ı hodnˇe ˇctverc˚ u ⇒ dˇelen´ı je dobr´y kandid´at pro dˇelen´ı slova
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
8 / 26
Segmentace Obecnˇ e zkus´ıme rozdˇelit slovo spoˇc´ıt´ame, v kolika ˇctverc´ıch se obˇe ˇc´asti vyskytuj´ı hodnˇe ˇctverc˚ u ⇒ dˇelen´ı je dobr´y kandid´at pro dˇelen´ı slova
Konkr´ etnˇ e zkus´ıme rozdˇelit slovo u pˇredpon spoˇc´ıt´ame, v kolika ˇctverc´ıch se vyskytuje poˇc´ateˇcn´ı ˇc´ast u pˇr´ıpon spoˇc´ıt´ame, v kolika ˇctverc´ıch se vyskytuje koncov´a ˇc´ast hodnˇe ˇctverc˚ u ⇒ dˇelen´ı je dobr´y kandid´at na pˇredponu/pˇr´ıponu
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
8 / 26
Algoritmy: Metoda entropie
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
9 / 26
Entropie
Vyjadˇruje m´ıru nejistoty Definov´ana n´asledovnˇe: H(s) = −
X
p(si |s) log2 p(si |s)
si ∈S
kde S je mnoˇzina jev˚ u, kter´e mohou nastat po jevu s.
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
10 / 26
Dopˇredn´a entropie
Pˇredpona je spoleˇcn´y zaˇc´atek mnoha slov ⇒ je tˇeˇzk´e pˇredpovˇedˇet konec slova ⇒ budeme-li sledovat p´ısmena jdouc´ı po sobˇe, entropie bude vysok´a
Dopˇrednou entropii Hf definujeme jako: Hf (r ) = −
X
pf (si |r ) log2 pf (si |r )
si ;r ::si ∈Ω
kde pf (si |r ) oznaˇcuje pravdˇepodobnost, ˇze slovo zaˇc´ınaj´ıc´ı r bude pokraˇcovat si .
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
11 / 26
Zpˇetn´a entropie
Pˇr´ıpona je spoleˇcn´y konec mnoha slov ⇒ je tˇeˇzk´e pˇredpovˇedˇet zaˇc´atek slova ⇒ budeme-li sledovat p´ısmena jdouc´ı po sobˇe od konce, entropie bude vysok´a
Zpˇetnou entropii Hb definujeme jako: Hb (r ) = −
X
pb (si |r ) log2 pb (si |r )
si ;si ::r ∈Ω
kde pb (si |r ) oznaˇcuje pravdˇepodobnost, ˇze slovo konˇc´ıc´ı r bude zaˇc´ınat si .
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
12 / 26
Probl´emy metody entropie Dopˇredn´a entropie je vˇzdy na zaˇc´atku slova vysok´a Dopˇredn´a entropie je vˇzdy na konci slova n´ızk´a Mˇela by postupnˇe klesat ⇒ Jen hodnota na urˇcen´ı vhodnosti dˇelen´ı nestaˇc´ı
Slovo odpˇredchv´ıle o Hf
d
p
ˇr
e
d
c
h
v
...
2.55
2.92
2.16
1.43
0.00
1.55
0.00
0.00
...
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
13 / 26
Diferenˇcn´ı entropie ⇒ Potˇrebujeme promˇenlivou mez ⇒ Lze pouˇz´ıt zmˇenu entropie jako mˇeˇr´ıtko Nehled´ame m´ısta s vysokou entropi´ı, ale m´ısta, kde entropie naproti oˇcek´av´an´ı roste
Slovo odpˇredchv´ıle o Hf Hdf
d
p
ˇr
e
d
c
h
v
...
2.55 0.00
2.92 0.38
2.16 -0.76
1.43 -0.73
0.00 -1.43
1.55 1.55
0.00 -1.55
0.00 0.00
... ...
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
14 / 26
Affisix
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
15 / 26
O programu open source podporuje vyhled´av´an´ı pˇredpon, pˇr´ıpon i vnitˇrn´ıch ˇc´ast´ı slov dva m´ody collector V´ystupem je seznam segment˚ u podle zadan´ych podm´ınek
filter Oznaˇc´ı ve vstupn´ım textu segmenty podle zadan´ych podm´ınek
podporuje vyhodnocov´an´ı v´yraz˚ u lze snadno testovat r˚ uzn´e podm´ınky/kombinace metod
podporuje promˇenn´e a v´ıce pr˚ uchod˚ u lze vyj´adˇrit jeˇstˇe sloˇzitˇejˇs´ı podm´ınky
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
16 / 26
Uk´azka konfigurace - Dopˇredn´a entropie
mode: precision: cond_prefix_end: cond_prefix_comb: cond_prefix_format:
collector 8 10 ">(@(res;fentr;avg;fentr(j));1)" "%n: %w - %{fentr}\n"
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
17 / 26
Uk´azka konfigurace - Kombinace entropi´ı a XML v´ystup
mode: precision: cond_prefix_end: cond_prefix_comb: cond_prefix_format:
collector 8 10 ">(@(res;comb;avg; +(fentr(j);dfentr(j)));1)" "<%n value=\"%{comb}\">%w\n"
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
18 / 26
V´ysledky
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
19 / 26
Data a znaˇcen´ı Data data ze SYN2000 (lehce proˇciˇstˇen´e) testov´ano na pˇredpony v´ysledky hodnoceny ˇclovˇekem
Znaˇ cen´ı ||Hf || - normalizovan´a dopˇredn´a entropie ||Hdf || - normalizovan´a dopˇredn´a diferenˇcn´ı entropie ||Sf || - normalizovan´y poˇcet dopˇredn´ych ˇctverc˚ u C = ||Hf || + ||Hdf || + ||Sf ||
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
20 / 26
V´ysledky vyhled´av´an´ı pˇredpon
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
prefix
Cf
||Hf ||
||Hdf ||
||Sf ||
super pseudo mikro sebe r´adoby deseti mimo hyper anti roz
2.682 2.602 2.532 2.505 2.480 2.437 2.423 2.420 2.393 2.390
0.967 0.963 0.921 0.898 0.983 0.917 0.968 0.906 0.942 0.922
0.978 0.961 0.917 0.849 1.000 0.865 0.801 0.894 0.706 0.530
0.737 0.677 0.693 0.757 0.496 0.653 0.653 0.619 0.744 0.937
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
21 / 26
Srovn´an´ı precission jednotliv´ych metod (pˇredpony)
metoda Cf Hdf Hf Sf
10
50
100
150
200
100% 100% 94% 84% 73% 100% 100% 92% 81% 77% 100% 82% 79% 70% 70% 100% 60% 48% 36% 31%
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
22 / 26
Srovn´an´ı precission jednotliv´ych metod (pˇredpony)
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
23 / 26
Pl´any do budoucna
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
24 / 26
Pl´any do budoucna dalˇs´ı metody dalˇs´ı zdokonalov´an´ı n´astroje Affisix pokusy s tˇemito nov´ymi vlastnostmi pokusy s jin´ymi jazyky pokusy s re´aln´ymi aplikacemi dalˇs´ı pokusy se strojov´ym pˇrekladem
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
25 / 26
Dˇekuji za pozornost
Michal Hruˇseck´ y, Jaroslava Hlav´ aˇ cov´ a () Automatick´ a segmentace slov s pomoc´ı n´ astroje Affisix
26 / 26
