42001 - Computational Learning (APC)

The main goal of this course is to introduce students to the field of computational learning theory. More precisely, after following the course students should:

• Know the main formal models of computational learning, describe the general contexts to which they apply, and be able to relate them to learning tasks usually studied in Machine Learning and Statistics.
• Know the main learning algorithms developed for these models, and be able to reason about their correctness and efficiency.
• Know the limitations of these models, explaining them in complexity-theoretic terms whenever necessary.
• Know the main algorithmic challenges in Data Mining, describing them in terms similar to those of computational learning theory.
• Know the main current research fields in computational learning theory and data mining, and be ready to contribute to them with appropriate supervision.
• As procedural goals, student should improve their ability to:
• Relate concepts from different fields in / related to computing, (in this case, algorithmics, statistics, theory of computation, and artificial intelligence).
• Integrate information from different sources (courses, articles and books, Internet search, expert advice...)
• Formulate and answer questions in the borderline of the current knowledge of a discipline

1. Mathematical preliminaries

• Concepts from statistics and probability theory
• Concepts from discrete mathematics and theory of computation

2. Learning from examples and learning from queries

• Statistical learning
• Vapnik-Chervonenkis dimension and Occam's Razor
• The PAC model
• Learning from queries

3. Learning Boolean formulas

4. Learning finite-state machines

5. Complexity theory and learning

• Representation-dependent results: Learning and NP-completeness
• Representation-independent results: Learning and cryptography

6. Extensions of learning models

• Learning with noise
• Learning with irrelevant attributes

7. Practical learning methods with theoretical foundations

• Induction of decision trees
• Introduction to boosting
• Introduction to Support Vector Machines and Kernel Methods

8. Non-supervised learning

• Clustering
• Extraction of association rules and related models

9. Data Mining

• Data Mining tasks
• Current research trends

The 6 ECTS credits (180 hours) are divided in different types of activities: lectures (CP), reading and studying additional materials (articles and book chapters) to acquire complementary knowledge (Comp), solving problems (Prob), practical exercises in laboratory (Lab) and final test (Aval).

Lectures will introduce the main concepts of the course and will briefly revise additional topics. Also, problems will be proposed so that students solve them along the course. Finally, acquired knowledge will be applied using learning software and prospecting of data.

Evaluation will be based on the exercises and the activities in laboratory done along the course, and the final test. An average will be made for the final mark.

There will be a list of exercises per topics, and they must be handed over within a specific period of time (usually, after three weeks). The laboratory practicum process must be explained in a short report, explaining the tasks done and the results obtained.

The final exam will consist of a theoretical exposition of a topic related to those explained in class, and solving some problems.

• Hastie T., Tibshirani R., Friedman J.: The elements of statistical learning. Data mining, inference and prediction. Springer, 2001.
• Kearns M.J., Vazirani U.V.: An Introduction to Computational Learning Theory. The MIT Press, 1994.
• Witten I.H., Frank E.: Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, second edition. Morgan Kaufmann Publishers, 2005.
• Hand D., Mannila H., Smyth P.: Principles of Data Mining. The MIT Press, 2001.