Monitorización preditiva en procesos complexos non estruturados con información insuficiente

UNIVERSIDADE DE SANTIAGO DE COMPOSTELA ESCOLA T´ ECNICA SUPERIOR DE ENXE ˜ NAR´ IA Monitorizaci´on preditiva en procesos complexos non estruturados con informaci´on insuficiente Autor/a: Pedro Gamallo Fern´andez Titores: Juan Carlos Vidal Aguiar Manuel Lama Pen´ın Grao en Enxe˜nar´ıa Inform´atica Xu˜no 2021 Traballo de Fin de Grao presentado na Escola T´ecnica Superior de Enxe˜nar´ıa da Universidade de Santiago de Compostela para a obtenci´on do Grao en Enxe˜nar´ıa Inform´atica Agradecementos Primeiramente aos meus pais e ´a mi˜na irm´a, por ser o piar fundamental da mi˜na vida. Sen a vosa plena confianza en min este cami˜no, xa complexo de por si, ter´ıa sido moito m´ais dif´ıcil. A mi˜na t´ıa, por preocuparse sempre por min e facerme a vida en Santiago moito m´ais sinxela. Aos meus av´os que, a´ında que xa non poidan estar aqu´ı para verme, sempre foron o meu exemplo a seguir e cos que sempre quixen compartir os meus logros. A todos os meus amigos que me acompa˜naron ao longo de tantos anos. En especial a Uriel, Manuel, Dami´an e Brais, por ser os meus fieis compa˜neiros nesta traxectoria universitaria, tanto nas longas tardes de biblioteca como nas curtas ocasi´ons de festa. Aos meus titores, por darme a oportunidade de adentrarme no mundo da investigaci´on e saber animarme e dirixirme correctamente ao longo destes meses, facendo da realizaci´on deste traballo un proceso algo m´ais doado. 3 4 Resumo A monitorizaci´on preditiva de procesos, rama de investigaci´on en auxe nos ´ultimos anos pola s´ua utilidade para empresas e instituci´ons, permite predicir o comportamento futuro dunha instancia en execuci´on dun proceso de negocio. Nos ´ultimos anos, ´as t´ecnicas convencionais empregadas neste campo sum´aronselle novas aproximaci´ons baseadas en aprendizaxe profunda, ´area da intelixencia artificial que est´a ga˜nando moita popularidade ultimamente. Destas aproximaci´ons, as que mellores resultados est´an obtendo son aquelas baseadas en redes neuronais recurrentes, as cales permiten analizar correctamente a informaci´on hist´orica para realizar a predici´on correspondente. Recentemente, publicouse unha nova soluci´on que emprega unha arquitectura GAN, un tipo de redes novel que est´a destacando no ´ambito da xeraci´on de imaxes e do procesamento da linguaxe natural polos bos resultados obtidos. Esta soluci´on c´entrase no problema da predici´on da seguinte actividade a executar e o momento no que suceder´a. Neste traballo proponse unha nova aproximaci´on baseada tam´en neste tipo de arquitectura que pretende mellorar os resultados obtidos para a predici´on do seguinte tempo de execuci´on. Como parte desta proposta explicarase o dese˜no interno da arquitectura e tam´en o preprocesamento realizado sobre os datos de entrada para que estes sirvan de base ´a rede ´a hora de realizar as predici´ons. 5 6 Memoria tipo A – ´ Indice xeral 1. Introduci´on 1 1.1. Miner´ıadeprocesos.......................... 2 1.2. Monitorizaci´on preditiva . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Aprendizaxe profunda (Deep Learning)............... 5 1.4. ObxectivosdoTFG.......................... 8 2. Estado de co˜necemento 11 2.1. Monitorizaci´on preditiva . . . . . . . . . . . . . . . . . . . . . . . 11 2.2. Primeiras aproximaci´ons con Aprendizaxe Profunda . . . . . . . . 12 2.3. AuxedasGAN ............................ 14 3. Materiais 17 3.1. Conxuntos de datos empregados . . . . . . . . . . . . . . . . . . . 17 3.2. M´etrica de rendemento: MAE . . . . . . . . . . . . . . . . . . . . 17 3.3. Particionado train/validation/test .................. 18 3.4. Sistemas hardware e ferramentas software . . . . . . . . . . . . . 19 4. Metodolox´ıa 21 4.1. Preprocesamento dos datos . . . . . . . . . . . . . . . . . . . . . . 21 4.1.1. Partici´on dos datos . . . . . . . . . . . . . . . . . . . . . . 21 4.1.2. Agrupaci´on dos eventos de cada caso de execuci´on . . . . . 22 4.1.3. C´alculo da duraci´on de cada actividade . . . . . . . . . . . 23 4.1.4. Xeraci´on dos prefixos . . . . . . . . . . . . . . . . . . . . . 23 4.2. Dese˜no da arquitectura CGAN . . . . . . . . . . . . . . . . . . . . 26 4.2.1. Limitaci´on das GAN na monitorizaci´on preditiva . . . . . 27 4.2.2. Nova arquitectura de predici´on: GAN condicional . . . . . 28 5. Probas 37 5.1. Optimizaci´on dos hiperpar´ametros . . . . . . . . . . . . . . . . . . 37 5.2. Comparativa coa proposta de referencia . . . . . . . . . . . . . . . 40 6. Discusi´on dos resultados 43 7. Conclusi´ons e posibles ampliaci´ons 45 7 Bibliograf´ıa 47 A. Manual de usuario 51 Glosario 53 Siglas 55 8 ´ Indice de figuras 1.1. Modelo dun proceso, representado en notaci´on BPMN. . . . . . . 1 1.2. Exemplo dunha ´arbore de decisi´on [3]. . . . . . . . . . . . . . . . 5 1.3. Exemplos de funci´ons de activaci´on non lineais [5]. . . . . . . . . . 6 1.4. Representaci´on dun perceptr´on [5]. . . . . . . . . . . . . . . . . . 6 1.5. Sistema de capas de neuronas dunha rede neuronal. . . . . . . . . 7 1.6. Esquema interno dunha rede neuronal recurrente [7]. . . . . . . . 8 2.1. Representaci´on dunha neurona LSTM [15]. . . . . . . . . . . . . . 13 2.2. Estrutura b´asica dunha GAN convencional. . . . . . . . . . . . . . 15 4.1. Exemplo da xeraci´on convencional de prefixos dada unha secuencia. 25 4.2. Exemplo dun mini-lote de prefixos e o mini-lote cos seguintes temposasociados.............................. 27 4.3. Estrutura GAN empregada na publicaci´on de referencia. . . . . . 28 4.4. Estrutura dunha GAN Condicional. . . . . . . . . . . . . . . . . . 28 4.5. Dese˜no do Xerador proposto. . . . . . . . . . . . . . . . . . . . . 30 4.6. L´oxica interna da capa LSTM do Xerador. . . . . . . . . . . . . . 31 4.7. Dese˜no do Discriminador proposto. . . . . . . . . . . . . . . . . . 32 4.8. Representaci´on xerada para o prefixo na capa LSTM. . . . . . . . 33 5.1. Evoluci´on do MAE durante a validaci´on cos distintos valores dos hiperpar´ametros. ........................... 39 5.2. Evoluci´on do erro para o conxunto de datos Helpdesk........ 41 5.3. Evoluci´on do erro para o conxunto de datos BPI 2012. ...... 41 5.4. Evoluci´on do erro para o conxunto de datos Sepsis. ........ 42 5.5. Evoluci´on do erro para o conxunto de datos Env. permit. . . . . . 42 5.6. Evoluci´on do erro para o conxunto de datos BPI 2012 w. . . . . . 42 9 4CAP´ ITULO 1. INTRODUCI ´ ON ´e mellorable. 1.2. Monitorizaci´on preditiva Dentro das tecnolox´ıas de mellora da miner´ıa de procesos, nos ´ultimos anos ten xurdido con forza a monitorizaci´on preditiva [3]. A diferenza da maior parte das t´ecnicas de mellora, que analizan os puntos cr´ıticos do modelo en base ´as instancias xa finalizadas [4], na monitorizaci´on preditiva real´ızase unha an´alise na que se pred´ın non s´o os puntos cr´ıticos antes de que estos cheguen a selo, sen´on tam´en outros elementos do proceso que son de interese. Para isto, as t´ecnicas de monitorizaci´on preditiva utilizan como entradas os k´ultimos eventos. Estes k ´ultimos eventos reciben o nome de prefixos (ou k-prefixos) e conforman secuencias dunha determinada lonxitude kque permiten co˜necer, para un evento concreto, os keventos sucedidos anteriormente como parte da execuci´on do caso. As´ı pois, as t´ecnicas enmarcadas dentro desta disciplina permiten predicir a continuaci´on dunha instancia en execuci´on do proceso de negocio en base a unha an´alise do prefixo correspondente ´a actividade actual. Analizando esta informaci´on co˜necida, tr´atase de atopar patr´ons de comportamento que permitan relacionar a informaci´on presente nos eventos para predicir eventos e atributos futuros. Entre as predici´ons m´ais com´uns que tratan de realizar estas t´ecnicas at´opanse as seguintes: Predici´on da seguinte actividade: Co˜necendo as actividades executadas previamente nunha instancia, pret´endese predicir a actividade que se executar´a en seguinte lugar. Nos exemplos presentados anteriormente, poder´ıase co˜necer que tenda visitar´a a continuaci´on o cliente do centro comercial ou que transacci´on realizar´a o titular da conta de aforros. Predici´on do seguinte sufixo de actividades: Ampl´ıase o problema anterior ´a predici´on de todas actividades futuras ata a finalizaci´on do caso estudado. Con este predici´on poderanse co˜necer toda a secuencia de acci´ons que realizar´a, por exemplo, o cliente antes de sa´ır do centro comercial, pero engade unha maior incertidume e tr´atase dun problema de predici´on m´ais dif´ıcil. Predici´on do seguinte tempo: Ao co˜necer as actividades executadas previamente e os seus tempos de duraci´on, pode ser posible predicir o momento no que rematar´a a actividade actual para dar paso ´a seguinte. Grazas a esto, p´odese saber en que momento quedar´an liberados certos recursos e pasar´an a ser necesarios outros distintos. Deste xeito, ´e m´ais doado realizar unha planificaci´on da asignaci´on dos mesmos, incrementando a eficiencia dos procesos. 1.3. APRENDIZAXE PROFUNDA (DEEP LEARNING)5 Predici´on do tempo restante: En base ´a secuencia seguida polo caso de execuci´on ata un determinado punto (actividades realizadas e os seus tempos), tr´atase de predicir en que momento finalizar´a por completo o caso. Esta informaci´on pode ser empregada para priorizar uns casos do proceso de negocio sobre outros, co fin de evitar a violaci´on de certas restrici´ons, como datas l´ımites. Este Traballo de Fin de Grao (TFG) c´entranse na predici´on do seguinte tempo, debido a que ´e a m´ais amplamente abordada no estado de co˜necemento en monitorizaci´on preditiva, sendo tam´en o problema que trata a aproximaci´on de referencia coa que se comparar´a a proposta e implementaci´on realizada no TFG. Orixinalmente as t´ecnicas empregadas base´abanse en t´ecnicas de aprendizaxe autom´atica convencionais coma as m´aquinas de vectores de soporte ou as ´arbores de decisi´on. Na Figura 1.2 am´osase a ´arbore de decisi´on que se xera nun determinado punto da execuci´on dun proceso de negocio relacionado co ´ambito m´edico, na cal cada p´ola leva asociado un peso que corresponde coa posibilidade de que dita actividade sexa executada a continuaci´on para acadar o obxectivo de negocio (lograr a recuperaci´on do paciente). Por´en, nos ´ultimos tempos o campo da monitorizaci´on preditiva viuse enriquecido con diversas aportaci´ons baseadas na introduci´on de algoritmos de aprendizaxe profunda para a realizaci´on das distintas predici´ons. Este tipo de t´ecnicas son as que actualmente obte˜nen os mellores resultados na monitorizaci´on preditiva e tam´en ser´an as que se empreguen na soluci´on proposta neste traballo. Figura 1.2: Exemplo dunha ´arbore de decisi´on [3]. 1.3. Aprendizaxe profunda (Deep Learning) Aaprendizaxe profunda (co˜necida como Deep Learning, polo seu nome en ingl´es) [5] ´e un subconxunto da aprendizaxe autom´atica, disciplina da Intelixencia Artificial orientada a desenvolver modelos capaces de aprender por si mesmos as transformaci´ons das entradas recibidas nas sa´ıdas esperadas. O Deep Learning 6CAP´ ITULO 1. INTRODUCI ´ ON caracter´ızase en que os modelos xerados aprenden moitas capas de transformaci´ons, onde cada unha ofrece un nivel de representaci´on distinto, obtendo as´ı unha xerarqu´ıa de caracter´ısticas. As arquitecturas de aprendizaxe profunda conf´ormanse por capas de neuronas. Na s´ua expresi´on m´ais sinxela (o perceptr´on), dita operaci´on corresp´ondese coa suma ponderada das s´uas entradas, como se mostra na ecuaci´on 1.1. y= ( n X i=1 xi∗wi) + b=XW +b(1.1) Nesta ecuaci´on, Xsimboliza o vector de valores de entrada que recibe a neurona, W´e un vector de n´umeros denominados pesos, e b´e o valor que se co˜nece coma o sesgo. Cada valor do vector Xmultipl´ıcase polo valor correspondente do vector de pesos, sumando posteriormente todos os resultados obtidos, e finalmente o sesgo. A continuaci´on, sobre o resultado obtido pode aplicarse unha funci´on non lineal, denominada funci´on de activaci´on, como a ReLU, a Sigmoide ou a tanxente hiperb´olica (todas elas mostradas na figura 1.3). Na figura 1.4 repres´entase graficamente o preceptr´on. (a) ReLU (b) Sigmoide (c) Tanxente hiperb´olica Figura 1.3: Exemplos de funci´ons de activaci´on non lineais [5]. Figura 1.4: Representaci´on dun perceptr´on [5]. Estendendo o concepto de perceptr´on, xorden os sistemas de capas de neuronas (Figura 1.5) nos que as neuronas de cada capa se comunican directamente 1.3. APRENDIZAXE PROFUNDA (DEEP LEARNING)7 coas neuronas doutras capas, propagando as´ı os seus resultados pola rede. Tipicamente, a entrada dunha neurona corresp´ondese coa sa´ıda das neuronas da capa anterior, mentres que a s´ua sa´ıda serve como entrada das neuronas da capa seguinte. Novamente, esta situaci´on pode variar en funci´on do tipo de arquitectura. Neste sistema, ademais, existen d´uas capas especiais: por unha parte a capa de entrada, que recibe directamente os valores reais que alimentan ´a rede e, por outra, a capa de sa´ıda que devolve ao exterior os resultados. Todas as demais capas intermedias reciben o nome de capas ocultas. Para aprender a realizar as transformaci´ons correctas, a rede axusta iterativamente os pesos das s´uas neuronas durante o proceso de adestramento. Entre as distintas t´ecnicas, a m´ais com´un ´e a da propagaci´on cara atr´as ou retropropagaci´on (backpropagation en ingl´es), mediante a cal calc´ulanse os respectivos gradientes e co˜n´ecese en que medida debe ser axustado cada peso. Esta t´ecnica explicarase m´ais en detalle no cap´ıtulo 3. Capa de entrada Capas ocultas Capa de saída Rede neuronal profunda Figura 1.5: Sistema de capas de neuronas dunha rede neuronal. Entre os distintos tipos de redes existentes, as que resultan m´ais relevantes para este TFG son as que se catalogan como redes recurrentes. Estas redes especial´ızanse no procesamento de secuencias [6], ´e dicir, en realizar diversas operaci´ons como a clasificaci´on ou a xeraci´on de novos elementos nunha secuencia de datos. Dada a natureza secuencial dos procesos de negocio (secuencias de actividades), este tipo de redes resultan moi ´utiles para afrontar o problema da monitorizaci´on preditiva. As redes recurrentes, na s´ua versi´on m´ais sinxela co˜necida como RNN (Recurrent Neural Network), incl´uen un novo valor como entrada de cada neurona denominado estado oculto. Este estado oculto (hidden state en ingl´es), proporciona a informaci´on sobre as entradas pasadas da secuencia, posibilitando as´ı que se te˜nan en conta os sucesos anteriores. As operaci´ons matem´aticas que se realizan en cada neurona RNN son as que se amosan na ecuaci´on 1.2, onde o elemento htdenota o estado oculto no instante de tempo actual t, mentres que ht−1especifica o estado oculto do tempo inmediatamente anterior; a variable xtreferencia a entrada no momento actual t;U,V,Wrepresentan os vectores de pesos; bec indican os sesgos correspondentes; e o valor de ot´e a sa´ıda final da neurona no 8CAP´ ITULO 1. INTRODUCI ´ ON instante de tempo t. Na figura 1.6 repres´entase gr´aficamente esta neurona. ht=tanh(b+Wht−1+Uxt) ot=c+V ht (1.2) Figura 1.6: Esquema interno dunha rede neuronal recurrente [7]. Existen outras variantes das redes recurrentes como as LSTM, GRU ou MANN que ser´an introducidas no cap´ıtulo 2. De todas estas, a m´ais interesante para este TFG ´e a LSTM, empregada dentro da arquitectura de tipo GAN proposta que se presenta no cap´ıtulo 4. Este tipo de arquitecturas, que ser´an presentadas m´ais a fondo tam´en no cap´ıtulo 2, sup´on unha das aproimaci´ons que mellores resultados est´an ofrecendo nos problemas relacionados coa xeraci´on de novos datos, como a xeraci´on de imaxes. Dado que o problema da predici´on na monitorizaci´on preditiva pode ser considerado como a xeraci´on de novos datos (actividades nos casos da predici´on da seguinte actividade e da predici´on do sufixo, e tempos nos problemas da predici´on do seguinte tempo e do tempo restante), a inclusi´on de arquitecturas GAN neste ´ambito proponse como unha boa soluci´on, a´ında que se trata dunha aproximaci´on moi recente. En concreto, existe unha ´unica proposta [8] (que se presenta tam´en no cap´ıtulo seguinte) que fai uso deste tipo de arquitecturas de redes neuronais. A mellora dos resultados obtidos por dita soluci´on sup´on a motivaci´on principal deste traballo. 1.4. Obxectivos do TFG Recapitulando o xa comentado ao longo dos apartados anteriores, neste TFG ab´ordase a presentaci´on dunha soluci´on baseada nunha nova modalidade de redes de aprendizaxe profunda, as GAN, para abordar unha das predici´ons m´ais com´uns no ´ambito da monitorizaci´on preditiva: a predici´on do tempo de inicio da seguinte actividade. Tomarase como referencia a publicaci´on [8] na que xa se intentaron inclu´ır estas redes para realizar predici´ons sobre procesos non estruturados, tratando de mellorar os resultados obtidos polos autores. De tal xeito, o obxectivo principal deste TFG ´e a implementaci´on dunha arquitectura de aprendizaxe profunda para abordar o problema da monitorizaci´on preditiva sobre procesos non estruturados, comparando a 1.4. OBXECTIVOS DO 9 eficiencia da mesma coa outra aproximaci´on baseada en redes GAN existente. Este obxectivo principal div´ıdese nos seguintes obxectivos m´ais concretos: 1. Estudo e an´alise da proposta de referencia. Para a implementaci´on da soluci´on proposta, inicialmente ´e preciso realizar unha an´alise sobre a ´unica aproximaci´on que existe ata o momento na que se empregue a arquitectura GAN para o problema da monitorizaci´on preditiva. Estudarase en que puntos ´e mellorable dita aproximaci´on para abordar o problema da predici´on do seguinte tempo. 2. Analise do preprocesamento dos datos. Un dos aspectos m´ais importantes ´a hora de traballar tanto con redes de aprendizaxe profundo como con t´ecnicas de miner´ıa de procesos ´e o correcto tratamento dos datos de entrada. Por iso, ser´a preciso realizar unha an´alise para determinar cal ´e a forma ´optima de procesar os datos antes de que estes sirvan como entrada para a arquitectura GAN. 3. Dese˜no da arquitectura GAN como t´ecnica de monitorizaci´on preditiva. Dese˜narase unha soluci´on baseada en redes de tipo GAN capaz de predicir o momento no que se executar´a a seguinte actividade dun caso en execuci´on. Neste dese˜no analizarase a estrutura interna da arquitectura explicando as s´uas compo˜nentes. 4. Implementaci´on da arquitectura GAN. Realizarase a implementaci´on do dese˜no resultante nunha linguaxe de programaci´on de alto nivel, obtendo as´ı un modelo apto para realizar as predici´ons. 5. Validaci´on da arquitectura GAN con conxuntos de datos reais. O modelo obtido do punto anterior ser´a validado con alg´uns dos conxuntos de datos reais m´ais usados pola comunidade de miner´ıa de procesos, obtendo as´ı uns valores que permitan medir o grao de acerto nas s´uas predici´ons. 6. Comparaci´on do sistema proposto coa soluci´on de referencia. Para poder contextualizar os resultados obtidos durante a validaci´on, realizarase unha comparativa xusta entre a aproximaci´on de referencia e a soluci´on proposta. Equiparando alg´uns aspectos relevantes como os conxuntos de datos e as partici´ons empregadas, obteranse uns resultados que permitir´an co˜necer en que medida a soluci´on mellora (ou empeora) os resultados obtidos pola GAN de [8]. 10 CAP´ ITULO 1. INTRODUCI ´ ON Cap´ıtulo 2 Estado de co˜necemento Neste cap´ıtulo presentarase o estado de co˜necemento relacionado coas t´ecnicas de monitorizaci´on preditiva, facendo ´enfase nas proposta de aprendizaxe profunda, en xeral, e nas redes GAN, en particular. Cabe rese˜nar que a descrici´on da ´unica proposta GAN para monitorizaci´on preditiva, de Taymouri et al. [8], realizarase no cap´ıtulo 4, xa que deste xeito ´e m´ais sinxelo comparar as caracter´ısticas de dita arquitectura coa soluci´on proposta neste TFG. 2.1. Monitorizaci´on preditiva Dado que as primeiras publicaci´ons sobre miner´ıa de procesos datan de 2011 [2], a monitorizaci´on preditiva de procesos de negocio constit´ue tam´en unha disciplina de investigaci´on novel. Un dos primeiros traballos de monitorizaci´on preditiva ´e [3]. Neste artigo, o autor presenta unha soluci´on baseada en t´ecnicas de clustering (agrupamento dos datos) e ´arbores de decisi´on para realizar predici´ons sobre a consecuci´on de determinados obxectivos, como poden ser a finalizaci´on do caso antes dunha determinada data l´ımite ou chegar a un estado desexado. A partir deste punto, proliferaron diversas propostas empregando un amplo rango de t´ecnicas. Algunhas delas bas´eanse en xerar representaci´ons expl´ıcitas dun modelo de proceso, coma en [9], onde se empregan redes de Petri estoc´asticas para capturar distribuci´ons de duraci´on arbitrarias e as´ı lograr unha maior precisi´on nas predici´ons. Outros enfoques c´entranse na extracci´on de vectores de caracter´ısticas dos casos de execuci´on para adestrar modelos de aprendizaxe autom´atica, coma en [10], onde se empregan m´aquinas de vectores de soporte para descubrir posibles violaci´ons do proceso en tempo de execuci´on; ou en [11], que fai uso de m´aquinas de factorizaci´on para co˜necer as interaci´ons entre caracter´ısticas latentes que poden ser utilizadas para predicir o pr´oximo evento dun caso en curso. 11 12 CAP´ ITULO 2. ESTADO DE CO ˜ NECEMENTO 2.2. Primeiras aproximaci´ons con Aprendizaxe Profunda A´ında que as propostas anteriores obte˜nen polo xeral un b´o rendemento, estas metodolox´ıas s´o poden considerar un n´umero limitado de eventos anteriores ´a actividade actual, o que fai que non se poda considerar un hist´orico moi longo para poder facer unha predici´on. Para resolver este problema, no ano 2017 J. Evermann et al. en [12] e N. Tax et al. en [13] iniciaron un novo campo de investigaci´on centrado en desenvolver arquitecturas de redes de aprendizaxe profunda capaces de xeneralizar o problema de predici´on. Nestes traballos us´aronse as redes de tipo LSTM debido ´a s´ua versatilidade ´a hora de tratar problemas de secuencias de elementos que te˜nen dependencias entre s´ı e nos que, polo tanto, hai que gardar en memoria os resultados do procesamento de elementos previos cando se trata o elemento actual. As redes LSTM, ideadas por Hochreiter e Schmidhuber no 1997 [14], reciben este nome do termo ingl´es orixinal Long Short-Time Memory, facendo alusi´on ´a s´ua capacidade de manexar longas dependencias de entradas previas. Estas redes, ao tratarse dunha variante das redes recurrentes covencionais, responden correctamente ante problemas que traballan con secuencias temporais, como pode ser o fluxo de actividades e os seus tempos nun caso en execuci´on dun proceso de negocio. A diferenza das Vanilla RNN (ou RNN b´asicas, como a presentada no cap´ıtulo 1), que unicamente traballaban co valor do instante de tempo anterior (ht−1), as LSTM son capaces de recordar informaci´on por longos per´ıodos temporais. Para lograr este comportamento, introd´ucense na s´ua estrutura interna unha cela de memoria Ctde car´acter recurrente (Figura 2.1). Para obter esta recurrencia, a cela internamente cont´en 3 portas: a porta de entrada (it), a porta de sa´ıda (ot) e a porta de esquecemento (ft). Estas portas controlan como fl´ue a informaci´on da cela e seguen as ecuaci´ons 2.1, 2.2 e 2.3 respectivamente, onde U, VeWrepresentan os vectores de pesos, bo sesgo, e σrepresenta a funci´on de activaci´on empregada. it=σ(bi+Uixt+Wiht−1)(2.1) ot=σ(bo+Uoxt+Woht−1)(2.2) ft=σ(bf+Ufxt+Wfht−1)(2.3) Para obter o valor da cela no momento de tempo actual ( ˆ Ct) empr´egase a ecuaci´on 2.4. A sa´ıda final da cela (Ct), aplicando o valor desta sa´ıda no instante anterior (Ct−1), refl´ıctese na ecuaci´on 2.5. O valor final da neurona para o instante actual (ht) calc´ulase seguindo a ecuaci´on 2.6. Nestas ecuaci´ons, o s´ımbolo ·representa o producto Hadamard (multiplicaci´on elemento a elemento das compo˜nentes das matrices). 2.2. PRIMEIRAS APROXIMACI ´ ONS CON APRENDIZAXE PROFUNDA13 ˆ Ct=tanh(bC+UCxt+WCht−1)(2.4) Ct=ft·Ct−1+it·ˆ Ct(2.5) ht=ot·tanh(Ct)(2.6) Figura 2.1: Representaci´on dunha neurona LSTM [15]. Evermann, motivado pola aplicaci´on das t´ecnicas de Deep Learning nos problemas de procesamento da linguaxe natural (NLP, do termo ingl´es Natural Language Processing), avoga pola inclusi´on destas redes na monitorizaci´on preditiva facendo un s´ımil entre o problema da predici´on da seguinte palabra nunha frase e a predici´on da seguinte actividade nun caso dun proceso de negocio. Na soluci´on proposta, desenv´olvese unha rede recurrente de tipo LSTM capaz de predicir a seguinte actividade dun prefixo dado, obtendo en xeral mellores resultados que a aproximaci´on baseada en t´ecnicas convencionais que empregan como referencia [16]. Na publicaci´on de Tax, o autor prop´on novamente a utilizaci´on dunha rede neuronal artificial de tipo LSTM en base aos b´os resultados obtidos por este tipo de arquitecturas noutros dominios de modelado de secuencias coma o procesamento da linguaxe natural ou o reco˜necemento da fala. En dito traballo, o autor aborda tanto o problema da predici´on da seguinte actividade xa tratado por Evermann, como a predici´on do sufixo de actividades, a predici´on do tempo de execuci´on da seguinte actividade e a predici´on do tempo restante de execuci´on convert´ındose as´ı nun dos traballos m´ais completos da literatura. A partires destas d´uas propostas, m´ais autores seguiron aportando novas soluci´ons baseadas tam´en en redes recurrentes. Navarin et al. [17] abordan a predici´on do tempo restante por medio dunha rede de tipo LSTM coa que calcula directamente o tempo que falta ata a finalizaci´on. Este m´etodo sup´on unha innovaci´on con respecto ´a proposta de Tax [13] e ´a de M. Camargo et al. [18] (que tam´en 20 CAP´ ITULO 3. MATERIAIS do CiTIUS (Centro Singular de Investigaci´on en Tecnolox´ıas Intelixentes), o cal conta con varios servidores espec´ıficos de GPUs da reco˜necida marca NVIDIA. En concreto, empregouse un servidor equipado con d´uas tarxetas NVIDIA Tesla V100S-PCIe, cuxas especificaci´ons det´allanse no Cadro 3.2. Modelo NVIDIA Tesla V100S-PCIe Arquitectura NVIDIA Volta Tensor Cores 640 CUDA Cores 5120 Memoria 32 GB Ancho de banda da memoria 1134 GB/seg Consumo m´aximo de enerx´ıa 250 W Cadro 3.2: Especificaci´ons da tarxeta NVIDIA Tesla V100S-PCIe. No tocante ´a linguaxe de programaci´on, na implementaci´on aportada como parte deste TFG optouse por empregar Python, seguindo a li˜na da meirande parte das aproximaci´ons do estado de co˜necemento. Dentro das posibilidades que ofrece Python para implementar redes de Deep Learning, neste traballo decidiuse empregar PyTorch polas posibilidades que ofrece para personalizar os modelos e as arquitecturas de redes neuronais creadas. Outros paquetes de funci´ons usados foron Pandas para o preprocesamento de datos, NumPy para traballar con vectores e matrices multidimensionais, WandB para a monitorizaci´on dos resultados e do axuste dos pesos das redes neuronais e Tune para a optimizaci´on dos hiperpar´ametros empregados. Para manter unha correcta xesti´on de todas estas librer´ıas e paquetes precisos empregouse Conda, un xestor de paquetes e de entornos que permite a virtualizaci´on dun espazo de traballo ou entorno (environment) no cal reunir todos os paquetes necesarios para a execuci´on. As´ı mesmo, Linux foi o sistema operativo empregado tanto para realizar a implementaci´on como as experimentaci´ons deste traballo. En concreto, as distribuci´ons empregadas foron Debian 9 no equipo de desenvolvemento e CentOS 8 no servidor de GPUs. Recapitulando, de xeito resumido os elementos hardware e software empregados foron os que se mostran no Cadro 3.3: Sistema hardware GPU NVIDIA Tesla V100S-PCIe (CiTIUS) Sistema operativo Debian GNU/Linux 9, CentOS Linux 8 Linguaxe de programaci´on Python 3.8 Xestor de entornos Conda Librer´ıas PyTorch 1.7.1, Pandas, NumPy, WandB e Tune Cadro 3.3: Elementos hardware e software empregados durante a realizaci´on deste traballo. Cap´ıtulo 4 Metodolox´ıa Neste cap´ıtulo pres´entase a soluci´on proposta para abordar o problema da predici´on do seguinte tempo. Esta soluci´on, como xa se avanzou no cap´ıtulo 2, est´a baseada nunha arquitectura CGAN, composta ´a s´ua vez por d´uas redes de tipo LSTM. Cabe destacar que esta nova arquitectura ´e a primeira proposta de CGAN que aborda o problema da predici´on do seguinte tempo. Tanto o dese˜no de ambas redes coma o preprocesamento previo do datos realizado neste traballo det´allanse nas seguintes secci´ons. 4.1. Preprocesamento dos datos Os rexistros hist´oricos dos eventos dun proceso de negocio serven como entrada ´a aproximaci´on presentada. Ditos rexistros de eventos comp´o˜nense dunha secuencia eventos asociados a un caso de execuci´on. Entre a informaci´on que se recolle destes eventos at´opase o identificador do caso ao que corresponden, o identificador da actividade executada e o momento no que se produce (timestamp da actividade). Toda esta informaci´on as´ı presentada non pode ser usada directamente como entrada das redes neuronais. Previamente ´e preciso realizar un proceso de selecci´on e tratamento dos datos ata obter os prefixos que finalmente recibir´a a arquitectura CGAN. As tarefas involucradas neste proceso son as que se co˜necen conxuntamente como preprocesamento dos datos de entrada. A continuaci´on, detallaranse as tarefas de preprocesamenteo realizadas no marco do TFG. 4.1.1. Partici´on dos datos De entre as distintas t´ecnicas de particionado dos datos empregadas para adestrar e validar as t´ecnicas de aprendizaxe autom´atica, o particionado train/ validation/test ´e unha das m´ais empregadas. Por medio desta t´ecnica cons´eguense reducir os tempos de computaci´on requeridos ao empregar un menor n´umero de 21 22 CAP´ ITULO 4. METODOLOX´ IA iteraci´ons que outras t´ecnicas como a validaci´on cruzada. ´ A hora de empregar esta t´ecnica, un aspecto fundamental ´e seleccionar os tama˜nos m´ais axeitados para ditas partici´ons. Xeralmente, unha partici´on grande de train axudar´a a adestrar mellor a rede, facendo que esta consiga aprender m´ais, a´ında que tam´en pode derivar no problema do sobreaxuste (ou overfitting en ingl´es). Este efecto provoca que o modelo obtido sexa capaz de predicir ´a perfecci´on os valores cos que foi adestrado, xerando uns resultados excesivamente artificiais que, ademais, tender´an a fallar maioritariamente ante novos datos que poida recibir a rede durante o seu uso. Por contra, contar cunhas partici´ons de validaci´on e test moi grandes axuda a comprobar mellor cal ser´a a eficacia da rede na s´ua futura explotaci´on, pero pode derivar nun escaso adestramento, facendo que a rede non sexa capaz de realizar boas predici´ons en ning´un caso, tendo o que se co˜nece coma subaxuste (underfitting en ingl´es). Neste traballo, para afrontar este problema seguiuse o esquema de particionado proposto por Rama-Maneiro et al. en [21]. En concreto, no c´odigo empregado primeiramente real´ızase unha ordenaci´on dos eventos polo seu valor na columna do timestamp, obtendo as´ı todas as actividades ordenadas polo momento no que se executaron. A continuaci´on, real´ızase unha primeira separaci´on en dous subconxuntos conformados por un 80 % e un 20 % dos datos, onde o segundo grupo se etiqueta directamente como a partici´on de test, mentres que o primeiro volve ser dividido novamente en dous subgrupos cunha distribuci´on 80/20. O primeiro destes subgrupos, que abarca un 64 % do conxunto global (0.8 x 0.8 = 0.64), nom´ease como a partici´on de adestramento; mentres que o outro subgrupo, co 16 % restante (0.8 x 0.2 = 0.16), conforma a partici´on de validaci´on. O Cadro 4.1 reflicte esta situaci´on. Partici´on 1ªdivisi´on 2ªdivisi´on Porcentaxe global Adestramento 80 % 80 % 64 % Validaci´on 20 % 16 % Test 20 % 20 % Cadro 4.1: Particionado dos datos de entrada. 4.1.2. Agrupaci´on dos eventos de cada caso de execuci´on A informaci´on dos eventos hist´oricos dunha instancia en execuci´on s´o ´e ´util se estos se presentan de forma ordenada. Para asegurarse de que isto ´e as´ı, d´ebese ler o conxunto de datos empregado e realizar un agrupamento exclusivo dos rexistros que o conforman, eliminando eventos pertencentes a outros casos. As´ı, unha vez lidos os rexistros, estes agr´upanse segundo o valor da columna do identificador do caso (CaseID), obtendo as´ı os conxuntos de eventos corres- 4.1. PREPROCESAMENTO DOS DATOS 23 pondentes a cada instancia. Nun conxunto atoparanse todos os eventos asociados ao caso de execuci´on identificado co n´umero 0, noutro distinto os correspondentes ao caso de execuci´on n´umero 1, e as´ı sucesivamente. 4.1.3. C´alculo da duraci´on de cada actividade A´ında que o tempo no que se rexistran os eventos dentro dun caso de execuci´on ´e unha informaci´on moi relevante, o dato que verdadeiramente se precisa co˜necer para o problema da predici´on do seguinte tempo ´e o tempo transcurrido dende a execuci´on da actividade anterior ata a actual. Sabendo que os eventos notifican o momento de execuci´on da actividade que rexistran, neste traballo a diferencia entre os tempos de execuci´on dunha actividade e a anterior calc´ulase como a diferencia (en d´ıas) entre os timestamps do evento actual e do inmediatamente anterior na secuencia ordenada. O feito de ter escollido o d´ıa como a unidade de referencia d´ebese ´as duraci´ons medias dos eventos nos distintos conxuntos de datos descritos no Cadro 3.1. Para o caso do primeiro evento, que non ten un evento anterior co que calcular a diferencia temporal, as´ıgnaselle unha duraci´on igual a 0. Esta situaci´on especial non sup´on ningunha alteraci´on do resultado das predici´ons feitas pola rede, xa que a primeira actividade de cada caso nunca ser´a predita, igual que tampouco o ´e en ningunha das aproximaci´ons do estado de co˜necemento. Esto d´ebese a que se precisa como m´ınimo un evento anterior para poder predicir a actividade seguinte. As diferenzas entre os timestamps calculadas almac´enanse nunha nova columna baixo o nome de diff time, que volver´a ser empregada ´a hora de xerar os prefixos finais. 4.1.4. Xeraci´on dos prefixos A ´ultima operaci´on propia do preprocesamento dos datos, e a m´ais complexa, ´e a xeraci´on dos prefixos que finalmente servir´an como entrada real (variable x) da arquitectura implementada, as´ı coma os valores futuros que a rede tentar´a predicir (variable y). Neste traballo, para cada evento optouse por seleccionar exclusivamente a informaci´on considerada m´ais relevante que est´a recollida en todos os conxuntos de datos; non tendo en conta informaci´on que unicamente se atopa nalg´uns destes conxuntos, como o recurso que realiza a actividade ou indicadores de negocio. As´ı, a informaci´on considerada ´e o identificador da actividade, o timestamp na que ten lugar e a diferenza de tempo coa actividade anterior (diff temp). Ao elixir esta informaci´on, estamos considerando que a predici´on do seguinte tempo est´a condicionado polo tipo de actividades anteriormente executadas no caso e a diferenza entre os tempos de execuci´ons das mesmas. Esta suposici´on tam´en 24 CAP´ ITULO 4. METODOLOX´ IA se fai noutras aproximaci´ons do estado de co˜necemento, como na publicaci´on de Taymouri [8]. Por outra parte, ao final da secuencia de eventos de cada caso eng´adese un novo evento co˜necido como final de caso (end of case en ingl´es), que marca de xeito inequ´ıvoco a fin do caso de execuci´on. Este evento mant´en a mesma informaci´on que os demais eventos do caso, tendo un valor 0 para todos os atributos, excepto no identificador da actividade, onde se emprega un identificador ´unico no conxunto de datos. No exemplo do dataset BPI 2013 Closed Problems, que cont´en 7 actividades distintas (do 0 ao 6), o identificador de actividade deste rexistro ´e o 7. Cos pasos anteriores realizados, xa se poden crear os prefixos finais. ´ A hora de realizar esta tarefa, un dos aspectos m´ais relevantes ´e a selecci´on da lonxitude k, o que se co˜nece como o tama˜no ou lonxitude do prefixo. Un tama˜no de prefixo grande permite proporcionar ´a rede m´ais informaci´on hist´orica sobre a instancia coa que se est´a traballando, a cal poder´a empregar para realizar predici´ons m´ais acertadas. Por contra, empregar prefixos longos implica un coste computacional maior, problema que se ve incrementado nas GAN ao estar constitu´ıdas por d´uas redes. Por todo elo, debe buscarse un valor de compromiso para esta lonxitude do prefixo, que realmente constit´ue un hiperpar´ametro da arquitectura proposta. No cap´ıtulo 5 disc´utese a selecci´on destes hiperpar´ametros, inclu´ındo a lonxitude de prefixo, que finalmente ser´a de 4. En base ao tama˜no kde prefixo seleccionado, os rexistros da secuencia preparada nos anteriores pasos agr´upanse de xeito ordenado en conxuntos de dita lonxitude. Xeralmente, para a xeraci´on destas agrupaci´ons esc´olmanse os primeiros krexistros da secuencia e m´arcanse coma o primeiro prefixo. Para o prefixo inmediamente seguinte, m´ovense os rexistros unha posici´on ´a esquerda, pasando o que ocupaba a segunda posici´on a situarse na primeira, o da terceira a ocupar a segunda, e as´ı sucesivamente, entrando no ´ultimo lugar do grupo o primeiro rexistro dos exclu´ıdos no paso anterior. Este algoritmo, do que se pode ver unha representaci´on gr´afica na Figura 4.1, rep´ıtese ata cubrir todos os eventos da secuencia (a excepci´on do engadido end of case, que xa non foi inclu´ıdo na Figura). Padding O principal problema deste algoritmo ´e que se precisan polo menos keventos previos dunha instancia para comezar a xerar os prefixos, co que s´o se poden realizar predici´ons a partir do elemento k+ 1, impedindo as´ı facer predici´ons para tama˜nos de prefixo menores que a lonxitude especificada k. Para paliar este impedimento, na soluci´on aportada faise uso da t´ecnica de padding. Por medio desta t´ecnica, naquelas situaci´ons nas que todav´ıa non existen suficientes rexistros para xerar un prefixo, introd´ucese un recheo que permite chegar ao tama˜no k co que se estea a traballar. Desta forma, ´e posible co˜necer unicamente a primeira 4.1. PREPROCESAMENTO DOS DATOS 25 A B C D E Caso de execución Tamaño de prefixo (k): 3 Prefixos A B C B C D C D E Figura 4.1: Exemplo da xeraci´on convencional de prefixos dada unha secuencia. das actividades para realizar predici´ons xa sobre a segunda. As´ı pois, co mesmo n´umero de datos dispo˜nibles p´odense realizar m´ais predici´ons e, consecuentemente, mell´orase o adestramento da rede. Esta t´ecnica implem´entase por medio do Algoritmo 1: Algoritmo 1 Creaci´on de prefixos con padding prefixo ←vector() contador ←1 mentres contador <tama~no prefixo facer tama~no padding ←tama~no prefixo −contador padding ←filasDeCeros(tama~no padding) engadir(prefixo,padding) rexistros reais ←obterPrimeirosRexistros(contador) engadir(prefixo,rexistros reais) contador++ fin A introduci´on de filas con todos os valores iguais a 0 ao comezo do prefixo representa un recheo carente de informaci´on ´util para a rede. O feito de que este recheo se sit´ue ao principio bas´ease no estudo realizado en [25], onde se demostra que esta t´ecnica obt´en mellores resultados que colocar o recheo ao final, xa que desta forma a informaci´on ´util do prefixo ser´a a ´ultima en ser introducida na rede e, por tanto, ser´a recordada mellor para as predici´ons. Ademais, por medio dun correcto adestramento, a rede aprender´a a obviar dita informaci´on de recheo e centrarse en analizar exclusivamente as filas ´utiles dos prefixos que recibiron o 26 CAP´ ITULO 4. METODOLOX´ IA padding. ´ A par que se xeran estes prefixos, tam´en se seleccionan os valores reais que a rede tentar´a predicir para cada un. Deste xeito, para o problema da predici´on do seguinte tempo esc´ollese o valor de diff time do seguinte evento non inclu´ıdo todav´ıa no prefixo. Seguidamente, os valores enteiros de ActivityID codif´ıcanse en vectores one-hot. Esto d´ebese a que estes valores son de tipo categ´orico, servindo para identificar a categor´ıa ou tipo da actividade, e non simples n´umeros ordinais. Con esta codificaci´on ev´ıtase o problema de que a rede asuma ordenaci´ons impl´ıcitas entre estos valores. As´ı pois, se o dataset do exemplo ten agora 8 actividades (7 m´ais o end of case), a actividade 0 pasar´ıa a representarse polo vector h1,0,0,0,0,0,0,0i, a actividade 1 polo vector h0,1,0,0,0,0,0,0i, e as´ı sucesivamente. Mini-lotes (mini-batches) Unha vez se disp´on de todos os prefixos co seu correspondente seguinte valor, ambos conxuntos son reagrupados novamente en grupos dun mesmo tama˜no, conformando os mini-lotes (mini-batches en ingl´es). Os mini-lotes son pequenas agrupaci´ons dos datos de entrada que le a rede en cada iteraci´on do adestramento. Desta forma, o axuste dos pesos s´o se realiza despois de ter lido todos os exemplos do mini-lote, e non para cada dato individual, reducindo as´ı o n´umero de c´alculos a realizar. Os mini-lotes que conte˜nen os prefixos son empregados como entrada da arquitectura implementada (sendo as´ı a variable Xdo problema), mentres que os que conte˜nen os seguintes valores correspondentes serven para medir o grao de acerto das predici´ons realizadas (sendo a variable Y). As´ı pois, as entradas da aproximaci´on proposta (X) presentan a dimensionalidade B∗K∗N, onde Brepresenta o tama˜no do mini-batch empregado (o cal tam´en ´e un hiperpar´ametro da rede que ser´a analizado no cap´ıtulo 5), K corresp´ondese coa lonxitude do prefixo; e Nref´ırese ao n´umero de elementos inclu´ıdos en cada elemento do prefixo, ´e dicir, todas as compo˜nentes do vector one-hot m´ais o valor diff time asociado. As sa´ıdas (Y) ´a s´ua vez presentan a dimensionalidade B∗K∗1, dado que para cada prefixo as´ociase un ´unico valor: a diferenza entre o tempo de execuci´on da ´ultima actividade do prefixo e a seguinte no caso de execuci´on. A Figura 4.2 ilustra como se conforman estos conxuntos. 4.2. Dese˜no da arquitectura CGAN A partires do estudio das importantes limitaci´ons da arquitectura GAN de referencia, proposta por Taymouri et al. [8], dese˜nouse e implementouse unha nova arquitectura de redes de aprendizaxe profunda que segue o paradigma das GAN condicionais (Conditional GAN, CGAN, en ingl´es). A continuaci´on presentarase esta nova arquitectura. 4.2. DESE ˜ NO DA ARQUITECTURA 27 Prefixo 1 Prefixo 2 Prefixo B ... Mini-lote de prefixos X Seguinte tempo 1 Seguinte tempo 2 Seguinte tempo B ... Mini-lote de seguintes tempos Y Figura 4.2: Exemplo dun mini-lote de prefixos e o mini-lote cos seguintes tempos asociados. 4.2.1. Limitaci´on das GAN na monitorizaci´on preditiva Na arquitectura orixinal das GAN, a rede que act´ua como xerador recibe exclusivamente como entrada un vector de ru´ıdo (v´exase a Figura 2.2). Este vector de ru´ıdo est´a composto por valores aleatorios, que son os ´unicos tidos en conta por esta rede para xerar os novos datos. Ademais, para realizar as predici´ons sobre a autenticidade dos datos, a ´unica informaci´on de entrada que recibe o discriminador son os exemplos tanto reais (extra´ıdos do dataset dispo˜nible) como obtidos polo xerador. Soamente con esta informaci´on, o discriminador ten que predicir se o dato que recibe en cada momento ´e real e procedente do conxunto de datos, ou xerado polo seu opo˜nente. Esta arquitectura il´ustrase na Figura 2.2. No caso da monitorizaci´on preditiva, onde a informaci´on hist´orica conforma a entrada principal, a anterior estrutura presenta un notable problema. O xerador, encargado de realizar as predici´ons, deber´ıa poder recibir os prefixos preprocesados para basearse neles ´a hora de obter o seguinte valor. Do mesmo xeito, o discriminador tam´en precisa estes prefixos para poder contextualizar o dato a clasificar. Sen esta informaci´on, as sa´ıdas de ambas redes ser´an puramente aleatorias. Para solucionar esta restrici´on, na aproximaci´on proposta por Taymouri et al. [8] substit´uese o vector de ru´ıdo que alimenta a rede do xerador polo propio prefixo preprocesado, serv´ındolle ´a rede como base para fundamentar as s´uas predici´ons. Igualmente, introd´ucense cambios na entrada do discriminador, o cal pasa a recibir non s´o o seguinte valor (real ou predito), sen´on unha concatenaci´on do mesmo co seu prefixo correspondente. Todas estas variaci´ons quedan reflexadas na Figura 4.3. Non obstante, tal e como se ver´a no cap´ıtulo 5, esta estratexia non soluciona o problema, xa que disfraza o seguinte o valor dentro dunha secuencia de datos maioritariamente reais, facendo que as predici´ons do discriminador sexan menos precisas e influ´ındo negativamente no adestramento global da rede. Por outra, as GAN impo˜nen un algoritmo de adestramento estrito, que ser´a analizado no apartado 4.2.2.3, consistente en adestrar o xerador exclusivamente en 28 CAP´ ITULO 4. METODOLOX´ IA Figura 4.3: Estrutura GAN empregada na publicaci´on de referencia. base ao erro cometido nas predici´ons realizadas polo discriminador. Sen embargo, na implementaci´on da GAN de Taymouri et al. o adestramento do xerador incl´ue o erro cometido polo propio xerador na predicci´on do seguinte tempo. Tal e como se ver´a no cap´ıtulo 5, esta estratexia dificulta a converxencia do xerador ´a hora de predecir os seguintes tempos, xa que o adestramento da rede non ten en conta unicamente a sa´ıda do discriminador. 4.2.2. Nova arquitectura de predici´on: GAN condicional Para resolver os problemas de predici´on do seguinte tempo que presentan as GAN, en xeral, e a implementaci´on de Taymouri et al., en particular, neste TFG proponse a implementaci´on dunha nova arquitectura baseada no paradigma das GAN condicionais (Conditional GAN, CGAN, en ingl´es). Esta arquitectura am´osase na Figura 4.4. Figura 4.4: Estrutura dunha GAN Condicional. A arquitectura CGAN mant´en a estrutura b´asica das GAN (Vanilla GAN ), pero engade un vector de condici´on como entrada tanto ao xerador coma ao discriminador. Por medio deste vector ´e posible proporcionar informaci´on adicional 4.2. DESE ˜ NO DA ARQUITECTURA 29 que axude, por unha parte, ao xerador a obter novos datos m´ais precisos, xa que disp´on dunha condici´on que aporta informaci´on do contexto no que se realiza a predici´on; e, por outra, ao discriminador para realizar os seus veredictos. No caso da CGAN para predici´on do seguinte tempo, este vector de condici´on ´e o prefixo, que cont´en esa informaci´on contextual, na que se asume que unha predici´on depende da execuci´on das actividades previas. Por suposto, seguindo o paradigma das GAN, o xerador tam´en recibe como entrada un vector de ru´ıdo, que se deber´a combinar co prefixo para facilitar a obtenci´on de mellores predici´ons. O tratamento especial que recibe este vector de condici´on dentro de cada unha das redes detallarase a continuaci´on, ao afondar na estrutura interna tanto do xerador coma do discriminador na implementaci´on proposta. 4.2.2.1. Rede do xerador CGAN Tal e como ocorre nunha GAN cl´asica, o xerador do sistema ´e o encargado de xerar novos datos que, no noso problema, corresp´ondense coa predici´on do seguinte tempo. Para levar a cabo esta tarefa, en cada execuci´on a rede recibe como entradas ovector de ru´ıdo propio das GAN e o vector de condici´on que aporta como novidade a arquitectura CGAN. Por unha parte, o vector de condici´on cr´ease en cada iteraci´on por un dos prefixos preparados durante a etapa do preprocesamento dos datos. Este prefixo proporciona a informaci´on sobre as actividades previas (en formato one-hot) e os seus tempos asociados (a diferenza entre os timestamp de cada par de actividades). Por outra banda, o vector de ru´ıdo ax´ustase previamente para seguir a mesma estrutura dos prefixos. Para obter o equivalente ao identificador da actividade, mostr´ease un n´umero enteiro seguindo unha distribuci´on de probabilidade uniforme no rango comprendido entre o m´ınimo e o m´aximo dos identificadores do conxunto de datos (ambos inclusive). A continuaci´on, este valor codif´ıcase nun vector one-hot da mesma forma que ocorre cos prefixos. Para o valor do timestamp, x´erase un n´umero real aleatorio comprendido entre o valor de tempo m´ais pequeno e o m´ais grande dos existentes na partici´on de adestramento, axust´andose as´ı ao mesmo espazo de valores. O feito de escollelos nesta partici´on e non no conxunto global dos datos d´ebese a que este ´e o ´unico conxunto que a rede co˜nece durante o seu adestramento e, polo tanto, o ´unico en base ao cal se poden facer as suposici´ons. De ter collido un m´ınimo e un m´aximo ubicados noutra partici´on estar´ıase proporcionando ´a rede informaci´on que deber´ıa ver por primeira vez na etapa de validaci´on ou test, e non no adestramento. As´ı pois, en certa medida, dita validaci´on estar´ıa adulterada no momento da s´ua realizaci´on. O vector de condici´on e o vector de ru´ıdo concat´enanse xerando un vector m´ais longo que o orixinal (concretamente, o dobre de longo) no que algunha das s´uas compo˜nentes se corresponden con actividades reais e outros con valores aleatorios. Con isto, mantense o sentido da inclusi´on do ru´ıdo nas GAN orixinais para a xeraci´on dunha variedade m´ais ampla de novos datos, pero ap´ortase tam´en 36 CAP´ ITULO 4. METODOLOX´ IA Algoritmo 5 Validaci´on da rede Funci´on validacion(particion validacion): vector diffs ←vector() para cada mini batch en particion validacion facer condicion ←obterPrefixos(mini batch) y real ←obterGroundTruth(mini batch) ruido ←obterRuido() y fake ←Xerador(condicion,ruido) diff ← |y real −y fake| engadirAVector(vector diffs,diff) fin mae ←calcularMAE(vector diffs) return mae Cap´ıtulo 5 Probas A continuaci´on, descr´ıbense as probas realizadas sobre a implementaci´on da soluci´on proposta. A finalidade principal destas probas ´e comparar esta soluci´on coa aproximaci´on de referencia en monitorizaci´on predictiva [8], co obxectivo de validar que o uso dunha arquitectura baseada no paradigma CGAN permite obter mellores resultados. 5.1. Optimizaci´on dos hiperpar´ametros Para lograr minimizar o erro cometido nas predici´ons real´ızase unha optimizaci´on dos hiperpar´ametros da arquitectura, mencionados ao longo deste documento, os cales se mostran agrupados no Cadro 5.1. Con isto pers´eguese obter a combinaci´on m´ais axeitada entre os valores de cada un, coa cal se obte˜nen os mellores resultados. Para levar a cabo esta optimizaci´on empregouse a librer´ıa Tune [27], comentada no cap´ıtulo 3. Esta librer´ıa permite automatizar as execuci´ons da arquitectura cos distintos valores empregados para cada hiperpar´ametro, axilizando este proceso. En concreto, os valores utilizados m´ostranse no Cadro 5.2. Hiperpar´ametro Descripci´on batch size Tama˜no dos mini-batches. N´umero de prefixos inclu´ıdos en cada mini-batch prefix size Lonxitude dos prefixos. N´umero de rexistros inclu´ıdos en cada prefixo gen hidden size N´umero de neuronas da capa LSTM do Xerador disc hidden size N´umero de neuronas da capa LSTM do Discriminador Cadro 5.1: Hiperpar´ametros da arquitectura proposta. 37 38 CAP´ ITULO 5. PROBAS Hiperpar´ametro Valores batch size 3, 5, 7, 10 prefix size 2, 3, 4, 5 gen hidden size 4, 8, 16, 32 disc hidden size 4, 8, 16, 32 Cadro 5.2: Valores probados para cada hiperpar´ametro. Na selecci´on do rango de valores a probar para o tama˜no do mini-batch partiuse do valor inicial 5, empregado en [8]. Arredor deste valor extendeuse o rango para abranguer n´umeros menores (3) e maiores (7 e 10) e as´ı ver a influencia de empregar un tama˜no menor ou maior, o que implica axustar os pesos da rede m´ais ou menos a mi´udo respectivamente. Para o tama˜no do prefixo tomouse inicialmente o valor 4, empregado tam´en en [8]. Para a proba con valores menores baixouse o rango ata 2, exclu´ındo o 1 por considerarse unha situaci´on que aporta moi pouca informaci´on ´as redes para realizar as s´uas predici´ons. Por contra, nos valores maiores p´uxose o l´ımite en 5, tomando como referencia a lonxitude media dos casos en todos os conxuntos de datos (Cadro 3.1). Nos casos do n´umero de neuronas na capa LSTM optouse por empregar os mesmos valores tanto no xerador coma no discriminador. Para poder realizar o adestramento de forma m´ais optimizada na GPU escoll´eronse potencias de 2, empezando en 4 e finalizando en 32. O motivo de empezar en 4 d´ebese a que a presenza de menos neuronas pode facer que os c´alculos sexan excesivamente inexactos. Por contra, o l´ımite superior fixouse en 32 evitando valores maiores que poder´ıan chegar a saturar a memoria dos equipos empregados. As probas execut´aronse para todos os conxuntos de datos mencionados no cap´ıtulo 3, fixando en todos os casos un valor de 50 ´epocas para o adestramento, seleccionando sempre o estado da rede na ´epoca na que obtivo mellor efectividade. Para medir esta efectividade, empregouse a m´etrica MAE sobre a partici´on de validaci´on ao final da execuci´on de cada ´epoca. En todos os conxuntos de datos os resultados obtidos reflectiron a mesma situaci´on, ilustrada na Figura 5.1 para o caso concreto dos datasets Sepsis eBPI 2012 Complete. Esta figura amosa como todas as combinaci´ons executadas (as distintas li˜nas de cores na gr´afica) converxen nun mesmo punto, no cal o MAE acada o seu m´ınimo. A´ında que algunhas tardan m´ais en chegar a este punto, en todos os casos a converxencia l´ograse entre as ´epocas 10 e 20, momento a partir do cal o adestramento non produce melloras perceptibles na eficacia das predici´ons. As´ı pois, tras as 50 ´epocas de adestramento prefixadas, obs´ervase que con calquera dos valores escollidos para os hiperpar´ametros obtense un resultado practicamente id´entico. 5.1. OPTIMIZACI ´ ON DOS 39 (a) Dataset Sepsis (b) Dataset BPI 2012 Complete Figura 5.1: Evoluci´on do MAE durante a validaci´on cos distintos valores dos hiperpar´ametros. Os resultados acadados nestas probas reflicten que a arquitectura CGAN ´e capaz de chegar ao mellor resultado posible independentemente dos hiperpar´ametros empregados, por medio do adestramento nun n´umero de ´epocas relativamente baixo. Deste xeito, a selecci´on duns valores ou outros parece resultar irrelevante para a obtenci´on do m´ınimo MAE. Ante esta situaci´on, os valores finalmente escollidos son os amosados no Cadro 5.3. No caso do tama˜no dos mini-lotes e da lonxitude dos prefixos s´eguense os valores empregados na aproximaci´on de Taymouri et al. (5 e 4 respectivamente), mentres que para o n´umero de neuronas da capa LSTM, tanto no Xerador coma no Discriminador, escolleuse o 8 por ser un dos valores intermedios propostos, supo˜nendo un consumo de memoria menor que a outra opci´on intermedia (16). 40 CAP´ ITULO 5. PROBAS Hiperpar´ametro Valor batch size 5 prefix size 4 gen hidden size 8 disc hidden size 8 Cadro 5.3: Valores finalmente empregados para cada hiperpar´ametro. 5.2. Comparativa coa proposta de referencia Como se comentou ao longo deste traballo, para realizar a validaci´on final da implementaci´on proposta segu´ıronse as directrices marcadas en [21]. Entre estas directrices at´opanse os conxuntos de datos a empregar (presentados no cap´ıtulo 3), o esquema de particionado utilizado (desenvolto no apartado 4.1), e a m´etrica coa que computar o erro cometido nas predici´ons (tam´en explicada no cap´ıtulo 3). O seguimento destas indicaci´ons asegura poder realizar unha comparativa xusta entre os resultados obtidos pola soluci´on proposta e os que se acadan na aproximaci´on de referencia presentada en [8]. Por unha banda, para a execuci´on da arquitectura proposta, que xa se implementou seguindo estas directrices, fix´aronse os valores dos hiperpar´ametros mencionados no apartado anterior (Cadro 5.3). Por outra, para o caso da proposta de Taymouri et al. foi preciso realizar unha adaptaci´on no c´odigo orixinal para permitir que esta traballase co mesmo esquema de particionado. No caso da m´etrica non foi preciso realizar ningunha modificaci´on xa que os autores empregan o MAE para medir o erro. Ambas aproximaci´ons foron executadas para todos os conxuntos de datos, obtendo para cada un os valores mostrados no Cadro 5.4. Helpdesk BPI 2012 BPI 2012 Comp. BPI 2012 W BPI 2012 W Comp. BPI 2012 O BPI 2012 A BPI 2013 c.p. BPI 2013 Inc. Sepsis Env permit Taymouri 7.928 0.395 2.881 1.878 2.568 2.703 2.599 12.940 2.174 2.844 5.451 Gamallo 8.107 0.376 0.596 0.595 1.365 1.936 1.047 4.511 0.741 1.048 0.297 Cadro 5.4: Comparativa da soluci´on proposta coa aproximaci´on de referencia na predici´on do seguinte tempo. Estes valores representan o MAE obtido en cada caso na validaci´on final, realizada sobre a partici´on de test co mellor modelo obtido durante o adestramento (o 5.2. COMPARATIVA COA PROPOSTA DE REFERENCIA 41 que obtivo mellores resultados durante a validaci´on ao final de cada ´epoca). Neste cadro, a implementaci´on propia deste TFG identif´ıcase baixo o nome de Gamallo. En negri˜na m´arcase a mellor aproximaci´on para cada conxunto de datos. Outro dos aspectos que se compararon por medio da execuci´on de ambas aproximaci´ons foi a evoluci´on tanto do erro do discriminador como do erro do xerador ao longo das ´epocas de adestramento. As Figuras 5.2, 5.3, 5.4, 5.5 e 5.6 ilustran os resultados desta comparativa para os conxuntos de datos Helpdesk,BPI 2012, Sepsis Env. permit eBPI 2012 w, respectivamente. Estas gr´aficas son extensibles ao resto de conxuntos de datos, onde a evoluci´on en ambas aproximaci´ons ´e moi similar. (a) Implementaci´on propia (b) Implementaci´on de Taymouri Figura 5.2: Evoluci´on do erro para o conxunto de datos Helpdesk. (a) Implementaci´on propia (b) Implementaci´on de Taymouri Figura 5.3: Evoluci´on do erro para o conxunto de datos BPI 2012. 42 CAP´ ITULO 5. PROBAS (a) Implementaci´on propia (b) Implementaci´on de Taymouri Figura 5.4: Evoluci´on do erro para o conxunto de datos Sepsis. (a) Implementaci´on propia (b) Implementaci´on de Taymouri Figura 5.5: Evoluci´on do erro para o conxunto de datos Env. permit. (a) Implementaci´on propia (b) Implementaci´on de Taymouri Figura 5.6: Evoluci´on do erro para o conxunto de datos BPI 2012 w. Cap´ıtulo 6 Discusi´on dos resultados Nos resultados obtidos na comparativa coa proposta de referencia (Cadro 5.1) pode verse como en practicamente todos os casos (10 dos 11 conxuntos de datos empregados) a soluci´on implementada neste TFG obt´en os mellores resultados. No ´unico conxunto de datos no que os resultados non son mellores (Helpdesk), o MAE obtido ´e moi cercano ao acadado pola aproximaci´on de Taymouri. Estes resultados parecen confirmar certos problemas na adaptaci´on da GAN proposta por Taymouri et al. que son solucionados coa arquitectura CGAN implementada. Entre estes problemas destaca a concatenaci´on que se realiza entre o prefixo e o valor predito polo xerador para conformar a entrada do discriminador (v´exase de novo a Figura 4.3). Con isto, o discriminador recibe secuencias moi similares, unicamente diferenciadas no ´ultimo elemento, coas que non ´e capaz de distinguir correctamente cal ´e o caso real e cal o xerado; obtendo as´ı un grao de acerto non demasiado elevado, que condiciona ao mesmo tempo o adestramento do xerador. Os resultados obtidos demostran que esta situaci´on prod´ucedese de forma acrecentada naqueles conxuntos de datos cun menor n´umero de rexistros, como BPI 2013 closed problems ou Env. permit, nos que a diferenza entre os valores do MAE obtido son maiores. Isto expl´ıcase polo feito de que a rede require un maior adestramento para chegar a centrarse exclusivamente no ´ultimo elemento da secuencia ´a hora de determinar se a entrada ´e real ou xerada, e non nos elementos previos, os cales son sempre reais ao proceder do prefixo. Nos conxuntos de datos con menor n´umero de eventos o adestramento ´e menor e prod´ucese esta circustancia. Por contra, na CGAN tanto o prefixo coma o seguinte tempo conforman entradas diferenciadas, ao facer uso do vector de condici´on, d´andolle as´ı a importancia necesaria ao propio valor do seguinte tempo. Por outra banda, outro dos aspectos que pode condicionar os resultados obtidos pola proposta de Taymouri et al. ´e o adestramento empregado. Como xa se explicou no apartado 4.2.1, na arquitectura proposta os autores modifican o adestramento orixinal dos sistemas GAN, inclu´ındo no adestramento do xerador non s´o o erro da predici´on do discriminador, sen´on tam´en o erro da predici´on do seguinte tempo feita polo propio xerador. Deste xeito, mest´uranse dous erros de naturezas completamente 43 44 CAP´ ITULO 6. DISCUSI ´ ON DOS RESULTADOS distintas: un ´e a diferenza entre un valor acoutado entre 0 e 1, mentres que o outro ´e a diferenza entre dous valores reais que poden ser arbitrariamente grandes. Traballar con estos erros tan diferentes parece dificultar o correcto progreso do adestramento. En contraste, na CGAN implementada empr´egase o adestramento com´un das redes GAN (cuxa efectividade quedou demostrada na literatura existente), obtendo as´ı finalmente mellores resultados. O efecto destes distintos adestramentos empregados pode verse nas curvas de evoluci´on dos erros do discriminador e do xerador (Figuras 5.2, 5.3, 5.4, 5.5 e 5.6). Na CGAN proposta, tanto o erro do discriminador como o erro do xerador tenden a converxer segundo avanza o adestramento, chegando ao punto no que ningunha das d´uas redes ´e capaz de sobrepo˜nerse, acadando as´ı o equilibrio Nash. Ademais, durante este proceso, o empeoramento do erro dunha das redes tende a coincidir coa mellora da outra, amosando as´ı a competencia que definen as GAN (esto vese especialmente ben nas Figura 5.2a e 5.5a). Por contra, na aproximaci´on de Taymouri et al. os erros non converxen, chegando incluso a separarse notablemente (como no caso da Figura 5.6b). Este comportamento amosa o inestable que se volve o adestramento coas modificaci´ons introducidas polos autores. Ademais, cabe destacar que os resultados obtidos avalan o preprocesamento dos datos realizado na soluci´on proposta neste TFG. Se ben este preprocesamento ´e, en termos xerais, similar ao realizado por Taymouri et al., as grandes diferenzas residen na normalizaci´on realizada sobre os valores temporais e na inclusi´on do padding na xeraci´on dos prefixos. Mentres que na proposta de referencia de Taymouri et al. non se realiza ning´un tipo de normalizaci´on, neste taballo empregouse a normalizaci´on min-max para reducir as posibles grandes diferenzas entre os distintos valores. Ademais, coa inclusi´on do padding cons´eguense xerar m´ais prefixos, obtendo m´ais datos para realizar un adestramento m´ais completo, que deriva directamente nun maior acerto nas predici´ons finais da arquitectura. Consecuentemente, p´odese afirmar que ´e un acerto o emprego destas t´ecnicas no preprocesamento dos datos. En resumo, a arquitectura CGAN proposta, centrada en respectar fielmente os principios dos sistemas GAN, mellora de xeito significativo os resultados da implementaci´on proposta por Taymouri et al. Cap´ıtulo 7 Conclusi´ons e posibles ampliaci´ons Neste traballo presentouse unha arquitectura baseada nunha variante da GAN orixinal, a Conditional GAN, para resolver o problema da predici´on do seguinte tempo propio do campo da monitorizaci´on preditiva. Para a implementaci´on desta soluci´on empregouse como referencia a proposta publicada por Taymouri et al., o ´unico exemplo existente do uso de GAN neste ´ambito, a´ında que con sustanciais modificaci´ons sobre o esquema orixinal deste tipo de arquitecturas. Por medio dun completo preprocesamento dos datos de entrada e dun dese˜no simple pero eficaz tanto do xerador coma do discriminador, baseados en redes recurrentes, obtiv´eronse os compo˜nentes necesarios para, seguindo o adestramento propio das redes GAN, acadar un modelo capaz de realizar as predici´ons correspondentes. Ademais, analiz´aronse cales eran os mellores valores dos hiperpar´ametros da arquitectura, comprobando que con calquera combinaci´on das probadas a rede era capaz de adestrar ata chegar ao mesmo punto de acerto. Para obter unha comparativa xusta da soluci´on proposta con respecto da aproximaci´on de Taymouri et al. segu´ıronse as indicaci´ons da publicaci´on de RamaManeiro. Tras adaptar a soluci´on de Taymouri et al. coas directrices de dita publicaci´on, os resultados obtidos da comparativa amosaron como a arquitectura CGAN obt´en de xeito xeral rendementos notablemente maiores, realizando predici´ons m´ais acertadas. Desta forma, p´odese afirmar que esta proposta, baseada nos principios das GAN, sup´on unha mellor soluci´on que as variaci´ons propostas por dito autor. Sobre esta soluci´on, futuros traballos poden tratar de extender as predici´ons abordadas a outras t´ıpicas da monitorizaci´on preditiva coma a predici´on do tempo restante ata a finalizaci´on do caso. Igualmente, p´odese tratar de integrar ambas soluci´ons analizadas na comparativa desenvolta por Rama-Maneiro et al., comparando os resultados obtidos cos acadados polas propostas do estado de co˜necemento en monitorizaci´on preditiva. Por outra banda, a´ında que a an´alise dos valores dos hiperpar´ametros resultou moi conclu´ınte, pode extenderse o proceso 45 52 AP´ ENDICE A. MANUAL DE USUARIO # Crear o novo entorno con python 3.8 (base )$> conda create -n tfg_pedro python =3.8 # Activar o entorno creado (base )$> conda activate tfg_pedro # Instalar os paquetes necesarios ( tfg_pedro )$> pip install torch ==1.7.1 torchvision ==0.8.2 torchaudio ==0.7.2 # O anterior instala tamen numpy -1.21.0 ( tfg_pedro )$> pip install pandas ==1.2.3 ( tfg_pedro )$> pip install tqdm ( tfg_pedro )$> pip install wandb ( tfg_pedro )$> pip install ray [tune ] Estrutura de directorios Os distintos directorios que compo˜nen o proxecto son os seguintes: dataset: Cont´en os arquivos .csv dos datasets. doc: Cont´en o artigo de referencia empregado e a explicaci´on da creaci´on do entorno. src: Cont´en o c´odigo fonto da implementaci´on (ficheiros .py). Execuci´on do proxecto A rede pode executarse por medio do seguinte comando (estando situados no directorio src): ( tfg_pedro )$> python main . py -- dataset ../ dataset / SEPSIS .csv Os par´ametros posibles son: dataset: Conxunto de datos a empregar. Debe especificarse a ruta completa, non s´o o nome do dataset. optimizer params: Par´ametro optativo. Eng´adese s´o para realizar a optimizaci´on dos hiperpar´ametros. Exec´utase escribindo unicamente --optimizer params sen ning´un valor acompa˜n´andoo. api key: Par´ametro optativo. Eng´adese s´o para realizar a monitorizaci´on da execuci´on por medio da librer´ıa wandb. Acomp´a˜nase coa chave de usuario correspondente no portal web de WandB. Glosario caso Secuencia ordenada de todos os eventos rexistrados nunha determinada execuci´on do proceso de negocio. 3–5, 11, 13, 17, 21–24, 38, 53 evento Rexistro da execuci´on dunha actividade nun determinado momento e dentro dun caso concreto. 3, 4, 7, 14, 17, 21–24, 26 hiperpar´ametro Cada un dos par´ametros axustables que permiten controlar o proceso de adestramento da rede neuronal. 7, 9, 11, 20, 24, 30, 32, 37–40, 45 neurona Cada unha das celas que compo˜nen unha rede neuronal artificial. A neurona representa unha abstracci´on dos c´alculos matem´aticos executados nun determinado punto da rede neuronal. 6–9, 12, 13, 19, 30, 32, 38, 39, 53 peso Cada un dos valores num´ericos, variables, empregados nos c´alculos internos realizados dentro de cada neurona. 6, 7, 12, 18–20, 26, 34, 35 prefixo Secuencia ordenada de actividades executadas previamente a un evento determinado nunha instancia dun proceso de negocio. 4, 7, 9, 13, 16, 21, 23–27, 29, 31–35, 38, 39, 43 ru´ıdo Conxunto de valores xerados aleatoriamente, sen ningunha relaci´on aparente entre eles. 15, 16, 27, 29, 30, 34, 35 sufixo Secuencia ordenada de actividades executadas posteriormente a un evento determinado nunha instancia dun proceso de negocio. 4 53 54 Glosario Siglas BPMN Business Process Model and Notation. 1, 3, 9 CGAN Conditional GAN . 7, 16, 21, 26, 28, 29, 32, 33, 37, 39, 43–45 GAN Generative Adversarial Network. 7–9, 11, 14–16, 24, 26–29, 32, 43–45 GPU Graphics Processing Unit. 19, 38 GRU Gated Recurrent Unit. 8 LSTM Long Short-Time Memory. 8, 9, 12–16, 21, 30–33, 38, 39 LTL Linear Temporal Logic. 14 MAE Mean Absolute Error. 7, 9, 17, 18, 35, 38–40, 43 MANN Memory Augmented Neural Network. 8, 14 RNN Recurrent Neural Network. 7, 12, 14 TFG Traballo de Fin de Grao. 5, 7, 8, 11, 16, 17, 20, 21, 28, 41, 43, 44 55