Un entorn d'aprenentatge d'autòmates basat en mètodes algebraics

Un entorn d’aprenentatge d’aut`omats basat en m`etodes algebraics Andreu Mayo Casademont 19 de maig de 2014 Director: Xavier Carreras P´erez Departament: Llenguatges i Sistemes Inform`atics (LSI) Titulaci´o: Enginyeria en Inform`atica Centre: Facultat d’Inform`atica de Barcelona (FIB) Universitat: Universitat Polit`ecnica de Catalunya (UPC) BarcelonaTech 2 ´ Index 1 Introducci´o 5 1.1 Context del PFC . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Objectius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Planificaci´o i estimaci´o del cost . . . . . . . . . . . . . . . . . . 7 1.4 Organitzaci´o de la mem`oria . . . . . . . . . . . . . . . . . . . . 10 2 Aprenentatge 11 2.1 Conceptes b`asics i notaci´o . . . . . . . . . . . . . . . . . . . . 11 2.1.1 Aut`omats d’estats finits amb pesos . . . . . . . . . . . . 11 2.1.2 Matriu de Hankel . . . . . . . . . . . . . . . . . . . . . . 12 2.1.3 Relaci´o entre WFA i Hankel . . . . . . . . . . . . . . . . 12 2.1.4 Transductors d’estats finits . . . . . . . . . . . . . . . . 13 2.2 Visi´o general del m`etode . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Construcci´o de les matrius de Hankel . . . . . . . . . . . . . . 14 2.3.1 Definici´o de la base . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Aproximaci´o de la matriu . . . . . . . . . . . . . . . . . . 15 2.3.3 Projeccions aleat`ories . . . . . . . . . . . . . . . . . . . . 16 2.4 M`etode basat en SVD . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1 An`alisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.2 Descripci´o del m`etode . . . . . . . . . . . . . . . . . . 17 2.5 M`etode basat en optimitzaci´o convexa . . . . . . . . . . . . . . 19 2.5.1 An`alisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5.2 Optimitzaci´o convexa. Operadors proximals . . . . . . 20 3 Predicci´o 25 3.1 Predicci´o amb aut`omats . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Predicci´o amb transductors alineats . . . . . . . . . . . . . . . . 27 3.3 Testeig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3.1 Word Error Rate (WER) . . . . . . . . . . . . . . . . . . 29 3.3.2 Perplexitat . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 4 Llibreria 31 4.1 An`alisi de les caracter´ıstiques . . . . . . . . . . . . . . . . . . 31 4.2 An`alisi de les funcionalitats . . . . . . . . . . . . . . . . . . . . 31 4.3 Casos d’´us . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.1 Construcci´o de les matrius de Hankel . . . . . . . . . . 32 4.3.2 Aprenentatge del model . . . . . . . . . . . . . . . . . . 33 4.3.3 Aplicaci´o del model d’un aut`omat . . . . . . . . . . . . 33 4.3.4 Aplicaci´o del model d’un transductor alineat . . . . . . 33 4.3.5 Testeig del model . . . . . . . . . . . . . . . . . . . . . . 34 4.4 Diagrama de classes . . . . . . . . . . . . . . . . . . . . . . . . 34 4.5 Detalls de la implementaci´o . . . . . . . . . . . . . . . . . . . . 36 4.6 Exemple d’´us de la llibreria . . . . . . . . . . . . . . . . . . . . 38 5 Experiments 41 5.1 Aut`omats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.1.1 Descripci´o de les dades i matrius de Hankel . . . . . . 41 5.1.2 M`etode basat en SVD . . . . . . . . . . . . . . . . . . 42 5.1.3 M`etodes basats en optimitzaci´o convexa . . . . . . . . 44 5.1.4 Comparativa . . . . . . . . . . . . . . . . . . . . . . . . 47 5.2 Transductors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5.2.1 Descripci´o de les dades i matrius de Hankel . . . . . . 52 5.2.2 M`etode basat en SVD . . . . . . . . . . . . . . . . . . 53 5.2.3 M`etodes basats en optimitzaci´o convexa . . . . . . . . 53 5.2.4 Comparativa . . . . . . . . . . . . . . . . . . . . . . . . 56 5.3 Matrius de Hankel alternatives . . . . . . . . . . . . . . . . . . 58 5.3.1 Projeccions aleat`ories . . . . . . . . . . . . . . . . . . . . 58 5.3.2 Bases alternatives . . . . . . . . . . . . . . . . . . . . . . 61 6 Conclusi´o 65 1 Introducci´o L’aprenentatge autom`atic d’aut`omats a partir de dades ´es un problema cl`assic en computaci´o, amb aplicacions a processament del llenguatge natural, veu i imatge, processament de seq¨u`encies biol`ogiques, motors de cerca, entre d’altres. Un aut`omat ´es un conjunt d’estats amb transicions. Segons el tipus d’aut`omat pot tenir un o diversos estats inicials, i a mesura que llegeix s´ımbols de l’entrada va transitant d’un estat a altre. Els aut`omats tamb´e tenen estats finals, de manera que una paraula de l’entrada ´es acceptada per l’aut`omat si, i nom´es si, l’estat on es troba l’aut`omat despr´es de llegir la paraula ´es un estat final. Segons les seves caracter´ıstiques els aut`omats es poden classificar en diferents fam´ılies. La m´es senzilla seria el cas d’aut`omats finits deterministes (Deterministic Finite Automata, DFA) que tenen un nombre finit d’estats, un ´unic estat inicial, i cada s´ımbol de l’entrada defineix una ´unica transici´o desde cada estat. El nom determinista prov´e del fet que l’estat on es troba l’aut`omat despr´es d’haver llegit una seq¨u`encia d’entrada est`a un´ıvocament determinat. Aix`o no passa amb els aut`omats indeterministes (Non-deterministic Finite Automata, NFA), on poden haver-hi diversos estats inicials i diverses transicions d’un estat al llegir un s´ımbol. Una generalitzaci´o del NFA s´on els aut`omats finits amb pesos (Weighted Finite Automata, WFA), on les transicions tenen pesos, i cada estat t´e assignat un cert pes de ser estat inicial i final. Una variaci´o dels aut`omats s´on els transductors. Aquestes m`aquines es comporten igual que els aut`omats per`o, a m´es a m´es, a cada transici´o d’un estat a un altre es pot generar un o m´es s´ımbols. Un cas particular de transductor anomenat transductor alineat esdev´e quan imposem que cada transici´o generi exactament un s´ımbol. Com en el cas d’aut`omats podem parlar de transductors finits deterministes (Deterministic Finite Transducer, DFT), transductors finits indeterministes (Non-deterministic Finite Transducer, NFT) i transductors finits amb pesos (Weighted Finite Transducers, WFT). En aquest ´ultim cas cada transici´o t´e assignat un per a cada s´ımbol de sortida. 6 Cap´ıtol 1. Introducci´o Entrada g u e s s a p p l e e n a b l e Sortida g - E s - @ p - L - I n e b L - Figura 1.1: Exemple de seq¨u`encies d’entrada i de sortida d’un transductor que obt´e la transcripci´o fon`etica de paraules angleses. Aix´ı doncs, usarem t`ecniques d’aprenentatge autom`atic per aprendre aut`omats i transductors que posteriorment farem servir per tasques de predicci´o. L’aprenentatge autom`atic ´es una branca de la intel·lig`encia artificial on s’estudien t`ecniques que permeten generalitzar comportament a partir d’exemples. Un exemple d’aplicaci´o que fa servir l’aprenentatge autom`atic ´es el detector de correu spam en el nostre correu electr`onic, usant diferents t`ecniques l’aplicaci´o acaba aprenent a distingir un correu spam d’un que no ho ´es. Segons l’objectiu dels algorismes d’aprenentatge aquests es poden classificar en aprenentatge supervisat oaprenentatge no supervisat. En el cas d’aprenentatge supervisat les dades d’aprenentatge s´on exemples d’entrades i les seves respectives sortides de manera que l’objectiu ´es produir una funci´o capa¸c de fer correspondre a una entrada la seva sortida. En el cas de no supervisat les dades d’aprenentatge s´on nom´es dades d’entrada de manera que l’objectiu ´es descobrir l’estructura d’aquestes dades. En aquest projecte farem servir algorismes que entren dins el camp d’aprenentatge supervisat. En concret, ens centrarem en l’aprenentatge d’aut`omats amb pesos (WFA) i transductors amb pesos (WFT). Un exemple d’aplicaci´o de transductors el podem trobar a la figura 1.1, on donada una paraula de l’angl`es com entrada generem la seva transcripci´o fon`etica. Per l’aprenentatge ens centrarem en m`etodes espectrals, que es basen en propietats algebraiques de certes matrius que obtenim de les dades. Aquests m`etodes s´on escalables a grans quantitats de dades i permeten fer an`alisi te`orica. 1.1 Context del PFC Abans de l’inici d’aquest projecte l’autor va estar treballant com a becari de col·laboraci´o a la recerca amb en Xavier Carreras, Borja Balle i Ariadna Quattoni. Aquest equip de recerca ha estat treballant en m`etodes espectrals amb importants publicacions com [BQC11], [BQC12] i [BCLQ13]. Aix´ı doncs, aquest projecte neix de la necessitat de tenir bones implementacions dels m`etodes amb els quals s’estava treballant. Fins al moment no hi ha llibreries estables d’acc´es lliure que permetin experimentar amb aquests m`etodes, i per tant la llibreria implementada en aquest projecte podria ser la primera. 1.2. Objectius 7 Per l’elaboraci´o del projecte el Ministerio de Educaci´on, Cultura y Deporte (MEC) ha concedit una beca de col·laboraci´o en departaments universitaris al seu autor. 1.2 Objectius L’objectiu d’aquest projecte ´es l’elaboraci´o d’un entorn d’aprenentatge d’aut`omats basats en m`etodes algebraics que permeti i faciliti l’estudi dels models i m`etodes ja existents i la recerca de nous. Com a tasca principal es dissenyar`a i s’implementar`a una llibreria de software en C++ que permetr`a experimentar amb aquests algorismes. Pr`eviament a la construcci´o de la llibreria ser`a necessari estudiar i entendre els m`etodes i algorismes que es faran servir. Un cop implementada la llibreria realitzarem experiments per avaluar i comparar els m`etodes implementats. El treball contempla dos problemes que ens permetran realitzar diferents tasques. El primer, l’aprenentatge d’aut`omats finits amb pesos que farem servir per realitzar prediccions del seg¨uent s´ımbol de les seq¨u`encies d’entrada. Aquests models tamb´e s´on ´utils per recon`eixer seq¨u`encies d’un llenguatge. El segon, l’aprenentatge de transductors alineats que s´on ´utils per transformar seq¨u`encies d’entrada de cert llenguatge a seq¨u`encies d’un altre llenguatge. Aquests models es fan servir molt en processament del llenguatge natural, un exemple ´es predir la funcionalitat sint`actica de cada paraula d’una oraci´o. Veurem que els dos m`etodes que farem servir per solucionar el primer problema tamb´e ens serviran pel segon. El primer dels dos m`etodes planteja l’aprenentatge com una descomposici´o en valors singulars (Singular Value Descomposition, SVD) de certa matriu que anomenarem matriu de Hankel. El segon m`etode planteja l’aprenentatge com un problema d’optimitzaci´o convexa on la funci´o objectiu t´e dos termes, el primer valora l’aproximaci´o del model a les dades mentre que el segon mesura la complexitat del model en termes de norma nuclear. Per realitzar l’optimitzaci´o farem servir diferents m`etodes iteratius basats en subgradients i operadors proximals. 1.3 Planificaci´o i estimaci´o del cost En aquesta secci´o presentem la planificaci´o de les tasques a realitzar per completar el projecte. Tamb´e farem una estimaci´o econ`omica del cost que tindria el projecte. Com es pot veure en el diagrama de Gantt al final de la secci´o la durada del projecte ´es de 14 setmanes. Es preveu una setmana i mitja per la correcta de- 8 Cap´ıtol 1. Introducci´o C`arrec Hores dedicades Preu per hora Cost total Expert 30 60 1800 Analista 200 30 6000 Programador 288 20 5760 Becari 96 12 1152 Total 14712 Figura 1.2: Taula de costos del projecte. finici´o del projecte. Durant les seg¨uents cinc setmanes es realitzar`a un estudi dels coneixements te`orics necessaris. Un cop es tingui prou coneixement en el tema, s’iniciar`a el disseny i implementaci´o de la llibreria. En acabar es realitzaran experiments amb els m`etodes implementats. Finalment es realitzar`a la documentaci´o de la feina feta. Per l’an`alisi econ`omica suposarem que el projecte ´es realitzat per un equip de persones amb diferents perfils. El personal d’aquest equip ´es el seg¨uent: Expert: T´e un ampli coneixement del tema. S’encarrega de facilitar a l’analista l’aprenentatge dels coneixements necessaris. Tamb´e organitza i supervisa el treball de l’equip. Analista: S’encarrega del disseny de la llibreria. Per fer aix`o necessita haver estudiat i ent`es els coneixements te`orics que intervenen. Tamb´e interpreta els experiments realitzats amb la llibreria. Programador: La seva tasca ´es implementar i testejar la llibreria. Becari: S’ecarrega de la realitzaci´o dels experiments. A la taula de la figura 1.2 mostrem els costos associats a cada c`arrec. El cost total del projecte ´es de 14712 e. . . 16 Cap´ıtol 2. Aprenentatge (P,S)←Base H←Matriu nul·la de #Pfiles i #Scolumnes Ha←Matriu nul·la de #Pfiles i #Scolumnes ∀σ D←Corpus for all w∈Ddo for all (p, s)∈(P,S) tal que ps ´es substring de wdo H(p, s) = H(p, s)+1/(n−(|p|+|s|−1) ·m) end for for all (p, s)∈(P,S) i σ∈Σ tal que pσs ´es substring de wdo Hσ(p, s) = Hσ(p, s)+1/(n−(|p|+|s|)·m) end for end for Figura 2.2: Algorisme per generar les matrius de Hankel donada una base i un corpus de seq¨u`encies. 2.3.3 Projeccions aleat`ories Com ja hem dit anteriorment, la dimensi´o de la matriu de Hankel dep`en de la mida de la base escollida. Com ´es natural ens interessar`a treballar amb bases grans per perdre el m´ınim d’informaci´o de la matriu de Hankel original, per`o un augment en la mida de la matriu provoca un augment en el cost temporal i espai al dels m`etodes d’aprenentatge. Per tant, en certs casos ser`a necessari aplicar t`ecniques per reduir les dimensions de la matriu sense perdre informaci´o. En el nostre cas hem experimentat amb projeccions aleat`ories. Suposem que tenim la matriu de Hankel Hde pfiles i scolumnes. Suposem tamb´e que tenim Φpi Φsmatrius de dp×pis×ds respectivament tal que ˜ H= ΦpHΦscompleix rang( ˜ H) = rang(H) = n. Llavors, la teoria de projeccions aleat`ories ens diu que si dpidss´on suficientment grans (en funci´o de p,sin) llavors, amb alta probabilitat, es conservaran les propietats que necessitem. Fent ´us d’aquesta teoria podem usar la matriu ˜ Hen comptes de la Hper l’aprenentatge conservant els bons resultats obtinguts. Aix`o ´es molt ´util, ja que podem triar dp ids prou petits per tal d’accelerar els m`etodes i disminuir la mem`oria necess`aria. Existeixen diferents t`ecniques per escollir les matrius Φpi Φs. Les m´es senzilles es basen en escollir cada element de la matriu usant una distribuci´o fixada. En aquest projecte hem usat la distribuci´o de Rademacher, ´es a dir, a cada element de la matriu se li assigna +1 amb probabilitat 1 2i -1 amb probabilitat 1 2. Una altra opci´o seria usar una distribuci´o gaussiana amb mitjana 0 i vari`ancia 1 dp per Φpi1 dsper Φs. 2.4. M`etode basat en SVD 17 2.4 M`etode basat en SVD En aquesta secci´o presentem un m`etode d’aprenentatge d’aut`omats que formula l’aprenentatge com una descomposici´o de matrius. El m`etode fou presentat per [HKZ09]. 2.4.1 An`alisi Aquest m`etode es basa en una dualitat entre WFA m´ınims i factoritzacions de rang de la matriu de Hankel que descrivim a continuaci´o. Sigui A=hα1, α∞,{Aσ}iun WFA amb nestats que defineix la funci´o f: Σ?→ R, i Hfla Matriu de Hankel associada. Observem que Aindueix una factoritzaci´o de Hf: si prenem P∈R|Σ?|×ntal que la fila corresponent a u∈Σ?´es el vector fila α> 1Au, i S∈Rn×|Σ?|tal que la columna corresponent a v∈Σ? ´es el vector columna Avα∞, llavors ´es trivial demostrar que H=PS. Aix`o tamb´e ´es cert si tenim una submatriu HBde Hfdefinida per un base qualsevol B= (P,S), prenent les submatrius de PiS,PBiSB, amb files i columnes corresponents a elements de PiSrespectivament. A m´es a m´es, podem factoritzar Hσ, submatriu de HB, com Hσ=PBAσSB. Un resultat immediat ´es que si A´es un WFA m´ınim per ftenim que rang(f) = ni per tant Hf=PS ´es una factoritzaci´o de rang. En el cas d’agafar HB, nom´es ´es cert que tenim una factoritzaci´o de rang si HB´es una submatriu completa de Hf. Al seg¨uent lema, demostrat a [BCLQ13], veiem que l’invers tamb´e ´es cert. ´ Es a dir, donada una factoritzaci´o de rang d’una submatriu completa de Hfes pot computar un WFA m´ınim per f. 1 Lema Sigui HBuna submatriu completa de Hfdefinida per la base B= (P,S) i Hσla submatriu corresponent a la base (Pσ, S). Sigui hP,λ ∈R|P| el vector amb coordenades hP,λ(u) = f(u), i hλ,S∈R|S| el vector amb coordenades hλ,S(v) = f(v). Si HB=PS ´es una factoritzaci´o de rang i denotem per P+ iS+les matrius pseudo-inverses de PiS, llavors el WFA A=hα1, α∞,{Aσ}i amb α> 1=h> λ,SS+,α∞=P+hP,λ, i Aσ=P+HσS+, ´es m´ınim per f. 2.4.2 Descripci´o del m`etode Implementant de forma eficient aquest lema obtenim el m`etode espectral que detallem a continuaci´o. El m`etode fa ´us d’un tipus de descomposici´o espectral anomenat Singular Value Descomposition (SVD), d’aqu´ı ve el seu nom. Una propietat interessant d’aquest m`etode ´es la robustesa a petites variacions de les 18 Cap´ıtol 2. Aprenentatge Entrada: H,{Hσ},hP,λ,hλ,S Entrada: n←Nombre d’estats de l’aut`omat a aprendre U, Λ, V >←SVD(H) V←Primeres ncolumnes de V α> 1←h> λ,SV α∞←(HV )+hP,λ for all σ∈Σdo Aσ←(HV )+HσV end for Figura 2.3: Pseudocodi del m`etode basat en SVD. dades d’entrada, que s’aconsegueix en aplicar l’SVD sobre la matriu de Hankel H. D’aquesta manera, el WFA que obtenim amb unes dades aproximades ´es molt similar al que obtindriem amb les dades exactes. Aquesta ´es una propietat important, ja que la matriu Hs’obtindr`a de forma aproximada. Suposem que existeix una funci´o f: Σ?→Rde rang ni volem computar un WFA m´ınim per ella. Suposem que coneixem una base completa B= (P,S) per fi que coneixem el valor de fsobre, almenys, les paraules del conjunt PΣS ∪ P ∪ S, de manera que podem calcular les submatrius HiHσ corresponents a la base Bi tamb´e els vectors hλ,SihP,λ. Donada aquesta informaci´o d’entrada l’algorisme aplica l’SVD sobre Hque recordem que ´es una matriu de tamany p×s, on p=|P| is=|S|, i ´es de rang n. Per tant, obtenim la descomposici´o H=UΛV>, on U∈Rp×niV∈Rs×ns´on matrius ortogonals, i Λ ∈Rn×n´es una matriu diagonal amb els valors singulars de H. De cara a l’algorisme fem servir l’ortogonalitat de V,V>V=I, per reescriure la descomposici´o de la manera H= (HV )V>. Aix´ı doncs el WFA que busquem s’aconsegueix amb les seg¨uents equacions: α> 1=h> λ,SV α∞= (HV )+hP,λ Aσ= (HV )+HσV A nivell pr`actic executarem el m`etode amb les matrius HiHσ, i els vectors hP,λ ihλ,Scalculats de forma aproximada, de manera que no coneixerem el rang de f, ja que podria no ser el mateix que el de Ha causa del soroll. En aquest cas caldr`a donar un nd’entrada a l’algorisme de manera que es computar`a l’SVD de Htruncat a dimensi´o n. Aquest par`ametre que pren valors naturals ens permet regular el nombre d’estats del WFA. A la figura 2.3 podem veure el pseudocodi del m`etode que es dedueix directament de les equacions. 2.5. M`etode basat en optimitzaci´o convexa 19 2.5 M`etode basat en optimitzaci´o convexa En aquesta secci´o veurem una alternativa al m`etode basat en SVD vist pr`eviament proposada a [BQC12]. Aquest m`etode es basa en reduir el problema d’aprenentatge a un problema d’optimitzaci´o d’una funci´o convexa en un domini convex. ´ Es important remarcar que volem propietats de convexitat, ja que aquestes asseguren que els algorismes que es fan servir per l’optimitzaci´o troben l’`optim global. 2.5.1 An`alisi Siguin Hi{Hσ}el conjunt de matrius de Hankel definides anteriorment, sigui H=PS iHσ=PAσSles factoritzacions de rang indu¨ıdes per un cert WFA A amb nestats. ´ Es f`acil veure que Bσ=PAσP+∈Rp×p´es una matriu de rang menor o igual a ni que satisf`a que BσH=Hσ. A m´es a m´es, usant la propietat que els WFA s´on invariants per canvi de base tenim que el WFA hβ1, β∞,{Bσ}i amb β> 1=α> 1P+,β∞=Pα∞iBσ=PAσP+defineix la mateixa funci´o que A. Aix´ı doncs, constru¨ım els seg¨uents problemes d’optimitzaci´o tal que els `optims s’assoleixen amb les {Bσ}que busquem. min Bσ||BσH−Hσ||2 F+τ||Bσ||? on L(X) = ||XH −Hσ||2 F´es la funci´o de p`erdua (de l’angl`es loss function) i||·||?´es la norma nuclear que actua com a regularitzador. La funci´o del regularitzador ´es evitar que el model apr`es sigui massa complex, fins al punt de sobre-ajustar-se a les dades d’aprenentatge i perdre precisi´o amb dades noves. Considerant la concatenaci´o de les matrius Bσen una sola matriu BΣ i el mateix amb les matrius de Hankel podem reduir el problema a un sol problema d’optimitzaci´o: min BΣ||BΣH−HΣ||2 F+τ||BΣ||? El valor de τcontrola el comprom´ıs entre ajustar-se a les dades i la complexitat de l’aut`omat obtingut. Valors petits de τpermeten que la norma nuclear prengui valors m´es grans i per tant obtenen models m´es complexos, mentre que valors grans forcen que el model tingui una norma nuclear baixa i per tant siguin m´es simples. Als experiments mostrem el comportament de models obtinguts amb diferents τi com aquest par`ametre afecta la norma nuclear. Aix´ı doncs, gr`acies a la convexitat de la funci´o de p`erdua i de la norma nuclear hem transformat el problema d’aprenentatge en un problema de minimitzaci´o convexa pel qual existeixen una varietat d’algorismes per solucionar-lo. 20 Cap´ıtol 2. Aprenentatge 2.5.2 Optimitzaci´o convexa. Operadors proximals Per solucionar aquesta optimitzaci´o convexa no ens serveixen les t`ecniques convencionals per optimitzar sobre funcions diferenciables com el M`etode del gradient, ja que la norma nuclear no ´es diferenciable. Per aquest motiu farem servir M`etodes de gradient proximal. Aquests m`etodes es basen en separar la funci´o objectiu en diverses components i aplicar l’operador proximal corresponent sobre cada component. Aquests m`etodes s´on molt populars en el camp de l’aprenentatge, per les seves bones propietats de converg`encia, la facilitat d’implementaci´o, i pels bons resultats que donen. A continuaci´o definirem el concepte d’operador proximal i explicarem els dos m`etodes de gradient proximal que hem usat en aquest projecte, el FISTA [BT09] i l’ADMM [BPC+10]. 2.5.2.1 Operadors proximals Un operador proximal d’una funci´o fen un punt xes defineix com proxf,η(x) = argmin y f(y) + 1 2η||x−y||2 2 Quan f´es prou simple o t´e certes propietats aquests operadors s´on coneguts i existeixen m`etodes r`apids per calcular-los. Per exemple, en el cas que la funci´o f´es diferenciable, llavors y= proxf(x) compleix que x−y´es paral·lel a∇f(y). O b´e, si f´es una funci´o indicadora d’un conjunt convex C, llavors proxf(x) = argmin y∈C||x−y||2= projC(x) ´es a dir, xsi x∈Ci la projecci´o de xal conjunt Caltrament. 2.5.2.2 FISTA L’algorsime FISTA (Fast ISTA) [BT09] ´es una millora de l’algorisme ISTA (Iterative Shrinkage-Thresholding Algorithm). L’ISTA est`a considerat un algorisme d’optimitzaci´o lent per`o f`acil d’implementar, mentre que el FISTA mant´e la simplicitat i aporta una millora significativa a la velocitat de coverg`encia. El FISTA ´es un algorisme per fer minimitzaci´o no restringida de la suma de dues funcions f+g. Aquestes funcions han de ser convexes i la f(o la gper simetria) ha de ser diferenciable i amb primera diferencial L-Lipschitz continua. Una iteraci´o de l’algorisme FISTA consisteix a fer primer un pas de gradient de la funci´o f, que ´es diferenciable, i posteriorment aplicar l’operador proximal de 2.5. M`etode basat en optimitzaci´o convexa 21 x0 y0←x0 γ0←1 for all k≥0do xk+1 = proxg, 1 Lyk−∇f(yk) L γk+1 =1+√1+4γ2 k 2 yk+1 =xk+1 +γk−1 γk+1 (xk+1 −xk) end for Figura 2.4: Pseudocodi de l’algorisme FISTA. la funci´o g. Tant en fer el pas de gradient com en aplicar l’operador proximal interv´e un par`ametre per controlar la longitud de pas, tal com passa amb els algorismes convencionals de descens pel gradient. Aqu´ı n’hi diem γk, on k´es el n´umero d’iteraci´o. El problema que t´e ´es que aplicar l’operador proximal de la funci´o gpot ser una tasca d’optimitzaci´o costosa que no ens podem permetre fer a cada iteraci´o. Per aquest motiu ´es necessari que gsigui suficientment simple perqu`e aquest c`alcul es pugui fer de forma r`apida. En el nostre cas la funci´o figseran les funcions de p`erdua i el regularitzador. Concretament, si BΣiHΣs´on les concatenacions horitzontals de les BσiHσ respectivament, f(BΣ) = τ||HBΣ−HΣ||2 F g(BΣ) = ||BΣ||? i per tant, ∇f(BΣ)=2τH>(HBΣ−HΣ) L= 2τ    H>H    F i proxg,η(BΣ) = shrη(BΣ) on shrη(BΣ) ´es l’operador de contracci´o (“Shrinkage operator”) definit sobre les matrius de la seg¨uent manera shrη(M) = Ushrη(Λ)V> on M=UΛV>´es la descomposici´o SVD i shrη(Λ) ´es la matriu diagonal amb elements (max{s1−1 η,0},...,max{sr−1 η,0}). 22 Cap´ıtol 2. Aprenentatge for all k≥0do xk+1 = argminxf(x) + ρ 2||Ax +Bzk−c+uk||2 2 zk+1 = argminzg(z) + ρ 2||Ax +Bz −c+uk||2 2 uk+1 =uk+Axk+1 +Bzk+1 −c end for Figura 2.5: Pseudocodi de l’algorisme ADMM. 2.5.2.3 ADMM L’algorisme ADMM (Alternating Direction Method of Multipliers) ´es un m`etode basat en el m`etode de descomposici´o dual i el m`etode dels multiplicadors de Lagrange. L’ADMM aconsegueix les propietats de descomposici´o que t´e el m`etode de descomposici´o dual, i a la vegada conserva la robustesa del m`etode dels mutliplicadors de manera que les condicions de converg`encia s´on relaxades. Com en el cas del FISTA aquest algorisme t´e la caracter´ıstica de ser relativament f`acil d’implementar. Aquest algorisme es fa servir per problemes d’optimitzaci´o on tenim dues variables amb objectius separats. ´ Es a dir, problemes de la forma minimize x,z f(x) + g(z) subject to Ax +Bz =c on, per assegurar la converg`encia, es demana que figsiguin convexes, tancades i amb domini no buit. Cada iteraci´o del m`etode consisteix en minimitzar la primera variable deixant la segona fixada, minimitzar la segona deixant la primera fixada i despr´es actualitzar la variable dual. A la figura 2.5 veiem l’esquema de l’algorisme ADMM. Per realitzar aquestes minimitzacions fem servir operadors proximals de manera que desitjarem que figsiguin prou simples o que es puguin descompondre en diverses funcions simples. Semblant al FISTA, en el nostre cas les funcions figseran la funci´o de p`erdua i el regularitzador. Concretament, en aquest cas considerarem les matrius BΣ iHΣformades de la concatenaci´o vertical de les BσiHσrespectivament. I per tant tindrem que, f(BΣ) = ||BΣH−HΣ||2 F g(BΣ) = τ||BΣ||? A= 1, B=−1, c= 0 2.5. M`etode basat en optimitzaci´o convexa 23 i el c`alcul per obtenir xk+1 izk+1 es fa usant operadors proximals de fig. M´es detalls del m`etode es poden trobar a [BPC+10]. 24 Cap´ıtol 2. Aprenentatge 3 Predicci´o En aquest cap´ıtol comentarem l’aplicaci´o dels models apresos per fer predicci´o i veurem les t`ecniques usades per estudiar la bondat d’aquestes prediccions. 3.1 Predicci´o amb aut`omats Amb els m`etodes d’aprenentatge hem apr`es WFA que reprodueixen una distribuci´o de probabilitats fsobre les seq¨u`encies de s´ımbols d’un llenguatge. Volem usar aquests aut`omats per fer tasques de predicc´o del seg¨uent s´ımbol en una seq¨u`encia. Per fer aquesta predicci´o, el que farem ser`a triar aquell s´ımbol que maximitzi la probabilitat de que la seq¨u`encia resultant sigui prefix d’alguna paraula m´es llarga o decidir que la seq¨u`encia actual ja ´es una paraula completa. En aquesta secci´o expliquem com fer aix`o usant els aut`omats apresos. Recordem que estem treballant amb un WFA, ´es a dir un aut`omat indeterminista amb pesos. Aix´ı doncs, una seq¨u`encia w∈Σ?defineix un vector que indica el pes assignat a estar a cada estat de l’aut`omat despr´es d’haver llegit la seq¨u`encia. ´ Es a dir, inicialment tenim el vector d’inici α1que indica el pes d’estar a cada estat sense haver llegit cap s´ımbol. En llegir el primer s´ımbol de whem d’avan¸car als seg¨uents estats segons ens defineix la matriu de transici´o del s´ımbol, per fer aix`o multipliquem el vector actual per la matriu de transici´o per obtenir un nou vector. D’aquesta manera, si fem aix`o per cada s´ımbol de w, al final obtindrem un cert vector d’estats, que correspondr`a a la seq¨u`encia w. La puntuaci´o assignada per l’aut`omat a aquesta seq¨u`encia wcom a paraula completa s’obt´e al multiplicar aquest vector pel vector de final α∞.´ Es a dir, f(w) = α> 1Awα∞ on Aw=Aw1Aw2···Awtamb |w|=tiw=w1w2···wt. 32 Cap´ıtol 4. Llibreria diferents aproximacions. Aix`o implicar`a, entre altres coses, tenir llibertat per escollir la base de prefixos i sufixos amb la qual construir les matrius. Donades les matrius de Hankel, la llibreria permetr`a dur a terme l’aprenentatge d’aut`omats o transductors usant diferents m`etodes. Aquests m`etodes, com ´es natural, tindran par`ametres que l’usuari podr`a ajustar amb llibertat per aconseguir un o diversos models. Una altra funcionalitat ser`a aplicar els models apresos sobre noves seq¨u`encies, ´es a dir, en cas d’aut`omats fer predicci´o i en cas de transductors aconseguir la seq¨u`encia de sortida m´es probable donada una seq¨u`encia d’entrada. Finalment, ja que l’objectiu ´es experimentar i comparar diferents models, la llibreria tindr`a eines per testejar els models apresos i poder fer comparacions entre ells. Haurem de tenir en compte que existeixen diferents tipus de mesura de correctesa d’un model. 4.3 Casos d’´us De l’an`alisi feta podem deduir quatre casos d’´us b`asics: construcci´o de les matrius de Hankel, aprenentatge del model, aplicaci´o del model i testeig del model. En el nostre cas estem treballant amb dos problemes diferents, i per tant cadascun d’aquests casos d’´us tindr`a una versi´o per aut`omats i una per transductors alineats. Com ja hem comentat anteriorment, per tractar amb el problema de transductors alineats considerem l’espai de bi-s´ımbols per simplificar el problema al cas d’una sola seq¨u`encia. Aix`o fa que la construcci´o de les matrius de Hankel i l’aprenentatge del model sigui molt similar en el cas d’aut`omats i de transductors alineats. La ´unica diferencia entre els dos problemes en aquests casos d’´us ´es l’estructura de dades que fan servir per emmagatzemar la informaci´o. 4.3.1 Construcci´o de les matrius de Hankel La sortida d’aquest cas d’´us s´on, com diu el nom, les matrius de Hankel d’un llenguatge aconseguides a partir d’un conjunt de seq¨u`encies d’aquest llenguatge. L’entrada consistir`a en: el nombre de s´ımbols del llenguatge en q¨uesti´o, un corpus de seq¨u`encies d’aprenentatge, instruccions per indicar com construir la base de prefixos i sufixos i, finalment, par`ametres extres per la construcci´o de les matrius. Per a la construcci´o de la base cal especificar el nombre de s´ımbols del llenguatge amb el qual s’est`a treballant, aix´ı com l’estrat`egia per construir-la. Aquesta pot ser o b´e la lectura directa d’un fitxer, a partir de les xprimeres 4.3. Casos d’´us 33 subseq¨u`encies en ordre alfab`etic on x´es un par`ametre, o b´e les xprimeres subseq¨u`encies de mida menor o igual que nordenades segons la freq¨u`encia d’aparici´o en un corpus, on xins´on par`ametres de l’estrat`egia. Els par`ametres extres per la construcci´o de les matrius de Hankel s´on: un indicador per determinar si usar o no el prefix buit i l’opci´o d’usar projeccions aleat`ories per tal de reduir les files i columnes de les matrius al p%, on p´es un par`ametre donat. 4.3.2 Aprenentatge del model La sortida d’aquest cas d’´us ´es un model apr`es usant les matrius de Hankel especificades. Aix´ı doncs, a part de les matrius de Hankel tamb´e cal definir el m`etode d’aprenentatge a fer servir, cadascun dels quals requereix un cert nombre de par`ametres. Per usar el m`etode basat en SVD cal determinar el nombre d’estats que ha de tenir el model. En cas d’usar el m`etode basat en optimitzaci´o convexa amb l’algorisme FISTA cal especificar τi el nombre m`axim d’iteracions de l’optimitzaci´o, on τest`a definida en el cap´ıtol d’aprenentatge. En el cas d’usar el m`etode d’optimitzaci´o convexa amb un algorisme basat en l’ADMM cal especificar τi el nombre m`axim d’iteracions de l’optimitzaci´o, per`o tenint en compte que τest`a definit d’una altra manera (veure cap´ıtol d’aprenentatge). En el cas de l’ADMM amb SVD truncat cal especificar tamb´e el rang m`axim amb el qual fer l’SVD. 4.3.3 Aplicaci´o del model d’un aut`omat Un cop apr`es el model d’un aut`omat, aquest es pot usar per tasques de predicci´o. ´ Es a dir, donat un model i una seq¨u`encia la llibreria et permet obtenir la predicci´o que el model fa del seg¨uent s´ımbol de la seq¨u`encia. De forma similar, donat un model i una seq¨u`encia la llibreria et permet obtenir la puntuaci´o assignada pel model a aquesta seq¨u`encia. 4.3.4 Aplicaci´o del model d’un transductor alineat Com ja hem comentat, si considerem l’espai de bi-s´ımbols i bi-seq¨u`encies un transductor alineat pot actuar com un aut`omat, i per tant pot dur a terme tasques de predicci´o del seg¨uent bi-s´ımbol en una bi-seq¨u`encia. Per aquest motiu la llibreria permet realitzar aquestes tasques de la mateixa manera que ho permet amb els aut`omats. 34 Cap´ıtol 4. Llibreria L’´us natural dels transductors ´es determinar la seq¨u`encia de sortida donada una seq¨u`encia d’entrada. Per tant, donat un model d’un transductor i una seq¨u`encia del llenguatge d’entrada la llibreria et permet obtenir la seq¨u`encia de sortida m´es probable segons el model. 4.3.5 Testeig del model Aquest cas d’´us permet obtenir informaci´o de la correctesa del model. L’entrada s´on un model, un conjunt de dades de testeig i una indicaci´o de quins m`etodes de c`alcul de la bondat d’un model es volen fer servir. El conjunt de dades es recomana que sigui diferent del conjunt usat per entrenar el model per tal d’evitar valoracions err`onies en casos de models sobre-ajustats. En el cas d’aut`omats la llibreria disposa de dos m`etodes de c`alcul de la bondat d’un model que s´on el Word Error Rate (WER) i la perplexitat explicats al cap´ıtol de predicci´o. En el cas de transductors nom´es hi ha disponible el Word Error Rate (WER). 4.4 Diagrama de classes En aquesta secci´o mostrem el diagrama de classes de la llibreria. Aquest diagrama permet implementar tots els casos d’´us descrits a la secci´o anterior. Recordem que la llibreria est`a pensada per realitzar experiments amb els m`etodes que implementa, per`o tamb´e vol permetre implementar-ne de nous de forma senzilla. El diagrama de classes intenta aconseguir un disseny amb bona escalabilitat per`o sempre i quan permeti una implementaci´o eficient de la llibreria. Ja hem dit que aquests m`etodes s´on molt costosos en espai i temps i no ens interessa que l’efici`encia quedi afectada. Un altre fet a tenir en compte ´es que hem decidit separar completament les estructures per tractar el problema d’aprenentatge d’aut`omats i el d’aprenentatge de transductors alineats. Tot i ser cert que tenen moltes coses en com´u i, de fet, els transductors alineats es poden veure com un cas particular d’aut`omats on treballem sobre un espai de bi-s´ımbols, hem considerat que separar les estructures permet una implementaci´o m´es eficient i senzilla. D’aquesta manera tindrem dues classes separades, una per aut`omats i les altres per transductors, dues classes que representaran el concepte de matriu de Hankel i dues per representar les dades, seq¨u`encies en el cas d’aut`omats i bi-seq¨u`encies en el cas de transductors. En la figura 4.1 podem veure la part del diagrama de classes que involucra aquelles classes dedicades a l’aprenentatge. Els diferents m`etodes d’aprenentatge hereten l’estructura de la classe gen`erica “Learner”. Aquesta defineix el 4.4. Diagrama de classes 35 Figura 4.1: Diagrama de classes: Part que involucra les classes d’aprenentatge. m`etode p´ublic “learn” que far`a tasques comunes de tots els m`etodes d’aprenentatge com per exemple cronometrar el temps, i cridar`a a la implementaci´o concreta de cada m`etode, “learn impl”. Aquesta implementaci´o pot ser delicada i per tant no ens interessa repetir-la per cada model de dades. Per aquest 36 Cap´ıtol 4. Llibreria motiu les classes d’aprenentatge defineixen el m`etode privat “learn core” per independitzar el nucli dels m`etodes del tipus de model. Aix´ı, abans de dur a terme l’aprenentatge hi ha un preproc´es per unificar el format de les dades en un de sol. En les figures 4.2 i 4.3 podem veure la part del diagrama de classes que involucra aquelles classes que defineixen les estructures de dades necess`aries pel problema d’aut`omats i el de transductors alineats. Com ja hem comentat, hem decidit no unificar les dues parts per tal de no perdre efici`encia i simplificar la implementaci´o. 4.5 Detalls de la implementaci´o En aquesta secci´o comentarem detalls de la implementaci´o que creiem prou importants per ser destacats. Com ja hem definit anteriorment, les matrius de Hankel v´enen indexades per prefixos i sufixos. Aix`o requereix tenir una indexaci´o de seq¨u`encies. En particular, aquesta indexaci´o la farem servir per generar les matrius de Hankel mitjan¸cant el comptatge del nombre d’aparicions de cada subseq¨u`encia en un corpus. Pensant en aquesta tasca hem decidit usar un Trie per dur a terme aquesta indexaci´o. El Trie ens permet un acc´es r`apid i un ´us redu¨ıt de mem`oria. La implementaci´o s’ha templetitzat perqu`e pugui usar-se tant amb seq¨u`encies com amb bi-seq¨u`encies. Hem templetitzat els operadors proximals dels m`etodes d’aprenentatge basats en optimitzaci´o convexa. Aix`o ens permet modificar els operadors proximals usats en els m`etodes. Aquests operadors s´on l’operador proximal de la funci´o de p`erdua i el de la funci´o que fa el paper de regularitzador del model. D’aquesta manera aconseguim una mica m´es de llibertat perqu`e l’usuari de la llibreria pugui experimentar. En el cas de transducci´o, on considerem l’espai de bi-s´ımbols, hem observat que molts dels bi-s´ımbols de l’alfabet no apareixen al corpus d’aprenentatge. El motiu ´es que moltes de les parelles de s´ımbol d’entrada i s´ımbol de sortida no tenen sentit. Per exemple, suposant que estem fent transcripci´o fon`etica de l’angl`es, o sigui, estem treballant amb paraules de l’angl`es i volem aprendre un transductor capa¸c d’obtenir la seva transcripci´o fon`etica. En aquest conjunt de bi-seq¨u`encies mai observarem la parella <’a’, ’t’ >, ´es a dir, no existeix cap paraula en angl`es on una ’a’ es pronuncii com una ’t’. Aquest fet fa que moltes de les matrius de transici´o del transductor apr`es siguin nul·les. Com que no ens interessa malgastar mem`oria per guardar zeros hem implementat una classe matriu que en cas de ser tota zero no reserva espai en mem`oria. 4.5. Detalls de la implementaci´o 37 Figura 4.2: Diagrama de classes: Part que involucra les estructures de dades per aut`omats. Per la implementaci´o dels m`etodes hem usat la llibreria de codi obert Eigen [Eig], una llibreria d’`algebra lineal en C++. 38 Cap´ıtol 4. Llibreria Figura 4.3: Diagrama de classes: Part que involucra les estructures de dades per transductors. 4.6 Exemple d’´us de la llibreria En aquesta secci´o mostrarem un codi C++ d’exemple de com usar la llibreria. Com ´es natural aquest codi no explora totes les opcions i configuracions de 4.6. Exemple d’´us de la llibreria 39 par`ametres que es poden usar, per`o s´ı que d´ona una idea de com fer-ho. De fet, aquest codi apr`en un aut`omat a partir d’un conjunt de seq¨u`encies d’un llenguatge de 12 s´ımbols (1, 2, ... 12), el testeja amb un conjunt diferent del d’aprenentatge i finalment prediu el seg¨uent s´ımbol de les paraules que es van introduint. s t r i n g symbols [ 1 2 ] = {” . ” , ”ADJ” , ”ADP” , ”ADV” , ”CONJ” , ”DET” , ”NOUN” , ”NUM” , ”PRON” , ”PRT” , ”VERB” , ”X” }; s t r i n g i nt to s ym bo l ( int a ) {return symbols [a −1 ] ; } int sym bo l t o i nt ( s t r i n g pos ) { for (int i = 0 ; i <12; ++i ) i f ( symbols [ i ] == pos ) return i + 1; return 12; } int main () { cout << ” Learning tha automaton . . . ” << endl ; // Training and t e s t i n g s et s Data t r a i n s e t (12 , ” . . / data /ptb−u n i v e r s a l / t r a i n ” ) ; Data t e s t s e t (12 , ” . . / data /ptb−u n i v e r s a l / val ” ) ; // Basis : the 50 most frequen t ngrams of s i z e <= 4 Ba sis b a s i s ( 12 , true ) ; b as i s . setPTN (4 , 50 , &t r a i n s e t ) ; // Hankel Hankel hankel ; hankel . b ui l d ( t r a i n s e t , ba si s , true ) ; //SVD method Model svdModel ; Learner ∗svdLearner = new SVDLearner (25); svdLearner−>le a r n ( hankel , svdModel ) ; // Test the model Test svdTest ( t e s t s e t , svdModel ) ; cout << setw (40) << left << svdModel . g e tInf o () << ”−>” ; cout << ”wer= ” << svdTest .getWER( ) << ” %” << endl << endl ; // Pr edictio n game : Write the f i r s t symbols of a word // and th e model w i l l p r e d i c t t he f o l l o w i n g one cout << ” Please , ente r your sequences : ” << endl ; cout << ” Let me remind you the 12 symbols of the alphabet : ” ; for (int i = 0 ; i <12; ++i ) cout << symbols [ i ] << ’ ’ ; cout << endl << endl ; s t r i n g s ; while ( g e t l i n e ( cin , s ) ) { str ings tream ss ( s ) ; s t r i n g pos ; vector<wchar t>v ( 0 ) ; while ( ss >> pos ) v . push back ( s ymbo l to i nt ( pos ) ) ; 40 Cap´ıtol 4. Llibreria svdModel . i n i t ( ) ; cout << ”The next symbol w i l l be . . . ” ; cout << i nt to symb ol ( svdModel . p r e di c t ( v ) ) << endl ; } } A continuaci´o mostrem la sortida que d´ona el programa si l’executem: Learning the automaton . . . svd (d= 12 , n= 25 ) nn 22.94318 −>wer= 62.7515 % Please , enter your sequences : Let me remind you the 12 symbols of the alphabet : . ADJ ADP ADV CONJ DET NOUN NUM PRON PRT VERB X DET NOUN VERB ADJ CONJ The next symbol w i l l be . . . ADJ PRON VERB ADJ The next symbol w i l l be . . . NOUN Aquest exemple es pot executar f`acilment seguint les seg¨uents instruccions: Descomprimim la llibreria. Ens situem a la carpeta “pfc-amayo/src”. Compilem amb la comanda “make example”. Executem amb la comanda “./example”. Uns requisits suficients perqu`e funcioni s´on estar en una m`aquina amb sistema operatiu Ubuntu(Linux) i disposar de la versi´o 4.6 o posterior del gcc. 5 Experiments En aquest cap´ıtol mostrarem els experiments que s’han dut a terme usant la llibreria. Aquests experiments tenen com a objectiu comparar els m`etodes d’aprenentatge i veure el seu comportament amb diferents configuracions dels par`ametres que intervenen. En general, aquests experiments il·lustrem un ´us intensiu de la llibreria implementada, fent servir la metodologia est`andard en recerca per dur a terme experiments. En la primera secci´o ens centrarem en el problema d’aprenentatge d’aut`omats i posteriorment estudiarem l’aprenentatge de transductors alineats. Per aquestes dues seccions usarem les matrius de Hankel que han donat millors resultats, de manera que en una tercera secci´o mostrarem proves emp´ıriques on s’observa que altres matrius obtingudes amb bases diferents o usant projeccions aleat`ories no milloren els resultats. 5.1 Aut`omats En aquesta secci´o mostrarem la bondat dels models d’aut`omats apresos usant el m`etode basat en SVD i els m`etodes basats en optimitzaci´o convexa. En primer lloc observarem el comportament de cada m`etode per separat i finalment veurem una comparaci´o entre ells. La hip`otesi inicial ´es que els m`etodes d’optimitzaci´o convexa ens permetran trobar millors models pel fet de disposar d’un regularitzador continu, mentre els m`etodes basats en SVD usen com a regularitzador el nombre d’estats de l’aut`omat, que ´es discret. ´ Es clar, per`o, que el temps d’aprenentatge ser`a major en el cas de m`etodes basats en optimitzaci´o convexa. 5.1.1 Descripci´o de les dades i matrius de Hankel Com ja hem comentat usarem les mateixes dades i les mateixes matrius de Hankel en tots els m`etodes per tal de qu`e els resultats siguin comparables. En 48 Cap´ıtol 5. Experiments 60 61 62 63 64 65 66 67 68 69 70 1000 10000 100000 1e+06 1e+07 1e+08 1e+09 wer tau p=12 p=25 p=50 p=100 p=300 0 5 10 15 20 25 30 35 40 45 50 1000 10000 100000 1e+06 1e+07 1e+08 1e+09 Norma nuclear tau p=12 p=25 p=50 p=100 p=300 Figura 5.7: Bondat de models d’aut`omats apresos amb el m`etode basat en optimitzaci´o convexa amb FISTA usant bases de diferents mides (p) en funci´o de τ. La primera gr`afica mostra el Word Error Rate en funci´o de τ, mentre que la segona mostra la norma nuclear del model en funci´o de τ. Estad´ıstic 12 25 50 100 SVD n= 6 n= 10 n= 24 n= 31 ADMM τ= 10−7τ= 10−7τ= 10−11 τ= 10−12 FISTA τ= 10000 τ= 10000 τ= 10000 τ= 10000 Figura 5.8: Par`ametres que aconsegueixen el model d’aut`omat amb m´es encert per cada m`etode i mida de base. fa servir l’algorisme ADMM per l’optimitzaci´o ´es el que troba models amb m´es encert. En segon lloc hi ha el m`etode basat en SVD i finalment, a bas- 5.1. Aut`omats 49 60 61 62 63 64 65 66 67 68 69 70 50 100 150 200 250 300 350 400 450 500 wer Tamany de la base SVD ADMM FISTA 0 5 10 15 20 25 30 35 40 45 50 50 100 150 200 250 300 350 400 450 500 Norma nuclear Tamany de la base SVD ADMM FISTA Figura 5.9: Comparaci´o entre el models apresos amb diferents m`etodes i diferents mides de base. tant dist`ancia trobem el m`etode basat en optimitzaci´o convexa que fa servir l’algorisme FISTA. Ja hav´ıem observat que el FISTA no convergia suficientment r`apid i per tant ´es natural que els seus resultats siguin m´es dolents que els dels altres m`etodes. En el cas de l’SVD i l’ADMM esdev´e quelcom que ja esper`avem: el m`etode d’optimitzaci´o convexa disposa d’un regularitzador continu que ens permet una exploraci´o m´es exhaustiva de l’espai d’aut`omats. D’aquesta manera ´es capa¸c de trobar un model que s’ajusta millor a les nostres necessitats. 50 Cap´ıtol 5. Experiments 5.1.4.2 Mem`oria El cost en mem`oria d’aquests m`etodes ´es significatiu, sobretot si volem treballar amb alfabets de mida considerable. Un exemple ´es el cas de considerar totes les paraules d’un diccionari com elements de l’alfabet i intentar predir la seg¨uent paraula d’una oraci´o. Per aquest motiu ens interessen m`etodes que requereixin poca mem`oria. A continuaci´o fem una an`alisi de la quantitat de mem`oria necess`aria pels m`etodes que hem estudiat en aquest projecte. Suposarem que tots els valors que intervenen ocupen el mateix nombre de bytes, 4 o 8 segons la m`aquina on s’estiguin executant els m`etodes. Com ´es natural cada m`etode necessita espai per emmagatzemar el model de l’aut`omat que intenta aprendre i tamb´e les matrius de Hankel. Farem les mateixes suposicions que hem fet per analitzar el temps: una mida d’alfabet d, una base de pprefixos i psufixos, i que el nombre d’estats del model ´es n. Per tant, l’espai necessari per emmagatzemar el model ´es O(dn2) i per les matrius de Hankel es necessita O(dp2). En el cas del m`etode basat en SVD es necessita una quantitat addicional de mem`oria molt inferior a la necessaria pel model i les matrius de Hankel. Aquesta informaci´o s´on dues matrius de n×pcadascuna. El nombre d’estats del model nve determinat per l’usuari, per facilitar els n´umeros suposarem que ´es p. Llavors l’espai total necessari ´es de l’ordre de O(2dp2). En el cas del m`etode basat en optimitzaci´o convexa que fa servir l’ADMM l’hem programat usant quatre matrius addicionals de la mateixa mida que totes les matrius de Hankel concatenades. ´ Es a dir, un total de 4 matrius de dp2. El nombre d’estats del model ´es p, i per tant l’espai total necessari ´es de l’ordre de O(6dp2). El FISTA l’hem programat usant cinc matrius addicionals de la mida de les matrius de Hankel concatenades, ´es a dir, 5 matrius de dp2. El nombre d’estats del model ´es p, i per tant l’espai total necessari ´es de l’ordre de O(7dp2). SVD ADMM FISTA O(2dp2)O(6dp2)O(7dp2) Figura 5.10: Quantitat de mem`oria necess`aria per l’aprenentatge d’aut`omats usant diferents m`etodes. 5.1.4.3 Temps ´ Es cert que el m`etode basat en optimitzaci´o convexa aconsegueix millors resultats que el m`etode basat en SVD, per`o sabem que l’aprenentatge ´es m´es 5.2. Transductors 51 lent. En aquesta secci´o farem una an`alisi del nombre d’operacions necess`aries per cada m`etode. Per fer els c`alculs suposem un alfabet de mida d, una base de pprefixos i p sufixos, de manera que les matrius de Hankel s´on quadrades de mida p×pi que el nombre d’estats del model ´es n. Per simplificar els c`alculs suposarem que n=ptot i que en el m`etode basat en SVD aquest ´es un par`ametre que pot prendre valors entre 1 i p. Farem servir que el cost d’invertir una matriu n×n´es O(n3), fer SVD d’una matriu m×n´es O(km2n+k0n3) on k= 4 i k0= 22 si fem servir l’algorisme R-SVD i fer el producte de dues matrius de mida n×kik×m´es O(nmk). Pels m`etodes basats en optimitzaci´o convexa suposarem que necessitem el nombre d’iteracions que hem marcat anteriorment per convergir. ´ Es a dir, l’ADMM suposarem que fa 100 iteracions i el FISTA 1000. El m`etode basat en SVD ha de fer un SVD de la matriu de Hankel Hque ´es de mida p×p, invertir una matriu de p×pi fer 2dproductes de matrius de p×pcadascuna. Per tant, el cost total ´es de O((k+k0)p3) + O(2dp3) = O((4 + 22 + 2d)p3) = O((26 + 2d)p3). La complexitat dels m`etodes basats en optimitzaci´o convexa est`a dominada per l’SVD a una matriu de la mida de concatenar totes les matrius de transici´o, per tant de mida dp×p. El cost d’aquest SVD ´es O(k(dp)2p+k0p3) = O((4d2+ 22)p3). Aquest temps ja ´es major que el necessari per el m`etode basat en SVD, per`o a m´es a m´es l’hem de multiplicar pel nombre d’iteracions. SVD ADMM FISTA O((26 + 2d)p3)O(100(4d2+ 22)p3)O(1000(4d2+ 22)p3) Figura 5.11: Temps necessari per l’aprenentatge d’aut`omats usant diferents m`etodes. A la taula 5.11 veiem un resum de l’an`alisi temporal dels m`etodes. Com a refer`encia en segons, dur a terme un SVD d’una matriu de 300 ×300 tarda aproximadament 9 segons en un Intel Core i7-2600. 5.2 Transductors En aquesta secci´o mostrarem la bondat dels models de transductors apresos usant el m`etode basat en SVD i els m`etodes basats en optimitzaci´o convexa. En primer lloc observarem cada m`etode per separat i finalment veurem una comparaci´o entre ells. Com en el cas d’aut`omats, la hip`otesi inicial ´es que els 52 Cap´ıtol 5. Experiments m`etodes d’optimitzaci´o convexa ens permetran trobar millors models pel fet de disposar d’un regularitzador continu. Com que en el problema de transducci´o treballem en l’espai de bi-s´ımbols, la mida de l’alfabet augmenta considerablement. Aix´ı com en el cas d’aut`omats hem experimentat amb alfabets de mida 12, en aquest cas treballarem amb un alfabet d’entrada de mida 26 i un de sortida de mida 51. Aix`o fa que tinguem un total de 26 ·51 = 1326 bi-s´ımbols, tot i que observarem que molts d’ells no apareixen al corpus d’aprenentatge perqu`e s´on combinacions de s´ımbol d’entrada i de sortida sense sentit. Recordem que en el cas de transductors prediem la seq¨u`encia sencera de sortida usant l’algorisme de Viterbi i despr´es comparem el resultat s´ımbol a s´ımbol. 5.2.1 Descripci´o de les dades i matrius de Hankel Estad´ıstic Valor N´umero de s´ımbols d’entrada 26 N´umero de s´ımbols de sortida 51 N´umero de bi-s´ımbols te`orics 1326 N´umero de bi-s´ımbols diferents en el corpus d’aprenentatge 137 N´umero de bi-s´ımbols en el corpus de testeig 108 N´umero de bi-seq¨u`encies d’aprenentatge 5000 N´umero de bi-seq¨u`encies de testeig 1034 Longitud mitjana de bi-seq¨u`encies d’aprenentatge 7.43 Longitud mitjana de bi-seq¨u`encies de testeig 5.42 Figura 5.12: Descripci´o dels conjunts de dades d’aprenentatge i testeig usats per l’elaboraci´o dels experiments de transductors. Com ja hem comentat usarem les mateixes dades i les mateixes matrius de Hankel en tots els m`etodes per tal que els resultats siguin comparables. En particular, en aquest cas farem servir bi-seq¨uencies de paraules en angl`es i la seva transcripci´o fon`etica codificada amb 51 car`acters de la taula ASCII. A la taula 5.12 es poden veure els detalls del corpus de seq¨u`encies d’aprenentatge i de testeig, i a la figura 5.13 mostrem algunes de les bi-seq¨u`encies que trobem en aquest corpus. Observem que hi ha 10 vegades m´es bi-s´ımbols te`orics que bi-s´ımbols observables en el corpus d’aprenentatge. ´ Es a dir, la mida de l’alfabet amb el qual estem treballant usant aquest conjunt de seq¨u`encies d’aprenentatge ´es de 137. En comparaci´o al conjunt de dades usat pel cas d’aut`omats hem multiplicat per 10 el nombre total de s´ımbols de l’alfabet, cosa que augmentar`a la mida 5.2. Transductors 53 seamstress s i - m s t r x s - p u n c h p ˆ n C - c o s m o n a u t kazmxnc -t c a p i t u l a t e k x p I C x l e t - Figura 5.13: Exemples de bi-seq¨u`encies de paraules en angl`es i la seva transcripci´o fon`etica codificada amb 51 car`acters de la taula ASCII. de base necessaria per obtenir bons resultats. Augmentar`a tamb´e el cost temporal de realitzar la predicci´o, ja que tenim m´es opcions per escollir, i el cost en mem`oria d’emmagatzemar el model, ja que tenim 10 vegades m´es matrius de transici´o. Donades les dades d’aprenentatge hem generat les matrius de Hankel usades pels experiments. En particular hem usat bases de diferents mides per`o sempre escollint com a prefixos i sufixos aquelles subseq¨u`encies de mida menor o igual a 4 que apareixen amb m´es freq¨u`encia al corpus d’aprenentatge, juntament amb la subseq¨u`encia buida. Tot i no ser necessari hem fet servir bases amb el mateix nombre de prefixos i de sufixos. 5.2.2 M`etode basat en SVD Les seg¨uents gr`afiques mostren la bondat dels models apresos usant el m`etode basat en SVD sobre les matrius de Hankel descrites anteriorment. A la figura 5.14 veiem el comportament dels diferents de models de transductors apresos amb el m`etode basat en SVD a mesura que prenem diferents bases. El comportament ´es molt similar al que hem vist amb els aut`omats. Bases m´es grans milloren els resultats obtinguts, ja que tenim matrius de Hankel que aproximen millor el Hankel original. Tamb´e podem observar el fenomen de sobreajustament a les dades, en aquesta gr`afica es veu clarament en el cas de les bases m´es petites on a partir d’un cert nombre d’estats l’error del model augmenta. 5.2.3 M`etodes basats en optimitzaci´o convexa Com ja hem comentat la mida de l’alfabet ha augmentat considerablement, i per tant tamb´e ho ha fet el cost temporal de dur a terme experiments i 54 Cap´ıtol 5. Experiments 20 22 24 26 28 30 32 34 36 38 40 5 10 15 20 25 30 35 40 45 50 wer Nombre d’estats 25 50 100 300 1000 0 5 10 15 20 25 30 35 40 45 50 5 10 15 20 25 30 35 40 45 50 Norma nuclear Nombre d’estats 25 50 100 300 1000 Figura 5.14: Bondat dels models de transductors apresos amb el m`etode basat en SVD usant bases de diferents mides (p). La primera gr`afica mostra el Word Error Rate en funci´o del nombre d’estats, mentre que la segona mostra la norma nuclear del model en funci´o del nombre d’estats. generar aquestes gr`afiques. Com que en el cas d’aut`omats ja hem observat que el m`etode basat en optimitzaci´o convexa que fa servir el FISTA t´e una converg`encia lenta, no el farem servir en el cas de transductors. Aix´ı doncs ens centrarem en el m`etode d’optimitzaci´o convexa que fa servir l’ADMM. Per aquest m`etode hem decidit no fer proves amb bases tan grans com en el cas del m`etode basat en SVD, ja que el temps d’execuci´o ´es elevat. 5.2. Transductors 55 5.2.3.1 ADMM El m`etode ADMM disposa de dos par`ametres: el nombre m`axim d’iteracions per l’optimitzaci´o i la τque trobem a la funci´o objectiu que multiplica la norma nuclear. Aix´ı doncs, en primer lloc observarem les gr`afiques de converg`encia per tal de fixar un nombre m`axim d’iteracions pels experiments i posteriorment exacutarem el m`etode usant diferents valors de τ. p = 25 0 0.0002 0.0004 0.0006 0.0008 0.001 0.0012 0.0014 0.0016 0.0018 0.002 0 20 40 60 80 100 Funció de pèrdua Número d’iteració tau=1e−2 tau=1e−4 tau=1e−6 tau=1e−8 tau=1e−10 tau=0 p = 50 0 0.0002 0.0004 0.0006 0.0008 0.001 0.0012 0.0014 0.0016 0.0018 0.002 0 20 40 60 80 100 Funció de pèrdua Número d’iteració tau=1e−2 tau=1e−4 tau=1e−6 tau=1e−8 tau=1e−10 tau=0 p = 100 0 0.0002 0.0004 0.0006 0.0008 0.001 0.0012 0.0014 0.0016 0.0018 0.002 0 20 40 60 80 100 Funció de pèrdua Número d’iteració tau=1e−2 tau=1e−4 tau=1e−6 tau=1e−8 tau=1e−10 tau=1e−12 tau=0 Figura 5.15: Gr`afiques de la converg`encia del m`etode d’optimitzaci´o convexa que usa l’algorisme ADMM amb diferents mides de base aplicat al problema de transductors. A la figura 5.15 podem veure que l’optimitzaci´o convergeix, i m´es o menys amb 100 iteracions ha assolit un punt dif´ıcil de millorar. Observem tamb´e que en el cas d’una base de mida 25, per τ= 0.01 la funci´o de p`erdua oscil·la entre dos valors sense convergir. Dit aix`o, hem fixat el nombre m`axim d’iteracions a 100 per estudiar la bondat dels models aconseguits per diferents valors de τ. A la figura 5.16 observem que el comportament de la gr`afica ´es semblant al que hem vist amb el m`etode basat en SVD. Usar bases m´es grans millora els resultats obtinguts i si no donem prou import`ancia al regularitzador (la norma nuclear) el model empitjora a causa del sobreajustament a les dades. 56 Cap´ıtol 5. Experiments 20 22 24 26 28 30 32 34 36 38 40 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 wer tau p=25 p=50 p=100 0 10 20 30 40 50 60 70 80 90 100 1e-14 1e-12 1e-10 1e-08 1e-06 0.0001 0.01 Norma nuclear tau p=25 p=50 p=100 Figura 5.16: Bondat de models de transductors apresos amb el m`etode basat en optimitzaci´o convexa amb ADMM usant bases de diferents mides (p). La primera gr`afica mostra el Word Error Rate en funci´o de τ, mentre que la segona mostra la norma nuclear del model en funci´o de τ. Tal com passava en el cas d’aut`omats, a la gr`afica de la norma nuclear es pot veure el comportament esperat, com menor ´es τ(que multiplica la norma nuclear a la funci´o objectiu) major ´es la norma nuclear. ´ Es a dir, τens permet regular la complexitat del model. 5.2.4 Comparativa L’objectiu d’aquest apartat ´es comparar els resultats obtinguts pels diferents models. Com en el cas d’aut`omats estem interessats en la correctesa dels models a l’hora de predir, per`o tamb´e en el cost temporal i espacial de l’apre- 5.2. Transductors 57 nentatge. 5.2.4.1 Correctesa Estad´ıstic 25 50 100 SVD n= 4 n= 11 n= 25 ADMM τ= 10−4τ= 10−6τ= 10−6 Figura 5.17: Par`ametres que aconsegueixen el model de transductor amb m´es encert per cada m`etode i mida de base. 20 22 24 26 28 30 32 34 36 38 40 30 40 50 60 70 80 90 100 wer Tamany de la base SVD ADMM 0 10 20 30 40 50 60 70 80 90 100 30 40 50 60 70 80 90 100 Norma nuclear Tamany de la base SVD ADMM Figura 5.18: Comparaci´o entre els models apresos amb diferents m`etodes i diferents mides de base. Per comparar la bondat dels m`etodes hem considerat diferents mides de base. 64 Cap´ıtol 5. Experiments p = 100 60 61 62 63 64 65 66 67 68 69 70 5 10 15 20 25 30 35 40 45 50 wer states RegPath SVD (p = 100) (ngrams) NO-RP RP-50 RP-33 RP-25 RP-20 RP-10 RP-05 RP-01 Figura 5.25: Bondat d’aut`omats apresos amb SVD usant projeccions aleat`ories amb base de les 100 primeres subseq¨u`encies. NO-RP ´es el model que no ha usat projeccions aleat`ories i RP-X s´on models que han projectat les matrius de Hankel al X% de la seva capacitat. no aporten millores als models. 6 Conclusi´o L’objectiu principal d’aquest projecte era l’elaboraci´o d’una llibreria en C++ per dur a terme tasques d’aprenentatge d’aut`omats usant m`etodes espectrals. Hem complert amb aquest objectiu i, de fet, hem usat la llibreria per generar una bateria d’experiments que ens ha perm`es comparar i treure conclusions dels m`etodes d’aprenentatge que hem implementat. Molts d’aquests experiments no s’havien pogut realitzar fins ara pel grup de recerca de’n Xavier Carreras, en Borja Balle i l’Ariadna Quattoni perqu`e nom´es es disposava d’una implementaci´o dels m`etodes amb MATLAB, usant el paquet d’alt nivell CVX. Aquesta implementaci´o no era escalable a grans volums de dades i per tant nom´es permetia experimentar amb conjunts de dades petits. En l’`ambit personal aquest projecte m’ha introdu¨ıt en el m´on de l’aprenentatge autom`atic treballant en un grup de recerca. L’assist`encia a les reunions del grup m’han donat una perspectiva de com treballa el personal de recerca de la universitat, fet que em ser`a molt ´util a l’hora de decidir qu`e far´e en un futur. A m´es a m´es, he pogut aplicar molts dels coneixements apresos a la carrera, he apr`es a fer servir la llibreria matem`atica Eigen i he apr`es a escriure en L A T EX. 66 Cap´ıtol 6. Conclusi´o Bibliografia [BCLQ13] B. Balle, X. Carreras, F.M. Luque, and A. Quattoni. Spectral learning of weighted automata: A forward-backward perspective. Machine Learning, 2013. [BPC+10] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. 2010. [BQC11] B. Balle, A. Quattoni, and X. Carreras. A spectral learning algorithm for finite state transducers. ECML, 2011. [BQC12] B. Balle, A. Quattoni, and X. Carreras. Local loss optimization in operator models: A new insight into spectral learning. ICML, 2012. [BT09] Amir Beck and Marc Teboulle. A fast iterative shrinkagethresholding algorithm for linear inverse problems. SIAM J. Img. Sci., 2(1):183–202, March 2009. [CP71] J.W. Carlyle and A. Paz. Realizations by stochastic finite automata. Journal of Computer and System Sciences, 5(1):26–40, 1971. [Eig] Eigen library (http://eigen.tuxfamily.org). [HKZ09] D. Hsu, S. M. Kakade, and T. Zhang. A spectral algorithm for learning hidden Markov models. Conference on Learning Theory (COLT), 2009.