Redundancy in implications

Loading...

From the course by National Research University Higher School of Economics

Introduction to Formal Concept Analysis

18 оценки

National Research University Higher School of Economics

Introduction to Formal Concept Analysis

18 оценки

This course is an introduction into formal concept analysis (FCA), a mathematical theory oriented at applications in knowledge representation, knowledge acquisition, data analysis and visualization. It provides tools for understanding the data by representing it as a hierarchy of concepts or, more exactly, a concept lattice. FCA can help in processing a wide class of data types providing a framework in which various data analysis and knowledge acquisition techniques can be formulated. In this course, we focus on some of these techniques, as well as cover the theoretical foundations and algorithmic issues of FCA. Upon completion of the course, the students will be able to use the mathematical techniques and computational tools of formal concept analysis in their own research projects involving data processing. Among other things, the students will learn about FCA-based approaches to clustering and dependency mining. The course is self-contained, although basic knowledge of elementary set theory, propositional logic, and probability theory would help. End-of-the-week quizzes include easy questions aimed at checking basic understanding of the topic, as well as more advanced problems that may require some effort to be solved.

From the lesson

Implications

This week we'll continue talking about implications. We'll see that implication sets can be redundant, and we'll learn to summarise all valid implications of a formal context by its canonical (Duquenne–Guigues) basis. We'll study one concrete algorithm that computes the canonical basis, which turns out to be a modification of the Next Closure algorithm from the previous week. We'll also talk about what is known in database theory as functional dependencies, and we'll show how they are related to implications.

Redundancy in implications7:03

Pseudo-closed sets and canonical basis12:03

Preclosed sets8:43

Preclosure operator6:23

Meet the Instructors

Sergei Obiedkov
Associate Professor
Faculty of computer science

[MUSIC]

Last time we talked about implications of a formal context.

There may be a lot of implications valid in a formal context.

As an extreme case, consider a context which has no objects at all.

So in this context, A double

prime equals M for all

Subsets of M.

Well, in this case, because this context has no objects,

it has no counter example to any implication you may think of.

And therefore, all implication are valid in this context.

So if we have that a'' = m,

then A implies B for

all a and b.

And if M contains N attributes,

then there are two to the N possible subsets of M.

And so we have two to the n possible As, two the N possible Bs.

And this gives us two to the 2n possible implications.

A huge number if n is big.

But what's interesting is that they all follow from

a single implication, empty set implies m.

So when we have a formal context and we want to compute it's implicational theory,

we generally don't want to have to see all the implications.

We want to see a small sub-set.

From which a small subset of valid implications

from which all of other valid implication follow.

Such a fad is called an implication basis.

Let's give a formal definition.

So a set L of implications

A is called an implication basis.

If it satisfied three properties.

Well, first it must be sound.

It must include only valid implications.

if A implies B isn't L then or

formal context, G,M,I and

I should say although this is an implication

basis over formal context, G,M,I.

So if A implies B is an L, then this implication must be valid in G,M,I.

The second property is completeness.

Well, we need to ask for some kind of reverse property.

But we don't want to ask the reverse property exactly,

because we don't want L to contain all valid implications.

We want this set to be small, so we'll ask for something weaker.

If A-B is a valid implication

We don't need it to be contained in L but it must follow from L.

Okay, but now that the set of all valid implications satisfies these two

properties, and it may be huge, as in this case, we want something small, like this.

So to call L a basis, we'll need a third property.

And this is non-redundancy.

So that is a crucial perpeture for L to be basis.

A set is non redundant an implication set l is non redundant if you can't

remove an implication from it without losing the second property completeness.

So if we have an implication

A implies B in L.

This implication doesn't follow from a smaller set of implications.

So if you remove it from l you can't get it back.

It doesn't follow from what remains.

So in a way it's necessary.

You can't remove any implication without losing completeness.

So that's the meaning on nonredundancy.

Okay, and so this is the definition of an implication basis.

Another, if we were working with the formal context,

it's quite easy to check this property.

So it implies is volatile in G,M,I.

If a null if.

B is a subset of A double prime.

And so we can replace this condition in the first two properties by this one.

b is a subset of a double prime and

we'll still get the definition of an implication basis of a formal context.

[SOUND]

[MUSIC]

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play