The 15th International Conference on

Algorithmic Learning Theory
andThe 7th International Conference on

Discovery Science
Padova University, Padova, Italy
October 2 - 5, 2004
ALT ’04 / DS ’04 – Conference Program

The 15th International Conference on Algorithmic Learning Theory (ALT’04) and the 7th International Conference on Discovery Science will be held at Padova University, Padova, Italy, October 2 - 5, 2004 as part of the
Padova Dialogues. The Conferences are sponsored by theInstitute for Theoretical Computer Science, University atLübeck, by the Division of Computer Science, Hokkaido
University, Department of Information Engineering of the
University of Padova, Yokohama National University, andthe Research Institute on High Performance Computing
and Networking of the Italian National Research Council(ICAR-CNR)
This ALT conference is the 15th in a series of annual meetings established in 1990. For information concerning previous ALT meetings visit the Archives of ALT conferences
at http://www.tcs.uni-luebeck.de/pages/thomas/
The ALT series is focusing on all areas related to algorithmic learning theory including (but not limited to):the design and analysis of learning algorithms, computational models of machine learning (e.g., on-line learning, learning via queries, inductive inference, statisticallearning), specific algorithmic approaches (e.g., marginbased algorithms, MDL estimation), learning complex
models (e.g., neural networks, Bayesian networks, logical formulae, grammars, instance-based models), machine
discovery, and applications of machine learning to otherfields (e.g., data mining, web mining, bioinformatics).
The ALT conference program comprises 29 lectures selected by its program committee from 91 submissions.
This DS conference is the seventh in a series of annual
meetings established by the Discovery Science Project ofJapan in 1998. The DS conferences provide an open forum
for intensive discussions and interchange of new information among researchers working in the area of Discovery
Science including (but not limited to) the following top-

ics: logic for/of knowledge discovery; knowledge discovery
by inferences; abductive reasoning; heuristic search; constructive programming as discovery; knowledge discovery
from texts and the Web; knowledge discovery from unstructured and multimedia data; knowledge discovery indatabases; data mining; data and knowledge visualization;
active mining; knowledge discovery in network environments; intelligent network agents; machine learning; statistical methods and neural networks for knowledge discovery; Bayesian networks; knowledge discovery and human interaction; human factors in knowledge discovery;
philosophy and psychology of discovery; chance discovery;
scientific discovery; application of knowledge discovery tonatural and social sciences.
The DS conference program comprises 20 long papers and
19 regular papers selected by its program committee from80 submissions.
Additionally, we are are fortunate to present five invitedlectures by:
Nicolò Cesa-Bianchi (Univ. degli Studi di Milano, Italy)
Pedro Domingos (Univ. of Washington, Seattle, USA)Luc De Raedt (Univ. Freiburg, Freiburg, Germany)
Ayumi Shinohara (Kyushu Univ. Fukuoka, Japan)
Esko Ukkonen (Univ. of Helsinki, Helsinki, Finland)
which are shared by both conferences.
The E.M. Gold Award winner in 2004 is Hubie Chen. Congratulations !!!
For any further information as well as for registration,
we refer to the following web-pages:
http://www.tcs.uni-luebeck.de/pages/alt04.html
http://www.slab.dnj.ynu.ac.jp/DS04/
http://thepadovadialogues.dei.unipd.it/

Saturday, October 2
ALT ’04 and DS ’04 Joint Program

Saturday, October 2, Morning
REGISTRATION:
from 8.30 to 13.00 and from 18.30 to 20.30 at the Department of Information Engineering of the University of Padova
9.00–9.10:

Opening of Dialogues 2004: Alberto Apostolico

SESSION 1: Saturday, October 2, Morning
Tutorial on Statistical Bases of Machine Learning
Chair: John Case
9.10–11.10: Bruno Apolloni
Foundations
Short Break
11.20–12.50: Bruno Apolloni and Dario Malchiodi
Machine Learning
Lunch Break (at your own)
SESSION 2: Saturday, October 2, Afternoon
Chair: Einoshin Suzuki
13.50–14.50: Invited Talk by Pedro Domingos
Learning, Logic, and Probability: A Unified View
Short BreakSESSION 3: Saturday, October 2, Afternoon
Tutorial on Statistical Mechanical Methods in Learning
Chair: Shai Ben-David
15.00–16.00: Toshiyuki Tanaka
Statistical Learning in Digital Wireless Communications
16.00–17.00: Yoshiyuki Kabashima
A BP-Based Algorithm for Performing Bayesian Inference in Large Networks of Perceptron-Type
Short Break
17.10–18.10: Manfred Opper
Approximate Inference in Probabilistic Models
18.30–20.30: Reception

17.10–17.35: Amos Fiat and Dmitry Pechyony

Program

Decision Trees: More Theoretical Justification for Practical Algorithms

SESSION 1: Sunday, October 3, Morning

17.35–18.00: Daniil Ryabko

Chair: Steffen Lange
9.00–10.00: Invited Talk by Ayumi Shinohara

Application of Classical Nonparametric Predictors to
Learning Conditionally I.I.D. Data

String Pattern Discovery

18.00–18.25: Amiran Ambroladze and John Shawe-Taylor

Coffee BreakComplexity of Pattern Classes and Lipschitz Property

SESSION 2: Sunday, October 3, Morning

18.25–18.50: Jan Poland and Marcus Hutter

Inductive Inference I

On the Convergence Speed of MDL Predictions for
Bernoulli Sequences

Chair: Sandra Zilles
10.40–11.05: Sanjay Jain and Efim Kinber

19.00–20.00: ALT & DS Business Meeting

Learning Languages from Positive Data and Negative
Counterexamples

SESSION 7: Monday, October 4, Morning

11.05–11.30: M. R. K. Krishna Rao

Chair: Rocco Servedio

Inductive Inference of Term Rewriting Systems from Positive Data

9.00–9.25:
Maria-Florina Balcan, Avrim Blum, andSantosh Vempala

Short BreakOn Kernels, Margins, and Low-dimensional Mappings

SESSION 3: Sunday, October 3, Morning

9.25–9.50:

Inductive Inference II

Estimation of the Data Region Using Extreme-value Distributions

Chair: Peter Flach

Statistical Analysis of Unlabeled Data I

Kazuho Watanabe and Sumio Watanabe

11.40–12.05: Eric Martin, Arun Sharma, and Frank
StephanCoffee BreakOn the Data Consumption Benefits of Accepting Increased
Uncertainty

Statistical Analysis of Unlabeled Data II

12.05–12.30: Steffen Lange and Sandra Zilles

10.30–10.55: Victor Maslov and Vladimir V’yugin

Comparison of Query Learning and Gold-style Learningin Dependence of the Hypothesis Space

Maximum Entropy Principle in Non-Ordered Setting

12.30–12.55: Yasuhito Mukouchi and Masako Sato
Learning Languages generated by Elementary Formal Systems and its Application to SH Languages
Lunch BreakSESSION 4: Sunday, October 3, Afternoon
Chair: Arun Sharma
14.30–15.30: Invited Talk by Nicoló Cesa-Bianchi
Applications of Regularized Least Squares in Classification
Problems
Short BreakSESSION 5: Sunday, October 3, Afternoon

SESSION 8: Monday, October 4, Morning
Chair: Eiji Takimoto

10.55–11.20: Marcus Hutter and Andrej Muchnik
Universal Convergence of Semimeasures on Individual
Random Sequences
Short BreakSESSION 9: Monday, October 4, Morning
Online Sequence Prediction
Chair: Nicolò Cesa-Bianchi
11.30–11.55: Yuri Kalnishkan,
Michael V. Vyugin

Vladimir Vovk,

andA Criterion for the Existence of Predictive Complexity for
Binary GamesPAC Learning and Boosting I

11.55–12.20: Chamy Allenberg-Neeman and Benny Neeman

Chair: Gabor Lugosi

Full Information Game with Gains and Losses

15.40–16.05: Kohei Hatano and Osamu Watanabe

12.20–12.45: Marcus Hutter and Jan Poland

Learning r-of-k Functions by Boosting

Prediction with Expert Advice by Following the Perturbed
Leader for General Weights

16.05–16.30: Eiji Takimoto, Syuhei Koya, and Akira
Maruoka
Boosting Based on Divide and Merge

Lunch BreakSESSION 10: Monday, October 4, Afternoon

Coffee Break

Chair: Hiroshi Motoda

SESSION 6: Sunday, October 3, Afternoon

14.15–15.15: Invited Talk by Luc De Raedt

Statistical Supervised Learning

Probabilistic Inductive Logic Programming

Chair: Akira Maruoka

Short BreakSESSION 11: Monday, October 4, Afternoon
Approximate Optimization Algorithms I
Chair: Susumu Hayashi
15.25–15.50: Mark Herbster

10.55–11.20: Marta Arias and Roni Khardon
The Subsumption Lattice and Query Learning
11.20–11.45: Akinobu Miyata, Jun Tarui, Etsuji Tomita
Learning Boolean Functions in AC 0 on Attribute andClassification Noise
Short Break

Relative Loss Bounds and Polynomial-time Predictions forthe k-lms-net Algorithm

SESSION 16: Tuesday, October 5, Morning

15.50–16.15: Hans Ulrich Simon

Chair: Thomas Zeugmann

On the Complexity of Working Set Selection

11.55–12.55: Invited Talk by Esko Ukkonen

Coffee Break

Hidden Markov Modelling Techniques for Haplotype Analysis

SESSION 12: Monday, October 4, Afternoon
Approximate Optimization Algorithms II
Chair: Setsuo Arikawa
16.55–17.20: Nikolas List
Convergence of a Generalized Gradient Selection Approach for the Decomposition Method
17.20–17.45: Keisuke Yamazaki and Sumio Watanabe
Newton Diagram and Stochastic Complexity in Mixture of
Binomial Distributions
Short BreakSESSION 13: Monday, October 4, Afternoon
Logic Based Learning I
Chair: Peter Flach
17.55–18.20: Andrei Bulatov, Hubie Chen, and Vı́ctor
DalmauLearnability of Relatively Quantified Generalized Formulas
18.20–18.45: Judy Goldsmith, Robert H. Sloan, Balázs
Szörényi, and György Turán
New Revision Algorithms

Conference Dinner from 20.00 on
SESSION 14: Tuesday, October 5, Morning
Query and Reinforcement Learning
Chair: Rüdiger Reischuk
9.00–9.25:

Satoshi Matsumoto and Takayoshi Shoudai

Learning of Ordered Tree Languages with Height-Bounded
Variables using Queries
9.25–9.50:

Jérôme Besombes and Jean-Yves Marion

Learning Tree Languages from Positive Examples andMembership Queries
9.50–10.15: Ana Iglesias, Paloma Martı́nez, Ricardo
Aler, and Fernando Fernández
Learning Content Sequencing in an Educational Environment According to Student Needs
Coffee BreakSESSION 15: Tuesday, October 5, Morning
Learning and Logic
Chair: Hans Ulrich Simon

AdjornPROGRAM17.10–17.35: Son Bao Pham and Achim Hoffmann
Extracting Positive Attributions from Scientific Papers

SESSION 1: Sunday, October 3, Morning

17.35–18.00: Thanh-Nghi Do and François Poulet

Chair: Steffen Lange
9.00–10.00: Invited Talk by Ayumi Shinohara

Enhancing SVM with Visualization
18.00–18.25: Mina Akaishi, Ken Satoh, and Yuzuru
TanakaString Pattern Discovery
Coffee BreakSESSION 2: Sunday, October 3, Morning

An Associative Information Retrieval based on the Dependency of Term Co-occurrence

Discovery Science in Reality I

18.25–18.50: Tri M. Cao, Eric Martin, and Paul Compton

Chair: Luc De Raedt

On the Convergence of Incremental Knowledge Base Construction

10.40–11.05: Taneli Mielikäinen
Privacy Problems
Databases

with

Anonymized

Transaction

19.00–20.00: ALT & DS Business Meeting
SESSION 7: Monday, October 4, Morning

11.05–11.30: Ruggero G. Pensa, Jérémy Besson, and JeanFrançois Boulicaut

Introductory Presentations of Regular Papers on
Pattern Mining and Machine Learning Algorithms

A Methodology for Biologically Relevant Pattern Discovery from Gene Expression Data

Chair: Einoshin Suzuki

Short BreakSESSION 3: Sunday, October 3, Morning
Classification

9.00–9.05:
gio Satta

Alberto Apostolico, Cinzia Pizzi, and Gior-

Optimal Discovery of Subword Associations in Strings(Extended abstract)

11.40–12.05: Fang Chu, Yizhou Wang, and Carlo Zaniolo

9.05–9.10:
Floris Geerts, Bart Goethals, and Taneli
Mielikäinen

Mining Noisy Data Streams via a Discriminative Model

Tiling Databases

12.05–12.30: Albrecht Zimmermann and Luc De Raedt

9.10–9.15:
Benoı̂t Vaillant,Stéphane Lallich

Chair: Sanjay Jain

CorClass: Correlated Association Rule Mining for Classification

Philippe Lenca,

and

A Clustering of Interestingness Measures

12.30–12.55: Jesús Cerquides and Ramon Lòpez deMàntaras

9.15–9.20: Yoshikazu Shima, Shinji Mitsuishi, Kouichi
Hirata, and Masateru Harao

Maximum a Posteriori Tree Augmented Naive Bayes Classifiers

Extracting Minimal and Closed Monotone DNF Formulas

Lunch BreakCharacterizations of Multivalued Dependencies and Related Expressions (Extended Abstract)

SESSION 4: Sunday, October 3, Afternoon
Chair: Arun Sharma
14.30–15.30: Invited Talk by Nicoló Cesa-Bianchi
Applications of Regularized Least Squares in Classification
Problems
Short Break

9.20–9.25:

José Luis Balcázar and Jaume Baixeries

9.25–9.30: Fabrice Muhlenbach, Stéphane Lallich, andDjamel A. Zighed
Outlier Handling in the Neighbourhood-based Learning ofa Continuous Class
9.30–9.35:

Minho Kim and R.S. Ramakrishna

SESSION 5: Sunday, October 3, Afternoon

A New Clustering Algorithm based on Cluster Validity Indices

Clustering

9.35–9.40:

Chair: Carlo Zaniolo

An Efficient Rules Induction Algorithm for Rough Set
Classification

15.40–16.05: Hisashi Koga, Tetsuo Ishibashi, and Toshinori Watanabe
Fast Hierarchical Clustering Algorithm using LocalitySensitive Hashing

Songbo Tan and Jun Gu

9.40–9.45:
Ricardo Blanco-Vega, José HernándezOrallo, and Marı́a José Ramı́rez-Quintana

16.05–16.30: SiQuang Le and TuBao HoAnalysing the Trade-off between Comprehensibility and
Accuracy in Mimetic Models

Measuring the Similarity for Heterogenous Data: An Ordered Probability-Based Approach

9.45–9.50: Jinu Joo, Jun Zhang, Jihoon Yang, and Vasant Honavar

Coffee BreakSESSION 6: Sunday, October 3, Afternoon

Generating AVTs Using GA for Learning Decision TreeClassifiers with Missing Data

Knowledge Acquisition

Coffee Break

Chair: Ramon Lòpez de Màntaras

SESSION 8: Monday, October 4, Morning

Introductory Presentations of Regular Papers on
Web Mining, Applications of Predictive Methods,
and Interdisciplinary Approaches
Chair: Einoshin Suzuki
10.30–10.35: Masayuki Hirose and Einoshin Suzuki

Chair: Hiroshi Motoda
14.15–15.15: Invited Talk by Luc De Raedt
Probabilistic Inductive Logic Programming
Short Break

Using WWW-Distribution of Words in Detecting Peculiar
Web Pages

SESSION 11: Monday, October 4, Afternoon

10.35–10.40: Shoujian Yu, Jianwei Liu, and Jiajin Le

Chair: Akihiro Yamamoto

DHT Facilitated Web Service Discovery Incorporating Semantic Annotation

15.25–15.50: Kouzou Ohara, Yukio Onishi, Noboru
Babaguchi, and Hiroshi Motoda

10.40–10.45: Ryutaro Ichise, Masahiro Hamasaki, andHideaki Takeda

Constructive Inductive Learning based on Meta-Attributes

Feature Construction and Generation

Discovering Relationships among Catalogs

15.50–16.15: Gexiang Zhang, Laizhao Hu, and Weidong
Jin

10.45–10.50: Chiara Cumbo, Salvatore Iiritano, andPasquale Rullo

Resemblance Coefficient and a Quantum Genetic Algorithm for Feature Selection *Reasoning-based Knowledge Extraction for Text Classification

Coffee Break

10.50–10.55: Ye Du, Huiqiang Wang, and Yonggang Pang

SESSION 12 & 13: Monday, October 4, Afternoon

A Useful System Prototype for Intrusion Detection - Architecture and Experiments *16.55–18.45: Poster Presentations of Regular Papers

10.55–11.00: Sanghack Lee, Jihoon Yang, and Sung-Yong
Park
Discovery of Hidden Similarity on Collaborative Filtering
to Overcome Sparsity Problem
11.00–11.05: Marcelo A. T. Aragão and Alvaro A. A. Fernandes
Seamlessly Supporting Combined Knowledge Discovery
and Query Answering: A Case Study

Conference Dinner from 20.00 on
SESSION 14: Tuesday, October 5, Morning
Outlier Detection
Chair: Hiroki Arimura
9.25–9.50:
PizzutiFabrizio Angiulli, Stefano Basta, and Clara

Improving Prediction of Distance-Based Outliers

11.05–11.10: Charles-David Wajnberg, Vincent Corruble,
Jean-Gabriel Ganascia, and C. Ulises Moulines

9.50–10.15: Fabrizio Angiulli, Gianluigi Greco, and Luigi
Palopoli

A Structuralist Approach towards Computational Scientific Discovery

Detecting Outliers via Logical Theories and its Data Complexity

11.10–11.15: Radoslaw Piotr Katarzyniak

Coffee Break

Extracting Modal Implications and Equivalences from
Cognitive Minds

SESSION 15: Tuesday, October 5, Morning

Short BreakDiscovery Science in Reality II

SESSION 9: Monday, October 4, Morning

Chair: Achim Hoffmann

Pattern Mining

10.55–11.20: Gilles Caporossi, Denis Alamargot, andDavid Chesnet

Chair: Esko Ukkonen
11.30–11.55: Andreas Karwath and Luc De Raedt

Using the Computer to Study the Dynamics of the Handwriting Processes

Predictive Graph Mining

11.20–11.45: Przemyslaw Kazienko

11.55–12.20: Takeaki Uno, Tatsuya Asai, Yuzo Uchida,and Hiroki Arimura

Product Recommendation in E-Commerce Using Direct
and Indirect Confidence for Historical User Sessions

An Efficient Algorithm for Enumerating Closed Patternsin Transaction Databases

Short Break12.20–12.45: Shunsuke Inenaga, Hideo Bannai, HeikkiHyyrö, Ayumi Shinohara, Masayuki Takeda, Kenta Nakai,and Satoru Miyano
Finding Optimal Pairs of Cooperative and Competing Patterns with Bounded Distance

SESSION 16: Tuesday, October 5, Morning
Chair: Thomas Zeugmann
11.55–12.55: Invited Talk by Esko Ukkonen
Hidden Markov Modelling Techniques for Haplotype Analysis

Lunch Break
AdjornSESSION 10: Monday, October 4, Afternoon

Acknowledgments

DS 2004 Program Committee:

Conference Chair ALT 2004:

Einoshin Suzuki (Yokohama National Univ., Japan)
Chair
Elisa Bertino (Univ. of Milan, Italy)
Wray Buntine (Helsinki Institute of Information
Technology, Finland)
Vincent Corruble (Univ. of Pierre et Marie Curie, Paris,
France)Manoranjan Dash (Nanyang Technological Univ.,
Singapore)
Luc De Raedt (Albert-Ludwigs Univ. of Freiburg,
Germany)
Andreas Dress (Max Planck Institute for Mathematics in
the Sciences, Leipzig, Germany)
Sašo Džeroski (Jožef Stefan Institute, Slovenia)
Tapio Elomaa (Tampere Univ. of Technology, Finland)
Johannes Fürnkranz (Technical Univ. of Darmstadt,
Germany)
Gunter Grieser (Technical Univ. of Darmstadt,
Germany)
Fabrice Guillet (Ecole Polytechnique of the Univ. ofNantes, France)
Mohand-Said Hacid (Univ. of Claude Bernard, Lyon,
France)Achim Hoffmann (Univ. of New South Wales, Australia)
Eamonn Keogh (Univ. of California, Riverside, USA)
Ramamohanarao Kotagiri (Univ. of Melbourne,
Australia)
Aleksandar Lazarević (Univ. of Minnesota, USA)
Michael May (Fraunhofer Institute for AutonomousIntelligent Systems, Germany)
Hiroshi Motoda (Osaka Univ., Japan)
Jan Rauch (Univ. of Economics, Prague, Czech
Republic)
Domenico Saccá (ICAR-CNR and Univ. of Calabria,
Italy)
Tobias Scheffer (Humboldt Univ. of Berlin, Germany)
Rudy Setiono (National Univ. of Singapore, Singapore)
Masayuki Takeda (Kyushu Univ., Japan)
Kai Ming Ting (Monash Univ., Australia)
Ljupčo Todorovski (Jožef Stefan Institute, Slovenia)
Hannu Toivonen (Univ. of Helsinki, Finland)
Akihiro Yamamoto (Kyoto Univ., Japan)
Djamel A. Zighed (Lumière Univ., Lyon, France)

Akira Marouka, Tohoku University, Sendai, Japan

Conference Chair DS 2004:
Setsuo Arikawa, Kyushu University, Fukuoka, Japan

Local Arrangement Chair:
Massimo Melucci, University of Padova, Italy
melo@dei.unipd.it

ALT 2004 Program Committee:
Shai Ben-David (Univ. of Waterloo, Canada) Co-ChairJohn Case (Univ. of Delaware, USA) Co-Chair
Nader Bshouty (Technion, Israel)
Michael Collins (MIT, USA)
Sanjoy Dasgupta (UC San Diego, USA)Peter Flach (Univ. of Bristol, UK)
Steffen Lange (DFKI, Saarbrücken, Germany)
Jon Langford (TTI Chicago, USA)
Gabor Lugosi (UPF, Barcelona, Spain)Rüdiger Reischuk (Univ. at Lübeck, Germany)
Rocco Servedio (Columbia Univ., USA)
Arun Sharma (Queensland Univ. of Technology,
Brisbane, Australia)
Ayumi Shinohara (Kyushu Univ., Japan)
Eiji Takimoto (Tohoku Univ., Japan)
Sandra Zilles (Univ. Kaiserslautern, Germany)
The continuing success of these ALT-meetings has been
managed and supervised by its

ALT Steering Committee:
Thomas Zeugmann (Hokkaido Univ., Japan, Chair)
Arun Sharma (Queensland Univ. of Technology,
Brisbane, Australia, Co-Chair)
Naoki Abe (IBM Thomas J. Watson Research Center,
Yorktown, USA)
Klaus Peter Jantke (DFKI, Saarbrücken, Germany)
Roni Khardon (Tufts University, Medford, USA)
Phil Long (National Univ. of Singapore)
Hiroshi Motoda (Osaka University, Japan)
Akira Maruoka (Tohoku Univ., Sendai, Japan)
Luc De Raedt (Albert-Ludwigs-Univ. Freiburg,
Germany)
Takeshi Shinohara (Kyushu Institute of Technology,
Iizuka, Japan)
Osamu Watanabe (Tokyo Institute of Technology, Japan)
and the current PC Chairs, who are one-year members of
the ALT steering committee, i.e.,
Shai Ben-David (Univ. of Waterloo, Canada)
John Case (Univ. of Delaware, USA)The continuing success of these DS-meetings has been
managed and supervised by its

DS Steering Committee:
Hiroshi Motoda (Osaka Univ. Japan, Chair)
Alberto Apostolico (Univ. of Padova, Italy and Purdue
Univ., USA)
Setsuo Arikawa (Kyushu Univ. Japan)
Achim Hoffmann (Univ. of New South Wales, Australia)
Klaus Peter Jantke (DFKI, Germany)
Masahiko Sato (Kyoto Univ. Japan)
Ayumi Shinohara (Kyushu Univ. Japan)
Carl H. Smith (Univ. of Maryland, College Park, USA)
Thomas Zeugmann (Hokkaido Univ., Japan)
We look forward to seeing you in Padova.