Lista decyzyjna

Listy decyzyjne są reprezentacją funkcji boolowskich, których można łatwo nauczyć się na przykładach. Jednoczłonowe listy decyzyjne są bardziej wyraziste niż alternatywy i koniunkcje ; jednak 1-członowe listy decyzyjne są mniej wyraziste niż ogólna rozłączna postać normalna i koniunkcyjna postać normalna .

Język określony przez k-długą listę decyzyjną zawiera jako podzbiór język określony przez k-głębokie drzewo decyzyjne .

Listy decyzyjne dotyczące uczenia się mogą być używane do efektywnego uczenia się według atrybutów.

Definicja

Lista decyzyjna (DL) o długości $r$ ma postać:

  
     jeśli  $f 1$  to  wyprowadź  $b 1$  jeśli  $f 2$  to  wyprowadź  $b 2$  ...  jeśli  $f r$  to  wyprowadź  $b r$

gdzie $fa ja$ jest $i-$ tą formułą, a $b ja$ jest $i-$ tą wartością logiczną dla ${\ Displaystyle i \ in \ {1... r \}}$ . Ostatni przypadek if-then-else jest przypadkiem domyślnym, co oznacza, że formuła $f r$ jest zawsze równa true. A $k$ -DL to lista decyzyjna, w której wszystkie formuły mają co najwyżej $k$ wyrazów. Czasami „lista decyzyjna” jest używana w odniesieniu do 1-DL, gdzie wszystkie formuły są albo zmienną, albo jej negacją .

Zobacz też

Pęt decyzyjny

^ Ronald L. Rivest (listopad 1987). „Listy decyzyjne dotyczące uczenia się” (PDF) . Uczenie maszynowe . 2 (3): 229–246. doi : 10.1023/A:1022607331053 .
^ Adam R. Klivans i Rocco A. Servedio, „W kierunku efektywnego uczenia się list decyzyjnych i parzystości atrybutów”, Journal of Machine Learning Research 7 : 12: 587-602 ACM Digital Library pełny tekst

[1] Ronald L. Rivest (listopad 1987). „Listy decyzyjne dotyczące uczenia się” (PDF) . Uczenie maszynowe . 2 (3): 229–246. doi : 10.1023/A:1022607331053 .

[2] Adam R. Klivans i Rocco A. Servedio, „W kierunku efektywnego uczenia się list decyzyjnych i parzystości atrybutów”, Journal of Machine Learning Research 7 : 12: 587-602 ACM Digital Library pełny tekst