You are not logged in | Log in

Zespoły klasyfikatorów: NP-trudność i nowe przykłady

Speaker(s)
Dominik Ślęzak, Sebastian Stawicki
Affiliation
MIM UW
Date
March 29, 2019, 2:15 p.m.
Room
room 5820
Seminar
Research Seminar of the Logic Group: Approximate reasoning in data mining

Jest to kontynuacja poprzednich referatów związanych z pojęciem bireduktu, a konkretnie zespołów jak najprostszych bireduktów wyuczanych z danych treningowych w taki sposób, by dany zespół umiał dla każdego przypadku treningowego podjąć słuszną decyzję w wyniku głosowania większościowego. Podczas wystąpienia przypomnimy twierdzenie mówiące o tym, że problem wyznaczania optymalnego w powyższym sensie zespołu bireduktów jest NP-trudny. Sformułujemy także nowy analogiczny rezultat dotyczący zespołów drzew decyzyjnych. Poświęcimy przy tym szczególną uwagę analizie przykładów optymalnych zespółow, w których reguły klasyfikacyjne kodowane przez drzewa decyzyjne bądź biredukty nie wskazują na decyzje większościowe.