ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

TSELM

•
•
Umberto Manganiello
Umberto Manganiello

Effort estimation: un approccio basato su Extreme Learning Machine e Tabu Search

1 of 18
Download to read offline
UNIVERSITÀ DEGLI STUDI DI SALERNO Facoltà di Scienze Matematiche Fisiche e Naturali Corso di Laurea Magistrale in Informatica Effort estimation: un approccio basato su Extreme Learning Machine e Tabu Search Relatori: Prof.ssa Filomena Ferrucci Dott.sa Federica Sarro AA 2011/2012 Candidato: Umberto Manganiello Matr. 0522500033 1
Software development effort estimation • Stima dell’effort necessario per la realizzazione di un progetto software • Fondamentale per il successo di un progetto AA 2011/2012 2
Software development effort estimation Dimensione stimata + Predizione dell’effort Effort stimato Indici di costo Costruzione del modello Conoscenza ottenuta da progetti passati AA 2011/2012 3
Software development effort estimation Tecniche di software effort estimation o Expert estimation • “È facile stimare ciò che si conosce, è difficile stimare ciò che non si conosce, ma è ancora più difficile stimare ciò che non si sa di non conoscere“ o Tecniche algoritmiche AA 2011/2012 4
Extreme learning machine (ELM) • Tecnica di intelligenza artificiale basata su reti neurali • Variante di single layer feed-forward network (SLFN) AA 2011/2012 5
Extreme learning machine (ELM) Vantaggi di ELM o Velocità! • “[…] ELM may learn faster than SVM by a factor up to thousands […] “ Extreme learning machine: Theory and applications G.-B. Huang et al. /Neurocomputing 70 (2006) p.499 AA 2011/2012 6
ELM per software effort estimation • ELM mai usata per effort estimation • Obiettivo dello studio: o Verificare l’applicabilità della tecnica in tale ambito, confrontandone l’accuratezza con altre tecniche di machine learning AA 2011/2012 7
Setting dei parametri : Tabu Search • Parametri di ELM o Kernel lineare: c o Kernel RBF: c, k • Settare correttamente i parametri della tecnica è cruciale! o Non esistono valori universalmente validi o Non esistono linee guida generali E’ necessario un meccanismo di ricerca AA 2011/2012 8
Setting dei parametri : Tabu Search Meta-euristica o Metodologia di risoluzione di un problema di ottimizzazione o Approccio generale, applicabile in vari contesti o Permette di ottenere soluzioni sub-ottime, in tempi ragionevolmente brevi AA 2011/2012 9
Setting dei parametri : Tabu Search La meta-euristica Tabu Search o Cerca di risolvere il problema dei minimi locali permettendo mosse peggioranti o Introduce il concetto di tabu list: • In tabu list vengono salvate anche le soluzioni correnti, per evitare di ripetere le stesse mosse o E’ possibile specificare un criterio per cui anche una mossa in tabu list può essere selezionata come soluzione (aspiration criterion) AA 2011/2012 10
Algoritmo di Tabu Search Genera la lista delle soluzioni candidate (mosse) Soluzione iniziale No Aggiorna Tabu List Le condizioni di arresto sono verificate? Sì Valuta le soluzioni Seleziona la migliore soluzione trovata che non sia in tabu list, a meno che non soddisfi il criterio di aspirazione Soluzione finale AA 2011/2012 11
Configurazione di Tabu Search per ELM • Rappresentazione della soluzione o X = [c, k] • Scelta della soluzione iniziale é -24 ê o c e k scelti randomicamente in ë2 , 2 ù ú û 25 [G.-B. Huang et al - Extreme Learning Machine for regression and multiclass classification P.524] • Criterio d’arresto o 100 iterazioni • Numero di mosse per iterazione o 25 • Criterio di aspirazione o Se la soluzione migliora la funzione obiettivo più di ogni altra soluzione esplorata, allora viene rimossa dalla Tabu List. • Tabu List o Soluzione corrente in Tabu List o Soluzioni che differiscono meno del 10% da una qualsiasi soluzione in Tabu List AA 2011/2012 12
Configurazione di Tabu Search per ELM – Funzione obiettivo • L’algoritmo è stato ottimizzato su due funzioni obiettivo. 1. SSR(Sum of Squared Residuals) n n SSR = åui = å( y - f i i=1 i=1 o MRE (Magnitude of relative error) o EMRE(Estimate magnitude of relative error) MRE = EMRE  2 ( xi )) 2 ActualEffort - EstimatedEffort ActualEffort ActualEffort  EstimatedEffort EstimatedEffort o MMRE (Mean MRE), MEMRE (Mean EMRE) • Ottenuti calcolando la media rispettivamente di MRE e EMRE su tutte le osservazioni 2. avg(MEMRE, MMRE) AA 2011/2012 13
Configurazione di Tabu Search per ELM – Le mosse Ad ogni iterazione, vengono ottenute 25 soluzioni applicando altrettante mosse nel modo seguente: o Si sceglie a caso uno dei parametri (c, k) da modificare o Il parametro selezionato: • Nell’80% dei casi viene incrementato o decrementato al più del suo 20%. Questo per favorire l’esplorazione di soluzioni vicine a quella corrente • Nel restante 20% dei casi viene generato randomicamente é ù ë û nell’intervallo ê2 , 2 ú -24 AA 2011/2012 25 14
Esecuzione della tecnica • TSELM è non deterministico o Media su 30 Run • Dataset utilizzati o PROMISE: Dati single-company o cross-company • Metodo di validazione o > 60 osservazioni • 10-fold cross validation • Trade-off tra accuratezza e velocità della validazione o < 60 osservazioni • Leave-one-out cross validation AA 2011/2012 15
Valutazione dei risultati • Abs residuals o abs_res = ActualEffort - EstimatedEffort • Confrontati per determinare eventuali miglioramenti significativi o Wilcoxon Signed Rank Test AA 2011/2012 16
Risultati ottenuti e conclusioni • TS+EL significativamente migliore di EL • TS+EL significativamente migliore, nel 97% dei casi, di: o o o o o o o Grid Search SVR default Weka Mean Effort Median Effort MSWR CBR CBRss Extreme Learning Machine valida alternativa sia in termini di accuratezza che di efficienza AA 2011/2012 17
Grazie per l’attenzione! AA 2011/2012 18

More Related Content

TSELM

  • 1. UNIVERSITÀ DEGLI STUDI DI SALERNO Facoltà di Scienze Matematiche Fisiche e Naturali Corso di Laurea Magistrale in Informatica Effort estimation: un approccio basato su Extreme Learning Machine e Tabu Search Relatori: Prof.ssa Filomena Ferrucci Dott.sa Federica Sarro AA 2011/2012 Candidato: Umberto Manganiello Matr. 0522500033 1
  • 2. Software development effort estimation • Stima dell’effort necessario per la realizzazione di un progetto software • Fondamentale per il successo di un progetto AA 2011/2012 2
  • 3. Software development effort estimation Dimensione stimata + Predizione dell’effort Effort stimato Indici di costo Costruzione del modello Conoscenza ottenuta da progetti passati AA 2011/2012 3
  • 4. Software development effort estimation Tecniche di software effort estimation o Expert estimation • “È facile stimare ciò che si conosce, è difficile stimare ciò che non si conosce, ma è ancora più difficile stimare ciò che non si sa di non conoscere“ o Tecniche algoritmiche AA 2011/2012 4
  • 5. Extreme learning machine (ELM) • Tecnica di intelligenza artificiale basata su reti neurali • Variante di single layer feed-forward network (SLFN) AA 2011/2012 5
  • 6. Extreme learning machine (ELM) Vantaggi di ELM o Velocità! • “[…] ELM may learn faster than SVM by a factor up to thousands […] “ Extreme learning machine: Theory and applications G.-B. Huang et al. /Neurocomputing 70 (2006) p.499 AA 2011/2012 6
  • 7. ELM per software effort estimation • ELM mai usata per effort estimation • Obiettivo dello studio: o Verificare l’applicabilità della tecnica in tale ambito, confrontandone l’accuratezza con altre tecniche di machine learning AA 2011/2012 7
  • 8. Setting dei parametri : Tabu Search • Parametri di ELM o Kernel lineare: c o Kernel RBF: c, k • Settare correttamente i parametri della tecnica è cruciale! o Non esistono valori universalmente validi o Non esistono linee guida generali E’ necessario un meccanismo di ricerca AA 2011/2012 8
  • 9. Setting dei parametri : Tabu Search Meta-euristica o Metodologia di risoluzione di un problema di ottimizzazione o Approccio generale, applicabile in vari contesti o Permette di ottenere soluzioni sub-ottime, in tempi ragionevolmente brevi AA 2011/2012 9
  • 10. Setting dei parametri : Tabu Search La meta-euristica Tabu Search o Cerca di risolvere il problema dei minimi locali permettendo mosse peggioranti o Introduce il concetto di tabu list: • In tabu list vengono salvate anche le soluzioni correnti, per evitare di ripetere le stesse mosse o E’ possibile specificare un criterio per cui anche una mossa in tabu list può essere selezionata come soluzione (aspiration criterion) AA 2011/2012 10
  • 11. Algoritmo di Tabu Search Genera la lista delle soluzioni candidate (mosse) Soluzione iniziale No Aggiorna Tabu List Le condizioni di arresto sono verificate? Sì Valuta le soluzioni Seleziona la migliore soluzione trovata che non sia in tabu list, a meno che non soddisfi il criterio di aspirazione Soluzione finale AA 2011/2012 11
  • 12. Configurazione di Tabu Search per ELM • Rappresentazione della soluzione o X = [c, k] • Scelta della soluzione iniziale é -24 ê o c e k scelti randomicamente in ë2 , 2 ù ú û 25 [G.-B. Huang et al - Extreme Learning Machine for regression and multiclass classification P.524] • Criterio d’arresto o 100 iterazioni • Numero di mosse per iterazione o 25 • Criterio di aspirazione o Se la soluzione migliora la funzione obiettivo più di ogni altra soluzione esplorata, allora viene rimossa dalla Tabu List. • Tabu List o Soluzione corrente in Tabu List o Soluzioni che differiscono meno del 10% da una qualsiasi soluzione in Tabu List AA 2011/2012 12
  • 13. Configurazione di Tabu Search per ELM – Funzione obiettivo • L’algoritmo è stato ottimizzato su due funzioni obiettivo. 1. SSR(Sum of Squared Residuals) n n SSR = Ã¥ui = Ã¥( y - f i i=1 i=1 o MRE (Magnitude of relative error) o EMRE(Estimate magnitude of relative error) MRE = EMRE  2 ( xi )) 2 ActualEffort - EstimatedEffort ActualEffort ActualEffort  EstimatedEffort EstimatedEffort o MMRE (Mean MRE), MEMRE (Mean EMRE) • Ottenuti calcolando la media rispettivamente di MRE e EMRE su tutte le osservazioni 2. avg(MEMRE, MMRE) AA 2011/2012 13
  • 14. Configurazione di Tabu Search per ELM – Le mosse Ad ogni iterazione, vengono ottenute 25 soluzioni applicando altrettante mosse nel modo seguente: o Si sceglie a caso uno dei parametri (c, k) da modificare o Il parametro selezionato: • Nell’80% dei casi viene incrementato o decrementato al più del suo 20%. Questo per favorire l’esplorazione di soluzioni vicine a quella corrente • Nel restante 20% dei casi viene generato randomicamente é ù ë û nell’intervallo ê2 , 2 ú -24 AA 2011/2012 25 14
  • 15. Esecuzione della tecnica • TSELM è non deterministico o Media su 30 Run • Dataset utilizzati o PROMISE: Dati single-company o cross-company • Metodo di validazione o > 60 osservazioni • 10-fold cross validation • Trade-off tra accuratezza e velocità della validazione o < 60 osservazioni • Leave-one-out cross validation AA 2011/2012 15
  • 16. Valutazione dei risultati • Abs residuals o abs_res = ActualEffort - EstimatedEffort • Confrontati per determinare eventuali miglioramenti significativi o Wilcoxon Signed Rank Test AA 2011/2012 16
  • 17. Risultati ottenuti e conclusioni • TS+EL significativamente migliore di EL • TS+EL significativamente migliore, nel 97% dei casi, di: o o o o o o o Grid Search SVR default Weka Mean Effort Median Effort MSWR CBR CBRss Extreme Learning Machine valida alternativa sia in termini di accuratezza che di efficienza AA 2011/2012 17