International School "Eduardo R. Caianiello", 10th Course
and
Workshop of the PASCAL Network of Excellence

The Analysis of Patterns
Centre "Ettore Majorana" for Scientific Culture, Erice, Italy
October 28 - November 6, 2005

New Edition: BERTINORO 2007

Directors of the Course:
Nello Cristianini, University of California, Davis, USA
Raffaele Cerulli, Universita' di Salerno, Italy
John Shawe-Taylor, University of Southampton, UK

Director of the School "Eduardo Caianiello":
Maria Marinaro, Universita' di Salerno, Italy

PHOTOS

VIDEOS

Main Page

Course Description

Speakers

Course Directors

Venue

Scientific Program

work with nello

BERTINORO 2007

There will be three types of presentations: lectures, seminars and posters.
While the lectures aim at describing the emergent field of pattern analysis, seminars and posters report on recent research and related topic.

LECTURES

Gregory Chaitin (IBM T J Watson) - "Patterns, Randomness and Information"

Information, Complexity, Patterns, Randomness and Compression.And how these ideas can be traced back through Hermann Weyl to Leibniz in 1686, and connect them with Godel & Turing and with the question of how math compares & contrasts with physics and with biology.

Nello Cristianini - (University of California, Davis) - "The Analysis of Patterns"

Tijl De Bie (KU Leuven) - Patterns in Sets of Points

1 - "Patterns in sets of points: an overview"
"We illustrate the importance of optimization principles in the search for interesting patterns, more in particular for patterns in sets of points embedded in a metric space. This talk will be a journey along the types of patterns in point sets that can efficiently be searched for, and general principles will be outlined. We provide examples from dimensionality reduction, classification, clustering, and others. The emphasis will be on patterns that can be expressed in terms of linear functions of the data."

2-"Patterns in sets of points: the myriad virtues of eigenproblems" :-)
"In the second hour, one specific powerful type of optimization problem will be highlighted: the eigenvalue problem. A brief discussion of the computational aspects, and an overview of its applications in finding patterns in point sets will be provided. The talk will cover principal component analysis, canonical correlation analysis, Fisher's discriminant, partial least squares, and spectral clustering. We will emphasize connections between these algorithms where appropriate."

Esko Ukkonen (University of Helsinki) - Suffix tree and Hidden Markov techniques for pattern analysis

Suffix tree construction. Mention the new linear time array constructions -
- using suffix trees for finding motifs with gaps (some new observations: 0.5 - 1 hours).
- finding cis-regulatory motifs by comparative genomics (1 hour)
- Hidden Markov techniques for haplotyping

Nicolo' Cesa-Bianchi (University of Milano) - "On-line linear learning algorithms"

Prediction with expert advice. Learning with linear experts. The Perceptron algorithm and its extensions. On-line learning with kernels. Mistake bounds. From mistake bounds to risk bounds

John Shawe-Taylor (University of Southampton) - "Statistical Aspects of Pattern Analysis"

Abstract: The lectures will introduce the role of statistics in pattern analysis with a discussion of the difference between pattern significance and pattern stability. We will go on to discuss composite hypothesis testing and the Bonferroni correction. Concentration inequalities will be introduced and used to assess the statistical reliability of empirical estimates. We move to consider uniform convergence in order to analyse pattern stability. Rademacher complexity will be discussed as a theoretical tool for the bounding of uniform convergence.

Heikki Mannila (Helsinki University of Technology) - Finding frequent patterns from data

Discovery of frequent patterns = finding positive conjunctions that are true for a given fraction of the observations
- this basic idea can be instantiated in many ways: - finding frequent sets from 0/1 data (association mining) - finding frequent episodes in sequences - finding frequent subgraphs in graphs etc.
- efficient algorithms exist -- the levelwise approach
- theoretical analysis of the algorithms is not trivial - leads to connections to hypergraph transversals etc.
- the second part: how can the patterns be used?
- sometimes interesting in themselves - can be used to approximate the joint distribution - maximum entropy approaches - combining information from several patterns - ordering patterns

Bernhard Schoelkopf (MPI for Biological Cybernetics, Tubingen) - "Kernel Methods"

Dan Gusfield - (University of California, Davis) - Trees, Arrays, Networks and Optimization for Finding Patterns in
Biological Sequences

a) The use of suffix trees and integer programming for finding optimal virus signatures.
b) A current treatment of suffix-arrays and their uses. In the last several years simple linear-time algorithms for building suffix arrays have been developed making explicit suffix-trees mostly obsolete.
c) Algorithms for finding signatures (patterns) of historical recombination and gene-conversion in SNP (binary) sequences. The techniques here relate to graph-theory.

Colin de la Higuera (University Jean Monnet at Saint-Etienne) - "Grammatical Inference: a Tutorial"

The leactures will introduce the key ideas of grammatical inference and concentrate specially on the algorithmic aspects. Some algorithms that will be described are: The "State merging" family : Gold, Rpni, Edsm... The "Window" languages : Local and k-testable Learning with queries.

Alberto Apostolico (University of Padova and Georgia Tech) - "Algorithmic and Combinatorial Foundations of Pattern Discovery"

Edwin Hancock (University of York, UK) - ``Pattern Analysis with Graphs and Trees''
Spectral representations of graphs, Pattern spaces from graph spectra, Spectral approaches to matching, Heat kernel methods Probabilistic and spectral methods for graph matching and clustering. Applications in computer vision.

Raffaele Giancarlo (University of Palermo) - On Indexing and Compression: Two Sides of the Same Coin

SEMINARS

COLIN CAMPBELL Bayesian Methods in Bioinformatics
JAAK VILO Pattern discovery in bioinformatics
ROBERTO TAGLIAFERRI Neural Networks, Information measures and data distribution estimation
CESARE FURLANELLO Semi-supervised pattern classification for molecular profiling
SILVIA CANALE -- TBA

POSTERS

(TO BE ANNOUNCED....)