DMVCCM.org.~1~

   1 # -*- coding: mule-utf-8-unix -*-
   2 #+STARTUP: overview
   3 #+TAGS: PUGGE(p) SPML(s) NORGLISH(n) DEFINISJON(d) INNLEVERING(i)
   4 #+STARTUP: hidestars
   5 #+TITLE: PG-DOP (and Beyond!)
   6 #+AUTHOR: Kevin Brubeck Unhammer
   7 #+EMAIL: K.BrubeckUnhammer at student uva nl
   8 #+LANGUAGE: nn
   9 #+SEQ_TODO: TOGROK TODO DONE
  10 #+OPTIONS: H:4 toc:3
  11
  12 * dmvccm
  13   DEADLINE: <2008-06-30 Mon>
  14
  15 (But absolute, extended, really-quite-dead-now deadline: August 31...)
  16 [[file:dmvccm/src/dmv.py][dmv.py]]
  17 [[file:dmvccm/src/io.py][io.py]]
  18 ** TODO [#A] DMV-probabilities
  19 [[file:~/Documents/Skole/V08/Probability/dmvccm/src/dmv.py::DMV%20probabilities][dmv.py]]
  20 ** TOGROK Initialization
  21 *** COMMENT
  22 E: «For the initial symbols, I think we're supposed to
  23 implement someone-or-other's POS tagger and use the parts of speech as
  24 our tags. (K&M say they used parts of speech, anyway, and we can't use
  25 the ones from the annotated corpus or else we won't be unsupervised
  26 anymore.) I think you're right about how the tree is formed. The only
  27 thing I'm not sure about is whether those left and right marks are
  28 supposed to be part of the tree. I guess not because in a well-formed
  29 tree, every word needs a stop on both sides, so actually all nodes
  30 would be left and right marked in the end, which is the same as not
  31 using them at all. So I guess they're relevant in the E step of EM,
  32 but not the M step.» [[https://mail.google.com/mail/%3Ffs%3D1&tf%3D1&source%3Datom&view%3Dcv&search%3Dall&th%3D119b3e3d7d8f1d1f&shva%3D1&ui%3D1&disablechatbrowsercheck%3D1][gmail]]
  33
  34 K: About initialization, when they say they start with an M-step and get
  35 a harmonic distribution (where close dependencies have higher
  36 probabilities than far-away ones), I guess we could do this either in
  37 a function of its own, or as a special case of the IO-algorithm -- I'm
  38 not sure how different the harmonizing step will be from the regular
  39 M-step. But I'm pretty sure harmonizing means having to go through the
  40 whole corpus, since that's the only way we can find out distances for
  41 each dependency (without having actual distance-numbers in the rules
  42 in the first place). If sentence s is ABCD, rules from A to B should
  43 have higher probability than rules from A to D. Assuming we find some
  44 average distance between A and B, and A and D, etc. throughout the
  45 corpus, we then have to turn those numbers into probabilities that sum
  46 to 1; do you have any idea how to do that?
  47
  48 E: I think what it means to start with an M step is that we set the
  49 probabilities without regard for the initial corpus. They say that
  50 they start with an initial guess at "posterior distributions". I bet
  51 the word "posterior" is important, but I don't know what it means
  52 here. Do you?
  53
  54 ** Meet Yoav again about dmvccm
  55    SCHEDULED: <2008-05-26 Mon>
  56 13:30, P3.21.
  57
  58 Questions:
  59 *** Initialization
  60 *** Corpus access?
  61 *** How do we interpret DMV as an inside/outside process?
  62 The upside-down P_STOP formula (left-to-right also)
  63 c_s(x : i, j) is "the expected fraction of parses of s" with x from
  64 i to j; expectation then uses the probabilities gotten from
  65 initialization and previously gained probabilities, but these are of
  66 the form P_STOP and P_CHOOSE, how do we translate this to inside
  67 outside, which just uses the probabilities of CFG-rules?
  68
  69
  70
  71
  72
  73 * Python-stuff
  74 [[file:dmvccm/src/pseudo.py][pseudo.py]]
  75
  76 [[file:~/org/gtd.org::*Python][Python-notat]] i gtd.org
  77 ~/downloads/undecided/diveintopython-5.4/py/[[file:~/downloads/undecided/diveintopython-5.4/py/odbchelper.py][odbchelper.py]]
  78 [[file:/Library/Frameworks/Python.framework/Versions/2.5/lib/python2.5/site-packages/nltk]]
  79
  80 http://nltk.org/doc/en/structured-programming.html recursive dynamic
  81 http://nltk.org/doc/en/advanced-parsing.html
  82
  83
  84 * DONE [#A] Presentasjon av Klein & Manning-artiklar
  85   DEADLINE: <2008-03-10 Mon> CLOSED: [2008-03-12 Wed 17:36]
  86 [[file:DMV/k_m_presentation/dependency_induction_notes.org::Weak%20vs%20strong%20generative%20capacity%20of%20models%20improving%20models%20over][notes]]
  87 [[file:DMV/k_m_presentation/dependency_induction.pdf][presentasjon]]
  88
  89
  90
  91 * F1, P, R
  92 P = korrekte resultat fått / alle resultat fått,
  93 dvs. P = (relevante snitt gjenhenta) / gjenhenta,
  94 positiv prediktiv verdi.
  95
  96 R = korrekte resultat fått / resultat ein skulle fått,
  97 dvs. R = (relevante snitt gjenhenta) / relevante,
  98 sensitivitet.
  99
 100 F1 = (2 * P * R)/(P + R), harmonisk snitt av P og R
 101
 102
 103
 104 * EM-tutorial
 105 EM = Expectation Maximation
 106 ** Relativ frekvensestimat
 107 _Relativ Frekvensestimat_ (RFE) er berre basert på faktisk observerte
 108 utfall, uobserverte har P=0 (utvalet er ukomplett). Me kan nytte
 109 _dekomposisjon_ for å tilnærme oss den faktiske distribusjonen, t.d. REF
 110 for kvar terning i staden for alle 20 som blir kasta sameleis (her
 111 føreset me at terningane er _uavhengige_), eller t.d. ved å definere ein
 112 språkmodell (n-gram, PCFG) som gir positivt sannsyn til uobserverte
 113 utfall.
 114
 115 RFE på korpuset f: X → R er: \\
 116 ~p: X → [0, 1] kor ~p = f(x) / |f|
 117
 118 ** Modellar og MLE
 119 Den _uavgrensa modellen_ /M(X)/ på /X/ er mengda av alla
 120 sannsynsdistribusjonar på /X/. Ei ikkje-tom mengd /M/ av
 121 sannsynsdistribusjonar på ei typemengd /X/ er ein _sannsynsmodell_ på /X/.
 122
 123 Gitt f og /M/ vil me finne den «beste» instansen av /M/ som skildrar
 124 f. _Korpussannsynet_ L(f; p) kor p er ein sannsynsdistribusjon (strengt
 125 teke ein pmf?) er: \\
 126 L(f; p) = ∏_{x∈X} p(x)^{f(x)}
 127
 128 ^p ∈ /M/ er ein _sannsynsmaksimeringsestimator_ («Maximum Likelihood
 129 Estimate», MLE) for /M/ på /f/ viss han maksimerer korpussannsynet:\\
 130 L(f; ^p) = max_{p∈M} L(f; p)
 131
 132 ** MLE for PCFG-ar
 133 i M-steget av EM finn me
 134
 135 ^p_A(r) = f_A(r) / |f_A| = f(r) / ∑_{r∈G_A} f(r),
 136
 137 dvs., det oppdaterte sannsynet til kvar regel er regelfrekvens delt på
 138 tal på reglar med same lhs.
 139 ** Entropi
 140 D(p||q), _Kullback-Leibler-divergens_, aka _relativ entropi_, er definert
 141 slik:\\
 142 for p, q ∈ /M(X)/: D(p||q) = ∑_{x∈X} p(x) log(p(x)/q(x)) \\
 143 eller D(p||q) = ∑_{x∈X} p(x) (log p(x) - log q(x)) \\
 144 eller D(p||q) = E_p (log p(x) - log q(x))
 145
 146 (kor E_p er forventinga om p(x) og x∈X)
 147
 148 Teorem (=Gibb='s Ulikskap, informasjonsulikskap): \\
 149 D(p||q) >= 0 ⋀ ( D(p||q) = 0 ↔ p=q )
 150
 151 Teorem: ~p er RFE på /f/. ^p € /M/ er MLE til /M/ på /f/ viss og berre viss:
 152 \\
 153 D(~p||^p) = min_{p€M} D(~p||p)
 154
 155 MLE treng ikkje vere unik eller ei gong finnast, men viss ~p € /M/ så er
 156 ~p den unike MLE (men oftast vil modellane våre utelukke RFE sidan RFE
 157 gir ~p=0 til uobserverte utfall, og treningskorpuset har aldri alle
 158 moglege utfall).
 159
 160 ** PCFG-døme
 161 G er ein CFG og G_A = {r ∈ G : lhs(r) = A}; X er trea generert av G.\\
 162 f_r(x) er kor mange gonger regel r førekjem i tre x.
 163
 164 M_G = { p ∈ M(X) : p(x) = p(x) ∏_{r∈G} p(r)^{f_r(x)} slik at ∑_{r∈G_A} p(r)=1 }
 165
 166 f_T er eit korpus over X, og f er det induserte korpuset over reglar i
 167 G:\\
 168 f(r) = ∑_{x∈X} f_T(x) f_r(x)
 169
 170 Så regelfrekvens = trefrekvens(x) * regelfrekvens_per_tre(x); f(r) er
 171 regelfrekvensen i det induserte korpuset.
 172
 173 f_A(r) = { f(r) viss r ∈ G_A, elles 0 }
 174
 175 Så ∑_{r∈G_NP} f_NP(r) gir tal på reglar frå NP til foo.
 176
 177 Korpussannsyn:\\
 178 L(f_T; p) = ∏_{r∈G} p(r)^f(r) \\
 179 L(f_T; p) = ∏_A ∏_{r∈G_A} p(r)^f(r) \\
 180 L(f_T; p) = ∏_A L(f_A; p)
 181
 182 Kvar L(f_A; p) kan maksimerast vha. RFE, som vanlegvis gir positivt
 183 sannsyn for tre som ikkje er i f_T, så dette er /ikkje/ det relative
 184 frekvensestimatet på f_T.
 185
 186