• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)SearchMenu

Probably Approximately Correct Learning of Implication Theories from Queries

Student: Ramil Yarullin

Supervisor: Sergei Obiedkov

Faculty: Faculty of Computer Science

Educational Programme: Applied Mathematics and Information Science (Bachelor)

Year of Graduation: 2017

In this work, we provide an analysis of the number of samples that need to be generated in stochastic equivalence testing to guarantee probably approximately correct identification of unknown concept with a given accuracy and confidence. This led to a theoretical improvement of the existing approach in terms of the number of samples to be generated. Within the experiments, we apply this modification to Horn1 algorithm for computing probably approximately correct bases and compare it with the existing approach and the Attribute Exploration algorithm on artificial and real data. We primarily focus on such metrics as the number of queries to implication oracle and Horn distance. We also show some cases when PAC bases can be useful and useless from a practical point of view. Keywords: Formal Concept Analysis, Implications, Concept Learning, Query Learning, PAC Learning

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses