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

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.    

---