Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Per gli Studenti
Soft computing

Docente responsabile: Vanneschi Leonardo
 
PROGRAMMA

Obiettivi e contenuti:

Il corso ha come obiettivo principale quello di introdurre gli studenti alla conoscenza di metodologie per la risoluzione di problemi complessi, note con il nome di Soft Computing. Tradizionalmente, queste metodologie si dividono in Algoritmi Evolutivi, Reti Neurali e Sistemi Fuzzy e sono accomunate dalla capacità di restituire soluzioni approssimate (nell'eventualità in cui non siano in grado di determinare una soluzione perfetta) e dalla peculiarità di saper trattare concetti quali imperfezione, imprecisione o incompletezza dell'informazione. In questo corso verranno anche trattate alcune tecniche non tradizionalmente riconducibili al settore del Soft Computing, ma ad esso strettamente correlate, come il Simulated Annealing, il Tabu Search, vari tipi di classificatori, come quelli ad apprendimento bayesiano, ecc. Tutte queste metodologie vengono anche tradizionalmente inserite nel più ampio settore del Machine Learning (o Apprendimento Artificiale) e quindi una parte consistente di questo corso verrà dedicata alla trattazione dei concetti fondamentali dell'apprendimento artificiale.

Programma:

1. Concetti introduttivi e motivazioni del corso

  • Problemi complessi ed NP-completi.
  • Definizione e concetti fondamentali del Machine Learning.
  • Definizione informale del termine Soft Computing.
  • Cenni sui domini applicativi del Soft Computing.

2. Spazi di Ricerca e Tecniche di Ottimizzazione

  • Problemi di Ottimizzazione Combinatoria e loro complessità.
  • No Free Lunch Theorem.
  • Ricerca Locale (Local Search o Hill Climbing).
  • Paesaggi di fitness, loro significato e importanza, loro struttura topologica.
  • Simulated Annealing
  • Definizioni generali e funzionamento.
  • Teoria del Simulated Annealing e suo comportamento asintotico.
  • Cenni al Tabu Search

3. Algoritmi Genetici

  • Cenni ai concetti di base della teoria dell'evoluzione di Darwin.
  • Operatori genetici.
  • Funzionamento generale dell'Algoritmo Genetico "standard" [Holland, 1975].
  • Genotipo e Fenotipo.
  • Il concetto di schema e la sua importanza nell'interpretazione del funzionamento degli Algoritmi Genetici.
  • Teorema degli Schemi.
  • Teoria dei Building Blocks.
  • Problema del k-Armed Bandit.
  • Comportamento asintotico degli Algoritmi Genetici.
  • Cromosoma diploide (modello di Bagley, primo e secondo modello di Hollstien-Holland).
  • Operatori di inversione e riordinamento (modelli di Bagley, Frantz).
  • Partially matched crossover, cycle crossover (Goldberg).
  • Ripartizione degli individui in specie:

-      fitness sharing (Goldberg).

-      riproduzione stretta (modelli di Hollstien e Brooker).

  • Ottimizzazione Multiobiettivo:

-      VEGA (Shaffer).

-      Modello di Baker.

  • Valutazione sperimentale delle prestazioni di un Algoritmo Genetico (funzioni di test di

Whitley).

4. Programmazione Genetica

  • Rappresentazione e principali differenze con gli Algoritmi Genetici.
  • Operatori Genetici.
  • Calcolo della Fitness.
  • Proprietà di Chiusura e Sufficienza.
  • Steady State.
  • Automatically Defined Functions (ADF).
  • GP Benchmarks (even parity, multiplexer, symbolic regression, artificial ant on the Santa Fe trail).
  • Problemi di ricerca ancora aperti in GP.
  • Difficoltà dei problemi in GP.

-  fitness distance correlation.

-  funzioni sintetiche (trap functions, royal trees).

  • Programmazione Genetica Parallela e Distribuita (definizioni e studio sperimentale).
  • Concetto di diversità di una popolazione e problema della convergenza prematura.
  • Concetto di bloat e metodi per combatterlo (PADGP; Tarpeian methods).
  • Cenni a altri tipi di Algoritmi Evolutivi:

-      Evolution Strategies.

-      Evolutionary Programming

 5. Ancora sul Machine Learning

  • Concetto di apprendimento. Apprendimento di una funzione.
  • Concetto di generalizzazione. Training set e test set.
  • Apprendimento supervisionato e non supervisionato.
  • Problemi di classificazione e clustering.
  • Prestazioni di un classificatore. Splitting dei dati. Crossvalidation e sue varianti. Precision e Recall. Veri positivi, falsi positivi, veri negativi e falsi negativi. F-measure. K-statistic.
  • Il concetto di feature. Feature selection.

6. Reti Neurali

  • Concetti introduttivi.
  • Perceptron:
  • Modello a un neurone
  • Perceptron Learning Rule.
  • Teorema di convergenza del Perceptron.
  • Cenni alle principali funzioni di attivazione.
  • Adaline:
  • Struttura generale
  • Delta rule. Concetto di discesa del gradiente.
  • Problemi linearmente separabili e non linearmente separabili.
  • Strati di neuroni nascosti.
  • Teorema dell'Approssimazione Universale.
  • Backpropagation
  • Reti Neurali cicliche o ricorsive:
  • Reti di Jordan
  • Reti di Elman
  • Reti di Hopfield (cocetto di memoria associativa, regola di apprendimento di Hebb).
  • Reti Neurali auto-organizzative
  • Reti ad apprendimento competitivo.
  • Reti di Kohonen o Self Organizing Maps (SOM).

Risultati di apprendimento previsti:

Le tecniche di Soft Computing vengono ormai da diversi anni utilizzate in numerosissimi settori applicativi, sia a livello accademico che industriale. Tra questi settori (elenco ben lontano dall'essere esaustivo), particolare interesse negli ultimi anni hanno assunto quelli della Biologia e della Bionformatica, della Robotica, dell'Ingegneria elettronica e meccanica, della Chimica, della Medicina, dell'Economia, del Marketing, della Sicurezza, ecc. La sola idea di coprire in maniera esauriente tutti questi settori applicativi in un solo corso sarebbe presuntuoso, prima ancora che irrealizzabile. Lo scopo del corso non è, quindi, quello di introdurre lo studente a particolari applicazioni, ma piuttosto quello di trasferire conoscenze sulle metodologie computazionali, in modo da fornire  gli strumenti per affrontare applicazioni in futuro. Quindi, i risultati di apprendimento attesi riguardano una semplicità nella formalizzazione e la gestione di problemi complessi più una conoscenza approfondita dei più noti metodi computazionali per la soluzione di tali problemi.

Prerequisiti:

Nessuna particolare competenza è propedeutica a questo corso, se non una conoscenza generale dei concetti fondamentali dell'Informatica (formalismi di programmazione e sviluppo software) e della Matematica di base, con particolare riferimento alle basi della Statistica.

Aims and contents

The goal of the course is introducing students to methods for solving complex problems, often globally known as Soft Computing. Traditionally, these methods can be partitioned in Evolutionary Algorithms (Holland, 1975; Goldberg, 1989), Neural Networks (Haykin, 1999) and Fuzzy Systems (Yager and Zadeh, 1994), and the two main features they all share are the ability of returning approximate solutions (in case they are not able to find a perfect one) to a problem and the ability of dealing with concepts such as imperfection, imprecision, and incomplete information. Other computational methods are also discussed in this course, like various forms of Local Search (like Hill Climbing (Aarts and Korst, 1998), Simulated Annealing (Kirkpatrick et al., 1983), Tabu Search (Glover and Laguna, 1997)) and Particle Swarm Optimization (Clerc, 2006), a new method for the optimization of continuous values inspired by the collective behavior of swarms (and belonging to the field of Swarm Intelligence). All the methods presented in this course are also traditionally classified as belonging to the wider field of Machine Learning (Mitchell, 1996). Thus an important part of this course is dedicated to introducing the fundations

of Machine Learning.

Program details

1 Introduction and Motivation

  • Complex problems and NP-hard problems.
  • Definition and foundations of Machine Learning.
  • Definition of Soft Computing.
  • Outline of typical Soft Computing applications.

2 Search Spaces and Optimization

  • Optimization Problems and their complexity. Are they hard? Why?
  • No Free Lunch Theorem.
  • Introduction to Local Search.
  • Hill Climbing.
  • Fitness Landscapes: their meaning and importance; their structure and topology.
  • Simulated Annealing
  • general definitions and functioning.
  • theory and asymptotic behavior.
  • Tabu Search
  • general definitions and functioning.
  • short term and long term memory.

3 Genetic Algorithms

  • Outline of the basic concepts of Darwinian Evolution Theory.
  • Genetic operators.
  • General functioning of a simple Genetic Algorithm (GA).
  • Genotype and phenotype.
  • Selection mechanisms.
  • The concept of Schema and its importance to understand the functioning of GAs.
  • Schema Theorem.
  • Building Blocks Theory.
  • k-Armed Bandit Problem and its binding with GAs.
  • Asymptotic behavior of GAs.
  • Advanced GAs concepts:
  • Diploid chromosome (Bagley model, first and second Hollstien-Holland models).
  • Inversion and reordering operators (Bagley model and Frantz model).
  • Partially matched crossover and cycle crossover (Goldberg).
  • Repartition of potential solutions (i.e. individuals) in species:
  • Fitness sharing (Goldberg)
  • Strict reproduction (model of Hollstien and model of Brooker)
  • Multiobjective optimization
  • VEGA (Shaffer)
  • The concepts of Pareto optimal set and Pareto front.
  • Model of Baker.
  • Experimental evaluation of the performance of a GA.
  • Whitley test functions as a possible set of benchmarks for experimental studies.
  • A general discussion of the possible applications.

4 Swarm Intelligence

In this part of the course, the following subjects will be discussed:

  • Introduction and motivation.
  • Outline of the biological metaphor: swarm behaviors.
  • Continuous optimization and real-valued parameters optimization.
  • Particle Swarm Optimization (PSO)
  • Basic (or "canonical") PSO version.
  • Possible extensions and their advantages and drawbacks.

5 Genetic Programming

  • Representation and main differences with GAs.
  • Genetic operators.
  • Fitness calculation methods.
  • Properties of Closure and Sufficiency.
  • The concept of Steady State.
  • Automatically Defined Functions (ADF).
  • Genetic Programming (GP) Benchmarks (even parity, multiplexer,symbolic regression, artificial ant on the Santa Fe trail).
  • Open Issues in GP.
  • Problem Difficulty in GP.
  • GP fitness landscapes.
  • Fitness distance correlation.
  • Synthetic functions (trap functions, royal trees).
  • Parallel and Distributed GP: definitions, most popular models (island model, cellular model, hybrid models) and experimental study.
  • The concept of diversity of a population and the problem of premature convergence.
  • The concept of Bloat
  • Some recent interpretations (crossover bias theory).
  • Methods to counteract bloat (parallel models, multiobjective optimization, parsimony pressure, Tarpeian methods).
  • Outline of other Evolutionary methods:
  • Evolution Strategies.
  • Evolutionary Programming.
  • A general discussion of the possible applications.

6 Deepening of some general concepts of Machine Learning

  • The concept of learning.
  • Learning a function.
  • The concept of generalization.
  • Supervised and unsupervised learning.
  • The case of classification and clustering.
  • Performance of a classifier.
  • Data splitting.
  • Training, test and validation sets. Definitions and motivations.
  • Crossvalidation and its variants.
  • Precision and Recall. True positives, true negatives, false positives, false negatives. F-measure and K-statistic.
  • The concept of feature and its importance.
  • The importance of feature selection.
  • Outline of the main feature selection methods.
  • Principal component based feature selection.
  • Correlation based feature selection.

7 Neural Networks

  • Introduction and Motivations.
  • A very light outline of the physical structure of human brain. Neurons.
  • Artificial neuron.
  • Perceptron
  • Single neuron model.
  • Perceptron learning rule.
  • Convergence theorem of perceptron.
  • The main activation functions.
  • Networks of neurons.
  • Adaline
  • General structure and functioning.
  • Delta learning rule. Gradient descent.
  • Linearly separable and non-linearly separable problems.
  • Hidden layer of neurons.
  • Universal Approximation Theorem.
  • Backpropagation. Formal justification and implementation.
  • Cyclic (or Recursive) Neural Networks.
  • Jordan networks.
  • Elman networks
  • Hopfield networks. The concept of associative memory. Hebb learning rule.
  • Non-Supervised Neural Networks
  • Competitive learning networks.
  • Kohonen networks (Self-Organizing Maps).

Learning outcomes

Soft Computing methods are nowadays used in many applicative domains, both in academia and industry, and their popularity is clearly growing with time. Among these domains, a particular interest has been recently dedicated to Soft Computing methods by a large community of researchers and practitioners in fields as Biology, Bioinformatics, Robotics, Electronics and Mechanic Engineering, Chemistry, Medicine, Economy, Marketing, Security Control, etc. The purpose of covering in an exhaustive manner all these applicative domains in this course would be conceited and impossible. Thus, the goal of this course is not introducing students to particular applications, but instead transferring to them knowledge on general computational methods, to give them the necessary tools and competencies to solve complex applications in the future. This should allow students to gain new important competencies, that should allow them to tackle complex problems in many applicative fields. This should give them a new opportunity for challenging professional activities, both in industry and academia.

Prerequisites

No particular propaedeutic knowledge is requested for attending this course, except a general knowledge of the fundaments of Computer Science and the basics of Mathematics, in particular Statistics.

Tipo esame:

X    Orale

  • Scritto
  • Scritto e orale

Tipo valutazione:

X    Voto finale

  • Giudizio finale
  • Nessuno

 

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 28/03/2011