Ja/nej-frågor som sorterar: beslutsträd

Gissa vilket djur jag tänker på — du får bara ja/nej-frågor.

Har det päls?
├─ ja: Säger det mjau?
│      ├─ ja: KATT
│      └─ nej: HUND
└─ nej: Kan det flyga?
       ├─ ja: FÅGEL
       └─ nej: FISK

Det är ett beslutsträd. Varje fråga delar upp i två högar. Datorer bygger sådana träd automatiskt av exempel — en av de äldsta sorterna av maskininlärning.

Bra fråga eller dålig? Med djuren katt, hund, fågel, fisk:

• «Har det päls?» delar 2–2. Bra.
• «Är det en katt?» delar 1–3. Sämre — du behöver fler frågor sedan.

Bästa frågan är den som delar högen så jämnt som möjligt. Bygg ett träd för fyra frukter (banan, äpple, jordgubbe, apelsin). Hur få frågor klarar du dig med? (Två räcker för fyra saker om varje fråga delar jämnt.)