Basic introduction to learning with queries

Loading...

Из курса от партнера National Research University Higher School of Economics

Introduction to Formal Concept Analysis

19 оценки

National Research University Higher School of Economics

Introduction to Formal Concept Analysis

19 оценки

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.

Из урока

Interactive algorithms for learning implications

What if we don't have a direct access to a formal context, but still want to compute its concept lattice and its implicational theory? This can be done if there is a domain expert (or an oracle) willing to answer our queries about the domain. We'll study an approach known as learning with queries that addresses this setting. We'll get to know a few standard types of queries, and we'll see how an implication set can be learnt in time polynomial of its size with so called membership and equivalence queries. We'll then introduce attribute exploration, a method from formal concept analysis, which may require exponential time, but which uses different queries, more suitable for building implicational theories and representative samples of subject domains.

Basic introduction to learning with queries6:20

Learning binary patterns2:12

An easy case7:22

The general case8:56

Познакомьтесь с преподавателями

Sergei Obiedkov
Associate Professor
Faculty of computer science

[MUSIC]

This week, we will talk about how we can compute concepts and implications when

we don't really have data, but instead have access to someone who has data

or at least knowledge about the domain we want to conceptualize.

In this case, we will communicate with this, let's call him or

her expert, through formalized interactive procedures.

Our goal will be to get enough domain knowledge to be able to compute

the concept lattice of the domain and to find out the implications valid in it.

But we'll take a slightly broader perspective and

will present these interactive procedures in the context of what is called learning

with queries, which is a rather well- known subfield of machine learning.

In classical supervised machine learning, our goal is to build

a classifier that can classify objects into several predefined classes.

For simplicity, assume that we have only two classes:

objects that have a certain target property (positive examples) and

those without this property (negative examples).

For instance, we may want to classify pictures into two groups:

those that have an image of a pipe and those that don't.

The picture on the left is then a positive example

(it is not a pipe, but it is an image of a pipe), while the one on the right is not.

In the classical setup, we are given a training dataset divided into positive and

negative examples and we want to learn to classify new, previously unseen examples.

Learning with queries originates from the works of Dana Angluin and her colleagues.

Here, we still want to learn to classify new examples, but

we no longer have a training dataset.

Instead, we have access to an oracle capable of answering

certain types of questions.

Our goal is to design an algorithm that asks as few questions as possible,

but enough to be able to build a reliable classifier based on answers provided.

There may be different types of questions that the oracle might be

willing to answer.

In a membership query,

we ask the oracle to label an example as positive or negative.

If, say, we want to learn to recognize dogs,

we can show a picture of an animal and ask the oracle whether it's a dog.

It's called a membership query, because we essentially ask if a certain object is

a member of the class whose description we want to learn.

In principle, we can use membership queries to build a training data set,

which can then be used with any standard supervised machine learning

algorithm to build a classifier.

Another important type of queries is the equivalence query.

Here, we suggest a hypothesis H and asked the oracle whether it

describes precisely the positive examples of the target property.

If the answer is “yes”, our learning is complete:

we can use the hypothesis H to classify any new example:

if the example matches the hypothesis, it is classified as positive;

otherwise, it is classified as negative.

If, however, the answer is “no”, there may be two cases.

It might be that our hypothesis is too restrictive and there are positive

examples of the target property that fail to satisfy the hypothesis.

These are called positive counterexamples.

Or it might happen that our hypothesis is too general and

it matches some objects that do not belong to the class being learned.

Such objects are called negative counterexamples.

If the oracle answers “no” to an equivalence query,

it has to provide a counterexample, either positive or negative.

It's up to the oracle to choose which counterexample it provides.

Again, suppose we want to learn to recognize dogs,

and we've come up with the idea that

dogs are precisely all animals with four legs and curly hair.

Why would we have such a strange idea?

Well, because some of the dogs are indeed like this, and,

maybe, these are the only dogs we've seen so far.

But if we ask the oracle to verify this hypothesis,

it may point out that other kinds of dogs do exist and will show us one of them,

which will be a positive counterexample to our hypothesis.

Or it may show us someone with four legs and

curly hair who is nevertheless not a dog—

this will be a negative counterexample.

When posing an equivalence query, we have no control on which kind of

counterexample, positive or negative, we'll get in return.

If we are looking specifically for negative counterexamples,

we can pose a subset query instead.

That is, we ask if the set of objects satisfying our hypothesis

is a subset of the class being learned.

For example,

we might want to ask if all animals with four legs and curly hair are dogs,

that is, whether having four legs and curly hair is a sufficient condition for

being a dog.

In this case, we may get a lamb as a counterexample, but not, say, a dachshund.

If we are interested in positive counterexamples,

we may pose a superset query.

This amounts to asking if the class of objects satisfying our hypothesis

includes the target class, the one being learned.

In other words, in a superset query,

we ask if H is a necessary condition for being an instance of the target class;

if, say, it is necessary for a dog to have curly hair and four legs.

Any counterexample must be negative:

something that satisfies the hypothesis, but still not in the class.

[MUSIC]

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

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

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

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

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

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