On ubiquity of implications (and how to avoid computing all of them)

Séminaire mensuel du LIRIS par Sergei O. Kuznetsov, National Research University Higher School of Economics (Moscow, Russia)

From 12/03/2013 at 10:30 to 12:00. Amphi Claude Chappe, INSA de Lyon
URL : https://liris.cnrs.fr/seminaire/seminaires-mensuels/seminaires-mensuels
Informations contact : S. Servigne et G. Damiand. guillaume.damiand@liris.cnrs.fr. +33 (0)4.72.43.26.62.

We discuss relationships of implications between attributes in object-attribute data tables to various important notions in computer science and artificial intelligence: functional dependencies, horn theories, emergent patterns, disjunctive version spaces, etc. The intractability of computing implication bases seems to be the main challenge for the use of implications in analyzing large data collections. Alternatives to generation of implication bases such as lazy-learning classification, target-driven generation of classifiers, and sampling are considered.