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

Prelegent(ci)

Dominik Ślęzak, Sebastian Stawicki

Afiliacja

MIM UW

Termin

29 marca 2019 14:15

Pokój

p. 5820

Seminarium

Seminarium badawcze Zakładu Logiki: Wnioskowania aproksymacyjne w eksploracji danych

---

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.    

---