Árboles de decisión: representación y expresividad

• Un árbol de decisión tiene como entrada las propiedades de un objeto o situación y su salida una decisión si/no
• Considérese el problema del aprendizaje de una definición del predicado WillWait. Se muestra el árbol de decisión donde cada nodo corresponde al test sobre el valor de una propiedad y cada rama se etiqueta con un valor posible. (Previamente hay que elegir las propiedades o atributos)
• El árbol representa un conjunto de implicaciones, cada una de ellas se corresponde con un camino que lleva a un nodo yes. Una de esas implicaciones sería

  

• La expresividad es básicamente proposicional (cada proposición es un test sobre un atributo). No podemos referirnos a dos o mas objetos

  

  Dados n atributos un árbol de decisión puede representar cualquier función Booleana. El problema es que hay funciones. Se necesita algún algoritmo ingenioso para encontrar hipótesis consistentes en ese espacio tan grande