Nie jesteś zalogowany | Zaloguj się

On the depth of decision trees over infinite 1-homogeneous binary information systems

Prelegent(ci)
Mikhail Moshkov
Afiliacja
King Abdullah University of Science and Technology (KAUST)
Termin
20 grudnia 2019 14:00
Pokój
p. 5820
Seminarium
Seminarium badawcze Zakładu Logiki: Wnioskowania aproksymacyjne w eksploracji danych

We consider a class of infinite sets of attributes represented as information systems (the class of so-called infinite 1-homogeneous binary information systems), define the notion of a problem over an information system, and study decision trees solving these problems.

We prove that, for each information system from this class, in the worst case, the minimum depth of a decision tree (as a function on the number of attributes in a problem description) either grows as logarithm or grows linearly.

 

Please not the eralier than usual start of this lecture (14:00).

After the lecture we invite everybody to the Christmas Party.